Reinforcement learning with imperceptible rewards

[Vanessa Kosoy]

TLDR: We define a variant of reinforcement learning in which the reward is not perceived directly, but can be estimated at any given moment by some (possibly costly) experiment. The reward function is no longer a function of the observation history, but a different object that we call “instrumental reward function”. We give two definitions of instrumental reward function and prove their equivalence. We also derive a regret bound for this setting.

Background

In “classical” reinforcement learning the agent perceives the reward signal on every round of its interaction with the environment, whether through a distinct input channel or through some given way to compute the reward from the interaction history so far. On the other hand, we can rather easily imagine agents that optimize properties of their environment that they do not directly perceive. For example, if Alice, who lives in Dominica, donates money to the Against Malaria Foundation in order to save someone in Africa, then the result is usually not visible to Alice at the time it occurs, if ever. Similarly, Clippy the paperclip maximizer doesn’t always perceive all the paperclips in the universe. Moreover, we might want to design agents that, in order to estimate the reward, direct queries to humans (which is costly and cannot be done continuously non-stop).

Now, it is possible to define the perceived reward as the subjective expected value of the “true” imperceptible reward (see the Results section for details). Although this transformation preserves expected utility, it does not preserve Bayesian regret. Indeed, Bayesian regret is the difference between the expected utility attained by the agent and the expected utility attained by a “reference” agent that knows the true environment from the onset. However, after the transformation, the reference agent will behave as if it knows the observable dynamics of the true environment but still pretends not to know the true environment for the purpose of computing the reward. Therefore, regret analysis requires us to consider the imperceptible reward honestly. In fact, as we will see, certain assumptions about the imperceptible reward function are needed even to make the problem learnable at all. Finally, this transformation makes the reward function more complex and hence applying a “generic” reinforcement learning algorithm after the transformation (instead of exploiting the special form of the resulting reward function) might carry a significant computational complexity penalty.

Related Work: De Blanc 2011 studies so called “ontological crises”. That is, de Blanc examines the problem of translating a reward function from one ontology into another. Here, we avoid this problem by considering reward functions that are automatically defined in all ontologies. That said, it might still be interesting to think about how to specify our type of reward function starting from a reward function that is only defined in one particular ontology. We will return to this in the Discussion section.

Krueger et al 2016 consider a setting where querying the reward is instantaneous and has a fixed cost. This is a special case of our setting, but we allow a much more general type of query and cost. Also, Krueger et al don’t derive any theoretical regret bound (but they do present some experimental results).

Finally, multi-armed bandits with partial monitoring are closely related, see for example Bartok et al 2013. However, bandits by definition assume a stateless environment, and also our approach is rather different than what is usually studied in partial monitoring.

The literature study was very cursory and I will be glad to know about prior work I missed!

Results

Partially Observable MDPs with Imperceptible Rewards

Partially Observable Markov Decision Processes (POMDPs) serve as a natural starting point for thinking about imperceptible rewards. Indeed, it might seem like all we have to do is consider RL in a POMDP environment and let the reward to be a function of the (imperceptible) state. However, this setting is in general unlearnable even given assumptions that rule out traps.

A (finite) POMDP is defined by non-empty finite sets $S$ (states), $A$ (actions) and $O$ (observations), the transition kernel $T:S\times A\stackrel{k}{\to }S\times O$ and the reward function $R:S\to [0,1]$. As opposed to the “classical” definition of POMDP, we allow the value of $R$ is to be imperceptible. The perceptible setting is a special case of the imperceptible setting: we can always encode the reward into the observation.

To formulate a learning problem, we assume $S$, $A$ and $O$ to be fixed and an initial state $s_0\in S$ to be given, while $T$ and $R$ are unknown and belong to some hypothesis class $H$:

$$H\subseteq \{S\times A\stackrel{k}{\to }S\times O\}\times \{S\to [0,1]\}$$

Such a problem can be unlearnable even if $R$ is known and there are no irreversible events that can happen:

Example 1

Suppose that $S=\{s_0,s_{-},s_{+}\}$, $A=\{a_{-},a_{+}\}$, $O=\left\{\perp \right\}$, $R\left(s_0\right)=\frac{1}{2}$, $R\left(s_{-}\right)=0,R\left(s_{+}\right)=1$ and $H=\{(T_{-},R),(T_{+},R)\}$ where for any $s\in S$

$$T_{-}(s_{+},\perp |s,a_{-})=1$$ $$T_{-}(s_{-},\perp |s,a_{+})=1$$ $$T_{+}(s_{+},\perp |s,a_{+})=1$$ $$T_{+}(s_{-},\perp |s,a_{-})=1$$

Since $\left|O\right|=1$, there is no way to gain any information about which hypothesis is correct. Moreover, the optimal policies for the two hypotheses are different. Namely, for $T_{+}$ we should always take action $a_{+}$ and for $T_{-}$ we should always take action $a_{-}$.

To formalize and illustrate the discussion in the Background section, suppose $H$ is Borel and $\zeta \in \Delta H$ is the prior. We can then define the “perceived effective reward” $ER:{(A\times O)}^{\ast }\to [0,1]$ by

$$ER\left(ao\right):=\underset{\begin{array}{c}(T,R)\sim \zeta \\ (s_{n+1},o_n^{\prime })\sim T(s_n,a_n)\end{array}}{E}\left[R\left(s_{\left|h\right|}\right)\right|o^{\prime }=o]$$

It is then easy to see that the $E$ operator preserves expected utility: given any policy $\pi :{(A\times O)}^{\ast }\stackrel{k}{\to }A$ and $m\in N$

$$\underset{\begin{array}{c}(T,R)\sim \zeta \\ a_n\sim \pi \left(a{o}_{:n}\right)\\ (s_{n+1},o_n)\sim T(s_n,a_n)\end{array}}{E}\left[ER\left(a{o}_{:m}\right)\right]=\underset{\begin{array}{c}(T,R)\sim \zeta \\ a_n\sim \pi \left(a{o}_{:n}\right)\\ (s_{n+1},o_n)\sim T(s_n,a_n)\end{array}}{E}\left[R\left(s_m\right)\right]$$

and therefore, for any geometric time discount parameter $\gamma \in [0,1)$

$$\underset{\begin{array}{c}(T,R)\sim \zeta \\ a_n\sim \pi \left(a{o}_{:n}\right)\\ (s_{n+1},o_n)\sim T(s_n,a_n)\end{array}}{E}\left[\sum _{n=0}^{\infty }{\gamma }^{n}ER\left(a{o}_{:n}\right)\right]=\underset{\begin{array}{c}(T,R)\sim \zeta \\ a_n\sim \pi \left(a{o}_{:n}\right)\\ (s_{n+1},o_n)\sim T(s_n,a_n)\end{array}}{E}\left[\sum _{n=0}^{\infty }{\gamma }^{n}R\left(s_n\right)\right]$$

On the other hand, Bayesian regret is not preserved since, in general

$$\underset{(T,R)\sim \zeta }{E}\left[\underset{\pi }{max}\underset{aos\sim T\pi }{E}\left[\sum _{n=0}^{\infty }{\gamma }^{n}ER\left(a{o}_{:n}\right)\right]\right]\ne \underset{(T,R)\sim \zeta }{E}\left[\underset{\pi }{max}\underset{aos\sim T\pi }{E}\left[\sum _{n=0}^{\infty }{\gamma }^{n}R\left(s_n\right)\right]\right]$$

Here $aos\sim T\pi$ is shorthand notation for the same probability distribution as before.

Indeed, in Example 1 the LHS of the above is $\frac{1}{2}\cdot \frac{1}{1-\gamma }$ since $ER\equiv \frac{1}{2}$, whereas the RHS is $\frac{1}{2}+\frac{\gamma }{1-\gamma }$.

The pathology of Example 1 comes about because reward is not only imperceptible but entirely unobservable. That is, no experiment can produce any information about whether the reward on a given round $n>0$ was 0 or 1. More specifically, the states $s_{-}$ and $s_{+}$ are assigned different rewards, but there is no observable difference between them. It is as if Alice would assign value, not to people in Africa (whose existence and well-being can be measured) but to some Flying Spaghetti Monster s.t. the world behaves exactly the same regardless of its existence or condition.

This observation suggests that, instead of assigning rewards to states which are just abstract labels in a model, we should assign rewards to states that are defined in terms of the observable consequences of the interaction of the agent with the environment. This leads us to the notion of “instrumental state”, which we will now define formally.

Instrumental States and Reward Functions

First, we introduce some technical definitions for notational convenience.

Definition 1

$ConSet$ is the category whose objects are pairs $(V,C)$ where $V$ is a real vector space and $C$ is a convex subset of $V$, and whose morphisms are

$$Mor\left(\right(V,C),(W,D\left)\right):=$$ $$\{f:C\to D|\exists A\in Hom(V,W),w\in W\forall v\in C:f\left(v\right)=Av+w\}$$

We omit describing identity and composition of morphisms since they are obvious.

It is easy to see that $ConSet$ has arbitrary limits. In particular, $ConSet$ has a final object that we denote by $pt$ (the one point set), products ($(V,C)\times (W,D)\cong (V\oplus W,C\times D)$) and inverse limits of sequences. For any finite set $A$, $(R^A,\Delta A)$ is an object in $ConSet$. Also, we will sometimes abuse notation by regarding $C$ as an object of $ConSet$ instead of $(V,C)$ (i.e. making $V$ implicit).

Definition 2

The functor $\mathrm{Cone}:ConSet\to ConSet$ is defined by

$$\mathrm{Cone}(V,C):=(V\oplus R,\left\{\right(\lambda v,\lambda \left)\right|\lambda \in [0,1],v\in C\})$$ $$\left(\mathrm{Cone}f\right)(\lambda v,\lambda ):=\left(\lambda f\right(v),\lambda )$$

Definition 3

For any $C\in ConSet$, we define $h_C:\mathrm{Cone}C\to [0,1]$ by

$$h_C(\lambda v,\lambda ):=\lambda$$

Note that $h$ is a natural transformation from $\mathrm{Cone}$ to the constant functor with value $[0,1]$.

Given $C\in ConSet$ and $x\in \mathrm{Cone}C$ s.t.$x=(u,\lambda )$ for $\lambda >0$, we denote $\left[x\right]:={\lambda }^{-1}u\in C$.

Now, we are ready to define instrumental states. We fix the sets $A$ and $O$.

Definition 4

For any $n\in N$, we define ${IS}_n\in ConSet$, the space of $n$ time step instrumental states, recursively by

$${IS}_0:=pt$$ $${IS}_{n+1}:=\prod _{a\in A}{\left(\prod _{o\in O}{h}_{{IS}_n}\right)}^{-1}\left(\Delta O\right)$$

Here, ${\prod }_{o\in O}{h}_{{IS}_n}$ is a mapping from ${\prod }_{o\in O}\mathrm{Cone}{IS}_n$ to $[0,1{]}^O$. The inverse image of a convex set (in this case $\Delta O\subseteq [0,1{]}^O$) under an affine mapping (in this case ${\prod }_{o\in O}{h}_{{IS}_n}$) is also a convex set.

The semantics of Definition 4 is as follows. Any $\alpha \in {\left({\prod }_{o\in O}{h}_{{IS}_n}\right)}^{-1}\left(\Delta O\right)$ can be regarded as a pair consisting of some ${\alpha }^{\prime }\in \Delta O$ (the image of $\alpha$ under ${\prod }_{o\in O}{h}_{{IS}_n}$) and a mapping ${\alpha }^{\prime \prime }:\mathrm{supp}{\alpha }^{\prime }\to {IS}_n$ defined by ${\alpha }^{\prime \prime }\left(o\right):=\left[{\alpha }_o\right]$. Given $\theta \in {IS}_{n+1}$, ${\theta }_a^{\prime }$ is the probability distribution over observations resulting from taking action $a$ in state $\theta$, whereas ${\theta }_a^{\prime \prime }\left(o\right)$ is the state resulting from taking action a in state $\theta$ conditional on observing $o$. This semantics can be made more formal as follows:

Definition 5

Given $\theta \in {IS}_n$, we define $\mathrm{dom}\theta \subseteq {(A\times O)}^{\ast }$ recursively as follows:

1. $\lambda \in \mathrm{dom}\theta$

2. For all $h\in {(A\times O)}^{\ast }$, $a\in A$ and $o\in O$: $aoh\in \mathrm{dom}\theta$ iff $n>0$, $h_{{IS}_{n-1}}\left({\theta }_{ao}\right)>0$ and $h\in \mathrm{dom}\left[{\theta }_{ao}\right]$.

Definition 6

Given $\theta \in {IS}_n$, $h\in \mathrm{dom}\theta$ and $a\in A$, and assuming that $\left|h\right|<n$, we recursively define $\theta \left(ha\right)\in \Delta O$ by

1. For $h=\lambda$: $\theta (o\mid a):=h_{{IS}_{n-1}}\left({\theta }_{ao}\right)$

2. For $h=a^{\prime }{o}^{\prime }{h}^{\prime }$ with some $a^{\prime }\in A$, $o^{\prime }\in O$ and $h^{\prime }\in {(A\times O)}^{\ast }$: $\theta \left(ha\right):=\left[{\theta }_{a^{\prime }{o}^{\prime }}\right]\left(h^{\prime }a\right)$

The point of defining ${IS}_n$ in this manner is that (i) different points in ${IS}_n$ correspond to states that are truly not equivalent, i.e. can be empirically distinguished (statistically) and (ii) convex combinations of points in ${IS}_n$ correspond precisely to probabilistic mixtures. Formally, we have:

Definition 7

Given $\theta \in {IS}_n$ and $\pi :{(A\times O)}^{<n}\stackrel{k}{\to }A$ (a policy), we define $\theta \pi \in \Delta {(A\times O)}^n$ (probability distribution over histories resulting from following policy $\pi$ in state $\theta$) by

$$\underset{ao\sim \theta \pi }{\mathrm{Pr}}[a_m=a_{\ast }]=\underset{ao\sim \theta \pi }{E}\left[\pi \left(a_{\ast }\right|a{o}_{:m})\right]$$ $$\underset{ao\sim \theta \pi }{\mathrm{Pr}}[o_m=o_{\ast }]=\underset{ao\sim \theta \pi }{E}\left[\theta \left(o_{\ast }\right|a{o}_{:m}{a}_m)\right]$$

Proposition 1

Consider some $\theta ,{\theta }^{\prime }\in {IS}_n$ and assume that for any $\pi :{(A\times O)}^{<n}\to A$, $\theta \pi ={\theta }^{\prime }\pi$. Then, $\theta ={\theta }^{\prime }$.

Proposition 2

Consider some $\theta ,{\theta }^{\prime }\in {IS}_n$, $\pi :{(A\times O)}^{<n}\stackrel{k}{\to }A$ and $p\in [0,1]$. Then

$$(p\theta +(1-p\left){\theta }^{\prime }\right)\pi =p\theta \pi +(1-p){\theta }^{\prime }\pi$$

${IS}_n$ is a bounded polytope but in general it is *not} a simplex: we cannot regard it as just probability distributions over some set. For example, if $\left|A\right|=\left|O\right|=2$, then it’s easy to see that ${IS}_1$ is a square (one axis is the probability to get a given observation when taking one action, the other axis is the probability for the other action). On the other hand, if $\left|A\right|=1$ then ${IS}_n$ is a simplex: it is canonically isomorphic to $\Delta O^n$.

There are a natural morphisms ${pr}_n:{IS}_{n+1}\to {IS}_n$ whose semantics is forgetting about the behavior of the state at time step $n$:

Definition 8

We define ${pr}_n:{IS}_{n+1}\to {IS}_n$ for any $n\in N$ recursively.${pr}_0$ is the unique morphism from ${IS}_1$ to ${IS}_0\cong pt$. For any $n\in N$, ${pr}_{n+1}$ is given by

$${pr}_{n+1}(\theta {)}_{ao}:=\left(\mathrm{Cone}{pr}_n\right)\left({\theta }_{ao}\right)$$

We thereby get a sequence ${IS}_0\leftarrow {IS}_1\leftarrow {IS}_2\leftarrow \dots$

Definition 9

We define ${IS}_{\omega }$, the space of (infinite time step) instrumental states by

$${IS}_{\omega }:=\underset{n}{\underleftarrow{\lim }}{IS}_n$$

We denote the canonical projections by ${pr}_n^{\omega }:{IS}_{\omega }\to {IS}_n$.

Of course, ${IS}_{\omega }$ can also be regarded as the space of all possible stochastic environments. Specifically, we have:

Definition 10

For any $\mu \in {IS}_{\omega }$ we define $\mathrm{dom}\mu \in {(A\times O)}^{\ast }$ by

$$\mathrm{dom}\mu :=\bigcup _{n=0}^{\infty }\mathrm{dom}{pr}_n^{\omega }\mu$$

Definition 11

Given $\mu \in {IS}_{\omega }$, $h\in \mathrm{dom}\mu$ and $a\in A$, we define $\mu \left(ha\right)\in \Delta O$ by

$$\mu \left(ha\right):={pr}_{\left|h\right|+1}^{\omega }\mu \left(ha\right)$$

Like in the finite time case, we have

Definition 12

Given $\mu \in {IS}_{\omega }$ and $\pi :{(A\times O)}^{\ast }\stackrel{k}{\to }A$, we define $\mu \pi \in \Delta {(A\times O)}^{\omega }$ by

$$\underset{ao\sim \mu \pi }{\mathrm{Pr}}[a_n=a_{\ast }]=\underset{ao\sim \mu \pi }{E}\left[\pi \left(a_{\ast }\right|a{o}_{:n})\right]$$ $$\underset{ao\sim \mu \pi }{\mathrm{Pr}}[o_n=o_{\ast }]=\underset{ao\sim \mu \pi }{E}\left[\mu \left(o_{\ast }\right|a{o}_{:n}{a}_n)\right]$$

Proposition 3

Consider some $\mu ,{\mu }^{\prime }\in {IS}_{\omega }$ and assume that for any $\pi :{(A\times O)}^{\ast }\to A$, $\mu \pi ={\mu }^{\prime }\pi$. Then, $\mu ={\mu }^{\prime }$.

Proposition 4

Consider some $\mu ,{\mu }^{\prime }\in {IS}_{\omega }$, $\pi :{(A\times O)}^{\ast }\stackrel{k}{\to }A$ and $p\in [0,1]$. Then

$$(p\mu +(1-p\left){\mu }^{\prime }\right)\pi =p\mu \pi +(1-p){\mu }^{\prime }\pi$$

For each $n\in N$, ${IS}_n$ is finite-dimensional and therefore has a natural topology.${IS}_{\omega }$ also becomes a topological space by equipping it with the inverse limit topology. Since the ${IS}_n$ are closed and bounded they are compact, and therefore ${IS}_{\omega }$ is also compact by Tychonoff’s theorem. In the special case $\left|A\right|=1$, ${IS}_{\omega }\cong \Delta O^{\omega }$ and the inverse limit topology is the weak topology for probability measures, defined w.r.t. the product topology on $O^{\omega }$.

We can now give the first definition of an instrumental reward function: a continuous affine function $R:{IS}_{\omega }\to R$. Why affine? A convex linear combination of instrumental states is empirically indistinguishable from a probabilistic lottery. If we assign expected values to probabilistic lotteries (as we should by the VNM theorem), then we must also assign them to convex linear combinations of instrumental states: otherwise our reward again depends on entirely unobservable parameters of our model.

An alternative approach is to consider the notion of “experiment” explicitly.

We will use the notation $X^{\le \omega }:=X^{\ast }\bigsqcup X^{\omega }$. Given a logical condition $\varphi$, the symbol $1_{\varphi }$ will denote 1 when $\varphi$ is true and 0 when $\varphi$ is false.

Definition 13

Given $\pi :{(A\times O)}^{\ast }\stackrel{k}{\to }A\bigsqcup \left\{\perp \right\}$ and $\mu \in {IS}_{\omega }$, we define $\mu \pi \in \Delta {(A\times O)}^{\le \omega }$ by

$$\underset{ao\sim \mu \pi }{\mathrm{Pr}}[a_n=a_{\ast }]=\underset{ao\sim \mu \pi }{E}\left[1_{\left|ao\right|\ge n}\pi \left(a_{\ast }\right|a{o}_{:n})\right]$$ $$\underset{ao\sim \mu \pi }{\mathrm{Pr}}[o_n=o_{\ast }]=\underset{ao\sim \mu \pi }{E}\left[1_{\left|ao\right|>n}\mu \left(o_{\ast }\right|a{o}_{:n}{a}_n)\right]$$

$\pi$ is said to be a terminable policy when for any $\mu \in {IS}_{\omega }$

$$\underset{h\sim \mu \pi }{\mathrm{Pr}}[\left|h\right|<\infty ]=1$$

