$r-l+1$ such that each extended hyperedge is a self-neighbour of its
predecessor in $\mathcal{P}$, and this sequence is maximal.

Suppose the intervals in $I_{\mathrm{self}}$ are
$[l_{1},r_{1}],[l_{2},r_{2}],\ldots,[l_{a},r_{a}]$ such that $l_{1}\leq
r_{1}<l_{2}\leq r_{2}<\ldots<l_{a}\leq r_{a}$, where
$a=\left|I_{\mathrm{self}}\right|$. It is straightforward to verify that

$\displaystyle\sum_{i=1}^{a}\left(r_{i}-l_{i}+1\right)=R_{\mathrm{self}}.$
(26)

Define a subset $I^{(1)}_{\mathrm{self}}\subseteq I_{\mathrm{self}}$ by

$\displaystyle I^{(1)}_{\mathrm{self}}:=\left\\{[l,r]\in I_{\mathrm{self}}\mid
l=r\right\\}.$

The quantity $b$ is the size of $I^{(1)}_{\mathrm{self}}$, i.e.
$b:=\left|I^{(1)}_{\mathrm{self}}\right|$. Since $I^{(1)}_{\mathrm{self}}$ is
a subset of $I_{\mathrm{self}}$, by (26), we have

$\displaystyle b\leq R_{\mathrm{self}}.$ (27)

Note that $\ell\geq T/n\geq 40\log n\geq 20$. If $R_{\mathrm{out}}=0$, then
$I_{\mathrm{self}}$ contains only a single interval $[2,\ell]$. Thus $b=0$ and
we have $b\leq 2R_{\mathrm{out}}$. Otherwise $R_{\mathrm{out}}\geq 1$. By
property 3 above, for each $j\in[a]$, it holds that either $r_{j}=\ell$ or
${e}^{\mathrm{ext}}_{r_{j}+1}\in
N_{\mathrm{out}}\left({e}^{\mathrm{ext}}_{r_{j}}\right)$ (namely $r_{j}+1\in
S_{\mathrm{out}}$). This implies $b\leq R+1=R_{\mathrm{out}}+1\leq
2R_{\mathrm{out}}$, because there are at most one $(l_{j},r_{j})\in
I^{(1)}_{\mathrm{self}}$ satisfying $l_{j}=r_{j}=\ell$. Hence, in both cases,
we have

$\displaystyle b\leq 2R_{\mathrm{out}}.$ (28)

Combining (27) and (28) proves that
$b\leq\min\\{R_{\mathrm{self}},2R_{\mathrm{out}}\\}$.

Finally, we construct the the subsequence
${f}^{\mathrm{ext}}_{1}<{f}^{\mathrm{ext}}_{2}<\ldots<{f}^{\mathrm{ext}}_{m}$
from IPP $\mathcal{P}$. We construct a subset $\mathcal{F}$ by the following
procedure.

  * •

For each $i\in S_{\mathrm{out}}$, we add ${e}^{\mathrm{ext}}_{i}$ into
$\mathcal{F}$.

  * •

For each interval $[l,r]\in I_{\mathrm{self}}$, for all integers $j\in[l,r]$
such that $(j-l)$ is an odd number, we add ${e}^{\mathrm{ext}}_{j}$ into
$\mathcal{F}$. Note that by property 2, if $l>2$, ${e}^{\mathrm{ext}}_{l-1}$
is always in $\mathcal{F}$ because of the previous rule.

  * •

To finish, we sort all extended hyperedges in $\mathcal{F}$ to obtain
${f}^{\mathrm{ext}}_{1}<{f}^{\mathrm{ext}}_{2}<\ldots<{f}^{\mathrm{ext}}_{m}$.

We now verify the three properties in Lemma 36.

  * •

By the definition of IPP, for any $1\leq i,j\leq\ell$ satisfying
$\left|i-j\right|\geq 2$,
${e}^{\mathrm{ext}}_{i}\cap{e}^{\mathrm{ext}}_{j}=\emptyset$. Since
${f}^{\mathrm{ext}}_{1}<{f}^{\mathrm{ext}}_{2}<\ldots<{f}^{\mathrm{ext}}_{m}$
is a subsequence of $\mathcal{P}$, the first property holds.

  * •

Fix an index $2\leq j\leq m$. Suppose
${f}^{\mathrm{ext}}_{j-1}={e}^{\mathrm{ext}}_{j_{1}}$ and
${f}^{\mathrm{ext}}_{j}={e}^{\mathrm{ext}}_{j_{2}}$. If
$\left|j_{1}-j_{2}\right|\geq 2$, then
$\left|{f}^{\mathrm{ext}}_{i}\cap{f}^{\mathrm{ext}}_{i-1}\right|=0$. Assume
$j_{1}+1=j_{2}$, which means that ${e}^{\mathrm{ext}}_{j_{1}}$ and
${e}^{\mathrm{ext}}_{j_{2}}$ are neighbours in extended hypergraph. If
${e}^{\mathrm{ext}}_{j_{2}}\in N_{\mathsf{out}}({e}^{\mathrm{ext}}_{j_{1}})$,
by Observation 33, it holds that
$\left|{f}^{\mathrm{ext}}_{i}\cap{f}^{\mathrm{ext}}_{i-1}\right|=1$.
Otherwise, ${e}^{\mathrm{ext}}_{j_{2}}\in
N_{\mathsf{self}}({e}^{\mathrm{ext}}_{j_{1}})$. There must exist an interval
$[l,r]\in I_{\mathrm{self}}$ such that either $j_{1},j_{2}\in[l,r]$ or
$j_{1}\not\in[l,r]$ but $j_{2}\in[l,r]$. The first case is impossible because
we do not add two consecutive indices in any interval of $I_{\mathrm{self}}$.
The second case is also impossible because it implies $j_{1}=l-1$ and
$j_{2}=l$, but $l$ cannot be added.

  * •

All extendeds hyperedge in $S_{\mathrm{out}}$ are added into $\mathcal{F}$.
For each interval $[l,r]\in I_{\mathrm{self}}$,
$\lfloor\frac{r-l+1}{2}\rfloor$ extended hyperedges in $[l,r]$ are added into
$\mathcal{F}$. Hence, if $l\neq r$, the number of vertices in $[l,r]$ added to
$\mathcal{F}$ is at least $(r-l+1)/3$ (with $r=l+2$ being the worst case). By
(26), we have $m\geq R_{\mathrm{out}}+\frac{1}{3}(R_{\mathrm{self}}-b)$.

Hence, the subsequence
${f}^{\mathrm{ext}}_{1}<{f}^{\mathrm{ext}}_{2}<\ldots<{f}^{\mathrm{ext}}_{m}$
satisfies all the properties in Lemma 36. ∎

Now we are ready to prove Lemma 35.

###### Proof of Lemma 35.

Let
${f}^{\mathrm{ext}}_{1}<{f}^{\mathrm{ext}}_{2}<\ldots<{f}^{\mathrm{ext}}_{m}$
be the subsequence given in Lemma 36. For each ${f}^{\mathrm{ext}}_{i}$ and
$c\in[s]$, define a bad event $\mathcal{B}_{i}(c)$ that for all
$(j,w)\in{f}^{\mathrm{ext}}_{i}$, either $X_{j}(w)\neq Y_{j}(w)$ or
$X_{j}(w)=Y_{j}(w)=c$. Note that
${f}^{\mathrm{ext}}_{1}<{f}^{\mathrm{ext}}_{2}<\ldots<{f}^{\mathrm{ext}}_{m}$
is a subsequence in IPP $\mathcal{P}$, the probability of
$\mathcal{B}(\mathcal{P})$ can be bounded as follows

$\displaystyle\mathop{\mathrm{Pr}}\nolimits_{\mathcal{C}}\left[\mathcal{B}(\mathcal{P})\right]\leq\mathop{\mathrm{Pr}}\nolimits_{\mathcal{C}}\left[\forall
i\in[m],\exists c_{i}\in[s]\text{ s.t. }\mathcal{B}_{i}(c_{i})\right].$

By (24), it holds that $\ell\geq T/n\geq 40\log n\geq 20$. By the last
property in Lemma 36,
$m\geq\frac{1}{3}(R_{\mathrm{out}}+R_{\mathrm{self}})=\frac{\ell-1}{3}>6$. We
further truncate the last element ${f}^{\mathrm{ext}}_{m}$ and obtain the
following inequality

$\displaystyle\mathop{\mathrm{Pr}}\nolimits_{\mathcal{C}}\left[\mathcal{B}(\mathcal{P})\right]\leq\mathop{\mathrm{Pr}}\nolimits_{\mathcal{C}}\left[\forall
i\in[m-1],\exists c_{i}\in[s]\text{ s.t.
}\mathcal{B}_{i}(c_{i})\right]\leq\sum_{\bm{c}\in[s]^{m-1}}\mathop{\mathrm{Pr}}\nolimits_{\mathcal{C}}\left[\bigwedge_{i=1}^{m-1}\mathcal{B}_{i}(c_{i})\right],$
(29)

where the second inequality follows from the union bound, and
$\bm{c}=(c_{1},\dots,c_{m-1})\in[s]^{m-1}$. The truncation ensures that all
elements $(j,w)\in\cup_{i=1}^{m-1}{f}^{\mathrm{ext}}_{i}$ satisfy $j>0$. (See
Definition 30 of IPPs.)

Fix $\bm{c}\in[s]^{m-1}$, we bound the probability of the event
$\bigwedge_{i=1}^{m-1}\mathcal{B}_{i}(c_{i})$. For each $1\leq i<m$, we define

$\displaystyle{S}^{\mathrm{ext}}_{i}:=\begin{cases}{f}^{\mathrm{ext}}_{i}&\text{if
}i=1;\\\ {f}^{\mathrm{ext}}_{i}\setminus{f}^{\mathrm{ext}}_{i-1}&\text{if
}i>1.\end{cases}$

Since ${S}^{\mathrm{ext}}_{i}\subseteq{f}^{\mathrm{ext}}_{i}$, we have the
following bound

$\displaystyle\mathop{\mathrm{Pr}}\nolimits_{\mathcal{C}}\left[\bigwedge_{i=1}^{m-1}\mathcal{B}_{i}(c_{i})\right]\leq\mathop{\mathrm{Pr}}\nolimits_{\mathcal{C}}\left[\bigwedge_{i=1}^{m-1}\left(\forall(j,w)\in{S}^{\mathrm{ext}}_{i},\left(X_{j}(w)\neq
Y_{j}(w)\right)\lor\left(X_{j}(w)=Y_{j}(w)=c_{i}\right)\right)\right].$

By the first property in Lemma 36, all ${S}^{\mathrm{ext}}_{i}$ are mutually
disjoint. Now we list all the extended vertices
$\cup_{i=1}^{m-1}{S}^{\mathrm{ext}}_{i}$ as
$(j_{1},w_{1}),(j_{2},w_{2}),\ldots,(j_{M},w_{M})$, where
$0<j_{1}<j_{2}<\ldots<j_{M}$. For each $1\leq p\leq M$, there is a unique $i$
such that $(j_{p},w_{p})\in{S}^{\mathrm{ext}}_{i}$ and we denote
$\mathsf{idx}(j_{p}):=i$. We define a bad event $\mathcal{A}(p)$ that either
$X_{j_{p}}(w_{p})\neq Y_{j_{P}}(w_{p})$ or
$X_{j_{p}}(w_{p})=Y_{j_{P}}(w_{p})=c_{\mathsf{idx}(j_{p})}$. Using the chain
rule for the RHS of the inequality above, it holds that

$\displaystyle\mathop{\mathrm{Pr}}\nolimits_{\mathcal{C}}\left[\bigwedge_{i=1}^{m-1}\mathcal{B}_{i}(c_{i})\right]\leq\prod_{p=1}^{M}\mathop{\mathrm{Pr}}\nolimits_{\mathcal{C}}\left[\mathcal{A}(p)\mid\bigwedge_{p^{\prime}<p}\mathcal{A}(p^{\prime})\right].$

