Introduction

This post accompanies An Introduction to Reinforcement Learning for Understanding Infra-Bayesianism. The goal of this introduction is to provide a high-level overview of the proofs contained in this post.

The proof of Proposition 1 is achieved through three lemmas. I believe the most insightful part of the proof is the use of the “epsilon over three” trick that lets us break the proof down into these lemmas. The first lemma uses the concept of the product topology on the space of policies, and I found this very useful for understanding better what convergence in the product topology on the space of policies actually means. The text Topology by James Munkres is a standard reference for topology.

The second lemma uses the concept of a Lebesgue integral and is simply an application of the dominated convergence theorem from measure theory. One standard reference for these ideas is Real Analysis: Modern Techniques and Their Applications by Gerald Folland.

The proof of Proposition 2 is less technical than the other proofs and should be readable to those with a basic real analysis and probability background. For basic real analysis, Principles of Mathematical Analysis by Walter Rudin is a standard reference.

Proposition 1

For brevity throughout this section, we use ${\mu }^{\pi }\left(L^{\gamma }\right)$ to denote $E_{h\sim {\mu }^{\pi }}\left[L^{\gamma }\right(h\left)\right].$

Proposition 1 Lemma 1: Suppose that ${\pi }_n\to \pi$ in the product topology on $\Pi .$ Then for any finite time-horizon $N\in N,$ ${\mu }^{{\pi }_n}\left(L^{\gamma }{|}_N\right)\to {\mu }^{\pi }\left(L^{\gamma }{|}_N\right).$

Proof: Suppose that ${\pi }_n\to \pi$ in the product topology on $\Pi$. Let $ϵ>0$ be given and fix $N\in N$. To satisfy the definition of the limit, we must show that there exists $M\in N$ such that for all $n\ge M,$ $|{\mu }^{{\pi }_n}\left(L^{\gamma }{|}_N\right)-{\mu }^{\pi }\left(L^{\gamma }{|}_N\right)|<ϵ.$

Let $N(A,O)$ denote the number of histories of length $N.$ Since $A$ and $O$ are finite sets and $N<\infty ,$ $N(A,O)<\infty .$ Let the set of histories of length $N$ then be indexed by $\{1,2,\dots ,N(A,O\left)\right\}.$ 

Then we have:

At this point, we want to bound the magnitude of terms of the form ${\mu }^{{\pi }_n}\left(h_i\right)-{\mu }^{\pi }\left(h_i\right)$ for $1\le i\le N(A,O).$ The key idea is to show that these terms can be factored into the product of two terms: one term that is finite and one term that becomes arbitrarily small for sufficiently large $n$.

Let $(h_i{)}_{\le t}$ denote the sequence of the first $t$ elements of $h_i.$ By the product rule,

Since ${\mu }^{{\pi }_n}$ and ${\mu }^{\pi }$ are induced by the same environment, we can observe a common factor of ${\mu }^{{\pi }_n}\left(h_i\right)$ and ${\mu }^{\pi }\left(h_i\right)$. Namely, we have:

Let $c={max}_{1\le i\le N(A,O)}\left\{{\prod }_{t=0}^N\mu \right(o_t|\left(h_i{)}_{\le t}\right)\},$ which is finite.  Consider now the second term of the product, which we will show becomes arbitrarily small for sufficiently large $n$since ${\pi }_n\to \pi$ in the product topology.

First, we establish some notation: Let $J=|\{h:h\in (A\times O{)}^{\ast },|h|\le N\}|,$ the cardinality of the set of histories of length at most $N,$ which is a finite set since $N<\infty ,$ and $A$ and $O$ are finite sets. We can enumerate elements of this set of histories by $h_j$ with the index $1\le j\le J.$

Given $\widehat{ϵ}>0$, let $B_{\widehat{ϵ}}\left(\pi \right(h_j\left)\right)$ denote the ball of radius $\widehat{ϵ}$ centered at $\pi \left(h_j\right)\in \Delta A$ under the total variation distance, which we denote by $d_{TV}$. Importantly, $B_{\widehat{ϵ}}\left(\pi \right(h_j\left)\right)$ is an open set of probability distributions over actions. Let $U:={\prod }_{j=1}^J{B}_{\widehat{ϵ}}\left(\pi \right(h_j\left)\right)\times {\prod }_{j=J+1}^{\infty }\Delta A$, which is open in the product topology since it is the product of open sets in $\Delta A$ not equal to $\Delta A$ in finitely many components.

Since ${\pi }_n\to \pi$ in the product topology, by definition: for all $\widehat{ϵ}>0,$ there exists $M$ such that for all $n\ge M,$ ${\pi }_n\in U.$ By construction, if ${\pi }_n\in U,$ for $1\le j\le J,$ $d_{\text{TV}}\left(\pi \right(h_j),{\pi }_n(h_j\left)\right)<\widehat{ϵ}.$ By definition, then for $1\le j\le J,$ ${sup}_{a\in A}|\pi \left(a|h_j\right)-{\pi }_n\left(a|h_j\right)|<\widehat{ϵ}.$