That is, a terminable policy is allowed to produce a special token $\perp$ which terminates the “experiment” (instead of choosing an action), and we require that, for any environment, this token will be eventually produced with probability 1.

Definition 14

Given a terminable policy $\pi$ and a bounded function $r:{(A\times O)}^{\ast }\to R$, we define the function $R_{\pi r}:{IS}_{\omega }\to R$ by

$$R_{\pi r}\left(\mu \right):=\underset{h\sim \mu \pi }{E}\left[r\right(h\left)\right]$$

This gives us a second definition of instrumental reward functions. In fact, the two definitions are equivalent:

Theorem 1

For any terminable policy $\pi$ and bounded function $r:{(A\times O)}^{\ast }\to R$, $R_{\pi r}$ is continuous and affine. Conversely, for any continuous affine $R:{IS}_{\omega }\to [0,1]$, there exists a terminable policy $\pi$ and $r:{(A\times O)}^{\ast }\to [-2,2]$ s.t. $R=R_{\pi r}$.

Putting the second part of the theorem into words, for any instrumental reward function (in the sense of the first definition) there is some experiment the agent can do which yields an unbiased estimate of the reward for the instrumental state that existed at the beginning of the experiment.

The range $[-2,2]$ is not optimal, but for the regret bound in the next subsection, it’s only important that it is bounded by some fixed constant.

To illustrate this concept of instrumental reward function, imagine that Clippy has access to a black box with a collection of levers on its outside. Pulling the levers produces some sounds that hint at what happens inside the box, but are not enough to determine it with certainty. The box has a shuttered glass window, whose shutter can be opened from the outside. Through the window, Clippy can see a jumble of scrap metal, mechanical manipulators that are controlled by the levers (and can be used to shape the scrap metal), and also a few mice running around the box and wreaking havoc. However, it is not possible to control the manipulators while the shutter is open. Worse, while opening the shutter allows seeing a snapshot of the shape of the metal, it also causes the manipulators to move chaotically, ruining this shape. So, Clippy can experiment with the levers and occasionally open the shutter to test the result. However, in order to produce and maintain paperclips inside the box, the shutter has to be kept closed (and the paperclips hidden) most of the time.

It is also possible to consider reward functions of the more general form $R:{(A\times O)}^{\ast }\times {IS}_{\omega }\to R$, required to be continuous and affine in the second argument. Such a reward function depends both on the current (unknown) instrumental state of the environment and the observable history so far. By Theorem 1, such a reward can be equivalently described in terms of a family ${\{{\pi }_h:{(A\times O)}^{\ast }\to A\bigsqcup \{\perp \left\}\right\}}_{h\in {(A\times O)}^{\ast }}$ of terminable policies and a family ${\{r_h:{(A\times O)}^{\ast }\to R\}}_{h\in {(A\times O)}^{\ast }}$ of bounded functions s.t.

$$R(h,\mu )=R_{{\pi }_h{r}_h}\left(\mu \right)$$

This means that, the value of reward can be estimated empirically, but only if the agent remembers the entire observation history. If the history is forgotten at some point, it might never be able to estimate the reward again. We will such reward functions “semi-instrumental”.

Although semi-instrumental reward functions are more general than instrumental reward functions, I think that there is some interest in studying the narrower class. Arguably, instrumental reward functions are a better model of what counts as “consequentialist” or “goal-directed” behavior, since they depend only on the state of the environment. Indeed, it is easy to construct a semi-instrumental reward function that makes any given policy Bayes-optimal for any given prior, so semi-instrumental reward functions are incapable (without further assumptions) to distinguish between “intelligent” and “unintelligent” behavior. On the other hand, optimality w.r.t. some instrumental reward function seems like a stronger condition.

In order to derive a regret bound, we will restrict attention to those reward functions for which the terminable policy can be made to terminate within time that has some finite and bounded expected value. I don’t know an elegant way to characterize those reward functions in general, but we will describe one class of such functions.

Definition 15

Consider any $C\in ConSet$. Then, we can define the total variation distance $d_{\text{tv}}:C\times C\to R$ by

$$d_{\text{tv}}(x,y):=\underset{r\in Mor(C,[0,1\left]\right)}{sup}\left|r\right(x)-r(y\left)\right|$$

In general, $d_{\text{tv}}$ is a pseudometric. Moreover, when $C$ is finite-dimensional and bounded, it is a metrization of the natural topology. For a finite set $A$ and $C=\Delta A$, $d_{\text{tv}}$ is just the usual total variation metric. For $C$ a ball of unit diameter in Euclidean space, $d_{\text{tv}}$ is the Euclidean metric.

Definition 16

Consider any $\lambda \in (0,1)$. We define the metric $d_{\text{tv}}^{\lambda }$ on ${IS}_{\omega }$ by

$$d_{\text{tv}}^{\lambda }(\mu ,\nu ):=\underset{n\in N}{sup}{\lambda }^n{d}_{\text{tv}}({pr}_n^{\omega }\mu ,{pr}_n^{\omega }\nu )$$

For any $\lambda$, $d_{\text{tv}}^{\lambda }$ is a metrization of the inverse limit topology on ${IS}_{\omega }$.

Proposition 5

Consider any $\lambda \in (0,1)$ and $R:{IS}_{\omega }\to R$ affine and Lipschitz with respect to $d_{\text{tv}}^{\lambda }$. Then there is a terminable policy $\pi$ and a bounded function $r:{(A\times O)}^{\ast }\to R$ s.t.$R=R_{\pi r}$ and

$$\underset{\mu \in {IS}_{\omega }}{sup}\underset{h\sim \mu \pi }{E}\left[\left|h\right|\right]<\infty$$

Note that $\lambda$ is a parameter reminiscent of geometric time discount that constraints the shape of the reward function. However, in the regret analysis that follows, it is not the same as the actual geometric time discount parameter $\gamma$. In particular, we consider the asymptotics in which the latter approaches 1, while the reward function is assumed to be fixed. It might be interesting to study regimes in which both approach 1, but we will not attempt it at present.

A Regret Bound for RL with Instrumental Rewards

Fix $A$ and $O$. For any finite set $S$ and $T:S\times A\stackrel{k}{\to }S\times O$, there is a unique mapping $I_T:S\to {IS}_{\omega }$ s.t.

$$I_T(s{)}_{ao}=(\sum _{s^{\prime }\in S}T(s^{\prime },o|s,a)I_T\left(s^{\prime }\right),\sum _{s^{\prime }\in S}T(s^{\prime },o|s,a))$$

That is, $I_T\left(s\right)$ is just the instrumental state corresponding to the POMDP state $s$.

Given $R:{IS}_{\omega }\to R$ continuous affine, we get for any $S$ and $T$ the POMDP reward function $R\circ I_T$. Hence, one natural setting for regret analysis is fixing $R$ and $S$ and considering a hypothesis class of transition kernels

$$H\subseteq \{S\times A\stackrel{k}{\to }S\times O\}$$

However, regret analysis for POMDPs involves some technical complexity, and we prefer to start with a simpler setting. Hopefully, we will address the POMDP case in a followup essay.

Suppose that $O=S$. Then, given any MPD transition kernel $T:S\times A\stackrel{k}{\to }S$, we can define the POMDP transition kernel $T^{♯}:S\times A\stackrel{k}{\to }S\times O$ by

$$T^{♯}(s^{\prime },s^{\prime \prime }|s,a):=1_{s^{\prime }=s^{\prime \prime }}T\left(s^{\prime }\right|s,a)$$

Fix $R:S\times {IS}_{\omega }\to [0,1]$ continuous affine in the second argument (a type of semi-instrumental reward function). For any $T$ as above, we get the induced reward function $R_T:S\to [0,1]$ given by $R_T\left(s\right):=R(s,I_{T^{♯}}(s\left)\right)$. We can now consider the learning problem corresponding to a hypothesis class of MDP transition kernels

$$H\subseteq \{S\times A\stackrel{k}{\to }S\}$$

It might seem odd to consider a setting with fully observable states in the context of imperceptible rewards. However, we can think about it as follows: what we observe is only a label whose physical meaning is unknown. Only given the (unknown) transition kernel, such a label can be interpreted as assigned a reward.

For example, imagine a robot tasked with sorting balls into bins according to their weight. Some of the balls are solid gold and some of them are solid silver, so it’s in principle possible to know their weight just by looking at them. However, the robot doesn’t know a priori whether silver or gold is heavier. On the other hand, the robot can perform some experiment with a ball to determine its weight. In this situation, the reward is imperceptible even if the state (e.g. the locations, colors and sizes of the balls, the locations and shapes of the bins and the location of the robot and the state of its manipulators) is fully observable.

Using the concepts of MB dimension and RVO dimension we defined in a previous essay, we can formulate the regret bound.

Theorem 2

There is some $C\in R^{+}$ s.t. the following holds.

Consider any finite non-empty sets $S$ and $A$, function continuous affine in the second argument $R:S\times {IS}_{\omega }\to [0,1]$, closed set $H\subseteq \{S\times A\stackrel{k}{\to }S\}$ and Borel probability measure $\zeta$ on $H$ (prior). Suppose ${\pi }_{est}:S\times {(A\times S)}^{\ast }\stackrel{k}{\to }A\bigsqcup \left\{\perp \right\}$ is s.t. for any $s\in S$, ${\pi }_{est}(s,\cdot )$ is terminable, and $r:S\times {(A\times S)}^{\ast }\to [0,1]$ is a bounded function s.t.

$$R(s,\cdot )=R_{{\pi }_{est}(s,\cdot )r(s,\cdot )}$$

Define the maximal expected reward estimation time $t_{est}$ by

$$t_{est}=\underset{s\in S,\mu \in {IS}_{\omega }}{sup}\underset{h\sim \mu {\pi }_{est}(s,\cdot )}{E}\left[\left|h\right|\right]$$

Define the maximal bias span $\tau$ by

$$\tau :=\underset{\gamma \to 1}{limsup}\underset{T\in H}{max}\frac{{max}_{s\in S}{V}_{T{R}_T}(s,\gamma )-{min}_{s\in S}{V}_{T{R}_T}(s,\gamma )}{1-\gamma }$$

Define $H_R\subseteq \{S\to R\}$ by

$$H_R:=\left\{R_T\right|T\in H\}$$

Denote $D_{MB}:={\dim }_{MB}{H}_R$ and $D_{RVO}:={\dim }_{RVO}{H}_R$. Define the Bayesian regret $R\left(\gamma \right)$ by

$$R\left(\gamma \right):=\underset{T\sim \zeta }{E}\left[{EU}_{T{R}_T}^{\ast }\right(\gamma )-{EU}_{T{R}_T}^{{\pi }_{\gamma }^{†}}(\gamma \left)\right]$$

Then, there is a family of policies ${\{{\pi }_{\gamma }^{†}:S^{\ast }\times S\stackrel{k}{\to }A\}}_{\gamma \in (0,1)}$ s.t.

$$\underset{\gamma \to 1}{limsup}\frac{R\left(\gamma \right)}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)(D_{RVO}+1)(1-\gamma )\ln \frac{1}{1-\gamma }}}\le C$$

Discussion

More on the Regret Bound

It might appear odd that the regret bound in Theorem 2 depends on the dimensions of the class of reward functions, but not on the dimensions on the class of transition kernels, like in the perceptible case. The reason for this is that we only give the asymptotic form. Asymptotically, the leading term is $O\left(\sqrt[3]{3(1-\gamma )\ln \frac{1}{1-\gamma }}\right)$ and its coefficient depends only on those parameters that appear in Theorem 2. However, examining the proof reveals that there is also an $O\left(\sqrt{(1-\gamma )\ln \frac{1}{1-\gamma }}\right)$ term that has the same form as the regret bound in the perceptible case. For the sake of brevity and simplicity we will not attempt to write down a more precise regret bound that reflects the role of the dimensions of the class of transition kernels, but in principle it is not difficult. We must keep in mind, however, that in practice the other term might be significant: a priori the dimensions of the class of transition kernels are only bounded by a polynomial in $\left|S\right|$ and $\left|A\right|$ and the latter might be exponentially big for realistic models.

The Death of the Agent and Kamikaze Strategies

There is one potential application of defining rewards that are not a direct function of observations which seems not supported by instrumental rewards as we defined them. Namely, one can imagine agents that are motivated to follow a certain strategy that is designed to destroy the agent but produce some desirable results in the external world (“kamikaze strategy”). In other words, although survival is a convergent instrumental goal, it seems entirely reasonable for it to be sacrificed in certain specific scenarios. To give an example, imagine a bodyguard robot whose primary goal is keeping a certain person alive. If assassins shoot at the person, and the only wait to stop them is for the robot to block the bullets with its body, then it can be the optimal strategy, even if it will destroy the robot and prevent it from continuing its function as bodyguard (assuming that e.g. it will give the person a chance to escape or someone else a chance to stop the assassins).

Our formalism doesn’t directly address the possibility of the agent’s death, because the sequence of actions and observations is assumed to be infinite. One simple way to accommodate death is postulating a special observation $\perp \in O$ s.t. it is never received before death and always received after death. If we do this, then death corresponds to a specific instrumental state and therefore its reward is a fixed constant. This seems incompatible with kamikaze strategies where the decision of self-sacrifice is contingent on conditions in the external world after death.

Another approach is assuming the agent becomes a “ghost”: it keeps receiving observations which reflect the actual physical world but its actions have no effect. Such ghosts might theoretically be produced by a simplicity prior: for example, if the agent is an AI connected to a camera that monitors a room, then we can imagine a virtual video of the same room continuing beyond the AI’s shutdown. This allows for different instrumental states after death and can potentially justify kamikaze strategies, but it seems like a very fragile construct and is unlikely to guarantee reasonable behavior.

The problem with death can be viewed from another perspective: our regret analysis assumes a no-traps condition ($\tau <\infty$) whereas death is usually a trap. Therefore, to guarantee rational behavior while accounting for death, we need to operate within a framework that allows for traps.

One such framework is requiring Bayes-optimality and giving up on learnability. This seems both too weak (because nothing is guaranteed for specific environments) and too strong (because it’s computationally intractable). That said, I think this approach can be salvaged by requiring something somewhat weaker than Bayes-optimality and proving something somewhat weaker than learnability (hopefully I will write on that in a future essay). In any case, once we give up on learnability we can allow unobservable rewards (the general POMDP setting in the beginning of the Results section) which allow handling death and kamikaze strategies easily. Specifically, we can have a plethora of “dead” states that produce only the $\perp$ observation and whose transitions do no depend on the action, but which have different rewards. So, this approach “solves” the problem but at a high cost: no learnability or regret analysis.

Another framework for dealing with traps is Delegative Reinforcement Learning (DRL). In DRL the agent interacts with an external advisor, and is thereby able to successfully navigate all traps that the advisor knows about. In other words, it converges to a policy that is Bayes-optimal with respect to the belief state of the advisor (while the advisor is not able to produce such a policy by itself). Combining DRL with the instrumental rewards formalism should allow accounting for death. Specifically, in any given POMDP hypothesis, the state space will be decomposed as $S=S_{\text{dead}}\bigsqcup S_{\text{alive}}$, with the following assumptions:

• The transition kernel on states in $S_{\text{dead}}$ doesn’t depend on the action.

• $S_{\text{dead}}$ is invariant under the dynamics (death is irreversible).

• The reward function on $S_{\text{dead}}$ can be arbitrary.

• The reward function on $S_{\text{alive}}$ has to factor through $I_T$ (i.e. depend only on the instrumental state), and moreover the policy for estimating the reward function is known to be safe (alternatively, we might let the agent learn a safe estimation policy from some space of candidate policies).

Under these assumptions (or some variant thereof), it seems plausible that we should be able to prove learnability and derive a reasonable regret bound. Formalizing this line of thought is a task for future work.

The DRL approach to kamikaze strategies also has implications on corrigibility. Indeed, if the external advice is compatible with an admissible reward function that recommends shutting down the agent (i.e. upon delegation, the advisor acts to shut down the agent) then a DRL agent will assist with its own shutdown. This property is preserved by subagents, since creating a subagent is another potentially irreversible action (and therefore must be vetted by the advisor).

Also, it is tempting to speculate about DRL as a model of human self-sacrifice. We have already speculated before that we can view DRL as model of human learning, where the human’s social environment or humanity as a whole is regarded as playing the role of the advisor. Similarly, humans that sacrifice their lives for the sake of their loved ones or the “greater good” can be regarded as heeding that “advise” regarding the rewards of states in which the human doesn’t exist. Under this model, we can make sense of self-sacrifices by individual humans but not of hypothetical self-sacrifice by humanity as a whole (potentially augmented by other minds with which we could communicate and find common ground), but, the latter restriction seems compatible with intuition.

Specifying Instrumental Reward Functions

It might be useful to find natural ways to specify instrumental reward functions. In particular, it is interesting to start with a reward function defined on a specific ontology (POMDP) and somehow extend it to a full instrumental reward function (which, like we said before, induces a reward function on any ontology via the $I_T$ mapping).

De Blanc suggests one way to extend reward functions from one POMDP to another, but I don’t know whether this operation leads to an instrumental reward function, i.e. whether it is compatible with the constraints imposed by affine dependencies between the states (and I don’t see any reason why it should).

Essentially, what we’re looking for is a way to extend an affine function from an affine subspace to the entire affine space (the affine subspace is the affine span of the instrumental states corresponding to the states of the initial ontology; note that, if these instrumental states are not affine independent, then we have some constraint on this initial reward function). One natural way to do it is looking for an affine function whose differential (the linear function part) has minimal norm, or choosing some privileged projection operator from the entire space to the affine subspace. However, since the natural norms we have here are not inner product norms, these choices are usually non-unique, and it’s possible we can’t get much out of it.

A different natural approach is using Occam’s razor, i.e. looking for an extension of minimal description length or the expected value of a random extension sampled from a conditional simplicity prior. This requires a natural way to describe instrumental reward functions. We do have such a way: assuming that the $\pi$ and $r$ guaranteed to exist by Theorem 1 can be chosen to be computable, the description is the program for those objects with respect to a fixed universal Turing machine (we consider a single program that computes both $\pi$ and $r$ to exploit possible mutual information between the two).

These questions are left for future research.

Proofs

Proof of Proposition 1

We proceed by induction on $n$. For $n=0$ there is nothing to prove since ${IS}_0=pt$ so $\theta ={\theta }^{\prime }$ a priori. Now, suppose $n>0$.

We need to show that for any $a_{\ast }\in A$ and $o_{\ast }\in O$, ${\theta }_{a_{\ast }{o}_{\ast }}={\theta }_{a_{\ast }{o}_{\ast }}^{\prime }$. To show it for given $a_{\ast }$ and $o_{\ast }$, we consider some $\pi$ s.t. $\pi \left(\lambda \right)=a_{\ast }$. Since $\theta \pi ={\theta }^{\prime }\pi$, we have

$$\underset{ao\sim \theta \pi }{\mathrm{Pr}}[o_0=o_{\ast }]=\underset{ao\sim {\theta }^{\prime }\pi }{\mathrm{Pr}}[o_0=o_{\ast }]$$

By Definition 7, we get,

$$\theta \left(o_{\ast }\right|a_{\ast })={\theta }^{\prime }\left(o_{\ast }\right|a_{\ast })$$

By Definition 6, we get,

$$h_{{IS}_{n-1}}({\theta }_{a_{\ast }{o}_{\ast }})=h_{{IS}_{n-1}}\left({\theta }_{a_{\ast }{o}_{\ast }}^{\prime }\right)$$

If this value vanishes then ${\theta }_{a_{\ast }{o}_{\ast }}={\theta }_{a_{\ast }{o}_{\ast }}^{\prime }=0$. Otherwise, consider any $\sigma :{(A\times O)}^{<n-1}\to A$ and define $\pi :{(A\times O)}^{<n}\to A$ by

$$\pi \left(\lambda \right):=a_{\ast }$$ $$\pi \left(aoh\right):=\sigma \left(h\right)$$

Definitions 6 and 7 imply that

$$\left[{\theta }_{a_{\ast }{o}_{\ast }}\right]\sigma \left(h\right)=\frac{\theta \pi \left(a_{\ast }{o}_{\ast }h\right)}{\theta \left(o_{\ast }\right|a_{\ast })}$$

and similarly for ${\theta }^{\prime }$. We have $\theta \pi ={\theta }^{\prime }\pi$ and $\theta \left(o_{\ast }\right|a_{\ast })={\theta }^{\prime }\left(o_{\ast }\right|a_{\ast })$, which implies $[{\theta }_{a_{\ast }{o}_{\ast }}]\sigma =\left[{\theta }_{a_{\ast }{o}_{\ast }}^{\prime }\right]\sigma$. By the induction hypothesis, we get $[{\theta }_{a_{\ast }{o}_{\ast }}]=\left[{\theta }_{a_{\ast }{o}_{\ast }}^{\prime }\right]$. Combining this with $h_{{IS}_{n-1}}({\theta }_{a_{\ast }{o}_{\ast }})=h_{{IS}_{n-1}}\left({\theta }_{a_{\ast }{o}_{\ast }}^{\prime }\right)$, we get ${\theta }_{a_{\ast }{o}_{\ast }}={\theta }_{a_{\ast }{o}_{\ast }}^{\prime }$. $■$

Proposition A.1

Consider any $C\in ConSet$, $\theta ,{\theta }^{\prime }\in \mathrm{Cone}C$ and $p\in [0,1]$. Assume that

$$h_C(p\theta +(1-p\left){\theta }^{\prime }\right)>0$$

Then

$$[p\theta +(1-p\left){\theta }^{\prime }\right]=\frac{p{h}_C(\theta )[\theta ]+(1-p)h_C\left({\theta }^{\prime }\right)\left[{\theta }^{\prime }\right]}{p{h}_C(\theta )+(1-p)h_C\left({\theta }^{\prime }\right)}$$

Here, $h_C(\theta )[\theta ]$ is understood to mean $0$ when $h_C(\theta )=0$ and the same for ${\theta }^{\prime }$.

Proof of Proposition A.1

Obvious from the definitions.

Proof of Proposition 2

Given $n\in N^{+}$ and some $\alpha ,\beta \in \Delta {(A\times O)}^n$, to show that $\alpha =\beta$ it is sufficient to show that

1. For any $a_{\ast }\in A$ and $o_{\ast }\in O$,

$$\underset{ao\sim \alpha }{\mathrm{Pr}}[a{o}_{:1}=a_{\ast }{o}_{\ast }]=\underset{ao\sim \beta }{\mathrm{Pr}}[a{o}_{:1}=a_{\ast }{o}_{\ast }]$$

1. For any $a_{\ast }\in A$ and $o_{\ast }\in O$, if $\underset{ao\sim \alpha }{\mathrm{Pr}}[a{o}_{:1}=a_{\ast }{o}_{\ast }]>0$ then for any $h\in {(A\times O)}^{n-1}$

$$\underset{ao\sim \alpha }{\mathrm{Pr}}[ao=a_{\ast }{o}_{\ast }h|a{o}_{:1}=a_{\ast }{o}_{\ast }]=\underset{ao\sim \beta }{\mathrm{Pr}}[ao=a_{\ast }{o}_{\ast }h|a{o}_{:1}=a_{\ast }{o}_{\ast }]$$

We will use this to prove the claim by induction on $n$. For $n=0$, there is nothing to prove. For $n>0$, by Definition 7

$$\underset{ao\sim (p\theta +(1-p\left){\theta }^{\prime }\right)\pi }{\mathrm{Pr}}[a{o}_{:1}=a_{\ast }{o}_{\ast }]=\pi \left(a_{\ast }\right|\lambda )(p\theta +(1-p\left){\theta }^{\prime }\right)\left(o_{\ast }\right|a_{\ast })$$

By Definition 6 $$\underset{ao\sim (p\theta +(1-p\left){\theta }^{\prime }\right)\pi }{\mathrm{Pr}}[a{o}_{:1}=a_{\ast }{o}_{\ast }]=\pi \left(a_{\ast }\right|\lambda )h_{{IS}_{n-1}}\left({(p\theta +(1-p\left){\theta }^{\prime }\right)}_{a_{\ast }{o}_{\ast }}\right)$$

$$\underset{(p\theta +(1-p\left){\theta }^{\prime }\right)\pi }{\mathrm{Pr}}[a{o}_{:1}=a_{\ast }{o}_{\ast }]=p\pi \left(a_{\ast }\right|\lambda )h\left({\theta }_{a_{\ast }{o}_{\ast }}\right)+(1-p)\pi \left(a_{\ast }\right|\lambda )h\left({\theta }_{a_{\ast }{o}_{\ast }}^{\prime }\right)$$

$$\underset{(p\theta +(1-p\left){\theta }^{\prime }\right)\pi }{\mathrm{Pr}}[a{o}_{:1}=a_{\ast }{o}_{\ast }]=p\pi \left(a_{\ast }\right|\lambda )\theta \left(o_{\ast }\right|a_{\ast })+(1-p)\pi \left(a_{\ast }\right|\lambda ){\theta }^{\prime }\left(o_{\ast }\right|a_{\ast })$$

$$\underset{(p\theta +(1-p\left){\theta }^{\prime }\right)\pi }{\mathrm{Pr}}[a{o}_{:1}=a_{\ast }{o}_{\ast }]=p\underset{\theta \pi }{\mathrm{Pr}}[a{o}_{:1}=a_{\ast }{o}_{\ast }]+(1-p)\underset{{\theta }^{\prime }\pi }{\mathrm{Pr}}[a{o}_{:1}=a_{\ast }{o}_{\ast }]$$

$$\underset{(p\theta +(1-p\left){\theta }^{\prime }\right)\pi }{\mathrm{Pr}}[a{o}_{:1}=a_{\ast }{o}_{\ast }]=\underset{p\theta \pi +(1-p)\theta \pi }{\mathrm{Pr}}[a{o}_{:1}=a_{\ast }{o}_{\ast }]$$

Furthermore, Definitions 6 and 7 imply that

$$\underset{(p\theta +(1-p\left){\theta }^{\prime }\right)\pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }h\right|a{o}_{:1}=a_{\ast }{o}_{\ast }]=\underset{\left[{(p\theta +(1-p\left){\theta }^{\prime }\right)}_{a_{\ast }{o}_{\ast }}\right]\sigma }{\mathrm{Pr}}\left[h\right]$$

Here, $\sigma$ is defined by $\sigma \left(h\right):=\pi \left(a_{\ast }{o}_{\ast }h\right)$.

Denote

$$q:=\frac{ph({\theta }_{a_{\ast }{o}_{\ast }})}{ph({\theta }_{a_{\ast }{o}_{\ast }})+(1-p)h({\theta }_{a_{\ast }{o}_{\ast }}^{\prime })}$$

By Proposition A.1

$$\left[{(p\theta +(1-p\left){\theta }^{\prime }\right)}_{a_{\ast }{o}_{\ast }}\right]=q[{\theta }_{a_{\ast }{o}_{\ast }}]+(1-q)\left[{\theta }_{a_{\ast }{o}_{\ast }}^{\prime }\right]$$

We get

$$\underset{(p\theta +(1-p\left){\theta }^{\prime }\right)\pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }h\right|a{o}_{:1}=a_{\ast }{o}_{\ast }]=\underset{(q[{\theta }_{a_{\ast }{o}_{\ast }}]+(1-q\left)\left[{\theta }_{a_{\ast }{o}_{\ast }}^{\prime }\right]\right)\sigma }{\mathrm{Pr}}\left[h\right]$$

By the induction hypothesis, we get

$$\underset{(p\theta +(1-p\left){\theta }^{\prime }\right)\pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }h\right|a{o}_{:1}=a_{\ast }{o}_{\ast }]=\underset{q[{\theta }_{a_{\ast }{o}_{\ast }}]\sigma +(1-q)\left[{\theta }_{a_{\ast }{o}_{\ast }}^{\prime }\right]\sigma }{\mathrm{Pr}}\left[h\right]$$

Decomposing the right hand side and applying the same reasoning in reverse,

$$\underset{(p\theta +(1-p\left){\theta }^{\prime }\right)\pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }h\right|a_{\ast }{o}_{\ast }]=q\underset{\theta \pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }h\right|a_{\ast }{o}_{\ast }]+(1-q)\underset{{\theta }^{\prime }\pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }h\right|a_{\ast }{o}_{\ast }]$$

By Definition 6, $q$ can be written as

$$q=\frac{p\theta \left(o_{\ast }\right|a_{\ast })}{p\theta \left(o_{\ast }\right|a_{\ast })+(1-p){\theta }^{\prime }\left(o_{\ast }\right|a_{\ast })}$$

Multiplying the numerator and denominator by $\pi \left(a_{\ast }\right|\lambda )$, we get

$$q=\frac{p\pi \left(a_{\ast }\right|\lambda )\theta \left(o_{\ast }\right|a_{\ast })}{p\pi \left(a_{\ast }\right|\lambda )\theta \left(o_{\ast }\right|a_{\ast })+(1-p)\pi \left(a_{\ast }\right|\lambda ){\theta }^{\prime }\left(o_{\ast }\right|a_{\ast })}$$

$$q=\frac{p\underset{\theta \pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }\right]}{p\underset{\theta \pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }\right]+(1-p)\underset{{\theta }^{\prime }\pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }\right]}$$

Combining this with the previous identity, we get

$$\dots =\frac{p\underset{\theta \pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }\right]\underset{\theta \pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }h\right|a_{\ast }{o}_{\ast }]+(1-p)\underset{{\theta }^{\prime }\pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }\right]\underset{{\theta }^{\prime }\pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }h\right|a_{\ast }{o}_{\ast }]}{p\underset{\theta \pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }\right]+(1-p)\underset{{\theta }^{\prime }\pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }\right]}$$

$$\underset{(p\theta +(1-p\left){\theta }^{\prime }\right)\pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }h\right|a_{\ast }{o}_{\ast }]=\frac{p\underset{\theta \pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }h\right]+(1-p)\underset{{\theta }^{\prime }\pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }h\right]}{p\underset{\theta \pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }\right]+(1-p)\underset{{\theta }^{\prime }\pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }\right]}$$

$$\underset{(p\theta +(1-p\left){\theta }^{\prime }\right)\pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }h\right|a_{\ast }{o}_{\ast }]=\frac{\underset{p\theta \pi +(1-p){\theta }^{\prime }\pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }h\right]}{\underset{p\theta \pi +(1-p){\theta }^{\prime }\pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }\right]}$$

$$\underset{(p\theta +(1-p\left){\theta }^{\prime }\right)\pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }h\right|a_{\ast }{o}_{\ast }]=\underset{p\theta \pi +(1-p){\theta }^{\prime }\pi }{\mathrm{Pr}}\left[a_{\ast }{o}_{\ast }h\right|a_{\ast }{o}_{\ast }]■$$

Given $\mu \in \Delta X^{\omega }$ and $f:X^{\omega }\to X^n$ defined by $f\left(x\right):=x_{:n}$, we will denote ${\mu }_{:n}:=f_{\ast }\mu$.

Proposition A.2

Consider any $C,D\in ConSet$ and $f\in Mor(C,D)$. Then,

$$h_D\circ \mathrm{Cone}f=h_C$$

Proof of Proposition A.2

Obvious from the definitions.

Proposition A.3

Consider any $C,D\in ConSet$, $f\in Mor(C,D)$ and $\theta \in \mathrm{Cone}C\setminus 0$. Then,

$$\left[\left(\mathrm{Cone}f\right)\right(\theta \left)\right]=f\left(\left[\theta \right]\right)$$

Proof of Proposition A.3

Obvious from the definitions.

Proposition A.4

Consider any $n\in N$, $\theta \in {IS}_{n+1}$, $a\in A$ and $h\in \mathrm{dom}\theta$ s.t. $\left|h\right|<n$. Then,

$${pr}_n\left(\theta \right)\left(ha\right)=\theta \left(ha\right)$$

Proof of Proposition A.4

We prove the claim by induction on $n$. For $n=0$, there is nothing to prove. Assume $n>0$. For $h=\lambda$, we have

$${pr}_n\left(\theta \right)\left(o\right|a)=h\left({pr}_n\right(\theta {)}_{ao})=h\left(\left(\mathrm{Cone}{pr}_{n-1}\right)\left({\theta }_{ao}\right)\right)$$

By Proposition A.2

$${pr}_n\left(\theta \right)\left(o\right|a)=h\left({\theta }_{ao}\right)=\theta \left(o\right|a)$$

Now suppose that $h=a^{\prime }{o}^{\prime }{h}^{\prime }$. We get

$${pr}_n\left(\theta \right)\left(a^{\prime }{o}^{\prime }{h}^{\prime }a\right)=\left[{pr}_n\right(\theta {)}_{a^{\prime }{o}^{\prime }}]\left(h^{\prime }a\right)=\left[\left(\mathrm{Cone}{pr}_{n-1}\right)\left({\theta }_{a^{\prime }{o}^{\prime }}\right)\right]\left(h^{\prime }a\right)$$

By Proposition A.3

$${pr}_n\left(\theta \right)\left(a^{\prime }{o}^{\prime }{h}^{\prime }a\right)={pr}_{n-1}\left[{\theta }_{a^{\prime }{o}^{\prime }}\right]\left(h^{\prime }a\right)$$

Using the induction hypothesis

$${pr}_n\left(\theta \right)\left(a^{\prime }{o}^{\prime }{h}^{\prime }a\right)=\left[{\theta }_{a^{\prime }{o}^{\prime }}\right]\left(h^{\prime }a\right)=\theta \left(a^{\prime }{o}^{\prime }{h}^{\prime }a\right)■$$

Proof of Proposition 3

Proposition A.4 implies that, in Definition 11, we can replace $\left|h\right|+1$ by any $m\ge \left|h\right|+1$. Therefore, for any $n\in N$, $\left({pr}_n^{\omega }\mu \right)\pi =\mu {\pi }_{:n}$. Hence, $\mu \pi ={\mu }^{\prime }\pi$ implies that $({pr}_n^{\omega }\mu )\pi =\left({pr}_n^{\omega }{\mu }^{\prime }\right)\pi$. By Proposition 1, we get ${pr}_n^{\omega }\mu ={pr}_n^{\omega }{\mu }^{\prime }$, and therefore $\mu ={\mu }^{\prime }$. $■$

Proof of Proposition 4

For any $n\in N$, Proposition 2 implies that

$$(p\cdot {pr}_n^{\omega }\mu +(1-p)\cdot {pr}_n^{\omega }{\mu }^{\prime })\pi =p({pr}_n^{\omega }\mu )\pi +(1-p)\left({pr}_n^{\omega }{\mu }^{\prime }\right)\pi$$

${pr}_n^{\omega }$ is an affine mapping, therefore

$${pr}_n^{\omega }(p\mu +(1-p\left){\mu }^{\prime }\right)\pi =p({pr}_n^{\omega }\mu )\pi +(1-p)\left({pr}_n^{\omega }{\mu }^{\prime }\right)\pi$$

Using Proposition A.4

$$(p\mu +(1-p\left){\mu }^{\prime }\right){\pi }_{:n}=p\mu {\pi }_{:n}+(1-p){\mu }^{\prime }{\pi }_{:n}={(p\mu \pi +(1-p\left){\mu }^{\prime }\pi \right)}_{:n}$$

Since this holds for any $n$, we must have that

$$(p\mu +(1-p\left){\mu }^{\prime }\right)\pi =p\mu \pi +(1-p){\mu }^{\prime }\pi ■$$

Proposition A.5

For any terminable policy $\pi$

$$\underset{n\to \infty }{lim}\underset{\mu \in {IS}_{\omega }}{sup}\underset{h\sim \mu \pi }{\mathrm{Pr}}[\left|h\right|>n]=0$$

Proof of Proposition A.5

Assume to the contrary that there is $ϵ\in (0,1)$ and sequences ${\{n_k\in N\}}_{k\in N}$ and ${\{{\mu }_k\in {IS}_{\omega }\}}_{k\in N}$ s.t.$n_{k+1}>n_k$ and, for any $k\in N$

$$\underset{h\sim {\mu }_k\pi }{\mathrm{Pr}}[\left|h\right|>n_k]>ϵ$$

${IS}_{\omega }$ is compact, therefore $\left\{{\mu }_k\right\}$ has a convergent subsequence. Without loss of generality, we can assume that $\left\{{\mu }_k\right\}$ itself converges and denote ${\mu }_{\ast }:={lim}_{k\to \infty }{\mu }_k$. For any $k\in N$ and $j>k$, we have $n_k<n_j$ and therefore

$$\underset{h\sim {\mu }_j\pi }{\mathrm{Pr}}[\left|h\right|>n_k]\ge \underset{h\sim {\mu }_j\pi }{\mathrm{Pr}}[\left|h\right|>n_j]>ϵ$$

Using Proposition A.4, it follows that

$$\underset{h\sim {pr}_{n_k+1}^{\omega }\left({\mu }_j\right)\pi }{\mathrm{Pr}}[\left|h\right|>n_k]>ϵ$$

The right hand side is clearly continuous in ${pr}_{n_k+1}^{\omega }\left({\mu }_j\right)$, and the latter converges to ${pr}_{n_k+1}^{\omega }\left({\mu }_{\ast }\right)$ as $j$ goes to $\infty$. We get

$$\underset{h\sim {\mu }_{\ast }\pi }{\mathrm{Pr}}[\left|h\right|>n_k]=\underset{h\sim {pr}_{n_k+1}^{\omega }\left({\mu }_{\ast }\right)\pi }{\mathrm{Pr}}[\left|h\right|>n_k]>ϵ$$

Since this holds for any $k$, it follows that

$$\underset{h\sim {\mu }_{\ast }\pi }{\mathrm{Pr}}[\left|h\right|=\infty ]=\underset{k\to \infty }{lim}\underset{h\sim {\mu }_{\ast }\pi }{\mathrm{Pr}}[\left|h\right|>n_k]\ge ϵ$$

This contradicts the assumption that $\pi$ is terminable. $■$

Proposition A.6

Consider ${\left\{X_n\right\}}_{n\in N}$ a sequence of compact Polish spaces, and ${\{{pr}_n:X_{n+1}\to X_n\}}_{n\in N}$ continuous mappings. Denote

$$X_{\omega }:=\underset{n}{\underleftarrow{\lim }}{X}_n$$

Denote ${pr}_n^{\omega }:X_{\omega }\to X_n$ the canonical mapping. Let $f:X\to R$ be continuous. Then,

$$\underset{n\to \infty }{lim}\underset{\begin{array}{c}x\in X_n\\ x_{1,2}\in {\left({pr}_n^{\omega }\right)}^{-1}\left(x\right)\end{array}}{sup}|f\left(x_1\right)-f\left(x_2\right)|=0$$

Proof of Proposition A.6

Assume to the contrary that there is $ϵ\in R^{+}$, and sequences ${\{n_k\in N\}}_{k\in N}$, ${\{x_1^k,x_2^k\in X_{\omega }\}}_{k\in N}$ s.t. $n_{k+1}>n_k$, ${pr}_{n_k}^{\omega }\left(x_1^k\right)={pr}_{n_k}^{\omega }\left(x_2^k\right)$ and $f\left(x_1^k\right)-f\left(x_2^k\right)>ϵ$. Without loss of generality, we assume that $n_k=k$ and the limits $x_{1,2}^{\ast }:={lim}_{n\to \infty }{x}_{1,2}^n$ exist (the latter using the fact $X_{\omega }$ is compact by Tychonoff’s theorem). It follows that $f\left(x_1^{\ast }\right)-f\left(x_2^{\ast }\right)\ge ϵ$, and in particular $x_1^{\ast }\ne x_2^{\ast }$ and therefore there is $m\in N$ s.t. ${pr}_m^{\omega }\left(x_1^{\ast }\right)\ne {pr}_m^{\omega }\left(x_2^{\ast }\right)$. On the other hand, ${pr}_n^{\omega }\left(x_1^n\right)={pr}_n^{\omega }\left(x_2^n\right)$, implying that, for $n\ge m$, ${pr}_m^{\omega }\left(x_1^n\right)={pr}_m^{\omega }\left(x_2^n\right)$ and therefore ${pr}_m^{\omega }\left(x_1^{\ast }\right)={pr}_m^{\omega }\left(x_2^{\ast }\right)$, a contradiction. $■$

Proposition A.7

Let $V$ be a finite-dimensional normed vector space and $W\subseteq V^{\ast }$ a linear subspace. Suppose $v\in V$ and $ϵ\in R^{+}$ are s.t. for any $\alpha \in W$, $\left|\alpha \right(v\left)\right|\le ϵ\parallel \alpha \parallel$. Then, there is $v^{\prime }\in W^{\perp }\subseteq V$ s.t. $\parallel v-v^{\prime }\parallel \le ϵ$.

In the above, $\parallel \alpha \parallel$ refers to the standard dual norm on $V^{\ast }$, induced by the norm on $V$. $W^{\perp }$ refers to the set $\{v\in V|\forall \alpha \in W:\alpha \left(v\right)=0\}$.

Proof of Proposition A.7

Consider $v^{\ast }\in W^{\ast }$ defined by $v^{\ast }\left(\alpha \right):=\alpha \left(v\right)$. By the assumption about $v$, $\parallel v^{\ast }\parallel \le ϵ$. By the Hahn-Banach theorem, there is $u^{\ast }\in V^{\ast \ast }$ s.t.$u^{\ast }{|}_W=v^{\ast }$ and $\parallel u^{\ast }\parallel \le ϵ$. Using the canonical isomorphism $V\cong V^{\ast \ast }$, $u^{\ast }$ corresponds to some $u\in V$, and it follows that $\parallel u\parallel \le ϵ$ and for any $\alpha \in W$, $\alpha \left(u\right)=\alpha \left(v\right)$. We now take $v^{\prime }:=v-u$. $■$

