Proof Section to an Introduction to Credal Sets and Infra-Bayes Learnability

[Brittany Gelb]

This post accompanies An Introduction to Credal Sets and Infra-Bayes Learnability.

Notation

We use $\Delta X$ to denote the space of probability distributions over a set $X$, which is assumed throughout to be a compact metric space. We use $\square X$ to denote the set of credal sets over $X.$

Given $f:X\to R$ and $m\in \Delta X$, let $m\left(f\right):=E_m\left[f\right].$

Let $C(X,Y)$ denote the space of continuous functions from $X$ to $Y.$

Proof of Lemma 1

Lemma 1: If $A$ and $O$ are finite, the set of countably infinite histories $(A\times O{)}^{\omega }$ is a compact metric space under the metric $d(h,h^{\prime })={\gamma }^{t(h,h^{\prime })}$ where $\gamma \in (0,1)$ and $t(h,h^{\prime })$ is the time of first difference between $h$ and $h^{\prime }.$

Proof. The space $A\times O$ is compact under the discrete topology since it is finite. Therefore, $(A\times O{)}^{\omega }$ is compact under the product topology $P$ by Tychonoff’s theorem. The stated metric induces a topology $M$. By the definition of compactness, it is sufficient to show that all basis elements of $M$ are contained in $P.$

The basis elements of $M$ have the form

$$B_{\delta }\left(h\right):=\{h^{\prime }\in (A\times O{)}^{\omega }:d(h,h^{\prime })<\delta \}$$

for $h\in (A\times O{)}^{\omega }$ and $\delta \in (0,1].$

Furthermore, sets of the form

$$U_{h,N}:=\prod _{i=0}^N\left\{h_i\right\}\times \prod _{i=N+1}^{\infty }(A\times O)$$

are basis elements of $P$ where $h_i\in A\times O$ and $N\in N.$

Given $\delta \in (0,1],$ define $N\left(\delta \right)=max\{n\in N:{\gamma }^n\ge \delta \}$. We will verify that ${\gamma }^{t(h,h^{\prime })}<\delta$ if and only if $d(h,h^{\prime })\ge N\left(\delta \right)+1.$ Note that if $d(h,h^{\prime })\ge N\left(\delta \right)+1>N\left(\delta \right),$ then by construction, ${\gamma }^{t(h,h^{\prime })}<\delta .$ For the other direction, we have that if $d(h,h^{\prime })\le N\left(\delta \right),$ then since $\gamma \in (0,1),$ ${\gamma }^{t(h,h^{\prime })}\ge {\gamma }^{N\left(\delta \right)}\ge \delta .$ By the contrapositive, if ${\gamma }^{t(h,h^{\prime })}<\delta ,$ then $d(h,h^{\prime })\ge N\left(\delta \right)+1.$

Since $d(h,h^{\prime })\ge N\left(\delta \right)+1$ if and only if $h_i=h_i^{\prime }$ for $0\le i\le N\left(\delta \right)$, this proves that $U_{h,N\left(\delta \right)}$ and $B_{\delta }\left(h\right)$ are equal as sets. Thus all basis elements of $M$ are contained in $P,$ and $(A\times O{)}^{\omega }$ is compact in the metric topology. $\square$

Proof of Proposition 1

The following lemma is used both in the proof of Proposition 1 and Proposition 2.

Lemma 2: The set of deterministic policies $\Pi$ is first-countable under the product topology.

Proof: Let $\pi \in \Pi .$ We aim to show that $\pi$ has a countable neighborhood basis. Consider the collection $B$ of open sets in $\Pi$ of the form ${\prod }_{h_i\in (A\times O{)}^{\omega }}{U}_{h_i}$ where $U_{h_i}=\pi \left(h_i\right)$ for finitely many $h_i$ and otherwise $U_{h_i}=A.$ There is a bijection between $B$ and the set of finite binary sequences, so this collection is countable.

Let $N$ be a neighborhood of $\pi .$ By the definition of a basis, there exists a basis element $V$for the product topology such that $x\in V\subset N.$ By definition of the product topology, the set $V$ can be written as ${\prod }_{h_i\in (A\times O{)}^{\omega }}{V}_{h_i}$ where $V_{h_i}\ne A$ for finitely many $h_i.$ Since $x\in V,$ an element of $B$ is contained in $V$ and thus in $N.$ Therefore, $B$ is a countable neighborhood basis. $\square$

Proposition 1: Every crisp causal law $\Lambda :\Pi \to \square (A\times O{)}^{\omega }$ is continuous with respect to the product topology on $\Pi$ and the Hausdorff topology on $\square (A\times O{)}^{\omega }.$

Proof: By Lemma 2, $\Pi$ is first-countable under the product topology. Consequently, $\Lambda :\Pi \to \square (A\times O{)}^{\omega }$ is continuous if given a convergent sequence $\{{\pi }_n{\}}_{n\in N}$ such that ${\pi }_n\to \pi$, then $\Lambda \left({\pi }_n\right)\to \Lambda \left(\pi \right).$ Let such a convergent sequence $\{{\pi }_n{\}}_{n\in N}$ be given.

By definition, there exists a set of environments $E$ that generates $\Lambda .$ We will show convergence using the weak topology, so let $g:(A\times O{)}^{\omega }\to [0,1]$ be a 1-Lipschitz continuous function.

Since ${\pi }_n\to \pi ,$ given any finite time horizon $T<\infty ,$ there exists $N$ such that for all $n\ge N,$ ${\pi }_n$ and $\pi$ agree up to time $T.$ Furthermore, the set of destinies $(A\times O{)}^{\omega }$ can be partitioned into a disjoint union ${⨿}_{j=0}^{J\left(T\right)}{D}_j$ where $D_j$ is a set of destinies that are equal up to time $T$ and $J\left(T\right)<\infty .$ Note that by construction, if $h,h^{\prime }\in D_j,$ then $d(h,h^{\prime })\le {\gamma }^T.$

Then for every environment $\mu \in E,$

$$|E_{{\mu }^{{\pi }_n}}g-E_{{\mu }^{\pi }}g|$$$$=|\sum _{j=0}^{J\left(T\right)}{\int }_{D_j}gd{\mu }^{{\pi }_n}-{\int }_{D_j}gd{\mu }^{\pi }|$$$$\le \sum _{j=0}^{J\left(T\right)}|{\int }_{D_j}gd{\mu }^{{\pi }_n}-{\int }_{D_j}gd{\mu }^{\pi }|$$$$\le \sum _{j=0}^{J\left(T\right)}|{\int }_{D_j}\underset{h\in D_j}{sup}g\left(h\right)d{\mu }^{{\pi }_n}-{\int }_{D_j}\underset{h\in D_j}{inf}g\left(h\right)d{\mu }^{\pi }|$$$$=\sum _{j=0}^{J\left(T\right)}|\underset{h\in D_j}{sup}g\left(h\right){\mu }^{{\pi }_n}\left(D_j\right)-\underset{h\in D_j}{inf}g\left(h\right){\mu }^{\pi }\left(D_j\right)|.$$

For all $n\ge N,$ ${\mu }^{{\pi }_n}\left(D_j\right)={\mu }^{\pi }\left(D_j\right).$ By the 1-Lipschitz property of $g$ and the construction of $D_j,$

$$|\underset{h\in D_j}{sup}g\left(h\right)-\underset{h\in D_j}{inf}g\left(h\right)|\le \underset{h,h^{\prime }\in D_j}{sup}d(h,h^{\prime })\le {\gamma }^T.$$

Therefore,

$$\sum _{j=0}^{J\left(T\right)}|\underset{h\in D_j}{sup}g\left(h\right){\mu }^{{\pi }_n}\left(D_j\right)-\underset{h\in D_j}{inf}g\left(h\right){\mu }^{\pi }\left(D_j\right)|$$$$\le \sum _{j=0}^{J\left(T\right)}{\gamma }^T{\mu }^{\pi }\left(D_j\right)$$$$={\gamma }^T.$$

As $T$ can be taken arbitrarily large and $\gamma \in (0,1),$ $|E_{{\mu }^{{\pi }_n}}g-E_{{\mu }^{\pi }}g|$ tends to zero as $n$ tends to infinity. The Kantorovich-Rubinstein metric induces the weak topology on $\Delta (A\times O{)}^{\omega },$ so for all $\mu \in E,$ ${\mu }^{{\pi }_n}\to {\mu }^{\pi }.$ Therefore, $\Lambda \left({\pi }_n\right)\to \Lambda \left(\pi \right)$ in the Hausdorff topology. $\square$

Proof of Proposition 2 and Corollary 1