Consider the term we’re trying to bound,

We want to rewrite the terms ${\pi }_n\left(a_t|\right(h_i{)}_{\le t-1})$ using the approximation provided above. We have that

Then by the triangle inequality,

Thus ${\pi }_n\left(a|\right(h_i{)}_{\le t-1})\le \widehat{ϵ}+\pi (a|\left(h_i{)}_{\le t-1}\right),$ so we now have:

Notice that when expanded, the only term of ${\prod }_{t=0}^N\widehat{ϵ}+\pi \left(a|\right(h_i{)}_{\le t-1})$ that isn’t the product of $\widehat{ϵ}$ and some finite term is ${\prod }_{t=0}^N\pi \left(a|\right(h_i{)}_{\le t-1})$, which cancels out with an identical term in the original expression. Since $\widehat{ϵ}$ can be chosen arbitrarily small by choosing the index $n$ of ${\pi }_n$ to be large, this means: given any $\widetilde{ϵ}>0,$ there exists $M_i$ such that for all $n\ge M_i,$ 

Then if $n\ge max\{M_i:1\le i\le N(A,O\left)\right\},$ for all $1\le i\le N(A,O),$$|{\mu }^{{\pi }_n}\left(h_i\right)-{\mu }^{\pi }\left(h_i\right)|\le c\cdot \widetilde{ϵ}.$ Then

Choose, $\widetilde{ϵ}<\frac{ϵ}{N(A,O)\cdot c}.$ Then for $n\ge max\{M_i:1\le i\le N(A,O\left)\right\},$ $|{\mu }^{{\pi }_n}\left(L^{\gamma }{|}_N\right)-{\mu }^{\pi }\left(L^{\gamma }{|}_N\right)|<ϵ.\square$

Proposition 1 Lemma 2: Define $L^{\gamma }{|}_N$ for $N\in N$ as $L^{\gamma }{|}_N(a_t,o_t{)}_{t=0}^N={\sum }_{t=0}^N{\gamma }^{t}L(o_t).$ Let $m\in M(A\times O{)}^{\infty }$ be a probability measure on destinies. Then $m\left(L^{\gamma }{|}_N\right)\to m\left(L^{\gamma }\right)$ as $N\to \infty .$

Proof: This lemma follows directly from the dominated convergence theorem, so our proof will be a check that all the conditions of that theorem are satisfied. First note that $L^{\gamma }{|}_N$ converges to $L^{\gamma }$ pointwise. Also ${\int }_{(A\times O{)}^{\infty }}|L^{\gamma }\left(h\right)|dm<\infty$ since $m$ is a probability measure (and thus $m(A\times O{)}^{\infty }=1$) and $L^{\gamma }\left(h\right)\le 1$ for all $h\in (A\times O{)}^{\infty }.$ Also, for all $N\in N$ and $h\in (A\times O{)}^{\infty },$ $L^{\gamma }{|}_N\left(h\right)\le |L^{\gamma }\left(h\right)|.$ Then, by the dominated convergence theorem, ${lim}_{N\to \infty }\int L^{\gamma }{|}_{N}dm=\int L^{\gamma }dm.$ $\square$

Proposition 1 Lemma 3: Suppose that $\{{\pi }_n{\}}_{n\in N}$ is a convergent sequence in $\Pi .$ Then for any $ϵ>0,$ there exists $M\in N$ and a finite time-horizon $N_0\in N$ such that for all $m\ge M$and $N\ge N_0,$ $|{\mu }^{{\pi }_m}\left(L^{\gamma }{|}_N\right)-{\mu }^{{\pi }_m}\left(L^{\gamma }\right)|<ϵ.$

Proof: Let $ϵ>0$ be given. Note that $\Pi$ is a metric space since it is the countable product of metric spaces (namely, $\Delta A)$. This implies that if $\{{\pi }_n{\}}_{n\in N}$ is a convergent sequence, $\{{\pi }_n{\}}_{n\in N}$ is Cauchy. 

For any $n,m\in N,$ we have by the triangle inequality that

Since $\{{\pi }_n{\}}_{n\in N}$ is Cauchy, the same technique used in Proposition 1 Lemma 1 can be used to show that there exists $M$ such that for all $n,m\ge M,$ there exists $N_1$ such that for all $N\ge N_1,$ $|{\mu }^{{\pi }_n}\left(L^{\gamma }{|}_N\right)-{\mu }^{{\pi }_m}\left(L^{\gamma }{|}_N\right)|<\frac{ϵ}{9}.$