Proposition A.8

Let $C,D\in ConSet$, $f\in Mor(C,D)$ and $r\in Mor(C,R)$. Assume $D$ is a bounded closed finite-dimensional polytope, and $f$ is onto (as a mapping). Suppose $ϵ\in R^{+}$ s.t. for any $x_{1,2}\in C$, if $f\left(x_1\right)=f\left(x_2\right)$ then $|r\left(x_1\right)-r\left(x_2\right)|\le ϵ$. Then, there exists $r^{\prime }\in Mor(D,R)$ s.t. for any $x\in C$

$$|r\left(x\right)-r^{\prime }\left(f\right(x\left)\right)|\le \frac{3}{2}ϵ$$

Proof of Proposition A.8

Let $X$ be the vector space correspond to $C$, let $Y$ be the vector space corresponding to $D$ (so that $C\subseteq X$ and $D\subseteq Y$) and let $Q$ be the (finite) set of vertices of $D$. Since $f$ is onto, we can choose some $g:Q\to C$ s.t. for any $q\in Q$, $f\left(g\right(q\left)\right)=q$. Define $v\in R^Q$ by $v_q:=r\left(g\right(q\left)\right)$. Let $R_0^Q$ be the linear subspace of $R^Q$ given by

$$R_0^Q:=\{u\in R^Q|\sum _{q\in Q}{u}_q=0\}$$

Define the linear operators $A:R^Q\to X$ and $B:R^Q\to Y$ by

$$Au:=\sum _{q\in Q}{u}_{q}g\left(q\right)$$

$$Bu:=\sum _{q\in Q}{u}_{q}q$$

Consider any $w\in \ker B\cap R_0^Q\setminus 0$. In particular, $w\in R_0^Q$ and therefore

$$0=\sum _{q\in Q}{w}_q=\sum _{q\in Q}{1}_{w_q>0}{w}_q+\sum _{q\in Q}{1}_{w_q<0}{w}_q$$

Also

$${\parallel w\parallel }_1=\sum _{q\in Q}\left|w_q\right|=\sum _{q\in Q}{1}_{w_q>0}{w}_q-\sum _{q\in Q}{1}_{w_q<0}{w}_q$$

Combining the last two identities, we conclude

$$\sum _{q\in Q}{1}_{w_q>0}{w}_q=-\sum _{q\in Q}{1}_{w_q<0}{w}_q=\frac{{\parallel w\parallel }_1}{2}$$

Using the assumption $w\ne 0$, this allows us to define $w^{+},w^{-}\in \Delta Q$ by

$$w_q^{+}:=\frac{2}{{\parallel w\parallel }_1}{1}_{w_q>0}{w}_q$$

$$w_q^{-}:=-\frac{2}{{\parallel w\parallel }_1}{1}_{w_q<0}{w}_q$$

We have $w=\frac{1}{2}{\parallel w\parallel }_1(w^{+}-w^{-})$. Also, $Bw=0$ and therefore $B{w}^{+}=B{w}^{-}$.

Now, for any $u\in \Delta Q$, we have

$$u\cdot v=\sum _{q\in Q}{u}_q{v}_q=\sum _{q\in Q}{u}_{q}r\left(g\right(q\left)\right)=r\left(\sum _{q\in Q}{u}_{q}g\right(q\left)\right)=r\left(Au\right)$$

Moreover,

$$f\left(Au\right)=f\left(\sum _{q\in Q}{u}_{q}g\right(q\left)\right)=\sum _{q\in Q}{u}_{q}f\left(g\right(q\left)\right)=\sum _{q\in Q}{u}_{q}q=Bu$$

It follows that

$$w\cdot v=\frac{1}{2}{\parallel w\parallel }_1(w^{+}\cdot v-w^{-}\cdot v)=\frac{1}{2}{\parallel w\parallel }_1(r\left(A{w}^{+}\right)-r\left(A{w}^{-}\right))$$

By our previous reasoning, $f\left(A{w}^{+}\right)=B{w}^{+}=B{w}^{-}=f\left(A{w}^{-}\right)$. Therefore, we can use the assumption on $r$ to conclude that

$$|w\cdot v|=\frac{1}{2}{\parallel w\parallel }_1|r\left(A{w}^{+}\right)-r\left(A{w}^{-}\right)|\le \frac{ϵ}{2}{\parallel w\parallel }_1$$

By Proposition A.7, it follows that there is some $v^{\prime }\in R^Q$ s.t.$v^{\prime }\in {(\ker B\cap R_0^Q)}^{\perp }$ and ${\parallel v-v^{\prime }\parallel }_{\infty }\le \frac{ϵ}{2}$ (the $L^{\infty }$ norm is dual to the $L^1$ norm).

Now, consider some $y\in D$. There is some $u\in \Delta Q$ s.t. $y=Bu$. We define $r^{\prime }\left(y\right):=u\cdot v^{\prime }$. To see this definition is unambiguous, consider some $u^{\prime }\in \Delta Q$ s.t. also $y=B{u}^{\prime }$. In particular, $B(u-u^{\prime })=0$ and therefore $u-u^{\prime }\in \ker B$. Moreover, $u-u^{\prime }\in R_0^Q$ since $u,u^{\prime }\in \Delta Q$. Using that $u-u^{\prime }\in \ker B\cap R_0^Q$ and $v^{\prime }\in {(\ker B\cap R_0^Q)}^{\perp }$, we get

$$u\cdot v^{\prime }-u^{\prime }\cdot v^{\prime }=(u-u^{\prime })\cdot v^{\prime }=0$$

It is easy to see that $r^{\prime }$ is affine.

Finally, consider any $x\in C$. Choose $u\in \Delta Q$ s.t. $f\left(x\right)=Bu$. We have

$$|r\left(x\right)-r^{\prime }\left(f\right(x\left)\right)|\le |r\left(x\right)-r\left(Au\right)|+|r\left(Au\right)-r^{\prime }\left(f\right(x\left)\right)|$$

Since $f\left(Au\right)=Bu$, we can use the assumption on $r$ to bound the first term on the right hand side:

$$|r\left(x\right)-r\left(Au\right)|\le ϵ$$

For the second term, we have

$$|r\left(Au\right)-r^{\prime }\left(f\right(x\left)\right)|=|u\cdot v-u\cdot v^{\prime }|=|u\cdot (v-v^{\prime })|\le {\parallel u\parallel }_1{\Vert v-v^{\prime }\Vert }_{\infty }\le \frac{ϵ}{2}$$

Combining the two, we conclude

$$|r\left(x\right)-r^{\prime }\left(f\right(x\left)\right)|\le \frac{3}{2}ϵ■$$

Proposition A.9

Let $A$ be a finite set, $C\in ConSet$ and $R\in Mor(C^A,[0,1\left]\right)$. Assume $R$ attains its infimum at some point ${\theta }^{\ast }\in C^A$. Then, there exist $\pi \in \Delta A$ and $r:A\to Mor(C,[0,1\left]\right)$ s.t. for any $\theta \in C^A$ $$R\left(\theta \right)=\underset{a\sim \pi }{E}\left[r(a,{\theta }_a)\right]$$

Here, we used implicit currying: $r(a,x):=r\left(a\right)\left(x\right)$.

Proof of Proposition A.9

For each $a\in A$, define ${\iota }_a\in Mor(C,C^A)$ by