Consider the probability of $\mathcal{A}(p)$ conditional on all
$\mathcal{A}(p^{\prime})$ for $p^{\prime}<p$. To simplify the notation, let
$j=j_{p}>0$ and $w=w_{p}$. In the $j$-th update, $X_{j}(w)$ is sampled from
the distribution $\nu_{w}^{X_{j-1}(V\setminus\\{w\\})}$ and $Y_{j}(w)$ is
sampled from the distribution $\nu_{w}^{Y_{j-1}(V\setminus\\{w\\})}$. For any
$\tau\in[s]^{V\setminus\\{w\\}}$, it holds that

$\displaystyle\forall x\in[s],\quad\nu^{\tau}_{w}(x)=\sum_{y\in
h^{-1}(x)}\mu^{\tau}_{w}(y).$

Note that $\mu^{\tau}$ is actually the uniform distribution over a list
colouring instance on $H$ where for each $u\neq w$, the colour list is
$h^{-1}(\tau_{u})$, and the colour list for $w$ is $[q]$. Hence, for each
$u\neq w$, the size of colour list of $u$ is at least $\lfloor q/s\rfloor$,
and the size of colour list of $w$ is $q$, where
$s=\left\lceil{\sqrt{q}}\right\rceil$. Note that $q\geq
40\Delta^{\frac{2}{k-4}}$ and $k\geq 20$ implies $\lfloor q/s\rfloor^{k}\geq
2\mathrm{e}q^{2}k\Delta$. By Lemma 6, for all
$\tau\in[s]^{V\setminus\\{w\\}}$, it holds that

$\displaystyle\forall
y\in[q],\quad\frac{1}{q}\left(1-\frac{4}{kq}\right)\leq\frac{1}{q}\exp\left(-\frac{2}{kq}\right)\leq\mu^{\tau}_{w}(y)\leq\frac{1}{q}\exp\left(\frac{2}{kq}\right)\leq\frac{1}{q}\left(1+\frac{4}{kq}\right).$

Hence, for any $\tau\in[s]^{V\setminus\\{w\\}}$, it holds that for any
$x\in[s]$,

$\displaystyle\frac{\left|h^{-1}(x)\right|}{q}\left(1-\frac{4}{kq}\right)\leq\nu^{\tau}_{w}(x)\leq\frac{\left|h^{-1}(x)\right|}{q}\left(1+\frac{4}{kq}\right).$

Note that all the events $\mathcal{A}(p^{\prime})$ for $p^{\prime}<p$ are
determined by the updates from time 1 to time $j-1$. The above bounds for
$\nu^{\tau}_{w}(x)$ holds for any configuration
$\tau\in[s]^{V\setminus\\{w\\}}$. In the $j$-th update step, since $X_{j}(w)$
and $Y_{j}(w)$ are coupled by the optimal coupling and
$\left|h^{-1}(x)\right|\leq\left\lceil{q/s}\right\rceil$, we have the
probability of $X_{j}(w)\neq Y_{j}(w)$ is at most
$\frac{1}{2}\sum_{x\in[s]}\frac{\left|h^{-1}(x)\right|}{q}\cdot\frac{8}{kq}=\frac{4}{kq}$,
and the probability of $X_{j}(w)=Y_{j}(w)=c_{i}$ is at most
$\frac{\left\lceil{q/s}\right\rceil}{q}\left(1+\frac{4}{kq}\right)$. Hence,

$\displaystyle\mathop{\mathrm{Pr}}\nolimits_{\mathcal{C}}\left[\mathcal{A}(p)\mid\bigwedge_{p^{\prime}<p}\mathcal{A}(p^{\prime})\right]$
$\displaystyle\leq\frac{4}{kq}+\frac{\left\lceil{q/s}\right\rceil}{q}\left(1+\frac{4}{kq}\right)\overset{(\star)}{\leq}\frac{\left\lceil{q/s}\right\rceil}{q}\left(1+\frac{5}{k}\right)$
$\displaystyle\leq\frac{1.16}{\sqrt{q}}\left(1+\frac{5}{k}\right).$

where $(\star)$ holds because
$\frac{\left\lceil{q/s}\right\rceil}{kq}\geq\frac{4}{kq}$ if $q\geq 40$ and
the last inequality is due to $\left\lceil{q/s}\right\rceil\leq 1.16\sqrt{q}$.
This implies

$\displaystyle\mathop{\mathrm{Pr}}\nolimits_{\mathcal{C}}\left[\bigwedge_{i=1}^{m-1}\mathcal{B}_{i}(c_{i})\right]\leq\prod_{p=1}^{M}\left(\frac{1.16}{\sqrt{q}}\left(1+\frac{5}{k}\right)\right)=\prod_{i=1}^{m-1}\left(\frac{1.16}{\sqrt{q}}\left(1+\frac{5}{k}\right)\right)^{\left|{S}^{\mathrm{ext}}_{i}\right|}.$

By the second property in Lemma 36 and the definition
${S}^{\mathrm{ext}}_{i}$, it holds that

$\displaystyle\forall 1\leq i\leq
m,\quad\left|{S}^{\mathrm{ext}}_{i}\right|\geq k-1.$

Combining with (29), we have

$\displaystyle\mathop{\mathrm{Pr}}\nolimits_{\mathcal{C}}\left[\mathcal{B}(\mathcal{P})\right]$
$\displaystyle\leq\sum_{\bm{c}\in[s]^{m-1}}\mathop{\mathrm{Pr}}\nolimits_{\mathcal{C}}\left[\bigwedge_{i=1}^{m-1}\mathcal{B}_{i}(c_{i})\right]\leq\sum_{\bm{c}\in[s]^{m-1}}\left(\frac{1.16}{\sqrt{q}}\left(1+\frac{5}{k}\right)\right)^{(m-1)(k-1)}$
$\displaystyle\leq\left(s\left(\frac{1.16}{\sqrt{q}}\left(1+\frac{5}{k}\right)\right)^{k-1}\right)^{m-1}.$

Now we claim that

$\displaystyle
s\left(\frac{1.16}{\sqrt{q}}\left(1+\frac{5}{k}\right)\right)^{k-1}\leq\frac{1}{10^{3}\Delta
k^{6}}.$

Using $s=\lceil\sqrt{q}\rceil\leq 1.16\sqrt{q}$, it suffices to show that

$\displaystyle 1.16\times
10^{3}(1.16)^{k-1}\left(1+\frac{5}{k}\right)^{k-1}\Delta k^{6}\leq
q^{(k-2)/2}.$

Using $\left(1+\frac{5}{k}\right)^{\frac{2(k-1)}{k-2}}\leq 1.7$ and
$k^{12/(k-2)}\leq 7.4$ for $k\geq 20$, we further simplifies the condition
into

$\displaystyle q\geq 7.4\times 1.7\times(1.16\times
10^{3})^{2/(k-2)}(1.16)^{2(k-1)/(k-2)}\Delta^{2/(k-2)},$

which is implied by $q\geq 40\Delta^{\frac{2}{k-4}}$ and $k\geq 20$.

The claim implies that

$\displaystyle\mathop{\mathrm{Pr}}\nolimits_{\mathcal{C}}\left[\mathcal{B}(\mathcal{P})\right]\leq\left(\frac{1}{10^{3}\Delta
k^{6}}\right)^{m-1}=10^{3}\Delta k^{6}\left(\frac{1}{10^{3}\Delta
k^{6}}\right)^{m}.$

Finally, by the third property in Lemma 36, we have

$\displaystyle\mathop{\mathrm{Pr}}\nolimits_{\mathcal{C}}\left[\mathcal{B}(\mathcal{P})\right]\leq
10^{3}\Delta k^{6}\left(\frac{1}{10^{3}\Delta
k^{6}}\right)^{R_{\mathrm{out}}+\frac{1}{3}\left(R_{\mathrm{self}}-b\right)}.$

## References

  * Alo [91] Noga Alon.  A parallel algorithmic version of the local lemma.  Random Struct. Algorithms, 2(4):367–378, 1991.
  * BCKL [13] Christian Borgs, Jennifer Chayes, Jeff Kahn, and László Lovász.  Left and right convergence of graphs with bounded degree.  Random Struct. Algorithms, 42(1):1–28, 2013.
  * Bec [91] József Beck.  An algorithmic approach to the Lovász local lemma. I.  Random Struct. Algorithms, 2(4):343–366, 1991.
  * BGG+ [19] Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Daniel Štefankovič.  Approximation via correlation decay when strong spatial mixing fails.  SIAM J. Comput., 48(2):279–349, 2019.
  * CS [00] Artur Czumaj and Christian Scheideler.  Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lovász local lemma.  Random Struct. Algorithms, 17(3-4):213–237, 2000.
  * EL [75] P. Erdős and L. Lovász.  Problems and results on $3$-chromatic hypergraphs and some related questions.  In Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, pages 609–627. Colloq. Math. Soc. János Bolyai, Vol. 10. 1975.
  * FA [17] Alan M. Frieze and Michael Anastos.  Randomly coloring simple hypergraphs with fewer colors.  Inf. Process. Lett., 126:39–42, 2017.
  * FGYZ [21] Weiming Feng, Heng Guo, Yitong Yin, and Chihao Zhang.  Fast sampling and counting $k$-SAT solutions in the local lemma regime.  J. ACM, 68(6):40:1–40:42, 2021.
  * FHY [20] Weiming Feng, Kun He, and Yitong Yin.  Sampling constraint satisfaction solutions in the local lemma regime.  arXiv, abs/2011.03915, 2020.
  * FM [11] Alan M. Frieze and Páll Melsted.  Randomly coloring simple hypergraphs.  Inf. Process. Lett., 111(17):848–853, 2011.
  * FM [13] Alan Frieze and Dhruv Mubayi.  Coloring simple hypergraphs.  J. Combin. Theory Ser. B, 103(6):767–794, 2013.
  * GGW [21] Andreas Galanis, Heng Guo, and Jiaheng Wang.  Inapproximability of counting hypergraph colourings.  arXiv preprint arXiv:2107.05486, 2021.
  * GJL [19] Heng Guo, Mark Jerrum, and Jingcheng Liu.  Uniform sampling through the Lovász local lemma.  J. ACM, 66(3):18:1–18:31, 2019.
  * GLLZ [19] Heng Guo, Chao Liao, Pinyan Lu, and Chihao Zhang.  Counting hypergraph colorings in the local lemma regime.  SIAM J. Comput., 48(4):1397–1424, 2019.
  * GST [16] Heidi Gebauer, Tibor Szabó, and Gábor Tardos.  The local lemma is asymptotically tight for SAT.  J. ACM, 63(5):43:1–43:32, 2016.
  * HSS [11] Bernhard Haeupler, Barna Saha, and Aravind Srinivasan.  New constructive aspects of the Lovász local lemma.  J. ACM, 58(6):28, 2011.
  * HSW [21] Kun He, Xiaoming Sun, and Kewen Wu.  Perfect sampling for (atomic) Lovász local lemma.  arXiv, abs/2107.03932, 2021.
  * HSZ [19] Jonathan Hermon, Allan Sly, and Yumeng Zhang.  Rapid mixing of hypergraph independent sets.  Random Struct. Algorithms, 54(4):730–767, 2019.
  * Hub [98] Mark Huber.  Exact sampling and approximate counting techniques.  In STOC, pages 31–40. ACM, 1998.
  * Hub [15] Mark Huber.  Approximation algorithms for the normalizing constant of Gibbs distributions.  Ann. Appl. Probab., 25(2):974–985, 2015.
  * JPV [20] Vishesh Jain, Huy Tuan Pham, and Thuy Duong Vuong.  Towards the sampling Lovász local lemma.  arXiv, abs/2011.12196, 2020.
  * JPV [21] Vishesh Jain, Huy Tuan Pham, and Thuy Duong Vuong.  On the sampling Lovász local lemma for atomic constraint satisfaction problems.  arXiv, abs/2102.08342, 2021.
  * JVV [86] Mark R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani.  Random generation of combinatorial structures from a uniform distribution.  Theoret. Comput. Sci., 43:169–188, 1986.
  * Kol [18] Vladimir Kolmogorov.  A faster approximation algorithm for the Gibbs partition function.  In COLT, pages 228–249. PMLR, 2018.
  * Moi [19] Ankur Moitra.  Approximate counting, the Lovász local lemma, and inference in graphical models.  J. ACM, 66(2):10:1–10:25, 2019.
  * Mos [09] Robin A. Moser.  A constructive proof of the Lovász local lemma.  In STOC, pages 343–350. ACM, 2009.
  * MR [98] Michael Molloy and Bruce A. Reed.  Further algorithmic aspects of the local lemma.  In STOC, pages 524–529. ACM, 1998.
  * MT [10] Robin A. Moser and Gábor Tardos.  A constructive proof of the general Lovász local lemma.  J. ACM, 57(2):11, 2010.
  * PW [96] James G. Propp and David B. Wilson.  Exact sampling with coupled Markov chains and applications to statistical mechanics.  Random Structures Algorithms, 9(1-2):223–252, 1996.
  * Sri [08] Aravind Srinivasan.  Improved algorithmic versions of the Lovász local lemma.  In SODA, pages 611–620. SIAM, 2008.
  * Sta [99] Richard P. Stanley.  Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 1999.
  * ŠVV [09] Daniel Štefankovič, Santosh Vempala, and Eric Vigoda.  Adaptive simulated annealing: A near-optimal connection between sampling and counting.  J. ACM, 56(3):18, 2009.
  * WW [20] Ian M Wanless and David R Wood.  A general framework for hypergraph colouring.  arXiv preprint arXiv:2008.00775, 2020.


