Proof. We simply do a union bound and then plug in our bound from Lemma 18. \[\begin{align} &\mathbb{P}(\{\mathcal{E}^1_T(\lambda)\}^C) \\ &\leq \sum_{s,a} \mathbb{P}\left(\exists t \in [1,T], : {\rm KL}_{\hat{M}_t|M}(s,a) > \frac{\beta_1(N_t(s,a),\lambda)}{N_t(s,a)} \right)\\ &=\sum_{s,a} \mathbb{P}\left(\exists t \in [1,T], : {\rm KL}_{\hat{M}_t|M}(s,a)N_t(s,a) > (S-1) \log\!\left(e\!\left(1 + \frac{N_t(s,a)}{S-1}\right)\!\right) + \log(SA/\delta) \right)\\ &\leq \sum_{s,a} \frac{\lambda}{SA}\\ &= \lambda \end{align}\] The proof is then complete. ◻

Proof. Fix a state-action pair \(z = (s,a)\) and let \(Y_t = \mathbb{1}_{z_t = z}\) and \(X_k = \mathbb{1}_{Y_{(k-1)m+1} + \cdots + Y_{km} > 0}\) for \(k = 1, \ldots, \lfloor t/m \rfloor\). Define \(\tilde{N}_{\lfloor t/m \rfloor}(s,a) = \sum_{k=1}^{\lfloor t/m \rfloor} X_k\), and note that \(N_t(s,a) \ge \tilde{N}_{\lfloor t/m \rfloor}(s,a)\) for all \(t \ge 1\).

Let \(Q_k = \mathbb{P}(X_k = 1 \mid \mathcal{F}_{k-1})\), where \(\mathcal{F}_k = \sigma(Y_1, \ldots, Y_{km})\). Note that we can also write \(Q_k\) as \(Q_k = \mathbb{P}(\exists n \in \{1, \ldots, m\} : Y_{(k-1)m+n} = 1 \mid \mathcal{F}_{k-1})\). Then \[\begin{align} Q_k &= \mathbb{E}_{(\pi_t)}\big[ \mathbb{P}(\exists n \in \{1, \ldots, m\} : Y_{(k-1)m+n} = 1 \mid \mathcal{F}_{k-1}, (\pi_t)_{t}) \big] \\ &\ge \mathbb{E}_{(\pi_t)} \Big[ \max_{1 \le n \le m} \mathbb{P}(Y_{(k-1)m+n} = 1 \mid \mathcal{F}_{k-1}, (\pi_t)_t) \Big] \\ &\ge \mathbb{E}_{(\pi_t), z_0} \Big[ \max_{1 \le n \le m} \mathbb{P}(z_{(k-1)m+n} = z \mid z_{(k-1)m} = z_0, \mathcal{F}_{k-1}, (\pi_t)_t) \Big] \\ &= \mathbb{E}_{(\pi_t), z_0} \Big[ \max_{1 \le n \le m} \mathbb{E}_{(z_j)_{j=1}^{n-1}} \Big[ \prod_{j=0}^{n-1} \mathbb{P}(z_{(k-1)m+j+1} = z_{j+1} \mid z_{(k-1)m+j} = z_j) \big| z_1, \ldots, z_n = z \Big] \Big| z_0 \Big] \\ &\ge \mathbb{E}_{(\pi_t), z_0} \Big[ \max_{1 \le n \le m} \mathbb{E}_{(z_j)_{j=1}^{n-1}} \Big[ \prod_{j=0}^{n-1} \frac{1}{(km)^{\alpha+\beta}} P^{n}_{u}(z_{(k-1)m+j+1} = z_{j+1} \mid z_{(k-1)m+j} = z_j) \Big| z_1, \ldots, z_n = z \Big] \Big| z_0 \Big] \\ &= \mathbb{E}_{(\pi_t), z_0} \Big[ \max_{1 \le n \le m} \frac{1}{(km)^{n(\alpha+\beta)}} P^{n}_{u}(z_{(k-1)m+n} = z \mid z_{(k-1)m} = z_0) \Big| z_0 \Big] \\ &\geq \mathbb{E}_{(\pi_t), z_0} \Big[ \max_{1 \le n \le m} \frac{1}{(km)^{n(\alpha+\beta)}} \eta_n \Big| z_0 \Big] \\ &\geq \mathbb{E}_{(\pi_t), z_0} \Big[ \max_{1 \le n \le m} \frac{1}{(km)^{n(\alpha+\beta)}} \eta_m \Big| z_0 \Big] \\ &\ge \frac{\eta_m}{(km)^{\alpha+\beta}}. \end{align}\]

Hence, for \(\lambda' \ge 0\) due to Lemma 17 we also have \[\mathbb{P}\left( \exists t \in [1,T] : N_t(s,a) \le \frac{1}{2} \sum_{k=1}^{\lfloor t/m \rfloor} \frac{\eta_m}{(km)^{\alpha+\beta}} - \lambda' \right) \le \mathbb{P}\left( \exists t \in [1,T]: \tilde{N}_{\lfloor t/m \rfloor}(s,a) \le \frac{1}{2} \sum_{k=1}^{\lfloor t/m \rfloor} Q_k - \lambda' \right) \le e^{-\lambda'}.\]