$${\iota }_a(x{)}_b:=\{\begin{array}{c}x\text{if}a=b\\ {\theta }_b^{\ast }\text{if}a\ne b\end{array}$$

Denote $R_a:=R\circ {\iota }_a$ and $N_a:=sup{R}_a-inf{R}_a$. If $N_a$ vanishes for every $a\in A$, then $R$ is constant, so we can set $r$ to the same constant and take arbitrary $\pi$. Otherwise, we define $\pi$ and $r$ by

$${\pi }_a:=\frac{N_a}{{\sum }_{b\in A}{N}_b}$$

$$r(a,x):=R\left({\theta }^{\ast }\right)+\frac{{\sum }_{b\in A}{N}_b}{N_a}\left(R_a\right(x)-R\left({\theta }^{\ast }\right))$$

We need to show that $r$ takes values in $[0,1]$. It is non-negative since $R$ is minimal at ${\theta }^{\ast }$, so both terms in $r$ are non-negative. To see it is not greater than $1$, observe that

$$r(a,x)=R\left({\theta }^{\ast }\right)+\frac{{\sum }_{b\in A}{N}_b}{N_a}\left(R_a\right(x)-R\left({\theta }^{\ast }\right))\le infR+\frac{{\sum }_{b\in A}{N}_b}{N_a}(sup{R}_a-infR)$$

Clearly $infR=inf{R}_a$ and therefore $sup{R}_a-infR=N_a$. It is also easy to see that, since $R$ is affine, $supR-infR={\sum }_{b\in A}{N}_b$. We get

$$r(a,x)\le infR+\frac{{\sum }_{b\in A}{N}_b}{N_a}{N}_a=infR+\sum _{b\in A}{N}_b=supR\le 1$$

It remains to show that $R\left(\theta \right)=\underset{a\sim \pi }{E}\left[r(a,{\theta }_a)\right]$. We have

$$\underset{a\sim \pi }{E}\left[r(a,{\theta }_a)\right]=\sum _{a\in A}{\pi }_{a}r(a,{\theta }_a)$$

$$\underset{a\sim \pi }{E}\left[r(a,{\theta }_a)\right]=\sum _{a\in A}{\pi }_a(R\left({\theta }^{\ast }\right)+\frac{{\sum }_{b\in A}{N}_b}{N_a}(R_a\left({\theta }_a\right)-R\left({\theta }^{\ast }\right)))$$

$$\underset{a\sim \pi }{E}\left[r(a,{\theta }_a)\right]=\sum _{a\in A}{\pi }_{a}R\left({\theta }^{\ast }\right)+\sum _{a\in A}{\pi }_a\frac{{\sum }_{b\in A}{N}_b}{N_a}(R_a\left({\theta }_a\right)-R\left({\theta }^{\ast }\right))$$

$$\underset{a\sim \pi }{E}\left[r(a,{\theta }_a)\right]=R\left({\theta }^{\ast }\right)+\sum _{a\in A}\frac{N_a}{{\sum }_{b\in A}{N}_b}\cdot \frac{{\sum }_{b\in A}{N}_b}{N_a}(R_a\left({\theta }_a\right)-R\left({\theta }^{\ast }\right))$$

$$\underset{a\sim \pi }{E}\left[r(a,{\theta }_a)\right]=R\left({\theta }^{\ast }\right)+\sum _{a\in A}(R_a\left({\theta }_a\right)-R\left({\theta }^{\ast }\right))$$

Using the fact $R$ is affine, the desired conclusion follows. $■$

Proposition A.10

Consider any $n\in N$ and $R\in Mor({IS}_n,[0,1\left]\right)$. Then, there exist $\pi :{(A\times O)}^{<n}\stackrel{k}{\to }A$ and $r:{(A\times O)}^n\to [0,1]$ s.t. for any $\theta \in {IS}_n$

$$R\left(\theta \right)=\underset{\theta \pi }{E}\left[r\right]$$

Proof of Proposition A.10

We proceed by induction on $n$. For $n=0$, $R$ is constant and we set $r$ to the same constant. Now, suppose $n>0$.

Define ${IS}_{n-\frac{1}{2}}\in ConSet$ by

$${IS}_{n-\frac{1}{2}}:={\left(\prod _{o\in O}{h}_{{IS}_{n-1}}\right)}^{-1}\left(\Delta O\right)$$

Using Proposition A.9, we get ${\pi }_0\in \Delta A$ and $r_0:A\to Mor({IS}_{n-\frac{1}{2}},[0,1\left]\right)$ s.t. for any $\theta \in {IS}_n$

$$R\left(\theta \right)=\underset{a\sim {\pi }_0}{E}\left[r_0(a,{\theta }_a)\right]$$

For every $o\in O$, we define $j_o\in Mor({IS}_{n-1},{IS}_{n-\frac{1}{2}})$ by

$$j_o(\theta {)}_{o^{\prime }}:=\{\begin{array}{c}(\theta ,1)\text{if}o=o^{\prime }\\ 0\text{if}o\ne o^{\prime }\end{array}$$

For every $a\in A$ and $o\in O$, we apply the induction hypothesis to $r_0\left(a\right)\circ j_o$, and get ${\pi }_{ao}:{(A\times O)}^{<n-1}\stackrel{k}{\to }A$ and $r_{ao}:{(A\times O)}^{n-1}\to [0,1]$ s.t. for any $\theta \in {IS}_{n-1}$

$$r_0(a,j_o(\theta \left)\right)=\underset{\theta {\pi }_{ao}}{E}\left[r_{ao}\right]$$

We now define $\pi$ and $r$ by

$$\pi \left(\lambda \right):={\pi }_0$$ $$\pi \left(aoh\right):={\pi }_{ao}\left(h\right)$$

$$r\left(aoh\right):=r_{ao}\left(h\right)$$

Now, observe that, for any $\theta \in {IS}_n$

$$\underset{h\sim \theta \pi }{E}\left[r\right(h\left)\right]=\underset{\begin{array}{c}a\sim {\pi }_0\\ o\sim \theta \left(a\right)\end{array}}{E}\left[\underset{h^{\prime }\sim \left[{\theta }_{ao}\right]{\pi }_{ao}}{E}\left[r_{ao}\left(h^{\prime }\right)\right]\right]=\underset{\begin{array}{c}a\sim {\pi }_0\\ o\sim \theta \left(a\right)\end{array}}{E}\left[r_0(a,j_o\left[{\theta }_{ao}\right])\right]$$

Using the fact that $r_0$ is affine in the second argument, we get

$$\underset{h\sim \theta \pi }{E}\left[r\right(h\left)\right]=\underset{\begin{array}{c}a\sim {\pi }_0\end{array}}{E}\left[r_0(a,\underset{o\sim \theta \left(a\right)}{E}\left[j_o\left[{\theta }_{ao}\right]\right])\right]$$

Moreover, using Definition 6 and the definition of $j_0$, we get

$$\underset{o\sim \theta \left(a\right)}{E}\left[j_o\left[{\theta }_{ao}\right]\right]=\sum _{o\in O}h\left({\theta }_{ao}\right)\underset{o^{\prime }\in O}{⨁}(1_{o^{\prime }=o}{\theta }_{ao},1_{o^{\prime }=o})$$

$$\underset{o\sim \theta \left(a\right)}{E}\left[j_o\left[{\theta }_{ao}\right]\right]=\underset{o^{\prime }\in O}{⨁}(\sum _{o\in O}h\left({\theta }_{ao}\right)1_{o^{\prime }=o}{\theta }_{ao},\sum _{o\in O}h\left({\theta }_{ao}\right)1_{o^{\prime }=o})$$

$$\underset{o\sim \theta \left(a\right)}{E}\left[j_o\left[{\theta }_{ao}\right]\right]=\underset{o^{\prime }\in O}{⨁}(h\left({\theta }_{a{o}^{\prime }}\right){\theta }_{a{o}^{\prime }},h\left({\theta }_{a{o}^{\prime }}\right))=\underset{o^{\prime }\in O}{⨁}{\theta }_{a{o}^{\prime }}={\theta }_a$$

Combining this with the previous identity, we get

$$\underset{h\sim \theta \pi }{E}\left[r\right(h\left)\right]=\underset{\begin{array}{c}a\sim {\pi }_0\end{array}}{E}\left[r_0(a,{\theta }_a)\right]=R\left(\theta \right)■$$

Proposition A.11

Consider some $\alpha \in \Delta N$ and sequences

$${\{{\pi }_k:{(A\times O)}^{\ast }\stackrel{k}{\to }A\bigsqcup \{\perp \left\}\right\}}_{k\in N}$$

$$\{r_k:{(A\times O)}^{\ast }\to [0,1]{\}}_{k\in N}$$

Assume ${\pi }_k$ is a terminable policy for every $k\in N$. Then, there is $\pi$ a terminable policy and $r:{(A\times O)}^{\ast }\to [0,1]$ s.t.

$$R_{\pi r}=\underset{k\sim \alpha }{E}\left[R_{{\pi }_k{r}_k}\right]$$

Proof of Proposition A.11

Define $\pi$ and $r$ by setting, for any $n\in N$ and $ao\in {(A\times O)}^n$

$$\pi \left(ao\right):=\frac{\underset{n\sim \alpha }{E}[{\prod }_{m=0}^{n-1}{\pi }_n\left(a_m\right|a{o}_{:m})\cdot {\pi }_n\left(ao\right)]}{\underset{n\sim \alpha }{E}\left[{\prod }_{m=0}^{n-1}{\pi }_n\left(a_m\right|a{o}_{:m})\right]}$$

$$r\left(ao\right):=\frac{\underset{n\sim \alpha }{E}[{\prod }_{m=0}^{n-1}{\pi }_n\left(a_m\right|a{o}_{:m})\cdot {\pi }_n\left(\perp \right|ao)r_n\left(ao\right)]}{\underset{n\sim \alpha }{E}[{\prod }_{m=0}^{n-1}{\pi }_n\left(a_m\right|a{o}_{:m})\cdot {\pi }_n\left(\perp \right|ao)]}$$

When the denominator vanishes, we can make an arbitrary choice.

Essentially, what we do is sample $n$ from $\alpha$ and then run the “experiment” defined by $({\pi }_n,r_n)$. We have

$$R_{\pi r}\left(\mu \right)=\underset{\mu \pi }{E}\left[r\right]=\underset{n\sim \alpha }{E}\left[\underset{\mu {\pi }_n}{E}\left[r_n\right]\right]=\underset{n\sim \alpha }{E}\left[R_{{\pi }_n{r}_n}\right(\mu \left)\right]■$$

For any $n,m\in N$ s.t. $m\ge n$, we will denote by ${pr}_n^m:{IS}_m\to {IS}_n$ the canonical projection. That is

$${pr}_n^m:={pr}_{m-1}\circ {pr}_{m-2}\dots \circ {pr}_{n+1}\circ {pr}_n$$

Proof of Theorem 1

Direction 1: $R_{\pi r}$ is affine by Proposition 4. To verify it is continuous, consider a sequence ${\{{\mu }_k\in {IS}_{\omega }\}}_{k\in N}$ s.t.${\mu }_{\ast }:={lim}_{k\to \infty }{\mu }_k$ exists. Denote $\Delta r:=supr-infr$, ${\mu }_k^n:={pr}_n^{\omega }\left({\mu }_k\right)$ and ${\mu }_{\ast }^n:={pr}_n^{\omega }\left({\mu }_{\ast }\right)$. For any $n\in N$, we can decompose the expected value into the contribution of histories at length at most $n$ and the contribution of longer histories.

$$|R_{\pi r}\left({\mu }_k\right)-R_{\pi r}\left({\mu }_{\ast }\right)|\le \Delta r(d_{\text{tv}}({\mu }_k^n,{\mu }_{\ast }^n)+\underset{{\mu }_k\pi }{\mathrm{Pr}}[\left|h\right|>n]+\underset{{\mu }_{\ast }\pi }{\mathrm{Pr}}[\left|h\right|>n])$$

${\mu }_k^n$ converges to ${\mu }_{\ast }^n$ as $k$ goes to $\infty$, therefore $d_{\text{tv}}({\mu }_k^n,{\mu }_{\ast }^n)$ converges to 0 and we get

$$\underset{k\to \infty }{limsup}|R_{\pi r}\left({\mu }_k\right)-R_{\pi r}\left({\mu }_{\ast }\right)|\le 2\Delta r\underset{\mu \in {IS}_{\omega }}{sup}\underset{\mu \pi }{\mathrm{Pr}}[\left|h\right|>n]$$

Since this holds for any $n\in N$, we get

$$\underset{k\to \infty }{limsup}|R_{\pi r}\left({\mu }_k\right)-R_{\pi r}\left({\mu }_{\ast }\right)|\le 2\Delta r\underset{n\in N}{inf}\underset{\mu \in {IS}_{\omega }}{sup}\underset{\mu \pi }{\mathrm{Pr}}[\left|h\right|>n]$$

By Proposition A.5, the right hand side vanishes.

Direction 2: Define ${\{{ϵ}_n\in [0,1\left]\right\}}_{n\in N}$ by

$${ϵ}_n:=\underset{\begin{array}{c}\theta \in {IS}_n\\ {\mu }_{1,2}\in {\left({pr}_n^{\omega }\right)}^{-1}\left(\theta \right)\end{array}}{sup}|R\left({\mu }_1\right)-R\left({\mu }_2\right)|$$

By Proposition A.6, ${lim}_{n\to \infty }{ϵ}_n=0$. By Proposition A.8, there is a sequence ${\{{\tilde{R}}_n\in Mor({IS}_n,[0,1\left]\right)\}}_{n\in N}$ s.t. for any $n\in N$

$$\underset{\mu \in {IS}_{\omega }}{sup}\left|R\right(\mu )-{\tilde{R}}_n\left({pr}_n^{\omega }\right(\mu \left)\right)|\le \frac{3}{2}{ϵ}_n$$

It follows that there is a sequence ${\{n_k\in N\}}_{k\in N}$ s.t.$n_{k+1}>n_k$ and

$$\sum _{k=0}^{\infty }\underset{\mu \in {IS}_{\omega }}{sup}|{\tilde{R}}_{n_{k+1}}\left({pr}_{n_{k+1}}^{\omega }\left(\mu \right)\right)-{\tilde{R}}_{n_k}\left({pr}_{n_k}^{\omega }\right(\mu \left)\right)|<1$$

Define $\Delta R_k\in Mor({IS}_{n_{k+1}},[-1,1\left]\right)$ by

$$\Delta R_k\left(\theta \right):={\tilde{R}}_{n_{k+1}}(\theta )-{\tilde{R}}_{n_k}\left({pr}_{n_k}^{n_{k+1}}\right(\theta \left)\right)$$

Denote ${\delta }_k:=sup\left|\Delta R_k\right|$. We can assume without loss of generality that ${\delta }_k>0$ for every $k\in N$ (this can be arranged by choosing appropriate $n_k$, unless for some $m\in N$, $R={pr}_n^{\omega }\circ {\tilde{R}}_m$; but in the latter case, the theorem follows directly from Proposition A.10). By Proposition A.10, for every $k\in N$, there is ${\pi }_{k+1}:{(A\times O)}^{<n_{k+1}}\stackrel{k}{\to }A$ and $r_{k+1}:{(A\times O)}^{n_{k+1}}\to [-1,1]$ s.t.

$$\frac{1}{{\delta }_k}\Delta R_k\left(\theta \right)=\underset{\theta {\pi }_{k+1}}{E}\left[r_{k+1}\right]$$

Also by Proposition A.10, there is ${\pi }_0:{(A\times O)}^{<n_0}\stackrel{k}{\to }A$ and $r_0:{(A\times O)}^{n_0}\to [0,1]$ s.t.

$${\tilde{R}}_{n_0}\left(\theta \right)=\underset{\theta {\pi }_0}{E}\left[r_0\right]$$

By the construction, ${\sum }_{k=0}^{\infty }{\delta }_k<1$, and moreover, denoting $C:=1+{\sum }_{k=0}^{\infty }{\delta }_k$

$$R={pr}_{n_0}^{\omega }\circ {\tilde{R}}_{n_0}+\sum _{k=0}^{\infty }{pr}_{n_{k+1}}^{\omega }\circ \Delta R_k=C(\frac{1}{C}{pr}_{n_0}^{\omega }\circ {\tilde{R}}_{n_0}+\sum _{k=0}^{\infty }\frac{{\delta }_k}{C}\cdot \frac{{pr}_{n_{k+1}}^{\omega }\circ \Delta R_k}{{\delta }_k})$$

By Proposition A.11, there is $\pi$ a terminable policy and $r:{(A\times O)}^{\ast }\to [-2,2]$ (the range of $r_k$ is $[-1,1]$ and $C<2$) s.t. $R_{\pi r}=R$. $■$

Proposition A.12

Consider any $\lambda \in (0,1)$, $n\in N$, $\theta \in {IS}_n$ and ${\mu }_{1,2}\in {\left({pr}_n^{\omega }\right)}^{-1}\left(\theta \right)$. Then,

$$d_{\text{tv}}^{\lambda }({\mu }_1,{\mu }_2)\le {\lambda }^{n+1}$$

Proof of Proposition A.12

By Definition 16,

$$d_{\text{tv}}^{\lambda }({\mu }_1,{\mu }_2)=\underset{m\in N}{sup}{\lambda }^m{d}_{\text{tv}}({pr}_m^{\omega }{\mu }_1,{pr}_m^{\omega }{\mu }_2)$$

For $m\le n$, ${pr}_m^{\omega }{\mu }_1={pr}_m^n\theta ={pr}_m^{\omega }{\mu }_2$, and therefore $d_{\text{tv}}({pr}_m^{\omega }{\mu }_1,{pr}_m^{\omega }{\mu }_2)=0$. For $m>n$, $d_{\text{tv}}({pr}_m^{\omega }{\mu }_1,{pr}_m^{\omega }{\mu }_2)\le 1$ by Definition 15. We get

$$d_{\text{tv}}^{\lambda }({\mu }_1,{\mu }_2)\le \underset{m>n}{sup}{\lambda }^m={\lambda }^{n+1}■$$

Proof of Proposition 5

Define ${\{{ϵ}_n\in [0,1\left]\right\}}_{n\in N}$ by

$${ϵ}_n:=\underset{\begin{array}{c}\theta \in {IS}_n\\ {\mu }_{1,2}\in {\left({pr}_n^{\omega }\right)}^{-1}\left(\theta \right)\end{array}}{sup}|R\left({\mu }_1\right)-R\left({\mu }_2\right)|$$

Let $L\in R$ be the Lipschitz constant of $R$. We have

$${ϵ}_n\le L\underset{\begin{array}{c}\theta \in {IS}_n\\ {\mu }_{1,2}\in {\left({pr}_n^{\omega }\right)}^{-1}\left(\theta \right)\end{array}}{sup}{d}_{\text{tv}}^{\lambda }({\mu }_1,{\mu }_2)$$ By Proposition A.12, we get

$${ϵ}_n\le L{\lambda }^{n+1}$$

Without loss of generality, assume the range of $R$ is contained in $[0,1]$. By Proposition A.8, it follows that there is a sequence ${\{{\tilde{R}}_n\in Mor({IS}_n,[0,1\left]\right)\}}_{n\in N}$ s.t. for any $n\in N$

$$\underset{\mu \in {IS}_{\omega }}{sup}\left|R\right(\mu )-{\tilde{R}}_n\left({pr}_n^{\omega }\right(\mu \left)\right)|\le \frac{3}{2}L{\lambda }^{n+1}$$

It follows that

$$\sum _{n=0}^{\infty }\underset{\mu \in {IS}_{\omega }}{sup}|{\tilde{R}}_{n+1}\left({pr}_{n+1}^{\omega }\left(\mu \right)\right)-{\tilde{R}}_n\left({pr}_n^{\omega }\right(\mu \left)\right)|\le \frac{3}{2}L\sum _{n=0}^{\infty }({\lambda }^{n+2}+{\lambda }^{n+1})$$

$$\sum _{n=0}^{\infty }\underset{\mu \in {IS}_{\omega }}{sup}|{\tilde{R}}_{n+1}\left({pr}_{n+1}^{\omega }\left(\mu \right)\right)-{\tilde{R}}_n\left({pr}_n^{\omega }\right(\mu \left)\right)|\le \frac{3L}{2}\cdot \frac{{\lambda }^2+\lambda }{1-\lambda }$$

Define $\Delta R_n\in Mor({IS}_{n+1},[-1,1\left]\right)$ by

$$\Delta R_n\left(\theta \right):={\tilde{R}}_{n+1}(\theta )-{\tilde{R}}_n\left({pr}_n\right(\theta \left)\right)$$

Denote ${\delta }_n:=sup\left|\Delta R_n\right|$. By Proposition A.10, for every $n\in N$ s.t. ${\delta }_n>0$, there is ${\pi }_{n+1}:{(A\times O)}^{\le n}\stackrel{k}{\to }A$ and $r_{n+1}:{(A\times O)}^{n+1}\to [-1,1]$ s.t.

$$\frac{1}{{\delta }_n}\Delta R_n\left(\theta \right)=\underset{\theta {\pi }_{n+1}}{E}\left[r_{n+1}\right]$$

${\tilde{R}}_0$ is a constant. Define $C\in R^{+}$ by

$$C:=1+\sum _{k=0}^{\infty }{\delta }_k\le 1+\frac{3L}{2}\cdot \frac{{\lambda }^2+\lambda }{1-\lambda }$$

We have

$$R={\tilde{R}}_0+\sum _{n=0}^{\infty }{pr}_{n+1}^{\omega }\circ \Delta R_n=C(\frac{1}{C}{\tilde{R}}_0+\sum _{n=0}^{\infty }\frac{{\delta }_n}{C}\cdot \frac{{pr}_{n+1}^{\omega }\circ \Delta R_n}{{\delta }_n})$$

Here, the terms with ${\delta }_n=0$ are understood to vanish. By Proposition A.11, there is $\pi$ a terminable policy and $r:{(A\times O)}^{\ast }\to [-C,C]$ s.t. $R_{\pi r}=R$. Moreover, looking at the construction in the proof of Proposition A.11, we can see that

$$\underset{h\sim \mu \pi }{E}\left[\left|h\right|\right]=\sum _{n=0}^{\infty }\frac{{\delta }_n}{C}(n+1)\le \sum _{n=0}^{\infty }\frac{3L}{2}({\lambda }^{n+2}+{\lambda }^{n+1})(n+1)<\infty ■$$

In order to prove Theorem 2, we will consider the policy ${\pi }_{\gamma ,T}^{\text{PS}}:S^{\ast }\times S\stackrel{k}{\to }A$ implemented by an algorithm which is PSRL with two modifications:

1. Each episode has random duration, uniformly distributed from $1$ to $2T-1$, for some fixed $T\in N^{+}$.

2. Between any two regular episodes, there is an “interlude” which consists of, performing the reward estimation experiment (${\pi }_{est}$).

The PSRL algorithm assumes choosing $\Pi :H\times S\to A$, a Borel measurable mapping s.t.$\Pi \left(T\right)$ is an optimal policy, i.e.

$${EU}_{T{R}_T}^{\Pi \left(T\right)}\left(\gamma \right)={EU}_{T{R}_T}^{\ast }\left(\gamma \right)$$

As usual, we will consider $(\Omega ,P)$, a probability space governing both the uncertainty about the true hypothesis, the stochastic behavior of the environment and the random sampling inside the algorithm. Let $Y_{\ast }:\Omega \to H$ be a random variable representing the true hypothesis, ${\{Y_k:\Omega \to H\}}_{k\in N}$ be random variables s.t.$Y_n$ represents the hypothesis sampled at episode $k$, ${\{{\Theta }_n:\Omega \to S\}}_{n\in N}$ be s.t.${\Theta }_n$ represents the state at time $n$, ${\{A_n:\Omega \to A\}}_{n\in N}$ be s.t.$A_n$ represents the action taken at time $n$, ${\{N_k:\Omega \to N\}}_{k\in N}$ be s.t.$N_k$ represents the time when the $k$-th episode starts and ${\{M_k:\Omega \to N\}}_{k\in N}$ be s.t.$M_k$ represents the time when the $k$-the interlude starts.

This probability space can be formally defined via recursive equations on the random variables, but this is straightforward and we will omit it.

Proposition A.13

In the setting of Theorem 2, fix $T\in N^{+}$ and $\gamma \in (0,1)$.

Denote $R_k:=R_{Y_k}$, $R_{\ast }:=R_{Y_{\ast }}$, $\Delta R_k:=R_k-R_{\ast }$, $\Delta Y_k:=Y_k-Y_{\ast }$, $E_{\ast k}:=Y_{\ast }\Pi \left(Y_k\right)$, $E_{k\ast }:=Y_k\Pi \left(Y_{\ast }\right)$, $E_{\ast \ast }:=Y_{\ast }\Pi \left(Y_{\ast }\right)$, $\Delta N_k:=M_k-N_k$ and $\Delta M_k:=N_{k+1}-M_k$. Then,

$$R\left(\gamma \right)=\sum _{k=0}^{\infty }E\left[\sum _{n=N_k}^{M_k-1}{\gamma }^n\left(\right(1-\gamma )\Delta R_k\left({\Theta }_n\right)+\gamma \underset{\Delta Y_k}{E}\left[V_{Y_k{R}_k}\right(\gamma \left)\right|{\Theta }_n,A_n])\right]$$ $$+\sum _{k=0}^{\infty }E\left[{\gamma }^{M_k}\underset{E_{k\ast }^{\Delta N_k}-E_{\ast k}^{\Delta N_k}}{E}\left[V_{Y_{\ast }{R}_{\ast }}\right(\gamma \left)\right|{\Theta }_{N_k}]\right]$$ $$+(1-\gamma )\sum _{k=0}^{\infty }E\left[\sum _{n=M_k}^{N_{k+1}-1}{\gamma }^n\underset{E_{\ast \ast }^{n-M_k}-E_{\ast k}^{n-M_k}}{E}\left[R_{\ast }\right|{\Theta }_{M_k}]\right]$$ $$+\sum _{k=0}^{\infty }E\left[{\gamma }^{N_{k+1}}\underset{E_{\ast \ast }^{\Delta M_k}-E_{\ast k}^{\Delta M_k}}{E}\left[V_{Y_{\ast }{R}_{\ast }}\right(\gamma \left)\right|{\Theta }_{M_k}]\right]$$

Proof of Proposition A.13

For any $n\in N$, define ${\Pi }_n:H\times H\times S^{\ast }\times S\stackrel{k}{\to }A$ as follows.

$${\Pi }_n(T_1,T_2,h,s):=\{\begin{array}{c}\Pi (T_1,s)\text{if}\left|h\right|<n\\ \Pi (T_2,s)\text{if}\left|h\right|\ge n\end{array}$$

That is, ${\Pi }_n(T_1,T_2)$ is a policy that follows $\Pi \left(T_1\right)$ for time $n$ and $\Pi \left(T_2\right)$ afterwards.

In the following, we use the shorthand notation

$$V_{\ast }\left(s\right):=V_{Y_{\ast }{R}_{\ast }}(s,\gamma )$$

$$V_k\left(s\right):=V_{Y_k{R}_k}(s,\gamma )$$

$$V_{kl}\left(s\right):=V_{Y_{\ast }{\Pi }_{\Delta N_k-l}(Y_k,Y_{\ast })R_{\ast }}(s,\gamma )$$

It is easy to see that

$$R\left(\gamma \right)=\sum _{k=0}^{\infty }E\left[{\gamma }^{N_k}(V_{\ast }\left({\Theta }_{N_k}\right)-V_{k0}\left({\Theta }_{N_k}\right))\right]$$ $$+(1-\gamma )\sum _{k=0}^{\infty }E\left[\sum _{n=M_k}^{N_{k+1}-1}{\gamma }^n\underset{E_{\ast \ast }^{n-M_k}-E_{\ast k}^{n-M_k}}{E}\left[R_{\ast }\right|{\Theta }_{M_k}]\right]$$ $$+\sum _{k=0}^{\infty }E\left[{\gamma }^{N_{k+1}}\underset{E_{\ast \ast }^{\Delta M_k}-E_{\ast k}^{\Delta M_k}}{E}\left[V_{Y_{\ast }{R}_{\ast }}\right(\gamma \left)\right|{\Theta }_{M_k}]\right]$$

Here, the first term represents the regret incurred during the episodes, whereas the second and third term represent the regret incurred during the interludes (the lost reward and lost value respectively). We will denote the first term $R_0\left(\gamma \right)$ in the following.

By definition, $Y_k$ and $Y_{\ast }$ have the same distribution even when conditioned by the history up to $N_k$. Therefore

$$E\left[V_{\ast }\left({\Theta }_{N_k}\right)\right]=E\left[V_k\left({\Theta }_{N_k}\right)\right]$$

It follows that

$$R_0\left(\gamma \right)=\sum _{k=0}^{\infty }E\left[{\gamma }^{N_k}(V_k\left({\Theta }_{N_k}\right)-V_{k0}\left({\Theta }_{N_k}\right))\right]$$

Denote ${\Theta }_{kl}:={\Theta }_{N_k+l}$ and $\Delta V_{kl}:=V_k\left({\Theta }_{kl}\right)-V_{kl}\left({\Theta }_{kl}\right)$. We now prove by induction on $l\in N$ that, with probability 1

$$l\le \Delta N_k⟹\underset{}{E}\left[\Delta V_{k0}\right|N_k,M_k]=$$ $$\underset{}{E}[\sum _{n=N_k}^{N_k+l-1}{\gamma }^{n-N_k}\left(\right(1-\gamma )\Delta R_k\left({\Theta }_n\right)+\gamma \underset{\Delta Y_k}{E}\left[V_k\right|{\Theta }_n,A_n])+{\gamma }^l\Delta V_{kl}|N_k,M_k]$$

For $l=0$ this is a tautology. For any $l\in N$, the Bellman equation says that

$$V_k\left(s\right)=(1-\gamma )R_k\left(s\right)+\gamma \underset{Y_k\Pi \left(Y_k\right)}{E}\left[V_k\right|s]$$

$$l<\Delta N_k⟹V_{kl}\left(s\right)=(1-\gamma )R_{\ast }\left(s\right)+\gamma \underset{Y_{\ast }\Pi \left(Y_k\right)}{E}\left[V_{k,l+1}\right|s]$$

Denote $E_{kk}:=Y_k\Pi \left(Y_k\right)$. We will also use the notation $E_k\left[X\right]:=\underset{}{E}\left[X\right|N_k,M_k]$. Substituting $s={\Theta }_{kl}$ and subtracting the two identities, we get that, in the subspace of $\Omega$ defined by $l<\Delta N_k$

$$E_k\left[\Delta V_{kl}\right]=E_k\left[\right(1-\gamma )\Delta R\left({\Theta }_{kl}\right)+\gamma (\underset{E_{kk}}{E}\left[V_k\right|{\Theta }_{kl}]-\underset{E_{\ast k}}{E}\left[V_{k,l+1}\right|{\Theta }_{kl}])]$$

Denote $A_{kl}:=A_{N_k+l}$. Since $\Pi \left(Y_k\right)$ is exactly the policy followed by PSRL at time $N_k+l$, we get

$$E_k\left[\Delta V_{kl}\right]=E_k\left[\right(1-\gamma )\Delta R\left({\Theta }_{kl}\right)+\gamma (\underset{Y_k}{E}\left[V_k\right|{\Theta }_{kl},A_{kl}]-\underset{Y_{\ast }}{E}\left[V_{k,l+1}\right|{\Theta }_{kl},A_{kl}])]$$

We now subtract and add $\gamma \underset{Y_{\ast }}{E}\left[V_k\right|{\Theta }_{kl},A_{kl}]$, and use the fact that $Y_{\ast }({\Theta }_{kl},A_{kl})$ is the conditional distribution of ${\Theta }_{k,l+1}$.

$$E_k\left[\Delta V_{kl}\right]=E_k\left[\right(1-\gamma )\Delta R\left({\Theta }_{kl}\right)+\gamma (\underset{\Delta Y_k}{E}\left[V_k\right|{\Theta }_{kl},A_{kl}]+\Delta V_{k,l+1})]$$

Applying this identity to the last term on the right hand side of the induction hypothesis, we prove the induction step. For $l=\Delta N_k$, we get

$$E_k\left[\Delta V_{k0}\right]=\sum _{n=N_k}^{M_k}{\gamma }^{n-N_k}{E}_k\left[\right(1-\gamma )\Delta R_k\left({\Theta }_n\right)+\gamma \underset{\Delta Y_k}{E}\left[V_k\right|{\Theta }_n,A_n]]+$$ $${\gamma }^{\Delta N_k}{E}_k[V_k\left({\Theta }_{M_k}\right)-V_{\ast }\left({\Theta }_{M_k}\right)]$$

Clearly

$$E_k\left[V_k\left({\Theta }_{M_k}\right)\right]=E_k\left[\underset{E_{\ast k}^{\Delta N_k}}{E}\left[V_k\right|{\Theta }_{N_k}]\right]$$

$$E_k\left[V_{\ast }\left({\Theta }_{M_k}\right)\right]=E_k\left[\underset{E_{\ast k}^{\Delta N_k}}{E}\left[V_{\ast }\right|{\Theta }_{N_k}]\right]$$

Using the definition of PSRL, we can exchange and true and sampled hypothesis and get

$$E_k\left[V_k\left({\Theta }_{M_k}\right)\right]=E_k\left[\underset{E_{k\ast }^{\Delta N_k}}{E}\left[V_{\ast }\right|{\Theta }_{N_k}]\right]$$

It follows that

$$E_k\left[\Delta V_{k0}\right]=\sum _{n=N_k}^{M_k}{\gamma }^{n-N_k}{E}_k\left[\right(1-\gamma )\Delta R_k\left({\Theta }_n\right)+\gamma \underset{\Delta Y_k}{E}\left[V_k\right|{\Theta }_n,A_n]]+$$ $${\gamma }^{\Delta N_k}{E}_k\left[\underset{E_{k\ast }^{\Delta N_k}-E_{\ast k}^{\Delta N_k}}{E}\left[V_{\ast }\right|{\Theta }_{N_k}]\right]$$

Applying this to each term in the earlier expression for $R_0\left(\gamma \right)$, we get the desired result. $■$

Proposition A.14

Consider $(\Omega ,P)$ a probability space, ${\{M_k,{\Delta }_k:\Omega \to N\}}_{k\in N}$ random variables and $T\in N^{+}$. Assume that $M_{k+1}-M_k\ge {\Delta }_k$ and the ${\Delta }_k$ are all independent and uniformly distributed between $1$ and $2T-1$. Define the random variable $K_n:\Omega \to N$ by

$$K_n:=min\{k\in N|M_k\ge n\}$$

Then,

$$\underset{}{\mathrm{Pr}}[K_n>\frac{2n}{T}+1]\le \exp (-\frac{n}{4T})$$

Proof of Proposition A.14

Define $M_k^{\prime }:={\sum }_{l=0}^{k=1}{\Delta }_l$. Obviously, $M_k^{\prime }\le M_k$. For any $k\in N$ and $m\in R^{\ge 0}$

$$\underset{}{\mathrm{Pr}}[M_k\le kT-m]\le \underset{}{\mathrm{Pr}}[M_k^{\prime }\le kT-m]$$

Apply Hoeffding’s inequality to the RHS,

$$\underset{}{\mathrm{Pr}}[M_k\le kT-m]\le \exp (-\frac{2m^2}{k(2T-2{)}^2})\le \exp (-\frac{m^2}{2k{T}^2})$$

Taking $m:=\frac{1}{2}kT$, we get

$$\underset{}{\mathrm{Pr}}[M_k\le \frac{kT}{2}]\le \exp (-\frac{{\left(\frac{1}{2}kT\right)}^2}{2k{T}^2})=\exp (-\frac{k}{8})$$

Moreover, by definition of $K_n$, we have, for any $k,n\in N$

$$\underset{}{\mathrm{Pr}}[K_n>k]=\underset{}{\mathrm{Pr}}[M_k<n]$$

It follows that

$$\underset{}{\mathrm{Pr}}[K_{\lceil \frac{1}{2}kT\rceil }>k]=\underset{}{\mathrm{Pr}}[M_k<\lceil \frac{kT}{2}\rceil ]=\underset{}{\mathrm{Pr}}[M_k<\frac{kT}{2}]\le \exp (-\frac{k}{8})$$

Take $k:=\lceil \frac{2n}{T}\rceil$. We get

$$\underset{}{\mathrm{Pr}}[K_n>\frac{2n}{T}+1]\le \underset{}{\mathrm{Pr}}[K_{\lceil \frac{1}{2}\lceil \frac{2n}{T}\rceil T\rceil }>\lceil \frac{2n}{T}\rceil ]\le \exp (-\frac{\lceil \frac{2n}{T}\rceil }{8})\le \exp (-\frac{n}{4T})■$$

Proposition A.15

Consider $\Psi$ be a measurable space, $(\Omega ,P)$ a probability space, ${\{H_n\subseteq P\left(\Omega \right)\}}_{n\in N}$ a filtration, ${\{X_n:\Omega \to \Psi \}}_{n\in N}$ a stochastic process adapted to $H$, ${\{M_k:\Omega \to N\}}_{k\in N}$ stopping times and ${\{f_n:{\Psi }^{n+1}\to [0,1\left]\right\}}_{n\in N}$ measurable functions. Consider also $\gamma \in (0,1)$ and $C\in R^{+}$ and assume that with probability 1

$$\sum _{k=0}^{\infty }{\gamma }^k{f}_k(X_{M_0},X_{M_1}\dots X_{M_k})\le C$$

In addition, consider some $T\in N^{+}$, $T\ge 2$ and assume that for all $k\in N$

$$\underset{}{\mathrm{Pr}}[M_k=n|M_{k-1}]=\{\begin{array}{c}{(2T-1)}^{-1}\text{if}{M}_{k-1}<n<M_{k-1}+2T\\ 0\text{otherwise}\end{array}$$

Here, $M_{-1}$ is understood to identically equal $-1$.

Finally, assume that, conditional on $M_k\ge n$, $M_k$ and $X_n$ are independent. Define the $H_n$-measurable random variable $K_n:\Omega \to N$ by

$$K_n:=min\{k\in N|M_k\ge n\}$$

Then,

$$\sum _{n=0}^{\infty }{\gamma }^{\frac{2n}{T}+1}E\left[f_{K_n}(X_{M_0},X_{M_1}\dots X_{M_{K_n-1}},X_n)\right]\le 2CT+\frac{1}{1-\exp (-\frac{1}{4T})}$$

Proof of Proposition A.15

We have, with probability 1

$$\sum _{n=0}^{\infty }{1}_{M_{K_n}=n}{\gamma }^{K_n}{f}_{K_n}(X_{M_0},X_{M_1}\dots X_{M_{K_n-1}},X_n)\le C$$

Taking expected value

$$\sum _{n=0}^{\infty }E\left[1_{M_{K_n}=n}{\gamma }^{K_n}{f}_{K_n}(X_{M_0},X_{M_1}\dots X_{M_{K_n-1}},X_n)\right]\le C$$

Denote by $K_n^{♯}$ the joint random variables $K_n$ and $M_0,M_1\dots M_{K_n-1}$. Our assumptions imply that, conditional on $K_n^{♯}$, the factor $1_{M_{K_n}=n}$ is independent of the rest of the expression inside the expected value. It follows that

$$\sum _{n=0}^{\infty }E\left[\underset{}{\mathrm{Pr}}[M_{K_n}=n|K_n^{♯}]{\gamma }^{K_n}\underset{}{E}\left[f_{K_n}(X_{M_0},X_{M_1}\dots X_{M_{K_n-1}},X_n)\right|K_n^{♯}]\right]\le C$$

Clearly

$$\underset{}{\mathrm{Pr}}[M_{K_n}=n|K_n^{♯}]=\frac{1}{2T-n+M_{K_n-1}}\ge \frac{1}{2T}$$

We get

$$\sum _{n=0}^{\infty }E\left[\frac{1}{2T}{\gamma }^{K_n}{f}_{K_n}(X_{M_0},X_{M_1}\dots X_{M_{K_n-1}},X_n)\right]\le C$$

$$\sum _{n=0}^{\infty }E\left[{\gamma }^{K_n}{f}_{K_n}(X_{M_0},X_{M_1}\dots X_{M_{K_n-1}},X_n)\right]\le 2CT$$

Using Proposition A.14, we get

$$\sum _{n=0}^{\infty }(E\left[{\gamma }^{\frac{2n}{T}+1}{f}_{K_n}(X_{M_0},X_{M_1}\dots X_{M_{K_n-1}},X_n)\right]-\exp (-\frac{n}{4T}))\le 2CT$$

$$\sum _{n=0}^{\infty }{\gamma }^{\frac{2n}{T}+1}E\left[f_{K_n}(X_{M_0},X_{M_1}\dots X_{M_{K_n-1}},X_n)\right]\le 2CT+\sum _{n=0}^{\infty }\exp (-\frac{n}{4T})$$

$$\sum _{n=0}^{\infty }{\gamma }^{\frac{2n}{T}+1}E\left[f_{K_n}(X_{M_0},X_{M_1}\dots X_{M_{K_n-1}},X_n)\right]\le 2CT+\frac{1}{1-\exp (-\frac{1}{4T})}■$$

Proposition A.16

Consider $(\Omega ,P)$ a probability space, $T\in N^{+}$ and ${\{N_k,{\Delta }_k:\Omega \to N\}}_{k\in N}$ random variables s.t.$N_{k+1}-N_k\ge {\Delta }_k$ and the ${\Delta }_k$ are all independent and uniformly distributed between $1$ and $2T-1$. Consider also $\gamma \in (0,1)$. Then, for any $k\in N$

$$E\left[{\gamma }^{N_k}\right]\le {(1-T{\gamma }^{2T-2}(1-\gamma \left)\right)}^k$$

In particular,

$$\sum _{k=0}^{\infty }E\left[{\gamma }^{N_k}\right]\le \frac{1}{T{\gamma }^{2T-2}(1-\gamma )}$$

Proof of Proposition A.16

For any $n\in N$, we have

$$\frac{1-{\gamma }^n}{1-\gamma }=\sum _{m=0}^{n-1}{\gamma }^m$$

$$1-{\gamma }^n=(1-\gamma )\sum _{m=0}^{n-1}{\gamma }^m\ge n(1-\gamma ){\gamma }^{n-1}$$

$${\gamma }^n\le 1-n(1-\gamma ){\gamma }^{n-1}$$

Therefore, since ${\Delta }_0$ is uniformly distributed between $1$ and $2T-1$,

$$E\left[{\gamma }^{{\Delta }_0}\right]=\frac{1}{2T-1}\sum _{n=1}^{2T-1}{\gamma }^n\le \frac{1}{2T-1}\sum _{n=1}^{2T-1}(1-n(1-\gamma \left){\gamma }^{n-1}\right)$$

$$E\left[{\gamma }^{{\Delta }_0}\right]\le \frac{1}{2T-1}\sum _{n=1}^{2T-1}(1-n(1-\gamma \left){\gamma }^{2T-2}\right)=1-T(1-\gamma ){\gamma }^{2T-2}$$

Also, for any $k\in N$

$$N_k\ge \sum _{l=0}^{k-1}{\Delta }_l$$

$${\gamma }^{N_k}\le {\gamma }^{{\sum }_{l=0}^{k-1}{\Delta }_l}=\prod _{l=0}^{k-1}{\gamma }^{{\Delta }_l}$$

$$E\left[{\gamma }^{N_k}\right]\le E\left[\prod _{l=0}^{k-1}{\gamma }^{{\Delta }_l}\right]=\prod _{l=0}^{k-1}E\left[{\gamma }^{{\Delta }_l}\right]=E{\left[{\gamma }^{{\Delta }_0}\right]}^k$$

Here, we used that the ${\Delta }_l$ are independent and equally distributed. Substituting the expression for $E\left[{\Delta }_0\right]$, we get the desired result. $■$

Proposition A.17

In the setting of Proposition A.16, consider some $\delta \in R^{+}$. Denote

$$\alpha :=1-T{\gamma }^{2T-2}(1-\gamma )$$

Assume $\alpha >0$. Then,

$$\sum _{k=0}^{\infty }min(E\left[{\gamma }^{N_k}\right],\delta )\le (\lceil \frac{\ln \delta }{\ln \alpha }\rceil +\frac{1}{1-\alpha })\delta$$

Proof of Proposition A.17

By Proposition A.16

$$\sum _{k=0}^{\infty }min(E\left[{\gamma }^{N_k}\right],\delta )\le \sum _{k=0}^{\infty }min({\alpha }^k,\delta )$$

$$\sum _{k=0}^{\infty }min(E\left[{\gamma }^{N_k}\right],\delta )\le \sum _{k=0}^{\lceil \frac{\ln \delta }{\ln \alpha }\rceil -1}min({\alpha }^k,\delta )+\sum _{k=\lceil \frac{\ln \delta }{\ln \alpha }\rceil }^{\infty }min({\alpha }^k,\delta )$$

In the second term, we have

$${\alpha }^k\le {\alpha }^{\lceil \frac{\ln \delta }{\ln \alpha }\rceil }\le {\alpha }^{\frac{\ln \delta }{\ln \alpha }}=e^{\ln \alpha \frac{\ln \delta }{\ln \alpha }}=e^{\ln \delta }=\delta$$

We get

$$\sum _{k=0}^{\infty }min(E\left[{\gamma }^{N_k}\right],\delta )\le \sum _{k=0}^{\lceil \frac{\ln \delta }{\ln \alpha }\rceil -1}\delta +\sum _{k=\lceil \frac{\ln \delta }{\ln \alpha }\rceil }^{\infty }{\alpha }^k=\lceil \frac{\ln \delta }{\ln \alpha }\rceil \delta +\frac{{\alpha }^{\lceil \frac{\ln \delta }{\ln \alpha }\rceil }}{1-\alpha }$$

We’ve already seen that ${\alpha }^{\lceil \frac{\ln \delta }{\ln \alpha }\rceil }\le \delta$, and therefore

$$\sum _{k=0}^{\infty }min(E\left[{\gamma }^{N_k}\right],\delta )\le \lceil \frac{\ln \delta }{\ln \alpha }\rceil \delta +\frac{\delta }{1-\alpha }=(\lceil \frac{\ln \delta }{\ln \alpha }\rceil +\frac{1}{1-\alpha })\delta ■$$

We will use the notations of Definitions B.1 and B.2 (see Appendix).

The following is a simple generalization of “Lemma 1” in Osband and Van Roy 2014 and the proof is essentially the same.

Proposition A.18

Consider a set $X$, a finite-dimensional inner product space $Y$ and some $F\subseteq \{X\to Y\}$. Consider also some $x\in X^{\omega }$, $y\in Y^{\omega }$, $T\in N$, $\theta \in R^{+}$, an increasing sequence ${\{N_k\in N\}}_{k\in N}$ and a nondecreasing sequence ${\{{\beta }_k\in R^{+}\}}_{k\in N}$. Suppose that for any $k\in N$, $N_{k+1}\le N_k+T$. For any $k\in N$, define $F^k$ by

$$F^k:={CS}^F[{xy}_{:N_k},{\beta }_k^{-1}]$$

Denote $D:={\dim }_{RVO}F$. Then, for any $K\in N$

$$\left|\left\{(k\in [K],n\in N)\right|N_k\le n<N_{k+1},W^{F^k}\left(x_n\right)>\theta \}\right|\le (D+1)(\frac{4{\beta }_{K-1}}{{\theta }^2}+T)$$

Here, ${\beta }_{-1}$ is understood to mean $0$.

Proof of Proposition A.18

Let $A\subset N\times N$ be the set

$$A:=\left\{(k\in [K],n\in N)\right|N_k\le n<N_{k+1},W^{F^k}\left(x_n\right)>\theta \}$$

Let $A^{\prime }\subset N$ be the set

$$A^{\prime }:=\{n\in N|\exists k\in \left[K\right]:(k,n)\in A\}$$

For each $i\in \left[\left|A\right|\right]$, we define $(k_i,n_i)\in A$ recursively by

$$n_0:=min{A}^{\prime }$$ $$n_{i+1}:=min\{n\in A^{\prime }|n>n_i\}$$

Denote $D:={\dim }_{RVO}F$ and let $L:=\lfloor \frac{\left|A\right|}{D+1}\rfloor$. Given any $n\in N^{\ast }$, the notation $x_n$ will refer to the element of $X^{\ast }$ s.t.$\left|x_n\right|=\left|n\right|$ and for any $i\in \left[\left|n\right|\right]$, ${\left(x_n\right)}_i:=x_{n_i}$. We define $j\in \left[\left|A\right|\right]$ and ${\{m_{li}\in N^{\ast }\}}_{l\in \left[L\right],i\in [j+1]}$ by recursion over $i$.

For $i=0$, we set $m_{l0}:=\lambda$. For any $i$, we consider whether there is $l\in \left[L\right]$ s.t.$x_{n_i}$ is $(F,\theta )$-independent of $x_{m_{li}}$. If there is such $l$, we set $m_{l,i+1}:=m_{li}{n}_i$ and for any $l^{\prime }\in \left[L\right]\setminus l$, $m_{l^{\prime },i+1}:=m_{li}$. If there is no such $l$, we set $j:=i$. The latter situation must occur for some $i\in \left[\left|A\right|\right]$, since otherwise we would get

$$\sum _{l\in \left[L\right]}\left|m_{l\left|A\right|}\right|=\left|A\right|$$

That would imply that there is $l\in \left[L\right]$ s.t.

$$\left|m_{l\left|A\right|}\right|\ge \frac{\left|A\right|}{L}=\frac{\left|A\right|}{\lfloor \frac{\left|A\right|}{D+1}\rfloor }\ge \frac{\left|A\right|}{\left(\frac{\left|A\right|}{D+1}\right)}=D+1$$

This is impossible since, by construction, each element of the sequence $x_{m_{l\left|A\right|}}$ is $(F,\theta )$-independent of the preceding subsequence, whereas, by definition of $D$, it is the maximal length of such a sequence.

Since $(k_j,n_j)\in A$, $W^{F^{k_j}}\left(x_{n_j}\right)>\theta$. Therefore, there are $f,\tilde{f}\in F^{k_j}$ s.t.

$$\Vert f\left(x_{n_j}\right)-\tilde{f}\left(x_{n_j}\right)\Vert >\theta$$

By construction of $j$ and $m$, For each $l\in \left[L\right]$, $x_{n_j}$ is $(F,\theta )$-dependent of $x_{m_{lj}}$. Therefore,

$$\sum _{i=0}^{\left|m_{lj}\right|-1}{\Vert f\left(x_{m_{lji}}\right)-\tilde{f}\left(x_{m_{lji}}\right)\Vert }^2>{\theta }^2$$

Define $J\subseteq \left[L\right]$ by

$$J:=\{l\in [L\left]\right|\forall i\in \left[\left|m_{lj}\right|\right]:m_{lji}<N_{k_j}\}$$

$$\sum _{l\in J}\sum _{i=0}^{\left|m_{lj}\right|-1}{\Vert f\left(x_{m_{lji}}\right)-\tilde{f}\left(x_{m_{lji}}\right)\Vert }^2\ge \left|J\right|{\theta }^2$$

By construction, the sequences $m_{lj}$ for all values of $l$ together are a collection of distinct elements of $\left[n_j\right]$. Therefore, $\left|J\right|\ge L-(n_j-N_{k_j})\ge L-T+1$. It follows that

$$\sum _{n=0}^{N_{k_j}-1}{\Vert f\left(x_n\right)-\tilde{f}\left(x_n\right)\Vert }^2\ge (L-T+1){\theta }^2$$

$$\sqrt{\sum _{n=0}^{N_{k_j}-1}{\Vert f\left(x_n\right)-\tilde{f}\left(x_n\right)\Vert }^2}\ge \theta \sqrt{max(L-T+1,0)}$$

Denote $f^{\ast }:={LS}^F\left[{xy}_{:N_{k_j}}\right]$.

$$\sqrt{\sum _{n=0}^{N_{k_j}-1}{\parallel f\left(x_n\right)-f^{\ast }\left(x_n\right)\parallel }^2}+\sqrt{\sum _{n=0}^{N_{k_j}-1}{\Vert \tilde{f}\left(x_n\right)-f^{\ast }\left(x_n\right)\Vert }^2}\ge \theta \sqrt{max(L-T+1,0)}$$

Since $f,\tilde{f}\in F^{k_j}$, by the definition of $F^{k_j}$ each of the two terms on the RHS is at most $\sqrt{{\beta }_{k_j}}\le \sqrt{{\beta }_{K-1}}$ and we get

$$2\sqrt{{\beta }_{K-1}}\ge \theta \sqrt{max(L-T+1,0)}$$

$$4{\beta }_{K-1}\ge {\theta }^2(L+1-T)$$

$$4{\beta }_{K-1}\ge {\theta }^2(\frac{\left|A\right|}{D+1}-T)$$

$$\left|A\right|\le (D+1)(\frac{4{\beta }_{K-1}}{{\theta }^2}+T)■$$

Proposition A.19

Consider $\alpha \in N$ and $f:R^{+}\to R^{+}$ non-decreasing. Define $g:R\to R$ by $g\left(x\right):=\ln f\left(e^x\right)$, and assume $g$ is Lipschitz continuous with constant $\alpha$. In other words, for any $t\in R^{+}$ and $\lambda \in [1,\infty )$, we have $f\left(\lambda t\right)\le {\lambda }^{\alpha }f\left(t\right)$. Let $L$ denote the Laplace transform operator. Then,

$$L\left[f\right]\left(s\right)\le \frac{1-e^{-1}+\alpha !}{s}f\left(\frac{1}{s}\right)$$

Proof of Proposition A.19

$$L\left[f\right]\left(s\right)={\int }_0^{\infty }{e}^{-st}f\left(t\right)dt={\int }_0^{\frac{1}{s}}{e}^{-st}f\left(t\right)dt+{\int }_{\frac{1}{s}}^{\infty }{e}^{-st}f\left(t\right)dt$$

For the first term, we will use that $f$ is non-decreasing, and for the second term, we will use that $g$ is Lipschitz continuous with constant $\alpha$.

$$L\left[f\right]\left(s\right)\le {\int }_0^{\frac{1}{s}}{e}^{-st}f\left(\frac{1}{s}\right)dt+{\int }_{\frac{1}{s}}^{\infty }{e}^{-st}f\left(\frac{1}{s}\right)\cdot {\left(ts\right)}^{\alpha }dt$$

$$L\left[f\right]\left(s\right)\le ({\int }_0^{\frac{1}{s}}{e}^{-st}dt+s^{\alpha }{\int }_{\frac{1}{s}}^{\infty }{e}^{-st}{t}^{\alpha }dt)f\left(\frac{1}{s}\right)$$

$$L\left[f\right]\left(s\right)\le ({\int }_0^{\frac{1}{s}}{e}^{-st}dt+s^{\alpha }{\int }_0^{\infty }{e}^{-st}{t}^{\alpha }dt)f\left(\frac{1}{s}\right)$$

$$L\left[f\right]\left(s\right)\le (\frac{1-e^{-1}}{s}+s^{\alpha }\cdot \alpha !s^{-\alpha -1})f\left(\frac{1}{s}\right)=\frac{1-e^{-1}+\alpha !}{s}f\left(\frac{1}{s}\right)■$$

Proposition A.20

There is some $C_{A.20}\in R^{+}$ s.t. the following holds.

Consider a set $X$, an inner product space $Y$ and some $F\subseteq \{X\to Y\}$. Consider also some $x\in X^{\omega }$, $y\in Y^{\omega }$, $T\in N^{+}$, $\gamma \in (0,1)$, $\theta \in R^{+}$, ${\eta }_0,{\eta }_1\in R^{+}$, $\delta \in (0,1)$ and an increasing sequence ${\{N_k\in N\}}_{k\in N}$. Suppose that $N_0=0$, for any $k\in N$, $N_{k+1}\le N_k+T$, and ${\gamma }^T>\frac{1}{2}$. Denote

$$\beta \left(t\right):={\eta }_0+{\eta }_{1}t\ln \frac{et}{\delta }$$

For any $k\in N$, define $F^k$ by

$$F^k:={CS}^F[{xy}_{:N_k},\beta {(N_k+1)}^{-1}]$$

Denote $D:={\dim }_{RVO}F$. Then,

$$\sum _{k=0}^{\infty }\sum _{n=N_k}^{N_{k+1}-1}{\gamma }^{kT}{1}_{W^{F^k}\left(x_n\right)>\theta }\le C_{A.20}D(\frac{1}{{\theta }^2}\beta \left(\frac{1}{1-\gamma }\right)+T)$$

Proof of Proposition A.20

By Proposition A.18, for any $K\in N$

$$\sum _{k=0}^{K-1}\sum _{n=N_k}^{N_{k+1}-1}{1}_{W^{F^k}\left(x_n\right)>\theta }\le (D+1)(\frac{4\beta (N_{K-1}+1)}{{\theta }^2}+T)$$

Here, $N_{-1}$ is understood to mean $0$. Observing that $N_k\le kT$, we get

$$\sum _{k=0}^{K-1}\sum _{n=N_k}^{N_{k+1}-1}{1}_{W^{F^k}\left(x_n\right)>\theta }\le (D+1)(\frac{4\beta (KT+1)}{{\theta }^2}+T)$$

Multiplying the inequality by ${\gamma }^{KT}$ and summing over $K$, we get

$$\sum _{k=0}^{\infty }\left(\sum _{K=k+1}^{\infty }{\gamma }^{KT}\right)\sum _{n=N_k}^{N_{k+1}-1}{1}_{W^{F^k}\left(x_n\right)>\theta }\le (D+1)\sum _{K=0}^{\infty }{\gamma }^{KT}(\frac{4\beta (KT+1)}{{\theta }^2}+T)$$

On the left hand side, we sum the geometric series. On the right hand side, we use the observation that

$${\gamma }^{KT}(\frac{4\beta (KT+1)}{{\theta }^2}+T)\le \frac{1}{T}{\int }_0^T{\gamma }^{KT+t-T}(\frac{4\beta (KT+t+1)}{{\theta }^2}+T)dt$$

$${\gamma }^{KT}(\frac{4\beta (KT+1)}{{\theta }^2}+T)\le \frac{1}{T{\gamma }^T}{\int }_0^T{\gamma }^{KT+t}(\frac{4\beta (KT+t+1)}{{\theta }^2}+T)dt$$

Here, we used that $\beta \left(t\right)$ is an increasing function for $t\ge 1$. We get

$$\sum _{k=0}^{\infty }\frac{{\gamma }^{(k+1)T}}{1-{\gamma }^T}\sum _{n=N_k}^{N_{k+1}-1}{1}_{W^{F^k}\left(x_n\right)>\theta }\le \frac{D+1}{T{\gamma }^T}{\int }_0^{\infty }{\gamma }^t(\frac{4\beta (t+1)}{{\theta }^2}+T)dt$$

$$\frac{{\gamma }^T}{1-{\gamma }^T}\sum _{k=0}^{\infty }{\gamma }^{kT}\sum _{n=N_k}^{N_{k+1}-1}{1}_{W^{F^k}\left(x_n\right)>\theta }\le \frac{D+1}{T{\gamma }^T}{L}_t[\frac{4\beta (t+1)}{{\theta }^2}+T]\left(\ln \frac{1}{\gamma }\right)$$

It is easy to see that Proposition A.19 is applicable to the RHS for $\alpha =2$. We get,

$$\frac{{\gamma }^T}{1-{\gamma }^T}\sum _{k=0}^{\infty }{\gamma }^{kT}\sum _{n=N_k}^{N_{k+1}-1}{1}_{W^{F^k}\left(x_n\right)>\theta }\le \frac{D+1}{T{\gamma }^T}\cdot \frac{3-e^{-1}}{\ln \frac{1}{\gamma }}(\frac{4\beta (\frac{1}{\ln \frac{1}{\gamma }}+1)}{{\theta }^2}+T)$$

Using the condition ${\gamma }^T>\frac{1}{2}$ and absorbing $O\left(1\right)$ factors into the definition of $C_{\text{A.20}}$, we get

$$\sum _{k=0}^{\infty }{\gamma }^{kT}\sum _{n=N_k}^{N_{k+1}-1}{1}_{W^{F^k}\left(x_n\right)>\theta }\le C_{\text{A.20}}D(\frac{1}{{\theta }^2}\beta \left(\frac{1}{1-\gamma }\right)+T)■$$

Proposition A.21

There is some $C_{A.21}\in R^{+}$ s.t. the following holds. In the setting of Proposition A.20, assume that for any $x\in X$ and $f\in F$, $\parallel f\left(x\right)\parallel \le 1$. Then,

$$\sum _{k=0}^{\infty }\sum _{n=N_k}^{N_{k+1}-1}{\gamma }^{kT}{W}^{F^k}\left(x_n\right)\le C_{\text{A.21}}(DT+\sqrt{D\beta \left(\frac{1}{1-\gamma }\right)\frac{1}{1-\gamma }})$$

Proof of Proposition A.21

Due to the assumption $\parallel f\left(x\right)\parallel \le 1$, we have $W^{F^k}\left(x\right)\le 2$. For any $t\in R^{+}$, we have

$$W^{F^k}\left(x_n\right)={\int }_0^2{1}_{W^{F^k}\left(x_n\right)>\theta }d\theta \le t+{\int }_t^2{1}_{W^{F^k}\left(x_n\right)>\theta }d\theta$$

$$\sum _{k=0}^{\infty }\sum _{n=N_k}^{N_{k+1}-1}{\gamma }^{kT}{W}^{F^k}\left(x_n\right)\le \frac{tT}{1-{\gamma }^T}+{\int }_t^2\sum _{k=0}^{\infty }\sum _{n=N_k}^{N_{k+1}-1}{\gamma }^{kT}{1}_{W^{F^k}\left(x_n\right)>\theta }d\theta$$

Applying Proposition A.20 to integrand on the RHS

$$\sum _{k=0}^{\infty }\sum _{n=N_k}^{N_{k+1}-1}{\gamma }^{kT}{W}^{F^k}\left(x_n\right)\le \frac{tT}{1-{\gamma }^T}+C_{\text{A.20}}D{\int }_t^2(\frac{1}{{\theta }^2}\beta \left(\frac{1}{1-\gamma }\right)+T)d\theta$$

Evaluating the integral and dropping some negative terms on the right hand side, we get

$$\sum _{k=0}^{\infty }\sum _{n=N_k}^{N_{k+1}-1}{\gamma }^{kT}{W}^{F^k}\left(x_n\right)\le \frac{tT}{1-{\gamma }^T}+C_{\text{A.20}}D(\frac{1}{t}\beta \left(\frac{1}{1-\gamma }\right)+2T)$$

We now set $t$ to be

$$t:=\sqrt{D\beta \left(\frac{1}{1-\gamma }\right)\cdot (1-\gamma )}$$

For an appropriate choice of $C_{\text{A.21}}$, and using the assumption ${\gamma }^T>\frac{1}{2}$, it follows that

$$\sum _{k=0}^{\infty }\sum _{n=N_k}^{N_{k+1}-1}{\gamma }^{kT}{W}^{F^k}\left(x_n\right)\le C_{\text{A.21}}(DT+\sqrt{D\beta \left(\frac{1}{1-\gamma }\right)\frac{1}{1-\gamma }})■$$

Proof of Theorem 2

We take ${\pi }_{\gamma }^{†}:={\pi }_{\gamma ,T}^{\text{PS}}$ where $T\in N^{+}$ will be specified later. By Proposition A.13

$$R\left(\gamma \right)\le \sum _{k=0}^{\infty }E\left[\sum _{n=N_k}^{M_k-1}{\gamma }^n\left(\right(1-\gamma )\left|\Delta R_k\left({\Theta }_n\right)\right|+\gamma \left|\underset{\Delta Y_k}{E}\left[V_{Y_k{R}_k}\right(\gamma \left)\right|{\Theta }_n,A_n]\right|)\right]$$ $$+\sum _{k=0}^{\infty }E\left[{\gamma }^{M_k}\left|\underset{E_{k\ast }^{\Delta N_k}-E_{\ast k}^{\Delta N_k}}{E}\left[V_{Y_{\ast }{R}_{\ast }}\right(\gamma \left)\right|{\Theta }_{N_k}]\right|\right]$$ $$+(1-\gamma )\sum _{k=0}^{\infty }E\left[\sum _{n=M_k}^{N_{k+1}-1}{\gamma }^n\left|\underset{E_{\ast \ast }^{n-M_k}-E_{\ast k}^{n-M_k}}{E}\left[R_{\ast }\right|{\Theta }_{M_k}]\right|\right]$$ $$+\sum _{k=0}^{\infty }E\left[{\gamma }^{N_{k+1}}\left|\underset{E_{\ast \ast }^{\Delta M_k}-E_{\ast k}^{\Delta M_k}}{E}\left[V_{Y_{\ast }{R}_{\ast }}\right(\gamma \left)\right|{\Theta }_{M_k}]\right|\right]$$

We will use the notation

$$\Delta V\left(\gamma \right):=\underset{T\in H}{max}(\underset{s\in S}{max}{V}_{T{R}_T}(s,\gamma )-\underset{s\in S}{min}{V}_{T{R}_T}(s,\gamma ))$$

We will also use the notation $d_{\text{tv}}(\mu -\nu ):=d_{\text{tv}}(\mu ,\nu )$.

It follows that

$$R\left(\gamma \right)\le \sum _{k=0}^{\infty }E\left[\sum _{n=N_k}^{M_k-1}{\gamma }^n\left(\right(1-\gamma )\left|\Delta R_k\left({\Theta }_n\right)\right|+\gamma \Delta V(\gamma \left)d_{\text{tv}}\left(\Delta Y_k({\Theta }_n,A_n)\right)\right)\right]$$ $$+\Delta V\left(\gamma \right)\sum _{k=0}^{\infty }E\left[{\gamma }^{M_k}\right]+(1-\gamma )\sum _{k=0}^{\infty }E\left[\sum _{n=M_k}^{N_{k+1}-1}{\gamma }^n\right]+\Delta V\left(\gamma \right)\sum _{k=0}^{\infty }E\left[{\gamma }^{N_{k+1}}\right]$$

Denote $R_0\left(\gamma \right)$ the first term on the RHS and $R_1\left(\gamma \right)$ the sum of the others terms. We have

$$R\left(\gamma \right)\le R_0\left(\gamma \right)+R_1\left(\gamma \right)$$

First, we analyze $R_1$. In the second term, we have ${\gamma }^n\le {\gamma }^{M_k}$, leading to

$$E\left[\sum _{n=M_k}^{N_{k+1}-1}{\gamma }^n\right]\le E\left[\Delta M_k{\gamma }^{M_k}\right]=E\left[\underset{}{E}\left[\Delta M_k\right|M_k]{\gamma }^{M_k}\right]\le t_{est}E\left[{\gamma }^{M_k}\right]$$

We get

$$R_1\left(\gamma \right)\le \Delta V\left(\gamma \right)\sum _{k=0}^{\infty }E\left[{\gamma }^{M_k}\right]+t_{est}(1-\gamma )\sum _{k=0}^{\infty }E\left[{\gamma }^{M_k}\right]+\Delta V\left(\gamma \right)\sum _{k=0}^{\infty }E\left[{\gamma }^{N_{k+1}}\right]$$

Applying Proposition A.16 to each term, we get

$$R_1\left(\gamma \right)\le \frac{2\Delta V\left(\gamma \right)+t_{est}(1-\gamma )}{{\gamma }^{2T-2}(1-\gamma )T}$$

Now, we analyze $R_0$. Define ${\Theta }_M^r\in {(S\times R)}^{\omega }$ by

$${\Theta }_{Mk}^r:=({\Theta }_{M_k},r\left(\Theta A_{M_k:N_{k+1}}{\Theta }_{N_{k+1}}\right))$$

That is, ${\Theta }_M^r$ is the history of reward estimation experiments. For any $i\in N$, let $L_i$ be the stopping time defined recursively by

$$L_0:=0$$ $$L_{i+1}:=min\{l\in N|l>L_i,\exists k\in N:N_k\le l<M_k\}$$

That is, $L$ are time indices that traverse the “interior” of the episodes only. Define $\Theta A_L\in {(S\times A)}^{\omega }$ by

$$\Theta A_{Li}:={\Theta }_{L_i}{A}_{L_i}$$

We apply Proposition B.1 (see Appendix) with $\delta :=\frac{1}{2}(1-\gamma {)}^2$ and $ϵ:=(1-\gamma {)}^2$, to each of the two terms in $R_0\left(\gamma \right)$:

$$\mathrm{Pr}[R_{\ast }\in \bigcap _{k=0}^{\infty }{CS}^{H_R}[{\Theta }_{M:k}^r,{\beta }_R(k+1{)}^{-1}]]\ge 1-\frac{1}{2}(1-\gamma {)}^2$$ $$\mathrm{Pr}[Y_{\ast }\in \bigcap _{i=0}^{\infty }{CS}^H[\Theta A_{L:i}{\Theta }_{L_i},{\beta }_T(i+1{)}^{-1}]]\ge 1-\frac{1}{2}(1-\gamma {)}^2$$

Here, ${\beta }_R$ and ${\beta }_T$ correspond to $\beta$ in Proposition B.1.

We also define $N_k^{\prime }$ by the condition $L_{N_k^{\prime }}=N_k$. Since the hypotheses $Y_k$ is sampled from the posterior, for any $k\in N$ we also have

$$\mathrm{Pr}[R_k\in {CS}^{H_R}[{\Theta }_{M:k}^r,{\beta }_R(k+1{)}^{-1}]]\ge 1-\frac{1}{2}(1-\gamma {)}^2$$ $$\mathrm{Pr}[Y_k\in {CS}^H[\Theta A_{L:N_k^{\prime }}{\Theta }_{N_k},{\beta }_T{(N_k^{\prime }+1)}^{-1}]]\ge 1-\frac{1}{2}(1-\gamma {)}^2$$

$$\mathrm{Pr}[R_{\ast },R_k\in {CS}^{H_R}[{\Theta }_{M:k}^r,{\beta }_R(k+1{)}^{-1}]]\ge 1-(1-\gamma {)}^2$$ $$\mathrm{Pr}[Y_{\ast },Y_k\in {CS}^H[\Theta A_{L:N_k^{\prime }}{\Theta }_{N_k},{\beta }_T{(N_k^{\prime }+1)}^{-1}]]\ge 1-(1-\gamma {)}^2$$

Denote

$$G_R^k:=\{R_{\ast },R_k\in {CS}^{H_R}[{\Theta }_{M:k}^r,{\beta }_R(k+1{)}^{-1}]\}\subseteq \Omega$$ $$G_T^k:=\{Y_{\ast },Y_k\in {CS}^H[\Theta A_{L:N_k^{\prime }}{\Theta }_{N_k},{\beta }_T{(N_k^{\prime }+1)}^{-1}]\}\subseteq \Omega$$

Define $R_R\left(\gamma \right)$ and $R_T\left(\gamma \right)$ by

$$R_R\left(\gamma \right):=(1-\gamma )\sum _{k=0}^{\infty }E\left[\sum _{n=N_k}^{M_k-1}{\gamma }^n\left|\Delta R_k\left({\Theta }_n\right)\right|\right]$$ $$R_T\left(\gamma \right):=\Delta V\left(\gamma \right)\sum _{k=0}^{\infty }E\left[\sum _{n=N_k}^{M_k-1}{\gamma }^{n+1}{d}_{\text{tv}}\left(\Delta Y_k({\Theta }_n,A_n)\right)\right]$$

We have

$$R_0\left(\gamma \right)=R_R\left(\gamma \right)+R_T\left(\gamma \right)$$

We split $R_R$ into the $G_R^k$ and $G_R^{k\complement }$ contributions

$$R_R\left(\gamma \right)=(1-\gamma )\sum _{k=0}^{\infty }(E[\sum _{n=N_k}^{M_k-1}{\gamma }^n\left|\Delta R_k\left({\Theta }_n\right)\right|;G_R^k]+$$ $$E[\sum _{n=N_k}^{M_k-1}{\gamma }^n\left|\Delta R_k\left({\Theta }_n\right)\right|;G_R^{k\complement }])$$

For the second term, we have

$$\sum _{n=N_k}^{M_k-1}{\gamma }^n\left|\Delta R_k\left({\Theta }_n\right)\right|\le 2T{\gamma }^{N_k}$$

$$E[\sum _{n=N_k}^{M_k-1}{\gamma }^n\left|\Delta R_k\left({\Theta }_n\right)\right|;G_R^{k\complement }]\le 2TE[{\gamma }^{N_k};G_R^{k\complement }]\le 2Tmin(E\left[{\gamma }^{N_k}\right],\mathrm{Pr}\left[G_R^{k\complement }\right])$$

$$E[\sum _{n=N_k}^{M_k-1}{\gamma }^n\left|\Delta R_k\left({\Theta }_n\right)\right|;G_R^{k\complement }]\le 2Tmin(E\left[{\gamma }^{N_k}\right],(1-\gamma {)}^2)$$

$$\sum _{k=0}^{\infty }E[\sum _{n=N_k}^{M_k-1}{\gamma }^n\left|\Delta R_k\left({\Theta }_n\right)\right|;G_R^{k\complement }]\le 2T\sum _{k=0}^{\infty }min(E\left[{\gamma }^{N_k}\right],(1-\gamma {)}^2)$$

Applying Proposition A.17 to the RHS, we get

$$\sum _{k=0}^{\infty }E[\sum _{n=N_k}^{M_k-1}{\gamma }^n\left|\Delta R_k\left({\Theta }_n\right)\right|;G_R^{k\complement }]\le 2T(\lceil \frac{2\ln (1-\gamma )}{\ln \alpha }\rceil +\frac{1}{T{\gamma }^{2T-2}(1-\gamma )})(1-\gamma {)}^2$$

Here, $\alpha$ is as defined in Proposition A.17. Since we are interested in the asymptotics $\gamma \to 1$, and our ultimate choice of $T$ will ensure that ${\gamma }^T\to 1$, we will henceforth make the assumption that ${\gamma }^{2T}>\frac{1}{2}$.

$$\sum _{k=0}^{\infty }E[\sum _{n=N_k}^{M_k-1}{\gamma }^n\left|\Delta R_k\left({\Theta }_n\right)\right|;G_R^{k\complement }]\le 2T\lceil \frac{2\ln (1-\gamma )}{\ln (1-\frac{1}{2}T(1-\gamma \left)\right)}\rceil (1-\gamma {)}^2+4(1-\gamma )$$

Denote $\rho (\gamma ,T)$ the expression on the RHS. We get

$$R_R\left(\gamma \right)\le (1-\gamma )(\sum _{k=0}^{\infty }E[\sum _{n=N_k}^{M_k-1}{\gamma }^n\left|\Delta R_k\left({\Theta }_n\right)\right|;G_R^k]+\rho (\gamma ,T\left)\right)$$

Denote

$$H_R^k:={CS}^{H_R}[{\Theta }_{M:k}^r,{\beta }_R(k+1{)}^{-1}]$$

Clearly

$$\mathrm{Pr}[\left|\Delta R_k\left({\Theta }_n\right)\right|\le W^{H_R^k}\left({\Theta }_n\right)|G_R^k]=1$$

Using this inequality, dropping the $;G_R^k$ (since it can only the right hand side smaller) and moving the sum inside the expected value, we get

$$R_R\left(\gamma \right)\le (1-\gamma )(E\left[\sum _{k=0}^{\infty }\sum _{n=N_k}^{M_k-1}{\gamma }^n{W}^{H_R^k}\left({\Theta }_n\right)\right]+\rho (\gamma ,T\left)\right)$$

Extending the sum on the RHS to $M_k$ (that can only increase it), and using the fact that the width is $\le 1$,

$$R_R\left(\gamma \right)\le (1-\gamma )(E\left[\sum _{k=0}^{\infty }({\gamma }^{N_k}+\sum _{n=N_k+1}^{M_k}{\gamma }^n{W}^{H_R^k}\left({\Theta }_n\right))\right]+\rho (\gamma ,T\left)\right)$$

By Proposition A.16,

$$R_R\left(\gamma \right)\le (1-\gamma )(E\left[\sum _{k=0}^{\infty }\sum _{n=N_k+1}^{M_k}{\gamma }^n{W}^{H_R^k}\left({\Theta }_n\right)\right]+\rho (\gamma ,T\left)\right)+\frac{2}{T}$$

We define the random variable $K_i:\Omega \to N$ by

$$K_i:=min\{k\in N|M_k\ge L_i\}$$

We can now rewrite the previous inequality as

$$R_R\left(\gamma \right)\le (1-\gamma )(E\left[\sum _{i=0}^{\infty }{\gamma }^{L_i+1}{W}^{H_R^{K_i}}\left({\Theta }_{L_i+1}\right)\right]+\rho (\gamma ,T\left)\right)+\frac{2}{T}$$

Obviously $L_i+1\ge i$ and hence

$$R_R\left(\gamma \right)\le (1-\gamma )(\sum _{i=0}^{\infty }{\gamma }^{i}E\left[W^{H_R^{K_i}}\left({\Theta }_{L_i+1}\right)\right]+\rho (\gamma ,T\left)\right)+\frac{2}{T}$$

On the other hand, by Proposition A.21 (for the $T=1$, $N_k=k$ case, applied to the subsequence ${\Theta }_{M_k}$, with ${\gamma }^{\frac{1}{2}T}$ playing the role of $\gamma$)

$$\sum _{k=0}^{\infty }{\gamma }^{\frac{1}{2}Tk}{W}^{H_R^k}\left({\Theta }_{M_k}\right)\le C_{\text{A.21}}(D_{RVO}+\sqrt{D_{RVO}{\beta }_R\left(\frac{1}{1-{\gamma }^{\frac{1}{2}T}}\right)\frac{1}{1-{\gamma }^{\frac{1}{2}T}}})$$

Denote ${\tilde{\beta }}_R(\gamma ,T,D_{RVO})$ the expression on the RHS. Applying Proposition A.15, we conclude

$$\sum _{i=0}^{\infty }{\gamma }^{i+\frac{1}{2}T}E\left[W^{H_R^{K_i}}\left({\Theta }_{L_i+1}\right)\right]\le 2T{\tilde{\beta }}_R(\gamma ,T,D_{RVO})+\frac{1}{1-\exp (-\frac{1}{4T})}$$

It follows

$$R_R\left(\gamma \right)\le (1-\gamma )({\gamma }^{-\frac{1}{2}T}\left(2T{\tilde{\beta }}_R\right(\gamma ,T,D_{RVO})+\frac{1}{1-\exp (-\frac{1}{4T})})+\rho (\gamma ,T\left)\right)+\frac{2}{T}$$

Now, we analyze $R_T$. By the same reasoning as for $R_R$, we have

$$R_T\left(\gamma \right)\le \Delta V\left(\gamma \right)(E[\sum _{n=N_k}^{M_k-1}{\gamma }^n{d}_{\text{tv}}\left(\Delta Y_k({\Theta }_n,A_n)\right);G_T^k]+\rho (\gamma ,T\left)\right)$$

Denote

$$H_T^k:={CS}^H[\Theta A_{L:N_k^{\prime }}{\Theta }_{N_k},{\beta }_T{(N_k^{\prime }+1)}^{-1}]$$

It is easy to see that for $N_k\le n<M_k$

$$\mathrm{Pr}[d_{\text{tv}}\left(\Delta Y_k({\Theta }_n,A_n)\right)\le \frac{\left|S\right|}{2}{W}^{H_T^k}\left({\Theta }_n{A}_n\right)|G_T^k]=1$$

It follows

$$R_T\left(\gamma \right)\le \Delta V\left(\gamma \right)(\frac{\left|S\right|}{2}E\left[\sum _{k=0}^{\infty }\sum _{n=N_k}^{M_k-1}{\gamma }^n{W}^{H_T^k}\left({\Theta }_n{A}_n\right)\right]+\rho (\gamma ,T\left)\right)$$

$$R_T\left(\gamma \right)\le \Delta V\left(\gamma \right)(\frac{\left|S\right|}{2}\sum _{i=0}^{\infty }E\left[{\gamma }^{L_i}{W}^{H_T^{K_i}}\left({\Theta }_{L_i}{A}_{L_i}\right)\right]+\rho (\gamma ,T\left)\right)$$

Since $L_i\ge i$, By Proposition A.14

$$\sum _{i=0}^{\infty }E\left[{\gamma }^{L_i}{W}^{H_T^{K_i}}\left({\Theta }_{L_i}{A}_{L_i}\right)\right]\le \sum _{i=0}^{\infty }(E\left[{\gamma }^{\frac{1}{2}(K_i-1)T}{W}^{H_T^{K_i}}\left({\Theta }_{L_i}{A}_{L_i}\right)\right]+\exp (-\frac{i}{4T}))$$

$$\sum _{i=0}^{\infty }E\left[{\gamma }^{L_i}{W}^{H_T^{K_i}}\left({\Theta }_{L_i}{A}_{L_i}\right)\right]\le {\gamma }^{-\frac{1}{2}T}\sum _{i=0}^{\infty }E\left[{\gamma }^{\frac{1}{2}{K}_{i}T}{W}^{H_T^{K_i}}\left({\Theta }_{L_i}{A}_{L_i}\right)\right]+\frac{1}{1-\exp (-\frac{1}{4T})}$$

Denote

$$\tilde{\rho }(\gamma ,T,\left|S\right|):=\rho (\gamma ,T)+\frac{\left|S\right|}{2}\cdot \frac{1}{1-\exp (-\frac{1}{4T})}$$

We get, using that ${\gamma }^{-\frac{1}{2}T}<2$

$$R_T\left(\gamma \right)\le \Delta V\left(\gamma \right)(\left|S\right|\sum _{i=0}^{\infty }E\left[{\gamma }^{\frac{1}{2}{K}_{i}T}{W}^{H_T^{K_i}}\left({\Theta }_{L_i}{A}_{L_i}\right)\right]+\tilde{\rho }(\gamma ,T,\left|S\right|))$$

On the other hand, ${\dim }_{RVO}H\le \left|S\right|\left|A\right|$ and by Proposition A.21

$$\sum _{i=0}^{\infty }{\gamma }^{\frac{1}{2}{K}_{i}T}{W}^{H_T^{K_i}}\left({\Theta }_{L_i}{A}_{L_i}\right)\le C_{\text{A.21}}(\left|S\right|\left|A\right|T+\sqrt{\left|S\right|\left|A\right|{\beta }_T\left(\frac{1}{1-{\gamma }^{\frac{1}{2}}}\right)\frac{1}{1-{\gamma }^{\frac{1}{2}}}})$$

Denote ${\tilde{\beta }}_T(\gamma ,T,\left|S\right|\left|A\right|)$ the expression on the RHS. It follows that

$$R_T\left(\gamma \right)\le \Delta V\left(\gamma \right)(\left|S\right|{\tilde{\beta }}_T(\gamma ,T,\left|S\right|\left|A\right|)+\tilde{\rho }(\gamma ,T\left)\right)$$

We set

$$T:=\sqrt[3]{3\frac{{(\tau +t_{est})}^2}{(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}$$

Now, we analyze the $\gamma \to 1$ limit. In this limit, the expression for $T$ justifies our assumption that ${\gamma }^{2T}>\frac{1}{2}$. Indeed, we have

$$\underset{\gamma \to 1}{lim}\ln {\gamma }^T=\underset{\gamma \to 1}{lim}T\ln \gamma =\underset{\gamma \to 1}{lim}\sqrt[3]{3\frac{{(\tau +t_{est})}^2}{(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}\cdot \ln \gamma =0$$

We now analyze the separate contributions of $R_R$, $R_T$ and $R_1$ to the limit of interest. We will use the notation $x\lesssim y$ to mean, there is some constant $C_0\in R^{+}$ that depends on nothing (i.e. on none of the parameters of the problem) s.t. $x\le C_{0}y$.

Our previous bound on $R_R$ can be written as

$$R_R\left(\gamma \right)\lesssim D_{RVO}(1-\gamma )T+$$ $$\sqrt{D_{RVO}\ln N(H_R,(1-\gamma {)}^{-4})\cdot \frac{1}{1-{\gamma }^{\frac{1}{2}T}}}\cdot (1-\gamma )T+$$ $$\sqrt{D_{RVO}\frac{1}{1-{\gamma }^{\frac{1}{2}T}}\ln \frac{1}{1-\gamma }}\cdot (1-\gamma )T+$$ $$\frac{1-\gamma }{1-\exp (-\frac{1}{4T})}+$$ $$T\lceil \frac{\ln (1-\gamma )}{\ln (1-\frac{1}{2}T(1-\gamma \left)\right)}\rceil (1-\gamma {)}^3+$$ $$(1-\gamma {)}^2+$$ $$\frac{1}{T}$$

Here we used that $1\lesssim {\gamma }^T\le 1$, substituted the expressions for ${\tilde{\beta }}_R$, $\tilde{\beta }$ and $\rho$, and dropped some dominated terms.

We analyze the separate contribution of each term.

$$\underset{\gamma \to 1}{limsup}\frac{D_{RVO}(1-\gamma )T}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}=0$$

$$\underset{\gamma \to 1}{limsup}\frac{\sqrt{D_{RVO}\ln N(H_R,(1-\gamma {)}^{-4})\cdot \frac{1}{1-{\gamma }^{\frac{1}{2}T}}}\cdot (1-\gamma )T}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}\lesssim$$ $$\underset{\gamma \to 1}{limsup}\frac{\sqrt{D_{RVO}{D}_{MB}\ln \frac{1}{1-\gamma }\cdot \frac{1}{(1-\gamma )T}}\cdot (1-\gamma )T}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}\lesssim$$ $$\underset{\gamma \to 1}{limsup}\frac{\sqrt{D_{RVO}{D}_{MB}(1-\gamma )\ln \frac{1}{1-\gamma }\cdot T}}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}\lesssim 1$$

$$\underset{\gamma \to 1}{limsup}\frac{\sqrt{D_{RVO}\frac{1}{1-{\gamma }^{\frac{1}{2}T}}\ln \frac{1}{1-\gamma }}\cdot (1-\gamma )T}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}\lesssim$$ $$\underset{\gamma \to 1}{limsup}\frac{\sqrt{D_{RVO}\frac{1}{(1-\gamma )T}\ln \frac{1}{1-\gamma }}\cdot (1-\gamma )T}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}=$$ $$\underset{\gamma \to 1}{limsup}\frac{\sqrt{D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }\cdot T}}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}=\frac{1}{\sqrt[3]{3D_{MB}+1}}$$