* [LOS13] Christina E Lee, Asuman Ozdaglar and Devavrat Shah  “Approximating the Stationary Probability of a Single State in a Markov chain”  In _arXiv preprint arXiv:1312.1986_ , 2013
  * [LPW08] David A Levin, Yuval Peres and Elizabeth L Wilmer  “Markov chains and mixing times”  American Mathematical Soc., 2008
  * [MA12] Teodor Mihai Moldovan and Pieter Abbeel  “Safe exploration in Markov decision processes”  In _Proceedings of the 29th International Coference on International Conference on Machine Learning_ , 2012, pp. 1451–1458
  * [Mni+15] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland and Georg Ostrovski  “Human-level control through deep reinforcement learning”  In _Nature_ 518.7540 Nature Publishing Group, 2015, pp. 529
  * [NHR99] Andrew Y Ng, Daishi Harada and Stuart Russell  “Policy invariance under reward transformations: Theory and application to reward shaping”  In _Proceedings of the International Conference on Machine Learning (ICML)_ 99, 1999, pp. 278–287
  * [Ohn88] K. Ohno  “A value iteration method for undiscounted multichain Markov decision processes”  In _Zeitschrift für Operations Research_ 32.2, 1988, pp. 71–93  DOI: 10.1007/BF01919182
  * [Ouy+22] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama and Alex Ray  “Training language models to follow instructions with human feedback”  In _Advances in Neural Information Processing Systems_ 35, 2022, pp. 27730–27744
  * [PD12] William H. Press and Freeman J. Dyson  “Iterated Prisoner’s Dilemma contains strategies that dominate any evolutionary opponent”  In _Proceedings of the National Academy of Sciences_ 109.26 National Academy of Sciences, 2012, pp. 10409–10413  DOI: 10.1073/pnas.1206569109
  * [Put94] Martin L Puterman  “Markov Decision Processes: Discrete Stochastic Dynamic Programming”  John Wiley & Sons, Inc., 1994
  * [PW19] Ashwin Pananjady and Martin J. Wainwright  “Value function estimation in Markov reward processes: Instance-dependent $\ell_{\infty}$-bounds for policy evaluation”  In _arXiv preprint_ , 2019  URL: https://arxiv.org/abs/1909.08749
  * [RH08] Daniil Ryabko and Marcus Hutter  “On the possibility of learning in reactive environments with arbitrary dependence”  In _Theoretical Computer Science_ 405.3, Algorithmic Learning Theory, 2008, pp. 274–284  DOI: 10.1016/j.tcs.2008.06.039
  * [Ros96] Sheldon M Ross  “Stochastic processes”  John Wiley, 1996
  * [SB18] Richard S Sutton and Andrew G Barto  “Reinforcement learning: An introduction”  MIT press, 2018
  * [SB98] Richard S Sutton and Andrew G Barto  “Reinforcement learning: An introduction”  MIT press, 1998
  * [Sch84] P.. Schweitzer  “A value-iteration scheme for undiscounted multichain Markov renewal programs”  In _Zeitschrift für Operations Research_ 28.5, 1984, pp. 143–152  DOI: 10.1007/BF01920916
  * [SDW17] Chip Schaff, Falcon Z Dai and Matthew R Walter  “Towards Active Imitation Learning”  In _Learning from Demonstrations in High-Dimensional Feature Spaces workshop at Robotics: Science and Systems (RSS)_ , 2017  URL: https://people.csail.mit.edu/mmonfort/papers/rss2017/active-imitation-learning.pdf
  * [Sil+16] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam and Marc Lanctot  “Mastering the game of Go with deep neural networks and tree search”  In _Nature_ 529.7587 Nature Publishing Group, 2016, pp. 484
  * [SL05] Alexander L Strehl and Michael L Littman  “A theoretical analysis of model-based interval estimation”  In _Proceedings of the International Conference on Machine Learning (ICML)_ , 2005, pp. 856–863  ACM
  * [SL08] Alexander L Strehl and Michael L Littman  “An analysis of model-based interval estimation for Markov decision processes”  In _Journal of Computer and System Sciences_ 74.8 Elsevier, 2008, pp. 1309–1331
  * [SM19] Jayakumar Subramanian and Aditya Mahajan  “Renewal Monte Carlo: Renewal theory based reinforcement learning”  In _IEEE Transactions on Automatic Control_ , 2019, pp. 1–1
  * [SPS99] Richard S. Sutton, Doina Precup and Satinder Singh  “Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning”  In _Artificial intelligence_ 112.1–2, 1999, pp. 181–211
  * [Sut88] Richard S Sutton  “Learning to predict by the methods of temporal differences”  In _Machine Learning_ 3.1, 1988, pp. 9–44
  * [TB07] Ambuj Tewari and Peter L Bartlett  “Bounded parameter Markov decision processes with average reward criterion”  In _International Conference on Computational Learning Theory (COLT)_ , 2007, pp. 263–277  Springer
  * [Tur50] Alan M Turing  “I.—COMPUTING MACHINERY AND INTELLIGENCE”  In _Mind_ LIX.236, 1950, pp. 433–460  DOI: 10.1093/mind/LIX.236.433
  * [WCE03] Eric Wiewiora, Garrison W Cottrell and Charles Elkan  “Principled methods for advising reinforcement learning agents”  In _Proceedings of the International Conference on Machine Learning (ICML)_ , 2003, pp. 792–799
  * [WD92] Christopher JCH Watkins and Peter Dayan  “Q-learning”  In _Machine learning_ 8.3-4 Springer, 1992, pp. 279–292
  * [Wie03] Eric Wiewiora  “Potential-based shaping and Q-value initialization are equivalent”  In _Journal of Artificial Intelligence Research_ 19, 2003, pp. 205–208

##  Chapter 5 Appendix

##  Appendix 5.A Detailed proofs of Chapter 1

####  1 Proof of Theorem 4.1

###### Proof.

Note that since $X_{0}=s$, we have $W_{1}(s)=0$ and $I_{1}(s)=W_{2}(s)$. Since
only state $s$ appears here, we will suppress $s$ from the random variables
below to simplify the notation. We use Assumption 3.1 or the weaker assumption
that $s$ is positive recurrent, i.e., $\rho_{s}<\infty$, to guarantee that
$W_{2}<\infty$ with probability 1.

$\displaystyle v(s)$ $\displaystyle\quad\triangleright\text{By definition
\eqref{eq:value}}$
$\displaystyle\quad=\mathbb{E}_{s}\left[\sum_{t=0}^{\infty}\gamma^{t}R_{t}\right]$
$\displaystyle\quad\triangleright\text{Split the infinite sum at $W_{2}$}$
$\displaystyle\quad=\mathbb{E}_{s}\left[\sum_{t=0}^{W_{2}-1}\gamma^{t}R_{t}+\sum_{t=W_{2}}^{\infty}\gamma^{t}R_{t}\right]$
$\displaystyle\quad\triangleright\text{Rewrite the indices}$
$\displaystyle\quad=\mathbb{E}_{s}\left[\sum_{t=0}^{W_{2}-1}\gamma^{t}R_{W_{1}+t}+\gamma^{W_{2}}\sum_{t=0}^{\infty}\gamma^{t}R_{W_{2}+t}\right]$
$\displaystyle\quad\triangleright\text{By definition \eqref{eq:interarrival-
times}}$
$\displaystyle\quad=\mathbb{E}_{s}\left[\sum_{t=0}^{I_{1}-1}\gamma^{t}R_{W_{1}+t}+\gamma^{I_{1}}\sum_{t=0}^{\infty}\gamma^{t}R_{W_{2}+t}\right]$
$\displaystyle\quad\triangleright\text{By definition \eqref{eq:partial-sum}}$
$\displaystyle\quad=\mathbb{E}_{s}\left[G_{1}+\gamma^{I_{1}}\sum_{t=0}^{\infty}\gamma^{t}R_{W_{2}+t}\right]$
$\displaystyle\quad\triangleright\text{Split off the first term}$
$\displaystyle\quad=\mathbb{E}_{s}\left[G_{1}\right]+\mathbb{E}_{s}\left[\gamma^{I_{1}}\sum_{t=0}^{\infty}\gamma^{t}R_{W_{2}+t}\right]$
$\displaystyle\quad\triangleright\text{Note that $X_{W_{2}}=s$ and by Markov
property}$
$\displaystyle\quad=\mathbb{E}_{s}\left[G_{1}\right]+\mathbb{E}_{s}\left[\gamma^{I_{1}}\right]\mathbb{E}_{s}\left[\sum_{t=0}^{\infty}\gamma^{t}R_{W_{2}+t}\right]$
$\displaystyle\quad\triangleright\text{$(R_{W_{2}+t})_{t\geq 0}$ and
$(R_{t})_{t\geq 0}$ are probabilistically identical}$
$\displaystyle\quad=\mathbb{E}_{s}\left[G_{1}\right]+\mathbb{E}_{s}\left[\gamma^{I_{1}}\right]v(s)$
$\displaystyle\quad\triangleright\text{By the definitions of $\alpha(s)$ and
$\beta(s)$}$ $\displaystyle\quad=\beta(s)+\alpha(s)\,v(s).$

####  2 Proof of Theorem 4.2

###### Proof.

Since only state $s$ appears below, we will suppress it in the interest of
conciseness. Consider

$\displaystyle\hat{v}_{n}-v$ $\displaystyle\quad\triangleright\text{By
\eqref{eq:loop-bellman} and \eqref{eq:loop-estimator} }$
$\displaystyle\quad=\left(\hat{\beta}_{n}+\hat{\alpha}_{n}\,\hat{v}_{n}\right)-\left(\beta+\alpha\,v\right)$
$\displaystyle\quad\triangleright\text{Rearrange the terms}$
$\displaystyle\quad=\hat{\beta}_{n}-\beta+\hat{\alpha}_{n}\,\hat{v}_{n}-\alpha\,v$
$\displaystyle\quad\triangleright\text{Add and subtract
$\hat{\alpha}_{n}\,v$}$
$\displaystyle\quad=\hat{\beta}_{n}-\beta+\hat{\alpha}_{n}\,\hat{v}_{n}-\hat{\alpha}_{n}\,v+\hat{\alpha}_{n}\,v-\alpha\,v$
$\displaystyle\quad=\left(\hat{\beta}_{n}-\beta\right)+\hat{\alpha}_{n}\left(\hat{v}_{n}-v\right)+\left(\hat{\alpha}_{n}-\alpha\right)v.$