Corollary 1 below corresponds to Proposition 5 in this proof section of the original infra-Bayesianism sequence. The proof of that proposition was organized in three phases. Since we expand the ideas in more detail, we have several lemmas; “phase 1” is captured here in Lemma 5, and “phase 2″ and “phase 3” are captured here in Proposition 2. The other lemmas cover prerequisite ideas that are used in the proof.

The following lemma is a special case of Theorem 6.9 of [1]. We provide a simplified proof under the assumption that $X$ is a compact metric space using the fact that the set of all Lipschitz functions is dense in $C(X,[0,1\left]\right),$ the space of continuous functions from $X$ to $[0,1]$ [2].

Lemma 3: Let $X$ be a compact metric space, $f:X\to [0,1]$ be continuous, and $m\in \Delta X.$Then $m\mapsto m\left(f\right)$ is continuous as a function from $\Delta X$ with the Kantorovich-Rubinstein (KR-) metric to $[0,1].$

Proof. Since $\Delta X$ is a metric space, $\Delta X$ is first-countable. Thus $m\mapsto m\left(f\right)$ is continuous if $m_n\to m$ implies $m_n\left(f\right)\to m\left(f\right)$. Let $m_n\to m$ and $ϵ>0.$ By definition, there exists $N\in N$ such that for all $n\ge N,$

$$\underset{f_{\text{lip}}}{sup}|m_n\left(f_{\text{lip}}\right)-m\left(f_{\text{lip}}\right)|<ϵ,$$

where the supremum is taken over all 1-Lipschitz continuous functions $f_{\text{lip}}:X\to [-1,1].$

Suppose $f$ is 1-Lipschitz. Then $m_n\left(f\right)\to m\left(f\right)$ since

$$|m_n\left(f\right)-m\left(f\right)|\le \underset{f_{\text{lip}}}{sup}|m_n\left(f_{\text{lip}}\right)-m\left(f_{\text{lip}}\right)|<ϵ.$$

Suppose $f$ is $K$-Lipschitz. Then $\frac{1}{K}f$ is 1-Lipschitz. So, by the first case, there exists $N\in N$ such that for all $n\ge N,$

$$|m_n\left(\frac{1}{K}f\right)-m\left(\frac{1}{K}f\right)|<\frac{1}{K}ϵ.$$

By linearity of expectation, for all $n\ge N,$

$$|m_n\left(f\right)-m\left(f\right)|=K|m_n\left(\frac{1}{K}f\right)-m\left(\frac{1}{K}f\right)|<ϵ.$$

Suppose $f$ is continuous. By the density of the set of all Lipschitz functions in $C(X,[0,1\left]\right)$ [2], there exists a Lipschitz function $g:X\to [0,1]$ such that ${sup}_{x\in X}|f\left(x\right)-g\left(x\right)|<\frac{ϵ}{3}.$ By the second case, there exists $N\in N$ such that for all $n\ge N,$ $|m_n\left(g\right)-m\left(g\right)|<\frac{ϵ}{3}.$ Applying the triangle inequality, we obtain that for all $n\ge N,$

$$|m_n\left(f\right)-m\left(f\right)|$$$$=|m_n\left(f\right)-m_n\left(g\right)+m_n\left(g\right)-m\left(g\right)+m\left(g\right)-m\left(f\right)|$$$$\le |m_n\left(f\right)-m_n\left(g\right)|+|m_n\left(g\right)-m\left(g\right)|+|m\left(g\right)-m\left(f\right)|$$$$\le m_n\left(X\right)\underset{x\in X}{sup}|f\left(x\right)-g\left(x\right)|+\frac{ϵ}{3}+m\left(X\right)\underset{x\in X}{sup}|f\left(x\right)-g\left(x\right)|$$$$<\frac{ϵ}{3}+\frac{ϵ}{3}+\frac{ϵ}{3}<ϵ.$$

Here we have used the fact that $m,m_n\in \Delta X$ and thus $m\left(X\right)=m_n\left(X\right)=1.$ This shows that $m_n\left(f\right)\to m\left(f\right),$ which completes the proof by the remark at the beginning. $\square$

Lemma 4: Let $\theta \in \square X$ be a credal set over a compact metric space $X.$ Then for all continuous $f:X\to [0,1]$ there exists $m^{\ast }\in \theta$ such that $m^{\ast }\left(f\right)={max}_{m\in \theta }\left\{m\right(f\left)\right\}$.