Consequently, choosing \(\lambda' = \log(SA / \lambda)\), we get that \[\mathbb{P}\big( \overline{\mathcal{E}_{\text{cnt}}(\lambda)} \big) \le \sum_{s,a} \mathbb{P}\left( \exists t \in [1,T]: N_t(s,a) \le \frac{1}{2} \sum_{k=1}^{\lfloor t/m \rfloor} Q_k(s,a) - \log\left( \frac{SA}{\lambda} \right) \right) \le \sum_{s,a} \frac{\lambda}{SA} = \lambda.\] ◻

Proof. By definition \({\rm KL}_{M_t|M}(s,a)={\rm KL}( P_t^\Pi(s,a), P(s,a))\). Therefore, under \({\cal E}_T^1\), an application of Pinsker’s inequality yields \[\| P_t^\Pi(s,a)-P(s,a)\|_1^2 \leq \frac{\beta_1(N_t(s,a),\lambda)}{2N_{t}(s,a)}\quad \forall(s,a).\] Therefore \[M_t\in B_{\tilde{\psi}(\lambda,t)}(M),\] where \(\tilde{\psi}(\lambda,t)\) is defined as \[\tilde{\psi}(\lambda,t)=\sqrt{\frac{\beta_1(N_t(s,a),\lambda)}{2N_{t}(s,a)}}.\] Now, using also the other event \({\cal E}_{T}^2\), we can also use the fact that \(N_t(s,a)\) is lower bounded by \(\phi(t,\lambda)= \frac{1}{2}\sum_{k=1}^{\lfloor\frac{t}{m}\rfloor} \frac{\eta_m}{(km)^{\alpha+\beta}} - \log\frac{SA}{\lambda}\). Additionally, we note that \(\tilde{\psi}(\lambda,t)\) is decreasing with respect to \(N_t\) for \[N_t(s,a) \geq \max\left\{1,\frac{S-1}{e}\exp\left(\frac{1}{S} - \frac{1}{S-1}\log(SA/\lambda)\right)-e\right\}.\] Combining these two facts with Lemma 12, we have that for \(t\geq C\) \[\tilde{\psi}(\lambda,t)\leq \psi(t,\lambda)=\sqrt{\frac{\beta_1(\phi(t,\lambda),\lambda)}{2\phi(t,\lambda)}},\] and thus \(M_t\in B_{\tilde{\psi}(\lambda,t)}(M)\subset B_{\psi(t,\lambda)}(M)\). ◻

Proof. For proof and further discussion see Appendix 9. ◻

Proof. This follows similarly to [7]. For completion we rewrite the minor modification to their proof here.
First, recall the definitions \(\pi^\star(a|s) = \omega^\star(a|s)/\sum_b \omega^\star(b|s)\) and \(\hat{\pi}^\star_t(a|s) = \omega^\star_t(a|s)/\sum_b \omega^\star_t(b|s)\). Under \(\mathcal{E}^{3}_{T}(\lambda)\) using Lemma 19, there exists an MDP-specific constant \(\kappa_M\) such that \[\begin{align} \|\omega_t - \omega^\star\|_1 &\leq \kappa_M \|P_t - P_{\pi^\star}\|_\infty, \\ &\leq \kappa_M \|\pi_t - \pi^\star\|_\infty, \\ &\leq \kappa_M \left[\|\pi_t^\star - \pi^\star\|_\infty + \epsilon_t\right]. \end{align}\]

Then, for \(\sqrt{t}\geq C\), we have \[\|\pi_t^\star - \pi^\star\|_\infty \leq \left\|\frac{1}{t} \sum_{k=1}^t (\hat{\pi}_t^\star - \pi^\star)\right\| \leq \frac{\sqrt{t}}{t} + \xi_{\sqrt{t}} = \frac{1}{\sqrt{t}} + \xi_{\sqrt{t}},\] which concludes the proof of the first and third inequalities of the Lemma. For the second part, we have that \[\begin{align} \|P_t - P_{t-1}\|_\infty &\leq \|P_t - P_{\pi^\star}\|_\infty + \|P_{\pi^\star} - P_{t-1}\|_\infty, \\ &\leq 2 \left(\frac{1}{\sqrt{t-1}} + \xi_{\sqrt{t-1}} + \epsilon_{t-1}\right). \end{align}\] ◻

Proof. This will follow along with the proof of [7] and we will denote \(\omega^*(f) = \mathbb{E}_{z\sim \omega^*}[f(z)]\) and \(\omega_t(f) = \mathbb{E}_{z\sim \omega_t}[f(z)]\). Using [5] we can rewrite the inside of the absolute value of our expression using \(\hat{f}_k\), the solution to the Poisson equation \(f(\cdot) - \omega_{k-1}(f) = [\hat{f}_k - P_k\hat{f}_k](\cdot)\).This is well-defined since the sampling policy at each round is a mixture with a forcing policy (e.g., the uniform policy), which ensures that the induced Markov chain is ergodic. Consequently, the Poisson equation admits a solution, allowing us to proceed with the decomposition.. In particular, we can write

\[\frac{\sum_{k=\sqrt{t}+1}^tf(z_k) - \omega_{k-1}(f)}{t} = \frac{1}{t}\sum_{k=\sqrt{t}}^t \hat{f}_{k-1}(z_k) - P_{k-1}\hat{f}_{k-1}(z_k) = M_t+C_t+R_t\] where \[\begin{align} M_t &:= \frac{\sum_{k = \sqrt{t} + 1}^{t} \hat{f}_{k-1}(z_k) - P_{k-1} \hat{f}_{k-1}(z_{k-1})}{t},\\ C_t &:= \frac{\sum_{k = \sqrt{t} + 1}^{t} P_k \hat{f}_k(z_k) - P_{k-1} \hat{f}_{k-1}(z_k)}{t},\\ R_t &:= \frac{P_{\sqrt{t}} \hat{f}_{\sqrt{t}}(z_{\sqrt{t}}) - P_t \hat{f}_t(z_t)}{t}. \end{align}\] Hence, we try to bound these three terms in order to complete the proof.
Following similar ideas from [7], we can bound the terms in this decomposition and relate them to the quantity \(L(\epsilon,\pi)\). This quantity captures the dependence of our bounds on the deviation of the sampling policy from the target allocation, as well as the level of forced exploration. For now, we treat it as an abstract complexity term; its precise definition and interpretation, along with non-asymptotic bounds on its value can be found later in Appendix 8.4.1.

these we can first note that for \(k \geq \sqrt{t}\) and using Corollary 2 we have

\[\epsilon_k \leq \min\{1,\kappa_k(\lambda)\} \leq \min\{1,\kappa_{\sqrt{t}}(\lambda)\}\]

and from Corollary 6 we have that for \(k\geq \sqrt{t}\geq C\) \[||\pi^*_k - \pi^*||_\infty \leq \frac{1}{\sqrt{k}} + \xi_{\sqrt{k}} \leq t^{-\frac{1}{4}} + \xi_{t^{\frac{1}{4}}}.\]

Then for \(k \geq \sqrt{t}\), we can relate this to the quantity \(L_k = L(\epsilon_t,\pi_t)\) \[\label{eqn95L95tilde95definition} L_k \leq \tilde{L}_t \leq \sup\, \left\{L(\epsilon,\pi) \,:\, |\epsilon|\leq \min\{1,\kappa_{\sqrt{t}}(\lambda)\}, ||\pi^* - \pi||_\infty\leq t^{-\frac{1}{4}} + \xi_{t^{\frac{1}{4}}}\right\}\tag{3}\] where we define \(\tilde{L}_t := \sup_{k\in [\sqrt{t},t]} L_k\). See section 8.4.1 for the relevant definitions and a more thorough analysis on the behaviour of \(\tilde{L}_t\).

8.4.0.1 Bounding \(M_t\):

We can use the fact that \(tM_t\) is a martingale such that for \(S_k = kM_k\) we have \(|S_k - S_{k-1}| \leq 2L_{k-1}\leq 2\tilde{L}_{k-1}\), and hence for \(\sqrt{t}\geq C\) we can apply the Azuma-Hoeffding inequality to attain \[\mathbb{P}(|M_t| \geq 2\tilde{L}_t g(t)) \leq 2\exp\left(-t(g(t))^2\right).\] Hence, by setting \(g(t) = t^{-\frac{1}{4}}\) we have \[\mathbb{P}(|M_t| \geq 2\tilde{L}_t t^{-\frac{1}{4}}) \leq 2\exp\left(-t^{\frac{1}{2}}\right).\]

8.4.0.2 Bounding \(C_t\):

For \(\sqrt{t}\geq C\) we have \[\begin{align} C_t &\leq (1/t) \sum_{k = \sqrt{t} + 1}^{t} L_k \left[\|\omega_k - \omega_{k-1}\| + L_{k-1} \|P_k - P_{k-1}\|_\infty \right], \\ &\leq (1/t) \sum_{k = \sqrt{t} + 1}^{t} L_k \left[ \|\omega_k - \omega_{k-1}\| + 2L_{k-1} \left(\frac{1}{\sqrt{k-1}} + \xi_{\sqrt{k-1}} + \epsilon_{k-1}\right) \right], \\ &\leq (1/t) \sum_{k = \sqrt{t} + 1}^{t} L_k \left[ \|\omega_k - \omega^\star\| + \|\omega_{k-1} - \omega^\star\| + 2L_{k-1} \left(\frac{1}{\sqrt{k-1}} + \xi_{\sqrt{k-1}} + \epsilon_{k-1}\right) \right], \\ &\leq (1/t) \sum_{k = \sqrt{t} + 1}^{t} 2L_k \left[ \kappa_M \left(\frac{1}{\sqrt{k-1}} + \xi_{\sqrt{k-1}} + \epsilon_{k-1}\right) + L_{k-1}\left(\frac{1}{\sqrt{k-1}} + \xi_{\sqrt{k-1}} + \epsilon_{k-1}\right) \right], \\ &\leq 2(1/t) \sum_{k = \sqrt{t} + 1}^{t} \tilde{L}_{t} (\kappa_M + \tilde{L}_{t}) \left(\frac{1}{\sqrt{k-1}} + \xi_{\sqrt{k-1}} + \epsilon_{k-1}\right), \\ &\leq 2\tilde{L}_{t} (\kappa_M + \tilde{L}_{t}) \left[ t^{-\frac{1}{4}} + \xi_{t^{\frac{1}{4}}} + \epsilon_{\sqrt{t}} \right]. \end{align}\] Here the second inequality comes from Corollary 6. The third inequality uses the triangle inequality. The fourth inequality uses Corollary 6 again. The penultimate line comes from the definition of \(\tilde{L}_t\) in 3 .

8.4.0.3 Bounding \(R_t\):

We have, again by similar arguments to [7] and [5], that \[\begin{align} |R_t| &\leq \frac{\|f\|_\infty (L_{\sqrt{t}}+L_t)}{t}\\ &\leq \frac{ (L_{\sqrt{t}}+L_t)}{t}\\ &\leq \frac{ 2\tilde{L}_{t}}{t} \end{align}\] ◻

Proof. We can first rewrite the term of interest as \[\frac{\sum_{k=1}^t f(z_k) - \omega_{k-1}(f)}{t} = \frac{\sum_{k=1}^{\sqrt{t}} f(z_k) - \omega_{k-1}(f)}{t} + \frac{\sum_{k=\sqrt{t}+1}^t f(z_k) - \omega_{k-1}(f)}{t}.\]

The second term here can be bounded using Proposition 9. Then, since \(f(z_k)\in[0,1]\) and \(\omega_{k-1}(f) \in [0,1]\) we can immediately bound the first term

\[\frac{\sum_{k=1}^{\sqrt{t}} f(z_k) - \omega_{k-1}(f)}{t} \leq \frac{\sum_{k=1}^{\sqrt{t}} 1}{t} \leq t^{-\frac{1}{2}}.\] The proof is then complete. ◻

Proof. We firstly have from the above proposition, by choosing \(f\) to be the indicator that the state and action in round \(t\), \(z_t\), is equal to \(s\) and \(a\), that \[\label{eqn95Nt95vs95wk} \mathbb{P}\left(\exists (s,a) \in \mathcal{Z}, \, \bigg|\frac{N_t(s,a) - \sum_{k=1}^t \omega_{k-1}(s,a)}{t}\bigg| \geq \ell''(t) \Bigg| \mathcal{E}_T^1\cap\mathcal{E}_{T}^2\right) \leq 2SA\exp\left(-t^{\frac{1}{2}}\right).\tag{4}\] What is left is to compare the empirical visitation frequency with the sum of approximated optimal allocations up to time \(t\). To do so, we firstly note that, by Lemma 19, we can almost surely bound the differences for all \(t \geq 1\) \[\begin{align} \|\omega_t - \omega^*_t\|_\infty &\leq \|P_{\pi_t} - P_{\pi^*_t}\|_{\infty} \\ &\leq \|\pi_t - \pi_t^*\|_{\infty}\\ &\leq \epsilon_t \end{align}\] Hence we have that \[\label{eqn95diff95sum95w95vs95wstar} \bigg|\frac{\sum_{k=1}^t \omega_{k-1}(s,a) - \omega^*_{k-1}(s,a)}{t}\bigg| \leq \frac{\sqrt{t}}{t} + \frac{\sum_{k=\sqrt{t}}^{t-2}\epsilon_k}{t}.\tag{5}\] As a consequence, we can plug this bound from equation 5 into the concentration from equation 4 using the triangle inequality to obtain the desired final concentration. ◻

Proof. For this, we can simply ensure \(\sigma_t \in (0,1)\). We can show this with the following two statements.

Statement 1: \([(1 - \epsilon_t) A \min_{s,a} \pi_t(a|s)]^{r_0} + \epsilon_t^{\frac{r_0(\alpha+\beta)}{\alpha}} \in (0,1)\). Which can be shown as follows, using that \(\epsilon_t \in (0,1)\). \[\begin{align} &[(1 - \epsilon_t) A \min_{s,a} \pi_t(a|s)]^{r_0} + \epsilon_t^{\frac{r_0(\alpha+\beta)}{\alpha}}\\ & \leq [(1 - \epsilon_t) ]^{r_0} + \epsilon_t^{\frac{r_0(\alpha+\beta)}{\alpha}}\\ &\leq (1 - \epsilon_t) + \epsilon_t^{\frac{r_0(\alpha+\beta)}{\alpha}}\\ &<1 \end{align}\] Similarly, we can show the lower bound since \[\begin{align} &[(1 - \epsilon_t) A \min_{s,a} \pi_t(a|s)]^{r_0} + \epsilon_t^{\frac{r_0(\alpha+\beta)}{\alpha}}\\ & \geq \epsilon_t^{\frac{r_0(\alpha+\beta)}{\alpha}}\\ &>0 . \end{align}\]

Statement 2: \(\sigma_u \in (0,1]\). See statement 2 of Lemma 7 ◻

Proof. Note that, since \(\kappa_{\sqrt{t}}\rightarrow0\) as \(t\rightarrow\infty\), we have \(\min\{1,\kappa_{\sqrt{t}}(\lambda)\} \rightarrow 0\) as \(t\rightarrow\infty\). Hence, in the conditions of \(\tilde{L}_t\) in it’s definition, we have \(\epsilon\rightarrow0\) as \(t\rightarrow\infty\).
Similarly, we have that \(t^{-\frac{1}{4}} + \xi_{t^{\frac{1}{4}}} \rightarrow 0\) as \(t\rightarrow\infty\), hence in the conditions of \(\tilde{L}_t\) in it’s definition, we have \(\pi \rightarrow \pi^*\).
Putting these two observations together, we have \[\begin{align} \limsup_{t\rightarrow\infty} \tilde{L}_t &= \sup\left\{L(\epsilon,\pi) \,:\, |\epsilon|\leq 0, ||\pi^* - \pi||_\infty\leq 0\right\}\\ &= L(0,\pi^*)\\ &= 2\left(\left(1-\theta_0^{1/r_0}\right)\theta_0\right)^{-1}\\ &< \infty \end{align}\]

Here the final line of boundedness comes from the fact that \(\theta_0 \in (0,1)\), which is a consequence of \(\sigma_0 \in (0,1)\). To prove \(\sigma_0 \in (0,1)\), we can use the following two statements.

Statement 1: \(A\min_{s,a}\pi^*(a|s) \in (0,1)\). Under Assumption 3 and the auxiliary Lemma 19, we know that the optimal weights \(w^*>0\) are strictly greater than zero. Hence, by the definition of the optimal policy, we have \(\min_{s,a}\pi^*(a|s)>0\). Now, the strict upper bound \(A\min_{s,a}\pi^*(a|s) < 1\) is also true as due to the uniqueness assumption on our optimal policy \(\pi^*(a|s)\). This is because \(A\min_{s,a}\pi^*(a|s) = 1\) only occurs when \(\pi^*(a|s) = 1/A \quad\forall a,s\). However, when this uniform policy is optimal in a communicating MDP, we have that any policy is optimal and therefore \(\pi^*\) is not unique (see Lemma 23).

Statement 2: \(\sigma_u \in (0,1]\). The upper bound is clear by contradiction, namely suppose that \[\sigma_u = \min_{z',z \in \mathcal{Z}} P_u^{r_0}(z'|z)/ \omega_u(z')>1\] Then, this tells us that \[\begin{align} \forall z,z' \quad P_u^{r_0}(z'|z) &> \omega_u(z')\\ \Longrightarrow \sum_{z'}P_u^{r_0}(z'|z) &> \sum_{z'}\omega_u(z')\\ \Longrightarrow 1 &> 1 \end{align}\] which is a contradiction. The lower bound is also clear by the definition of \(r_0\) (i.e. the first index in which every entry of \(P_u^{r_0}(z'|z)>0\) is strictly positive). ◻

Proof. Recall that \(\tilde{L}_t = \sup_{k\in[\sqrt{t},t]} L_k = L(\epsilon_k,\pi_k)\). By observing that by definition of \(L\) and \(\theta\), and since \(1-(1-x)^y\geq xy\) for any \(x,y\in (0,1)\), we have \[\begin{align} L(\epsilon,\pi) &\leq 2\left[\left(1-(1-\sigma)^\frac{1}{r_0}\right)(1-\sigma)\right]^{-1}\nonumber\\ &\leq 2\left[\frac{\sigma}{r_0}(1-\sigma)\right]^{-1}\label{eqn95L95simplification} \end{align}\tag{6}\]

All that is left is to upper and lower bound \(\sigma_k\) from times \(\sqrt{t}\) to \(t\). Let’s start with the upper bound. \[\begin{align} \sup_{k\in[\sqrt{t},t]} \sigma(\epsilon_k,\pi_k) &\leq \left(\left[(1-\epsilon_t)A\min_{s,a} (\pi^*(a|s) + t^{-\frac{1}{4}} + \xi_{t^{\frac{1}{4}}})\right]^{r_0} + \epsilon_{\sqrt{t}}^{\frac{r_0(\alpha+\beta)}{\alpha}}\right)\sigma_u\\ &\leq \sigma_u (1-\epsilon_t)^{r_0}A^{r_0}\left[\min_{s,a}\pi^*(a|s) + t^{-\frac{1}{4}}+\xi_{t^{\frac{1}{4}}}\right] + \sigma_u\epsilon_{\sqrt{t}}^{\frac{r_0(\alpha+\beta)}{\alpha}}\\ &\leq 2^{r_0-1}\sigma_u(1-\epsilon_t)^{r_0}A^{r_0}\left(\left[\min_{s,a}\pi^*(a|s)\right]^{r_0} + \left[t^{-\frac{1}{4}}+\xi_{t^{\frac{1}{4}}}\right]^{r_0}\right)+ \sigma_u\epsilon_{\sqrt{t}}^{\frac{r_0(\alpha+\beta)}{\alpha}}\\ \end{align}\] where the penultime inequality comes from the fact that for \(x,y>0\) and \(z\geq 1\) we have \((x+y)^z \leq 2^{z-1}(x^z+y^z)\).
Now we provide a lower bound \[\begin{align} \inf_{k\in[\sqrt{t},t]} \sigma(\epsilon_k,\pi_k) &\geq \left(\left[(1-\epsilon_{\sqrt{t}})A\min_{s,a} (\pi^*(a|s) - t^{-\frac{1}{4}} - \xi_{t^{\frac{1}{4}}})\right]^{r_0} + \epsilon_{t}^{\frac{r_0(\alpha+\beta)}{\alpha}}\right)\sigma_u\\ &\leq \sigma_u (1-\epsilon_{\sqrt{t}})^{r_0}A^{r_0}\left[\min_{s,a}\pi^*(a|s) - t^{-\frac{1}{4}}-\xi_{t^{\frac{1}{4}}}\right]^{r_0} + \sigma_u\epsilon_{t}^{\frac{r_0(\alpha+\beta)}{\alpha}}\\ \end{align}\] Plugging the upper and lower bound into equation 6 gives us the desired result. ◻

Proof. Suppose that the NaS algorithm has not yet stopped at time \(t\). Then, by definition of our stopping time, we have \[\begin{align} \beta(t,\delta) &\geq tT(M_t,N_t/t)^{-1} \\ &= t\inf_{M'\in \text{Alt}(M_t)} \sum_{s,a} \frac{N_t(s,a)}{t} {\rm KL}_{M_t|M'}(s,a)\\ &= \inf_{M'\in \text{Alt}(M_t)} \sum_{s,a} N_t(s,a) KL_{M_t|M'}(s,a)\\ \intertext{Since N_t(s,a) \approx \sum_{j=1}^t \omega_j (s,a), we have} &\geq \inf_{M'\in \text{Alt}(M_t)} \sum_{s,a} \left(\sum_{j=1}^t \omega_j (s,a)\right) KL_{M_t|M'}(s,a) + \ell_1\\ \intertext{where we formalize this with an explicit selection of \ell_1 in Lemma \ref{lemma95bounding95l1}. Since taking an infimum over each term of the sum is smaller than the infimum over the whole sum, we have} &\geq \sum_{j=1}^t \inf_{M'\in \text{Alt}(M_t)} \sum_{s,a} \omega_j (s,a) KL_{M_t|M'}(s,a) + \ell_1\tag{8}\\ \intertext{By a supremum argument, we can change the set over which we take the infimum. In particular, if we have that M_t \in Alt(M_j) then the sum in \eqref{eqn95swapping95first95alt95to95Mj} is equal to zero and the inequality holds trivially. If M_t \notin Alt(M_j) then either Alt(M_t)=Alt(M_j) or M_j is not absolutely continuous with respect to M_t. By Assumption \ref{assumption95P95in95G95bounded95ratio} we have that M_t\ll M_j, therefore we have that Alt(M_t)=Alt(M_j). Hence line \eqref{eqn95swapping95first95alt95to95Mj} holds by equality. (Note, more formally we can apply Lemma \ref{lemma95swapping95alternative95sets95useful} here an select M_j in the supremum to get the lower bound in \eqref{eqn95swapping95first95alt95to95Mj}.)} &\geq \sum_{j=1}^t \inf_{M'\in \text{Alt}(M_j)} \sum_{s,a} \omega_j (s,a) KL_{M_t|M'}(s,a)+\ell_1\tag{9}\\ \intertext{Since M_t \approx M and M_j \approx M under our good event, we have M_t \approx M_j. Hence } &\geq \sum_{j=\sqrt{t}}^t \inf_{M'\in \text{Alt}(M_j)} \sum_{s,a} \omega_j (s,a) KL_{M_j|M'}(s,a) + \ell_1 + \ell_2\tag{10}\\ \intertext{where we formalize this in Lemma \ref{lemma95l295bound} with an explicit derivation of \ell_2. If we use the definition of \omega_j(s,a)\in\mathop{\mathrm{arg\,max}}_{\tilde{\omega}\in \Omega(M_j)}\inf_{M'\in \text{Alt}(M_j)} \sum_{s,a} \tilde{\omega}(s,a) KL_{M_j|M'}(s,a), then we have} & =\sum_{j=\sqrt{t}}^t\sup_{\tilde{\omega}\in \Omega(M_j)}\inf_{M'\in \text{Alt}(M_j)} \sum_{s,a} \tilde{\omega}(s,a) KL_{M_j|M'}(s,a) + \ell_1 + \ell_2 \\ \intertext{Then, again using a similar argument for swapping the alternative sets, namely using Lemma \ref{lemma95swapping95alternative95sets95useful}, we can do the following supremum argument} & =\sum_{j=\sqrt{t}}^t \sup_{M''\,:\, M_j \ll M''} \sup_{\tilde{\omega}\in \Omega(M_j)} \inf_{M'\in \text{Alt}(M'')} \sum_{s,a} \tilde{\omega}(s,a) KL_{M_j|M'}(s,a) + \ell_1 + \ell_2 \\ \intertext{We can then choose M''=M in the set over which the supremum is acting, to get} & \geq \sum_{j=\sqrt{t}}^t \sup_{\tilde{\omega}\in \Omega(M_j)} \inf_{M'\in \text{Alt}(M)} \sum_{s,a} \tilde{\omega}(s,a) KL_{M_j|M'}(s,a) + \ell_1 + \ell_2 \\ \intertext{Then since M_j \approx M, we should also have that the sets (over which the supremum holds) are similar \Omega(M_j)\approx \Omega(M). Hence } & \geq \sum_{j=\sqrt{t}}^t \sup_{\tilde{\omega}\in \Omega(M)} \inf_{M'\in \text{Alt}(M)} \sum_{s,a} \tilde{\omega}_j(s,a) KL_{M|M'}(s,a) + \ell_1 + \ell_2 + \ell_3 \tag{11}\\ \intertext{where this is formalized in Lemma \ref{lemma95l395bound} and \ell_3 is explicitly dervied. This can then, by definition, be related directly to T_o(M) as} &= (t-\sqrt{t}) T_o(M)^{-1}+ \ell_1 + \ell_2 +\ell_3 \nonumber \end{align}\]

Hence, to complete the proof of the non-asymptotic lower bound, we simply need to bound \(\ell_1, \ell_2\) and \(\ell_3\) before putting everything together, which is done explicitly in Lemmas 9, 10, and 11 below. The proof is then complete. ◻

Proof. First let \[M^* \in \mathop{\mathrm{arg\,min}}_{M'\in \text{Alt}(\hat{M}_t)} \sum_{s,a} N_t(s,a) KL_{\hat{M}_t|M'}(s,a)\] Then we have \[\begin{align} &\inf_{M'\in \text{Alt}(\hat{M}_t)} \sum_{s,a} N_t(s,a) KL_{\hat{M}_t|M'}(s,a)\\ &=\sum_{s,a} N_t(s,a) KL_{\hat{M}_t|M^*}(s,a)\\ & = \sum_{s,a} \left[\left(\sum_{j=1}^t \omega_j (s,a)\right) - \left(\sum_{j=1}^t \omega_j (s,a)- N_t(s,a)\right)\right] KL_{\hat{M}_t|M^*}(s,a)\\ & = \sum_{s,a} \left[\left(\sum_{j=1}^t \omega_j (s,a)\right)\right] KL_{\hat{M}_t|M^*}(s,a) - \sum_{s,a} \left[\left(\sum_{j=1}^t \omega_j (s,a)- N_t(s,a)\right)\right] KL_{\hat{M}_t|M^*} (s,a) \nonumber\\ \intertext{By the definition of the concentration event \mathcal{E}_t^5, the second term can be bounded as} & \geq \sum_{s,a} \sum_{j=1}^t \omega_j (s,a) KL_{\hat{M}_t|M^*}(s,a) - t\ell(t)\sum_{s,a} KL_{\hat{M}_t|M^*} (s,a)\\ \intertext{The first term can be lower bounded by choosing instead an M' which minimises the first sum.} & \geq \inf_{M'\in \text{Alt}(\hat{M}_t)}\sum_{s,a} \sum_{j=1}^t \omega_j (s,a) KL_{\hat{M}_t|M'}(s,a) - \ell(t)\sum_{s,a} KL_{\hat{M}_t|M^*} (s,a) \tag{12}\\ & \geq \inf_{M'\in \text{Alt}(\hat{M}_t)}\sum_{s,a} \sum_{j=1}^t \omega_j (s,a) KL_{\hat{M}_t|M'}(s,a) - 2SAt\,\ell(t) \log(L) \tag{13} \end{align}\] Here the final line comes from our Assumption 2 and noticing that for any pair \(P, P' \in G_\mu(L)\) that \[\begin{align} {\rm KL}(P,P') &= \mathbb{E}_{x \sim P}\left[\log \frac{P(s)}{P'(x)}\right]\\ &= \mathbb{E}_{x \sim P}\left[\log \frac{P(s)}{P'(x)} \frac{\mu(s)}{\mu(s)}\right]\\ &= \mathbb{E}_{x \sim P}\left[\log \frac{\mu}{P'} \frac{P}{\mu}(s)\right]\\ &= \mathbb{E}_{x \sim P}\left[\log \frac{\mu}{P'}+ \log \frac{P}{\mu}(s)\right]\\ &\leq 2\log(L). \end{align}\] ◻

Proof. Consider the difference \[\begin{align} & \sum_{j=1}^t \inf_{M'\in \text{Alt}(M_j)} \sum_{s,a} \omega_j (s,a) KL_{M_j|M'}(s,a) - \sum_{j=1}^t \inf_{M'\in \text{Alt}(M_j)} \sum_{s,a} \omega_j (s,a) KL_{M_t|M'}(s,a)\\ &\leq \sum_{j=1}^t \sum_{s,a} \omega_j (s,a)\sup_{M'\in \text{Alt}(M_j)} KL_{M_j|M'}(s,a) - KL_{M_t|M'}(s,a)\\ \intertext{Since the weights are always upper bounded by 1 we have} &\leq \sum_{j=1}^t \sum_{s,a} \sup_{M'\in \text{Alt}(M_j) \cup \text{Alt}(M_t)}KL_{M_j|M'}(s,a) - KL_{M_t|M'}(s,a)\\ \intertext{By our Lipschitz Lemma \ref{lemma:KL95on95G95is95lipschitz} we have} &\leq \sum_{j=1}^t \sum_{s,a} S(1+2\log L)\|M_t - M_j\|_1\\ &\leq \sum_{j=1}^t \sum_{s,a} S(1+2\log L)\left(\|M_t - M\|_1 + \|M - M_j\|_1\right) \end{align}\] Hence, we can always select \(\ell_2\) to guarantee our desired inequality, as stated. ◻

Proof. Consider the quantity \[\begin{align} & \sum_{j=\sqrt{t}}^t \sup_{\tilde{\omega}\in \Omega(M)} \inf_{M'\in \text{Alt}(M)} \sum_{s,a} \tilde{\omega}_j(s,a) KL_{M|M'}(s,a)\nonumber\\ &\qquad - \sum_{j=\sqrt{t}}^t \sup_{\tilde{\omega}\in \Omega(M_j)} \inf_{M'\in \text{Alt}(M)} \sum_{s,a} \tilde{\omega}_j(s,a) KL_{M_j|M'}(s,a)\\ \intertext{If we denote \omega^1_j and \omega^2_j as the optimizing choice for the first and second supremum, then we can rewrite this as} &=\sum_{j=\sqrt{t}}^t \inf_{M'\in \text{Alt}(M)} \sum_{s,a} \omega^1_j(s,a) KL_{M|M'}(s,a)\nonumber\\ &\qquad - \sum_{j=\sqrt{t}}^t \inf_{M'\in \text{Alt}(M)} \sum_{s,a} \omega^2_j(s,a) KL_{M_j|M'}(s,a)\\ &\leq \sum_{j=\sqrt{t}}^t (\omega^1_j(s,a)- \omega^2_j(s,a)) \sup_{M'\in \text{Alt}(M)} \sum_{s,a} KL_{M|M'}(s,a)- KL_{M_j|M'}(s,a)\\ &\leq \sum_{j=\sqrt{t}}^t \sum_{s,a} S(1+2\log L) \| M-M_j\|_1 \end{align}\] Hence we can always select an \(\ell_3\) to gaurantee the desired inequality, as stated. Note that for the final inequality we use that KL is Lipschitz in \(G_\mu(L)\), as formalized in Lemma 16. ◻

Proof. Let’s prove the lower bound for \(\phi(t, \lambda)\) first. Note that the quantity \[\frac{1}{k^{\alpha+\beta}}\] is decreasing in \(k\). Hence we can lower bound the sum \[\begin{align} \sum_{k=1}^{\lfloor\frac{t}{m}\rfloor}\frac{1}{k^{\alpha+\beta}} &\geq \int_{1}^{\lfloor\frac{t}{m}\rfloor} \frac{1}{k^{\alpha+\beta}} dk\\ &= \frac{1}{1-(\alpha+\beta)}\left(\bigg\lfloor\frac{t}{m}\bigg\rfloor^{1-(\alpha+\beta)} -1\right) \end{align}\] and the proof of the lower bound is then complete. To prove the upper bound, note that since we are assuming \(\alpha+\beta\geq 0\) then we have that \[\frac{1}{(km)^{\alpha+\beta}} \leq \frac{1}{(km)^{0}} = 1\] Hence \[\frac{1}{2}\sum_{k=1}^{\lfloor\frac{t}{m}\rfloor} \frac{\eta_m}{(km)^{\alpha+\beta}} \leq \frac{1}{2}\sum_{k=1}^{\lfloor\frac{t}{m}\rfloor} \eta_m = \frac{\eta_m}{2}\lfloor\frac{t}{m}\rfloor\] as required. ◻

Proof. Recall by definition that, under event \(\mathcal{E}^4_t\) (which holds under \(\mathcal{E}^1_t \cap \mathcal{E}^2_t\), as in Lemma 4), we have for all \(j\geq C\) that \[\| M-M_j\|_1 \leq \psi(j,\lambda):=\sqrt{\frac{\beta_1(\phi(j,\lambda),\lambda)}{2\phi(j,\lambda)}}\]

Hence, since \(\beta_1\) is increasing in \(\phi\) which is increasing in \(t\), we have \[\begin{align} \sum_{j=C}^t \| M-M_j\|_1 &\leq 2\max\{J,C\}+\sum_{j=\max\{J,C\}}^t \| M-M_j\|_1\\ &\leq 2\max\{J,C\}+\sum_{j=\max\{J,C\}}^t \| M-M_j\|_1\\ &\leq 2\max\{J,C\}+\sum_{j=\max\{J,C\}}^t \sqrt{\frac{\beta_1(\phi(j,\lambda),\lambda)}{2\phi(j,\lambda)}}\\ &\leq 2\max\{J,C\}+\sqrt{\beta_1(\phi(t,\lambda),\lambda)} \sum_{j=\max\{J,C\}}^t \sqrt{\frac{1}{2\phi(j,\lambda)}}\label{eqn95M95sum95lemma95to95simplify} \end{align}\tag{14}\]

Now, if we focus on the final sum of this equation we can then use our lower bound for \(\phi\) in Lemma 12 to get \[\begin{align} \sum_{j=\max\{J,C\}}^t \sqrt{\frac{1}{2\phi(j,\lambda)}}&\leq \sum_{j=\max\{J,C\}}^t \left(\frac{\eta_m}{2m^{\alpha+\beta}\left(1-(\alpha+\beta)\right)}\left(\bigg\lfloor\frac{j}{m}\bigg\rfloor^{1-(\alpha+\beta)} -1\right) - \log\frac{SA}{\lambda}\right)^{-1/2}\\ &\leq \sum_{j=\max\{J,C\}}^t \left(\frac{\eta_m}{2m^{\alpha+\beta}\left(1-(\alpha+\beta)\right)}\left(\left(\frac{j}{2m}\right)^{1-(\alpha+\beta)} -1\right) - \log\frac{SA}{\lambda}\right)^{-1/2}\\ \intertext{If we isolate the j dependent terms and denote the term in this sum as (e_1(j)- e_2)^{-1/2}, then for sufficiently large j\geq J we have that e_1(j) \geq 2e_2. Hence, for j\geq J we have (e_1(j)- e_2)^{-1/2} \leq (e_1(j)/2)^{-1/2}. Hence} &\leq \sum_{j=\max\{J,C\}}^t \left(\frac{\eta_m}{4m^{\alpha+\beta}\left(1-(\alpha+\beta)\right)}\left(\frac{j}{2m}\right)^{1-(\alpha+\beta)} \right)^{-1/2}\\ &= \sum_{j=\max\{J,C\}}^t \sqrt{4m^{\alpha+\beta}\left(1-(\alpha+\beta)\right)/\eta_m} \left(\frac{j}{2m}\right)^{-(1-(\alpha+\beta))/2}\\ &\leq \sqrt{4m^{\alpha+\beta}\left(1-(\alpha+\beta)\right)/\eta_m}\int_{j=0}^{t+1} \left(\frac{j}{2m}\right)^{-(1-(\alpha+\beta))/2}dj\\ &= \left[\frac{\sqrt{4m^{\alpha+\beta}\left(1-(\alpha+\beta)\right)/\eta_m}}{1-(1-(\alpha+\beta))/2} \left(\frac{j}{2m}\right)^{1-(1-(\alpha+\beta))/2}\right]^{j=t+1}_{j=0}\\ &= \frac{\sqrt{16m^{\alpha+\beta}\left(1-(\alpha+\beta)\right)/\eta_m}}{1+(\alpha+\beta)} \left(\frac{t+1}{2m}\right)^{(1+\alpha+\beta)/2} \end{align}\] By substituting this into equation 14 and by using the upper bound for \(\phi\) in Lemma 12, namely that \[\phi(t,\lambda) \leq \frac{\eta_mt}{2m}- \log\frac{SA}{\lambda},\] the proof is then complete. ◻

Proof. There are two cases that occur over the set of \(\{M_2: M_1 \ll M_2\}\) in the supremum here. In particular we can either have that \(M_1 \in Alt(M_2)\) or \(M_1 \notin Alt(M_2)\).

8.5.3.1 Case 1:

Suppose first that \(M_1 \in Alt(M_2)\). In this case, since the allocation always has all non-negative entries, we have that \[\inf_{M'\in \text{Alt}(M_2)} \sum_{s,a} \tilde{\omega}(s,a) KL_{M_1|M'}(s,a) = \sum_{s,a} \tilde{\omega}(s,a) KL_{M_1|M_1}(s,a) = 0.\]

8.5.3.2 Case 2:

Now, instead suppose that \(M_1 \notin Alt(M_2)\). In this case, by the definition of the alternative sets in 1 , we have that either \(Alt(M_1) = Alt(M_2)\) or \(M_1\) is not absolutely continuous with respect to \(M_2\). However, by the definition of the supremum in our lemma statement here we know \(M_1 \ll M_2\), hence we know \[M_1 \notin Alt(M_2)\Longrightarrow Alt(M_1) = Alt(M_2).\] Hence we have \[\inf_{M'\in \text{Alt}(M_2)} \sum_{s,a} \tilde{\omega}(s,a) KL_{M_1|M'}(s,a) = \inf_{M'\in \text{Alt}(M_1)} \sum_{s,a} \tilde{\omega}(s,a) KL_{M_1|M'}(s,a).\]

8.5.3.3 Combining cases:

Then by considering the supremum of \(M''\) over \(M_{all}\) as simply the supremum over the union of the two sets \[\{M_2: M_1 \ll M_2\} = \{M_2: M_1 \ll M_2, M_1 \in Alt(M_2)\} \cup \{M_2: M_1 \ll M_2, M_1 \notin Alt(M_2)\},\] the proof is complete by considering the right hand side of our lemma statement \[\begin{align} \sup_{M_2: M_1 \ll M_2}\inf_{M'\in \text{Alt}(M_2)} \sum_{s,a} \tilde{\omega}(s,a) KL_{M_1|M'}(s,a) &=\max \left\{0,\inf_{M'\in \text{Alt}(M_1)} \sum_{s,a} \tilde{\omega}(s,a) KL_{M_1|M'}(s,a)\right\}\\ &= \inf_{M'\in \text{Alt}(M_1)} \sum_{s,a} \tilde{\omega}(s,a) KL_{M_1|M'}(s,a), \end{align}\] since \(\inf_{M'\in \text{Alt}(M_1)} \sum_{s,a} \tilde{\omega}(s,a) KL_{M_1|M'}(s,a) \geq 0\). The proof is then complete. ◻

Proof. Let \[\tau_\delta^{\mathrm{ub}} := \inf\left\{ t\in\mathbb{N}: b(t,\delta) < (t-\sqrt t)T(M)^{-1}-\ell_0(t) \right\}.\] By Theorem 5, \[\mathbb{E}_M[\tau_\delta]\le \tau_\delta^{\mathrm{ub}}+7.\] It is therefore enough to upper bound \(\tau_\delta^{\mathrm{ub}}\).

By definition, for any time \(t<\tau_\delta^{\mathrm{ub}}\), the stopping inequality has not yet been satisfied. Hence \[b(t,\delta) \ge (t-\sqrt t)T(M)^{-1}-\ell_0(t).\] Equivalently, \[t \le \sqrt t + T(M)b(t,\delta) + T(M)\ell_0(t).\] Using the assumed upper bound on the threshold gives \[t \le \sqrt t + T(M)\Bigl(c_0L_\delta+c_1\log t+c_2\Bigr) + T(M)\ell_0(t).\]

We now simplify \(\ell_0(t)\) under polynomial sharpness. From Theorem 5, \[\begin{align} \ell_0(t) = \widetilde{\mathcal{O}}\bigg( &S^{\frac{7}{2}}A\log(L)m^{-\frac{1}{2}}\eta_m^{-\frac{1}{2}} t^{\frac{1+\alpha+\beta}{2}} \\ &+ t\log(L)(\widetilde{L}+\kappa_M)\widetilde{L} \bigg[ t^{-\frac{1}{4}} \\ &\qquad\qquad + \frac{A}{\underline{\rho}_M} \varphi_M^{\frac{1}{2}}\left( \frac{ S^{\frac{3}{2}}m^{\frac{1}{2}}A\log(L)(S^2+\kappa_\Omega) }{ \eta_m^{\frac{1}{2}}t^{\frac{1-(\alpha+\beta)}{4}} } \right) \\ &\qquad\qquad + \frac{m^\alpha}{ t^{\alpha(1-(\alpha+\beta))/2}A^\alpha\eta_m^\alpha } \bigg] \bigg). \end{align}\] The first term is \[A_1 t^{r_1}, \qquad r_1=\frac{1+\alpha+\beta}{2}.\] The first term inside the bracket contributes \[tA_2t^{-1/4} = A_2t^{3/4} = A_2t^{r_2}, \qquad r_2=\frac{3}{4}.\] For the sharpness term, polynomial sharpness gives \[\begin{align} &tA_2 \frac{A}{\underline{\rho}_M} \varphi_M^{\frac{1}{2}}\left( \frac{ S^{\frac{3}{2}}m^{\frac{1}{2}}A\log(L)(S^2+\kappa_\Omega) }{ \eta_m^{\frac{1}{2}}t^{\frac{1-(\alpha+\beta)}{4}} } \right) \\ &\le tA_2 \frac{A }{\underline{\rho}_M} C_{\varphi,p} \left( \frac{ S^{\frac{3}{2}}m^{\frac{1}{2}}A\log(L)(S^2+\kappa_\Omega) }{ \eta_m^{\frac{1}{2}}t^{\frac{1-(\alpha+\beta)}{4}} } \right)^p \\ &= A_3^{(p)} t^{1-\frac{p(1-(\alpha+\beta))}{4}} = A_3^{(p)}t^{r_3^{(p)}}. \end{align}\] If \(r_3^{(p)}<0\), then for all \(t\ge1\) we have \(t^{r_3^{(p)}}\le1\), and hence this term is bounded by \(A_3^{(p)}=A_3^{(p)}t^0\). This is why we use \[\bar r_3^{(p)}:=\max\{0,r_3^{(p)}\}.\] Finally, the last term inside the bracket contributes \[tA_2 \frac{m^\alpha}{ t^{\alpha(1-(\alpha+\beta))/2}A^\alpha\eta_m^\alpha } = A_4 t^{1-\frac{\alpha(1-(\alpha+\beta))}{2}} = A_4t^{r_4}.\] Combining the preceding displays, \[\ell_0(t) = \widetilde{\mathcal{O}}\left( A_1t^{r_1} + A_2t^{r_2} + A_3^{(p)}t^{\bar r_3^{(p)}} + A_4t^{r_4} \right).\] Therefore, for every \(t<\tau_\delta^{\mathrm{ub}}\), \[\begin{align} t \le\;& T(M)\Bigl(c_0L_\delta+c_1\log t+c_2\Bigr) + \sqrt t \\ &+ \widetilde{\mathcal{O}}\left( T(M)A_1t^{r_1} + T(M)A_2t^{r_2} + T(M)A_3^{(p)}t^{\bar r_3^{(p)}} + T(M)A_4t^{r_4} \right). \end{align}\]

We next record that all powers appearing above are strictly sublinear. Since \(\alpha+\beta<1\), \[r_1=\frac{1+\alpha+\beta}{2}<1, \qquad r_2=\frac{3}{4}<1.\] Also, \[r_4 = 1-\frac{\alpha(1-(\alpha+\beta))}{2} <1,\] because \(\alpha>0\) and \(1-(\alpha+\beta)>0\). Finally, since \(p>0\), \[r_3^{(p)} = 1-\frac{p(1-(\alpha+\beta))}{4} <1.\] Thus also \(\bar r_3^{(p)}<1\).

It remains to invert the preceding inequality. Since every exponent is strictly smaller than one, the sublinear terms can be evaluated at the leading scale \[t\asymp T(M)\log(1/\delta).\] More explicitly, the logarithmic term contributes only \[T(M)c_1\log\bigl(eT(M)(1+L_\delta)\bigr)\] at this scale, and the remaining terms are sublinear perturbations. Hence the maximal value of \(t\) satisfying the preceding display is at most \[\begin{align} B_\delta + \widetilde{\mathcal{O}}\Bigl( \sqrt{B_\delta} + T(M)A_1B_\delta^{r_1} + T(M)A_2B_\delta^{r_2} + T(M)A_3^{(p)}B_\delta^{\bar r_3^{(p)}} + T(M)A_4B_\delta^{r_4} \Bigr). \end{align}\] Consequently, \[\begin{align} \tau_\delta^{\mathrm{ub}} \le\;& B_\delta + \widetilde{\mathcal{O}}\Bigl( \sqrt{B_\delta} + T(M)A_1B_\delta^{r_1} + T(M)A_2B_\delta^{r_2} + T(M)A_3^{(p)}B_\delta^{\bar r_3^{(p)}} + T(M)A_4B_\delta^{r_4} \Bigr). \end{align}\] Plugging this into the bound \[\mathbb{E}_M[\tau_\delta]\le \tau_\delta^{\mathrm{ub}}+7\] proves the claimed finite-confidence upper bound.

Finally, since \[B_\delta = T(M)c_0\log(1/\delta) + \mathcal{O}\!\left(T(M)\log\log(1/\delta)\right),\] and since \[r_1,r_2,\bar r_3^{(p)},r_4<1,\] all correction terms are \(o(\log(1/\delta))\) for fixed problem-dependent quantities. Hence \[\mathbb{E}_M[\tau_\delta] = T(M)c_0\log(1/\delta) + o(\log(1/\delta)),\] as \(\delta\to0\). ◻

Proof. Consider any two environments \(M_,M_2 \in G_\mu(L)\) and let \(\alpha\in[0,1]\). Let \(M_3 = \alpha M_1 + (1-\alpha)M_2\).
Since we have by assumption that \(M_1,M_2 \in \Delta(S)\) we have their convex combination is also a probability distribution \(M_3 \in \Delta(S)\). Furthermore, since \(\mu \ll M_1\) and \(\mu \ll M_2\) we have that \(\mu \ll M_3\). Finally, we have by assumption that \[\frac{M_1(s)}{\mu(s)}, \frac{M_2(s)}{\mu(s)} \in [1/L,L] \quad \forall s \in S.\] Hence we have \[\frac{M_3(s)}{\mu(s)} = \frac{\alpha M_1(s) + (1-\alpha)M_2(s)}{\mu(s)} = \alpha\frac{ M_1(s)}{\mu(s)} + (1-\alpha)\frac{M_2(s)}{\mu(s)} \in [1/L,L]\] since the set \([1/L,L]\) is convex. Hence, the proof is complete. ◻

Proof. In order to prove this, we can simply use the mean-value theorem. In particular, since \(G_\mu(L)\) is convex, we have that \[|{\rm KL}(P_1,P_3) - {\rm KL}(P_2,P_3)| \leq \sup_{P\in G_\mu(L)} \|\nabla_P {\rm KL}(P,P_3)\|_\infty \quad \cdot \quad\|P_1-P_2\|_1.\] Where we denote \(\nabla_P(\cdot) = (d/dP(1), \dots, d/dP(S))^\top\). Hence, to complete the proof, we need only bound the norm of gradient of the KL of \(\nabla_P {\rm KL}(P,P_3)\). Note that

\[\frac{d}{dP(s')} {\rm KL}(P,P_3) = \frac{d}{dP(s')} \sum_s P(s) \log \frac{P(s)}{P_3(s)} = 1 + \log \frac{P(s')}{P_3(s')} \leq 1+2\log L\]

Therefore we have that \[\sup_{P\in G_\mu(L)} \|\nabla_P {\rm KL}(P,P_3)\|_1 \leq S(1+2\log L)\] and the proof is complete. ◻

Proof. \(P_i - X_i\) is a martingale difference sequence with respect to the filtration \(\mathcal{F}_i\). Since \(X_i\) is nonnegative and has finite second moment, we have for any \(\lambda > 0\) that \[\mathbb{E}\left[e^{-\lambda(X_i - P_i)} \mid \mathcal{F}_{i-1}\right] \le e^{\lambda^2 P_t / 2}\] [28]). Hence, we have \[\mathbb{E}\left[ e^{\lambda (P_i - X_i) - \lambda^2 P_i / 2} \mid \mathcal{F}_{i-1} \right] \le 1.\]

By setting \(\lambda = 1\), we see that \[M_n = e^{\sum_{i=1}^{n} (-X_i + P_i / 2)}\] is a supermartingale. It hence holds by the definition of \(M_n\) and Doob’s inequality that \[\mathbb{P}\left(\exists n \in [1,t]: \sum_{i=1}^{n} (-X_i + P_i / 2) \ge W \right) = \mathbb{P}\left( \exists n \in [1,t]: M_n \ge e^{W} \right) \le e^{-W} \mathbb{E}[M_1] \le e^{-W},\] which gives us the desired result. ◻

Proof. Consider a Dirichlet prior on the mean parameter of the exponential family formed by the set of categorical distributions on \(\{1,\dots,m\}\). Let \[\phi_p(\lambda) = \log \mathbb{E}_{X \sim p}\!\left[e^{\lambda X}\right] = \log\!\left(p_m + \sum_{k=1}^{m-1} p_k e^{\lambda_k}\right)\] be the log-partition function. The following quantity is a martingale: \[M^\lambda_n = \exp\!\big(n \langle \lambda, \hat{p}_n \rangle - n \phi_p(\lambda)\big).\]

We set a Dirichlet prior \(q \sim \mathrm{Dir}(\alpha)\) with \(\alpha \in \mathbb{R}^{\ast +}_m\), and for \(\lambda_q = (\nabla \phi_p)^{-1}(q)\) consider the integrated martingale \[\begin{align} M_n &= \int M^{\lambda_q}_n \frac{\Gamma\!\left(\sum_{k=1}^m \alpha_k\right)}{\prod_{k=1}^m \Gamma(\alpha_k)} \prod_{k=1}^m q_k^{\alpha_k - 1} \, dq \\ &= \int e^{n(\mathrm{KL}(\hat{p}_n,p) - \mathrm{KL}(\hat{p}_n,q))} \frac{\Gamma\!\left(\sum_{k=1}^m \alpha_k\right)}{\prod_{k=1}^m \Gamma(\alpha_k)} \prod_{k=1}^m q_k^{\alpha_k - 1} \, dq \\ &= e^{n\mathrm{KL}(\hat{p}_n,p) + n H(\hat{p}_n)} \frac{\Gamma\!\left(\sum_{k=1}^m \alpha_k\right)}{\prod_{k=1}^m \Gamma(\alpha_k)} \int \prod_{k=1}^m q_k^{n \hat{p}_{n,k} + \alpha_k - 1} \, dq \\ &= e^{n\mathrm{KL}(\hat{p}_n,p) + n H(\hat{p}_n)} \frac{\Gamma\!\left(\sum_{k=1}^m \alpha_k\right)}{\prod_{k=1}^m \Gamma(\alpha_k)} \frac{\prod_{k=1}^m \Gamma(\alpha_k + n \hat{p}_{n,k})}{\Gamma\!\left(\sum_{k=1}^m \alpha_k + n\right)} . \end{align}\]

Now choose the uniform prior \(\alpha = (1,\dots,1)\). Then \[\begin{align} M_n &= e^{n\mathrm{KL}(\hat{p}_n,p) + n H(\hat{p}_n)} (m-1)! \frac{\prod_{k=1}^m \Gamma(1 + n \hat{p}_{n,k})}{\Gamma(m + n)} \\ &= e^{n\mathrm{KL}(\hat{p}_n,p) + n H(\hat{p}_n)} (m-1)! \frac{\prod_{k=1}^m (n \hat{p}_{n,k})!}{n!} \frac{n!}{(m + n - 1)!} \\ &= e^{n\mathrm{KL}(\hat{p}_n,p) + n H(\hat{p}_n)} \frac{\binom{n}{n \hat{p}_n}^{-1}}{\binom{m + n - 1}{m - 1}^{-1}} \\ &= e^{n\mathrm{KL}(\hat{p}_n,p) + n H(\hat{p}_n)} \frac{1}{\binom{n}{n \hat{p}_n} \binom{m + n - 1}{m - 1}} . \end{align}\]

Thanks to [29] , for any \(M \in \mathbb{N}^\ast\) and \(x \in \{0,\dots,M\}^m\) such that \(\sum_{k=1}^m x_k = M\), it holds that \[\binom{M}{x} = \frac{M!}{\prod_{k=1}^m x_k!} \le e^{M H(x/M)} .\] Hence \[M_n \ge e^{n\mathrm{KL}(\hat{p}_n,p) + n H(\hat{p}_n) - n H(\hat{p}_n) - (m + n - 1) H\!\left(\frac{m-1}{m + n - 1}\right)} = e^{n\mathrm{KL}(\hat{p}_n,p) - (m + n - 1) H\!\left(\frac{m-1}{m + n - 1}\right)} .\]

We upper bound the entropic term: \[\begin{align} (m + n - 1) H\!\left(\frac{m - 1}{m + n - 1}\right) &= (m - 1) \log\!\frac{m + n - 1}{m - 1} + n \log\!\frac{m + n - 1}{n} \\ &\le (m - 1) \log\!\left(1 + \frac{n}{m - 1}\right) + n \log\!\left(1 + \frac{m - 1}{n}\right) \\ &\le (m - 1) \log\!\left(1 + \frac{n}{m - 1}\right) + (m - 1). \end{align}\] Thus, \[M_n \ge e^{n\mathrm{KL}(\hat{p}_n,p)} \left(e\!\left(1 + \frac{n}{m - 1}\right)\right)^{-(m - 1)} .\]

Finally, using the fact that for any supermartingale \(M_n\), with Doob’s inequality we have \[\mathbb{P}\!\left(\exists n \in [1,t] : M_n > \frac{1}{\delta}\right) \le \delta \, \mathbb{E}[M_1],\] we conclude that \[\mathbb{P}\!\left( \exists n \in [1,t], \, n \, \mathrm{KL}(\hat{p}_n, p) > (m-1) \log\!\left(e\!\left(1 + \frac{n}{m-1}\right)\!\right) + \log(1/\delta) \right) \le \delta .\] ◻

Proof. The fact that the two stationary distributions are unique follow from standard MDP arguments [14]. The proof then follows as in [31] (see also [30] for a comparison between perturbation bounds). ◻

Proof. We prove it by contradiction. First, as in [13] note that we can always write the set of confusing models as \[{\rm Alt}({\cal M})=\cup_{s,a\neq \pi^\star(s)} {\rm Alt}_{s,a}({\cal M}),\] where \({\rm Alt}_{s,a}({\cal M})=\{{\cal M}': (P(s',a')\ll P'(s',a') \;\forall (s',a') )\,\wedge\,Q_{P'}^{\pi^\star}(s,a)>V_{P'}^{\pi^\star}(s)\}\) with \({\cal M}'=(S,A,P',r)\). Hence, the optimization problem can also be written as \[\max_{\omega \in \Omega({\cal M})} \min_{s',a'\neq\pi^\star(s_0)}\inf_{{\cal M}' \in {\rm Alt}_{s',a'}({\cal M})} \sum_{s,a}\omega(s,a){\rm KL}(P(s,a),P'(s,a)).\]

Assume \[\omega^\star \in \arg\max_{\omega\in \Omega({\cal M})}\inf_{{\cal M}'\in{\rm Alt}({\cal M})}\sum_{s,a}\omega(s,a){\rm KL}(P(s,a),P'(s,a))\] is such that \(\exists (s_0,a_0): \omega^\star(s_0,a_0)=0\). Then, to prove the statement, we can construct an alternative MDP \({\cal M}'\) such that \(P(s,a)\ll P'(s,a)\) in all \((s,a)\), satisfying \(\pi^\star\notin \Pi^\star({\cal M}')\), where \(\Pi^\star({\cal M}')\) is the set of optimal policies for \({\cal M}'\). If \(P'\) is built such that only the transition in \((s_0,a_0)\) is different, and all the other transitions satisfy \(P'(s,a)=P(s,a)\), then we have that \[\sum_{s,a}\omega^\star(s,a){\rm KL}(P(s,a),P'(s,a))= \omega^\star(s_0,a_0){\rm KL}(P(s_0,a_0),P'(s_0,a_0))=0.\] Since the minimum value is \(0\), then such \(P'\) attains the minimum value, implying that the sample complexity is infinite. But since we know that at the optimum the value is strictly better than \(0\), then \(\omega^\star\) is not an optimal solution, and thus we have a contradiction, and we must have \(\omega^\star(s_0,a_0)>0\).

In the proof we also use the following fact: by uniqueness of the optimal policy we have that \(V_P^{\pi^\star}(s)>Q_P^{\pi^\star}(s,a)\) for all \(s,a\neq \pi^\star(s)\). We also let \(s_{\rm max}\in \arg\max_s V_P^{\pi^\star}(s)\) be any state with maximum value and \(s_{\rm min}\in \arg\min V_P^{\pi^\star}(s)\) the minimum value.
We construct an alternative transition function using a parameter \(\lambda\in (0,1)\): \[P'(s'|s,a)=\begin{cases} (1-\lambda)P(s'|s,a)+\lambda \mathbf{1}_{(s'=s_{\rm max})} & (s,a)=(s_0,a_0),\\ P(s'|s,a) & otherwise. \end{cases}\] We then clearly have that \(P(s,a)\ll P'(s,a)\) for all \((s,a)\). Furthermore, we also have that \(P'\) is a communicating MDP and \(\sum_{s,a}\omega^\star(s,a){\rm KL}(P(s,a),P'(s,a))=0\). We are left with proving that the optimal policy in \({\cal M}'=(S,A,P',r)\) is not the same optimal policy in \({\cal M}\).
Let \(\pi'\) be an optimal policy in \({\cal M}'\). Then, consider \(\Delta(s,a)=V_{P}^{\pi^\star}(s)-Q_{P}^{\pi^\star}(s,a)\). We now \({\cal M}'\) is an alternative model if \(Q_{P'}^{\pi^\star}(s,a)> V_{P'}^{\pi^\star}(s)\) in some pair \(s,a\neq\pi^\star(s)\). This condition is also equivalent to \[Q_{P'}^{\pi^\star}(s,a)-V_P^{\pi^\star}(s)>V_{P'}^{\pi^\star}(s)-V_P^{\pi^\star}(s).\] However, note that for all \(s\) we have that \(V_{P'}^{\pi^\star}(s)-V_P^{\pi^\star}(s)=\gamma P(s,\pi^\star(s))^\top [V_{P'}^{\pi^\star}-V_P^{\pi^\star}]\). Since \(\gamma\in (0,1)\), the only value \(V_{P'}^{\pi^\star}\) satisfying the contraction is \(V_{P'}^{\pi^\star}-V_P^{\pi^\star}=0\). Therefore, the condition reduces to \[Q_{P'}^{\pi^\star}(s,a)-V_P^{\pi^\star}(s)>0.\]

Let \(s_0,a_0\neq\pi^\star(s_0)\) be the state-action pair in which we impose \(Q_{P'}^{\pi^\star}(s_0,a_0)-V_P^{\pi^\star}(s_0)>0\). Using that \(V_{P'}^{\pi^\star}=V_P^{\pi^\star}\), the condition is rewritten as follows \[r(s_0,a_0)+\gamma(1-\lambda)P_{s_0,a_0}^\top V_P^{\pi^\star} + \gamma \lambda \|V_P^{\pi^\star}\|_\infty -V_P^{\pi^\star} > 0.\] In other words, we have \[\gamma \lambda(\|V_P^{\pi^\star}\|_\infty- P_{s_0,a_0}^\top V_P^{\pi^\star}) \geq \Delta(s_0,a_0),\] where \(\Delta(s_0,a_0)\mathrel{\vcenter{:}}= V_P^{\pi^\star}(s_0)-r(s_0,a_0)-\gamma P_{s_0,a_0}^\top V_{P}^{\pi^\star}=V_P^{\pi^\star}(s_0)- Q_{P}^{\pi^\star}(s_0,a_0)\). Since \(a_0\neq \pi^\star(s_0)\), we have \(\Delta(s_0,a_0)>0\). Therefore, if \[\gamma(\|V_P^{\pi^\star}\|_\infty- P_{s_0,a_0}^\top V_P^{\pi^\star}) > \Delta(s_0,a_0),\] we have that there exists \(\lambda \in (0,1)\) such that \(P'\) is an alternative model. Thus, we have proven the statement for all \((s,a\neq \pi^\star(s))\)
The proof follows similarly as before, but now we change \(P'\) so that the value in \((s_0,a_0)\) decreases sufficiently (with \(a_0=\pi^\star(s_0)\)). Hence, to guarantee that \(P'\) is an alternative model, we need to show that there exists \((s_0,a\neq\pi^\star(s_0))\) such that \(Q_{P'}^{\pi^\star}(s_0,a)> V_{P'}^{\pi^\star}(s_0)\).

Define \(P'\) as follows with \(\lambda\in (0,1)\) \[P'(s'|s,a)=\begin{cases} (1-\lambda)P(s'|s,a)+\lambda \mathbf{1}_{(s'=s_{\rm min})} & (s,a)=(s_0,a_0),\\ P(s'|s,a) & otherwise \end{cases}\] We now show that this choice of \(P'\) yields a worse value of \(\pi^\star\) in \(P'\). Let \(P_{\pi^\star}=(P_{\pi^\star}(s'|s))_{s,s'}\) be the transition matrix induced by \(\pi^\star\) in \(P\) and similarly define \(P_{\pi^\star}'\). Observe that \(P_{\pi^\star}'=P_{\pi^\star}+\lambda A\), where \((A)_{s,s'}=[ \mathbf{1}_{(s'=s_{\rm min})}-(P_{\pi^\star})_{s,s'} ]\mathbf{1}_{(s=s_0)}\). Since \((I-\gamma P_{\pi^\star}) V_P^{\pi^\star}=r\) and \((I-\gamma P_{\pi^\star}') V_{P'}^{\pi^\star}=r\) we have that \[(I-\gamma P_{\pi^\star}) V_P^{\pi^\star}=(I-\gamma P_{\pi^\star}') V_{P'}^{\pi^\star}.\] Using that \(P_{\pi^\star}=P_{\pi^\star}'-\lambda A\), we have \((I-\gamma P_{\pi^\star}'+\gamma \lambda A) V_P^{\pi^\star}=(I-\gamma P_{\pi^\star}') V_{P'}^{\pi^\star}\), and therefore \[(V_{P'}^{\pi^\star}-V_{P}^{\pi^\star})= \gamma \lambda (I-\gamma P_{\pi^\star}')^{-1}A V_{P}^{\pi^\star}.\] By construction we have \((A V_{P}^{\pi^\star})_s=0\) for \(s\neq s_0\), and \((A V_{P}^{\pi^\star})_{s_0}= V_{P}^{\pi^\star}(s_{\rm min})-\sum_{s'} P_{\pi^\star}(s'|s_0) V_{P}^{\pi^\star}(s') \leq 0\). Therefore, since \((I-\gamma P_{\pi^\star}^{-1})=\sum_k (\gamma P_{\pi^\star}')^k\) has nonnegative entries, we see that \((V_{P'}^{\pi^\star}-V_{P}^{\pi^\star})\leq 0\) holds element-wise. In fact, we also write \(A V_{P}^{\pi^\star}= \kappa e_{s_0}\), where \(\kappa \mathrel{\vcenter{:}}= V_{P}^{\pi^\star}(s_{\rm min})-\sum_{s'} P_{\pi^\star}(s'|s_0) V_{P}^{\pi^\star}(s')\) and \((e_{s_0})_s=\mathbf{1}_{s=s_0}\) is an \(S\)-dimensional unit vector.

Now, to conclude the proof we need to guarantee the following condition \(Q_{P'}^{\pi^\star}(s_0,a)> V_{P'}^{\pi^\star}(s_0)\), which can be rewritten as follows \[\begin{align} r(s_0,a) +\gamma P_{s_0,a}^\top V_{P'}^{\pi^\star} \pm \gamma P_{s_0,a}^\top V_{P}^{\pi^\star} &> V_{P'}^{\pi^\star}(s_0),\\ Q_{P}^{\pi^\star}(s_0,a) + \gamma P_{s_0,a}^\top (V_{P'}^{\pi^\star}-V_{P}^{\pi^\star})&> V_{P'}^{\pi^\star}(s_0) \pm V_P^{\pi^\star}(s_0),\\ -\Delta(s_0,a) &> [e_{s_0}-\gamma P_{s_0,a}]^\top(V_{P'}^{\pi^\star}-V_{P}^{\pi^\star}). \end{align}\] Then, swapping the two sides, the condition to verify becomes \[[\gamma P_{s_0,a}-e_{s_0}]^\top(V_{P'}^{\pi^\star}-V_{P}^{\pi^\star})=\gamma \lambda|\kappa|[e_{s_0}-\gamma P_{s_0,a}]^\top (I-\gamma P_{\pi^\star}')^{-1} e_{s_0}>\Delta(s_0,a) .\] To lower bound \([e_{s_0}-\gamma P_{s_0,a}]^\top (I-\gamma P_{\pi^\star}')^{-1} e_{s_0}\) let \(W\) be the solution to the Bellman equation \(W= e_{s_0}+\gamma (P_{\pi^\star}')^\top W\). Clearly \(W(s_0)\geq W(s)\) for \(s\neq s_0\) by monotonicity, and \(W(s_0)\geq 1\) (since \(W(s_0)= \sum_{k\geq 0}(\gamma P_{\pi^\star}')_{s_0,s_0}^k\geq 1\)). Therefore \[[e_{s_0}-\gamma P_{s_0,a}]^\top (I-\gamma P_{\pi^\star}')^{-1} e_{s_0}= W(s_0)-\gamma P_{s_0,a}^\top W \geq W(s_0)-\gamma W(s_0)P_{s_0,a}^\top {\boldsymbol{1}}\geq 1-\gamma.\]

Thus the proof concludes by verifying \[\lambda \geq \frac{\Delta(s_0,a)}{\gamma |\kappa|(1-\gamma)},\] which allows to pick a valid value of \(\lambda\) if \(\gamma |\kappa|(1-\gamma)> \Delta(s_0,a)\). This concludes the proof. ◻

Proof. The idea of the proof is to apply twice Berge’s maximum Theorem 15. First, assume \({\cal M}\) to be fixed, and consider the function \[f(\omega, {\cal M}')= \sum_{s,a}\omega(s,a){\rm KL}(P(s,a),P'(s,a)).\] Let \({\cal X}=\Omega({\cal M})\) and \(\psi(\omega)\equiv\psi\mathrel{\vcenter{:}}= \overline{\rm Alt}({\cal M})\). Clearly, \(f\) is continuous in \((\omega,{\cal M}')\) and the set \(\psi\) is constant, non-empty and compact. Then, by Theorem 15 the function \(f^\star(\omega)=\min\{f(\omega,{\cal M}')\,|\,{\cal M}'\in \psi\}\) is continuous and \(\psi^\star=\{{\cal M}' \in \psi\,|\, f(\omega,{\cal M}')=f^\star(\omega)\}\) is a compact-valued upper-hemi-continuous correspondence.

At this point, note that for any \(\omega_1,\omega_2\in \Omega({\cal M})\) and \(\lambda\in [0,1]\) we have \[\begin{align} f^\star((1-\lambda)\omega_1+\lambda \omega_2) &= \min_{{\cal M}'\in\overline{\rm Alt}({\cal M})} f((1-\lambda)\omega_1+\lambda \omega_2,{\cal M}'),\\ &= \min_{{\cal M}'\in\overline{\rm Alt}({\cal M})} (1-\lambda)f(\omega_1,{\cal M}') + \lambda f(\omega_2,{\cal M}') ,\\ &\geq \min_{{\cal M}'\in\overline{\rm Alt}({\cal M})} (1-\lambda)f(\omega_1,{\cal M}') + \min_{{\cal M}'\in\overline{\rm Alt}({\cal M})}\lambda f(\omega_2,{\cal M}') ,\\ &= (1-\lambda)f^\star(\omega_1)+\lambda f^\star(\omega_2). \end{align}\] Hence \(f^\star\) is concave in \(\omega\). At this point we can apply the theorem again to \(f^\star(\omega)\), so that we consider the values \(\max\{f^\star(\omega)\,|\,\omega\in \Omega({\cal M})\}\). We let \({\cal X}=\{{\cal M}\}\) and \({\cal Y}=\Delta(S\times A)\), with \(\psi({\cal M})=\Omega({\cal M})\) (which is compact by the finiteness of the MDP). Since \(f^\star\) is continuous and concave, and \(\psi\) is a convex set, then \(\{\omega \in \Omega(M)\,|\, f^\star(\omega)=(T^\star({\cal M}))^{-1}\}\) is a convex-valued set by Lemma 15. ◻

Proof. This is an immediate consequence from the proof of Lemma 21. ◻

Proof. Let \(V^\pi\) denote the value function of policy \(\pi\): \[V^\pi(s) = \mathbb{E}_\pi \!\left[ \sum_{t=0}^{\infty} \gamma^t r(s_t, a_t) \,\middle|\, s_0 = s \right].\] Define the optimal value and \(Q\)-functions by \[V^*(s) = \max_{a \in A} Q^*(s,a), \qquad Q^*(s,a) = r(s,a) + \gamma \sum_{s'} P(s'|s,a) V^*(s').\]

8.7.0.1 Step 1. Characterization of optimal policies.

A standard result in dynamic programming (see, e.g., Puterman, Markov Decision Processes, 1994, Proposition 6.2.3) states that a policy \(\pi\) is optimal if and only if, for all \(s \in S\), \[\pi(a|s) > 0 \; \Rightarrow \; Q^*(s,a) = V^*(s). \label{eq:opt}\tag{15}\] In words: a policy may assign positive probability only to actions that achieve the maximal \(Q^*(s,a)\) value in each state.

8.7.0.2 Step 2. Apply 15 to the uniform policy.

Assume that the uniform policy \(\pi_u\) is optimal. Since \(\pi_u(a|s) = 1/|A| > 0\) for every \(s\) and \(a\), substituting into 15 gives \[Q^*(s,a) = V^*(s), \quad \forall s \in S, \, a \in A. \label{eq:qequal}\tag{16}\] Thus, in each state, all actions have identical optimal \(Q\)-values.

8.7.0.3 Step 3. The set of optimal actions.

Define the set of optimal actions in state \(s\) as \[A^*(s) = \{ a \in A : Q^*(s,a) = V^*(s) \}.\] Equation 16 implies \[A^*(s) = A, \quad \forall s \in S.\] Hence, every action is optimal in every state.

8.7.0.4 Step 4. The set of optimal policies.

Let \(\Pi^*\) denote the set of optimal policies: \[\Pi^* = \bigl\{ \pi : \pi(a|s) > 0 \Rightarrow a \in A^*(s), \;\forall s \in S \bigr\}.\] Since \(A^*(s) = A\) for all \(s\), we have \[\Pi^* = \{ \pi : \pi(\cdot|s) \in \Delta(A), \;\forall s \in S \},\] where \(\Delta(A)\) is the simplex over \(A\). That is, every possible policy (deterministic or stochastic) is optimal.

8.7.0.5 Step 5. Non-uniqueness.

Because \(\Pi^*\) contains all policies, the uniform policy \(\pi_u\) is not unique. Indeed, any policy \(\pi'\) differing from \(\pi_u\) on at least one \((s,a)\) is also optimal.

8.7.0.6 Step 6. Degenerate exception.

If \(|A|=1\), the MDP admits only one policy. In that trivial case the uniform policy is uniquely optimal, but this is vacuous.

8.7.0.7 Conclusion.

For any finite discounted MDP with \(|A|>1\), if the uniform policy is optimal, it cannot be the unique optimal policy. ◻

Proof. Fix \(M'\in \mathcal{M}\). We first prove a Hausdorff stability bound between \(S(M')\) and \(S(M)\).

Let \(\omega'\in S(M')\). By Assumption (A3), there exists \(\bar\omega'\in\Omega(M)\) such that \[\|\omega'-\bar\omega'\|_\infty \le \kappa_\Omega(M)\varepsilon .\] Let \(\omega^\star\in S(M)\). Again by Assumption (A3), there exists \(\bar\omega^\star\in\Omega(M')\) such that \[\|\omega^\star-\bar\omega^\star\|_\infty \le \kappa_\Omega(M)\varepsilon .\] Since \(\omega'\in S(M')\), it is optimal for \(J_{M'}\) over \(\Omega(M')\). Therefore, \[J_{M'}(\omega') \ge J_{M'}(\bar\omega^\star).\] Using Assumption (A2), we obtain \[\begin{align} J_M(\bar\omega') &\ge J_M(\omega') - L_\omega\|\bar\omega'-\omega'\|_\infty \\ &\ge J_{M'}(\omega') - L_M\varepsilon - L_\omega\kappa_\Omega(M)\varepsilon \\ &\ge J_{M'}(\bar\omega^\star) - L_M\varepsilon - L_\omega\kappa_\Omega(M)\varepsilon \\ &\ge J_M(\bar\omega^\star) - 2L_M\varepsilon - L_\omega\kappa_\Omega(M)\varepsilon \\ &\ge J_M(\omega^\star) -2L_M\varepsilon -2L_\omega\kappa_\Omega(M)\varepsilon . \end{align}\] Since \(\omega^\star\in S(M)\), \(J_M(\omega^\star)=J_M^\star\). Thus \[J_M^\star-J_M(\bar\omega') \le \left(2L_M+2L_\omega\kappa_\Omega(M)\right)\varepsilon = C_T(M)\varepsilon .\] By Assumption (A4) applied with \(N=M\), \[\mathrm{dist}_\infty(\bar\omega',S(M)) \le \varphi_M(C_T(M)\varepsilon).\] Therefore, \[\begin{align} \mathrm{dist}_\infty(\omega',S(M)) &\le \|\omega'-\bar\omega'\|_\infty + \mathrm{dist}_\infty(\bar\omega',S(M)) \\ &\le \kappa_\Omega(M)\varepsilon + \varphi_M(C_T(M)\varepsilon). \end{align}\] Taking the supremum over \(\omega'\in S(M')\), we obtain \[\sup_{\omega'\in S(M')} \mathrm{dist}_\infty(\omega',S(M)) \le \kappa_\Omega(M)\varepsilon + \varphi_M(C_T(M)\varepsilon).\]

We now prove the reverse inclusion bound. Let \(\omega\in S(M)\). By Assumption (A3), there exists \(\bar\omega\in\Omega(M')\) such that \[\|\omega-\bar\omega\|_\infty \le \kappa_\Omega(M)\varepsilon .\] Let \(\omega'^\star\in S(M')\). Again by Assumption (A3), there exists \(\bar\omega'^\star\in\Omega(M)\) such that \[\|\omega'^\star-\bar\omega'^\star\|_\infty \le \kappa_\Omega(M)\varepsilon .\] Since \(\omega'^\star\in S(M')\), \[J_{M'}^\star=J_{M'}(\omega'^\star).\] Using Assumption (A2) and the optimality of \(\omega\in S(M)\), we have \[\begin{align} J_{M'}^\star &= J_{M'}(\omega'^\star) \\ &\le J_M(\omega'^\star)+L_M\varepsilon \\ &\le J_M(\bar\omega'^\star) + L_\omega\|\omega'^\star-\bar\omega'^\star\|_\infty + L_M\varepsilon \\ &\le J_M(\bar\omega'^\star) + L_\omega\kappa_\Omega(M)\varepsilon + L_M\varepsilon \\ &\le J_M^\star + L_\omega\kappa_\Omega(M)\varepsilon + L_M\varepsilon \\ &= J_M(\omega) + L_\omega\kappa_\Omega(M)\varepsilon + L_M\varepsilon . \end{align}\] On the other hand, \[\begin{align} J_{M'}(\bar\omega) &\ge J_M(\bar\omega)-L_M\varepsilon \\ &\ge J_M(\omega) - L_\omega\|\bar\omega-\omega\|_\infty - L_M\varepsilon \\ &\ge J_M(\omega) - L_\omega\kappa_\Omega(M)\varepsilon - L_M\varepsilon . \end{align}\] Combining the two displays gives \[J_{M'}^\star-J_{M'}(\bar\omega) \le 2L_M\varepsilon+2L_\omega\kappa_\Omega(M)\varepsilon = C_T(M)\varepsilon .\] By Assumption (A4) applied with \(N=M'\), \[\mathrm{dist}_\infty(\bar\omega,S(M')) \le \varphi_M(C_T(M)\varepsilon).\] Therefore, \[\begin{align} \mathrm{dist}_\infty(\omega,S(M')) &\le \|\omega-\bar\omega\|_\infty + \mathrm{dist}_\infty(\bar\omega,S(M')) \\ &\le \kappa_\Omega(M)\varepsilon + \varphi_M(C_T(M)\varepsilon). \end{align}\] Taking the supremum over \(\omega\in S(M)\), we obtain \[\sup_{\omega\in S(M)} \mathrm{dist}_\infty(\omega,S(M')) \le \kappa_\Omega(M)\varepsilon + \varphi_M(C_T(M)\varepsilon).\] Consequently, \[d_H(S(M'),S(M)) \le \kappa_\Omega(M)\varepsilon + \varphi_M(C_T(M)\varepsilon).\] Set \[h := d_H(S(M'),S(M)).\] Then \[h \le \kappa_\Omega(M)\varepsilon + \varphi_M(C_T(M)\varepsilon).\]

We now control the minimum-norm selectors. Let \[x:=\omega^\dagger(M), \qquad y:=\omega^\dagger(M').\] Because \(S(M)\) and \(S(M')\) are non-empty, compact, and convex, \(x\) and \(y\) are the Euclidean projections of \(0\) onto \(S(M)\) and \(S(M')\), respectively.

Since \(d_H(S(M'),S(M))=h\), there exists \(\bar y\in S(M)\) such that \[\|y-\bar y\|_2\le h,\] and there exists \(\bar x\in S(M')\) such that \[\|x-\bar x\|_2\le h.\] The projection variational inequality for \(x=\Pi_{S(M)}(0) = \mathop{\mathrm{arg\,min}}_{\omega\in S(M)}\|\omega\|_2^2\) gives \[\langle x,\bar y-x\rangle\ge 0.\] Hence \[\begin{align} \langle x,y-x\rangle &= \langle x,\bar y-x\rangle + \langle x,y-\bar y\rangle \\ &\ge -\|x\|_2\|y-\bar y\|_2 \\ &\ge -h, \end{align}\] where we have used Cauchy-Schwarz and \(\|x\|_2\le 1\), since \(x\) is a probability vector. Similarly, the projection variational inequality for \(y=\Pi_{S(M')}(0)\) gives \[\langle y,x-y\rangle\ge -h.\] Therefore, \[\begin{align} \|x-y\|_2^2 &= \langle x-y,x-y\rangle \\ &= \langle x,x-y\rangle + \langle y,y-x\rangle \\ &\le h+h = 2h . \end{align}\] Thus, \[\|x-y\|_\infty \le \|x-y\|_2 \le \sqrt{2h}.\] Substituting the bound on \(h\) gives \[\|\omega^\dagger(M')-\omega^\dagger(M)\|_\infty \le \sqrt{ 2\left[ \kappa_\Omega(M)\varepsilon + \varphi_M(C_T(M)\varepsilon) \right] } .\]

It remains to prove the policy bound. For any \(\omega_1,\omega_2\), we have \[\|\pi_{\omega_1}-\pi_{\omega_2}\|_\infty \le \frac{A+1}{\rho(M)}\|\omega_1-\omega_2\|_\infty\] Combining this with the earlier allocation bound gives \[\|\pi^\dagger_{M'}-\pi^\dagger_M\|_\infty \le \frac{(A+1)}{\rho(M)} \sqrt{ 2\left[ \kappa_\Omega(M)\varepsilon + \varphi_M(C_T(M)\varepsilon) \right] } .\]

Finally, the empirical statements follow by setting \(M'=\widehat M_t\). On \(\mathcal{E}_T(\lambda)\), if \(\psi(t,\lambda)\le r_M\), then \[\|\widehat P_t-P\|_{\infty,1}\le \psi(t,\lambda),\] so the deterministic bounds above apply with \[\varepsilon=\|\widehat P_t-P\|_{\infty,1}\le \psi(t,\lambda).\] ◻

Proof. Recall that, for an MDP \(N=(\mathcal{S},\mathcal{A},P_N,r,\gamma)\), \[\Omega(N) = \left\{ \omega\in\Delta(\mathcal{S}\times\mathcal{A}): \sum_a \omega(s,a) = \sum_{s',a'} P_N(s\mid s',a')\omega(s',a') \quad \forall s\in\mathcal{S} \right\}.\] Equivalently, \[\Omega(N) = \left\{ \omega\in\mathbb{R}^{SA}: \omega\ge 0,\; \mathbf{1}^\top \omega=1,\; B(P_N)\omega=0 \right\},\] where \(B(P_N)\omega=0\) encodes the stationarity equations \[\sum_a \omega(s,a) - \sum_{s',a'} P_N(s\mid s',a')\omega(s',a') = 0, \qquad s\in\mathcal{S} .\] Thus \(\Omega(N)\) is a polyhedron of the form \[\{x\in\mathbb{R}^{SA}: Ax\le b,\;C_Nx=d\},\] where we may take \[A=-I, \qquad b=0,\] to encode the non-negativity constraints \(\omega\ge 0\), and \[C_N = \begin{pmatrix} \mathbf{1}^\top \\ B(P_N) \end{pmatrix}, \qquad d = \begin{pmatrix} 1\\ 0 \end{pmatrix}.\]

Fix \(\omega\in\Omega(M)\). We want to bound \[\mathrm{dist}_\infty(\omega,\Omega(N)).\] Since \(\omega\in\Omega(M)\), we have \[\omega\ge 0, \qquad \mathbf{1}^\top\omega=1, \qquad B(P)\omega=0.\] When \(\omega\) is tested against the constraints defining \(\Omega(N)\), the inequality residual is therefore zero: \[(-I\omega-0)_+ = (-\omega)_+ = 0,\] and the normalisation residual is also zero: \[\mathbf{1}^\top\omega-1=0.\] The only non-zero residual is the stationarity residual: \[B(P_N)\omega = B(P_N)\omega-B(P)\omega = \bigl(B(P_N)-B(P)\bigr)\omega.\] Since \(B(P)\) depends linearly on \(P\), there exists a finite dimension-dependent constant \(c_B>0\) such that \[\|B(P_N)-B(P)\|_\infty \le c_B\|P_N-P\|_{\infty,1}.\] Moreover, since \(\omega\in\Delta(\mathcal{S}\times\mathcal{A})\), we have \[\|\omega\|_1=1.\] Hence \[\|B(P_N)\omega\|_\infty \le c_B\|P_N-P\|_{\infty,1}.\]

Applying Hoffman’s lemma (Lemma 27) to the fixed polyhedron \(\Omega(N)\), there exists a constant \(H_N<\infty\) such that \[\mathrm{dist}_\infty(\omega,\Omega(N)) \le H_N \left( \|(-\omega)_+\|_\infty + |\mathbf{1}^\top\omega-1| + \|B(P_N)\omega\|_\infty \right).\] The first two terms are zero, and the third term is bounded as above. Therefore \[\mathrm{dist}_\infty(\omega,\Omega(N)) \le H_Nc_B\|P_N-P\|_{\infty,1}.\] Thus, for each fixed \(N\), the one-sided deviation satisfies \[\sup_{\omega\in\Omega(M)} \mathrm{dist}_\infty(\omega,\Omega(N)) \le H_Nc_B\|P_N-P\|_{\infty,1}.\] ◻

Proof. For every \(\omega\in S(M)\) and every \(s\in\mathcal{S}\), \[\omega(s) = \sum_a\omega(s,a)>0.\] The map \[\omega\mapsto \min_{s\in\mathcal{S}}\omega(s)\] is continuous. Since \(S(M)\) is compact, this map attains its minimum over \(S(M)\). By the strict positivity assumption, that minimum cannot be zero. Hence \[\rho(M) = \min_{\omega\in S(M)} \min_{s\in\mathcal{S}} \omega(s) >0.\] ◻

Proof. This is Hoffman’s lemma; see [34] and [35]. ◻

Proof. Since \(P\) is a polyhedron, there exist matrices \(A,C\) and vectors \(b,d\) such that \[P=\{x\in\mathbb{R}^{d+1}: Ax\le b,\; Cx=d\}.\] Hence \[S^\star = \{x\in\mathbb{R}^{d+1}: Ax\le b,\; Cx=d,\; t\le t^\star,\; -t\le -t^\star\}\] is also a nonempty polyhedron. Applying Hoffman’s error bound to this system, there exists \(\kappa_P>0\) such that for all \(x=(\omega,t)\), \[\mathrm{dist}_\infty(x,S^\star) \le \kappa_P\Big(\|(Ax-b)_+\|_\infty+\|Cx-d\|_\infty+(t-t^\star)_+ + (t^\star-t)_+\Big).\] Now let \(x=(\omega,t)\in P\). Then \((Ax-b)_+=0\) and \(Cx-d=0\). Moreover, since \(t^\star\) is the optimal value over \(P\), we have \(t\le t^\star\), so \((t-t^\star)_+=0\). Therefore \[\mathrm{dist}_\infty\big((\omega,t),S^\star\big) \le \kappa_P\,(t^\star-t),\] as claimed. ◻

Proof. Write \(k_i:=k(M_i)\in\mathbb{R}^d\) for \(i=1,\dots,N\). Since the alternative set is finite, \[T_\Delta(M,\omega)=\min_{1\le i\le N}\langle \omega,k_i\rangle\] is a concave piecewise-linear function of \(\omega\). Now, introduce the lifted feasible set \[P_\Delta(M) := \Bigl\{ (\omega,t)\in\mathbb{R}^{d+1} : \omega\in\Omega(M),\; t\le \langle \omega,k_i\rangle \;\forall i=1,\dots,N \Bigr\}.\] Then maximizing \(T_\Delta(M,\omega)\) over \(\Omega(M)\) is equivalent to the linear program \[T_\Delta^\star(M)=\max\{t:(\omega,t)\in P_\Delta(M)\}.\] Because \(\Omega(M)\) is a polytope and the additional constraints \(t\le \langle \omega,k_i\rangle\) are linear, \(P_\Delta(M)\) is a nonempty polyhedron. Since \(\Omega(M)\) is compact and each map \(\omega \mapsto \langle \omega,k_i\rangle\) is continuous, the function \(T_\Delta(M,\omega)=\min_i \langle \omega,k_i\rangle\) is continuous on \(\Omega(M)\). Hence the maximum \(T_\Delta^\star(M)\) is attained. Define the lifted optimal set \[S_\Delta^{\mathrm{lift}}(M) := P_\Delta(M)\cap\{t=T_\Delta^\star(M)\}.\] By Lemma 28, there exists a constant \(\kappa_\Delta(M)>0\) such that for all \((\omega,t)\in P_\Delta(M)\), \[\mathrm{dist}_\infty\big((\omega,t),S_\Delta^{\mathrm{lift}}(M)\big) \le \kappa_\Delta(M)\big(T_\Delta^\star(M)-t\big).\]

Now fix \(\omega\in\Omega(M)\), and set \(t:=T_\Delta(M,\omega)\). By definition of \(T_\Delta\), we have \(t\le \langle \omega,k_i\rangle\) for all \(i\), hence \((\omega,t)\in P_\Delta(M)\). Therefore \[\mathrm{dist}_\infty\big((\omega,T_\Delta(M,\omega)),S_\Delta^{\mathrm{lift}}(M)\big) \le \kappa_\Delta(M)\Big(T_\Delta^\star(M)-T_\Delta(M,\omega)\Big).\] Finally, projection onto the \(\omega\)-coordinates cannot increase \(\ell_\infty\)-distance, so \[\mathrm{dist}_\infty\big(\omega,S_\Delta(M)\big) \le \kappa_\Delta(M)\Big(T_\Delta^\star(M)-T_\Delta(M,\omega)\Big).\] Setting \(c_\Delta(M):=\kappa_\Delta(M)\) completes the proof. ◻

Proof. We divide the proof into several steps.

Step 1: the true MDP and the reward normalization. Let \[\mathcal{S}=\{x,y,d,g\}, \qquad \mathcal{A}=\{a,b\}, \qquad \gamma=\frac{1}{2}.\] Define the true transition kernel by \[P_M(\cdot\mid s,a)=P_M(\cdot\mid s,b)=p \qquad \forall s\in\mathcal{S},\] where \[p:=\Bigl(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4}\Bigr)\] in the state order \((x,y,d,g)\). Thus every row of every transition matrix equals \(p\). In particular, under every deterministic policy the induced state chain has strictly positive transition probabilities, so \(M\) is communicating and aperiodic.

The actual reward function used in the proposition is \[r(x,a)=r(y,a)=\frac{2}{3}, \qquad r(d,a)=\frac{41}{60}, \qquad r(g,a)=1,\] and \[r(x,b)=r(y,b)=r(g,b)=0, \qquad r(d,b)=\frac{2}{3}.\] Hence \(r(s,\alpha)\in[0,1]\) for every state-action pair. For algebraic convenience, introduce the auxiliary reward \[\bar r:=3r-2,\] so that \[\bar r(x,a)=\bar r(y,a)=0, \qquad \bar r(d,a)=\frac{1}{20}, \qquad \bar r(g,a)=1,\] and \[\bar r(x,b)=\bar r(y,b)=\bar r(g,b)=-2, \qquad \bar r(d,b)=0.\] The deterministic optimal-policy sets under \(r\) and \(\bar r\) coincide for the true model and for every alternative considered below. Therefore all optimality calculations may be carried out with \(\bar r\).

Under \(M\), the transition kernel is independent of the action, so action comparisons are determined entirely by immediate rewards. Since \[\bar r(s,a)-\bar r(s,b)>0 \qquad \forall s\in\mathcal{S},\] it follows that the policy \[\pi^\star(s)\equiv a \qquad (s\in\mathcal{S})\] is the unique deterministic optimal policy of \(M\). The same is true for the actual reward function \(r\in[0,1]\).

Step 2: the alternative family and the \(G_\mu(L)\) condition. Fix \(\bar u\in(0,1/16]\). For \(u\in[0,\bar u]\), define two probability vectors \[q_a(u):=\Bigl(\frac{3}{8}+u^m,\frac{1}{4},\frac{1}{4},\frac{1}{8}-u^m\Bigr), \qquad q_b(u):=\Bigl(\frac{1}{8}+u^n,\frac{1}{4},\frac{1}{4},\frac{3}{8}-u^n\Bigr),\] again in the state order \((x,y,d,g)\). Because \(\bar u\le 1/16\), all entries of \(q_a(u)\) and \(q_b(u)\) belong to \([1/16,7/16]\), in particular they are strictly positive.

Now define \(M_u\) by modifying only the two transitions at state \(d\): \[P_{M_u}(\cdot\mid d,a)=q_a(u), \qquad P_{M_u}(\cdot\mid d,b)=q_b(u),\] while for every other state-action pair \((s,\alpha)\neq(d,a),(d,b)\), \[P_{M_u}(\cdot\mid s,\alpha)=p.\] Set \[\Theta:=\{M\}\cup\{M_u:0\le u\le \bar u\}.\] The family \(\Theta\) is compact, and because it is parameterized polynomially by \(u\), it is semialgebraic as a subset of the product of simplices. Since every transition probability of every \(M_u\) is strictly positive, every \(M_u\) is also communicating and aperiodic.

Define the reference kernel \(\mu\) by \[\mu(\cdot\mid s,\alpha)=p \qquad \forall (s,\alpha)\in\mathcal{S}\times\mathcal{A}.\] Then \(P_M=\mu\), so \(P_M\in G_\mu(L)\) for every \(L>1\). Moreover, because every entry of every transition row in the family belongs to \([1/16,7/16]\), one has for every \(M_u\in\Theta\) and every state-action-state triple \((s,\alpha,s')\), \[\frac{\mu(s'\mid s,\alpha)}{P_{M_u}(s'\mid s,\alpha)} \in \left[\frac{1/4}{7/16},\frac{1/4}{1/16}\right] = \left[\frac{4}{7},4\right] \subseteq [1/4,4].\] Hence \(\Theta\subseteq G_\mu(4)\).

Step 3: the alternative policy is strictly optimal for all small \(u\). Define the deterministic policy \[\pi_u(x)=a,\qquad \pi_u(y)=a,\qquad \pi_u(d)=b,\qquad \pi_u(g)=a.\] We first verify strict optimality at \(u=0\). Under \(M_0\), the policy \(\pi_0\) has value vector \[V_{M_0}^{\pi_0} = \Bigl(\frac{17}{64},\frac{17}{64},\frac{21}{64},\frac{81}{64}\Bigr),\] which is obtained by solving the Bellman system \[V(x)=\frac{1}{2}\cdot\frac{V(x)+V(y)+V(d)+V(g)}{4},\] \[V(y)=\frac{1}{2}\cdot\frac{V(x)+V(y)+V(d)+V(g)}{4},\] \[V(d)=\frac{1}{2}\Bigl(\frac{1}{8}V(x)+\frac{1}{4}V(y)+\frac{1}{4}V(d)+\frac{3}{8}V(g)\Bigr),\] \[V(g)=1+\frac{1}{2}\cdot\frac{V(x)+V(y)+V(d)+V(g)}{4}.\] Now compare actions state by state.

At \(x\) and \(y\), action \(b\) has the same transition kernel as action \(a\) but a reward smaller by \(2\), so \[Q_{M_0}^{\pi_0}(x,a)-Q_{M_0}^{\pi_0}(x,b)=2, \qquad Q_{M_0}^{\pi_0}(y,a)-Q_{M_0}^{\pi_0}(y,b)=2.\] At \(g\), action \(b\) has the same transition kernel as \(a\) but a reward smaller by \(3\), so \[Q_{M_0}^{\pi_0}(g,a)-Q_{M_0}^{\pi_0}(g,b)=3.\] At \(d\), one computes \[Q_{M_0}^{\pi_0}(d,b) = \frac{1}{2}\Bigl(\frac{1}{8}\cdot\frac{17}{64}+\frac{1}{4}\cdot\frac{17}{64} +\frac{1}{4}\cdot\frac{21}{64}+\frac{3}{8}\cdot\frac{81}{64}\Bigr) = \frac{21}{64},\] whereas \[Q_{M_0}^{\pi_0}(d,a) = \frac{1}{20} +\frac{1}{2}\Bigl(\frac{3}{8}\cdot\frac{17}{64}+\frac{1}{4}\cdot\frac{17}{64} +\frac{1}{4}\cdot\frac{21}{64}+\frac{1}{8}\cdot\frac{81}{64}\Bigr) = \frac{81}{320}.\] Hence \[Q_{M_0}^{\pi_0}(d,b)-Q_{M_0}^{\pi_0}(d,a)=\frac{3}{40}>0.\] Thus \(\pi_0\) is the unique deterministic optimal policy of \(M_0\).

All Bellman action values for the auxiliary reward \(\bar r\) depend continuously on \(u\). Therefore, after possibly shrinking \(\bar u>0\), the same strict inequalities remain valid for every \(u\in[0,\bar u]\). Consequently, for all \(u\in[0,\bar u]\), \[\Pi^\star(M_u)=\{\pi_u\}, \qquad \pi^\star\notin\Pi^\star(M_u),\] first for the auxiliary reward \(\bar r\), and therefore also for the actual reward \(r\in[0,1]\). In particular, \[{\rm Alt}(M)=\{M_u:0\le u\le \bar u\}\] after replacing \(\Theta\) by the smaller compact family \(\{M\}\cup\{M_u:0\le u\le \bar u\}\).

Step 4: the navigation polytope. Because every row of \(P_M\) equals \(p\), the balance equations become \[\omega(s)=\sum_{s',\alpha} p(s)\,\omega(s',\alpha)=p(s)\sum_{s',\alpha}\omega(s',\alpha)=p(s) \qquad \forall s\in\mathcal{S}.\] Since \(\omega\in\Delta(\mathcal{S}\times\mathcal{A})\), this is equivalent to \[\omega(x)=\omega(y)=\omega(d)=\omega(g)=\frac{1}{4}.\] Hence \[\Omega(M) = \Bigl\{\omega\in\Delta(\mathcal{S}\times\mathcal{A}): \omega(x)=\omega(y)=\omega(d)=\omega(g)=\frac{1}{4}\Bigr\}.\]

Step 5: the objective and the optimal-allocation set. For \(u\in[0,\bar u]\), define \[K_m(u):={\rm KL}\bigl(p\,\|\,q_a(u)\bigr), \qquad L_n(u):={\rm KL}\bigl(p\,\|\,q_b(u)\bigr).\] Since every state-action pair other than \((d,a)\) and \((d,b)\) has the same transition under \(M\) and \(M_u\), one has, for every \(\omega\in\Omega(M)\), \[J_M(\omega) = \inf_{u\in[0,\bar u]} \Bigl[ \omega(d,a)K_m(u)+\omega(d,b)L_n(u) \Bigr].\] Because \(\omega(d,a)+\omega(d,b)=1/4\) for every \(\omega\in\Omega(M)\), this is a one-dimensional action-allocation problem at state \(d\).

A direct computation gives \[K_m(0)=L_n(0)=:A=\frac{1}{4}\log\frac{4}{3}.\] Moreover, for \(u>0\), \[K_m(u)>A>L_n(u).\] If \(\omega(d,b)=0\), then \(\omega(d,a)=1/4\) and \[J_M(\omega)=\inf_{u\in[0,\bar u]}\frac{1}{4} K_m(u)=\frac{1}{4} A.\] If \(\omega(d,b)>0\), then choosing \(u>0\) small enough yields \[\omega(d,a)K_m(u)+\omega(d,b)L_n(u)<\frac{1}{4} A,\] because the negative \(u^n\) variation in \(L_n(u)\) dominates the positive \(u^m\) variation in \(K_m(u)\) as \(u\downarrow0\). Hence \[J_M(\omega)<\frac{1}{4} A \qquad \text{whenever }\omega(d,b)>0.\] Therefore \[J^\star=\frac{1}{4} A\] and \[\Omega^\star(M) = \{\omega\in\Omega(M):\omega(d,b)=0,\;\omega(d,a)=1/4\}.\] Choose \[\omega^\star(s,a)=\frac{1}{4},\qquad \omega^\star(s,b)=0 \qquad (s\in\mathcal{S}).\] Then \(\omega^\star\in\Omega^\star(M)\), and it is a boundary point of \(\Omega^\star(M)\).

Step 6: the transverse direction. Let \[h:=e_{(d,b)}-e_{(d,a)}.\] Because \(h\) preserves the state marginal at \(d\) and leaves all other state marginals unchanged, it is a feasible direction at \(\omega^\star\). It is not strongly tangent to \(\Omega^\star(M)\), since \[(\omega^\star+t h)(d,b)=t>0 \qquad (t>0),\] whereas every point of \(\Omega^\star(M)\) satisfies \(\omega(d,b)=0\). Thus \(h\) is transverse.

For \(t\in(0,1/4)\), write \[\omega_t:=\omega^\star+t h.\] Then \[\omega_t(d,a)=\frac{1}{4}-t, \qquad \omega_t(d,b)=t,\] and therefore \[J_M(\omega_t)=\inf_{u\in[0,\bar u]}F_t(u), \qquad F_t(u):=\Bigl(\frac{1}{4}-t\Bigr)K_m(u)+tL_n(u).\]

Note also that the infinity norm distance between \(\omega_t\) and \(\Omega^*(M)\) is \(t\) in this case. Namely \(\mathrm{dist}_{\infty}(\omega_t,\Omega^*(M)) = t\). Hence, the final bounds on the curvature can be related to our definition of sharpness in Assumption (A4) of Lemma 24.

Step 7: asymptotic expansions of the branch costs. Because \[q_a(u)=\Bigl(\frac{3}{8}+u^m,\frac{1}{4},\frac{1}{4},\frac{1}{8}-u^m\Bigr), \qquad q_b(u)=\Bigl(\frac{1}{8}+u^n,\frac{1}{4},\frac{1}{4},\frac{3}{8}-u^n\Bigr),\] one computes \[K_m(u) = \frac{1}{4}\log\frac{(1/4)^2}{(3/8+u^m)(1/8-u^m)}, \qquad L_n(u) = \frac{1}{4}\log\frac{(1/4)^2}{(1/8+u^n)(3/8-u^n)}.\] Expanding at \(u=0\) gives \[K_m(u)=A+\frac{4}{3} u^m + O(u^{2m}), \qquad L_n(u)=A-\frac{4}{3} u^n + O(u^{2n}).\] Hence \[F_t(u) = \frac{A}{4} +\frac{1}{3} u^m -\frac{4}{3} t u^n +R_t(u),\] where \[|R_t(u)| \le C\bigl(tu^m+u^{2m}+t u^{2n}\bigr)\] for all sufficiently small \(u,t\).

Step 8: localization of the minimizer. Set \[s:=\frac{1}{m-n}, \qquad p^\sharp:=\frac{m}{m-n}.\] We claim that any minimizer \(u_t\) of \(F_t\) over \([0,\bar u]\) satisfies \[u_t=O(t^s).\] To see this, choose a constant \(M>0\) such that \(M^{m-n}>4\). If \(u\ge M t^s\), then \[\frac{1}{3} u^m-\frac{4}{3} t u^n = u^n\Bigl(\frac{1}{3} u^{m-n}-\frac{4}{3} t\Bigr) \ge 0.\] For such \(u\), the remainder \(R_t(u)\) is of strictly smaller order than \(u^m\), so in fact \[F_t(u)\ge \frac{A}{4}\] for all sufficiently small \(t\). On the other hand, at the trial point \(u=t^s\), \[F_t(t^s)=\frac{A}{4}+t^{p^\sharp}\Bigl(\frac{1}{3}-\frac{4}{3}+o(1)\Bigr) <\frac{A}{4}\] for small \(t\). Hence no minimizer can satisfy \(u_t\ge M t^s\), which proves the claim.

Step 9: scaling and the sharpness exponent. Set \(u=t^s v\). Since \(u_t=O(t^s)\), it suffices to analyze bounded \(v\). Uniformly for \(v\) in bounded sets, \[F_t(t^s v) = \frac{A}{4} +t^{p^\sharp} \Bigl[ \frac{1}{3} v^m-\frac{4}{3} v^n+o(1) \Bigr].\] Define \[\psi(v):=\frac{1}{3} v^m-\frac{4}{3} v^n.\] This polynomial has a unique minimizer at \[v_\star=\Bigl(\frac{4n}{m}\Bigr)^{1/(m-n)},\] and \[\psi(v_\star) = -\frac{4}{3}\Bigl(1-\frac{n}{m}\Bigr) \Bigl(\frac{4n}{m}\Bigr)^{\frac{n}{m-n}} =:-c_{m,n}<0.\] Therefore, \[\inf_{u\in[0,\bar u]}F_t(u) = \frac{A}{4} -c_{m,n}\, t^{p^\sharp} +o(t^{p^\sharp}).\] Since \(J^\star=A/4\), this gives \[J^\star-J_M(\omega^\star+t h) = c_{m,n}\, t^{m/(m-n)} +o\bigl(t^{m/(m-n)}\bigr),\] where \[c_{m,n} = \frac{4}{3}\Bigl(1-\frac{n}{m}\Bigr) \Bigl(\frac{4n}{m}\Bigr)^{\frac{n}{m-n}} >0.\] ◻

Proof. Since \(V_M^\pi=(I-\gamma P_\pi)^{-1} r_\pi\), by Cramer’s rule, \((I-\gamma P_\pi)^{-1}=\operatorname{adj}(I-\gamma P_\pi)/\det(I-\gamma P_\pi)\), with \(\det(I-\gamma P_\pi)\neq 0\) since \(\gamma\in [0,1)\). Entries of \(\operatorname{adj}(\cdot)\) and the determinant are polynomials in the entries of \(P_\pi\), hence \(V_M^\pi\) is componentwise a ratio of polynomials in \((P,r)\) for every \(s\). ◻

Proof. If \(r_\pi =c\mathbf{1}\) for some \(c\in [0,1]\), then for any \(P\) we have \(V_M^\pi=\frac{c}{1-\gamma}\mathbf{1}\). For any \(s\) and \(b\), \[Q_M^\pi(s,b)=r(s,b)+\gamma \frac{c}{1-\gamma},\qquad V_M^\pi(s)=\frac{c}{1-\gamma}.\] Optimality of \(\pi\) would require \(V_M^\pi(s)\geq Q_M^\pi(s,b)\) for all \((s,b)\), i.e. \[0\leq \frac{c}{1-\gamma}-r(s,b)-\gamma \frac{c}{1-\gamma} = c -r(s,b) \Rightarrow c\geq r(s,b)\] for all \((s,b)\), implying \(c\geq m(s)\) for all \(s\). But \(c=r_\pi(s) =r(s,\pi(s)) \leq m(s)\) for all \(s\), implying we must have \(c=m(s)\) for all \(s\), which is however a contradiction since there exist a pair \((s,s')\) s.t. \(m(s)\neq m(s')\). ◻

Proof. Write \[g_{s,a}^\pi(M)= [r(s,\pi(s))-r(s,a)] + \gamma(p-q)^\top V^\pi(P)\] for some MDP with transition \(P\) and we write \(p=P(\cdot|s,\pi(s))\), \(q=P(\cdot|s,a)\).

10.0.0.1 Sufficiency.

If \(r(s,\pi(s))=r(s,a)\) and \(r_\pi=c\mathbf{1}\) for some \(c\in [0,1]\), then \[g_{s,a}^\pi(M)= c\gamma(p-q)^\top (I-\gamma P_\pi)^{-1} \mathbf{1}\] Since \(\mathbf{1}\) is a right eigenvector of \((I-\gamma P_\pi)^{-1}\) satisfying \((I-\gamma P_\pi)^{-1}\mathbf{1}=\frac{1}{1-\gamma}\mathbf{1}\), we have that \[g_{s,a}^\pi(M)= c\gamma(p-q)^\top \mathbf{1}=0.\] which proves sufficiency.

10.0.0.2 Necessity.

Suppose \(g_{s,a}^\pi(M)\equiv 0\) on \(P\in \Delta(\mathcal{S})^{\mathcal{S}\times \mathcal{A}}\). For each \(P\) we obtain \(P_\pi\). Treat \(P_\pi\) as a fixed variable, while \(q\) is a degree of freedom. Then, we must have that \[0 = \sup_q \left| [r(s,\pi(s))-r(s,a)] + \gamma(p-q)^\top V^\pi(P)\right|.\] Since for any \(q\) we obtain \(0\), consider \(q=e_i\) and \(q=e_j\) for \(i,j\) taking value in an enumeration of \(\mathcal{S}\). Then \[[r(s,\pi(s))-r(s,a)] + \gamma(p-e_i)^\top V^\pi(P)= [r(s,\pi(s))-r(s,a)] + \gamma(p-e_j)^\top V^\pi(P)\] implying that \((e_j-e_i)^\top V^\pi(P)=0\). Since \(i,j\) are allowed to vary, this implies that \(V_P^\pi = c\mathbf{1}\) for some \(c\in \mathbb{R}\). Therefore \[g_{s,a}^\pi(M)= [r(s,\pi(s))-r(s,a)] + \gamma(p-q)^\top c\mathbf{1}= r(s,\pi(s))-r(s,a),\] implying that \(r(s,\pi(s))=r(s,a)\) if \(g_{s,a}^\pi(M)= 0\).

Now, for any fixed \(q\) consider varying \(P\) so that \(P_\pi\) varies. Since \(V_P^\pi = c\mathbf{1}=(I-\gamma P_\pi)^{-1}r_\pi\), and \(\mathbf{1}\) is the right eigenvector of \((I-\gamma P_\pi)^{-1}\), we have that \(r_\pi\) itself is proportional to \(\mathbf{1}\). Thus we conclude that \(r_\pi\) must be constant across states. ◻

Proof. By the previous lemma we know that \(g_{s,a}^\pi\) is a real rational function, thus real analytic. For a nontrivial real-analytic function, its zero set has Lebesgue measure zero.

If \(g_{s,a}^\pi\equiv 0\), then by the previous lemma we have that \(r_\pi\) is constant. But optimal policies do not admit constant \(r_\pi\) if there exists a pair \((s,s')\) such that \(m(s)\neq m(s')\), so \(\mathcal{U}^\pi=\varnothing\) and \(\mathcal{U}^\pi\cap Z_{s,a}^\pi=\varnothing\) (null). Alternatively, if \(g_{s,a}^\pi\not\equiv 0\), then \(Z_{s,a}^\pi\) is the zero set of a nontrivial real-analytic function, hence it has Lebesgue measure \(0\); intersecting with the measurable set \(\mathcal{U}^\pi\) preserves nullity. ◻

Proof. Optimal policies are w.l.o.g. deterministic. If \(P\in\mathcal{T}\), there exists an optimal deterministic \(\pi^\star\), a state \(s\), and \(a\neq \pi^\star(s)\) with \(Q^{\pi^\star}_M(s,\pi^\star(s))=Q^{\pi^\star}_M(s,a)=V_M^\star(s)\), hence \(P\in \mathcal{U}^{\pi^\star}\cap Z_{s,a}^{\pi^\star}\). Therefore \[\mathcal{T} \subseteq \bigcup_{\pi} \bigcup_{s} \bigcup_{a\neq \pi(s)} \left(\mathcal{U}^\pi\cap Z_{s,a}^\pi \right).\] Since we have a countable union of \(0\)-measure sets, we have that \(\mathcal{T}\) has measure \(0\). ◻