By the definition of an MRP, we have
$v\in[0,\nicefrac{{r_{\text{max}}}}{{1-\gamma}}]$ and
$G_{1}\in[0,\nicefrac{{r_{\text{max}}}}{{1-\gamma}})$. Furthermore, $I_{1}\geq
1$ implies that $\gamma^{I_{1}}\in(0,\gamma]$ and $0<1-\gamma\leq
1-\hat{\alpha}_{n}$. Hence the estimation error is bounded as follows

$\displaystyle\lvert\hat{v}_{n}-v\rvert$
$\displaystyle\leq\lvert\hat{\beta}_{n}-\beta\rvert+\hat{\alpha}_{n}\,\lvert\hat{v}_{n}-v\rvert+\lvert\hat{\alpha}_{n}-\alpha\rvert\,v$
$\displaystyle\lvert\hat{v}_{n}-v\rvert-\hat{\alpha}_{n}\,\lvert\hat{v}_{n}-v\rvert$
$\displaystyle\leq\lvert\hat{\beta}_{n}-\beta\rvert+\lvert\hat{\alpha}_{n}-\alpha\rvert\,v$
$\displaystyle\triangleright\text{Divide by $1-\hat{\alpha}_{n}$}$
$\displaystyle\lvert\hat{v}_{n}-v\rvert$
$\displaystyle\leq\left(1-\hat{\alpha}_{n}\right)^{-1}\,\left(\lvert\hat{\beta}_{n}-\beta\rvert+\lvert\hat{\alpha}_{n}-\alpha\rvert\,v\right)$
$\displaystyle\leq\frac{1}{1-\gamma}\,\left(\lvert\hat{\beta}_{n}-\beta\rvert+\lvert\hat{\alpha}_{n}-\alpha\rvert\,v\right).$

With failure probability of at most $\delta/2$, from Hoeffding’s inequality,
we have

$\lvert\hat{\beta}_{n}-\beta\rvert<\frac{r_{\text{max}}}{1-\gamma}\,\sqrt{\frac{\log\nicefrac{{4}}{{\delta}}}{2n}}$

and similarly

$\lvert\hat{\alpha}_{n}-\alpha\rvert<\gamma\,\sqrt{\frac{\log\nicefrac{{4}}{{\delta}}}{2n}}.$

Applying the union bound, we have

$\displaystyle\lvert\hat{v}_{n}-v\rvert$
$\displaystyle\leq\frac{1}{1-\gamma}\,\left(\frac{r_{\text{max}}}{1-\gamma}\,\sqrt{\frac{\log\nicefrac{{4}}{{\delta}}}{2n}}+\gamma\,v\,\sqrt{\frac{\log\nicefrac{{4}}{{\delta}}}{2n}}\right)$
$\displaystyle\leq\frac{1}{1-\gamma}\,\left(\frac{r_{\text{max}}}{1-\gamma}\,\sqrt{\frac{\log\nicefrac{{4}}{{\delta}}}{2n}}+\gamma\,\frac{r_{\text{max}}}{1-\gamma}\,\sqrt{\frac{\log\nicefrac{{4}}{{\delta}}}{2n}}\right)$
$\displaystyle<\frac{r_{\text{max}}}{(1-\gamma)^{2}}\,\sqrt{\frac{\log\nicefrac{{4}}{{\delta}}}{2n}}.$

####  3 Proof of Lemma 4.3

This proof largely follows the proof by [LOS13] and is presented here in the
interest of self-containedness.

###### Proof.

Suppose $a,b>0$, consider the probability of the event that $s$ is not visited
in the next $a$ steps given that it is not visited in the previous $b$ steps,
that is

$\displaystyle\mathbb{P}\left[H_{s}^{+}>a+b\middle|H_{s}^{+}>b\right]$
$\displaystyle\quad\triangleright\text{In particular, $X_{b}\neq s$}$
$\displaystyle\quad\leq\mathbb{P}\left[H_{s}^{+}>a+b\middle|X_{b}\neq
s\right]$ $\displaystyle\quad\triangleright\text{By Markov property, we can
shift the index}$
$\displaystyle\quad=\mathbb{P}\left[H_{s}^{+}>a\middle|X_{0}\neq s\right]$
$\displaystyle\quad\leq\max_{s^{\prime}\in\mathcal{S}}\mathbb{P}\left[H_{s}^{+}>a\middle|X_{0}=s^{\prime}\right]$
$\displaystyle\quad\triangleright\text{By Markov inequality}$
$\displaystyle\quad\leq\max_{s^{\prime}\in\mathcal{S}}\frac{\mathbb{E}\left[H_{s}^{+}\middle|X_{0}=s^{\prime}\right]}{a}$
$\displaystyle\quad\triangleright\text{By definition \eqref{eq:maximal-
expected-hitting-time}}$ $\displaystyle\quad\leq\frac{\tau_{s}}{a}.$ (1)

Let $a=e\,\tau_{s}$, and apply the above
$\left\lfloor\frac{t}{a}\right\rfloor$-many times to

$\displaystyle\mathbb{P}\left[H_{s}^{+}\geq t\right]$
$\displaystyle\leq\mathbb{P}\left[H_{s}^{+}\geq\left\lfloor\frac{t}{a}\right\rfloor\,a\right]$
$\displaystyle\triangleright\text{Apply \eqref{eq:tau-a}}$
$\displaystyle\leq\left(\frac{\tau_{s}}{a}\right)^{\left\lfloor\frac{t}{a}\right\rfloor}$
$\displaystyle\triangleright\text{Let $a=e\,\tau_{s}$}$
$\displaystyle\leq\left(\frac{1}{e}\right)^{\left\lfloor\frac{t}{e\tau_{s}}\right\rfloor}$
$\displaystyle<e\cdot\left(\frac{1}{e}\right)^{\frac{t}{e\tau_{s}}}.$

####  4 Proof of Corollary 4.4

###### Proof.

For conciseness, we suppress $s$ here since only state $s$ appears. Suppose
$a>0$. By Remark Remark, we have $W_{n}<n\,a$ if $W_{1}<a$ and $I_{i}<a$ for
$i=1,\cdots,n-1$. Note that $W_{1}\leq H_{s}^{+}$ and $I_{i}$ distribute
identically to $H_{s}^{+}$. Immediately from inverting Lemma 4.3, we have with
failure probability of at most $\nicefrac{{\delta}}{{n}}$, $W_{1}$ is bounded

$W_{1}\leq H_{s}^{+}<e\tau_{s}\log\frac{en}{\delta}.$

Suppose each $I_{i}<a$ fails with probability of at most
$\nicefrac{{\delta}}{{n}}$, then we similarly have

$I_{i}<e\tau_{s}\log\frac{en}{\delta}.$

Applying the union bound, and with probability of at least $1-\delta$, we have

$W_{n}<en\tau_{s}\log\frac{en}{\delta}.$

∎

####  5 Proof of Theorem 4.5

###### Proof.

First, we introduce the Lambert $\mathcal{W}$ function to invert Corollary
4.4. Recall that the Lambert $\mathcal{W}$ function is a transcendental
function defined such that $\mathcal{W}(x)e^{\mathcal{W}(x)}=x$, and thus it
is a monotonically increasing function. At step $T$, suppose

$\displaystyle en\,\tau_{s}\log\frac{en}{\delta}$ $\displaystyle=T$
$\displaystyle\frac{en}{\delta}\,\log\frac{en}{\delta}$
$\displaystyle=\frac{T}{\delta\,\tau_{s}}$
$\displaystyle\left(\log\frac{en}{\delta}\right)\,e^{\left(\log\frac{en}{\delta}\right)}$
$\displaystyle=\frac{T}{\delta\,\tau_{s}}$
$\displaystyle\triangleright\text{By the definition of $\mathcal{W}$}$
$\displaystyle\log\frac{en}{\delta}$
$\displaystyle=\mathcal{W}\left(\frac{T}{\delta\,\tau_{s}}\right)$
$\displaystyle\triangleright\text{Exponentiate both sides}$
$\displaystyle\frac{en}{\delta}$
$\displaystyle=e^{\mathcal{W}\left(\frac{T}{\delta\,\tau_{s}}\right)}.$

Use the fact that if $x>e$, then $\log x-\log\log x<\mathcal{W}(x)$. So given
$T>e\delta\tau_{s}$, we can lower-bound the number of visits

$\displaystyle
e^{\log\left(\frac{T}{\delta\,\tau_{s}}\right)-\log\log\left(\frac{T}{\delta\,\tau_{s}}\right)}$
$\displaystyle<\frac{en}{\delta}$
$\displaystyle\frac{\frac{T}{\delta\,\tau_{s}}}{\log\left(\frac{T}{\delta\,\tau_{s}}\right)}$
$\displaystyle<\frac{en}{\delta}$
$\displaystyle\frac{T\,}{e\,\tau_{s}\,\log\left(\frac{T}{\delta\,\tau_{s}}\right)}$
$\displaystyle<n.$

Plugging this into Theorem 4.2, we obtain the desired expression

$\left|\hat{v}_{T}(s)-v(s)\right|<\frac{r_{\text{max}}}{(1-\gamma)^{2}}\,\sqrt{\frac{e\tau_{s}\,\log\left(\frac{T}{\delta\,\tau_{s}}\right)\log\frac{4}{\delta}}{2T}}.$

∎

####  6 Proof of Corollary 4.6

###### Proof.

We run $S$ many copies of loop estimators, one for each state
$s\in\mathcal{S}$. Following Theorem 4.5, with failure probability of at most
$\nicefrac{{\delta}}{{S}}$, we can ensure that each estimator has an error of
at most

$\left|\hat{v}_{T}(s)-v(s)\right|<\frac{r_{\text{max}}}{(1-\gamma)^{2}}\,\sqrt{\frac{e\tau_{s}\,\log\left(\frac{S\,T}{\delta\,\tau_{s}}\right)\log\frac{4S}{\delta}}{2T}}.$

The largest upper bound comes from the state with the largest maximal expected
hitting time $\max_{s\in\mathcal{S}}\tau_{s}$ of the Markov chain. Apply the
union bound and we have

$\left\|\hat{\mathbf{v}}_{T}-\mathbf{v}\right\|_{\infty}<\frac{r_{\text{max}}}{(1-\gamma)^{2}}\,\sqrt{\frac{e\max_{s}\tau_{s}\,\log\left(\frac{S\,T}{\delta\,\min_{s}\tau_{s}}\right)\log\frac{4S}{\delta}}{2T}}.$

∎

##  Appendix 5.B Detailed proofs of Chapter 2

####  1 Proof of Lemma 2.1

Assuming that the actual MDP $M$ is in the extended MDP $M^{+}$, i.e.,
$\bar{r}(s,a)\in B_{\delta}(s,a)$ and $p(\cdot|s,a)\in C_{\delta}(s,a)$ for
all $s\in\mathcal{S},a\in\mathcal{A}$, we have

$\max_{s}u_{i}(s)-\min_{s^{\prime}}u_{i}(s^{\prime})\leq\kappa(M)$

where $u_{i}(s)$ is the $i$-step optimal undiscounted value of state $s$.

###### Proof.

By assumption, the actual mean rewards $\bar{r}$ and transitions $p$ are
contained in the extended MDP $M^{+}$, i.e., for any $s\in\mathcal{S}$ and
$a\in\mathcal{A}$, $\bar{r}(s,a)\in B_{\delta}(s,a)$ and $p(\cdot|s,a)\in
C_{\delta}(s,a)$. Thus for any policy $\pi:\mathcal{S}\rightarrow\mathcal{A}$
in the actual MDP $M$, we can construct a corresponding policy
$\pi^{+}:\mathcal{S}\rightarrow\mathcal{A}^{+}$ in the extended MDP $M^{+}$

$\pi^{+}(s)\coloneqq\Big{(}\pi(s),p(\cdot|s,\pi(s)),\bar{r}(s,\pi(s))\Big{)}.$