$$\underset{\gamma \to 1}{limsup}\frac{\left(\frac{1-\gamma }{1-\exp (-\frac{1}{4T})}\right)}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}\lesssim$$ $$\underset{\gamma \to 1}{limsup}\frac{(1-\gamma )T}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}=0$$

$$\underset{\gamma \to 1}{limsup}\frac{\left(T\lceil \frac{\ln (1-\gamma )}{\ln (1-\frac{1}{2}T(1-\gamma \left)\right)}\rceil \right(1-\gamma {)}^3)}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}\lesssim$$ $$\underset{\gamma \to 1}{limsup}\frac{\ln \frac{1}{1-\gamma }(1-\gamma {)}^2}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}=0$$

$$\underset{\gamma \to 1}{limsup}\frac{(1-\gamma {)}^2}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}=0$$

$$\underset{\gamma \to 1}{limsup}\frac{1}{T\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}=\frac{1}{\tau +t_{est}}$$

Our previous bound on $R_T$ can be written as

$$R_T\left(\gamma \right)\lesssim \Delta V\left(\gamma \right){\left|S\right|}^2\left|A\right|T$$ $$+\Delta V\left(\gamma \right)\left|S\right|\sqrt{\left|S\right|\left|A\right|\ln \frac{N(H,(1-\gamma {)}^{-4})}{(1-\gamma {)}^2}\cdot \frac{1}{1-{\gamma }^{\frac{1}{2}}}}$$ $$+\Delta V\left(\gamma \right)\left|S\right|\sqrt{\left|S\right|\left|A\right|(1-\gamma {)}^2\frac{1}{1-{\gamma }^{\frac{1}{2}}}\ln \frac{\left(\frac{1}{1-{\gamma }^{\frac{1}{2}}}\right)}{(1-\gamma {)}^2}\cdot \frac{1}{1-{\gamma }^{\frac{1}{2}}}}$$ $$+\Delta V\left(\gamma \right)T\lceil \frac{\ln (1-\gamma )}{\ln (1-\frac{1}{2}T(1-\gamma \left)\right)}\rceil (1-\gamma {)}^2$$ $$+\Delta V\left(\gamma \right)\cdot (1-\gamma )$$ $$+\Delta V\left(\gamma \right)\frac{\left|S\right|}{2}\cdot \frac{1}{1-\exp (-\frac{1}{4T})}$$