Proof. By Lemma 3, the map $m\mapsto m\left(f\right)$ is continuous. By definition, $\theta$ is compact. A continuous function over a compact set achieves a maximum over that set, which proves the result. $\square$

The next lemma corresponds to “phase one” of the proof of Proposition 5 in this proof section of the original infra-Bayesianism sequence.

Lemma 5: Let $\Lambda :\Pi \to \square (A\times O{)}^{\omega }$ be a crisp causal law, and let $g:\Pi \to C\left(\right(A\times O{)}^{\omega },[0,1])$ be continuous. Suppose a sequence of policies $\{{\pi }_n{\}}_{n\in N}$ converges to $\pi$ in the KR-metric on $\Pi .$ Then ${lim}_{n\to \infty }|E_{\Lambda \left({\pi }_n\right)}\left[g\right({\pi }_n\left)\right]-E_{\Lambda \left({\pi }_n\right)}\left[g\right(\pi \left)\right]|=0.$

Proof. Let a convergent sequence ${\pi }_n\to \pi$ and $ϵ>0$ be given. We aim to show that there exists $N$ such that for all $n\ge N,$ $|E_{\Lambda \left({\pi }_n\right)}\left[g\right({\pi }_n\left)\right]-E_{\Lambda \left({\pi }_n\right)}\left[g\right(\pi \left)\right]|<ϵ.$

By Lemma 1 and Lemma 4, for all $n\in N$, there exists $m_n\in \Lambda \left({\pi }_n\right)$ such that $E_{\Lambda \left({\pi }_n\right)}\left[g\right({\pi }_n\left)\right]=m_n\left(g\right({\pi }_n\left)\right)$. Similarly, there exists $m\in \Lambda \left({\pi }_n\right)$ such that $E_{\Lambda \left({\pi }_n\right)}\left[g\right(\pi \left)\right]=m\left(g\right(\pi \left)\right)$. Then

$$\text{(1)}|E_{\Lambda \left({\pi }_n\right)}\left[g\right({\pi }_n\left)\right]-E_{\Lambda \left({\pi }_n\right)}\left[g\right(\pi \left)\right]|=|m_n\left(g\right({\pi }_n\left)\right)-m\left(g\right(\pi \left)\right)|.$$

By definition, for all $n\in N,$ $m_n\left(g\right({\pi }_n\left)\right)\ge m\left(g\right({\pi }_n\left)\right)$and $m\left(g\right(\pi \left)\right)\ge m_n\left(g\right(\pi \left)\right).$ This implies

$$\text{(2)}{m}_n\left(g\right({\pi }_n\left)\right)-m\left(g\right({\pi }_n\left)\right)\ge 0,\text{and}$$$$\text{(3)}m\left(g\right(\pi \left)\right)-m_n\left(g\right(\pi \left)\right)\ge 0.$$

By (2),

$$m\left(g\right(\pi \left)\right)-m_n\left(g\right({\pi }_n\left)\right)$$$$\le m\left(g\right(\pi \left)\right)-m_n\left(g\right({\pi }_n\left)\right)+m_n\left(g\right({\pi }_n\left)\right)-m\left(g\right({\pi }_n\left)\right)$$$$=m\left(g\right(\pi \left)\right)-m\left(g\right({\pi }_n\left)\right).$$

By applying (3) similarly, we obtain

$$m_n\left(g\right({\pi }_n\left)\right)-m\left(g\right(\pi \left)\right)\le m_n\left(g\right({\pi }_n\left)\right)-m_n\left(g\right(\pi \left)\right).$$

These inequalities imply that

$$\text{(4)}|m_n\left(g\right({\pi }_n\left)\right)-m\left(g\right(\pi \left)\right)|\le max\left\{m\right(g\left(\pi \right))-m(g\left({\pi }_n\right)),m_n(g\left({\pi }_n\right))-m_n(g\left(\pi \right)\left)\right\}.$$

We will now consider how to bound each of the expressions in the set on the right hand side.

Since $\Pi$ is compact (by Lemma 2 of An Introduction to Reinforcement Learning for Understanding Infra-Bayesianism) and $g$ is continuous, $g$ is uniformly continuous by the Heine-Cantor theorem. Recall that the metric on $C\left(\right(A\times O{)}^{\omega },[0,1])$ is the Chebyshev metric defined by $d(f_1,f_2)={sup}_{h\in (A\times O{)}^{\omega }}|f_1\left(h\right)-f_2\left(h\right)|.$ By the definition of uniform continuity, there exists $\delta >0$ such that $d_{KR}({\pi }_n,\pi )<\delta$ implies that ${sup}_{h\in (A\times O{)}^{\omega }}|g\left({\pi }_n\right)\left(h\right)-g\left(\pi \right)\left(h\right)|<ϵ.$

Since ${\pi }_n\to \pi$, there exists $N\in N$ such that for all $n\ge N,$ $d_{KR}({\pi }_n,\pi )<\delta .$ Then (with steps explained below),

$$|m_n\left(g\right({\pi }_n\left)\right)-m_n\left(g\right(\pi \left)\right)|\le m_n\left(|g\right({\pi }_n)-g(\pi \left)|\right)={\int }_{(A\times O{)}^{\omega }}|g\left({\pi }_n\right)-g\left(\pi \right)|d{m}_n<{\int }_{(A\times O{)}^{\omega }}\left(ϵ\right)d{m}_n=ϵ.$$

Note that $|m_n\left(g\right({\pi }_n\left)\right)-m_n\left(g\right(\pi \left)\right)|\le m_n\left(|g\right({\pi }_n)-g(\pi \left)|\right)$ due to the linearity of expectation and the triangle inequality for integrals, which states that for any measure $m$ and integrable function $f,$ $|\int fdm|\le \int |f|dm.$ By definition, $m_n\left(|g\right({\pi }_n)-g(\pi \left)|\right)={\int }_{(A\times O{)}^{\omega }}|g\left({\pi }_n\right)-g\left(\pi \right)|d{m}_n.$ By monotonicity of the Lebesgue integral,

$${\int }_{(A\times O{)}^{\omega }}|g\left({\pi }_n\right)-g\left(\pi \right)|d{m}_n\le {\int }_{(A\times O{)}^{\omega }}\underset{h\in (A\times O{)}^{\omega }}{sup}|g\left({\pi }_n\right)\left(h\right)-g\left(\pi \right)\left(h\right)|d{m}_n.$$

By the fact that $m_n$ is a probability measure and thus $m_n\left(\right(A\times O{)}^{\omega })=1,$

$${\int }_{(A\times O{)}^{\omega }}\underset{h\in (A\times O{)}^{\omega }}{sup}|g\left({\pi }_n\right)\left(h\right)-g\left(\pi \right)\left(h\right)|<ϵ$$

for all $n\ge N.$

By a similar argument, for all $n\ge N,$

$$|m\left(g\right({\pi }_n\left)\right)-m\left(g\right(\pi \left)\right)|<ϵ.$$

Returning to equations (1) and (4), we obtain that for all $n\ge N$,

$$|E_{\Lambda \left({\pi }_n\right)}\left[g\right({\pi }_n\left)\right]-E_{\Lambda \left({\pi }_n\right)}\left[g\right(\pi \left)\right]|<ϵ,$$

which completes the proof. $\square$

The next proposition is a special case of “phase two” and “phase 3″ of the proof of Proposition 5 in this proof section of the original infra-Bayesianism sequence. The ideas here are the same, although we provide a direct proof.

Proposition 2: Let $\Lambda :\Pi \to \square (A\times O{)}^{\omega }$ be a crisp causal law, and let $g:\Pi \to C\left(\right(A\times O{)}^{\omega },[0,1])$ be continuous. Then the function $\pi \mapsto E_{\Lambda \left(\pi \right)}\left[g\right(\pi \left)\right]$ is continuous.

Proof: By Lemma 2, $\Pi$ is first-countable, and thus it is sufficient to show that for any convergent sequence ${\pi }_n\to \pi ,$ ${lim}_{n\to \infty }{E}_{\Lambda \left({\pi }_n\right)}\left[g\right({\pi }_n\left)\right]=E_{\Lambda \left(\pi \right)}\left[g\right(\pi \left)\right].$ By Lemma 5, it is furthermore sufficient to prove that ${lim}_{n\to \infty }{E}_{\Lambda \left({\pi }_n\right)}\left[g\right(\pi \left)\right]=E_{\Lambda \left(\pi \right)}\left[g\right(\pi \left)\right].$

To that end, let ${\pi }_n\to \pi .$ We will show that ${liminf}_{n\to \infty }{E}_{\Lambda \left({\pi }_n\right)}\left[g\right(\pi \left)\right]\ge E_{\Lambda \left(\pi \right)}\left[g\right(\pi \left)\right]$ and ${limsup}_{n\to \infty }{E}_{\Lambda \left({\pi }_n\right)}\left[g\right(\pi \left)\right]\le E_{\Lambda \left(\pi \right)}\left[g\right(\pi \left)\right].$

By Lemma 1 and Lemma 4, there exists $m\in \Lambda \left(\pi \right)$ such that $E_{\Lambda \left(\pi \right)}\left[g\right(\pi \left)\right]=m\left(g\right(\pi \left)\right).$ By the continuity of $\Lambda$, there exists a convergent sequence $\{m_n{\}}_{n\in N}$ such that $m_n\to m$ and $m_n\in \Lambda \left({\pi }_n\right)$ for all $n\in N.$ By assumption, $g$ is continuous, and thus Lemma 3 implies that $m_n\left(g\right(\pi \left)\right)\to m\left(g\right(\pi \left)\right).$ By construction, $E_{\Lambda \left({\pi }_n\right)}\left[g\right(\pi \left)\right]\ge m_n\left(g\right(\pi \left)\right).$ Then

$$\underset{n\to \infty }{liminf}{E}_{\Lambda \left({\pi }_n\right)}\left[g\right(\pi \left)\right]\ge \underset{n\to \infty }{liminf}{m}_n\left(g\right(\pi \left)\right)=m\left(g\right(\pi \left)\right)=E_{\Lambda \left(\pi \right)}\left[g\right(\pi \left)\right].$$

For the second argument, choose a subsequence $\{n_k{\}}_{k\in N}$ such that

$$\left(1\right)\underset{k\to \infty }{lim}{E}_{\Lambda \left({\pi }_{n_k}\right)}\left[g\right(\pi \left)\right]=\underset{n\to \infty }{limsup}{E}_{\Lambda \left({\pi }_n\right)}\left[g\right(\pi \left)\right].$$

Invoking Lemma 1 and Lemma 4 again, for each $n_k$, choose $m_{n_k}\in \Lambda \left({\pi }_{n_k}\right)$ such that $E_{\Lambda \left({\pi }_{n_k}\right)}\left[g\right(\pi \left)\right]=m_{n_k}\left(g\right(\pi \left)\right).$ Since $\Lambda$ is continuous and $\Lambda \left(\pi \right)$ is closed, there exists a convergent subsequence $\{m_{n_{k_j}}{\}}_{j\in N}$ with a limit point $m\in \Lambda \left(\pi \right).$

Then by (1), Lemma 3, and the definition of expectation with respect to a credal set,

$$\underset{n\to \infty }{limsup}{E}_{\Lambda \left({\pi }_n\right)}\left[g\right(\pi \left)\right]=\underset{j\to \infty }{lim}{m}_{n_{k_j}}\left[g\right(\pi \left)\right]=m\left(g\right(\pi \left)\right)\le E_{\Lambda \left(\pi \right)}\left[g\right(\pi \left)\right].$$

Thus ${lim}_{n\to \infty }{E}_{\Lambda \left({\pi }_n\right)}\left[g\right(\pi \left)\right]=E_{\Lambda \left(\pi \right)}\left[g\right(\pi \left)\right],$ which completes the proof. $\square$

Corollary 1 then follows from Proposition 2 using a standard continuity argument.

Corollary 1: For all crisp causal laws $\Lambda$ and for all continuous functions $g:\Pi \to C\left(\right(A\times O{)}^{\omega },[0,1])$, ${\text{argmin}}_{\pi \in \Pi }{E}_{\Lambda \sim \zeta }\left[E_{\Lambda \left(\pi \right)}\right[g\left(\pi \right)\left]\right]$ is a closed, non-empty set.

Proof of Proposition 3

The following proposition corresponds to Proposition 12 in this proof section of the infra-Bayesian sequence. Equation (2) below appears there, and we explain it in more detail here. The remainder of the proof differs from the original version.

Proposition 3: For any non-dogmatic prior $\zeta$ over a learnable collection of crisp causal laws $\{{\Lambda }_i{\}}_{i=0}^{\infty }$, if a family ${\pi }^{\ast \gamma }$ of policies is infra-Bayes optimal with respect to $\zeta$, then ${\pi }^{\ast \gamma }$ learns $\{{\Lambda }_i{\}}_{i=0}^{\infty }.$