Following $\pi^{+}$ in $M^{+}$ induces the same stochastic process
$(s_{t},a_{t},r_{t})_{t\geq 0}$ as following $\pi$ in $M$. In particular they
have the same expected hitting times and expected rewards. By definition
$u_{i}(s)$ is the value of following an _optimal_ $i$-step non-stationary
policy starting at $s$ in the extended MDP $\mathcal{M}^{+}$. For any
$s^{\prime}$, by optimality, $u_{i}(s)$ must be no worse than first following
$\pi^{+}$ from $s$ to $s^{\prime}$ and then following the optimal $i$-step
non-stationary policy from $s^{\prime}$ onward. Along the path from $s$ to
$s^{\prime}$, we receive rewards according to $\sigma_{3}(\pi^{+})=\bar{r}$
and after arriving at $s^{\prime}$, we have missed at most
$r_{\text{max}}h_{s\rightarrow s^{\prime}}(M^{+},\pi^{+})$-many rewards of
$u_{i}(s^{\prime})$ so in expectation

$\displaystyle u_{i}(s)$
$\displaystyle\geq\mathbb{E}\left[\sum_{t=0}^{h_{s\rightarrow
s^{\prime}}(M^{+},\pi^{+})-1}r_{t}\right]+u_{i}(s^{\prime})-\mathbb{E}[r_{\text{max}}h_{s\rightarrow
s^{\prime}}(M^{+},\pi^{+})]$
$\displaystyle=\mathbb{E}\left[\sum_{t=0}^{h_{s\rightarrow
s^{\prime}}(M^{+},\pi^{+})-1}r_{t}-r_{\text{max}}\right]+u_{i}(s^{\prime})$
$\displaystyle\triangleright\text{By definition of $\pi^{+}$, hitting time
$h_{s\rightarrow s^{\prime}}(M,\pi)=h_{s\rightarrow
s^{\prime}}(M^{+},\pi^{+})$ }$
$\displaystyle=\mathbb{E}\left[\sum_{t=0}^{h_{s\rightarrow
s^{\prime}}(M,\pi)-1}r_{t}-r_{\text{max}}\right]+u_{i}(s^{\prime}).$

Moving the terms around and we get

$u_{i}(s^{\prime})-u_{i}(s)\leq\mathbb{E}\left[\sum_{t=0}^{h_{s\rightarrow
s^{\prime}}(M,\pi)-1}r_{\text{max}}-r_{t}\right].$

Since this holds for any $\pi$ by optimality, we can choose one with the
smallest expected hitting cost

$u_{i}(s^{\prime})-u_{i}(s)\leq\min_{\pi:\mathcal{S}\rightarrow\mathcal{A}}\mathbb{E}\left[\sum_{t=0}^{h_{s\rightarrow
s^{\prime}}(M,\pi)-1}r_{\text{max}}-r_{t}\right].$

Since $s,s^{\prime}$ are arbitrary, we can maximize over pairs of states on
both sides and get

$\max_{s^{\prime}}u_{i}(s^{\prime})-\min_{s}u_{i}(s)\leq\max_{s,s^{\prime}}\min_{\pi:\mathcal{S}\rightarrow\mathcal{A}}\mathbb{E}\left[\sum_{t=0}^{h_{s\rightarrow
s^{\prime}}(M,\pi)-1}r_{\text{max}}-r_{t}\right]=\kappa(M).$

It should be noted that even in some cases where the hitting time is
infinity—in a non-communicating MDPs for example—$\kappa$ can still be finite
and this inequality is still true! In these cases, $r_{t}=r_{\text{max}}$
except for finitely many terms implying $\rho^{*}(M,s)=r_{\text{max}}$. ∎

####  2 Proof of Theorem 2.3

Given an MDP $M$ with finite maximum expected hitting cost $\kappa(M)<\infty$
and an unsaturated optimal average reward $\rho^{*}(M)<r_{\text{max}}$, the
maximum expected hitting cost of any PBRS-parametrized MDP $M^{\varphi}$ is
bounded by a multiplicative factor of two

$\frac{1}{2}\kappa(M)\leq\kappa(M^{\varphi})\leq 2\kappa(M).$

###### Proof.

We denote the expected hitting cost between two states $s,s^{\prime}$ as

$c(s,s^{\prime})\coloneqq\min_{\pi:\mathcal{S}\rightarrow\mathcal{A}}\mathbb{E}\left[\sum_{t=0}^{h_{s\rightarrow
s^{\prime}}(M,\pi)-1}r_{\text{max}}-r_{t}\right].$

Suppose that the pair of states $(s,s^{\prime})$ maximizes the expected
hitting cost in $M$ which is assumed to be finite

$\kappa(M)=c(s,s^{\prime})<\infty.$

Furthermore, the condition that $\rho^{*}(M)<r_{\text{max}}$ implies that the
hitting times are finite for the minimizing policies. This ensures that the
destination state is actually hit in the stochastic process.

Considering the expected hitting cost of the reverse pair, $(s^{\prime},s)$,

$\kappa(M)=\max\\{c(s,s^{\prime}),c(s^{\prime},s)\\}\leq
c(s,s^{\prime})+c(s^{\prime},s)$ (2)

since hitting costs are nonnegative.

With $\varphi$-shaping,

$\displaystyle c^{\varphi}(s,s^{\prime})$
$\displaystyle=\min_{\pi:\mathcal{S}\rightarrow\mathcal{A}}\mathbb{E}\left[\sum_{t=0}^{h_{s\rightarrow
s^{\prime}}(M,\pi)-1}r_{\text{max}}-r^{\varphi}_{t}\right]$
$\displaystyle=\min_{\pi:\mathcal{S}\rightarrow\mathcal{A}}\mathbb{E}\left[\sum_{t=0}^{h_{s\rightarrow
s^{\prime}}(M,\pi)-1}r_{\text{max}}-(r_{t}-\varphi(s_{t})+\varphi(s_{t+1}))\right]$
$\displaystyle\triangleright\text{By telescoping sums}$
$\displaystyle=\min_{\pi:\mathcal{S}\rightarrow\mathcal{A}}\mathbb{E}\left[\varphi(s_{0})-\varphi(s_{h_{s\rightarrow
s^{\prime}}(M,\pi)})+\sum_{t=0}^{h_{s\rightarrow
s^{\prime}}(M,\pi)-1}r_{\text{max}}-r_{t}\right]$
$\displaystyle\triangleright\text{By definition of a finite hitting time,
$s_{h_{s\rightarrow s^{\prime}}(M,\pi)}=s^{\prime}$}$
$\displaystyle=\varphi(s)-\varphi(s^{\prime})+\min_{\pi:\mathcal{S}\rightarrow\mathcal{A}}\mathbb{E}\left[\sum_{t=0}^{h_{s\rightarrow
s^{\prime}}(M,\pi)-1}r_{\text{max}}-r_{t}\right]$
$\displaystyle=\varphi(s)-\varphi(s^{\prime})+c(s,s^{\prime})$ (3)

and that the hitting cost-minimizing policy for a state pair is not changed.
Therefore,

$\displaystyle\kappa(M^{\varphi})$ $\displaystyle\triangleright\text{By
definition of MEHC}$
$\displaystyle\geq\max\\{c^{\varphi}(s,s^{\prime}),c^{\varphi}(s^{\prime},s)\\}$
$\displaystyle\triangleright\text{By (\ref{eq:shaped-cost})}$
$\displaystyle=\max\\{c(s,s^{\prime})+\varphi(s)-\varphi(s^{\prime}),c(s^{\prime},s)+\varphi(s^{\prime})-\varphi(s)\\}$
$\displaystyle\triangleright\text{The maximum is no smaller than half of the
sum}$ $\displaystyle\geq\frac{1}{2}[c(s,s^{\prime})+c(s^{\prime},s)]$
$\displaystyle\triangleright\text{By (\ref{eq:max-pair})}$
$\displaystyle\geq\frac{1}{2}\kappa(M).$

We obtain the other half of the inequality by observing
$M=(M^{\varphi})^{-\varphi}$. ∎

##  Appendix 5.C Details of the numerical experiment in Section 2

We constructed an MDP that models racing around a track. There are $\ell$-many
positions on the track represented by states $\\{s_{1},\dots,s_{\ell}\\}$ and
at each of them, there are $(k+1)$-many actions including a good action that
takes us to the next state wrapping around like in a track with probability of
$(1-\delta)$. The good action with probability of $\delta$ and the other $k$
actions lead to a crashed state at that track location. Once crashed, we are
stucked at that crashed location. We are rewarded everytime we reach state
$s_{\ell}$ and thus gain is the inverse of the time to finish a lap. It is
clear that a learner ignorant of the transitions cannot recover an inevitable
crash. We modify this MDP by adding a reset action to all the states which
transition to the state $s_{1}$.

We used $\ell=4,k=2,\delta=0.2$ in the reported experiments.

##  Appendix 5.D Details of the numerical experiment in Section 3

The MDP we used consists of two states with two actions each. We can think of
the $a_{1}$ as the “switch” action and $a_{2}$, the “stay” action. However,
both actions have a small probability of causing the opposite effect. The two
reward functions prefer staying in $s_{1}$ and $s_{2}$ respectively, creating
a tradeoff. See Figure 1 for details.

$s_{1}$$s_{2}$$a_{1}$$a_{2}$$a_{1}$$a_{2}$$\epsilon$$1-\epsilon$$\epsilon$$1-\epsilon$$\epsilon$$1-\epsilon$$\epsilon$$1-\epsilon$$0,0$$1,0$$0,0$$0,1$
Figure 1: Circular nodes represent states and square nodes represent actions.
The solid edges are labeled by the transition probabilities and the dashed
edges are labeled by the two kinds of rewards in red font. For our experiment,
we set $\epsilon=0.1$.

Since there are only two actions at two states, we can parameterize the Markov
stochastic policies by
$\left(\pi(a_{1}|s_{1}),\pi(a_{1}|s_{2})\right)\in[0,1]\times[0,1]$ and
visualize the gains over the policy space (Figure 2).

Figure 2: The gains of different policies plotted over the policy space.

Figure 3: Extra examples of iterates of the proposed Direct-cone policy
optimization algorithm color-coded from dark blue to bright yellow. The
trajectories have different initial policies. The blue dots are gains of some
stochastic policies as seen in Figure 5.


# Bias Challenges in Counterfactual Data Augmentation

S Chandra Mouli Department of Computer Science
Purdue University
West Lafayette, IN, USA  Yangze Zhou  Department of Statistics
Purdue University
West Lafayette, IN, USA  Bruno Ribeiro  Department of Computer Science
Purdue University
West Lafayette, IN, USA

###### Abstract

Deep learning models tend not to be out-of-distribution robust primarily due
to their reliance on spurious features to solve the task. Counterfactual data
augmentations provide a general way of (approximately) achieving
representations that are counterfactual-invariant to spurious features, a
requirement for out-of-distribution (OOD) robustness. In this work, we show
that counterfactual data augmentations may not achieve the desired
counterfactual-invariance if the augmentation is performed by a context-
guessing machine, an abstract machine that guesses the most-likely context of
a given input. We theoretically analyze the invariance imposed by such
counterfactual data augmentations and describe an exemplar NLP task where
counterfactual data augmentation by a context-guessing machine does not lead
to robust OOD classifiers.

##  1 Introduction

Despite its tremendous success, deep learning suffers from a significant
challenge of robust out-of-distribution (OOD) predictions when the test
distribution is different from the training distribution, especially due to
its inclination to learn spurious patterns and shortcuts to solve the task [Jo
and Bengio, 2017, Geirhos et al., 2020, Poliak et al., 2018, D’Amour et al.,
2020]. Invariant Risk Minimization and similar methods [Arjovsky et al., 2019,
Bellot and van der Schaar, 2020, Krueger et al., 2021] propose to solve this
by learning representations that are invariant across multiple environments
but can be insufficient for OOD generalization without additional assumptions
Ahuja et al. [2021]. Recent works have increasingly used causal language to
formally define and learn non-spurious representations [Wang and Jordan, 2021,
Veitch et al., 2021] in order to be robust in OOD tasks. Veitch et al. [2021],
Mouli and Ribeiro [2022] define counterfactual invariance to spurious features
as a requirement for robust OOD predictors.