Let $n,m\ge M$ be fixed. By Proposition 1 Lemma 2, there exists $N_2\in N$ such that for all $N\ge N_2,$ $|{\mu }^{{\pi }_n}\left(L^{\gamma }\right)-{\mu }^{{\pi }_n}\left(L^{\gamma }{|}_N\right)|<\frac{ϵ}{3}.$ 

Note that

By Proposition 1 Lemma 2 there exists $N_3$ such that for all $N\ge N_3$, $|{\mu }^{{\pi }_m}\left(L^{\gamma }\right)-{\mu }^{{\pi }_m}\left(L^{\gamma }{|}_N\right)|<\frac{ϵ}{9}.$ By the same lemma, there exists $N_4$ such that for all $N\ge N_4$, $|{\mu }^{{\pi }_n}\left(L^{\gamma }{|}_N\right)-{\mu }^{{\pi }_n}\left(L^{\gamma }\right)|<\frac{ϵ}{9}.$ As previously stated, if $N\ge N_1,$ then$|{\mu }^{{\pi }_m}\left(L^{\gamma }{|}_N\right)-{\mu }^{{\pi }_n}\left(L^{\gamma }{|}_N\right)|<\frac{ϵ}{9}.$ Therefore, if $N\ge max\{N_1,N_3,N_4\},$ then $|{\mu }^{{\pi }_m}\left(L^{\gamma }\right)-{\mu }^{{\pi }_n}\left(L^{\gamma }\right)|<\frac{ϵ}{3}.$

Let $N_0:=max\{N_1,N_2,N_3,N_4\}.$ Then if $N\ge N_0,$

Proposition 1: If $A$ and $O$ are finite, the optimal policy for a given environment $\mu$ exists; namely, ${\text{arg min}}_{\pi \in \Pi }{E}_{h\sim {\mu }^{\pi }}\left[L^{\gamma }\right(h\left)\right]\ne \varnothing .$  Furthermore, the optimal policy can be chosen to be deterministic.

Proof: The usual technique to show that a function attains a minimum is to show that it is continuous and that the domain is compact. Then the existence of a minimum follows by the generalization of the Extreme Value Theorem to topological spaces. Recall that Lemma 2 (from the main text) states that $\Pi$ is compact.

So, it suffices to show that the map $\pi \mapsto E_{h\sim {\mu }^{\pi }}\left[L^{\gamma }\right(h\left)\right]$ from $\Pi$ to $R$ is continuous. Assume that $\{{\pi }_n{\}}_{n\in N}$ is a sequence of policies converging to $\pi$ with respect to the product topology on $\Pi .$ Then we want to show that ${\mu }^{{\pi }_n}\left(L^{\gamma }\right)\to {\mu }^{\pi }\left(L^{\gamma }\right)$. Define $L^{\gamma }{|}_N$ for $N\in N$ as $L^{\gamma }{|}_N(a_t,o_t{)}_{t=0}^N:={\sum }_{t=0}^N{\gamma }^{t}L(o_t),$ which we can conceptualize as the truncation of $L^{\gamma }$ to a finite time-horizon.

By Proposition 1 Lemma 2, there exists $N_1$ such that for all $N\ge N_1,$ $|{\mu }^{\pi }\left(L^{\gamma }{|}_N\right)-{\mu }^{\pi }\left(L^{\gamma }\right)|<ϵ/3.$ By Proposition 1 Lemma 3, there exists $M_1$ and $N_2$ such that for all $n\ge M_1$ and $N\ge N_2,$ $|{\mu }^{{\pi }_n}\left(L^{\gamma }\right)-{\mu }^{{\pi }_n}\left(L^{\gamma }{|}_N\right)|<\frac{ϵ}{3}.$

Let $N_0=max\{N_1,N_2\}.$ By Proposition 1 Lemma 1, there exists $M_2$ such that for all $n\ge M_2,$ $|{\mu }^{\pi }\left(L^{\gamma }{|}_{N_0}\right)-{\mu }^{{\pi }_n}\left(L^{\gamma }{|}_{N_0}\right)|<\frac{ϵ}{3}.$ 

Let $ϵ>0$ be given. If $n\ge max\{M_1,M_2\}$, then by the triangle inequality,

Therefore, ${\mu }^{{\pi }_n}\left(L^{\gamma }\right)\to {\mu }^{\pi }\left(L^{\gamma }\right).$

Now we prove that the optimal policy can be chosen to be deterministic. The environment $\mu$ remains fixed. Let ${\Pi }_{det}\subset \Pi$ denote the set of deterministic policies, which is compact. By the same argument given more generally for $\Pi ,$ $d:={\text{min}}_{\pi \in {\Pi }_{\text{det}}}{E}_{{\mu }^{\pi }}\left[L^{\gamma }\right]$ is well-defined.