Proof: Assume that $\{{\Lambda }_i{\}}_{i=0}^{\infty }$ is learnable. We will proceed by contrapositive and show that if a family of policies ${\pi }^{\ast \gamma }$ does not learn $\{{\Lambda }_i{\}}_{i=0}^{\infty },$ then for any non-dogmatic prior $\zeta$ over $\{{\Lambda }_i{\}}_{i=0}^{\infty },$ ${\pi }^{\ast \gamma }$ is not infra-Bayes optimal. By definition, there exists a family of policies ${\pi }^{\gamma }$ such that for all $i\ge 0,$

$$\left(1\right)\underset{\gamma \to 1}{lim}\text{Reg}({\pi }^{\gamma },{\Lambda }_i,L^{\gamma })=0$$

Equivalently, by the definition of infra-regret, for all $i\ge 0,$

$$\left(1\right)\underset{\gamma \to 1}{lim}\left(E_{{\Lambda }_i\left({\pi }^{\gamma }\right)}\right[L^{\gamma }]-\underset{\pi \in \Pi }{min}{E}_{{\Lambda }_i\left(\pi \right)}[L^{\gamma }\left]\right)=0.$$

We preliminarily aim to show that

$$\left(2\right)\underset{\gamma \to 1}{lim}\text{IBReg}({\pi }^{\gamma },\zeta ,L^{\gamma })=\underset{\gamma \to 1}{lim}{E}_{{\Lambda }_i\sim \zeta }\text{Reg}({\pi }^{\gamma },{\Lambda }_i,L^{\gamma })=0.$$

Let $ϵ>0$ be given. Note that for all $N\in N,$

$$E_{{\Lambda }_i\sim \zeta }\text{Reg}({\pi }^{\gamma },{\Lambda }_i,L^{\gamma })$$$$=\sum _{i=0}^N\zeta \left({\Lambda }_i\right)\text{Reg}({\pi }^{\gamma },{\Lambda }_i,L^{\gamma })+\sum _{i=N+1}^{\infty }\zeta \left({\Lambda }_i\right)\text{Reg}({\pi }^{\gamma },{\Lambda }_i,L^{\gamma })$$

Since $\{{\Lambda }_i{\}}_{i=1}^{\infty }$ is countable and ${\sum }_{i\ge 0}\zeta \left({\Lambda }_i\right)=1<\infty$, there exists $N<\infty$ such that ${\sum }_{i\ge N+1}\zeta \left({\Lambda }_i\right)<ϵ/2.$ Since $\text{Reg}({\pi }^{\gamma },{\Lambda }_i,L^{\gamma })\le 1$ for all $i\in N,$ the second sum above is bounded by $ϵ/2$. We will now bound the first sum.

Let $\widehat{ϵ}:=\frac{ϵ}{2N}.$ Applying equation (1) for each $0\le i\le N,$ we can obtain ${\gamma }_i\in (0,1)$ such that for all $\gamma \in [{\gamma }_i,1),$ $\text{Reg}({\pi }^{\gamma },{\Lambda }_i,L^{\gamma })<\widehat{ϵ}.$ Let ${\gamma }^{\ast }={max}_{0\le i\le N}{\gamma }_i$. Then $\text{Reg}({\pi }^{\gamma },{\Lambda }_i,L^{\gamma })<\widehat{ϵ}$ holds simultaneously for all $0\le i\le N$ and $\gamma \ge {\gamma }^{\ast }.$ Thus for $\gamma \ge {\gamma }^{\ast },$ $E_{{\Lambda }_i\sim \zeta }\text{Reg}({\pi }^{\gamma },{\Lambda }_i,L^{\gamma })<ϵ,$ proving Equation (2).

Since ${\pi }^{\ast \gamma }$ does not learn $\{{\Lambda }_i{\}}_{i=1}^{\infty },$ there exists $j\in N$ such that ${lim}_{\gamma \to 1}\text{Reg}({\pi }^{\ast \gamma },{\Lambda }_j,L^{\gamma })\ne 0.$ We will show that this implies ${lim}_{\gamma \to 1}\text{IBReg}({\pi }^{\ast \gamma },\zeta ,L^{\gamma })>0,$ which when combined with (2) indicates that ${\pi }^{\ast \gamma }$ is not infra-Bayes optimal with respect to $\zeta$.

With steps explained in the proceeding paragraphs, we have that

$$\underset{\gamma \to 1}{lim}\text{IBReg}({\pi }^{\ast \gamma },\zeta ,L^{\gamma })$$$$=\underset{\gamma \to 1}{lim}{E}_{{\Lambda }_i\sim \zeta }\text{Reg}({\pi }^{\ast \gamma },{\Lambda }_i,L^{\gamma })$$$$=\underset{\gamma \to 1}{lim}\sum _{i=0}^{\infty }\zeta \left({\Lambda }_i\right)\text{Reg}({\pi }^{\ast \gamma },{\Lambda }_i,L^{\gamma })$$$$=\sum _{i=0}^{\infty }\zeta \left({\Lambda }_i\right)\underset{\gamma \to 1}{lim}\text{Reg}({\pi }^{\ast \gamma },{\Lambda }_i,L^{\gamma })$$$$\ge \zeta \left({\Lambda }_j\right)\underset{\gamma \to 1}{lim}\text{Reg}({\pi }^{\ast \gamma },{\Lambda }_j,L^{\gamma })$$$$>0.$$

The first equality follows from the definition of infra-regret, and the second equality follows from the definition of expectation with respect to a measure on a countable set. The third equality is an application of the Lebesgue Dominating Convergence Theorem using the constant one function as a dominating function. The inequalities follow from the fact that all terms in the sum are positive, ${lim}_{\gamma \to 1}\text{Reg}({\pi }^{\ast \gamma },{\Lambda }_j,L^{\gamma })>0,$ and $\zeta \left({\Lambda }_j\right)\ne 0,$ which is true by the assumption that $\zeta$ is non-dogmatic.

We will now show that ${\pi }^{\ast \gamma }$ is not infra-Bayes optimal with respect to $\zeta$. There exists ${\gamma }_0\in [0,1)$ such that

$$\text{IBReg}({\pi }^{\ast {\gamma }_0},\zeta ,L^{{\gamma }_0})>\text{IBReg}({\pi }^{{\gamma }_0},\zeta ,L^{{\gamma }_0}).$$

Therefore,

$$E_{\Lambda \sim \zeta }\text{Reg}({\pi }^{\ast {\gamma }_0},\Lambda ,L^{{\gamma }_0})-E_{\Lambda \sim \zeta }\text{Reg}({\pi }^{{\gamma }_0},\Lambda ,L^{{\gamma }_0})>0.$$

By linearity,

$$E_{\Lambda \sim \zeta }\left[\text{Reg}\right({\pi }^{\ast {\gamma }_0},\Lambda ,L^{{\gamma }_0})-\text{Reg}({\pi }^{{\gamma }_0},\Lambda ,L^{{\gamma }_0}\left)\right]>0.$$

By definition,

$$E_{\Lambda \sim \zeta }\left[E_{\Lambda \left({\pi }^{\ast {\gamma }_0}\right)}\right[L^{{\gamma }_0}]-\underset{\pi \in \Pi }{min}{E}_{\Lambda \left(\pi \right)}[L^{{\gamma }_0}]-(E_{\Lambda \left({\pi }^{{\gamma }_0}\right)}\left[L^{{\gamma }_0}\right]-\underset{\pi \in \Pi }{min}{E}_{\Lambda \left(\pi \right)}\left[L^{{\gamma }_0}\right]\left)\right]>0.$$

Simplifying and applying linearity of expectation, we obtain

$$E_{\Lambda \sim \zeta }\left[E_{\Lambda \left({\pi }^{\ast {\gamma }_0}\right)}\right[L^{{\gamma }_0}]-E_{\Lambda \left({\pi }^{{\gamma }_0}\right)}[L^{{\gamma }_0}\left]\right]$$$$=E_{\Lambda \sim \zeta }{E}_{\Lambda \left({\pi }^{\ast {\gamma }_0}\right)}\left[L^{{\gamma }_0}\right]-E_{\Lambda \sim \zeta }{E}_{\Lambda \left({\pi }^{{\gamma }_0}\right)}\left[L^{{\gamma }_0}\right]>0.$$

Therefore, ${\pi }^{\ast \gamma }$ is not an infra-Bayes optimal family of policies. $\square$

Acknowledgements

Many thanks Vanessa Kosoy and Marcus Ogren for their constructive feedback on the initial draft.

References

[1] Villani, Cédric, Optimal Transport: Old and New. Springer Berlin, Heidelberg, 2009.
[2] Carothers, N. L., “The Stone-Weierstrass Theorem.” In Real Analysis. Cambridge University Press, 2012.