A simple way of (approximately) achieving counterfactual-invariant predictors
is via counterfactual data augmentations (CDA) [Lu et al., 2020, Kaushik et
al., 2019, Sauer and Geiger, 2021], where one augments the training data with
inputs generated from different spurious features. This enables a predictor to
learn to be invariant to these spurious features. Lu et al. [2020], Zmigrod et
al. [2019], Maudslay et al. [2019] use counterfactual data augmentation to
mitigate gender biases in natural language models, for example by
counterfactually modifying the gendered words in the text. Kaushik et al.
[2019, 2020], Teney et al. [2020] use human annotators to generate
counterfactual examples by making minimal changes to a given text, although
this approach may not achieve the desired robustness due to lack of diversity
in augmented examples [Joshi and He, 2021]. Von Kügelgen et al. [2021] uses
self-supervision and data augmentation to provably disentangle content from
style in vision tasks. Other works have used pretrained models to
counterfactually augment smaller datasets [Hasan and Talbert, 2021, Liu et
al., 2021]. While these works propose varied ways of performing counterfactual
data augmentations, the general principle remains the same: To obtain
representations that are either disentangled or counterfactually-invariant to
spurious features (Definition 1).

In this work, we show how counterfactual data augmentations may not achieve
the desired counterfactual invariance to spurious associations if these
augmentations are performed by a context-guessing machine (Definition 2). We
define a context-guessing machine as an abstract machine (ML model, human
annotator or algorithm) that infers the most-likely context of a given input
$x$ before performing counterfactual modifications. We show that performing
counterfactual changes with the most-likely context rather than considering
all possible contexts can result in a representation that is not
counterfactually invariant (Theorem 1). Our analysis suggests that one must be
careful while designing counterfactual data augmentation methods (e.g.,
eliciting counterfactual examples from human annotators) to avoid the bias
introduced from guessing a particular context for the given example.

##  2 Counterfactual Invariance

We begin with a brief discussion of structural causal models and the
definition of counterfactual variables which will be helpful in defining
counterfactual-invariant representations.

Figure 1: SCM over the observed input $X$ and the corresponding label $Y$. $X$
is obtained from two variables $C$ and $Z$ with only $C$ affecting the label
$Y$ and $Z$ is spurious. $U_{X}$ and $U_{Y}$ denote the background noise
variables in the SCM. The associational task is to predict $Y$ from $X$. Since
$Y$ depends only on $C$, we wish to learn a representation
$\Gamma:{\mathcal{X}}\to{\mathbb{R}}^{d}$ of the input $X$ that is
counterfactually-invariant to $Z$.

#### Structural Causal Model.

A structural causal model (SCM) [Pearl, 2009, Chapter 7] describes the causal
relationships between all the relevant variables and encodes the assumptions
on how the observed data is generated. An SCM consists of two sets of
variables: (a) endogenous variables, those that have a causal definition of
how they are obtained from other variables, and (b) exogenous variables, those
that are not described by the given causal model, but affect the endogenous
variables. For example, consider the SCM given below

$\displaystyle X$ $\displaystyle=f_{X}(Z,C)+U_{X}$ $\displaystyle Y$
$\displaystyle=f_{Y}(C)+U_{Y}\>,$

where $\\{X,Y\\}$ are observed endogenous variables and
$\\{U_{X},U_{Y},Z,C\\}$ are unobserved exogenous variables. A (given)
distribution over the exogenous variables $P(U_{X},U_{Y},Z,C)$ entails a
distribution over the endogenous variables $P(X,Y)$. This SCM can be
represented as a causal graph as shown in Figure 1. A typical learning task is
to predict $Y$ from $X$; note that the task is associational, there is no
causal link from $X$ to $Y$.

#### Counterfactuals.

Counterfactuals describe a what-if question given a particular observation.
For example, observing $X=x$, the counterfactual question can be “what would
be the value of $X$ had $Z=z$?”. We express this question using the
counterfactual random variable $X(Z=z)|X=x$. Given the complete structural
causal model, the counterfactual variable $X(Z=z)|X=x$ can be computed as
follows [Pearl, 2009, Chapter 7]:

  1. 1.

(Abduction.) Compute $P(\mathcal{U}|X=x)$ where $\mathcal{U}$ is the set of
all exogenous variables.

  2. 2.

(Action.) Perform the intervention $\text{\em do}(Z=z)$ in the given SCM.

  3. 3.

(Prediction.) Compute the distribution of $X$ in the modified SCM using the
modified distribution for the exogenous variables.

We can write distribution of the counterfactual variable $X(Z=z)|X=x$ formally
as:

$\displaystyle P($ $\displaystyle X(Z=z)=x^{\prime}|X=x)=$ $\displaystyle\int
P(X=x^{\prime}|\text{\em
do}(Z=z),\mathcal{U}={\bm{u}})dP(\mathcal{U}={\bm{u}}|X=x)\>.$ (1)

The integral denotes the three steps of computing the counterfactuals: (i)
abduction step to obtain the distribution of the exogenous variables
$P(\mathcal{U}|X=x)$, (ii) making the desired intervention $\text{\em
do}(Z=z)$, and (iii) computing the endogenous variable $X$ under intervention
using the abducted distribution. An important point to remember while
computing counterfactuals is that they need not only deal with individual
realizations, i.e., given $X=x$, there can be a population of individuals
given by the distribution $P(\mathcal{U}|X=x)$. The do-operation is then
applied to all these individuals.

#### Counterfactual-invariant representations.

Now we are ready to describe counterfactual-invariant representation defined
in Mouli and Ribeiro [2022], Veitch et al. [2021]. Veitch et al. [2021] define
the counterfactual variable using the potential outcomes notation
$X(z^{\prime})$, i.e., what would $X$ be had $Z=z^{\prime}$ leaving all else
fixed. While we use the notation of Mouli and Ribeiro [2022], the definitions
are equivalent when $\text{supp}(Z^{\text{te}})=\text{supp}(Z)$, as assumed
throughout this work.

######  Definition 1 (Counterfactual-invariant representations [Mouli and
Ribeiro, 2022]).

Given any SCM with at least two variables $X$ and $Z$, a representation
$\Gamma_{\text{cf}}:{\mathcal{X}}\to{\mathbb{R}}^{d}$, $d\geq 1$ of $X$ is
counterfactual-invariant to the variable $Z$ if

$\displaystyle\Gamma_{\text{cf}}(x)=\Gamma_{\text{cf}}(X(Z=z^{\prime})|X=x)$
(2)

almost everywhere, $\forall z^{\prime}\in\text{supp}(Z),\forall
x\in\text{supp}(X)$, where $\text{supp}(A)$ is the support of random variable
$A$.

The counterfactual variable $X(Z=z^{\prime}|X=x)$ in the RHS of Equation 2 is
as defined in Section 2. Then, Equation 2 says that $\Gamma_{\text{cf}}$
should have the same output $\Gamma_{\text{cf}}(x)$ for all values in the
support of the counterfactual random variable $X(Z=z^{\prime})|X=x$.
Revisiting the SCM in Figure 1, we can see that an OOD robust classifier
should use representations that are counterfactual invariant to the spurious
features $Z$ (as $Z$ does not affect $Y$). A common way of obtaining
counterfactual invariant representations is to augment counterfactual examples
$(x^{\prime},y)$ for every data sample $(x,y)$ with $x^{\prime}\sim
P(X(Z=z^{\prime})|X=x)$ for $z^{\prime}\in\text{supp}(Z)$. In the next
section, we look at an example of counterfactual data augmentation in the
context of classifying text reviews and showcase a scenario when it does not
lead to robust classifiers.

##  3 Example: Counterfactual Data Augmentation in NLP

$U_{X}$ | $Z$ | $C$ | $U_{Y}$ | $X$ | $Y$
---|---|---|---|---|---
$1$ | like | [$\text{good}_{1}$] | 0 | [$\text{good}_{1}$, positive tone] | helpful
$1$ | dislike | [$\text{good}_{1}$] | 0 | [$\text{good}_{1}$, negative tone] | helpful
$-1$ | like | [$\text{good}_{1}$] | 0 | [$\text{good}_{1}$, neutral tone] | helpful
$-1$ | dislike | [$\text{good}_{1}$] | 0 | [$\text{good}_{1}$, positive tone] | helpful
$1$ | like | [$\text{poor}_{1}$] | 0 | [$\text{poor}_{1}$, positive tone] | not helpful
$1$ | dislike | [$\text{poor}_{1}$] | 0 | [$\text{poor}_{1}$, negative tone] | not helpful
$-1$ | like | [$\text{poor}_{1}$] | 0 | [$\text{poor}_{1}$, neutral tone] | not helpful
$-1$ | dislike | [$\text{poor}_{1}$] | 0 | [$\text{poor}_{1}$, positive tone] | not helpful
. . . |  . . . |  . . . |  . . . |  . . . |  . . .
Table 1:  An example where counterfactual data augmentation with a context-
guessing machine does not lead to a counterfactual-invariant representation.
The table shows a succinct description of the structural causal model for a
review classification task (associated causal graph in Figure 1). $X$ and $Y$
denote the observed text review and the corresponding helpfulness label
respectively. The associational task is to predict $Y$ from $X$. Input $X$ is
obtained as a function of two unobserved variables $C$ and $Z$. $C$ denotes
the actual content describing the product and directly affects the helpfulness
label $Y$. We show two possible values for $C$ denoted [$\text{good}_{1}$] and
[$\text{poor}_{1}$] for simplicity representing particular good and poor
quality contents respectively. $Z$ denotes the sentiment of the reviewer about
the product. $U_{X}$ denotes the different types of reviewers, straightforward
($U_{X}=1$) or sarcastic ($U_{X}=-1$). For a straightforward individual,
$Z=\texttt{like}$ implies that $X$ has a positive tone, whereas for a
sarcastic individual, $Z=\texttt{dislike}$ implies that $X$ has a positive
tone. Finally, since $Y$ depends only on $C$ and not on the sentiment $Z$, we
wish to learn a representation $\Gamma:{\mathcal{X}}\to{\mathbb{R}}^{d}$ of
the input $X$ that is counterfactually-invariant to $Z$ using counterfactual
DA. However, a context-guessing machine infers the most likely context, for
example, that positive tone is from a straightforward reviewer who likes the
product, and does CDA under this context. This does not result in
counterfactual invariance as the alternative context for the positive tone—a
sarcastic reviewer who dislikes the product—is not considered.

In this section, we consider an example NLP task of predicting the helpfulness
of a product review while being counterfactually-invariant to the sentiment of
the review which is spurious for this task [Veitch et al., 2021].

#### Structural causal model for review classifiation.

We begin with the structural causal model that generates the text $X$ and the
helpfulness label $Y$ (associated causal graph in Figure 1). In this example,
$Z$ denotes the sentiment of the reviewer about the product (like or dislike),
$C$ denotes the content describing the product, $U_{X}$ is the type of
reviewer, crudely categorized as straightforward ($U_{X}=1$) or sarcastic
($U_{X}=-1$), and $U_{Y}$ is label noise (assumed to be zero). Table 1
concretely defines how these variables affect the text $X$ and its helpfulness
label $Y$. Since it is not feasible to describe all possible text inputs $X$,
we use placeholders $[\leavevmode\nobreak\ \cdots\leavevmode\nobreak\ ]$ to
describe the type of text, while the actual content of the review may vary
across the dataset. For example, [$\text{good}_{1}$, positive tone] represents
a particular review with good quality content and written in a positive tone.
Further assume that $P(U_{X}=1)=0.9$, i.e., straightforward reviewers are a
lot more likely than sarcastic ones, $P(Z=\texttt{like})=0.5$, and
$P(U_{Y}=0)=1$.