Any stochastic policy ${\pi }_s$ is equivalent to a probabilistic mixture of deterministic policies. Therefore, any stochastic policy ${\pi }_s$ induces a probability measure ${\nu }_s$ on the countable set ${\mu }^{{\Pi }_{\text{det}}}:=\{{\mu }^{\pi }:\pi \in {\Pi }_{\text{det}}\}.$ As a result, ${\mu }^{{\pi }_s}$ can be written as a countable mixture of measures given by ${\mu }^{{\pi }_s}={\sum }_{{\mu }^{{\pi }_i}\in {\mu }^{{\Pi }_{\text{det}}}}{\nu }_s\left({\mu }^{{\pi }_i}\right){\mu }^{{\pi }_i}$.

This implies $E_{{\mu }^{{\pi }_s}}\left[L^{\gamma }\right]=E_{{\nu }_s}\left[E_{{\mu }^{\pi }}\right[L^{\gamma }\left]\right]$. (See problem 9.7 in reference [1] for an outline of how this can be justified^[1], as also cited in reference [2].) By the definition of $d$, $E_{{\nu }_s}\left[E_{{\mu }^{\pi }}\right[L^{\gamma }\left]\right]\ge E_{{\nu }_s}\left[d\right]=d$. Thus, the expected loss of a stochastic policy always exceeds the minimum loss of the deterministic policies. $\square$

Proposition 2

Proposition 2: If a countable class of environments $\{{\mu }_i{\}}_{i\in I}$ is learnable, then the Bayes-optimal family of policies for any non-dogmatic prior $\zeta$ on $\{{\mu }_i{\}}_{i\in I}$ learns the class.

Proof: Suppose a class of hypotheses $\{{\mu }_i{\}}_{i\in I}$ is learnable, and let $\zeta$ be a non-dogmatic prior on $\{{\mu }_i{\}}_{i\in I}.$ We will proceed by contrapositive and show that if the family of policies $\{{\pi }_{\zeta }^{\gamma }{\}}_{\gamma \in [0,1)}$ does not learn the class, then it is not the Bayes-optimal family for $\zeta .$

Assume that there exists $j$ such that ${lim}_{\gamma \to 1}\text{Reg}({\pi }_{\zeta }^{\gamma },{\mu }_j,\gamma )\ne 0.$ By negating the definition of a limit, this means that there exists $ϵ>0$ such that for all $\delta >0,$ there exists $\gamma$ such that $|\gamma -1|<\delta$ and $|\text{Reg}({\pi }_{\zeta }^{\gamma },{\mu }_j,\gamma )|\ge ϵ.$ By definition, $|\text{Reg}({\pi }_{\zeta }^{\gamma },{\mu }_j,\gamma )|\ge ϵ$ if and only if

We will show that this contradicts the assumption that $\{{\pi }_{\zeta }^{\gamma }{\}}_{\gamma \in [0,1)}$ is a Bayes-optimal family for $\zeta .$

With steps explained in the proceeding paragraphs, we have:

In the above, the first and second equalities follow from definition. To get the third equality, we switch sum and the limit, which is justified by the dominated convergence theorem. In the language of countably infinite sums, this theorem says: Let $f_{\gamma }\left(i\right):I\to R$ be a sequence of functions indexed by $\gamma \in [0,1)$ such that the pointwise limit of $f_{\gamma }$, ${lim}_{\gamma \to 1}{f}_{\gamma }\left(i\right),$ exists for all $i\in I$. Suppose there exists $g\left(i\right):I\to R$such that ${\sum }_{i\in I}g\left(i\right)<\infty ,$ and for all $\gamma$ and $i,$ $|f_{\gamma }\left(i\right)|\le g\left(i\right)$. Then 

So, this theorem essentially states that if we can find a sequence of terms $g\left(i\right)$ that “dominates” all of the the $f_{\gamma }\left(i\right)$ pointwise in $i,$ and the sum of the $g\left(i\right)$ doesn’t blow up, then the limit and sum can be interchanged.

To apply the dominated convergence theorem, let 

 Note that

So $g\left(i\right):=\zeta \left({\mu }_i\right)$ is an appropriate dominating function. By the definition of a prior, ${\sum }_{i\in I}\zeta \left({\mu }_i\right)=1<\infty .$ Therefore, the assumptions of the dominated convergence theorem are satisfied.

The second to last inequality follows from the fact that for all $i\in I,$

On the other hand, by assumption, $\{{\mu }_i{\}}_{i\in I}$ is learnable, so there exists some family of policies $\{{\pi }^{\gamma }{\}}_{\gamma \in [0,1)}$ such that for all $i,$ ${lim}_{\gamma \to 1}\text{Reg}({\pi }^{\gamma },{\mu }_i,\gamma )=0.$ Consider a parallel argument to what we have above, replacing ${\pi }_{\zeta }^{\gamma }$ with ${\pi }^{\gamma }$: