Dimensional regret without resets

[Vanessa Kosoy]

TLDR: I derive a variant of the RL regret bound by Osband and Van Roy (2014), that applies to learning without resets of environments without traps. The advantage of this regret bound over those known in the literature, is that it scales with certain learning-theoretic dimensions rather than number of states and actions. My goal is building on this result to derive this type of regret bound for DRL, and, later on, other settings interesting from an AI alignment perspective.

---

Previously I derived a regret bound for deterministic environments that scales with prior entropy and “prediction dimension”. That bound behaves as $O\left(\sqrt{1-\gamma }\right)$ in the episodic setting but only as $O\left(\sqrt[3]{31-\gamma }\right)$ in the setting without resets. Moreover, my attempts to generalize the result to stochastic environments led to bounds that are even weaker (have a lower exponent). Therefore, I decided to put that line of attack on hold, and use Osband and Van Roy’s technique instead, leading to an $O\left(\sqrt{1-\gamma }\right)$ bound in the stochastic setting without resets. This bound doesn’t scale down with the entropy of the prior, but this does not seem as important as dependence on $\gamma$.

Results

Russo and Van Roy (2013) introduced the concept of “eluder dimension” for the benefit of the multi-armed bandit setting, and Osband and Van Roy extended it to a form suitable for studying reinforcement learning. We will consider the following, slightly modified version of their definition.

Given a real vector space $Y$, we will use $PSD\left(Y\right)$ to denote the set of positive semidefinite bilinear forms on $Y$ and $PD\left(Y\right)$ to denote the set of positive definite bilinear forms on $Y$. Given a bilinear form $B:Y\times Y\to R$, we will slightly abuse notation by also regarding it as a linear functional $B:Y\otimes Y\to R$. Thereby, we have $B(v\otimes w)=B(v,w)$ and $B{v}^{\otimes 2}=B(v,v)$. Also, if $Y$ is finite-dimensional and $B$ is non-degenerate, we will denote $B^{-1}:Y^{\ast }\times Y^{\ast }\to R$ the unique bilinear form which satisfies

$$\forall v\in Y,\alpha \in Y^{\ast }:(\forall \beta \in Y^{\ast }:B^{-1}(\alpha ,\beta )=\beta v)⟺(\forall w\in Y:B(v,w)=\alpha w)$$

Definition 1

Consider a set $X$, a real vector space $Y$, some $F\subseteq \{X\to Y\}$ and a family ${\{B_x\in PSD(Y\left)\right\}}_{x\in X}$. Consider also $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,B)$-dependant on $\left\{x_k\right\}$ when, for any $f,\tilde{f}\in F$

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

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

Definition 2

Consider a set $X$, a real vector space $Y$ and some $F\subseteq \{X\to Y\}$. The Russo-Van Roy-Osband dimension (RVO dimension) ${\dim }_{RVO}F$ is the supremum of the set of $n\in N$ for which there is ${\{x_k\in X\}}_{k\in \left[n\right]}$ and $B$ s.t. for all $m\in \left[n\right]$, $x_m$ is $(F,B)$-independent of ${\left\{x_k\right\}}_{k\in \left[m\right]}$.

We have the following basic bounds on RVO dimension.

Proposition 1

Consider a set $X$, a real vector space $Y$ and some $F\subseteq \{X\to Y\}$. Then

$${\dim }_{RVO}F\le \left|X\right|$$

Proposition 2

Consider a set $X$, a real vector space $Y$ and some $F\subseteq \{X\to Y\}$. Then

$${\dim }_{RVO}F\le \frac{\left|F\right|(\left|F\right|-1)}{2}$$

Another concept we need to formulate the regret bound is the Minkowski–Bouligand dimension.

Definition 3

Consider a set $X$, a real vector space $Y$, some $F\subseteq \{X\to Y\}$ and a family ${\{B_x\in PSD(Y\left)\right\}}_{x\in X}$. A set $A\subseteq F$ is said to be a $B$-covering of $F$ when

$$\forall f\in F\exists \tilde{f}\in A:\underset{x\in X}{sup}{B}_x{\left(f\right(x)-\tilde{f}(x\left)\right)}^{\otimes 2}<1$$

Definition 4

Consider a set $X$, a real vector space $Y$, some $F\subseteq \{X\to Y\}$ and a family ${\{B_x\in PSD(Y\left)\right\}}_{x\in X}$. The covering number $N(F,B)$ is the infimum of the set of $n\in N$ for which there is a $B$-covering of $F$ of size $n$.

Definition 5

Consider a finite set $X$, a finite-dimensional real vector product space $Y$ and some $F\subseteq \{X\to Y\}$. Fix any ${\{B_x\in PD(Y\left)\right\}}_{x\in X}$. The Minkowski–Bouligand dimension (MB dimension) of $F$ is defined by

$${\dim }_{MB}F:=\underset{ϵ\to 0}{limsup}\frac{\ln N(F,{ϵ}^{-2}B)}{\ln \frac{1}{ϵ}}$$

It is easy to see the above is indeed well-defined, i.e. doesn’t depend on the choice of $B$. This is because given any $B,\tilde{B}$, there are constants $c_1,c_2\in R^{+}$ s.t. for all $F$ and $ϵ$

$$c_{1}N(F,{ϵ}^{-2}B)\le N(F,{ϵ}^{-2}\tilde{B})\le c_{2}N(F,{ϵ}^{-2}B)$$

Similarly, for any ${\{B_x\in PSD(Y\left)\right\}}_{x\in X}$, we have

$${\dim }_{MB}F\ge \underset{ϵ\to 0}{limsup}\frac{\ln N(F,{ϵ}^{-2}B)}{\ln \frac{1}{ϵ}}$$

For finite $F$ and $ϵ\ll 1$, it’s obvious that $N(F,{ϵ}^{-2}B)\le \left|F\right|$, and in particular ${\dim }_{MB}F=0$. It is also possible to show that, for any bounded $F$, ${\dim }_{MB}F\le \left|X\right|\dim Y$.

Note that, in general, MB dimension is fractional.

We will need yet another (but rather simple) notion of “dimension”.

Definition 6

Consider a set $X$, a vector space $Y$ and some $F\subseteq \{X\to Y\}$. The local dimension of $F$ is defined by

$${\dim }_{loc}F:=\underset{x\in X}{max}\dim \mathrm{span}\left\{f\right(x\left)\right|f\in F\}$$

Obviously ${\dim }_{loc}F\le \left|F\right|$ and ${\dim }_{loc}F\le \dim Y$.

Consider finite non-empty sets $S$ (states) and $A$ (actions). Observe that $\Delta S$ can be regarded as a subset of the vector space $R^S$. This allows us to speak of the RVO, MB and local dimensions of a hypothesis class of transition kernels $H\subseteq \{S\times A\stackrel{k}{\to }S\}$ (in this case $X=S\times A$ and $Y=R^S$).

We can now formulate the regret bound.

Theorem 1

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

Consider any finite non-empty sets $S$ and $A$, $R:S\to [0,1]$, closed set $H\subseteq \{S\times A\stackrel{k}{\to }S\}$ and Borel probability measure $\zeta$ on $H$ (prior). We define the maximal bias span ${\tau }_{\zeta R}$ by

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

Denote $D_{loc}:={\dim }_{loc}H$, $D_{MB}:={\dim }_{MB}H$ and $D_{RVO}:={\dim }_{RVO}H$. 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{\underset{T\sim \zeta }{E}\left[{EU}_{TR}^{\ast }\right(\gamma )-{EU}_{TR}^{{\pi }_{\gamma }^{†}}(\gamma \left)\right]}{{\tau }_{\zeta R}{D}_{loc}\sqrt{(D_{MB}+1)D_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}\le C$$

Here (like in previous essays), $V_{TR}(s,\gamma )$ is the value function for transition kernel $T$, reward function $R$, state $s$ and geometric time discount parameter $\gamma$; ${EU}_{TR}^{\pi }\left(\gamma \right)$ is the expected utility for policy $\pi$; ${EU}_{TR}^{\ast }\left(\gamma \right)$ is the maximal expected utility over policies. The expression in the numerator is, thereby, the Bayesian regret.

The implicit condition ${\tau }_{\zeta R}<\infty$ implies that for any $T\in H$ and $s,s^{\prime }\in S$, $V_{TR}^0\left(s\right)=V_{TR}^0\left(s^{\prime }\right)$. This is a no-traps condition stronger than the condition $A_{TR}^0\left(s\right)=A$ we used before: not only that long-term value cannot be lost in expectation, it cannot be lost at all. For any finite $H$ satisfying this no-traps condition, we have

$${\tau }_{\zeta R}=\underset{T\in H}{max}(\underset{s\in S}{max}{V}_{TR}^1\left(s\right)-\underset{s\in S}{min}{V}_{TR}^1\left(s\right))<\infty$$

A few directions for improving on this result:

• It is not hard to see from the proof that it is also possible to write down a concrete bound for fixed $\gamma$ (rather than considering the $\gamma \to 1$ limit), but its form is somewhat convoluted.

• It is probably possible to get an anytime policy with this form of regret, using PSRL with dynamic episode duration.

• It is interesting to try to make do with the weaker no-traps condition $A_{TR}^0\left(s\right)=A$, especially since a stronger no-traps conditions would translate to a stronger condition on the advisor in DRL.

• It is interesting to study RVO dimension in more detail. For example, I’m not even sure whether Proposition 2 is the best possible bound in terms of $\left|F\right|$ or it’s e.g. possible to get a linear bound.

• It seems tempting to generalize local dimension by allowing the values of $f\left(x\right)$ to lie on some nonlinear manifold of given dimension for any given $x$. This approach, if workable, might require a substantially more difficult proof.

• The “cellular decision processes” discussed previously in “Proposition 3″ have exponentially high local dimension, meaning that this regret bound is ineffective for them. We can consider a variant in which, on every time step, only one cell or a very small number of cells (possibly chosen randomly) change. This would have low local dimension. One way to interpret it is, as a continuous time process in which each cell has a certain rate of changing its state. EDIT (2019-07-06): It is actually possible to use Theorem 1 to get an effective regret bound for CDPs, by replacing the CDP with a different but equivalent MDP where each time step is replaced by a series of time steps in which the cells are “decided” one by one. It would be interesting to (i) have an explicit expression for the best possible bound among those generated by such “isomorphisms” for general MDPs (ii) derive bounds on RVO dimension for stochastic analogues of CDPs (possibly defined using Markov random fields).

Proofs

Proof of Proposition 1

Consider some ${\{x_k\in X\}}_{k\in \left[m\right]}$ and $x^{\ast }\in X$ which is $(F,B)$-independent of $\left\{x_k\right\}$. Then, there are some $f,\tilde{f}\in F$ s.t. the following two inequalities hold

$$\sum _{k=0}^{m-1}{B}_{x_k}{(f\left(x_k\right)-\tilde{f}\left(x_k\right))}^{\otimes 2}\le 1$$

$$B_{x^{\ast }}{(f\left(x^{\ast }\right)-\tilde{f}\left(x^{\ast }\right))}^{\otimes 2}>1$$

The first inequality implies that, for any $k\in \left[m\right]$, $B_{x_k}{(f\left(x_k\right)-\tilde{f}\left(x_k\right))}^{\otimes 2}\le 1$. Comparing with the second inequality, we conclude that $x^{\ast }\ne x_k$.

Now suppose that ${\{x_k\in X\}}_{k\in \left[n\right]}$ is s.t. for all $m\in \left[n\right]$, $x_m$ is $(F,B)$-independent of ${\left\{x_k\right\}}_{k\in \left[m\right]}$. By the previous paragraph, it follows that $x_m\ne x_k$ for any $m,k\in \left[n\right]$ s.t. $k<m$. Hence, $n\le \left|X\right|$, Q.E.D.

Proof of Proposition 2

Suppose that ${\{x_k\in X\}}_{k\in \left[n\right]}$ is s.t. for all $m\in \left[n\right]$, $x_m$ is $(F,B)$-independent of ${\left\{x_k\right\}}_{k\in \left[m\right]}$. Then, for each $m\in \left[n\right]$, we can choose $f_m,{\tilde{f}}_m\in F$ s.t. the following two inequalities hold

$$\sum _{k=0}^{m-1}{B}_{x_k}{(f_m\left(x_k\right)-{\tilde{f}}_m\left(x_k\right))}^{\otimes 2}\le 1$$

$$B_{x_m}{(f_m\left(x_m\right)-{\tilde{f}}_m\left(x_m\right))}^{\otimes 2}>1$$

In particular, the second inequality implies that $f_m\ne {\tilde{f}}_m$.

Now, consider some $k\in \left[m\right]$. By the first inequality

$$B_{x_k}{(f_m\left(x_k\right)-{\tilde{f}}_m\left(x_k\right))}^{\otimes 2}\le 1$$

On the other hand, the second inequality with $k$ instead of $m$ gives

$$B_{x_k}{(f_k\left(x_k\right)-{\tilde{f}}_k\left(x_k\right))}^{\otimes 2}>1$$

It follows that $\{f_m,{\tilde{f}}_m\}\ne \{f_k,{\tilde{f}}_k\}$. Therefore, $n$ cannot exceed the number of unordered pairs of distinct elements in $F$, Q.E.D.

Given a measurable space $X$, some $\mu ,\nu \in \Delta X$ and a measurable function $f:X\to R$, we will use the notation

$$\underset{x\sim \mu -\nu }{E}\left[f\right(x\left)\right]:=\underset{x\sim \mu }{E}\left[f\right(x\left)\right]-\underset{x\sim \nu }{E}\left[f\right(x\left)\right]$$

Given $X,Y$ measurable spaces, some $K,L:X\stackrel{k}{\to }Y$ and a measurable function $f:Y\to R$, we will use the notation

$$\underset{y\sim K}{E}\left[f\right(y\left)\right|x]:=\underset{y\sim K\left(x\right)}{E}\left[f\right(y\left)\right]$$

$$\underset{y\sim K-L}{E}\left[f\right(y\left)\right|x]:=\underset{y\sim K\left(x\right)-L\left(x\right)}{E}\left[f\right(y\left)\right]$$

Given finite sets $S,A$, some $T:S\times A\stackrel{k}{\to }S$ and $\pi :S\to A$, we will use the notation $T\pi :S\stackrel{k}{\to }S$ defined by

$$T\pi \left(s\right):=T(s,\pi (s\left)\right)$$

Proposition A.1

In the setting of Theorem 1, fix $T\in N^{+}$ and $\gamma \in (0,1)$. Let $\Pi :H\times S\to A$ be a Borel measurable mapping s.t.$\Pi \left(T\right)$ is an optimal policy, i.e.

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

Let ${\pi }_{\zeta \Pi T}^{\text{PS}}:S^{\ast }\times S\stackrel{k}{\to }A$ be the policy implemented by a PSRL algorithm with prior $\zeta$ and episode length $T$, s.t. whenever hypothesis $T$ is sampled, policy $\Pi \left(T\right)$ is followed. Denote the Bayesian regret by

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

Let $(\Omega ,P)$ be a probability space governing both the uncertainty about the true hypothesis, the stochastic behavior of the environment and the random sampling inside the algorithm. [See the proof of “Lemma 1” in this previous essay or the proof of “Theorem 1″ in another previous essay.] Furthermore, let $H_{\ast }:\Omega \to H$ be a random variable representing the true hypothesis, ${\{H_n:\Omega \to H\}}_{n\in N}$ be the random variables s.t.$H_n$ represents the hypothesis sampled at time $n$ (i.e. during episode number $\lfloor n/T\rfloor$), ${\{{\Theta }_n:\Omega \to S\}}_{n\in N}$ be random variables s.t.${\Theta }_n$ represents the state at time $n$ and ${\{A_n:\Omega \to A\}}_{n\in N}$ be random variables s.t.$A_n$ represents the action taken at time $n$. Denote $E_l:=H_{\ast }\Pi \left(H_{lT}\right)$ and ${\overline{E}}_l:=H_{lT}\Pi \left(H_{\ast }\right)$. Then

$$R\left(\gamma \right)=\sum _{n=0}^{\infty }{\gamma }^{n+1}\underset{}{E}\left[\underset{H_n-H_{\ast }}{E}\left[V_{H_{n}R}\right(\gamma \left)\right|{\Theta }_n,A_n]\right]+\sum _{l=0}^{\infty }{\gamma }^{(l+1)T}\underset{}{E}\left[\underset{{\overline{E}}_l^T-E_l^T}{E}\left[V_{H_{\ast }R}\right(\gamma \left)\right|{\Theta }_{lT}]\right]$$

Here, $E_l^T$ means raising $E_l$ to the $T$-th power w.r.t. Markov kernel composition, and the same for ${\overline{E}}_l^T$.

We will use the notation $V_{T\pi R}(s,\gamma )$ to stand for the expected utility achieved by policy $\pi$ when starting from state $s$ with transition kernel $T$, reward function $R$ and time discount parameter $\gamma$.

Proof of Proposition A.1

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_{H_{\ast }R}(s,\gamma )$$

$$V_l\left(s\right):=V_{H_{lT}R}(s,\gamma )$$

$$V_{lk}\left(s\right):=V_{H_{\ast }{\Pi }_{T-k}(H_{lT},H_{\ast })R}(s,\gamma )$$

It is easy to see that

$$R\left(\gamma \right)=\sum _{l=0}^{\infty }{\gamma }^{lT}\underset{}{E}[V_{\ast }\left({\Theta }_{lT}\right)-V_{l0}\left({\Theta }_{lT}\right)]$$

The above is essentially what appeared as “Proposition B.1” before, for the special case of PSRL, and where we regard every episode as a single time step in a new MDP in which every action is a policy for the duration of an episode in the original MDP.

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

$$\underset{}{E}\left[V_{\ast }\left({\Theta }_{lT}\right)\right]=\underset{}{E}\left[V_l\left({\Theta }_{lT}\right)\right]$$

It follows that

$$R\left(\gamma \right)=\sum _{l=0}^{\infty }{\gamma }^{lT}\underset{}{E}[V_l\left({\Theta }_{lT}\right)-V_{l0}\left({\Theta }_{lT}\right)]$$

We now prove by induction on $k\in [T+1]$ that

$$\underset{}{E}[V_l\left({\Theta }_{lT}\right)-V_{l0}\left({\Theta }_{lT}\right)]=\sum _{n=lT}^{lT+k-1}{\gamma }^{n-lT+1}\underset{}{E}\left[\underset{H_n-H_{\ast }}{E}\left[V_l\right|{\Theta }_n,A_n]\right]+{\gamma }^k\underset{}{E}[V_l\left({\Theta }_{lT+k}\right)-V_{lk}\left({\Theta }_{lT+k}\right)]$$

For $k=0$ this is a tautology. For any $k\in \left[T\right]$, the Bellman equation says that

$$V_l\left(s\right)=(1-\gamma )R\left(s\right)+\gamma \underset{H_{lT}\Pi \left(H_{lT}\right)}{E}\left[V_l\right|s]$$

$$V_{lk}\left(s\right)=(1-\gamma )R\left(s\right)+\gamma \underset{H_{\ast }\Pi \left(H_{lT}\right)}{E}\left[V_{l,k+1}\right|s]$$

It follows that

$$\underset{}{E}[V_l\left({\Theta }_{lT+k}\right)-V_{lk}\left({\Theta }_{lT+k}\right)]=\gamma \underset{}{E}[\underset{H_{lT}\Pi \left(H_{lT}\right)}{E}\left[V_l\right|{\Theta }_{lT+k}]-\underset{H_{\ast }\Pi \left(H_{lT}\right)}{E}\left[V_{l,k+1}\right|{\Theta }_{lT+k}]]$$

Since $\Pi \left(H_{lT}\right)$ is exactly the policy followed by PSRL at time $lT+k$, we get

$$\underset{}{E}[V_l\left({\Theta }_{lT+k}\right)-V_{lk}\left({\Theta }_{lT+k}\right)]=\gamma \underset{}{E}[\underset{H_{lT}}{E}\left[V_l\right|{\Theta }_{lT+k},A_{lT+k}]-\underset{H_{\ast }}{E}\left[V_{l,k+1}\right|{\Theta }_{lT+k},A_{lT+k}]]$$

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

$$\underset{}{E}[V_l\left({\Theta }_{lT+k}\right)-V_{lk}\left({\Theta }_{lT+k}\right)]=\gamma \underset{}{E}[\underset{H_{lT}-H_{\ast }}{E}\left[V_l\right|{\Theta }_{lT+k},A_{lT+k}]+V_l\left({\Theta }_{lT+k+1}\right)-V_{l,k+1}\left({\Theta }_{lT+k+1}\right)]$$

Applying this identity to the second second term on the right hand side of the induction hypothesis, we prove the induction step. For $k=T$, we get, denoting $n_0:=lT$ and $n_1:=(l+1)T$

$$\underset{}{E}[V_l\left({\Theta }_{n_0}\right)-V_{l0}\left({\Theta }_{n_0}\right)]=\sum _{n=n_0}^{n_1-1}{\gamma }^{n-n_0+1}\underset{}{E}\left[\underset{H_n-H_{\ast }}{E}\left[V_l\right|{\Theta }_n,A_n]\right]+{\gamma }^T\underset{}{E}[V_l\left({\Theta }_{n_1}\right)-V_{\ast }\left({\Theta }_{n_1}\right)]$$

Clearly

$$\underset{}{E}\left[V_l\left({\Theta }_{n_1}\right)\right]=\underset{}{E}\left[\underset{E_l^T}{E}\left[V_l\right|{\Theta }_{n_0}]\right]$$

$$\underset{}{E}\left[V_{\ast }\left({\Theta }_{n_1}\right)\right]=\underset{}{E}\left[\underset{E_l^T}{E}\left[V_{\ast }\right|{\Theta }_{n_0}]\right]$$

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

$$\underset{}{E}\left[V_l\left({\Theta }_{n_1}\right)\right]=\underset{}{E}\left[\underset{{\overline{E}}_l^T}{E}\left[V_{\ast }\right|{\Theta }_{n_0}]\right]$$

It follows that

$$\underset{}{E}[V_l\left({\Theta }_{n_0}\right)-V_{l0}\left({\Theta }_{n_0}\right)]=\sum _{n=n_0}^{n_1-1}{\gamma }^{n-n_0+1}\underset{}{E}\left[\underset{H_n-H_{\ast }}{E}\left[V_l\right|{\Theta }_n,A_n]\right]+{\gamma }^T\underset{}{E}\left[\underset{{\overline{E}}_l^T-E_l^T}{E}\left[V_{\ast }\right|{\Theta }_{n_0}]\right]$$

Applying this to each term in the earlier expression for $R\left(\gamma \right)$, we get the desired result. Q.E.D.

Proposition A.2

Consider a real finite-dimensional normed vector space $Y$ and a linear subspace $Z\subseteq Y$. Then, there exists $B\in PSD\left(Y\right)$ s.t.

1. For any $v\in Y$, $B{v}^{\otimes 2}\le {\parallel v\parallel }^2$

2. For any $v\in Z$, ${\left(\dim Z\right)}^{2}B{v}^{\otimes 2}\ge {\parallel v\parallel }^2$

Proof of Proposition A.2

We assume $\dim Z>0$ since otherwise the claim is trivial (take $B=0$).

By Theorem B.1 (see Appendix), there is $\tilde{B}\in PSD\left(Z\right)$ s.t. for any $v\in Z$

$$\tilde{B}{v}^{\otimes 2}\le {\parallel v\parallel }^2\le \dim Z\cdot \tilde{B}{v}^{\otimes 2}$$

By Corollary B.1 (see Appendix), there is a projection operator $P:Y\to Y$ s.t.$\mathrm{im}Y=Z$ and $\parallel P\parallel \le \sqrt{\dim Z}$. We define $B\in PSD\left(Y\right)$ by

$$B(v,w):=\frac{\tilde{B}(Pv,Pw)}{\dim Z}$$

For any $v\in Y$, we have

$$B{v}^{\otimes 2}=\frac{\tilde{B}(Pv,Pv)}{\dim Z}\le \frac{{\parallel Pv\parallel }^2}{\dim Z}\le \frac{{\parallel P\parallel }^2{\parallel v\parallel }^2}{\dim Z}\le {\parallel v\parallel }^2$$

For any $v\in Z$, we have $Pv=v$ and therefore

$${\parallel v\parallel }^2\le \dim Z\cdot \tilde{B}{v}^{\otimes 2}={\left(\dim Z\right)}^2\frac{\tilde{B}(Pv,Pv)}{\dim Z}={\left(\dim Z\right)}^{2}B{v}^{\otimes 2}$$

Q.E.D.

Proposition A.3

Consider a finite-dimensional real vector space $Y$, some $B\in PD\left(Y\right)$ and a Borel probability measure $\mu \in \Delta Y$ s.t. $\underset{y\sim \mu }{\mathrm{Pr}}[B{y}^{\otimes 2}\le 1]=1$. Let $y_0:=\underset{y\sim \mu }{E}\left[y\right]$ and $\sigma :=2\sqrt{2}$. Then, $\mu$ is $\sigma$-sub-Gaussian w.r.t. $B$, i.e., for any $\alpha \in Y^{\ast }$

$$\underset{y\sim \mu }{E}\left[\exp \left(\alpha (y-y_0)\right)\right]\le \exp \left(\frac{{\sigma }^2{B}^{-1}{\alpha }^{\otimes 2}}{2}\right)$$

Proof of Proposition A.3

By isomorphism, it is sufficient to consider the case $Y=R^n$, $B(v,w)=v\cdot w$, $\alpha \left(v\right)=t{v}_0$ for some $n\in N$ and $t\in [0,\infty )$. For this form of $\alpha$ it is sufficient to consider the case $n=1$. It remains to show that

$$\underset{y\sim \mu }{E}\left[e^{t(y-y_0)}\right]\le e^{\frac{1}{2}{\sigma }^2{t}^2}=e^{4t^2}$$

Here, we assume that $\underset{y\sim \mu }{\mathrm{Pr}}[\left|y\right|\le 1]=1$.

We consider separately the cases $t\ge \frac{1}{2}$ and $t<\frac{1}{2}$. In the first case

$$\underset{y\sim \mu }{E}\left[e^{t(y-y_0)}\right]\le \underset{y\in [-1,+1]}{max}{e}^{t(y-y_0)}\le e^{2t}\le e^{(2t{)}^2}=e^{4t^2}$$

In the second case, we use that for any $x\in (-\infty ,+1]$

$$e^x<1+x+\frac{e}{2}{x}^2$$

The above holds because, at $x=0$ the left hand side and the right hand have the same value and first derivative, and for any $x\in (-\infty ,+1)$, the second derivative of the left hand side is less than the second derivative of the right hand side. We get

$$\underset{y\sim \mu }{E}\left[e^{t(y-y_0)}\right]\le \underset{y\sim \mu }{E}[1+t(y-y_0)+\frac{e}{2}{t}^2{(y-y_0)}^2]=1+\frac{e}{2}{t}^2\underset{y\sim \mu }{\mathrm{Var}}\left[y\right]\le 1+\frac{e}{2}{t}^2\le e^{\frac{e}{2}{t}^2}\le e^{4t^2}$$

Q.E.D.

Definition A.1

Consider a set $X$, a finite-dimensional real vector space $Y$, some $F\subseteq \{X\to Y\}$ and a family ${\{B_x\in PSD(Y\left)\right\}}_{x\in X}$. 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$ and $y\in Y^n$. We then use the notation

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

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

I chose the notation $LS$ as an abbreviation of “least squares” and $CS$ as an abbreviation of “confidence set”. Note that $LS$ is somewhat ambiguous (and therefore, so is $CS$) since there might be multiple minima, but this will not be important in the following (i.e. an arbitrary minimum can be chosen).

Proposition A.4

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

Consider finite sets $X,S$, some $F\subseteq \left\{X\stackrel{k}{\to }S\right\}$ and a family ${\{B_x\in PSD\left(R^S\right)\}}_{x\in X}$. Assume that for any $x\in X$ and $\phi \in \Delta S$, $B_x{\phi }^{\otimes 2}\le 1$. Let ${\{H_n\subseteq P(X^{\omega }\times S^{\omega })\}}_{n\in N}$ be the canonical filtration, i.e.

$$H_n:=\{A^{\prime }\subseteq X^{\omega }\times S^{\omega }|A^{\prime }=\left\{xs\right|{xs}_{:n}\in A\},A\subseteq X^n\times S^n\}$$

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

$$\underset{xs\sim \mu }{\mathrm{Pr}}[s_n=s|x_n=x,H_n]=f^{\ast }(s\mid x)$$

Fix $ϵ\in R^{+}$, $\delta \in (0,1)$. Denote

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

Then,

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

Proof of Proposition A.4

For each $x\in X$, choose a finite set $E_x$ and a linear mapping $P_x:R^S\to R^{E_x}$ s.t. $B_x(v,w)=P_x\left(v\right)\cdot P_x\left(w\right)$. Let $\tilde{Y}:={⨁}_{x\in X}{R}^{E_x}$. Define $\tilde{F}\subseteq \{X\to \tilde{Y}\}$ by

$$\tilde{F}:=\{\tilde{f}:X\to \tilde{Y}|\tilde{f}\left(x\right)=P_x\left(f\right(x\left)\right),f\in F\}$$

Define $P^{\omega }:X^{\omega }\times S^{\omega }\to X^{\omega }\times {\tilde{Y}}^{\omega }$ by

$$P^{\omega }(xs{)}_n:=x_n{P}_{x_n}\left(s_n\right)$$

Let ${\tilde{f}}^{\ast }:=P^{\omega }\left(f^{\ast }\right)$ and $\tilde{\mu }:=P_{\ast }^{\omega }\mu$. By Proposition A.3, $\tilde{\mu }$ is $2\sqrt{2}$-sub-Gaussian. Applying Proposition B.1 (see Appendix) to the tilde objects gives the desired result. Here, we choose the constant $C_{\text{A.4}}$ s.t. the term $M=1$ in $\beta$ as defined in Proposition B.1 is absorbed by the term $\sigma \ln \frac{et}{\delta }\ge 1$ (note that $t\ge 1$ since we substitute $t=n+1$, $\delta <1$ and $\sigma =2\sqrt{2}>1$). Q.E.D.

Definition A.2

Consider a set $X$, some $x\in X$, a real vector space $Y$, some $F\subseteq \{X\to Y\}$ and a family ${\{B_x\in PSD(Y\left)\right\}}_{x\in X}$. The $B$-width of $F$ at $x$ is defined by

$$W^F(x,B):=\underset{f,\tilde{f}\in F}{sup}\sqrt{B_x{\left(f\right(x)-\tilde{f}(x\left)\right)}^{\otimes 2}}$$

Proposition A.5

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

Consider a set $X$, a real vector space $Y$, some $F\subseteq \{X\to Y\}$ and a family ${\{B_x\in PSD(Y\left)\right\}}_{x\in X}$. 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^{+}$ and $\delta \in (0,1)$. Denote

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

For any $n\in N$, define $F_n$ by

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

Assume that ${\gamma }^T>\frac{1}{2}$. Then,

$$\sum _{l=0}^{\infty }\sum _{m=0}^{T-1}{\gamma }^{lT+m}\left[\right[W^{F_{lT}}(x_{lT+m},B)>\theta \left]\right]\le C_{A.5}{\dim }_{RVO}F\cdot ({\theta }^{-2}\beta \left(\frac{1}{1-\gamma }\right)+T)$$

Proof of Proposition A.5

For each $x\in X$, choose a finite set $E_x$ and a linear mapping $P_x:Y\to R^{E_x}$ s.t. $B_x(v,w)=P_x\left(v\right)\cdot P_x\left(w\right)$. Let $\tilde{Y}:={⨁}_{x\in X}{R}^{E_x}$. Define $\tilde{F}\subseteq \{X\to \tilde{Y}\}$ by

$$\tilde{F}:=\{\tilde{f}:X\to \tilde{Y}|\tilde{f}\left(x\right)=P_x\left(f\right(x\left)\right),f\in F\}$$

Define also $\tilde{y}$ by

$${\tilde{y}}_n=P_{x_n}\left(y_n\right)$$

Applying Proposition B.2 (see Appendix) to the tilde objects, we conclude that for any $N\in N$

$$\sum _{l=0}^{N-1}\sum _{m=0}^{T-1}\left[\right[W^{F_{lT}}(x_{lT+m},B)>\theta \left]\right]\le {\dim }_{RVO}F\cdot \left(4{\theta }^{-2}\beta \right(NT)+T)$$

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

$$\sum _{l=0}^{\infty }\left(\sum _{N=l+1}^{\infty }{\gamma }^{NT}\right)\sum _{m=0}^{T-1}\left[\right[W^{F_{lT}}(x_{lT+m},B)>\theta \left]\right]\le {\dim }_{RVO}F\sum _{N=0}^{\infty }{\gamma }^{NT}\left(4{\theta }^{-2}\beta \right(NT)+T)$$

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

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

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

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

$$\sum _{l=0}^{\infty }\frac{{\gamma }^{(l+1)T}}{1-{\gamma }^T}\sum _{m=0}^{T-1}\left[\right[W^{F_{lT}}(x_{lT+m},B)>\theta \left]\right]\le \frac{{\dim }_{RVO}F}{T{\gamma }^T}{\int }_0^{\infty }{\gamma }^t\left(4{\theta }^{-2}\beta \right(t)+T)dt$$

The integral on the right hand side is a Laplace transform (where the dual variable is $s=\ln \frac{1}{\gamma }$). The functions $f\left(t\right)=1$, $f\left(t\right)=t$ and $f\left(t\right)=t\ln t$ all have the property that, for any $s\in R^{+}$

$$L\left[f\right]\left(s\right)\le \frac{1}{s}f\left(\frac{1}{s}\right)$$

Indeed, we have

$$L\left[1\right]\left(s\right)=\frac{1}{s}\le \frac{1}{s}$$

$$L\left[t\right]\left(s\right)=\frac{1}{s^2}\le \frac{1}{s}\cdot \frac{1}{s}$$

$$L\left[t\ln t\right]\left(s\right)=-\frac{\ln s+{\gamma }_{\text{EM}}-1}{s^2}=\frac{1}{s}\cdot \frac{1}{s}(\ln \frac{1}{s}+1-{\gamma }_{\text{EM}})\le \frac{1}{s}\cdot \frac{1}{s}\ln \frac{1}{s}$$

Here, ${\gamma }_{\text{EM}}$ is the Euler-Mascheroni constant.

We conclude

$$\frac{{\gamma }^T}{1-{\gamma }^T}\sum _{l=0}^{\infty }{\gamma }^{lT}\sum _{m=0}^{T-1}\left[\right[W^{F_{lT}}(x_{lT+m},B)>\theta \left]\right]\le \frac{{\dim }_{RVO}F}{T{\gamma }^T}\cdot \frac{1}{\ln \frac{1}{\gamma }}(4{\theta }^{-2}\beta \left(\frac{1}{\ln \frac{1}{\gamma }}\right)+T)$$

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

$$\sum _{l=0}^{\infty }{\gamma }^{lT}\sum _{m=0}^{T-1}\left[\right[W^{F_{lT}}(x_{lT+m},B)>\theta \left]\right]\le C_{\text{A.5}}{\dim }_{RVO}F\cdot ({\theta }^{-2}\beta \left(\frac{1}{1-\gamma }\right)+T)$$

Since ${\gamma }^m\le 1$, this implies

$$\sum _{l=0}^{\infty }\sum _{m=0}^{T-1}{\gamma }^{lT+m}\left[\right[W^{F_{lT}}(x_{lT+m},B)>\theta \left]\right]\le C_{A.5}{\dim }_{RVO}F\cdot ({\theta }^{-2}\beta \left(\frac{1}{1-\gamma }\right)+T)$$

Q.E.D.

Proposition A.6

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

Consider a set $X$, a real vector space $Y$, some $F\subseteq \{X\to Y\}$ and a family ${\{B_x\in PSD(Y\left)\right\}}_{x\in X}$. Assume that for any $x\in X$ and $f\in F$, $B_x{f\left(x\right)}^{\otimes 2}\le 1$. Consider also some $x\in X^{\omega }$, $y\in Y^{\omega }$, $T\in N^{+}$, $\gamma \in (0,1)$, ${\eta }_0,{\eta }_1\in R^{+}$ and $\delta \in (0,1)$. Define $\beta$ and $F_n$ the same way as in Proposition A.5. Denote $D:={\dim }_{RVO}F$. Assume $D>0$ and ${\gamma }^T>\frac{1}{2}$. Then,

$$\sum _{l=0}^{\infty }\sum _{m=0}^{T-1}{\gamma }^{lT+m}{W}^{F_{lT}}(x_{lT+m},B)\le C_{A.6}(DT+\sqrt{D\beta \left(\frac{1}{1-\gamma }\right)\frac{1}{1-\gamma }})$$

Proof of Proposition A.6

Due to the assumption $B_{x}f(x{)}^{\otimes 2}\le 1$, we have $W^{F_n}(x,B)\le 2$. For any $t\in R^{+}$, we have

$$W^{F_{lT}}(x_{lT+m},B)={\int }_0^2\left[\right[W^{F_{lT}}(x_{lT+m},B)>\theta \left]\right]d\theta \le t+{\int }_t^2\left[\right[W^{F_{lT}}(x_{lT+m},B)>\theta \left]\right]d\theta$$

$$\sum _{l=0}^{\infty }\sum _{m=0}^{T-1}{\gamma }^{lT+m}{W}^{F_{lT}}(x_{lT+m},B)\le \frac{t}{1-\gamma }+{\int }_t^2\sum _{l=0}^{\infty }\sum _{m=0}^{T-1}{\gamma }^{lT+m}\left[\right[W^{F_{lT}}(x_{lT+m},B)>\theta \left]\right]d\theta$$

Applying Proposition A.5 to the right hand side

$$\sum _{l=0}^{\infty }\sum _{m=0}^{T-1}{\gamma }^{lT+m}{W}^{F_{lT}}(x_{lT+m},B)\le \frac{t}{1-\gamma }+C_{\text{A.5}}D{\int }_t^2({\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 _{l=0}^{\infty }\sum _{m=0}^{T-1}{\gamma }^{lT+m}{W}^{F_{lT}}(x_{lT+m},B)\le \frac{t}{1-\gamma }+C_{\text{A.5}}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.6}}$, it follows that

$$\sum _{l=0}^{\infty }\sum _{m=0}^{T-1}{\gamma }^{lT+m}{W}^{F_{lT}}(x_{lT+m},B)\le C_{\text{A.6}}(DT+\sqrt{D\beta \left(\frac{1}{1-\gamma }\right)\frac{1}{1-\gamma }})$$

Q.E.D.

Proof of Theorem 1

We take ${\pi }_{\gamma }^{†}:={\pi }_{\zeta \Pi T}^{\text{PS}}$ where $\Pi$ is as in Proposition A.1 and $T\in N^{+}$ will be specified later. Denote the Bayesian regret by

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

By Proposition A.1

$$R\left(\gamma \right)=\sum _{n=0}^{\infty }{\gamma }^{n+1}\underset{}{E}\left[\underset{H_n-H_{\ast }}{E}\left[V_{H_{n}R}\right(\gamma \left)\right|{\Theta }_n,A_n]\right]+\sum _{l=0}^{\infty }{\gamma }^{(l+1)T}\underset{}{E}\left[\underset{{\overline{E}}_l^T-E_l^T}{E}\left[V_{H_{\ast }R}\right(\gamma \left)\right|{\Theta }_{lT}]\right]$$

$$R\left(\gamma \right)\le \sum _{n=0}^{\infty }{\gamma }^n\underset{}{E}\left[\left|\underset{H_n-H_{\ast }}{E}\left[V_{H_{n}R}\right(\gamma \left)\right|{\Theta }_n,A_n]\right|\right]+\sum _{l=0}^{\infty }{\gamma }^{lT}\underset{}{E}\left[\left|\underset{{\overline{E}}_l^T-E_l^T}{E}\left[V_{H_{\ast }R}\right(\gamma \left)\right|{\Theta }_{lT}]\right|\right]$$

We will use the notation

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

It follows that

$$R\left(\gamma \right)\le \Delta V\left(\gamma \right)(\sum _{n=0}^{\infty }{\gamma }^n\underset{}{E}\left[d_{\text{tv}}(H_n({\Theta }_n,A_n),H_{\ast }({\Theta }_n,A_n))\right]+\sum _{l=0}^{\infty }{\gamma }^{lT}\underset{}{E}\left[d_{\text{tv}}(E_{lT}^T\left({\Theta }_{lT}\right),{\overline{E}}_{lT}^T\left({\Theta }_{lT}\right))\right])$$

$$R\left(\gamma \right)\le \Delta V\left(\gamma \right)(\sum _{n=0}^{\infty }{\gamma }^n\underset{}{E}\left[d_{\text{tv}}(H_n({\Theta }_n,A_n),H_{\ast }({\Theta }_n,A_n))\right]+\frac{1}{1-{\gamma }^T})$$

Consider $Y=R^S$ equipped with the $L^1$ norm. Given $s\in S$ and $a\in A$, consider also the subspace

$$W_{sa}:=\mathrm{span}\left\{T\right(s,a\left)\right|T\in H\}$$

By Proposition A.2, there is $B_{sa}\in PSD\left(Y\right)$ s.t.

1. For any $\phi \in \Delta S$

$$B_{sa}{\phi }^{\otimes 2}\le 1$$

1. For any $T,\tilde{T}\in H$

$$\frac{1}{4}{D}_{loc}^2{B}_{sa}{\left(T\right(s,a)-\tilde{T}(s,a\left)\right)}^{\otimes 2}\ge d_{\text{tv}}{\left(T\right(s,a),\tilde{T}(s,a\left)\right)}^2$$

We now apply Proposition A.4 with $\delta :=\frac{1}{2}(1-\gamma {)}^2$ and $ϵ:=(1-\gamma {)}^2$. We get

$$\underset{}{\mathrm{Pr}}[H_{\ast }\in \bigcap _{n=0}^{\infty }{CS}^H[\Theta A_{:n}{\Theta }_n,\beta (n+1{)}^{-1}B]]\ge 1-\frac{1}{2}(1-\gamma {)}^2$$

Here, $\beta$ was defined in Proposition A.4.

Since the hypothesis $H_n$ is sampled from the posterior, for any $l\in N$ we also have

$$\underset{}{\mathrm{Pr}}[H_{lT}\in {CS}^H[\Theta A_{:lT}{\Theta }_{lT},\beta (lT+1{)}^{-1}B]]\ge 1-\frac{1}{2}(1-\gamma {)}^2$$

$$\underset{}{\mathrm{Pr}}[H_{\ast },H_{lT}\in {CS}^H[\Theta A_{:lT}{\Theta }_{lT},\beta (lT+1{)}^{-1}B]]\ge 1-(1-\gamma {)}^2$$

Denote

$$G_n:=\{H_{\ast },H_{lT}\in {CS}^H[\Theta A_{:lT}{\Theta }_{lT},\beta (lT+1{)}^{-1}B]\}\subseteq \Omega$$

We get

$$R\left(\gamma \right)\le \Delta V\left(\gamma \right)\sum _{n=0}^{\infty }{\gamma }^n(\underset{}{E}[d_{\text{tv}}(H_n({\Theta }_n,A_n),H_{\ast }({\Theta }_n,A_n));G_n]+(1-\gamma {)}^2)$$

$$R\left(\gamma \right)\le \Delta V\left(\gamma \right)(\sum _{n=0}^{\infty }{\gamma }^n\underset{}{E}[d_{\text{tv}}(H_n({\Theta }_n,A_n),H_{\ast }({\Theta }_n,A_n));G_n]+1-\gamma +\frac{1}{1-{\gamma }^T})$$

Using property 2 of B

$$R\left(\gamma \right)\le \Delta V\left(\gamma \right)(\frac{1}{2}{D}_{loc}\sum _{n=0}^{\infty }{\gamma }^n\underset{}{E}[\sqrt{B_{{\Theta }_n{A}_n}{(H_n({\Theta }_n,A_n)-H_{\ast }({\Theta }_n,A_n))}^{\otimes 2}};G_n]+1-\gamma +\frac{1}{1-{\gamma }^T})$$

Denote

$$H_l:={CS}^H[\Theta A_{:lT}{\Theta }_{lT},\beta (lT+1{)}^{-1}B]$$

Clearly

$$\underset{}{\mathrm{Pr}}[\sqrt{B_{{\Theta }_n{A}_n}{(H_n({\Theta }_n,A_n)-H_{\ast }({\Theta }_n,A_n))}^{\otimes 2}}\le W^{H_{\lfloor n/T\rfloor }}({\Theta }_n{A}_n,B)|G_n]=1$$

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

$$R\left(\gamma \right)\le \Delta V\left(\gamma \right)(\frac{1}{2}{D}_{loc}\underset{}{E}\left[\sum _{n=0}^{\infty }{\gamma }^n{W}^{H_{\lfloor n/T\rfloor }}({\Theta }_n{A}_n,B)\right]+1-\gamma +\frac{1}{1-{\gamma }^T})$$

We will now assume $D_{RVO}>0$ (if $D_{RVO}=0$, then $\left|H\right|=1$ and $R\left(\gamma \right)=0$) and ${\gamma }^T>\frac{1}{2}$. Applying Proposition A.6, we conclude

$$R\left(\gamma \right)\le \Delta V\left(\gamma \right)(\frac{D_{loc}{C}_{A.6}}{2}(D_{RVO}T+\sqrt{D_{RVO}\beta \left(\frac{1}{1-\gamma }\right)\frac{1}{1-\gamma }})+1-\gamma +\frac{1}{1-{\gamma }^T})$$

Denote the second factor on the right hand side $F\left(\gamma \right)$, so that the inequality becomes

$$R\left(\gamma \right)\le \Delta V\left(\gamma \right)F\left(\gamma \right)$$

We set

$$T:=\lfloor \frac{1}{\sqrt{D_{loc}{D}_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}\rfloor$$

Now, we analyze the $\gamma \to 1$ limit. In this limit, the expression for $T$ justifies our assumption that ${\gamma }^T>\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}\frac{\ln \gamma }{\sqrt{D_{loc}{D}_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}=0$$

Using the previous inequality for $R\left(\gamma \right)$, we get

$$\underset{\gamma \to 1}{limsup}\frac{R\left(\gamma \right)}{\sqrt{(1-\gamma )\ln \frac{1}{1-\gamma }}}\le \underset{\gamma \to 1}{limsup}\frac{\Delta V\left(\gamma \right)F\left(\gamma \right)}{\sqrt{(1-\gamma )\ln \frac{1}{1-\gamma }}}$$

We assume ${\tau }_{\zeta R}<\infty$, otherwise the theorem is vacuous. Multiplying the numerator and denominator on the right hand side by $\sqrt{1-\gamma }$, we get

$$\underset{\gamma \to 1}{limsup}\frac{R\left(\gamma \right)}{\sqrt{(1-\gamma )\ln \frac{1}{1-\gamma }}}\le {\tau }_{\zeta R}\underset{\gamma \to 1}{limsup}\sqrt{\frac{1-\gamma }{\ln \frac{1}{1-\gamma }}}\cdot F\left(\gamma \right)$$

We will now analyze the contribution of each term in $F\left(\gamma \right)$ to the limit on the right hand side (using the fact that $limsup(F_1+F_2)\le limsup{F}_1+limsup{F}_2$). We ignore multiplicative constants that can be absorbed into $C$.

The first term gives (using our choice of $T$)

$$\underset{\gamma \to 1}{limsup}\sqrt{\frac{1-\gamma }{\ln \frac{1}{1-\gamma }}}\cdot \sqrt{\frac{D_{loc}{D}_{RVO}}{(1-\gamma )\ln \frac{1}{1-\gamma }}}=0$$

The second term gives (using the definitions of $\beta$ and our choices of $\delta$ and $ϵ$)

$$\underset{\gamma \to 1}{limsup}\sqrt{\frac{1-\gamma }{\ln \frac{1}{1-\gamma }}}\cdot D_{loc}\sqrt{D_{RVO}(\ln \frac{2N(H,(1-\gamma {)}^{-4}B)}{(1-\gamma {)}^2}+(1-\gamma \left)\ln \frac{2e}{(1-\gamma {)}^3}\right)\frac{1}{1-\gamma }}\le$$

$$\underset{\gamma \to 1}{limsup}\sqrt{\frac{1-\gamma }{\ln \frac{1}{1-\gamma }}}\cdot D_{loc}\sqrt{\frac{D_{RVO}}{1-\gamma }}(\sqrt{\ln N(H,(1-\gamma {)}^{-4}B)}+\sqrt{\ln \frac{2}{(1-\gamma )}}+\sqrt{(1-\gamma )\ln \frac{2e}{(1-\gamma {)}^3}})$$

We analyze each subterm separately. The first subterm gives

$$\underset{\gamma \to 1}{limsup}\sqrt{\frac{1-\gamma }{\ln \frac{1}{1-\gamma }}}\cdot D_{loc}\sqrt{\frac{D_{RVO}}{1-\gamma }\ln N(H,(1-\gamma {)}^{-4}B)}=$$

$$D_{loc}\sqrt{D_{RVO}}\underset{\gamma \to 1}{limsup}\sqrt{\frac{\ln N(H,(1-\gamma {)}^{-4}B)}{\frac{1}{2}\ln \frac{1}{(1-\gamma {)}^2}}}\le$$

$$D_{loc}\sqrt{2D_{RVO}{D}_{MB}}$$

The second subterm gives

$$\underset{\gamma \to 1}{limsup}\sqrt{\frac{1-\gamma }{\ln \frac{1}{1-\gamma }}}\cdot D_{loc}\sqrt{\frac{D_{RVO}}{1-\gamma }\ln \frac{2}{1-\gamma }}=D_{loc}\sqrt{D_{RVO}}$$

The third subterm gives

$$\underset{\gamma \to 1}{limsup}\sqrt{\frac{1-\gamma }{\ln \frac{1}{1-\gamma }}}\cdot D_{loc}\sqrt{\frac{D_{RVO}}{1-\gamma }(1-\gamma )\ln \frac{2e}{(1-\gamma {)}^3}}=0$$

The third and fourth terms give

$$\underset{\gamma \to 1}{limsup}\sqrt{\frac{1-\gamma }{\ln \frac{1}{1-\gamma }}}\cdot (1-\gamma )=0$$

To analyze the fifth term, observe that ${lim}_{\gamma \to 1}(1-\gamma )T\left(\gamma \right)=0$. Hence

$$\underset{\gamma \to 1}{limsup}\sqrt{\frac{1-\gamma }{\ln \frac{1}{1-\gamma }}}\cdot \frac{1}{1-{\gamma }^{T\left(\gamma \right)}}=$$

$$\underset{\gamma \to 1}{limsup}\sqrt{\frac{1-\gamma }{\ln \frac{1}{1-\gamma }}}\cdot \frac{1}{(1-\gamma )T\left(\gamma \right)}=$$

$$\underset{\gamma \to 1}{limsup}\sqrt{\frac{1-\gamma }{\ln \frac{1}{1-\gamma }}}\cdot \frac{\sqrt{D_{loc}{D}_{RVO}(1-\gamma )\ln \frac{1}{1-\gamma }}}{(1-\gamma )}=$$

$$\sqrt{D_{loc}{D}_{RVO}}$$

Putting everything together, we observe that the expression $D_{loc}\sqrt{D_{RVO}(D_{MB}+1)}$ dominates all the terms (up to a multiplicative constant). Here, we use that $D_{loc}$ is an integer and hence $D_{loc}\ge \sqrt{D_{loc}}$. We conclude

$$\underset{\gamma \to 1}{limsup}\frac{R\left(\gamma \right)}{\sqrt{(1-\gamma )\ln \frac{1}{1-\gamma }}}\le C{\tau }_{\zeta R}{D}_{loc}\sqrt{D_{RVO}(D_{MB}+1)}$$

Q.E.D.

Appendix

The following was proved in John (1948), available in the collection Giorgi and Kjeldesen (2014) (the theorem in question is on page 214).

Theorem B.1 (John)

Consider a real finite-dimensional normed vector space $Y$. Then, there exists $B\in PD\left(Y\right)$ s.t. for any $v\in Y$

$$B{v}^{\otimes 2}\le {\parallel v\parallel }^2\le \dim Y\cdot B{v}^{\otimes 2}$$

The following is from Kadets and Snobar (1971).

Theorem B.2 (Kadets-Snobar)

Consider a real Banach space $Y$ and a finite-dimensional linear subspace $Z\subseteq Y$. Then, for any $ϵ\in R^{+}$, there is a projection operator $P:Y\to Y$ s.t.$\mathrm{im}P=Z$ and $\parallel P\parallel <\sqrt{\dim Z}+ϵ$.

Corollary B.1

Consider a real finite-dimensional normed vector space $Y$ and a linear subspace $Z\subseteq Y$. Then, there is a projection operator $P^{\star }:Y\to Y$ s.t.$\mathrm{im}{P}^{\star }=Z$ and $\parallel P^{\star }\parallel \le \sqrt{\dim Z}$.

Proof of Corollary B.1

Let $End\left(Y\right)$ be the vector space of linear operators $Y\to Y$. Define

$$Pr(Y,Z):=\{P\in End(Y\left)\right|P^2=P,\mathrm{im}P=Z\}$$

$$X:=\{P\in Pr(Y,Z\left)\right|\parallel P\parallel \le \sqrt{\dim Z}+1\}$$

$Pr(Y,Z)$ is an affine subspace of $End\left(Y\right)$ and $X$ is a compact set. Define $f:X\to R$ by $f\left(P\right):=\parallel P\parallel$. $f$ is a continuous function. By Theorem B.2, $inff\le \sqrt{\dim Z}$. Since $X$ is compact, $f$ attains its infimum at some $P^{\star }\in X$, and we have $f\left(P^{\star }\right)\le \sqrt{\dim Z}$, Q.E.D.

The next proposition appeared (in slightly greater generality) in Osband and Van Roy as “Proposition 5”. We will use $I_d\in PD\left(R^d\right)$ to denote the form corresponding to the identity matrix.

Proposition B.1 (Osband-Van Roy)

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

Consider a finite set $X$, the vector space $Y:=R^d$ for some $d\in N$ 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 $M\in R^{+}$ is s.t.$y_n\cdot y_n\le M^2$ with $\mu$-probability $1$ for all $n\in N$. Assume also that $\sigma \in R^{+}$ is s.t.$\mu$ is $\sigma$-sub-Gaussian, i.e., for any $\alpha \in Y$, $n\in N$ and $x\in X$

$$\underset{xy\sim \mu }{E}\left[\exp (\alpha \cdot (y_n-f^{\ast }(x\left)\right))\right|x_n=x,H_n]\le \exp \left(\frac{{\sigma }^2(\alpha \cdot \alpha )}{2}\right)$$

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(M+\sigma \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}{I}_d]]\le \delta$$

Note that we removed a square root in the definition of $\beta$ compared to equation (7) in Osband and Van Roy. This only makes $\beta$ larger (up to a constant factor) and therefore, only makes the claim weaker.

The proposition below appeared in Osband and Van Roy as “Lemma 1”.

Proposition B.2 (Osband-Van Roy)

Consider a set $X$, the vector space $Y=R^d$ for some $d\in N$ and some $F\subseteq \{X\to Y\}$. Consider also some $x\in X^{\omega }$, $y\in Y^{\omega }$, $T\in N^{+}$, $N\in N$, $\theta \in R^{+}$ and a nondecreasing sequence ${\{{\beta }_n\in R^{+}\}}_{n\in N}$. For any $n\in N$, define $F_n$ by

$$F_n:={CS}^F[{xy}_{:n},{\beta }_n^{-1}{I}_d]$$

Then,

$$\sum _{l=0}^{N-1}\sum _{m=0}^{T-1}\left[\right[W^{F_{lT}}(x_{lT+m},I_d)>\theta \left]\right]\le {\dim }_{RVO}F\cdot (4{\theta }^{-2}{\beta }_{NT-1}+T)$$