We analyze the contribution of each term.

$$\underset{\gamma \to 1}{limsup}\frac{\Delta V\left(\gamma \right){\left|S\right|}^2\left|A\right|T}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}\lesssim$$ $$\underset{\gamma \to 1}{limsup}\frac{\tau (1-\gamma ){\left|S\right|}^2\left|A\right|T}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}=0$$

$$\underset{\gamma \to 1}{limsup}\frac{\Delta V\left(\gamma \right)\left|S\right|\sqrt{\left|S\right|\left|A\right|\ln \frac{N(H,(1-\gamma {)}^{-4})}{(1-\gamma {)}^2}\cdot \frac{1}{1-{\gamma }^{\frac{1}{2}}}}}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}\lesssim$$ $$\underset{\gamma \to 1}{limsup}\frac{\tau (1-\gamma )\left|S\right|\sqrt{\left|S\right|\left|A\right|({\dim }_{MB}H+1)\ln \frac{1}{1-\gamma }\cdot \frac{1}{1-\gamma }}}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}=0$$

$$\underset{\gamma \to 1}{limsup}\frac{\Delta V\left(\gamma \right)\left|S\right|\sqrt{\left|S\right|\left|A\right|(1-\gamma {)}^2\frac{1}{1-{\gamma }^{\frac{1}{2}}}\ln \frac{\left(\frac{1}{1-{\gamma }^{\frac{1}{2}}}\right)}{(1-\gamma {)}^2}\cdot \frac{1}{1-{\gamma }^{\frac{1}{2}}}}}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}=0$$

$$\underset{\gamma \to 1}{limsup}\frac{\Delta V\left(\gamma \right)T\lceil \frac{\ln (1-\gamma )}{\ln (1-\frac{1}{2}T(1-\gamma \left)\right)}\rceil (1-\gamma {)}^2}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}\lesssim$$ $$\underset{\gamma \to 1}{limsup}\frac{\tau (1-\gamma {)}^2\ln \frac{1}{1-\gamma }}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}=0$$

$$\underset{\gamma \to 1}{limsup}\frac{\Delta V\left(\gamma \right)\cdot (1-\gamma )}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}=0$$

$$\underset{\gamma \to 1}{limsup}\frac{\Delta V\left(\gamma \right)\frac{\left|S\right|}{2}\cdot \frac{1}{1-\exp (-\frac{1}{4T})}}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}\lesssim$$ $$\underset{\gamma \to 1}{limsup}\frac{\tau (1-\gamma )\left|S\right|T}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}=0$$

To complete the proof, we need to analyze the contribution of $R_1$. We have

$$R_1\left(\gamma \right)\lesssim \frac{1}{T}(\frac{\Delta V\left(\gamma \right)}{(1-\gamma )}+t_{est})$$

$$\underset{\gamma \to 1}{limsup}\frac{\frac{1}{T}(\frac{\Delta V\left(\gamma \right)}{(1-\gamma )}+t_{est})}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}\lesssim$$ $$\underset{\gamma \to 1}{limsup}\frac{\tau +t_{est}}{T\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}=1$$

Putting everything together, we conclude

$$\underset{\gamma \to 1}{limsup}\frac{R\left(\gamma \right)}{\sqrt[3]{3(\tau +t_{est})(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}\lesssim 1■$$

Appendix

The following is a special case of what appeared in the previous essay as “Definition 1”, introduced here for the sake of simplifying notations.

Definition B.1

Consider a set $X$, an inner product space $Y$ and some $F\subseteq \{X\to Y\}$. Consider also $\theta \in R^{+}$, $n\in N$, a sequence ${\{x_k\in X\}}_{k\in \left[n\right]}$ and $x^{\ast }\in X$. $x^{\ast }$ is said to be $(F,\theta )$-dependant on $\left\{x_k\right\}$ when, for any $f,\tilde{f}\in F$

$$\sum _{k=0}^{n-1}{\Vert f\left(x_k\right)-\tilde{f}\left(x_k\right)\Vert }^2\le {\theta }^2⟹\Vert f\left(x^{\ast }\right)-\tilde{f}\left(x^{\ast }\right)\Vert \le \theta$$

Otherwise, $x^{\ast }$ is said to be $(F,\theta )$-independent of $\left\{x_k\right\}$.

The following is a special case of what appeared in the previous essay as “Definition A.1”.

Definition B.2

Consider a set $X$, a finite-dimensional inner product space $Y$ and some $F\subseteq \{X\to Y\}$. Assume $F$ is compact w.r.t. the product topology on $X\to Y\cong {\prod }_{x\in X}Y$. Consider also some $n\in N$, $x\in X^n$, $y\in Y^n$ and $\lambda \in R^{+}$. We then use the notation

$${LS}^F\left[xy\right]:=\underset{f\in F}{argmin}\sum _{m=0}^{n-1}{\parallel f\left(x_m\right)-y_m\parallel }^2$$

$${CS}^F[xy,\lambda ]:=\{f\in F|\sum _{m=0}^{n-1}{\Vert f\left(x_m\right)-{LS}^F\left[xy\right]\left(x_m\right)\Vert }^2\le \frac{1}{\lambda }\}$$

Proposition B.1

There is some $C_{B.1}\in R^{+}$ s.t. the following holds.

Consider a finite set $X$, a finite-dimensional inner product space $Y$ and some $F\subseteq \{X\to Y\}$. Let ${\{H_n\subseteq P(X^{\omega }\times Y^{\omega })\}}_{n\in N}$ be the canonical filtration, i.e.

$$H_n:=\{A^{\prime }\subseteq X^{\omega }\times Y^{\omega }|A^{\prime }=\left\{xy\right|{xy}_{:n}\in A\},A\subseteq X^n\times Y^n\text{Borel}\}$$

Consider also $f^{\ast }\in F$ and $\mu \in \Delta (X^{\omega }\times Y^{\omega })$ s.t. for any $n\in N$ and $x\in X$

$$\underset{xy\sim \mu }{E}\left[y_n\right|x_n=x,H_n]=f^{\ast }\left(x\right)$$

Assume that $\parallel y_n\parallel \le 1$ with $\mu$-probability $1$ for all $n\in N$. Fix $ϵ\in R^{+}$, $\delta \in (0,1)$. Define $\beta :R^{+}\to R$ by

$$\beta \left(t\right):=C_{B.1}({\sigma }^2\ln \frac{N(F,{ϵ}^{-2}{I}_d)}{\delta }+ϵt\ln \frac{et}{\delta })$$

Then,

$$\underset{xy\sim \mu }{\mathrm{Pr}}[f^{\ast }\notin \bigcap _{n=0}^{\infty }{CS}^F[{xy}_{:n},\beta (n+1{)}^{-1}]]\le \delta$$

Proof of Proposition B.1

Straightforward from “Proposition B.1” and “Proposition A.3″ in the previous essay. $■$

[John_Maxwell]

The literature study was very cursory and I will be glad to know about prior work I missed!

This post of mine seems related.