A straightforward individual’s sentiment affects the text in the usual way
(e.g., $Z=\texttt{like}$ $\implies$ $X$ has a positive tone). On the other
hand, the effect of a sarcastic individual’s sentiment on $X$ is more
complicated: $Z=\texttt{dislike}$ $\implies$ $X$ has a positive tone, and
$Z=\texttt{like}$ $\implies$ $X$ has a neutral tone. Now, it is clear from
Table 1 (also from Figure 1) that the sentiment $Z$ is spurious for the label
$Y$ which only depends on $C$. However, a classifier may not learn this
invariance to $Z$ automatically from training data, especially if all the
possible values of $X$ are not seen during training. Thus, our goal is to
obtain a representation that is counterfactually-invariant to the sentiment
$Z$ which will allow us to build OOD robust classifiers. That is, we want to
augment the original dataset with counterfactual data with respect to the
sentiment $Z$ in order to obtain the counterfactual-invariant representation.

#### Counterfactual data augmentation (CDA).

Given a text input
$x=[\text{good}_{1},\text{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}positive
tone}}]$, Definition 1 enforces the invariance considering all possible
contexts ($Z=\texttt{like},Z=\texttt{dislike}$), thus considering sarcastic
individuals as well as straightforward ones. Considering both contexts, CDA
augments
$[\text{good}_{1},\text{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}negative
tone}}]$ and
$[\text{good}_{1},\text{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}neutral
tone}}]$, thus enforcing the following invariance over the representation
$\Gamma_{\text{cf}}$:
$\Gamma_{\text{cf}}([\text{good}_{1},\text{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}positive
tone}}])=\Gamma_{\text{cf}}([\text{good}_{1},\text{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}negative
tone}}])=\Gamma_{\text{cf}}([\text{good}_{1},\text{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}neutral
tone}}])$.

Next we show that a bias may be introduced if the counterfactual data
augmentation algorithm (e.g., using humans-in-the-loop) does not consider all
the possible contexts, but instead guesses the most-likely context. We will
denote this type of augmentation machine as a context-guessing machine. As
before, consider the text input
$x=[\text{good}_{1},\text{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}positive
tone}}]$. A context-guessing machine infers the most-likely context (i.e.,
maximum a posteriori estimate) of the text as $Z=\texttt{like}$ due to the
positive tone, thus indirectly only considering straightforward individuals
with $U_{X}=1$. The counterfactually augmented example is
$x^{\prime}=[\text{good}_{1},\text{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}negative
tone}}]$ with the same label $Y=\texttt{helpful}$ and enforces the following
invariance on $\Gamma_{\text{cda}}$:
$\Gamma_{\text{cda}}([\text{good}_{1},\text{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}positive
tone}}])=\Gamma_{\text{cda}}([\text{good}_{1},\text{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}negative
tone}}])$. But, clearly this is not enough for counterfactual-invariance as
$\Gamma_{\text{cda}}([\text{good}_{1},\text{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}neutral
tone}}])$ can be arbitrarily different. Thus, a classifier that uses the
representation $\Gamma_{\text{cda}}$ is not guaranteed to be robust to OOD
changes to sentiment $Z$.

##  4 CDA by a context-guessing machine

In this section, we analyze the counterfactual data augmentations performed by
a context-guessing machine more formally. We begin with a definition of a
context-guessing machine, an abstract machine (e.g., ML model, human annotator
or algorithm) that guesses the most-likely context for the given input $x$,
i.e., most-likely instantiation of a parent of $x$. Throughout this section,
our definitions consider a single parent $Z$ of $X$, but they can be easily
extended for multiple parent (context) variables.

######  Definition 2 (Context-guessing machine).

Given any SCM with $Z\rightarrow X$, a context-guessing machine assumes the
context of $x$ to be $z^{\text{MAP}}(x)=\operatorname*{argmax}_{z}P(Z=z|X=x)$,
which is the maximum a posteriori (MAP) estimate of $Z$ given $X=x$.

In Definition 3, we define counterfactual data augmentation with such a
context-guessing machine which works as follows: (a) Given $X=x$, the context
is inferred to be $Z=z^{\text{MAP}}(x)$, and (b) a counterfactual example is
generated conditioned on the inferred context while preserving the label.

######  Definition 3 (Guess-CDA).

Counterfactual data augmentation derived from a context-guessing machine is
defined as follows: For every $(x,y)$ in the training data $\mathcal{D}$, an
augmented example is $(x^{\prime},y)$ where $x^{\prime}\sim
P(X(Z=z)|X=x,Z=z^{\text{MAP}}(x))$ for $z\in\text{supp}(Z)$.

The variable $X(Z=z)|X=x,Z=z^{\text{MAP}}(x)$ in Definition 3 is different
from the counterfactual variable of interest $X(Z=z)|X=x$. Recall that the
definition of counterfactual variables in Section 2 involved abducted
distributions over the set of exogenous $\mathcal{U}$ given the evidence. The
distribution of counterfactually-augmented examples in Definition 3 is given
by

$\displaystyle P($ $\displaystyle X(Z=z)=x^{\prime}|X=x,Z=z^{\text{MAP}}(x))=$
$\displaystyle\int P(X=x^{\prime}|\text{\em do}(Z=z),U_{X}=u)$
$\displaystyle\qquad\qquad dP(U_{X}=u|X=x,Z=z^{\text{MAP}}(x))\>,$ (3)

where the abducted distribution $P(U_{X}=u|X=x,Z=z^{\text{MAP}}(x))$ marks the
only difference from Section 2. Next, we explicitly define the invariance
imposed on a representation trained over the counterfactually-augmented data
of Definition 3.

######  Definition 4 (Guess-CDA-invariance).

Given any SCM with $Z\rightarrow X$, the invariance imposed on a
representation $\Gamma_{\text{cda}}:{\mathcal{X}}\to{\mathbb{R}}^{d}$, $d\geq
1$ of $X$ by the counterfactual data augmentation from a context-guessing
machine in Definition 3 is

$\displaystyle\Gamma_{\text{cda}}(x)=\Gamma_{\text{cda}}(X(Z=z)|X=x,Z=z^{\text{MAP}}(x))$
(4)

almost everywhere, $\forall z\in\text{supp}(Z),\forall x\in\text{supp}(X)$,
where $z^{\text{MAP}}(x)=\operatorname*{argmax}_{z}P(Z=z|X=x)$ is the maximum
a posteriori (MAP) estimate of $Z$ given $X=x$ and $\text{supp}(A)$ is the
support of random variable $A$.

The support of the counterfactual variable in the RHS of Equation 4 can be
different than the support of that in Equation 2 as illustrated by the example
in Section 3. Our next theorem formalizes this notion and states that the
invariance imposed by Definition 4 on $\Gamma_{\text{cda}}$ is weaker than the
desired invariance of Definition 1. Hence, when performing CDA with a context-
guessing machine, we are not guaranteed to obtain a counterfactually-invariant
representation.

######  Theorem 1 ($\Gamma_{\text{cda}}$ of Definition 4 is not
counterfactually-invariant).

Given any SCM with $Z\to X$, let $\Gamma_{\text{cda}}$ denote the
representation defined in Definition 4 obtained via counterfactual data
augmentation from a context-guessing machine. Then, in general,
$\Gamma_{\text{cda}}$ is not counterfactual-invariant according to Definition
1.

We prove the theorem in Section A.1 in two steps. (a) First, we show that the
invariance restriction imposed over $\Gamma_{\text{cda}}$ in Definition 4 is
never stronger than that imposed over $\Gamma_{\text{cf}}$ in Equation 2 by
comparing the supports of the RHS in Equations 2 and 4. That is, we show
$\bigcup_{z}\text{supp}(X(Z=z)|X=x,Z=z^{\text{MAP}}(x))\subseteq\bigcup_{z}\text{supp}(X(Z=z)|X=x)$.
(b) Then, we show a linear SCM example where the invariance restriction of
Definition 4 is strictly weaker than that of Definition 1. In this simple
example, Definition 1 forces $\Gamma_{\text{cf}}$ to be a constant function,
whereas Definition 4 allows $\Gamma_{\text{cda}}$ to take two different values
based on the input $x$.

##  5 Solution

The solution to the challenge described above is relatively simple. We just
need to avoid guessing the most likely context. The support (or at least all
likely contexts $Z$) must be present in the data augmentation procedure. That
means, for instance, giving context suggestions to human annotators either by
sampling from $P(Z|X)$ or by considering all the likely contexts based on
$P(Z|X)$.

##  6 Conclusions

Counterfactual invariance to spurious features is a desired property for OOD
robustness of predictors. A general way of approximately achieving
counterfactual invariance is via counterfactual data augmentations. In this
work, we studied counterfactual data augmentations performed by a context-
guessing machine and showed that a representation trained on the resultant
augmented data may not be counterfactual-invariant. Our analysis suggests that
one must be careful while designing counterfactual data augmentation methods
(e.g., eliciting counterfactual examples from human annotators) to avoid the
bias introduced from guessing a particular context for the given example.

###### Acknowledgements.

This work was funded in part by the National Science Foundation (NSF) Awards
CAREER IIS-1943364 and CCF-1918483, the Purdue Integrative Data Science
Initiative, and the Wabash Heartland Innovation Network. Any opinions,
findings and conclusions or recommendations expressed in this material are
those of the authors and do not necessarily reflect the views of the sponsors.

## References

  * Ahuja et al. [2021] Kartik Ahuja, Ethan Caballero, Dinghuai Zhang, Jean-Christophe Gagnon-Audet, Yoshua Bengio, Ioannis Mitliagkas, and Irina Rish.  Invariance principle meets information bottleneck for out-of-distribution generalization.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Arjovsky et al. [2019] Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz.  Invariant risk minimization.  _arXiv preprint arXiv:1907.02893_ , 2019.
  * Bellot and van der Schaar [2020] Alexis Bellot and Mihaela van der Schaar.  Accounting for unobserved confounding in domain generalization.  _arXiv preprint arXiv:2007.10653_ , 2020.
  * D’Amour et al. [2020] Alexander D’Amour, Katherine Heller, Dan Moldovan, Ben Adlam, Babak Alipanahi, Alex Beutel, Christina Chen, Jonathan Deaton, Jacob Eisenstein, Matthew D Hoffman, et al.  Underspecification presents challenges for credibility in modern machine learning.  _arXiv preprint arXiv:2011.03395_ , 2020.
  * Geirhos et al. [2020] Robert Geirhos, Jörn-Henrik Jacobsen, Claudio Michaelis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix A Wichmann.  Shortcut learning in deep neural networks.  _Nature Machine Intelligence_ , 2(11):665–673, 2020.
  * Hasan and Talbert [2021] Md Golam Moula Mehedi Hasan and Douglas A Talbert.  Counterfactual examples for data augmentation: A case study.  In _The International FLAIRS Conference Proceedings_ , volume 34, 2021\.
  * Jo and Bengio [2017] Jason Jo and Yoshua Bengio.  Measuring the tendency of cnns to learn surface statistical regularities.  _arXiv preprint arXiv:1711.11561_ , 2017.
  * Joshi and He [2021] Nitish Joshi and He He.  An investigation of the (in) effectiveness of counterfactually augmented data.  _arXiv preprint arXiv:2107.00753_ , 2021.
  * Kaushik et al. [2019] Divyansh Kaushik, Eduard Hovy, and Zachary C Lipton.  Learning the difference that makes a difference with counterfactually-augmented data.  _arXiv preprint arXiv:1909.12434_ , 2019.
  * Kaushik et al. [2020] Divyansh Kaushik, Amrith Setlur, Eduard Hovy, and Zachary C Lipton.  Explaining the efficacy of counterfactually augmented data.  _arXiv preprint arXiv:2010.02114_ , 2020.
  * Krueger et al. [2021] David Krueger, Ethan Caballero, Joern-Henrik Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang, Remi Le Priol, and Aaron Courville.  Out-of-distribution generalization via risk extrapolation (rex).  In _International Conference on Machine Learning_ , pages 5815–5826. PMLR, 2021.
  * Liu et al. [2021] Qi Liu, Matt Kusner, and Phil Blunsom.  Counterfactual data augmentation for neural machine translation.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 187–197, 2021.
  * Lu et al. [2020] Kaiji Lu, Piotr Mardziel, Fangjing Wu, Preetam Amancharla, and Anupam Datta.  Gender bias in neural natural language processing.  In _Logic, Language, and Security_ , pages 189–202. Springer, 2020\.
  * Maudslay et al. [2019] Rowan Hall Maudslay, Hila Gonen, Ryan Cotterell, and Simone Teufel.  It’s all in the name: Mitigating gender bias with name-based counterfactual data substitution.  _arXiv preprint arXiv:1909.00871_ , 2019.
  * Mouli and Ribeiro [2022] S Chandra Mouli and Bruno Ribeiro.  Asymmetry learning for counterfactually-invariant classification in ood tasks.  In _International Conference on Learning Representations_ , 2022.
  * Pearl [2009] Judea Pearl.  _Causality_.  Cambridge university press, 2009.
  * Poliak et al. [2018] Adam Poliak, Jason Naradowsky, Aparajita Haldar, Rachel Rudinger, and Benjamin Van Durme.  Hypothesis only baselines in natural language inference.  _arXiv preprint arXiv:1805.01042_ , 2018.
  * Sauer and Geiger [2021] Axel Sauer and Andreas Geiger.  Counterfactual generative networks.  _arXiv preprint arXiv:2101.06046_ , 2021.
  * Teney et al. [2020] Damien Teney, Ehsan Abbasnedjad, and Anton van den Hengel.  Learning what makes a difference from counterfactual examples and gradient supervision.  In _European Conference on Computer Vision_ , pages 580–599. Springer, 2020.
  * Veitch et al. [2021] Victor Veitch, Alexander D’Amour, Steve Yadlowsky, and Jacob Eisenstein.  Counterfactual invariance to spurious correlations in text classification.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Von Kügelgen et al. [2021] Julius Von Kügelgen, Yash Sharma, Luigi Gresele, Wieland Brendel, Bernhard Schölkopf, Michel Besserve, and Francesco Locatello.  Self-supervised learning with data augmentations provably isolates content from style.  _Advances in neural information processing systems_ , 34:16451–16467, 2021.
  * Wang and Jordan [2021] Yixin Wang and Michael I Jordan.  Desiderata for representation learning: A causal perspective.  _arXiv preprint arXiv:2109.03795_ , 2021.
  * Zmigrod et al. [2019] Ran Zmigrod, Sabrina J Mielke, Hanna Wallach, and Ryan Cotterell.  Counterfactual data augmentation for mitigating gender stereotypes in languages with rich morphology.  _arXiv preprint arXiv:1906.04571_ , 2019.

##  Appendix A Appendix

###  A.1 Proof of Theorem 1

See 1

###### Proof.

We prove the theorem in in two steps. (a) First, we show that the invariance
restriction imposed over $\Gamma_{\text{cda}}$ in Definition 4 is never
stronger than that imposed over $\Gamma_{\text{cf}}$ in Equation 2 by
comparing the supports of the RHS in Equations 2 and 4. That is, we show
$\bigcup_{z^{\prime}}\text{supp}(X(Z=z^{\prime})|X=x,Z=z^{\text{MAP}}(x))\subseteq\bigcup_{z^{\prime}}\text{supp}(X(Z=z^{\prime})|X=x)$.
(b) Next, we show a linear SCM example where invariance restriction of
Definition 4 is strictly weaker than that of Definition 1.

(a): Consider the random variable $X(Z=z^{\prime})|X=x$.

$\displaystyle P($ $\displaystyle X(Z=z^{\prime})=x^{\prime}|X=x)$
$\displaystyle=\int
P(X(Z=z^{\prime})=x^{\prime}|Z=z,U_{X}=u)dP(Z=z,U_{X}=u|X=x)$
$\displaystyle=\int P(X=x^{\prime}|\text{\em
do}(Z=z^{\prime}),U_{X}=u)dP(U_{X}=u|X=x)\>,$ (5)

where the first term within the integral is rewritten using a do-expression
and does not depend on $Z=z$.

Consider the random variable $X(Z=z^{\prime})|X=x,Z=z^{\text{MAP}}(x)$.

$\displaystyle P($ $\displaystyle
X(Z=z^{\prime})=x^{\prime}|X=x,Z=z^{\text{MAP}}(x))$ $\displaystyle=\int
P(X(Z=z^{\prime})=x^{\prime}|Z=z,U_{X}=u)dP(Z=z,U_{X}=u|X=x,Z=z^{\text{MAP}}(x))$
$\displaystyle=\int P(X=x^{\prime}|\text{\em
do}(Z=z^{\prime}),U_{X}=u)dP(U_{X}=u|X=x,Z=z^{\text{MAP}}(x))\>,$ (6)

where once again, we rewrite the first term using a do-expression.

Noting that $P(U_{X}=u|X=x)=0\implies P(U_{X}=u|X=x,Z=z^{\text{MAP}}(x))=0$,

$\displaystyle x^{\prime}\notin\text{supp}(X(Z=z^{\prime})|X=x)\implies
P(X(Z=z^{\prime})=x^{\prime}|X=x)=0$ $\displaystyle\implies$
$\displaystyle\int P(X=x^{\prime}|\text{\em
do}(Z=z^{\prime}),U_{X}=u)dP(U_{X}=u|X=x)=0$ (From Section A.1)
$\displaystyle\implies$ $\displaystyle\int P(X=x^{\prime}|\text{\em
do}(Z=z^{\prime}),U_{X}=u)dP(U_{X}=u|X=x,Z=z^{\text{MAP}}(x))=0$
$\displaystyle\implies$ $\displaystyle
P(X(Z=z^{\prime})=x^{\prime}|X=x,Z=z^{\text{MAP}}(x))=0$ (From Section A.1)
$\displaystyle\implies$ $\displaystyle
x^{\prime}\notin\text{supp}(X(Z=z^{\prime})|X=x,Z=z^{\text{MAP}}(x))\>.$

Thus, we have for all $z^{\prime}\in\text{supp}(Z)$,
$\text{supp}(X(Z=z^{\prime})|X=x,Z=z^{\text{MAP}}(x))\subseteq\text{supp}(X(Z=z^{\prime})|X=x)$,
and hence,
$\bigcup_{z^{\prime}}\text{supp}(X(Z=z^{\prime})|X=x,Z=z^{\text{MAP}}(x))\subseteq\bigcup_{z^{\prime}}\text{supp}(X(Z=z^{\prime})|X=x)$.
This shows that invariance restriction over the representation
$\Gamma_{\text{cda}}$ is never stronger than that over $\Gamma_{\text{cf}}$.
Next, we show an example where the restriction over $\Gamma_{\text{cda}}$ is
strictly weaker.

(b): Consider a simple SCM with $X=Z+2U_{X}$ where $U_{X}\in\\{-1,0,1\\}$,
$Z\in\\{-1,1\\}$ and subsequently $X\in\\{-3,-1,1,3\\}$. Let
$P(U_{X}=1)=P(U_{X}=-1)=0.4$ and $P(U_{X}=0)=0.2$. Also, let
$P(Z=1)=P(Z=-1)=0.5$.

#### Invariance imposed by Definition 1 on $\Gamma_{\text{cf}}$.

For each $x\in\\{-3,-1,1,3\\}$, we need to impose the condition:

$\Gamma_{\text{cf}}(x)=\Gamma_{\text{cf}}(X(Z=1)|X=x)=\Gamma_{\text{cf}}(X(Z=-1)|X=x)\>.$

In what follows, we show the invariance imposed with $x=1$. Consider
$X(Z=1)|X=1$ whose distribution is given by

$\displaystyle P(X(Z=1)|X=1)$
$\displaystyle=\sum_{u\in\\{-1,0,1\\}}P(X|do(Z=1),U_{X}=u)P(U_{X}=u|X=1)$
$\displaystyle=\delta_{1}\cdot P(U_{X}=0|X=1)+\delta_{3}\cdot P(U_{X}=1|X=1)$
$\displaystyle=\delta_{1}\cdot\frac{1}{3}+\delta_{3}\cdot\frac{2}{3}\>,$

where $\delta_{c}$ is the Dirac measure at $c$. Since the support of
$X(Z=1)|X=1$ is $\\{1,3\\}$, we obtain our first invariance constraint:
$\Gamma_{\text{cf}}(1)=\Gamma_{\text{cf}}(3)$. Next consider $X(Z=-1)|X=1$

$\displaystyle P(X(Z=-1)|X=1)$
$\displaystyle=\sum_{u\in\\{-1,0,1\\}}P(X|do(Z=-1),U_{X}=u)P(U_{X}=u|X=1)$
$\displaystyle=\delta_{-1}\cdot P(U_{X}=0|X=1)+\delta_{1}\cdot P(U_{X}=1|X=1)$
$\displaystyle=\delta_{-1}\cdot\frac{1}{3}+\delta_{1}\cdot\frac{2}{3}\>.$

Since the support of $X(Z=-1)|X=1$ is $\\{1,-1\\}$, we obtain
$\Gamma_{\text{cf}}(1)=\Gamma_{\text{cf}}(-1)$.

Repeating the above procedure for every $x\in\\{-3,-1,1,3\\}$, we obtain the
following invariance for $\Gamma_{\text{cf}}$:
$\Gamma_{\text{cf}}(1)=\Gamma_{\text{cf}}(-1)=\Gamma_{\text{cf}}(-3)=\Gamma_{\text{cf}}(3)$.
In words, $\Gamma_{\text{cf}}$ is forced to be constant in this example.

#### Invariance imposed by Definition 4 on $\Gamma_{\text{cda}}$.

For each $x\in\\{-3,-1,1,3\\}$, we need to impose the condition:

$\Gamma_{\text{cda}}(x)=\Gamma_{\text{cda}}(X(Z=1)|X=x,Z=z^{\text{MAP}}(x))=\Gamma_{\text{cda}}(X(Z=-1)|X=x,z^{\text{MAP}}(x))\>.$

In what follows, we show the invariance imposed with $x=1$. First, we can
obtain $z^{\text{MAP}}(1)=\operatorname*{argmax}_{z=\\{-1,1\\}}P(Z=z|X=1)=-1$.
Then consider $X(Z=1)|X=1,Z=z^{\text{MAP}}(1)$ with distribution

$\displaystyle P(X(Z=1)|X=1,Z=-1)$
$\displaystyle=\sum_{u\in\\{-1,0,1\\}}P(X|do(Z=1),U_{X}=u)P(U_{X}=u|X=1,Z=-1)$
$\displaystyle=\delta_{3}\>,$

where once again $\delta_{c}$ denotes the Dirac measure at $c$. Since the
support of $X(Z=1)|X=1,Z=-1$ is $\\{3\\}$, we obtain
$\Gamma_{\text{cda}}(1)=\Gamma_{\text{cda}}(3)$. The support of
$X(Z=-1)|X=1,Z=-1$ is simply $\\{1\\}$ and only imposes the trivial constraint
$\Gamma_{\text{cda}}(1)=\Gamma_{\text{cda}}(1)$.

Repeating the above procedure for every $x\in\\{-3,-1,1,3\\}$, we obtain the
following invariance for $\Gamma_{\text{cda}}$:
$\Gamma_{\text{cda}}(1)=\Gamma_{\text{cda}}(3)$ and
$\Gamma_{\text{cda}}(-1)=\Gamma_{\text{cf}}(-3)$. Note that unlike
$\Gamma_{\text{cf}}$, $\Gamma_{\text{cda}}$ is not enforced to be a constant
in this example; it can be such that
$\Gamma_{\text{cda}}(1)\neq\Gamma_{\text{cda}}(-1)$. Thus, there is a
representation that satisfies the invariance imposed in Definition 4 but is
not counterfactually-invariant as defined in Definition 1.

∎