Proof. By [proposition:32lower32bound32mab32varying32arm32costs], for any \(t\in\brs*{T}\), there exists an instance such that \[\begin{align} \mathbb{E}\brs*{\mathrm{Reg}(t)} \ge \frac{t}{140}\min\brc*{\sqrt\frac{\sum_{a=1}^Ac(a)}{B(t)(1+\log A)},1}\enspace. \end{align}\] Let \(t_m\) be the time index in which the r.h.s. is maximized and fix the bandit problem to the corresponding instance that leads to its lower bound. Then. \[\begin{align} \mathbb{E}\brs*{\mathrm{Reg}(T)} &\!\ge\! \mathbb{E}\brs*{\mathrm{Reg}(t_m)} \\ &\!=\!\max_{t\in\brs*{T}}\brc*{ \frac{t}{140}\min\brc*{\!\sqrt\frac{\sum_{a=1}^Ac(a)}{B(t)(1+\log A)},1}}. \end{align}\] Finally, by Hölder’s inequality, if \(x,y\in\mathbb{R}^T\) are such that \(x_t,y_t\ge0\) for all \(t\in\brs*{T}\), then \[\begin{align} \max_t x_t =\norm*{x}_\infty\ge \frac{\sum_{t=1}^T x_ty_t}{\norm*{y}_1} = \frac{\sum_{t=1}^T x_ty_t}{\sum_{t=1}^T y_t} \enspace. \end{align}\] Taking \(x_t \!=\! \frac{t}{140}\min\brc*{\sqrt\frac{\sum_{a=1}^Ac(a)}{B(t)(1+\log A)},1}\) and \(y_t \!=\! \frac{1}{t}\) and recalling that \(\sum_{t=1}^T \frac{1}{t} \le1+\log T\) concludes the proof. ◻

Proof. The proof closely follows the one of Inequality (6) in [20] and only differs by ignoring rounds where \(q_t=0\). Formally, let \(\nu_{a_t,q_t}\) be the distribution of \(Y_t\) when playing \(a_t\) and querying the reward according to \(q_t\). Specifically, if \(q_t=1\), then \(\nu_{a_t,q_t}=\nu_{a_t}\), and if \(q_t=0\), it deterministically outputs \(Y_t=0\). Following the notations of [20], for any two bandit instances \({\underline{\nu}}\) and \({\underline{\nu}}'\), we let \(\mathbb{P}_{{\underline{\nu}}}\) and \(\mathbb{P}_{{\underline{\nu}}'}\) be their associated probability measures, defined in some common measurable space \((\Omega,\mathcal{F})\) (which exists by Kolmogorov’s extension theorem). Then, for any \(t\ge0\) and any Borel sets \(G\subset\mathbb{R}\) and \(G'\subset[0,1]\), our model implies that \[\begin{align} \mathbb{P}_{{\underline{\nu}}}\br*{Y_{t+1}\in G, U_{t+1}\in G' \vert I_t} = \nu_{\pi_t^a(I_t),\pi_t^q(I_t)}(B)\lambda(B') \end{align}\] where \(\lambda\) is the Lasbesgue measure on \([0,1]\). Next, for any \(t\ge0\), let \(\mathbb{P}_{{\underline{\nu}}}^{I_t}\) and \(\mathbb{P}_{{\underline{\nu}}'}^{I_t}\) be the respective distributions of \(I_t\) w.r.t. \({\underline{\nu}}\) and \({\underline{\nu}}'\), and similarly use this notation for \(Y_t\) and \(U_t\). Then, the previous relation can be written as \[\begin{align} \mathbb{P}_{{\underline{\nu}}}^{(Y_{t+1}, U_{t+1})\vert I_t} = \nu_{\pi_t^a(I_t),\pi_t^q(I_t)} \otimes\lambda\enspace, \end{align}\] where \(\otimes\) denotes the product of measures. Moreover, by the chain-rule for KL divergences, for any \(t\ge0\), we can write \[\begin{align} \mathrm{KL}\br*{{\mathbb{P}_{{\underline{\nu}}}^{I_{t+1}},\mathbb{P}_{{\underline{\nu}}'}^{I_{t+1}}}} &= \mathrm{KL}\br*{{\mathbb{P}_{{\underline{\nu}}}^{(I_t,Y_{t+1},U_{t+1})},\mathbb{P}_{{\underline{\nu}}'}^{(I_t,Y_{t+1},U_{t+1})}}}\nonumber\\ &= \mathrm{KL}\br*{{\mathbb{P}_{{\underline{\nu}}}^{I_t},\mathbb{P}_{{\underline{\nu}}'}^{I_t}}} + \mathrm{KL}\br*{{\mathbb{P}_{{\underline{\nu}}}^{(Y_{t+1},U_{t+1})\vert I_t},\mathbb{P}_{{\underline{\nu}}'}^{(Y_{t+1},U_{t+1})\vert I_t}}} \label{eq:kl32chain32rule}\enspace. \end{align}\tag{3}\] Notably, the second term can be simplified to \[\begin{align} \mathrm{KL}\br*{{\mathbb{P}_{{\underline{\nu}}}^{(Y_{t+1},U_{t+1})\vert I_t},\mathbb{P}_{{\underline{\nu}}'}^{(Y_{t+1},U_{t+1})\vert I_t}}} &= \mathbb{E}_{{\underline{\nu}}}\brs*{\mathbb{E}_{\underline{\nu}}\brs*{\mathrm{KL}\br*{\nu_{\pi_t^a(I_t),\pi_t^q(I_t)} \otimes\lambda, \nu'_{\pi_t^a(I_t),\pi_t^q(I_t)} \otimes\lambda}\big\vert I_t}} \\ &=\mathbb{E}_{{\underline{\nu}}}\brs*{\mathbb{E}_{\underline{\nu}}\brs*{\mathrm{KL}\br*{\nu_{\pi_t^a(I_t),\pi_t^q(I_t)}, \nu'_{\pi_t^a(I_t),\pi_t^q(I_t)}}\big\vert I_t}} \\ & \overset{(*)}{=} \mathbb{E}_{{\underline{\nu}}}\brs*{\mathbb{E}_{\underline{\nu}}\brs*{1{\brc*{\pi_{t+1}^q(I_t)=1}}\mathrm{KL}\br*{\nu_{\pi_t^a(I_t)}, \nu'_{\pi_t^a(I_t)}}\big\vert I_t}} \\ & = \mathbb{E}_{{\underline{\nu}}}\brs*{1{\brc*{\pi_{t+1}^q(I_t)=1}}\sum_{a=1}^A\mathrm{KL}\br*{\nu_a, \nu'_a} 1{\brc*{\pi^a_{t+1}(I_t)=a}}} \\ & = \mathbb{E}_{{\underline{\nu}}}\brs*{\sum_{a=1}^A\mathrm{KL}\br*{\nu_a, \nu'_a} 1{\brc*{a_{t+1}=a,q_{t+1}=1}}} \end{align}\] where in \((*)\) we used the fact that if \(q_{t+1}=\pi_{t+1}^q(I_t)=0\), then both distributions deterministically output \(0\), so the KL divergence is also \(0\). For the last relation, also recall that \(\pi_t^a(I_t)=a_{t+1}\) and \(\pi_{t+1}^q(I_t)=q_{t+1}\). Substituting back into 3 and applying the same argument recursively, we get \[\begin{align} \mathrm{KL}\br*{{\mathbb{P}_{{\underline{\nu}}}^{I_{T}},\mathbb{P}_{{\underline{\nu}}'}^{I_{T}}}} &= \sum_{t=1}^T\mathbb{E}_{{\underline{\nu}}}\brs*{\sum_{a=1}^A\mathrm{KL}\br*{\nu_a, \nu'_a} 1{\brc*{a_t=a,q_t=1}}} \\ & = \sum_{a=1}^A\mathbb{E}_{{\underline{\nu}}}\brs*{n^q_T(a)}\mathrm{KL}\br*{\nu_a,\nu'_a}\enspace. \end{align}\] Notice that the recursion stops at \(\mathrm{KL}\br*{{\mathbb{P}_{{\underline{\nu}}}^{I_{0}},\mathbb{P}_{{\underline{\nu}}'}^{I_{0}}}}=\mathrm{KL}\br*{{\mathbb{P}_{{\underline{\nu}}}^{U_0},\mathbb{P}_{{\underline{\nu}}'}^{U_0}}} = \mathrm{KL}\br*{\lambda,\lambda}=0\). To conclude the proof, we apply Lemma 1 of [20], which implies that for any \(\sigma(I_T)\) measurable random variable \(Z\) over \([0,1]\), it holds that \[\begin{align} \mathrm{KL}\br*{\mathbb{P}_{{\underline{\nu}}}^{I_T},\mathbb{P}_{{\underline{\nu}}'}^{I_T}} \ge \mathrm{kl}\br*{\mathbb{E}_{\underline{\nu}}\brs*{Z},\mathbb{E}_{{\underline{\nu}}'}\brs*{Z}}\enspace. \end{align}\] ◻

Proof. Our proof closely follows the proof of Theorem 6 in [20], with small modifications due to the budget. We start by applying apply 1 on \({\underline{\nu}}\) and \({\underline{\nu}}'\) with \(Z=\frac{n_T(k)}{T}\), while noticing that \(\mathrm{KL}(\nu_a,\nu_a')=0\) for all \(a\ne k\): \[\begin{align} \mathbb{E}_{{\underline{\nu}}}\brs*{n^q_T(k)}\mathrm{KL}\br*{\nu_k,\nu_k'} \ge \mathrm{kl}\br*{\frac{\mathbb{E}_{\underline{\nu}}\brs*{n_T(k)}}{T},\frac{\mathbb{E}_{{\underline{\nu}}'}\brs*{n_T(k)}}{T}} \ge 2\br*{\frac{\mathbb{E}_{\underline{\nu}}\brs*{n_T(k)}}{T}-\frac{\mathbb{E}_{{\underline{\nu}}'}\brs*{n_T(k)}}{T}}^2\enspace, \end{align}\] where the last inequality is by Pinsker’s inequality. Alternatively, we can write \[\begin{align} \abs*{\mathbb{E}_{{\underline{\nu}}'}\brs*{n_T(k)} - \mathbb{E}_{{\underline{\nu}}}\brs*{n_T(k)}} \le T\sqrt{\frac{1}{2}\mathbb{E}_{{\underline{\nu}}}\brs*{n^q_T(k)}\mathrm{KL}\br*{\nu_k,\nu_k'}}\enspace, \end{align}\] which leads to the first result of the lemma. For the second result, we directly upper bound \(\mathrm{KL}\br*{\nu_k,\nu_k'}\) for any \(\epsilon\in\br*{0,\frac{1}{4}}\) by: \[\begin{align} \mathrm{KL}\br*{\nu_k,\nu_k'} = \mathrm{kl}\br*{\frac{1}{2},\frac{1}{2}+\epsilon} = \frac{1}{2}\log\frac{1}{1-4\epsilon^2} \le 8\epsilon^2\log\frac{4}{3}\enspace, \end{align}\] where the last inequality holds since \(\log\frac{1}{1-u}\le 4u\log\frac{4}{3}\) for any \(u\in\br*{0,\frac{1}{4}}\). Substituting back to the first result of the lemma concludes the proof. ◻

Proof. Let \({\underline{\nu}}\) be an arm distribution such that all arms are Bernoulli-distributed with parameter \(\frac{1}{2}\). By the pigeonhole principle, one can prove that for any \(A\ge2\), there must exist some arm \(t\) such that both \(\mathbb{E}_{\underline{\nu}}\brs{n_T(k)}\le \frac{5T}{4A}\) and \(\mathbb{E}_{\underline{\nu}}\brs{n^q_T(k)}\le \frac{15B}{A}\) (see prove in 3 for \(\alpha = \frac{5}{4}\) and \(\beta = 15\)).

Then, we define a new bandit instance \({\underline{\nu}}'\) such that \(\nu'_a=\nu_a\) for all \(a\ne k\) and \(\nu'_k\) is Bernoulli-distributed with parameter \(\frac{1}{2}+\epsilon\), for some \(\epsilon\in\br*{0,\frac{1}{4}}\) that will be determined later. Specifically, it implies that the regret of \(\pi\) on \({\underline{\nu}}'\) is \[\begin{align} \label{eq:32lower32bound32mab32unit32costs32base} \mathbb{E}_{{\underline{\nu}}'}\brs*{\mathrm{Reg}(T)} = \sum_{a\ne k} \epsilon \mathbb{E}_{{\underline{\nu}}'}\brs*{n_T(a)} = \epsilon T\br*{1-\frac{\mathbb{E}_{{\underline{\nu}}'}\brs*{n_T(k)}}{T}}\enspace. \end{align}\tag{4}\] Thus, to lower bound the regret, we need to upper bound \(\mathbb{E}_{{\underline{\nu}}'}\brs*{n_T(k)}\). By 2, we have \[\begin{align} \mathbb{E}_{{\underline{\nu}}'}\brs*{n_T(k)} \le \mathbb{E}_{\underline{\nu}}\brs*{n_T(k)} + 2\epsilon T\sqrt{\log\frac{4}{3}}\sqrt{\mathbb{E}_{{\underline{\nu}}}\brs*{n^q_T(k)}}\enspace, \end{align}\] and recalling that \(\mathbb{E}_{\underline{\nu}}\brs*{n_T(k)}\le \frac{5T}{4A}\) and \(\mathbb{E}_{\underline{\nu}}\brs*{n^q_T(k)}\le \frac{15B}{A}\), we get \[\begin{align} \mathbb{E}_{{\underline{\nu}}'}\brs*{n_T(k)} \le \frac{5T}{4A} + 2\epsilon T\sqrt{15\br*{\log\frac{4}{3}}\frac{B}{A}}\enspace. \end{align}\] Finally, fix \(\epsilon=\frac{1}{35}\min\brc*{\sqrt{\frac{A}{B}},1}\) (and, specifically, if \(B=0\), then \(\epsilon=\frac{1}{35}\)). Since \(A\ge2\), this value of \(\epsilon\) yields \[\begin{align} \mathbb{E}_{{\underline{\nu}}'}\brs*{n_T(k)} \le \frac{5T}{4A} + \frac{1}{8}T \le \frac{3}{4}T\enspace. \end{align}\] Substituting this bound and \(\epsilon\) back to 4 leads to the desired result and concludes the proof. ◻

Proof. Without loss of generality, assume that \(c(1)\ge c(2)\ge\dots\ge c(A)\). To prove the lemma, we will show that for any \(i\in\brs*{A}\), there exists a bandit instance \({\underline{\nu}}'\) such that \[\begin{align} \label{eq:32lower32bound32different32arm32costs32one32arm} \mathbb{E}_{{\underline{\nu}}'}\brs*{\mathrm{Reg}(T)} \ge \frac{1}{140}\min\brc*{T\sqrt\frac{i c(i)}{B(1+\log A)},T}\enspace. \end{align}\tag{5}\] In turn, this will imply that there exists an instance such that \[\begin{align} \label{eq:32lower32bound32different32arm32costs32all32arms} \mathbb{E}_{{\underline{\nu}}'}\brs*{\mathrm{Reg}(T)} \ge \frac{1}{140}\min\brc*{T\sqrt\frac{\max_{i\in\brs*{A}}\brc*{i c(i)}}{B(1+\log A)},T}\enspace. \end{align}\tag{6}\] Finally, we apply Hölder’s inequality to lower bound the maximum; for vectors \(x,y\) such that \(x_i=ic(i)\) and \(y_i =\frac{1}{i}\), it holds that \[\begin{align} \max_{i\in\brs*{A}}\brc*{i c(i)} = \norm*{x}_\infty \ge \frac{\sum_{i=1}^Ax_iy_i}{\norm*{y}_1} = \frac{\sum_{i=1}^Ax_iy_i}{\norm*{y}_1} = \frac{\sum_{i=1}^Ac(i)}{\sum_{i=1}^A\frac{1}{i}} \ge \frac{\sum_{i=1}^Ac(i)}{1+\log A}\enspace. \end{align}\] Substituting this bound to 6 will then conclude the proof.

We start by proving 5 when \(i\ge2\), a proof that greatly resembles the one of [proposition:32lower32bound32mab32unit32costs]. Fix some \(2\le i \le A\) and assume that \(c(i)>0\), as otherwise, the bound trivially holds. Also, let \({\underline{\nu}}\) be an arm distribution such that all arms are Bernoulli-distributed with parameter \(\frac{1}{2}\). Notice that it holds that \(\sum_{a=1}^i \mathbb{E}_{\underline{\nu}}\brs{n_T(a)} \le T\), and since \(c(j)\ge c(i)\) for all \(j\le i\), it also holds that \(\sum_{a=1}^i \mathbb{E}_{\underline{\nu}}\brs{n^q_T(a)} \le \frac{B}{c(i)}\), or otherwise, the budget constraint is violated. Then, by 3, there must exist some arm \(k\in\brs*{i}\) such that both \(\mathbb{E}_{\underline{\nu}}\brs{n_T(k)}\le \frac{5T}{4i}\) and \(\mathbb{E}_{\underline{\nu}}\brs{n^q_T(k)}\le \frac{15B}{ic(i)}\).

Next, we define a new bandit instance \({\underline{\nu}}'\) such that \(\nu'_a=\nu_a\) for all \(a\ne k\) and \(\nu'_k\) is Bernoulli-distributed with parameter \(\frac{1}{2}+\epsilon\), for some \(\epsilon\in\br*{0,\frac{1}{4}}\). Then, by 2, we have \[\begin{align} \mathbb{E}_{{\underline{\nu}}'}\brs*{n_T(k)} \le \mathbb{E}_{\underline{\nu}}\brs*{n_T(k)} + 2\epsilon T\sqrt{\log\frac{4}{3}}\sqrt{\mathbb{E}_{{\underline{\nu}}}\brs*{n^q_T(k)}}\enspace, \end{align}\] and recalling that \(\mathbb{E}_{\underline{\nu}}\brs*{n_T(k)}\le \frac{5T}{4i}\) and \(\mathbb{E}_{\underline{\nu}}\brs*{n^q_T(k)}\le \frac{15B}{i c(i)}\), we get \[\begin{align} \mathbb{E}_{{\underline{\nu}}'}\brs*{n_T(k)} \le \frac{5T}{4i} + 2\epsilon T\sqrt{15\br*{\log\frac{4}{3}}\frac{B}{i c(i)}}\enspace. \end{align}\] Finally, fix \(\epsilon=\frac{1}{35}\min\brc*{\sqrt{\frac{i c(i)}{B}},1}\) (and, specifically, if \(B=0\), then \(\epsilon=\frac{1}{35}\)). Since \(i\ge2\), this value of \(\epsilon\) yields \[\begin{align} \mathbb{E}_{{\underline{\nu}}'}\brs*{n_T(k)} \le \frac{5T}{4A} + \frac{1}{8}T \le \frac{3}{4}T\enspace. \end{align}\] Finally, as in the proof of [proposition:32lower32bound32mab32unit32costs], we lower bound the regret by \[\begin{align} \mathbb{E}_{{\underline{\nu}}'}\brs*{\mathrm{Reg}(T)} = \sum_{a\ne k} \epsilon \mathbb{E}_{{\underline{\nu}}'}\brs*{n_T(a)} = \epsilon T\br*{1-\frac{\mathbb{E}_{{\underline{\nu}}'}\brs*{n_T(k)}}{T}} \ge \frac{1}{140}\min\brc*{T\sqrt\frac{i c(i)}{B},T}\enspace, \end{align}\] which leads to 5 for any \(2\le i\le A\).

Finally, we prove that 5 holds when \(i=1\). If \(c(1)=0\), the result trivially holds. Otherwise, by our assumptions, we have that \(\mathbb{E}_{\underline{\nu}}\brs*{n^q_T(k)}\le \frac{B}{c(i)}\). For \(\mathbb{E}_{\underline{\nu}}\brs*{n^q_T(1)}\), we divide the proof into to cases:

• If \(\mathbb{E}_{\underline{\nu}}\brs*{n_T(1)}\le \frac{T}{2}\), we set \({\underline{\nu}}'\) such that \(\nu'_a=\nu_a\) for all \(a>1\) and \(\nu'_1\) is Bernoulli-distributed with parameter \(\frac{1}{2}+\epsilon\). Then, by 2, we have \[\begin{align} \mathbb{E}_{{\underline{\nu}}'}\brs*{n_T(k)} \le \mathbb{E}_{\underline{\nu}}\brs*{n_T(1)} + 2\epsilon T\sqrt{\log\frac{4}{3}}\sqrt{\mathbb{E}_{{\underline{\nu}}}\brs*{n^q_T(1)}} \le \frac{T}{2} + 2\epsilon T\sqrt{\log\frac{4}{3}}\sqrt{\frac{B}{c(1)}}\enspace, \end{align}\] and fixing \(\epsilon=\frac{1}{5}\min\brc*{\sqrt{\frac{c(1)}{B}},1}\) (or \(\epsilon=\frac{1}{5}\) when \(B=0\)) leads to \[\begin{align} \mathbb{E}_{{\underline{\nu}}'}\brs*{n_T(k)} \le \frac{3T}{4}\enspace. \end{align}\] Then, the regret for this instance is lower bounded by \[\begin{align} \mathbb{E}_{{\underline{\nu}}'}\brs*{\mathrm{Reg}(T)} = \sum_{a\ne 1} \epsilon \mathbb{E}_{{\underline{\nu}}'}\brs*{n_T(a)} = \epsilon T\br*{1-\frac{\mathbb{E}_{{\underline{\nu}}'}\brs*{n_T(1)}}{T}} \ge \frac{1}{20}\min\brc*{T\sqrt\frac{c(1)}{B},T}\enspace, \end{align}\]

• If \(\mathbb{E}_{\underline{\nu}}\brs*{n_T(1)}\ge \frac{T}{2}\), we set \({\underline{\nu}}'\) such that \(\nu'_a=\nu_a\) for all \(a>1\) and \(\nu'_1\) is Bernoulli-distributed with parameter \(\frac{1}{2}-\epsilon\). Then, by 2, we have \[\begin{align} \mathbb{E}_{{\underline{\nu}}'}\brs*{n_T(k)} \ge \mathbb{E}_{\underline{\nu}}\brs*{n_T(1)} - 2\epsilon T\sqrt{\log\frac{4}{3}}\sqrt{\mathbb{E}_{{\underline{\nu}}}\brs*{n^q_T(1)}} \ge \frac{T}{2} - 2\epsilon T\sqrt{\log\frac{4}{3}}\sqrt{\frac{B}{c(1)}}\enspace, \end{align}\] and fixing \(\epsilon=\frac{1}{5}\min\brc*{\sqrt{\frac{c(1)}{B}},1}\) (or \(\epsilon=\frac{1}{5}\) when \(B=0\)) leads to \[\begin{align} \mathbb{E}_{{\underline{\nu}}'}\brs*{n_T(k)} \ge \frac{T}{4}\enspace. \end{align}\] Then, the regret for this instance is lower bounded by \[\begin{align} \mathbb{E}_{{\underline{\nu}}'}\brs*{\mathrm{Reg}(T)} = \epsilon \mathbb{E}_{{\underline{\nu}}'}\brs*{n_T(1)} \ge \frac{1}{20}\min\brc*{T\sqrt\frac{c(1)}{B},T}\enspace, \end{align}\]

Combining both cases leads to 5 (with a better constant) and concludes the proof. ◻

Proof. We divide the proof into the case where \(n\le \beta\) and \(n\ge \beta\).

If \(n\le \beta\), recall that \(y_i\ge0\) and \(\sum_{i=1}^n y_i\le Y\). Therefore, for any \(i\in\brs*{n}\), \(y_i\le Y \le \frac{\beta}{n} Y\), and the required condition holds for all coordinates. Moreover, as \(\alpha>1\), by the pigeonhole principle, there exists at least one coordinate \(t\) such that \(x_t\le \frac{X}{n}\le \frac{\alpha X}{n}\). Then, for this coordinate, both required conditions hold.

Next, we analyze the case where \(n>\beta\). First notice that by the pigeonhole principle, there are at least \(\floor*{\br*{1-\frac{1}{\alpha}}n}\) coordinates such that \(x_i\le \frac{\alpha X}{n}\). To see this, assume in contradiction that this does not hold. Then, there are at least \(n-\floor*{\br*{1-\frac{1}{\alpha}}n}\ge \frac{n}{\alpha}\) coordinates such that \(x_i> \frac{\alpha X}{n}\), and \[\begin{align} \sum_{i=1}^n x_i \ge \sum_{i=1}^n x_i \cdot 1{\brc*{x_i> \frac{\alpha X}{n}}} > \frac{\alpha X}{n} \cdot \abs*{\brc*{i:x_i> \frac{\alpha X}{n} }} \ge \frac{\alpha X}{n} \cdot \frac{n}{\alpha} =X\enspace \end{align}\] which violates the assumption that \(\sum_{i=1}^d x_i \le X\). Similarly, there are at least \(\floor*{\br*{1-\frac{1}{\beta}}n}\) coordinates such that \(y_i\le \frac{\beta Y}{n}\). The number of coordinates for which at least one of the condition holds is then \[\begin{align} \sum_{i=1}^n 1{\brc*{x_i \le \frac{\alpha X}{n}}} + 1{\brc*{y_i \le \frac{\beta Y}{n}}} &\ge \floor*{\br*{1-\frac{1}{\alpha}}n} + \floor*{\br*{1-\frac{1}{\beta}}n} \\ & \ge \br*{1-\frac{1}{\alpha}}n -1 + \br*{1-\frac{1}{\beta}}n - 1 \\ & = \br*{1 - \frac{1}{\alpha} - \frac{1}{\beta}}n + n - 2 \end{align}\] We then use the fact that \(n>\beta\) to bound the first term as \[\begin{align} \br*{1 - \frac{1}{\alpha} - \frac{1}{\beta}}n > \br*{1 - \frac{1}{\alpha} - \frac{1}{\beta}}\beta = \beta\br*{1-\frac{1}{\alpha}} - 1 \ge 2\enspace, \end{align}\] where the last inequality is since \(\alpha>1\) and \(\beta\ge \frac{3\alpha}{\alpha-1} = 3 \frac{1}{1-1/\alpha}\). Substituting back leads to \[\begin{align} \sum_{i=1}^n 1{\brc*{x_i \le \frac{\alpha X}{n}}} + 1{\brc*{y_i \le \frac{\beta Y}{n}}} > 2 + n -2 = n\enspace. \end{align}\] Thus, there are strictly more than \(n\) coordinates where at least one condition holds, which implies that there is at least one coordinate \(t\) for which both conditions holds, i.e., \(x_t\le \frac{\alpha X}{n}\) and \(y_t\le \frac{\alpha Y}{n}\) ◻

Proof. Our proof closely follows the standard lower bound techniques used for proving the fundamental performance limit for linear bandits [33]. Notably, we prove the lower bound for a problem with a fixed context space \(\mathcal{X}=\brs*{-1,1}^d\). Therefore, the conditions of [proposition:32greedy32algorithm32equivalent] hold; namely, for any fixed problem, there exists a modified policy \(\pi'\) with the same expected regret as \(\pi\) that queries all rewards at the first \(B\) rounds. Thus, and without loss of generality, we assume that all rewards are queried at the \(B\) initial rounds.

As described in 2, we assume that the reward when choosing a context \(x_t\) is \(R_t=\inner{x_t,\theta}+\eta_t\) for some unknown \(\theta\).In this section, we limit \(\theta\in \Theta \triangleq \brc*{-\frac{1}{\sqrt B},\frac{1}{\sqrt B}}^d\). Moreover, we assume that the noises \(\eta_t \sim \mathcal{N}(0,1)\) are i.i.d. standard Gaussian variables. Notably, for a given \(\theta\), one can easily observe that the optimal context \(x^*=\arg\max_{x\in\mathcal{X}}\inner{x,\theta}\) is such that \(x^*(i)=\text{sign}(\theta(i)),\forall i\in\brs*{d}\). We also use the notation \(Y_t = R_t\cdot q_t\) to denote the reward observed by the agent and write \(R_t(\theta)\) when we want to emphasize the parameter that governed the reward generation.

Suppose that \(x_1,\dots,x_T\) are the contexts played by \(\pi\) at rounds \(1,\dots,T\) and for any fixed problem with parameter \(\theta\), denote the measure of contexts and queried rewards induced by the interaction of \(\pi\) with the problem by \(\mathbb{P}_\theta\). Then, we lower bound the regret by \[\begin{align} \mathbb{E}\brs*{\mathrm{Reg}(T)} &= \mathbb{E}\brs*{\sum_{t=1}^T \inner{x^*,\theta}-\inner{x_t,\theta}} \nonumber\\ &= \mathbb{E}\brs*{\sum_{t=1}^T \sum_{i=1}^d \abs*{\theta(i)}-x_t(i)\theta(i)}\nonumber\\ & \ge \sum_{i=1}^d \abs*{\theta(i)}\mathbb{E}\brs*{\sum_{t=1}^T 1{\brc*{\text{sign}(\theta(i)) \neq \text{sign}(x_t(i))}} }} \nonumber \\ &\ge \sum_{i=1}^d\abs*{\theta(i)}\frac{T}{2}\mathbb{E}\brs*{1{\brc*{\sum_{t=1}^T 1{\brc*{\text{sign}(\theta(i)) \neq \text{sign}(x_t(i))}}}}\ge \frac{T}{2}} \nonumber\\ &= \frac{T}{2\sqrt B} \sum_{i = 1}^{d}\mathbb{P}_{\theta}(i)~, \label{eq:lb195m} \end{align}\tag{7}\] where we denoted \(\mathbb{P}_{\theta}(i) := \mathbb{P}_{\theta}\br*{ \sum_{t = 1}^{T}1{\brc*{\text{sign}(\theta(i)) \neq \text{sign}(x_{t}(i)}} ) \ge \frac{T}{2} }\). Next, we lower bound \(\sum_{i = 1}^{d}\mathbb{P}_{\theta}(i)\).

For any choice of \(\theta \in \Theta\) and \(i \in [d]\), let \(\theta^i\) be a vector such that \(\theta^i(j) = \theta(j), \, \forall j \in [d]\setminus\{i\}\) and \(\theta^i(i) = -\theta(i)\). Now let us define \(\mathbb{P}^c_{\theta^{i}}(i) := \mathbb{P}_{\theta^{i}}\bigg( \sum_{t = 1}^{T}(\text{sign}(\theta^{i}_i) \neq \text{sign}(x_{ti}) ) \le \frac{T}{2} \bigg)\). By applying Bretagnolle-Huber inequality [33], [34] we further get that for any \(\theta \in \mathbb{R}^d\): \[\begin{align} \mathbb{P}_{\theta}(i) + \mathbb{P}^c_{\theta^{i}}(i) \ge \frac{1}{2}\exp\brc*{-\mathrm{KL}(\mathbb{P}_{\theta},\mathbb{P}_{\theta^i})}~, \end{align}\] where \(\mathrm{KL}(\cdot,\cdot)\) denotes the Kullback–Leibler divergence. Applying the chain rule of KL-divergence while recalling that the policy for both bandit instances is the same, we get: \[\begin{align} \mathbb{P}_{\theta}(i) + \mathbb{P}^c_{\theta^{i}}(i) & \ge \frac{1}{2}\exp\brc*{-\sum_{t = 1}^T \mathrm{KL}\br*{\mathbb{P}_{\theta}(Y_t(\theta) ),\mathbb{P}_{\theta^i}(Y_t(\theta^i)) \vert x_1,Y_1,\dots,x_{t-1},Y_{t-1},x_t}} \\ & \overset{(a)}{=} \frac{1}{2}\exp\brc*{-\sum_{t = 1}^B \mathrm{KL}\br*{\mathbb{P}_{\theta}(Y_t(\theta) ),\mathbb{P}_{\theta^i}(Y_t(\theta^i))\vert x_t}} \\ & \overset{(b)}{=} \frac{1}{2}\exp\brc*{-\frac{1}{2}\sum_{t=1}^B\br*{\inner{x_t,\theta - \theta^i}}^2} \\ &\overset{(c)}{\ge} \frac{1}{2}\exp(-2), \end{align}\] Relation \((a)\) follows since we assume the algorithm only queries for feedback for the first \(B\) rounds, so \(Y_t\ne0\) only generated for the first \(B\) rounds, and the algorithm does not observe any feedback for the last \(T-B\) rounds. Moreover, this relation also requires the assumption that the noise \(\eta_t\) is i.i.d, and therefore, the reward only depends on the chosen context \(x_t\). Furthermore, since we assume that \(\eta_t \sim \mathcal{N}(0,1)\), \((b)\) follows by direct calculation: \[\mathrm{KL}\br*{\mathbb{P}_{\theta}(R_t(\theta)),\mathbb{P}_{\theta^i}(R_t(\theta^i))\vert x_t} = \mathrm{KL}\br*{\mathcal{N}(\inner{x_t,\theta},1),N(\inner{x_t,\theta^i},1)\vert x_t} = \br*{x_t^T(\theta - \theta^i)}^2.\] Relating \((c)\) holds since \(\theta(j)=\theta^i(j)\) for all \(j\ne i\), \(\abs*{\theta(i)-\theta^i(i)}=2/\sqrt{B}\) and \(x_t(i)\in [-1,1]\); thus, we have that \(\br*{x_t^T(\theta - \theta^i)}^2 = x_t(i)^2\br*{\theta(i) - \theta^i(i)}^2\le 4/B\).

Finally, notice that this holds for any \(\theta \in \Theta\) and averaging over all \(\theta \in \Theta\) we get: \[\frac{1}{|\Theta|}\sum_{\theta \in \Theta}\sum_{i = 1}^d\mathbb{P}_{\theta}(i) \sum_{i = 1}^d\frac{1}{|\Theta|}\sum_{\theta \in \Theta}\mathbb{P}_{\theta}(i) \ge \frac{d \exp(-2)}{4}.\] This implies there exists at least one \(\theta \in \Theta\), say \(\tilde{\theta}\), for which \(\sum_{i = 1}^d\mathbb{P}_{\tilde{\theta}}(i) > \frac{d\exp(-2)}{4}\). The claim now follows from 7 and setting \(\theta = \tilde{\theta}\). ◻

Proof. Let \(\brc{B(t)}_{t\geq 1}\) be any fixed budget sequence and let \(T\in\mathbb{N}\) be some arbitrary time. For brevity, and with slight abuse of notation, we denote \(f(u,\pi)=\mathbb{E}\brs*{f(R_t)\vert u,\pi}\) and \(\pi^*(u) = \arg\max_{\pi\in\Pi(u)} \mathbb{E}\brs*{f(u,\pi)}\). Under these notations, the expected regret can also be written as \[\begin{align} \mathbb{E}\brs*{\mathrm{Reg}(T)} = \mathbb{E}\brs*{\sum_{t=1}^Tf(u_t,\pi^*(u_t))- f(u_t,\pi_t)}. \end{align}\] Also, let \(1{\brc*{Q_t}}=1{\brc*{q_t=1}}\) be the indicator function of the event a reward was queried at the \(t^{th}\) time step. Importantly, the greedy query rule of 1 does not depend on the observations, and for this reason, the sequence \(\brc*{1{\brc*{Q_t}}}_{t\geq 1}\) is fixed given \(\brc{B(t)}_{t\geq 1}\). Let \(B^q(t) = \sum_{s=1}^{t-1} 1{\brc*{Q_s}}\) be number of times a budget was used until time step \(t\). Let \(\brc{E_1(t), E_2(t)}_{t\geq 0}\) be sequence of events defined as \[\begin{align} &E_1(t) = \brc*{B(t)\geq B^q(t)+1, B(t-1) < B^q(t-1)+1}\\ &E_2(t) = \brc*{B(t)< B^q(t)+1, B(t-1) \geq B^q(t-1)+1}. \end{align}\] In words, \(E_1(t)\) represents the event that at time step \(t\) budget became available whereas at time step \(t-1\) it was not available. Furthermore, \(E_2(t)\), represents the event budget became unavailable at time step \(t\) whereas it was available at time step \(t-1\). Furthermore, define the following time steps (which are deterministic for a fixed budget sequence) \[\begin{align} &\tau_{1}(k) = \inf\brc*{t: \sum_{i=1}^t 1{\brc*{E_1(i)}}\geq k}\qquad\quad \mathrm{and}\qquad\quad \tau_{2}(k) = \inf\brc*{t: \sum_{i=1}^t 1{\brc*{E_2(i)}}\geq k}. \end{align}\] That is, \(\tau_{1}(k)\) is the \(k^{th}\) time the budget became available and \(\tau_{2}(k)\) is the \(k^{th}\) time the budget became unavailable. We now prove the following claim. For any time step \(T\) the expected regret of Algorithm 1 is bounded by \[\begin{align} \mathbb{E}[\mathrm{Reg}(T)]\leq \mathbb{E}\brs*{\sum_{t\in \mathcal{I}^q_T} f(u_t,\pi^*(u_t))- f(u_t,\pi_t) } +\sum_{t=1}^{T} \frac{\alpha}{B(t)^{1-\beta}} + \frac{C}{B(t)}, \label{eq:32induction32proof32to32show} \end{align}\tag{8}\] where \(\mathcal{I}^q_t = \brc{k\in [t]: 1{\brc*{Q_k}}=1}\), i.e., all time steps until time step \(t\) in which a reward was queried. Notice that these are the only time steps where algorithm \(\mathbb{A}\) advances, so the algorithm has been effectively applied only on these time steps. Then, by the anytime regret assumption on algorithm \(\mathbb{A}\) it holds that the first term in 8 is bounded by \(\alpha \abs*{\mathcal{I}^q_T}^\beta = \alpha\br*{B^q(T)}^\beta \leq \alpha \min\brc*{B(T),T}^\beta + C\) which completes the proof.

We establish 8 via an induction on time steps in which the budget becomes unavailable, that is on \(\tau_2(1),\tau_2(2),\cdots\). Assume that at \(t=1\), there is an available budget, that is, \(B(1)\geq 1\).

9.0.0.1 Base case. The claim holds for all \(t\in[1,\tau_{2}(k=1) -1]\).

By assumption and definition, for all \(t\in [1,\tau_{2}(1)-1]\) Algorithm 1 query rewards. For this reason, the regret is bounded by the regret of algorithm\(~\mathbb{A}\). Thus, for all \(t\in [1,\tau_{2}(1)-1]\) \[\begin{align} &\mathrm{Reg}(t) = \mathbb{E}\brs*{\sum_{t\in \mathcal{I}^q_t} f(u_t,\pi^*(u_t))- f(u_t,\pi_t) } \leq \mathbb{E}\brs*{\sum_{t\in \mathcal{I}^q_t} f(u_t,\pi^*(u_t))- f(u_t,\pi_t) } +\sum_{l=1}^{t} \frac{\alpha}{B(l)^{1-\beta}} + \frac{C}{B(l)}. \end{align}\]

9.0.0.2 Induction Step: Proving that the claim holds for all \(t\in [1,\tau_{2}(k+1)-1]\).

Assume the claim holds until time step \(t_k= \tau_{2}(k)-1\), that is, until the \(k^{th}\) time the budget becomes unavailable. We now prove the regret bound holds until the \((k+1)^{th}\) time the budget becomes unavailable for \(k\geq 1\) (if no such time exists then the exact same proof holds by replacing \(\tau_{2}(k+1)\) by \(\min\brc*{\tau_{2}(k+1),T+1}\) and \(\tau_1(k+ 1)\) by \(\min\brc*{\tau_{1}(k+1),T+1}\)). Consider the time steps between the \(k^{th}\) and \((k+1)^{th}\) time the budget becomes unavailable. We can partition the time steps into two parts \([\tau_{2}(k),\tau_{1}(k+1)-1]\), \(\brc{\tau_{1}(k+1),..,\tau_{2}(k+1)-1}\), that it, between the \(k^{th}\) and \((k+1)^{th}\) time the budget becomes unavailable there exists a time step \(\tau_{1}(k+1)\) in which the budget becomes available for the \((k+1)^{th}\) time (since we assumed at the first time step a budget is available, so \(\tau_1(1)=1\) and \(\tau_2(1)>1\)). Furthermore, let \(\mathrm{Reg}(t_1:t_2)=\sum_{t_1}^{t_2} f(u_t,\pi^*(u_t))- f(u_t,\pi_t)\) be partial sum of the cummulative regret. The following relations hold. \[\begin{align} \mathbb{E}[\mathrm{Reg}(&\tau_{2}(k+1)-1)] \nonumber\\ &= \mathbb{E}[\mathrm{Reg}(\tau_{2}(k)-1)] + \mathbb{E}[\mathrm{Reg}(\tau_{2}(k):\tau_{2}(k+1)-1)] \\ &\leq \mathbb{E}\brs*{\sum_{t\in \mathcal{I}^q_{\tau_{2}(k)}} f(u_t,\pi^*(u_t))- f(u_t,\pi_t) } +\sum_{t=1}^{\tau_{2}(k)-1} \br*{\frac{\alpha}{B(t)^{1-\beta}} + \frac{C}{B(t)}} + \mathbb{E}[\mathrm{Reg}(\tau_{2}(k):\tau_{2}(k+1)-1)] \\ &= \mathbb{E}\brs*{\sum_{t\in \mathcal{I}^q_{\tau_{2}(k)}} f(u_t,\pi^*(u_t))- f(u_t,\pi_t) } + \sum_{t=1}^{\tau_{2}(k)-1} \br*{\frac{\alpha}{B(t)^{1-\beta}} + \frac{C}{B(t)}} + \mathbb{E}[\mathrm{Reg}(\tau_{2}(k):\tau_{1}(k+1)-1)] \nonumber\\ &\quad+ \mathbb{E}\brs*{\sum_{t=\tau_1(k+1)}^{\tau_2(k+1)-1} f(u_t,\pi^*(u_t))- f(u_t,\pi_t) } \nonumber\\ &= \mathbb{E}\brs*{\sum_{t\in \mathcal{I}^q_{\tau_{2}(k+1)-1}} f(u_t,\pi^*(u_t))- f(u_t,\pi_t) } + \sum_{t=1}^{\tau_{2}(k)-1} \br*{\frac{\alpha}{B(t)^{1-\beta}} + \frac{C}{B(t)}} + \mathbb{E}[\mathrm{Reg}(\tau_{2}(k):\tau_{1}(k+1)-1)]. \label{eq:32gap32adv32stoc32contexts} \end{align}\tag{9}\] where the equalities are by the regret definition and since in the interval \(\brs*{\tau_{2}(k),\tau_{2}(k+1)-1}\), rewards were queried only at \(\brs*{\tau_{1}(k),\tau_{2}(k+1)-1}\); therefore, \(\mathcal{I}^q_{\tau_{2}(k+1)-1} = \mathcal{I}^q_{\tau_{2}(k)-1}\cup\brc*{\tau_{1}(k),\dots,\tau_{2}(k+1)-1}\). All that remains is to bound \(\mathbb{E}[\mathrm{Reg}(\tau_{2}(k):\tau_{1}(k+1)-1)]\). In time steps \(t\in [\tau_{2}(k):\tau_{1}(k+1)-1]\) there is no available budget and Algorithm 1 acts in accordance to one of the previous queried rounds; i.e., \(j\sim Uniform(I^q_t)\) and \(\pi_t\!=\!A_j(u_t)\). Notably, in these time steps, we have \(I^q_t=I^q_{\tau_2(k)-1}\). Also recall that \(\mathcal{I}^q_{\tau_{2}(k)-1}\) is deterministic given \(\brc{B(t)}_{t\geq 1}\). Thus, the expected value of \(\pi_t\) is given by \[\begin{align} \mathbb{E}[ f(u_t,\pi^*(u_t))- f(u_t,\pi_t)] &= \mathbb{E}[\mathbb{E}[ f(u_t,\pi^*(u_t))- f(u_t,\pi_t) \vert F_{\tau_{2}(k)-1}]]\\ & = \mathbb{E}\brs*{\frac{1}{ \abs*{I^q_{\tau_2(k)-1}} }\sum_{j\in I^q_{\tau_2(k)-1}} \mathbb{E}[ f(u_t,\pi^*(u_t))- f(u_t,\mathbb{A}_j(u_t)) \vert F_{\tau_{2}(k)-1}]}\\ & \overset{(1)}{=} \mathbb{E}\brs*{\frac{1}{ \abs*{I^q_{\tau_2(k)-1}} }\sum_{j\in I^q_{\tau_2(k)-1}} \mathbb{E}[ f(u_t,\pi^*(u_t))- f(u_t,\mathbb{A}_j(u_t)) \vert F_{\tau_{2}(j)-1}]} \\ & \overset{(2)}{=} \mathbb{E}\brs*{\frac{1}{ \abs*{I^q_{\tau_2(k)-1}} }\sum_{j\in I^q_{\tau_2(k)-1}} \mathbb{E}[ f(u_j,\pi^*(u_j))- f(u_t,\mathbb{A}_j(u_j)) \vert F_{\tau_{2}(j)-1}]} \\ & = \frac{1}{ \abs*{I^q_{\tau_2(k)-1}} }E\brs*{\sum_{j\in I^q_{\tau_2(k)-1}} f(u_j,\pi^*(u_j))- f(u_t,\mathbb{A}_j(u_j))} \\ &\overset{(3)}{\le} \frac{\alpha\abs*{I^q_{\tau_2(k)-1}}^\beta + C}{\abs*{I^q_{\tau_2(k)-1}}} \\ & \overset{(4)}{=} \frac{\alpha}{B(\tau_{2}(k))^{1-\beta}} + \frac{C}{B(\tau_{2}(k))}. \end{align}\] Relation \((1)\) is since rewards and contexts are i.i.d. between rounds and \(\mathbb{A}_j\) only depends on samples in \(\mathcal{I}^q_{\tau(j)-1}\). Equality \((2)\) is since the contexts are i.i.d. and \(\mathbb{A}_j\) only depends on samples in \(F_{\tau_{2}(j)-1}\) and internal randomness; therefore, for any \(t\ge j\), \[\begin{align} \mathbb{E}[ f(u_t,\pi^*(u_t))- f(u_t,\mathbb{A}_j(u_t)) \vert F_{\tau_{2}(j)-1}] = \mathbb{E}[ f(u_j,\pi^*(u_j))- f(u_j,\mathbb{A}_j(u_j)) \vert F_{\tau_{2}(j)-1}]\enspace. \end{align}\] Next, \((3)\) is by the regret bound of algorithm \(\mathbb{A}\) on samples in \(I^q_{\tau_2(k)-1}\), the only rounds where the algorithm advanced. Finally, \((4)\) holds since the the budget at time step \(\tau_{2}(k)\) equals to the number of queries at time step \(\tau_{2}(k)-1\) (if not, then there is an available budget at time step \(\tau_{2}(k)\), in contradiction to its definition). Plugging this back into 9 we get \[\begin{align} \eqref{eq:32gap32adv32stoc32contexts} &\leq \mathbb{E}\brs*{\sum_{t\in \mathcal{I}^q_{\tau_{2}(k+1)-1}} f(u_t,\pi^*(u_t))- f(u_t,\pi_t) } +\sum_{t=1}^{\tau_{2}(k)} \br*{\frac{\alpha}{B(t)^{1-\beta}} + \frac{C}{B(t)}} + (\tau_{1}(k+1)-1 - \tau_{2}(k))\alpha B(\tau_{2}(k)) ^{\beta -1 }\\ & = \mathbb{E}\brs*{\sum_{t\in \mathcal{I}^q_{\tau_{2}(k+1)-1}} f(u_t,\pi^*(u_t))- f(u_t,\pi_t) } +\sum_{t=1}^{\tau_{1}(k+1)-1} \br*{\frac{\alpha}{B(t)^{1-\beta}} + \frac{C}{B(t)}} (k),\tau_{1}(k+1)]}\\ &\leq \mathbb{E}\brs*{\sum_{t\in \mathcal{I}^q_{\tau_{2}(k+1)-1}} f(u_t,\pi^*(u_t))- f(u_t,\pi_t) } +\sum_{t=1}^{\tau_{2}(k+1)-1} \br*{\frac{\alpha}{B(t)^{1-\beta}} + \frac{C}{B(t)}}, \end{align}\] which proves the induction hypothesis. ◻

Proof. We prove the claim iteratively; specifically, we prove that for any \(b\in\brc*{0,\dots,B-1}\) and any policy \(\pi^b\) for which \(q_t=1 ,\forall t \in\brs*{b}\), there exists a policy \(\pi^{b+1}\) such that \(q_t=1 ,\forall t \in\brs*{b+1}\) and \(\mathbb{E}\brs*{\mathrm{Reg}(T)\vert \pi^{b+1}}=\mathbb{E}\brs*{\mathrm{Reg}(T)\vert \pi^b}\). Then, we can choose \(\pi^0=\pi\) and apply this result \(B\) times to obtain \(\pi'=\pi^B\) for which \(q_t=1\) for all \(t\in\brs*{B}\) and \(\mathbb{E}\brs*{\mathrm{Reg}(T)\vert \pi'}=\mathbb{E}\brs*{\mathrm{Reg}(T)\vert \pi}\).

To prove this claim, we further delve into the probabilistic model of the decision-making problem, which we carefully choose for this prove (see, e.g., [33], Chapters 4.6,4.7, for more details). Notice that under our assumptions, the action set is fixed for all time steps and only reward is generated. Also recall that under our model, and given the action, the reward is generated independently of other rounds. Denote by \(\nu_a\), the distribution of \(R_t\) given an action \(a\) was taken, and let \(B^q(t)\) be the number of queries taken up to time \(t\). Then, we describe the decision-process through the following random variables:

• \(U\) is a uniform random that is generated prior to the game and represents all randomness of the agent

• \(a_1\dots,a_T\) and \(q_1,\dots,q_T\) are the (random) actions and queries taken by the agent

• We let \(R_1^q,\dots,R_T^q\) and \(R_1^u,\dots,R_T^u\) be two reward sequences, one for queried actions and one for unqueried ones. Formally, if \(q_t=1\), then \(R_{B^q(t)}^q\) is sampled independently at random from \(\nu_{a_t}\) and \(R_t = R_{B^q(t)}^q\). Similarly, if \(q_t=0\), then \(R_{t-B^q(t)}^u\) is sampled independently at random from \(\nu_{a_t}\) and \(R_t = R_{t-B^q(t)}^u\). We brevity, we denote \(Y_t = R_t\cdot q_t\).

• We emphasize that under this model, a policy \(\pi_t\) deterministically maps \(U\), \(t\) and the sequence \(\brc*{Y_k}_{k:q_k=1}\) to action and queries \(a_t^\pi\) and \(q_t^\pi\) (given the internal randomization, the decision rule is deterministic, so previous actions are not needed to describe the mapping).

Now, let \(b\in\brc*{0,\dots,B-1}\) and let \(\pi=\pi^b\) be a policy such that \(q_t=1\) for all \(n\in\brs*{b}\), and let \(U,Y_1,\dots,\dots, Y_{b}\) an instantiation of the internal randomness and the rewards. Notably, under our model, \(Y_t=R_t^q\) for all \(t\in\brs*{b}\). Also note that until a new query is taken, the policy receives no new input. This implies that the action sequence up to the \((b+1)^{th}\)-query is deterministic given \(U,Y_1,\dots,\dots, Y_{b}\). We denote this time by \(\tau(b+1)\) and say that \(\tau(b+1)=\phi\) if no additional query is taken.

Next, we define a new policy \(\pi'=\pi^{b+1}\) as follows:

• For any \(t\le b\) we fix \(\pi'=\pi\).

• For any \(U,Y_1,\dots,\dots, Y_{b}\), if \(\tau(b+1)=\phi\), we set \(q_{b+1}^{\pi'}=1\) but continue choosing \(a_t^{\pi'} = a_t^{\pi}\) for all \(t\ge b+1\) and \(q_{b+1}^{\pi'}=0\) for any \(t\ge b+2\).

• For any \(U,Y_1,\dots,\dots, Y_{b}\), if \(\tau(b+1)\ne\phi\), we permute the action at time \(\tau(b+1)\) to time \(b+1\) and delay the actions of \(\pi\) at times \(b+1,\dots,\tau(b+1)-1\) by a single time step. Formally:

  • \(a_{b+1}^{\pi'} = a_{\tau(b+1)}^{\pi^{b}}\) and \(q_{b+1}=1\).

  • \(a_{t}^{\pi'} = a_{t-1}^{\pi^{b}}\) and \(q_{t}=0\) for all \(t\in\brc*{b+2,\dots,\tau(b+1)}\).

  • \(\pi'_t=\pi_t\) for all \(t>\tau(b+1)\).

Clearly, \(q_t^{\pi'}=1 ,\forall t \in\brs*{b+1}\). Thus, it remains to prove that \(\mathbb{E}\brs*{\mathrm{Reg}(T)\vert \pi'}=\mathbb{E}\brs*{\mathrm{Reg}(T)\vert \pi}\). Denote the instantaneous regret of algorithm \(\pi\) by \(r_t^\pi = \max_{\pi\in\Pi}\mathbb{E}\brs*{f(R_t)\vert \pi} - f(R_t)\), where \(R_t\) is generated when playing according to \(\pi\). We use a coupling argument, where as long as the policies agree, the model simultaneously generates the same reward for both process. As soon as either \(R_k^q\) or \(R_k^u\) is supposed to be generated from a different action, then the processes split into two independent process and continue separately. Since \(\pi'_t=\pi_t\) for all \(t\le b\), it also implies that the action and reward processes for both polices are identical up to time \(b\) and \(r_t^{\pi'} = r_t^\pi\) for all \(t\le b\).

For the rest of the time steps, for any instantiation of \(U,Y_1,\dots,Y_b\), we divide the analysis into two cases:

1. \(\tau(b+1)\ne\phi\). In this case, notice that during time steps \(b+1,\dots,\tau(b+1)\), both policies generate \(R_{b+1}^q\) from \(a_{\tau(b+1)}^\pi\) and generate \(R_1^u,\dots,R_{\tau(b+1)-b-1}\) from \(a_{b+1}^\pi,\dots a_{\tau(b+1)-1}^\pi\). Therefore, for these time steps, both policies agree on the actions and generate the same rewards, albeit in a different order. Specifically, this implies that \(\sum_{t=b+1}^{\tau(b+1)}r_t^{\pi'} = \sum_{t=b+1}^{\tau(b+1)}r_t^\pi\). Moreover, both policies generated the same queried reward \(R_{b+1}^q\) and continues the same for any \(t>\tau(b+1)\), which implies that they will generate the same actions and rewards until the end of the interactions. Thus, in this case, we have that \(\sum_{t=b+1}^{T}r_t^{\pi'} = \sum_{t=b+1}^{T}r_t^\pi\).

2. \(\tau(b+1)=\phi\). In this case, no additional reward is queried, and the same sequence of actions \(a_{b+1},\dots,a_T\) is deterministically chosen as a function of \(U,Y_1,\dots,Y_b\), for both \(\pi\) and \(\pi'\). Thus, as the reward is generated from the same distribution for both policies, we have for any \(t>b+1\) \[\begin{align} E\brs*{r_t^{\pi'} \vert U,Y_1,\dots,Y_b} = E\brs*{r_t^\pi \vert U,Y_1,\dots,Y_b} \end{align}\]

Combining both parts, and using the tower property we have \[\begin{align} \mathbb{E}\brs*{\sum_{t=b+1}^T r_t^{\pi'}} &= \mathbb{E}\brs*{\mathbb{E}\brs*{\sum_{t=b+1}^T r_t^{\pi'}\bigg\vert U,Y_1,\dots,Y_b}} \\ & = \mathbb{E}\brs*{\mathbb{E}\brs*{1{\brc*{\tau(b+1)\ne\phi}}\underbrace{\sum_{t=b+1}^T r_t^{\pi'}}_{=\sum_{t=b+1}^T r_t^{\pi}}\bigg\vert U,Y_1,\dots,Y_b} + \sum_{t=b+1}^T 1{\brc*{\tau(b+1)=\phi}}\underbrace{\mathbb{E}\brs*{r_t^{\pi'}\bigg\vert U,Y_1,\dots,Y_b}}_{=\mathbb{E}\brs*{r_t^{\pi}\bigg\vert U,Y_1,\dots,Y_b}}} \\ & = \mathbb{E}\brs*{\mathbb{E}\brs*{1{\brc*{\tau(b+1)\ne\phi}}\sum_{t=b+1}^T r_t^{\pi}\bigg\vert U,Y_1,\dots,Y_b} + \sum_{t=b+1}^T 1{\brc*{\tau(b+1)=\phi}}\mathbb{E}\brs*{r_t^{\pi}\bigg\vert U,Y_1,\dots,Y_b}} \\ & = \mathbb{E}\brs*{\mathbb{E}\brs*{\sum_{t=b+1}^T r_t^{\pi}\bigg\vert U,Y_1,\dots,Y_b}} \\ & = \mathbb{E}\brs*{\sum_{t=b+1}^T r_t^{\pi}}. \end{align}\] Finally, recalling that the polices are identical for \(t\le b\), we get the desired result for \(\pi'=\pi^{b+1}\) and \(\pi=\pi^b\): \[\begin{align} \mathbb{E}\brs*{\mathrm{Reg}(T)\vert\pi'} &= \mathbb{E}\brs*{\sum_{t=1}^b r_t^{\pi'}} + \mathbb{E}\brs*{\sum_{t=b+1}^T r_t^{\pi'}} = \mathbb{E}\brs*{\sum_{t=1}^b r_t^\pi} + \mathbb{E}\brs*{\sum_{t=b+1}^T r_t^{\pi}} = \mathbb{E}\brs*{\mathrm{Reg}(T)\vert\pi}\enspace. \end{align}\] ◻

Proof. Consider a contextual multi-armed bandit instance with two contexts. That is, the environment has two contexts \(u=1,2\); if we observe \(u=1\), then we interact with the first MAB problem, and if \(u=2\), we interact with the second MAB problem. We assume there is no relation between the first and second MAB problems.

Greedy Reduction Algorithm in the Presence of Adversarial Contexts.
Assume the budget sequence increases at each episode w.p. \(\frac{1}{2}\) by a unit. Assume the adversary picks \(u=1\) if the budget increases by one and \(u=2\) if the budget does not increase. Applying the Greedy Reduction, the algorithm will only query information from MAB \(u=1\) and will have no information on the rewards for MAB \(u=2\). Let the bandit problems of both contexts be two-armed problems. Then, there exists an arm \(a^*\) of context \(u=2\) that the algorithm samples, in expectation, at most \(\frac{T}{4}\) times, namely, \[\mathbb{E}\brs*{\sum_{t=1}^T 1{\brc*{u_t = 2, a_t= a^*}}}\le \frac{1}{2}\mathbb{E}\brs*{\sum_{t=1}^T 1{\brc*{u_t = 2}}} = \frac{T}{4},\] where we used the fact that \(\Pr\br*{u_t=2} = \Pr\br*{B(t)=B(t-1)+1}=\frac{1}{2}\). For this arm, we fix the reward to be equal \(R=1\), and for the other arm, we let \(R=0\). For simplicity, we fix the means of all arms in context \(u=1\) to be identical. Then, the regret is lower bounded by \[\begin{align} \mathbb{E}\brs*{\mathrm{Reg}(T)} = \mathbb{E}\brs*{\sum_{t=1}^T 1{\brc*{u_t = 2, a_t\ne a^*}}} = \mathbb{E}\brs*{\sum_{t=1}^T 1{\brc*{u_t = 2}}} - \mathbb{E}\brs*{\sum_{t=1}^T 1{\brc*{u_t = 2, a_t= a^*}}} \ge \frac{T}{2} - \frac{T}{4} = \frac{T}{4} \end{align}\] Notice that by definition, \(\mathbb{E}\brs*{B(t)}=\frac{t}{2}\) for all \(t\in\brs*{T}\).

Greedy Reduction Algorithm in the Presence of Adversarial Budget.
The example is symmetric to the previous one, i.e., we exchange the roles of the context and the budget. Assume that the context are chosen stochastically such that where \(\Pr(u_t=1) = \Pr(u_t=2) =\frac{1}{2}\). If the budget increases by one each time \(u_t=1\) then Greedy Reduction will not acquire any information on the MAB with \(u_t=2\). Repeating the same analysis as the previous case results in \(\mathbb{E}[\mathrm{Reg}(T)]\geq \Omega(T)\) as well as \(\mathbb{E}\brs*{B(t)} = \frac{t}{2}\) for all \(t\in\brs*{T}\). ◻

Proof. Define the filtration \(\brc{F_t}_{t\geq 0}\) where \(F_{t-1}\) contains \(\brc{B(1), a_1,R_{1},\dots,B(t-1),a_{t-1},R_{t-1},B(t)}\), i.e., all past actions, rewards and budgets, combined with the value of total budget at time step \(t\). We also assume w.l.o.g. that \(A\ge2\), otherwise the regret is always zero. The good event is defined as \[\begin{align} &E^r(t) = \brc*{a \in A:\;|\bar{r}_{t-1}(a) -r(a)| \leq \sqrt{ \frac{3\log(At) }{2n^q_{t-1}(a)\vee 1} } \stackrel{\text{def}}{=}b_{t}^r(a)}. \end{align}\] Importantly, notice that when \(E^r(t)\) holds, then \(r(a^*)\le UCB_t(a^*) \le UCB_t(a_t)\), and thus, the UCB of the chosen arm is optimistic. Moreover, the event directly implies that \(r(a_t)\ge LCB_t(a_t)\).

Meeting the budget constraint We prove that the CBM principle of 3 never violates the budget constraint in 5, that is, \(B^q(t)\le B(t)\) for all \(t\in\brs*{T}\). Thus, throughout the proof, we assume that \(q_t=1\) if and only if the CBM query rule decides so (i.e., the case where the algorithm wants to set \(q_t=1\) and does not have enough budget to do so cannot happen).

Regret analysis. We decouple the regret as follows. \[\begin{align} \mathbb{E}[\mathrm{Reg}(T)] &= \sum_{t=1}^T \mathbb{E}\brs*{(r^* - r(a_t))1{\brc*{E^r(t)}}} + \sum_{t=1}^T \mathbb{E}\brs*{(r^* - r(a_t))1{\brc*{\overline{E^r(t)}}}}\\ & \le \sum_{t=1}^T \mathbb{E}\brs*{(r^* - r(a_t))1{\brc*{E^r(t)}}} + \sum_{t=1}^T \mathbb{E}\brs*{1{\brc*{\overline{E^r(t)}}}} \\ & \le \sum_{t=1}^T \mathbb{E}\brs*{(r^* - r(a_t))1{\brc*{E^r(t)}}} + \sum_{t=1}^T \frac{1}{t^2} }\\ &\le \underbrace{\sum_{t=1}^T \mathbb{E}\brs*{1{\brc*{q_t=1}}(r^* - r(a_t))1{\brc*{E^r(t)}}}}_{(i)} + \underbrace{\sum_{t=1}^T \mathbb{E}\brs*{1{\brc*{q_t=0}}(r^* - r(a_t))1{\brc*{E^r(t)}}}}_{(ii)}+2. \end{align}\] Terms \((i)\) and \((ii)\) represent the regret over episodes in which feedback was queried and not queried, respectively. We bound each of the terms separately.

Bound on term \((i)\), episodes in which feedback is queried, under the good event. The following relations hold \[\begin{align} (i) &= \sum_{t=1}^T \mathbb{E}\brs*{1{\brc*{q_t=1}}(r^* - r(a_t))1{\brc*{E^r(t)}}}\\ &\leq \sum_{t=1}^T \mathbb{E}\br*{1{\brc*{q_t=1}}1{\brc*{E^r(t)}}(UCB(a_t) - r(a_t))} \\ &\leq \sum_{t=1}^T \mathbb{E}\br*{1{\brc*{q_t=1}}1{\brc*{E^r(t)}}(UCB(a_t) - LCB(a_t))} \\ & \le \mathbb{E}\brs*{ \sum_{t=1}^T 1{\brc*{q_t=1}} \sqrt{\frac{6\log(At)}{n_{t-1}^q(a_t)\vee 1}}}. \end{align}\] We bound the term in the expectation as follows (for every history sequence). \[\begin{align} \sum_{t=1}^T 1{\brc*{q_t=1}} \sqrt{\frac{6\log(At)}{n_{t-1}^q(a_t)\vee 1}} &\leq \sqrt{6\log(AT)}\sum_{t=1}^{T} \frac{1{\brc*{q_t=1}}}{\sqrt{n_{k-1}^q(a_t)\vee 1}}\\ & \overset{(*)}{=}\sqrt{6\log(AT)}\sum_{a=1}^{A} \sum_{i=0}^{n^q_T(a)} \frac{1}{\sqrt{i \vee 1}}\\ &\leq \sqrt{6\log(AT)}\sum_{a} \br*{2\sqrt{n^q_T(a)} + 1} ^T\frac{1}{\sqrt{i}}\le 2\sqrt{T}}\\ &\leq \sqrt{24\log(AT)} \sqrt{An^q_T} + A\sqrt{6\log(AT)} n^q_T(a) = n^q_T}, \end{align}\] where \((*)\) holds since every time an action \(a\) was queried, its counter advanced by 1. In the second relation, the summation is performed over time steps a reward is queried. Lastly, using \(n^q_T \leq T\), i.e., the number of times the algorithm queried feedback is smaller than the total number of round, we get, \[\begin{align} (i) \leq \sqrt{24AT\log(AT)} + A\sqrt{6\log(AT)}. \end{align}\] Bound on term \((ii)\), episodes in which feedback is not queried. To bound this term, we use the query rule, that is, \[\begin{align} (ii) &= \sum_{t=1}^T \mathbb{E}[1{\brc*{q_t=0}}1{\brc*{E^r(t)}}(r^* - r(a_t))] \\ &\leq \sum_{t=1}^T \mathbb{E}[1{\brc*{q_t=0}}1{\brc*{E^r(t)}}(UCB(a_t) - LCB(a_t))] \\ &\leq \sum_{t=1}^T \mathbb{E}\brs*{4\sqrt{\frac{6\log(At)\sum_{a=1}^{A}c(a)}{B(t)}}} \\ &\leq 4\sqrt{6\log(AT)\sum_{a=1}^{A}c(a)}\sum_{t=1}^T \mathbb{E}\brs*{\sqrt{\frac{1}{B(t)}}}. \end{align}\] Combining the bounds. Combining the two bounds we conclude the proof, \[\begin{align} \mathbb{E}[\mathrm{Reg}(T)] \leq \sqrt{24AT\log(AT)} + A\sqrt{6\log(AT)} + 4\sqrt{6\log(AT)\sum_{a=1}^{A}c(a)}\sum_{t=1}^T \mathbb{E}\brs*{\sqrt{\frac{1}{B(t)}}} + 2. \end{align}\] ◻

Proof. Fix \(t\ge1\). The following relations hold by applying Hoeffding’s inequality and the union bound. Denote by \(\hat{r}_n(a)\), the empirical mean of \(n\) i.i.d random variables over \([0,1]\) with an expectation \(r(a)\). Then, we have \[\begin{align} \Pr&\br*{\abs*{\bar{r}_{t-1}(a_t) -r(a_t)} \geq \sqrt{ \frac{3\log (At)}{2n^q_{t-1}(a_t)\vee 1}}}\\ &=\sum_{a=1}^{A}\Pr\br*{\abs*{\bar{r}_{t-1}(a) -r(a)} \geq \sqrt{ \frac{3\log (At)}{2n^q_{t-1}(a)\vee 1}}, a_t=a}\\ &\le \sum_{a=1}^{A}\Pr\br*{\abs*{\bar{r}_{t-1}(a) -r(a)} \geq \sqrt{ \frac{3\log (At)}{2n^q_{t-1}(a)\vee 1}}}\\ &= \sum_{a=1}^{A}\Pr\br*{\cup_{n=0}^t\brc*{\abs*{\bar{r}_{t-1}(a) -r(a)} \geq \sqrt{ \frac{3\log (At)}{2n\vee 1}}, n_{t-1}^q(a)=n}}\\ &= \sum_{a=1}^{A}\Pr\br*{\cup_{n=1}^t\brc*{\abs*{\hat{r}_n(a) -r(a)} \geq \sqrt{ \frac{3\log (At)}{2n}}, n_{t-1}^q(a)=n}} \\ &\le \sum_{a=1}^{A}\sum_{n=1}^t\Pr\br*{\abs*{\hat{r}_{n}(a) -r(a)} \geq \sqrt{ \frac{3\log (At)}{2n}}}\\ &\leq \sum_{a=1}^{A}\sum_{n=1}^t\frac{1}{At^3}\\ & = \frac{1}{t^2}. \end{align}\] ◻

Proof. Assume w.l.o.g. that \(c(a)>0\) for at least one action, as otherwise, the budget constraint can never be violated. Similarly, assume that \(B(1)>0\); otherwise, until a budget becomes available, no reward will be queried, and the same analysis would hold, starting from the first time querying became available. The following relations hold for any history. \[\begin{align} B^q(t) &= \sum_{k=1}^{t} c(a_k)1{\brc*{q_k=1}}\\ &= \sum_{a=1}^{A}\sum_{k=1}^{t} c(a)1{\brc*{a_k=a,q_k=1}}\\ &\leq \sum_{a=1}^{A}c(a)\sum_{k=1}^t 1{\brc*{a_k=a,q_k=1}} \frac{CI_t(a_t)}{ 4\sqrt{6\log(Ak)(\sum_{a'=1}^{A} c(a'))/{B(k)}}} \\ &=\sum_{a=1}^{A}c(a)\sum_{k=1}^t1{\brc*{a_k=a,q_k=1}} \frac{\sqrt{6 \log(Ak)/{(n_{k-1}^q(a)}\vee 1)}}{4\sqrt{6 \log(Ak)(\sum_{a'=1}^{A} c(a'))/{B(k)}}}\\ &=\frac{1}{4\sqrt{\sum_{a'=1}^{A} c(a')}}\sum_{a=1}^{A}c(a)\sum_{k=1}^t1{\brc*{a_k=a,q_k=1}} \sqrt{\frac{1}{{(n_{k-1}^q(a)}\vee 1)}}\sqrt{B(k)}\\ &\leq \frac{1}{4\sqrt{\sum_{a'=1}^{A} c(a')}}\sqrt{B(t)}\sum_{a=1}^{A} c(a)\sum_{i=0}^{n^q_t(a)} \sqrt{\frac{1}{i\vee 1}} \\ & \le \frac{1}{2\sqrt{\sum_{a'=1}^{A} c(a')}}\sqrt{B(t)}\sum_{a=1}^{A} c(a)\sum_{i=1}^{n^q_t(a)} \sqrt{\frac{1}{i}} \\ &\leq \frac{1}{\sqrt{\sum_{a'=1}^{A} c(a')}}\sqrt{B(t)}\sum_{a=1}^{A}c(a)\sqrt{n^q_{t}(a)}^T\frac{1}{\sqrt{i}}\le 2\sqrt{T}}\\ &\leq \frac{1}{\sqrt{\sum_{a'=1}^{A} c(a')}}\sqrt{B(t)}\sqrt{\sum_{a'=1}^{A} c(a')} \sqrt{\sum_{a=1}^{A} c(a)n^q_{t}(a)} \\ &= \sqrt{B(t)}\sqrt{B^q(t)}. \end{align}\] Rearranging we get that \(B^q(t)\leq B(t)\) for any \(t\geq 0\). ◻

Proof. With probability greater than \(1-\delta\) it holds that \(\theta^* \in C_t = \brc*{\theta\in \mathbb{R}^d: \norm{\hat{\theta}_t-\theta}_{V_t}\leq l_t }\), uniformly for all \(t\ge0\) (see Theorem 6 which generalizes [9] . We define this event as the good event and denote it by \(\mathbb{G}\). Also, we denote the parameter vector that maximizes the UCB by \(\tilde{\theta}_t\), i.e., \((x_t,\tilde{\theta}_t)\in\arg\max_{x\times\theta\in \mathcal{X}_t\times C_{t-1}} \inner{x,\theta}\). Then, under the good event we have that \(\max_{x\in\mathcal{X}_t}\inner{x,\theta^*}\le \inner{x_t,\tilde{\theta}_t}\) (‘optimism’).

As in the MAB setting ([theorem:32CBM32Bandits]), we prove that when CBM-OFUM asks for a query, it always has sufficient budget (6). Therefore, throughout the proof, we assume that the algorithm observes reward iff it sets \(q_t=1\) and that \(B^q(t)\le \min\brc*{T,B(t)}\) for all \(t\).

We now derive the performance bound by bounding the regret of the algorithm. The following relations hold for any \(T\geq 1\): \[\begin{align} \mathrm{Reg}(T) = \underbrace{\sum_{t=1}^T 1{\brc*{q_t = 1}} \br*{\max_{x\in\mathcal{X}_t}\inner{x,\theta^*} - \inner{x_t,\theta^*}}}_{(i)} + \underbrace{\sum_{t=1}^T 1{\brc*{q_t = 0}} \br*{\max_{x\in\mathcal{X}_t}\inner{x,\theta^*} - \inner{x_t,\theta^*}}}_{(ii)}. \end{align}\] Terms \((i)\) and \((ii)\) represent the regret over episodes in which feedback was queried and not queried, respectively. We bound each of the terms.

Bound on term \((i)\), episodes in which feedback is queried. The following relations hold. \[\begin{align} (i)=&\sum_{t=1}^T 1{\brc*{q_t = 1}} \br*{\max_{x\in\mathcal{X}_t}\inner{x,\theta^*} - \inner{x_t,\theta^*}} \\ &=\sum_{t=1}^T 1{\brc*{q_t = 1}} \min\brc*{\br*{\max_{x\in\mathcal{X}_t}\inner{x,\theta^*} - \inner{x_t,\theta^*}},2}\\ &\leq \sum_{t=1}^T 1{\brc*{q_t = 1}} \min\brc*{\br*{\inner{x_t,\tilde{\theta}_t} - \inner{x_t,\theta^*}},2}\\ &= \sum_{t=1}^T 1{\brc*{q_t = 1}} \min\brc*{\br*{\inner{x_t,\tilde{\theta}_t-\hat{\theta}_t} + \inner{x_t,\hat{\theta}_t - \theta^*}},2} \\ &=\sum_{t=1}^T 1{\brc*{q_t = 1}} \min\brc*{\norm{x_t}_{V_{t-1}^{-1}}\br*{\norm{\tilde{\theta}_t-\hat{\theta}_t}_{V_{t-1}}+\norm{\hat{\theta}_t-\theta^*}_{V_{t-1}}},2}\\ &\leq 2l_T\sum_{t=1}^T 1{\brc*{q_t = 1}} \min\brc*{\norm{x_t}_{V_{t-1}^{-1}},1}\& l_t\ge1 is increasing in t} \end{align}\] Next, denote the \(k^{th}\) time that CBM-OFUL queried a reward by \(\tau_k\). Then, we can write \(V_t = \lambda I_d+\sum_{k=1}^{B^q(t)}x_{\tau_k}x_{\tau_k}^T\). Rewriting the bound on \((i)\) and then using the the elliptical potential lemma (23) and get \[\begin{align} (i)&\leq 2l_T\sum_{k=1}^{B^q(T)} \min\brc*{\norm{x_{\tau_k}}_{V_{\tau_k-1}^{-1}},1} \\ & \le 2l_T\sqrt{B^q(t)}\sqrt{\sum_{k=1}^{B^q(T)} \min\brc*{\norm{x_{\tau_k}}_{V_{\tau_k-1}^{-1}}^2,1}} ^n x_i}^2 \le n\sum_{i=1}^n x_i^2}\\ &\le 2l_T\sqrt{B^q(T)}\sqrt{2 d\log\br*{1 + \frac{B^q(T)L^2}{d\lambda}}} }\\ & \quad\,\,\le 2l_T\sqrt{T}\sqrt{ 2d\log\br*{1 + \frac{T L^2}{d\lambda}}}\enspace. \end{align}\]

Bound on term \((ii)\), episodes in which feedback is not queried. The following relations hold. \[\begin{align} (ii)=&\sum_{t=1}^T 1{\brc*{q_t = 0}} \br*{\max_{x\in\mathcal{X}_t}\inner{x,\theta^*} - \inner{x_t,\theta^*}} \\ &\leq \sum_{t=1}^T 1{\brc*{q_t = 0}}\min \brc*{\inner{x_t,\tilde{\theta}_t} - \inner{x_t,\theta^*},2} \\ &\leq \sum_{t=1}^T 1{\brc*{q_t = 0}} \underbrace{\min\brc*{ \max_{\theta\in C_t}\inner{x_t,\theta} - \min_{\theta\in C_t}\inner{x_t,\theta},2}}_{\le CI_t(x_t)}\\ &\leq \sum_{t=1}^T 1{\brc*{q_t = 0}} \frac{2l_{t-1}v_{B(t)}}{\sqrt{B(t)}} \\ &\leq 2l_Tv_T\sum_{t=1}^T \frac{1}{\sqrt{B(t)}} . \end{align}\]

The forth relation holds since the algorithm does not query for feedback only when \(CI_t(x_t)\leq 2l_{t-1} v_{B(t)}/\sqrt{B(t)}\) (a case where \(q_t=0\) since the algorithm ran out of budget cannot happen).

Combining the bounds. Combining the bounds over \((i)\) and \((ii)\) we get that conditioned on the good event (which holds with probability greater than \(1-\delta\)), the regret is bounded by \[\begin{align} \mathrm{Reg}(T) &\leq 2l_Tv_T\sum_{t=1}^T \frac{1}{\sqrt{B(t)}} + 2l_T\sqrt{T} \underbrace{\sqrt{2d\log\br*{1 + \frac{TL^2}{d\lambda}}}}_{\stackrel{\text{def}}{=}v_T} \\ & = 2l_Tv_T\br*{\sum_{t=1}^T \frac{1}{\sqrt{B(t)}} + \sqrt{T}}, \end{align}\] for all \(T\geq 1\). ◻

Proof. Before supplying the proof, notice that the function \(f(x) = x/\log(1+x\alpha)\) is a strictly increasing function in \(\alpha>0,x\ge 0\) (since \(f'(x)>0\) for \(x>0\)). This implies that the ratio \[\frac{B(T)}{v_{B(T)}^2} = \frac{B(T)}{4d\log(1+ B(T)L^2/\lambda)}=\frac{f(B(T))}{4d}\] is a non-decreasing function in \(T\) since \(B(T)\) is non-decreasing in \(T\). Also, recall that \(CI_t(x_t) =2 l_t \min\brc*{\norm{x_t}_{V_t^{-1}},1}\). Using these facts we get the following relations for any \(T\geq 1\). \[\begin{align} &B^q(T) = \sum_{t=1}^T 1{\brc*{q_t=1}} \\ &\leq \sum_{t=1}^T 1{\brc*{q_t=1}} \frac{CI_t(x_t)}{2l_{t-1} v_{B(t)}\sqrt{1/B(t)}} \\ &=\sum_{t=1}^T 1{\brc*{q_t=1}} \frac{2 l_{t-1} \min\brc*{\norm{x_t}_{V_{t-1}^{-1}},1}}{2l_{t-1} v_{B(t)}\sqrt{1/B(t)}} \\ & \leq \sqrt{B(T)/v_{B(T)}} \sum_{t=1}^T 1{\brc*{q_t=1}}\min\brc*{\norm{x_t}_{V_{t-1}^{-1}},1}^2 is non-decreasing in T}\\ &\leq \sqrt{B(T)/v_{B(T)}}\sqrt{\sum_{t=1}^{T} 1{\brc*{q_t=1}}}\sqrt{\sum_{t=1}^{T} 1{\brc*{q_t=1}}\min\brc*{\norm{x_t}_{V_{t-1}^{-1}}^2,1}} \\ &\leq \sqrt{B(T)/v_{B(T)}}\sqrt{B^q(T)}\sqrt{2d\log\br*{1+\frac{B^q(T)L^2}{d}}} }\\ &= \sqrt{\frac{B(T)}{\log\br*{1+\frac{B(T)L^2}{d\lambda}}}}\sqrt{B^q(T)\log\br*{1+\frac{B^q(T)L^2}{d}}}. \end{align}\] Rearranging we get \[\begin{align} \frac{B^q(T)}{\log\br*{1+B^q(T)L^2/\lambda}} \leq \frac{B(T)}{\log\br*{1+B(T)L^2/\lambda}}. \label{eq:32budget32linear32bandit32pre32final} \end{align}\tag{11}\] Since \(f(x) = x/\log(1+x\alpha)\) is strictly increasing function for any \(\alpha>0,x\geq 0\), 11 implies that \(B^q(T)\leq B(T)\). ◻

Proof. We prove that each part of the good event holds with a probability of at least \(1-\delta/6\).

The event \(\cap_{t\ge1} E^r(t)\) holds with high probability. Fix an episode \(t\geq 1\) and \(s,a,h\in \mathcal{S}\times \mathcal{A}\times [H]\). There are at most \(t\) reward samples from \((s,a)\) at time step \(h\) at episode \(t\). Taking a union bound over these possible values and scaling \(\delta\rightarrow \delta/t\) we get that \[\begin{align} \Pr\br*{|\bar{r}_{t-1,h}(s,a) -r_h(s,a)| \leq \sqrt{ \frac{2 \widehat{\mathrm{Var}}_{R,t-1,h}(s,a)\log\frac{2t}{\delta} }{n^q_{t-1,h}(s,a)\vee 1}} + \frac{14\log \frac{2t}{\delta}}{3 n^q_{t-1,h}(s,a)\vee 1} } \geq 1-\delta, \end{align}\] by [22]. Note that we used the relation \(1/(n-1)\leq 2/n\) for \(n\geq 2\) and that the bound trivially holds for \(n<2\) since the reward is in \([0,1]\). Furthermore, taking a union bound on all \(s,a,h\in \mathcal{S}\times \mathcal{A} \times [H]\) and setting \(\delta \rightarrow \delta/6SAHt(t+1)\) results in \(\Pr\br*{\cap_{t\ge1} E^r(t)} \leq 1-\delta/6\) by using \(\sum_{t=1}^\infty \frac{\delta}{t(t+1)}=\delta\).

The event \(\cap_{t\ge1} E^p(t)\) holds with high probability. Fix an episode \(t\geq 1\) and \(s,a,s',h\in \mathcal{S}\times \mathcal{A} \times \mathcal{S} \times [H]\). At the \(t^{th}\) episode the tuple can be sampled for at most \(t\) times. Taking a union bound on all these possible values and applying Bennet’s inequality [22], we get \[\begin{align} \Pr\br*{|P_h\br*{s'|s,a} - \bar{P}_{t,h}\br*{s'|s,a}| \le \sqrt{\frac{2P(s'|s,a))\log\frac{2t}{\delta}}{n_{t-1}(s,a)\vee 1}} + \frac{4\log\frac{2t}{\delta}}{3n_{t-1}^p(s,a)\vee 1}} \geq 1-\delta, \end{align}\] since the variance of a Bernoulli random variable is \(P(s'|s,a)(1-P(s'|s,a)\leq P(s'|s,a)\). Taking a union bound over all \(s,a,s',h\in \mathcal{S}\times \mathcal{A} \times \mathcal{S} \times [H]\) and scaling \(\delta \rightarrow \delta/6S^2AHt(t+1)\) and repeating the same reasoning as before concludes the high probability bound for \(\cap_{t\ge1} E^p(t)\).

The event \(\cap_{t\ge1} E^{pv}(t)\) holds with high probability. Repeating the same arguments as for the event \(\cap E^r(t)\) while noticing that \(\bar{P}_{t,h}(\cdot \mid s,a)^TV_{h+1}^*\in\brs*{0,H}\) (and, thus, also the empirical variance, for all \(n\ge2\)) concludes the proof.

Combining the results. Taking a union bound concludes the proof. ◻

Proof. We prove this result via induction.

Base case, \(h=H\) and for all \(s\in \mathcal{S}\). Let \(a^*(s)\in \arg\max_{a\in \mathcal{A}} r_{H}(s,a)\). For any \(s\in \mathcal{S}\) it holds that \[\begin{align} &V^*_{H}(s) -\bar{V}_{t,H}(s) = r_{H}(s,a^*(s)) - \min\brc*{\max_a \brc*{\bar{r}_{t,H}(s,a) + b_{t,H}^r(s,a)},1}. \label{eq:32optimism32base32case32ucbvi32rel321} \end{align}\tag{14}\] Assume that \(\max_a \bar{r}_{t,H}(s,a) + b_{t,H}^r(s,a) < 1\) then, \[\begin{align} &\eqref{eq:32optimism32base32case32ucbvi32rel321} \leq r_{H}(s,a^*(s)) - \bar{r}_{t,H}(s,a^*(s)) - b_{t,H}^r(s,a^*(s))\\ &\leq b_{t,H}^r(s,a^*(s)) - b_{t,H}^r(s,a^*(s))\leq 0 . \end{align}\] If \(\max_a \brc*{\bar{r}_{t,H}(s,a) + b_{t,H}^r(s,a)}\geq 1\) then trivially \(\eqref{eq:32optimism32base32case32ucbvi32rel321}\leq 0\) since \(r_{H}(s,a)\in [0,1]\) for all \(a\in \mathcal{A}\). Overall, we conclude that \(V^*_{H}(s) \leq \bar{V}_{t,H}(s)\) for all \(s\in \mathcal{S}\) for \(h=H\).

Induction step, for \(h\in [H]\) \(s\in \mathcal{S}\) assuming it holds for all \(h'\geq h+1\). Let \(a^*(s)\in \arg\max_{a\in \mathcal{A}} Q^{*}_h(s,a)\) The following relations hold. \[\begin{align} &V^*_h(s)- \bar{V}_{t,h}(s) = Q^{*}_h(s,a^*(s))- \min\brc*{\max_a\bar{Q}_{t,h}(s,a),H-h} \label{eq:32optimism32base32case32ucbvi32rel322} \end{align}\tag{15}\] Assume that \(\max_a\bar{Q}^{\pi}_{t,h}(s,a)< H-h\), then, \[\begin{align} \eqref{eq:32optimism32base32case32ucbvi32rel322} &\leq Q^{*}_h(s,a^*(s)) - \bar{Q}_{t,h}(s,a^*(s))\\ & = r_h(s,a^*(s)) + P_h(\cdot| s,a^*(s))^TV^*_{h+1} \\ &\quad- \br*{\bar{r}_{t-1,h}(s,a^*(s)) + b_{t,h}^r(s,a^*(s)) + b_{t,h}^p(s,a^*(s)) + \bar{P}_h(\cdot| s,a^*(s))^T\bar{V}_{t,h+1}}\\ &= r_h(s,a^*(s)) - \bar{r}_{t-1,h}(s,a^*(s)) - b_{t,h}^r(s,a^*(s)) + (P_h-\bar{P}_{t-1,h})(\cdot| s,a^*(s))^TV^*_{h+1} - b_{t,h}^p(s,a^*(s)) \\ &\quad+ \mathbb{E}_{\bar{P}_{t-1,h}(\cdot|s,a^*(s))}[ \underbrace{V^{*}_{h+1}(s') - \bar{V}_{t,h+1}(s')}_{\leq 0\;\mathrm{Induction\;hypothesis}}]\\ &\leq b_{t,h}^r(s,a^*(s)) - b_{t,h}^r(s,a^*(s)) - b_{t,h}^p(s,a^*(s)) + b_{t,h}^p(s,a^*(s)) (t)\cup\cap_t E^{r}(t) holds}\\ &=0. \end{align}\] If \(\max_a\bar{Q}^{\pi}_{t,h}(s,a)\geq H-h\) then trivially \(\eqref{eq:32optimism32base32case32ucbvi32rel322}\leq 0\) since \(Q^*_h(s,a)\leq H-h\) since it is an expectation over \(H-h\) terms, each bounded by \([0,1]\). Thus, \(V^*_{h}(s) \leq \bar{V}_{t,h}(s)\) for all \(s\in \mathcal{S}\) for \(h'\geq h\) which proves the induction step and concludes the proof. ◻

Proof. Fix \(h\in [H],T\). We start by defining the random variable \(W_t=1{\brc*{\bar{V}_{t,h+1}(s) - V^{\pi_t}_{h}(s)\ge 0, \forall h\in\brs*{H}.s\in\mathcal{S}}}\) and the random process \(Y_t = Y_{t ,h}= \bar{V}_{t,h+1}(s_{t,h+1}) - V^{\pi_t}_{h+1}(s_{t,h+1})\) w.r.t. the filtration \(\brc*{F_{t+1,h-1}}_{t\geq 1}\) (observe that \(Y_{t ,h}\) is \(F_{t+1,h-1}\) measurable). Also notice that \(W_t\) is \(F_{t,h-1}\) measurable, as both \(\pi_t\) and \(\bar{V}_{t,h}\) are \(F_{t-1}\)-measurable. Finally, define \(\tilde{Y}_t = W_tY_t\). Importantly, \(\tilde{Y}_t\in\brs*{0,H}\) almost surely, by definition of \(W_t\) and since \(\bar{V}_{t,h+1}(s),V^{\pi_t}_{h}(s)\in [0,H]\) by the update rule. Thus, using 20 with \(C=H\ge1\), we get \[\begin{align} \sum_{t=1}^T \mathbb{E}[\tilde{Y}_{t ,h}|F_{t,h-1}]\leq \br*{1+\frac{1}{2H}} \sum_{t=1}^T \tilde{Y}_{t ,h} + 18H^2 \log\frac{1}{\delta}, \end{align}\] with probability greater than \(1-\delta\), and since \(W_t\) is \(F_{t,h-1}\)-measurable, we can write \[\begin{align} \sum_{t=1}^T W_t\mathbb{E}[Y_{t ,h}|F_{t,h-1}]\leq \br*{1+\frac{1}{2H}} \sum_{t=1}^TW_tY_{t ,h} + 18H^2 \log\frac{1}{\delta}. \label{eq:32good32event32relation321} \end{align}\tag{16}\] Importantly, notice that under \(\mathbb{G}_1\), it holds that \(W_t\equiv1\) (by 8). Therefore, applying the union bound and setting \(\delta= \delta/2HT(T+1)\) we get \[\begin{align} &\Pr(\overline{E^{O}}\cap \mathbb{G}_1)\\ &\leq \sum_{h=1}^H\sum_{T=1}^\infty \Pr\br*{\brc*{\sum_{t=1}^T \mathbb{E}[Y_{t ,h} |F_{t,h-1}]\geq \br*{1+\frac{1}{2H}} \sum_{t=1}^T Y_{t ,h} + 18H^2 \log\frac{2HT(T+1)}{\delta}}\cap\mathbb{G}_1} \\ & = \sum_{h=1}^H\sum_{T=1}^\infty \Pr\br*{\brc*{\sum_{t=1}^T W_t\mathbb{E}[Y_{t ,h} |F_{t,h-1}]\geq \br*{1+\frac{1}{2H}} \sum_{t=1}^T W_tY_{t ,h} + 18H^2 \log\frac{2HT(T+1)}{\delta}}\cap\mathbb{G}_1}_1}\\ & \le \sum_{h=1}^H\sum_{T=1}^\infty \Pr\br*{\sum_{t=1}^T W_t\mathbb{E}[Y_{t ,h} |F_{t,h-1}]\geq \br*{1+\frac{1}{2H}} \sum_{t=1}^T W_tY_{t ,h} + 18H^2 \log\frac{2HT(T+1)}{\delta}}\\ &\leq \sum_{h=1}^H\sum_{T=1}^\infty \frac{\delta}{2HT(T+1)}=\delta/2, }. \end{align}\] Finally, we have \[\begin{align} \Pr(\overline{\mathbb{G}}) \le \Pr(\overline{\mathbb{G}_2}\cap\mathbb{G}_1) + \Pr(\overline{\mathbb{G}_1}) \le \frac{\delta}{2} + \frac{\delta}{2} = \delta \end{align}\] ◻

Proof. It holds that \[\begin{align} B^q(T)&= \sum_{t=1}^T \sum_{h=1}^H 1{\brc*{q_{t,h}=1}} \nonumber \\ &\leq \sum_{t=1}^T \sum_{h=1}^H 1{\brc*{q_{t,h}=1}}\frac{CI_{t,h}^R(s_{t,h},a_{t,h})}{ L_{t,\delta} \br*{6\sqrt{\frac{|\mathcal{L}_R|}{B(t)}} + 4SAH\frac{\log(1+B(t))+1}{B(t)}}} \nonumber\\ &\leq \sum_{t=1}^T \sum_{h=1}^H 1{\brc*{q_{t,h}=1}}\frac{\sqrt{ \frac{2 \widehat{\mathrm{Var}}_{R,t-1,h}(s_{t,h},a_{t,h}) }{n^q_{t-1,h}(s_{t,h},a_{t,h})\vee 1}} + \frac{2 }{n^q_{t-1,h}(s_{t,h},a_{t,h})\vee 1}}{6\sqrt{\frac{|\mathcal{L}_R| }{B(t)}} + 4SAH\frac{\log(1+B(t)) + 1}{B(t)}} }}{L_{t,\delta}},\frac{L_{t,\delta}}{L_{t,\delta}} \leq 1} \nonumber\\ &\leq \br*{6\sqrt{\frac{|\mathcal{L}_R| }{B(T)}} + 4SAH\frac{ \log(1+B(T)) + 1}{B(T)}}^{-1} \cdot \nonumber\\ &\sum_{t=1}^T \sum_{h=1}^H 1{\brc*{q_{t,h}=1}}\br*{\sqrt{ \frac{2 \widehat{\mathrm{Var}}_{R,t-1,h}(s_{t,h},a_{t,h}) }{n^q_{t-1,h}(s_{t,h},a_{t,h})\vee 1}} + \frac{2 }{n^q_{t-1,h}(s_{t,h},a_{t,h})\vee 1}}, \label{eq:32RL32budget32constraint32relation321} \end{align}\tag{17}\] where the last relation holds since the budget is non-decreasing in \(T\) and both \(\frac{1}{\sqrt{x}},\frac{\log(1+x)+1}{x}\) are monotonically decreasing functions for \(x>0\). We now upper bound the sum in the last relation. Recall that up to time \(t\), a state action pair \((s,a)\) at time step \(h\) was queried \(n^q_{T,h}(s,a)\) times. Also, notice that \(\widehat{\mathrm{Var}}_{R,t-1}(s,a)=0\) if \((s,a,h)\notin \mathcal{L}_R\) and \(\widehat{\mathrm{Var}}_{R,t-1}(s,a)\leq 1\) if \((s,a,h)\in \mathcal{L}_R\). Then, we can write \[\begin{align} \sum_{t=1}^T\sum_{h=1}^H 1{\brc*{q_{t,h}=1}}&\br*{\sqrt{ \frac{2 \widehat{\mathrm{Var}}_{R,t-1,h}(s_{t,h},a_{t,h}) }{n^q_{t-1,h}(s_{t,h},a_{t,h})\vee 1}} + \frac{2 }{n^q_{t-1,h}(s_{t,h},a_{t,h})\vee 1}} \nonumber \\ &\leq \sum_{s,a,h\in \mathcal{L}_R} \sum_{i=0}^{n^q_{T,h}(s,a)}\sqrt{ \frac{2}{i\vee 1}} + \sum_{s,a,h} \sum_{i=0}^{n^q_{T,h}(s,a)}\frac{2 }{i\vee 1} }_{R,t-1}(s,a)}\\ &\leq 6\sum_{s,a,h\in \mathcal{L}_R} \sqrt{n^q_{T,h}(s,a))} +2\sum_{s,a,h}\br*{2+\log(n^q_{T,h}(s,a)) \vee 1)}\nonumber\\ &\overset{(a)}{\leq} 6\sqrt{|\mathcal{L}_R|B^q(T)} + 4SAH\log(1+B^q(T)) + 4SAH, \label{eq:32RL32budget32constraint32relation322} \end{align}\tag{18}\] where \((a)\) follows by Jensen’s inequality and \(\sum_{s,a,h\in \mathcal{L}_R} n^q_{T,h}(s,a)) \leq \sum_{s,a,h} n^q_{T,h}(s,a))=B^q(T)\). Plugging this back into 17 we get \[\begin{align} &B^q(T)\leq \eqref{eq:32RL32budget32constraint32relation321}\leq \br*{6\sqrt{\frac{|\mathcal{L}_R| }{B(T)}} + 4SAH\frac{\log(1+B(T)) + 1}{B(T)}}^{-1} \br*{6\sqrt{|\mathcal{L}_R|B^q(T)} + 4 SAH\log(1+B^q(T))+4SAH} \nonumber\\ \iff & 6\sqrt{\frac{|\mathcal{L}_R| }{B(T)}} + 4SAH\frac{\log(1+B(T))+1}{B(T)}\leq 6\sqrt{\frac{|\mathcal{L}_R|}{B^q(T)}} + 4SAH\frac{\log (1+B^q(T))+1 }{B^q(T)}. \label{eq:32RL32budget32constraint32almost32final} \end{align}\tag{19}\]

Remember that if \(f(x)\) is strictly monotonically decreasing function then \(f(x_1)\leq f(x_2) \iff x_1\geq x_2\). Furthermore, see that \(f_{\alpha,\beta}(x) = \frac{\alpha}{\sqrt{x}} + \beta\frac{\log(1+x)+1}{x}\) is a strictly monotonically decreasing function for \(x>0, \alpha\geq 0,\beta>0\) (since both \(\frac{1}{\sqrt{x}}\) and \(\frac{\log(1+x)+1}{x}\) are strictly decreasing). We can then write 19 , equivalently as \[\begin{align} f_{\alpha,\beta}(B(T)) \leq f_{\alpha,\beta}(B^q(T)), \end{align}\] for \(\alpha = 6|\mathcal{L}_R|,\beta = 4SAH\), and since \(f_{\alpha,\beta}\) is strictly monotonically decreasing it implies that \(B^q(T)\leq B(T)\). ◻

Proof. Let \(\Delta P_{t-1,h}(\cdot |s,a) = (\bar{P}_{t-1,h}-P_h)(\cdot |s,a)\). We bound each of the terms in the sum as follows. \[\begin{align} \bar{V}_{t,h}(s_{t,h})& - V_{h}^{\pi_t}(s_{t,h}) \nonumber \\ &= \bar{r}_{t-1,h}(s_1,a_{t,h}) + b^r_{t,h}(s_{t,h},a_{t,h}) - r_h(s_{t,h},a_{t,h}) + b^p_{t,h}(s_{t,h},a_{t,h}) \nonumber\\ &\quad+ \mathbb{E}_{\bar{P}_{t-1,h}(\cdot| s_{t,h},a_{t,h})}[ \bar{V}_{t,h+1}(s_{h+1})] - \mathbb{E}_{P_{h}(\cdot| s_{t,h},a_{t,h})}[ V_{h+1}^{\pi_t}(s_{h+1})] \nonumber \\ &\leq 2b^r_{t,h}(s_{t,h},a_{t,h}) + b^p_{t,h}(s_{t,h},a_{t,h}) \nonumber\\ &\quad+ \mathbb{E}_{\bar{P}_{t-1,h}(\cdot| s_{t,h},a_{t,h})}[ \bar{V}_{t,h+1}(s_{h+1})] - \mathbb{E}_{P_{h}(\cdot| s_{t,h},a_{t,h})}[ V_{h+1}^{\pi_t}(s_{h+1})]_1 holds}\nonumber\\ & = 2b^r_{t,h}(s_{t,h},a_{t,h}) + b^p_{t,h}(s_{t,h},a_{t,h}) + \mathbb{E}_{P_{h}(\cdot| s_{t,h},a_{t,h})}[ \bar{V}_{t,h+1}(s_{h+1}) - V_{h+1}^{\pi_t}(s_{h+1}) ] \nonumber\\ &\quad+\Delta P_{t-1,h} (\cdot| s_{t,h},a_{t,h})^T \bar{V}_{t-1,h+1} \nonumber\\ & = 2b^r_{t,h}(s_{t,h},a_{t,h}) + b^p_{t,h}(s_{t,h},a_{t,h}) + \mathbb{E}_{P_{h}(\cdot| s_{t,h},a_{t,h})}[ \bar{V}_{t,h+1}(s_{h+1}) - V_{h+1}^{\pi_t}(s_{h+1}) ] \nonumber\\ &\quad+ \Delta P_{t-1,h} (\cdot| s_{t,h},a_{t,h})^T(\bar{V}_{t,h+1} - V^*_{h+1}) +\underbrace{\Delta P_{t-1,h} (\cdot| s_{t,h},a_{t,h})^TV^*_{h+1}}_{\leq b_{t,h}^{p}(s_{t,h},a_{t,h})} \nonumber \\ &\leq 2b^r_{t,h}(s_{t,h},a_{t,h}) + 2b^p_{t,h}(s_{t,h},a_{t,h}) + \mathbb{E}_{P_{h}(\cdot| s_{t,h},a_{t,h})}[ \bar{V}_{t,h+1}(s_{h+1}) - V_{h+1}^{\pi_t}(s_{h+1}) ]\nonumber \\ & \quad + \Delta P_{t-1,h} (\cdot| s_{t,h},a_{t,h})^T(\bar{V}_{t,h+1} - V^*_{h+1})_1 holds}\nonumber\\ &\overset{(a)}{\le}2b^r_{t,h}(s_{t,h},a_{t,h}) + 3H\sqrt{\frac{ L_{t,\delta}}{n_{t-1,h}( s_{t,h},a_{t,h})\vee 1}} + \frac{ 13H^2SL_{t,\delta}}{n_{t-1,h}( s_{t,h},a_{t,h})\vee 1} \nonumber\\ &\quad + \br*{1+\frac{1}{2H}}\mathbb{E}_{P_{h}(\cdot| s_{t,h},a_{t,h})}[ \bar{V}_{t,h+1}(s_{h+1}) - V_{h+1}^{\pi_t}(s_{h+1})], \end{align}\] where \((a)\) by substituting \(b^p_{t,h}(s,a)\) while bounding its last term by \(\frac{5H^2SL_{t,\delta}}{n_{t-1,h}(s,a)\vee1}\) and by applying Lemma 21. Specifically, we set \({\alpha=2H,C_1=C_2=2L_{t,\delta}}\) and, thus, \(HS(C_2+\alpha C_2/4)\le 3H^2SL_{t,\delta}\) and observe that the conditions of 21 hold since the event \(\cap_t E^p(t)\) holds and by the optimism of 8 under the good event.

Taking the sum over the latter inequality we conclude the proof since \[\begin{align} &\sum_{t=1}^T \bar{V}_{t,h}(s_{t,h}) - V_{h}^{\pi_t}(s_{t,h})\\ &\leq 2\sum_{t=1}^Tb^r_{t,h}(s_{t,h},a_{t,h}) + \sum_{t=1}^T 3H\sqrt{\frac{ L_{t,\delta}}{n_{t-1,h}( s_{t,h},a_{t,h})\vee 1}} + \frac{ 13H^2SL_{t,\delta}}{n_{t-1,h}( s_{t,h},a_{t,h})\vee 1} \\ &\quad + \br*{1+\frac{1}{2H}}\sum_{t=1}^T \mathbb{E}_{P_{h}(\cdot| s_{t,h},a_{t,h})}[ \bar{V}_{t,h+1}(s_{h+1}) - V_{h+1}^{\pi_t}(s_{h+1})]\\ &=2\sum_{t=1}^Tb^r_{t,h}(s_{t,h},a_{t,h}) + \sum_{t=1}^T 3H\sqrt{\frac{ L_{t,\delta}}{n_{t-1,h}( s_{t,h},a_{t,h})\vee 1}} + \frac{ 13H^2SL_{t,\delta}}{n_{t-1,h}( s_{t,h},a_{t,h})\vee 1} \\ &\quad + \br*{1+\frac{1}{2H}}\sum_{t=1}^T \mathbb{E}[ \bar{V}_{t,h+1}(s_{h+1}) - V_{h+1}^{\pi_t}(s_{h+1})|F_{t,h-1}]\\ &\leq 27H^2 \log\br*{\frac{2HT(T+1)}{\delta}} + 2\sum_{t=1}^Tb^r_{t,h}(s_{t,h},a_{t,h}) + \sum_{t=1}^T 3H\sqrt{\frac{ L_{t,\delta}}{n_{t-1,h}( s_{t,h},a_{t,h})\vee 1}} + \frac{ 13H^2SL_{t,\delta}}{n_{t-1,h}( s_{t,h},a_{t,h})\vee 1} \\ &\quad + \br*{1+\frac{1}{2H}}^2\sum_{t=1}^T \bar{V}_{t,h+1}(s_{t,h+1}) - V_{h+1}^{\pi_t}(s_{t,h+1}) _2 = E^O}, \end{align}\] where in the last relation we also bounded \(18\br*{1+\frac{1}{2H}}\le 27\). ◻

Proof. We start by conditioning on the good event \(\mathbb{G}\), which holds with probability greater than \(1-\delta\). Conditioned on the good event, the value is optimistic (Lemma 8). This fact, together with the key recursion lemma (Lemma 11) yields the following. \[\begin{align} \sum_{t=1}^{T}& V_{1}^*(s_{t,1}) - V_{1}^{\pi_t}(s_{t,1}) \leq \sum_{t=1}^{T} \bar{V}_{t,1}(s_{t,1}) - V_{1}^{\pi_t}(s_{t,1})\\ &\leq 27H^2 \log\br*{\frac{2HT(T+1)}{\delta}} + \sum_{t=1}^T2 b^r_{t,1}(s_{t,1},a_{t,1}) + 3H\sqrt{\frac{ L_{t,\delta}}{n_{t-1,h}( s_{t,h},a_{t,h})\vee 1}} + \frac{ 13H^2SL_{t,\delta}}{n_{t-1,1}( s_{t,1},a_{t,1})\vee 1} \\ &\quad + \br*{1+\frac{1}{2H}}^2 \sum_{t=1}^T \bar{V}_{t,2}(s_{t,h+1}) - V_{2}^{\pi_t}(s_{t,2}) . } \end{align}\] Iterating on this relation over \(h\in\brc*{2,\dots,H}\) and using \(\br*{1+\frac{1}{2H}}^{2h}\leq e\leq 3\) for \(h\le H\) and \(\bar{V}_{t,H+1}(s) = V_{H+}^{\pi_t}(s) = 0\), we conclude that \[\begin{align} \sum_{t=1}^{T} V_{1}^*(s_{t,1}) - V_{1}^{\pi_t}(s_{t,1}) &\leq 81H^3 \log\br*{\frac{2HT(T+1)}{\delta}} + 6\sum_{t=1}^T \sum_{h=1}^H b^r_{t,h}(s_{t,h},a_{t,h}) \nonumber \\ &\quad + \sum_{t=1}^T \sum_{h=1}^H 9H\sqrt{\frac{ L_{t,\delta}}{n_{t-1,h}( s_{t,h},a_{t,h})\vee 1}} + \frac{ 39 H^2S L_{t,\delta} }{n_{t-1,h}( s_{t,h},a_{t,h}) \vee 1}. \label{eq:32rl32final32bound32relation321} \end{align}\tag{20}\] The first sum in 20 is bounded in [lemma:32bound32on32cummulative32reward32bonus32RL] as \[\begin{align} 6\sum_{t=1}^T &\sum_{h=1}^H b^r_{t,h}(s_{t,h},a_{t,h}) \\ &\leq 3L_{t,\delta}\br*{6 \sqrt{|\mathcal{L}_R| HT } + 10 SAH\log(HT) + 23SAH + \sum_{t=1}^T\br*{6\sqrt{\frac{|\mathcal{L}_R|H^2}{B(t)}} + 4SAH\frac{\log(1+ B(t))+1}{B(t)}}}. \end{align}\] The second sum in 20 is bounded via the following standard analysis as follows. \[\begin{align} \sum_{t=1}^T \sum_{h=1}^H \frac{ 1}{n_{t-1,h}( s_{t,h},a_{t,h}) \vee 1} &= \sum_{s,a,h}\sum_{i=0}^{n_{T,h}(s,a)} \frac{ 1}{i \vee 1}\nonumber\\ &\leq \sum_{s,a,h}(2+\log(n_{T,h}(s,a)\vee 1)) \nonumber\\ &\leq SAH(2+\log(TH)) \label{eq:32standard32RL32analysis32sum32of32147n} \end{align}\tag{21}\] where the last relation holds by Jensen’s inequality while using \(\sum_{s,a,h}n_{T,h}(s,a) = TH\). Similarly, we bound \[\begin{align} \sum_{t=1}^T \sum_{h=1}^H \frac{ 1}{\sqrt{n_{t-1,h}( s_{t,h},a_{t,h)} \vee 1}} &= \sum_{s,a,h}\sum_{i=0}^{n_{T,h}(s,a)} \frac{ 1}{\sqrt{i \vee 1}}\nonumber\\ &\leq \sum_{s,a,h}\br*{1+2\sqrt{n_{T,h}(s,a)}} \nonumber\\ &\leq SAH + 2\sqrt{SAH^2T} \label{eq:32standard32RL32analysis32sum32of32147sqrt40n41} \end{align}\tag{22}\] Thus, the second sum in 20 is bounded by \[\begin{align} &\sum_{t=1}^T \sum_{h=1}^H 9H\sqrt{\frac{ L_{t,\delta}}{n_{t-1,h}( s_{t,h},a_{t,h})\vee 1}} + \sum_{t=1}^T \sum_{h=1}^H \frac{ 39 H^2S L_{t,\delta} }{n_{t-1,h}( s_{t,h},a_{t,h}) \vee 1}\\ &\leq 9H \sqrt{L_{T,\delta}}\sum_{t=1}^T \sum_{h=1}^H \sqrt{\frac{1}{n_{t-1,h}( s_{t,h},a_{t,h})\vee 1}} + 39 H^2S L_{T,\delta} \sum_{t=1}^T \sum_{h=1}^H \frac{ 1}{n_{t-1,h}( s_{t,h},a_{t,h}) \vee 1}is increasing in t}\\ &\leq 18 \sqrt{SAH^4T L_{T,\delta}} +39 H^3S^2A L_{T,\delta}\log(TH) + 87H^3S^2A L_{T,\delta}. , \eqref{eq:32standard32RL32analysis32sum32of32147sqrt40n41} and since L_{T,\delta}\ge1} \end{align}\] Plugging the bounds on the first and second sums in 20 concludes the proof. ◻

Proof. Let \(q_{t,h}=1\) be the event reward feedback was queried at the \(h^{th}\) time step of the \(t^{th}\) episode and \(q_{t,h}=0\) be its complement event. The following relations hold. \[\begin{align} & \sum_{t=1}^T \sum_{h=1}^H CI^r_{t,h}(s_{t,h},a_{t,h}) = 2\sum_{t=1}^T \sum_{h=1}^H b^r_{t,h}(s_{t,h},a_{t,h}) \nonumber \\ &=\underbrace{\sum_{t=1}^T \sum_{h=1}^H 1{\brc*{q_{t,h}=1}}CI^r_{t,h}(s_{t,h},a_{t,h})}_{(i)} + \underbrace{\sum_{t=1}^T \sum_{h=1}^H 1{\brc*{q_{t,h}=0}}CI^r_{t,h}(s_{t,h},a_{t,h})}_{(ii)} \label{eq:32central32term32reward32bonus32lemma} \end{align}\tag{23}\]

Bound on term \((i)\), episodes in which feedback is queried. The following relations hold. \[\begin{align} (i) &= 2\sum_{t=1}^T \sum_{h=1}^H 1{\brc*{q_{t,h}=1}}b^r_{t,h}(s_{t,h},a_{t,h})\\ &\leq 2\sum_{t=1}^T \sum_{h=1}^H 1{\brc*{q_{t,h}=1}}\sqrt{ \frac{2 \widehat{\mathrm{Var}}_{r,t-1,h}(s_{t,h},a_{t,h}) L_{t,\delta}}{n^q_{t-1,h}(s_{t,h},a_{t,h})\vee 1}} + 2\sum_{t=1}^T \sum_{h=1}^H 1{\brc*{q_{t,h}=1}}\frac{5 L_{t,\delta}}{n^q_{t-1,h}(s_{t,h},a_{t,h})\vee 1}\\ &\overset{(a)}{\leq} 3 \sqrt{L_{T,\delta}}\sum_{s,a,h\in \mathcal{L}_R} \sum_{i=0}^{n^q_{T,h}(s,a)}\sqrt{ \frac{1}{n^q_{t-1,h}(s_{t,h},a_{t,h})\vee 1}} + 10L_{T,\delta}\sum_{s,a,h} \sum_{i=0}^{n_{T,h}(s,a)} \frac{1}{ n^q_{t-1,h}(s_{t,h},a_{t,h})\vee 1} \\ &\leq 6 \sqrt{|\mathcal{L}_R|B^q(T) L_{T,\delta} } + 10 L_{T,\delta}SAH\log(B^q(T)) + 23SAHL_{T,\delta} ,\eqref{eq:32standard32RL32analysis32sum32of32147sqrt40n41}, \& \sum_{s,a,h}n^q_{T,h}(s,a) = B^q(T)}\\ &\leq 6 \sqrt{|\mathcal{L}_R| TH L_{T,\delta} } + 10 L_{T,\delta}SAH\log(TH)+ 23SAHL_{T,\delta}, \end{align}\] Relation \((a)\) holds since \(\widehat{\mathrm{Var}}_{r,t-1,h}(s_{t,h},a_{t,h})=0\) for all rewards with deterministic reward (and zero reward is deterministic); for non-deterministic rewards, \(\widehat{\mathrm{Var}}_{r,t-1,h}(s_{t,h},a_{t,h})\leq 1\).

Bound on term \((ii)\), episodes in which feedback is not queried. Due to Lemma 10 it holds that \(B^q(T)\leq B(T)\), that is, the budget constraint is never violated. For this reason, if reward is not queried, it does not satisfy the query rule of CBM-UCBVI. Using this, we get the following relations. \[\begin{align} (ii) &= \sum_{t=1}^T \sum_{h=1}^H 1{\brc*{q_{t,h}=0}}CI^r_{t,h}(s_{t,h},a_{t,h})\\ &\leq \sum_{t=1}^T \sum_{h=1}^H \br*{L_{t,\delta}\br*{6\sqrt{\frac{|\mathcal{L}_R|}{B(t)}} + 4SAH \frac{\log(1+B(t))+1}{B(t)}}}\\ &\leq L_{T,\delta}\sum_{t=1}^T \sum_{h=1}^H \br*{6\sqrt{\frac{|\mathcal{L}_R|}{B(t)}} +4SAH \frac{\log(1+B(t))+1}{B(t)}}. \end{align}\]

Combining the bounds. Combining the bounds on \((i)\) and \((ii)\) we conclude the proof, \[\begin{align} \eqref{eq:32central32term32reward32bonus32lemma} \leq L_{t,\delta}\br*{6 \sqrt{|\mathcal{L}_R| HT } + 10 SAH\log(HT) + 23SAH + \sum_{t=1}^T\br*{6\sqrt{\frac{|\mathcal{L}_R|H^2}{B(t)}} + 4SAH^2\frac{\log(1+ B(t))+1}{B(t)}}}. \end{align}\] ◻

Proof. Each one of the events \(\cap_t E^r(t), \cap_t E^p(t),\cap_{t} E^{pv1}(t)\) holds with probability greater than \(1-\delta/8\) via similar analysis as in Lemma 7. We now turn to establish the high probability guarantee for the rest of events.

The event \(\cap_t E^{pv2}(t)\) holds with high probability. The event holds with high probability due to [22]. To see this, fix \(s,a,h\) and assume it was sampled for a fixed number of times \({n_{t-1,h}(s,a)=n>1}\). Let \(V_{s,a,h,n} = \frac{1}{2n(n-1)} \sum_{i,j} (V^*_{h+1}(s_i) - V^*_{h+1}(s_j))^2\) where \(s_i\sim P_{h}(\cdot|s,a)\) and are i.i.d.. See that this is an unbiased estimator for the variance, i.e., \(\mathbb{E}[V_{s,a,h,n}] = \mathrm{Var}_{P_h(\cdot| s,a )}(V_{h+1}^*)\). Applying [22], we get that \[\begin{align} \Pr&\br*{\abs*{\sqrt{V_{s,a,h,n}} - \sqrt{\mathbb{E}[V_{s,a,h,n}]}} \leq \sqrt{\frac{2H^2\log(2/\delta)}{n-1}}} \nonumber\\ &\qquad\qquad\qquad\qquad= \Pr\br*{\abs*{\sqrt{V_{s,a,h,n}} - \sqrt{\mathrm{Var}_{P_h(\cdot| s,a )}(V_{h+1}^*)}} \leq \sqrt{\frac{2H^2\log(2/\delta)}{n-1}}}\leq \delta. \label{eq:32event32PV232maurer32theorem3210} \end{align}\tag{25}\] On the other hand, \[\begin{align} V_{s,a,h,n} = \frac{1}{2n(n-1)} \sum_{i,j=1}^n (V^*_{h+1}(s_i) - V^*_{h+1}(s_j))^2 &= \sum_{s'} \frac{N(s')}{n} V^*_{h+1}(s')^2 - \br*{\sum_{s'}\frac{N(s')}{n} V^*_{h+1}(s')}^2\\ &\quad + \frac{1}{n(n-1)}\sum_{i=1}^n V^*_{h+1}(s_i)^2 - \frac{1}{n-1}\br*{\frac{1}{n}\sum_{i=1}^n V^*_{h+1}(s_i)}^2, \end{align}\] where \(N(s')\) is the number of times \(s'\) was sampled. By definition, \(\frac{N(s')}{n}\equiv \bar{P}_{n,h}(s'|s,a)\), that is, \(\frac{N(s')}{n}\) is the estimated transition model. Thus, the \(\mathrm{Var}_{\bar{P}_{n,h}(\cdot|s,a)} =\sum_{s'} \frac{N(s')}{n} V^*_{h+1}(s')^2 - \br*{\sum_{s'}\frac{N(s')}{n} V^*_{h+1}(s_i)}^2\). This, together with \(|V^*_{h}(s)|\leq H\), implies that \(\abs*{V_{s,a,h,n} - \mathrm{Var}_{\bar{P}_{n,h}(\cdot| s,a )}(V_{h+1}^*)} \leq \frac{H^2}{n-1}\), and, thus \[\begin{align} \abs*{ \sqrt{V_{s,a,h,n}} - \sqrt{\mathrm{Var}_{\bar{P}_{n,h}(\cdot| s,a )}(V_{h+1}^*)}} \leq \sqrt{\abs*{V_{s,a,h,n} - \mathrm{Var}_{\bar{P}_{n,h}(\cdot| s,a )}(V_{h+1}^*)}}\leq \sqrt{\frac{H^2}{n-1}},\label{eq:32event32PV232maurer32theorem321032relation321} \end{align}\tag{26}\] by \(\abs{\sqrt{a}-\sqrt{b}}\leq \sqrt{\abs*{a-b}}\). Combining 25 and 26 yields \[\begin{align} \Pr\br*{\abs*{\sqrt{\mathrm{Var}_{\bar{P}_{n,h}(\cdot| s,a )}(V_{h+1}^*)} - \sqrt{\mathrm{Var}_{P_h(\cdot| s,a )}(V_{h+1}^*)}} \leq \sqrt{ \frac{12H^2\log(2/\delta)}{n\vee 1}}}\leq \delta, \end{align}\] since \(\frac{2}{n\vee 1}\geq \frac{1}{n-1}\) for \(n\geq 2\) and for \(n\leq 1\) the bound trivially holds. Utilizing the same techniques as in 7 to generalize this result to hold for any (random) value of \(n=n_{t-1,h}(s,a)\) and any \(s,a,h\) establishes the high probability guarantee.

Combining the results. Taking a union bound concludes the proof. ◻

Proof. Since \(V^\pi_h(s)\leq V^*_h(s)\) for all \(\pi,s\in \mathcal{S},h\in[H]\), we only need to prove the leftmost and rightmost inequalities of the claim. We prove this result via induction.

Base case, the claim holds for \(h=H\).

Rightmost inequality, optimism, . Let \(a^*(s)\in \arg\max_{a\in \mathcal{A}} r_{H}(s,a)\). For any \(s\in \mathcal{S}\) it holds that \[\begin{align} &V^*_{H}(s) -\bar{V}_{t,H}(s) = r_{H}(s,a^*(s)) - \min\brc*{\max_a \brc*{\bar{r}_{t,H}(s,a) + b_{t,H}^r(s,a)},1}. \label{eq:32optimism32base32case32ulcvi32rel321} \end{align}\tag{27}\] Assume that \(\max_a \bar{r}_{t,H}(s,a) + b_{t,H}^r(s,a) < 1\) (otherwise, the inequality holds since \(r(s,a)\leq 1\)). Then, \[\begin{align} \eqref{eq:32optimism32base32case32ulcvi32rel321} &\leq r_{H}(s,a^*(s)) - \bar{r}_{t,H}(s,a^*(s)) - b_{t,H}^r(s,a^*(s))\\ &\leq b_{t,H}^r(s,a^*(s)) - b_{t,H}^r(s,a^*(s))\leq 0 . \end{align}\] Thus, \(V^*_{H}(s) \leq \bar{V}_{t,H}(s)\) for all \(s\in \mathcal{S}\) for \(h=H\).

Leftmost inequality, pessimism. For any \(s\in \mathcal{S}\) it holds that \[\begin{align} &V^{\pi_t}_{H}(s) -\underaccent{\bar}{V}_{t,H}(s) = r_{H}(s,\pi_{t,h}(s)) - \max(\bar{r}_{t,H}(s,\pi_{t,h}(s)) - b_{t,H}^r(s,\pi_{t,h}(s)),0). \label{eq:32optimism32base32case32ucbvi32UL32rel32132pessimsm} \end{align}\tag{28}\] Assume that \(\bar{r}_{t,H}(s,\pi_{t,h}(s)) - b_{t,H}^r(s,\pi_{t,h}(s)) > 0\) (otherwise, the inequality holds since \(r(s,a)\geq 0\)). Then, \[\begin{align} &\eqref{eq:32optimism32base32case32ucbvi32UL32rel32132pessimsm} \geq -b_{t,H}^r(s,\pi_{t,h}(s)) + b_{t,H}^r(s,\pi_{t,h}(s))\geq 0 . \end{align}\] Thus, \(V^*_{H}(s) \geq \underaccent{\bar}{V}_{t,H}(s)\) for all \(s\in \mathcal{S}\) for \(h=H\).

Induction step, prove for \(h\in [H]\) assuming the claim holds for all \(h+1\leq h'\leq H\).

Rightmost inequality, optimism. Let \(a^*(s)\in \arg\max_{a\in \mathcal{A}} Q^{*}_h(s,a)\). The following relations hold. \[\begin{align} &V^*_h(s)- \bar{V}_{t,h}(s) = Q^{*}_h(s,a^*(s))- \min\brc*{\max_a\bar{Q}_{t,h}(s,a),H-h+1} \label{eq:32optimism32base32case32ucbvi32rel32232UL} \end{align}\tag{29}\] Assume that \(\max_a\bar{Q}^{\pi}_{t,h}(s,a)< H-h+1\) (otherwise, the inequality is satisfied since \(Q^*_h(s,a)\leq H-h+1\)). Then, \[\begin{align} \eqref{eq:32optimism32base32case32ucbvi32rel32232UL} &\leq Q^{*}_h(s,a^*(s))- \bar{Q}_{t,h}(s,a^*(s)) \nonumber \\ &= r_h(s,a^*(s)) - \bar{r}_{t-1,h}(s,a^*(s)) - b_{t,h}^r(s,a^*(s)) - b_{t,h}^{p}(s,a^*(s)) \nonumber\\ &\quad + (P_h- \bar{P}_{t-1,h})(\cdot| s,a^*(s))V^*_{h+1} + \mathbb{E}_{\bar{P}_{t-1,h}(\cdot|s,a^*(s))}[ \underbrace{V^{*}_{h+1}(s') - \bar{V}_{t,h+1}(s')}_{\leq 0\;\mathrm{Induction\;hypothesis}}] \nonumber\\ &\leq b_{t,h}^r(s,a^*(s)) - b_{t,h}^r(s,a^*(s)) - b_{t,h}^{p}(s,a^*(s)) + b_{t,h}^{pv1}(s,a^*(s)) (t)\;\&\;\cap_t E^{r}(t) holds} \nonumber\\ &= b_{t,h}^{pv1}(s,a^*(s)) - b_{t,h}^{p}(s,a^*(s)) \label{eq:32optimism32base32case32ucbvi32rel32332UL} \end{align}\tag{30}\] We now analyze this term. \[\begin{align} \eqref{eq:32optimism32base32case32ucbvi32rel32332UL} &= b_{t,h}^{pv1}(s,a^*(s)) - b_{t,h}^{p}(s,a^*(s)) \nonumber \\ &\overset{(a)}{\leq} \sqrt{\frac{2\mathrm{Var}_{P(\cdot| s,a^*(s))}(V^*_{h+1})L_{t,\delta}}{n_{t-1,h}(s,a^*(s)) \vee1}} +\frac{5H L_{t,\delta}}{n_{t-1,h}(s,a^*(s))\vee 1} \nonumber \\ &\quad -\sqrt{\frac{2\mathrm{Var}_{\bar{P}_{t-1,h}(\cdot|s,a^*(s))}(\bar{V}_{t,h+1})L_{t,\delta}}{n_{t-1,h}(s,a^*(s)) \vee 1}} - \frac{18H^2L_{t,\delta}}{n_{t-1,h}(s,a^*(s))\vee 1} - \frac{1}{16H} \mathbb{E}_{\bar{P}_{t-1,h}(\cdot|s,a)}\brs*{\bar{V}_{t,h+1}(s')- V^*_{h+1}(s')} \nonumber\\ &= \sqrt{2L_{t,\delta}}\frac{\sqrt{\mathrm{Var}_{P_h(\cdot|s,a^*(s))}(V^*_{h+1})} -\sqrt{\mathrm{Var}_{\bar{P}_{t-1,h}(\cdot| s,a^*(s))}(\bar{V}_{t,h+1})}}{\sqrt{n_{t-1,h}(s,a^*(s)) \vee1}} \nonumber\\ &\quad - \frac{1}{16H} \mathbb{E}_{\bar{P}_{t-1,h}(\cdot|s,a)}\brs*{\bar{V}_{t,h+1}(s')- V^*_{h+1}(s')}- \frac{13H^2 L_{t,\delta}}{n_{t-1,h}(s,a^*(s))\vee 1} \nonumber\\ &\overset{(b)}{\leq} \frac{1}{16H}\mathbb{E}_{\bar{P}_{t-1,h}(\cdot|s,a)}\brs*{\bar{V}_{t,h+1}(s')- V^*_{h+1}(s')} + \frac{13H^2L_{t,\delta}}{ n_{t-1,h}(s,a)\vee 1} \nonumber\\ &\quad - \frac{1}{16H} \mathbb{E}_{\bar{P}_{t-1,h}(\cdot|s,a)}\brs*{\bar{V}_{t,h+1}(s')- V^*_{h+1}(s')} - \frac{13H^2L_{t,\delta}}{n_{t-1,h}(s,a^*(s)) \vee1} = 0 \nonumber \end{align}\] where \((a)\) holds by plugging the bonus and bounding \(-44 H^2S L_{t,\delta} \leq -18H^2 L_{t,\delta}\), and by the induction hypothesis (\(\underaccent{\bar}{V}_{t-1,h+1}(s)\le V^*_{h+1}(s),\forall s\in\mathcal{S}\)). \((b)\) holds by Lemma 19 while setting \(\alpha= 16H\) and bounding \((5H+ H\alpha/2)\leq 13H^2\). Combining all the above we conclude the proof of the rightmost inequality since \[\begin{align} V^*_h(s)- \bar{V}_{t,h}(s) \leq \eqref{eq:32optimism32base32case32ucbvi32rel32232UL} \leq \eqref{eq:32optimism32base32case32ucbvi32rel32332UL}\leq 0. \end{align}\]

Leftmost inequality, pessimism. The following relations hold. \[\begin{align} &V^{\pi_t}_h(s)- \underaccent{\bar}{V}_{t,h}(s) = Q^{\pi_t}_h(s,\pi_{t,h}(s))- \max(\bar{Q}_{t,h}(s,\pi_{t,h}(s)),0). \label{eq:32optimism32base32case32ucbvi32UL32rel3224432pessimsm} \end{align}\tag{31}\] Assume that \(\bar{Q}_{t,h}(s,\pi_{t,h}(s))>0\) (otherwise, the claim holds since \(Q^{\pi_t}_h(s,\pi_{t,h}(s))\geq 0\)). Then, \[\begin{align} \eqref{eq:32optimism32base32case32ucbvi32UL32rel3224432pessimsm} &= Q^{\pi_t}_h(s,\pi_{t,h}(s))- \underline{Q}_{t,h}(s,\pi_{t,h}(s)) \nonumber \\ &= r_h(s,\pi_{t,h}(s)) - \bar{r}_{t-1,h}(s,\pi_{t,h}(s)) + b_{t,h}^r(s,\pi_{t,h}(s)) + b_{t,h}^{p}(s,\pi_{t,h}(s)) \nonumber\\ &\quad + (P_h-\bar{P}_{t-1,h})(\cdot| s,\pi_{t,h}(s))V^{\pi_t}_{h+1} + \mathbb{E}_{\bar{P}_{t-1,h}(\cdot|s,a)}[ \underbrace{V^{\pi_t}_{h+1}(s') - \underaccent{\bar}{V}_{t,h+1}(s')}_{\geq 0\;\mathrm{Induction\;hypothesis}}|s_h=s,a_h=\pi_{t,h}(s)] \nonumber\\ &\geq -b_{t,h}^r(s,\pi_{t,h}(s)) + b_{t,h}^r(s,\pi_{t,h}(s)) + b_{t,h}^{p}(s,\pi_{t,h}(s)) + (P_h-\bar{P}_{t-1,h})(\cdot| s,\pi_{t,h}(s))V^{\pi_t}_{h+1} (t) holds} \nonumber \\ &= b_{t,h}^{p}(s,\pi_{t,h}(s)) + (P_h-\bar{P}_{t-1,h})(\cdot| s,\pi_{t,h}(s))V^{\pi_t}_{h+1}. \label{eq:32optimism32base32case32ucbvi32UL32rel3234432pessimsm} \end{align}\tag{32}\] We now focus on the last term. Observe that \[\begin{align} &(P_h-\bar{P}_{t-1,h})(\cdot| s,\pi_{t,h}(s))V^{\pi_t}_{h+1} = (P_h-\bar{P}_{t-1,h})(\cdot| s,\pi_{t,h}(s))V^{*}_{h+1} + (P_h-\bar{P}_{t-1,h})(\cdot| s,\pi_{t,h}(s))(V^{\pi_t}_{h+1} - V^*_{h+1})\\ & \geq -b^{pv1}_{t-1,h}(s,\pi_{t,h}(s))+(P_h-\bar{P}_{t-1,h})(\cdot| s,\pi_{t,h}(s))(V^{\pi_t}_{h+1} - V^*_{h+1}) (t) holds}\\ &\overset{(a)}{\geq} -b^{pv1}_{t-1,h}(s,\pi_{t,h}(s)) - \frac{18H^2 SL_{t,\delta}}{n_{t-1,h}(s,\pi_{t,h}(s))\vee 1} - \frac{1}{32H}\mathbb{E}_{\bar{P}_{t-1,h}(\cdot|s,\pi_{t,h}(s))}\brs*{(V^{\pi_t}_{h+1} - V^*_{h+1})(s')} \\ &\geq -b^{pv1}_{t-1,h}(s,\pi_{t,h}(s)) - \frac{18H^2SL_{t,\delta}}{n_{t-1,h}(s,\pi_{t,h}(s))\vee 1} - \frac{1}{32H}\mathbb{E}_{\bar{P}_{t-1,h}(\cdot|s,\pi_{t,h}(s))}\brs*{(\bar{V}_{t,h+1} - \underaccent{\bar}{V}_{t-1,h+1})(s')} \\ &\geq - \sqrt{\frac{2\mathrm{Var}_{P_h(\cdot| s,\pi_{t,h}(s))}(V^*_{h+1})L_{t,\delta}}{n_{t-1,h}(s,\pi_{t,h}(s))\vee 1 }}- \frac{23H^2SL_{t,\delta}}{n_{t-1,h}(s,\pi_{t,h}(s))\vee 1} - \frac{1}{32H}\mathbb{E}_{\bar{P}_{t-1,h}(\cdot|s,\pi_{t,h}(s))}\brs*{(\bar{V}_{t,h+1} - \underaccent{\bar}{V}_{t-1,h+1})(s')} _{t-1,h} and elementary bounds}, \end{align}\] where \((a)\) holds by applying Lemma 21 while setting \(\alpha=32H, C_1=2L_{t,\delta},C_2=2 L_{t,\delta}\) and bounding \(HS(C_2+ \alpha C_1/4)\le 18H^2S L_{t,\delta}\) (assumption holds since \(\cap_t E^{p}(t)\) holds). Plugging this back into 32 and plugging the explicit form of the bonus \(b^p_{t,h}(s,a)\) we get \[\begin{align} \eqref{eq:32optimism32base32case32ucbvi32UL32rel3234432pessimsm} &= \sqrt{2L_{t,\delta}}\frac{\sqrt{\mathrm{Var}_{\bar{P}_{t-1,h}(\cdot| s,\pi_{t,h}(s))}(\bar{V}_{t,h+1})} - \sqrt{\mathrm{Var}_{P_h(\cdot| s,\pi_{t,h}(s))}(V^*_{h+1})}}{\sqrt{n_{t-1,h}(s,\pi_{t,h}(s))\vee 1}} \\ &\quad + \frac{21H^2SL_{t,\delta}}{n_{t-1,h}(s,\pi_{t,h}(s))\vee 1} + \frac{1}{32H}\mathbb{E}_{\bar{P}_{t-1,h}(\cdot|s,\pi_{t,h}(s))}\brs*{\bar{V}_{t,h+1}(s') - \underaccent{\bar}{V}_{t-1,h+1}(s')}\\ &\overset{(a)}{\geq} -\frac{1}{32H}\mathbb{E}_{\bar{P}_{t-1,h}(\cdot|s,\pi_{t,h}(s))}\brs*{\bar{V}_{t,h+1}(s')- V^*_{h+1}(s')} - \frac{21H^2 L_{t,\delta}}{n_{t-1,h}(s,\pi_{t,h}(s))}\\ &\quad + \frac{1}{32H}\mathbb{E}_{\bar{P}_{t-1,h}(\cdot|s,\pi_{t,h}(s))}\brs*{\bar{V}_{t,h+1}(s') - \underaccent{\bar}{V}_{t-1,h+1}(s')} + \frac{21H^2S L_{t,\delta}}{n_{t-1,h}(s,\pi_{t,h}(s))}\geq 0 \end{align}\] where \((a)\) holds by Lemma 19 while setting \(\alpha=32H\) and bounding \((5H+ H\alpha/2)L_{t,\delta}\leq 21H^2 L_{t,\delta}\). Combining all the above we concludes the proof as \[\begin{align} V^{\pi_t}_h(s)- \underaccent{\bar}{V}_{t,h}(s)\geq\eqref{eq:32optimism32base32case32ucbvi32UL32rel3224432pessimsm}\geq \eqref{eq:32optimism32base32case32ucbvi32UL32rel3234432pessimsm}\geq 0. \end{align}\] ◻

Proof. Event \(E^{OP}\). The proof follows the lines of 9 while noting that \(0\leq \bar{V}_{t,h+1}(s_{t,h+1}) - \underaccent{\bar}{V}_{t,h+1}(s_{t,h+1})\leq H\) (replacing \(\bar{V}_{t,h+1}(s_{t,h+1}) - V^{\pi_t}_{h}(s_{t,h})\) as in Lemma 9). This holds conditioned on the first good event due to the optimism-pessimism lemma (Lemma 13). Notice that we replaced \(\delta\to\delta/2\), and therefore, the proof results with \(\Pr(\overline{E^{OP}}\cap \mathbb{G}_1)\le\frac{\delta}{4}\).

Event \(E^{\mathrm{Var}}\). Fix \(h\in [H]\). Set \(Y_t = Y_{2, t, h} = \mathrm{Var}_{P_h(\cdot|s_{t,h},a_{t,h})}( V^{\pi_t}_{h+1})\), and the filtration as \(\brc*{F_{t}}_{t\geq 0}\) (observe that \(Y_t\) is \(F_{t}\) measurable). Furthermore, see that \(0\leq Y_{2, t, h}\leq H\) a.s. . Applying the second statement of 20 we get that \[\begin{align} \sum_{t=1}^T Y_{2, t, h} \leq 2\sum_{t=1}^T\mathbb{E}[Y_{2, t, h}|F_{t-1}] + 4H^2 \log\frac{1}{\delta}. \end{align}\] By taking union bound, as in the proof of the first statement of the lemma and on all \(h\in [H]\) and summing over \(h\in [H]\), we get that with probability greater than \(1-\delta/4\) for all \(T\geq1\) it holds that \[\begin{align} \sum_{t=1}^T \sum_{h=1}^H Y_{2, t, h} \leq 2\sum_{t=1}^T\sum_{h=1}^H \mathbb{E}[Y_{2, t, h}|F_{t-1}] + 4H^3 \log\frac{4HT(T+1)}{\delta}. \end{align}\]

Combining all the above We bound the probability of \(\overline{G}\) as follows: \[\begin{align} \Pr(\overline{\mathbb{G}}) \le \Pr(\overline{\mathbb{G}_1}) + \Pr(\overline{E^{OP}}\cap\mathbb{G}_1) + \Pr(\overline{E^{\mathrm{Var}}}) \le \frac{\delta}{2} + \frac{\delta}{4} +\frac{\delta}{4}= \delta. \end{align}\] ◻

Proof. We bound each of the terms in the sum as follows. \[\begin{align} &\bar{V}_{t,h}(s_{t,h}) - \underaccent{\bar}{V}_{t,h}(s_{t,h}) \nonumber \\ &= 2b^r_{t,h}(s_{t,h},a_{t,h}) + 2b^{p}_{t-1}(s_{t,h},a_{t,h}) + \br*{1+\frac{1}{16H}}\mathbb{E}_{\bar{P}_{t-1,h}(\cdot| s_{t,h},a_{t,h})}[ \bar{V}_{t,h+1}(s_{h+1}) - \underaccent{\bar}{V}_{t,h+1}(s_{h+1})] \nonumber \\ &= 2b^r_{t,h}(s_{t,h},a_{t,h}) + 2b^{p}_{t-1}(s_{t,h},a_{t,h}) + \br*{1+\frac{1}{16H}}\mathbb{E}[ \bar{V}_{t,h+1}(s_{h+1}) - \underaccent{\bar}{V}_{t,h+1}(s_{h+1}) | F_{t,h-1}] \nonumber\\ &\quad + \br*{1+\frac{1}{16H}}(\bar{P}_{t-1,h}-P_h)(\cdot |s,a)^T \br*{\bar{V}_{t,h+1} - \underaccent{\bar}{V}_{t,h+1}}\nonumber\\ &\leq 2b^r_{t,h}(s_{t,h},a_{t,h}) + 2b^{p}_{t-1}(s_{t,h},a_{t,h}) + \frac{6SH^2L_{t,\delta}}{n_{t-1,h}(s,a)\vee 1}+ \br*{1+\frac{1}{4H}}\mathbb{E}[ \bar{V}_{t,h+1}(s_{h+1}) - \underaccent{\bar}{V}_{t,h+1}(s_{h+1}) | F_{t,h-1}] \label{eq:32central32theorem32UL32RL32relation321}, \end{align}\tag{33}\] where the last relation holds by Lemma 21 while setting \(\alpha=8H,C_1=C_2=2L_{t,\delta}\) and bounding \(HS( C_2+ \alpha S C_1/4)\le 6SH^2 L_{t,\delta}\) (the assumption of the lemma holds since the event \(\cap_t E^p(t)\) holds). By Lemma 17 it holds that \[\begin{align} \sum_{t=1}^T b^p_{t,h}(s_{t,h},a_{t,h})\leq &\sum_{t=1}^T\frac{109H^2S L_{t,\delta}}{ n_{t-1,h}(s_{t,h},a_{t,h})\vee 1} + \sqrt{2L_{t,\delta}}\frac{\sqrt{\mathrm{Var}_{P_{h}(\cdot|s_{t,h},a_{t,h})}(V^{\pi_t}_{h+1})}}{\sqrt{n_{t,h}(s_{t,h},a_{t,h})\vee 1}} \\ & + \frac{1}{8H}\sum_{t=1}^T \mathbb{E}[\bar{V}_{t,h+1}(s_{t,h+1}) - \underaccent{\bar}{V}_{t,h+1}(s_{t,h+1})| F_{t,h-1}]. \end{align}\] Plugging this into 33 and rearranging the terms we get \[\begin{align} \sum_{t=1}^T\bar{V}_{t,h}(s_{t,h}) - \underaccent{\bar}{V}_{t,h}(s_{t,h}) &\leq 2\sum_{t=1}^T b^r_{t,h}(s_{t,h},a_{t,h}) + \sum_{t=1}^T\frac{224H^2S L_{t,\delta}}{ n_{t-1,h}(s_{t,h},a_{t,h})\vee 1} + 2\sqrt{2L_{t,\delta}}\frac{\sqrt{\mathrm{Var}_{P_{h}(\cdot|s_{t,h},a_{t,h})}(V^{\pi_t}_{h+1})}}{\sqrt{n_{t,h}(s_{t,h},a_{t,h})\vee 1}} \\ &\quad+ \br*{1+ \frac{1}{2H}}\sum_{t=1}^T \mathbb{E}[\bar{V}_{t,h+1}(s_{t,h+1}) - \underaccent{\bar}{V}_{t,h+1}(s_{t,h+1})| F_{t,h-1}]\\ &\leq 27H^2\log\br*{\frac{4HT(T+1)}{\delta}}+ 2\sum_{t=1}^T b^r_{t,h}(s_{t,h},a_{t,h}) +\sum_{t=1}^T\frac{224H^2S L_{t,\delta}}{ n_{t-1,h}(s_{t,h},a_{t,h})\vee 1} \\ &\quad+ 2\sqrt{2L_{t,\delta}}\frac{\sqrt{\mathrm{Var}_{P_{h}(\cdot|s_{t,h},a_{t,h})}(V^{\pi_t}_{h+1})}}{\sqrt{n_{t,h}(s_{t,h},a_{t,h})\vee 1}} + \br*{1+ \frac{1}{2H}}^2\sum_{t=1}^T \bar{V}_{t,h+1}(s_{t,h+1}) - \underaccent{\bar}{V}_{t,h+1}(s_{t,h+1}),holds (the second good event)} \end{align}\] where in the last relation we also bounded \(18\br*{1+\frac{1}{2H}}\le 27\). ◻

Proof. Start by conditioning on the good event which holds with probability greater than \(1-\delta\). Applying the optimism-pessimism of the upper and lower value function we get \[\begin{align} \sum_{t=1}^{T} V_{1}^*(s_{t,1}) - V_{1}^{\pi_t}(s_{t,1}) \leq \sum_{t=1}^{T} \bar{V}_{t,1}(s_{t,1}) - \underaccent{\bar}{V}_{t,1}(s_{t,1}). \label{eq:32central32thm32UL32RL32132relation} \end{align}\tag{34}\] Iteratively applying 16 and bound the exponential growth by \(\br*{1+\frac{1}{2H}}^{2h}\leq e\leq 3\) for any \(h\in\brc*{0,\dots,H}\), The following upper bound on the cumulative regret is obtained. \[\begin{align} &\eqref{eq:32central32thm32UL32RL32132relation} \leq 81H^3 \log\br*{ \frac{HT(T+1)}{\delta}} + 6\sum_{t=1}^T \sum_{h=1}^H b^r_{t,h}(s_{t,h},a_{t,h}) + \sum_{t=1}^T \sum_{h=1}^H\frac{ 672 H^2SL_{t,\delta}}{n_{t-1,h}^{p}( s_{t,h},a_{t,h})\vee 1} \nonumber \\ &\quad\quad +9\sum_{t=1}^T \sum_{h=1}^H \frac{\sqrt{L_{t,\delta}\mathrm{Var}_{P_h(\cdot|s_{t,h},a_{t,h})}(V^{\pi_t}_{h+1}) }}{\sqrt{n_{t-1,h}(s_{t,h},a_{t,h})}}. \label{eq:32rl32final32bound32relation32232UL} \end{align}\tag{35}\] The first sum in 35 is bounded in [lemma:32bound32on32cummulative32reward32bonus32RL] (the reward bonus is exactly the same as for CBM-UCBVI which implies the same upper bound on the sum of bonuses hold) by \[\begin{align} &6\sum_{t=1}^T \sum_{h=1}^H b^r_{t,h}(s_{t,h},a_{t,h})\\ &\leq 3L_{t,\delta}\br*{6 \sqrt{|\mathcal{L}_R| HT } + 10 SAH\log(HT) + 23SAH + \sum_{t=1}^T\br*{6\sqrt{\frac{|\mathcal{L}_R|H^2}{B(t)}} + 4SAH^2\frac{\log(1+ B(t))+1}{B(t)}}}. \end{align}\] The second sum is bounded via standard analysis as follows: \[\begin{align} \sum_{t=1}^T \sum_{h=1}^H\frac{ 672 H^2SL_{t,\delta}}{n_{t-1,h}( s_{t,h},a_{t,h})\vee 1} &\leq 672 H^2SL_{T,\delta} \sum_{t=1}^T \sum_{h=1}^H\frac{1}{n_{t-1,h}( s_{t,h},a_{t,h})\vee 1}increasing in t}\\ &= 672 H^2S L_{T,\delta} \sum_{s,a,h} \sum_{i=0}^{n_{T,h}(s,a)} \frac{1}{i\vee 1} \\ &\leq 672 H^2S L_{T,\delta} \sum_{s,a,h} (2+\log(n_{T,h}(s,a)\vee1))\\ &\leq 672 H^3S^2AL_{T,\delta}(2+\log(TH))n_{T,h}(s,a)=HT} \\& \leq 2688 H^3S^2AL_{T,\delta}\log(TH+1) \end{align}\] The third sum in 35 is bounded in Lemma 18 by \[\begin{align} &9\sum_{t=1}^T \sum_{h=1}^H \frac{\sqrt{L_{t,\delta}\mathrm{Var}_{P_h(\cdot|s_{t,h},a_{t,h})}(V^{\pi_t}_{h+1}) }}{\sqrt{n_{t-1,h}(s_{t,h},a_{t,h})}} \leq 9 \sqrt{L_{T,\delta}}\sum_{t=1}^T \sum_{h=1}^H \frac{\sqrt{\mathrm{Var}_{P_h(\cdot|s_{t,h},a_{t,h})}(V^{\pi_t}_{h+1}) }}{\sqrt{n_{t-1,h}(s_{t,h},a_{t,h})}}increasing in t}\\ &\leq 27\sqrt{ SAH^3 T \log(TH+1)L_{T,\delta}} + 36H^2\sqrt{SA \log(TH+1) \log\br*{\frac{4HT(T+1)}{\delta}}L_{T,\delta}} \end{align}\] Combining the above bounds with proper simplification yields a bound on 35 and concludes the proof, \[\begin{align} \eqref{eq:32rl32final32bound32relation32232UL}\leq 45 L_{T,\delta}^2 \br*{\sqrt{SAH^3 T} + \sum_{t=1}^T\br*{\sqrt{\frac{|\mathcal{L}_R|H^2}{B(t)}} + SAH^2\frac{\log(1+ B(t))+1}{B(t)}}}+ 2904 H^3S^2A L^2_{T,\delta}. \end{align}\] ◻

Proof. First, observe that \[\begin{align} &\mathbb{E}_{\bar{P}_{t-1,h}(\cdot|s,a)}\brs{\bar{V}_{t,h+1}(s') - \underaccent{\bar}{V}_{t,h+1}(s')} \nonumber \\ & = \mathbb{E}_{P_{h}(\cdot|s,a)}\brs{\bar{V}_{t,h+1}(s') - \underaccent{\bar}{V}_{t,h+1}(s')} + (\bar{P}_{t-1,h}- P_h)(\cdot|s,a)^T\brs*{\bar{V}_{t,h+1}(s')- \underaccent{\bar}{V}_{t,h+1}(s')} \nonumber\\ &\leq \frac{9}{8}\mathbb{E}_{P_{h}(\cdot|s,a)}\brs{\bar{V}_{t,h+1}(s') - \underaccent{\bar}{V}_{t,h+1}(s')} + \frac{ 6H^2S L_{t,\delta}}{n_{t-1,h}(s,a)\vee 1}, \label{eq:32useful32relation32bound32on32bonus32bp} \end{align}\tag{36}\] by applying Lemma 21 with \(\alpha=8H,C_1=C_2=2L_{t,\delta}\) and \(HS(C_2+ \alpha C_1/4)\le 6H^2S\) (applicable since \(\cap_t E^p(t)\) holds).

The bonus \(b^p_{t,h}(s,a)\) can be upper bounded as follows. \[\begin{align} &b^p_{t,h}(s,a)\leq \sqrt{2}\sqrt{\frac{\mathrm{Var}_{\bar{P}_{t-1,h}(\cdot| s,a)}(\bar{V}_{t,h+1}) L_{t,\delta}}{n_{t-1,h}(s,a)\vee 1}} + \frac{1}{16H}\mathbb{E}_{\bar{P}_{t-1,h}(\cdot|s,a)}\brs{\bar{V}_{t,h+1}(s') - \underaccent{\bar}{V}_{t,h+1}(s')} + \frac{ 44H^2S L_{t,\delta}}{n_{t-1,h}(s,a)\vee 1} \nonumber \\ &\leq \sqrt{2}\sqrt{\frac{\mathrm{Var}_{\bar{P}_{t-1,h}(\cdot| s,a)}(\bar{V}_{t,h+1}) L_{t,\delta}}{n_{t-1,h}(s,a)\vee 1}} + \frac{9}{128H}\mathbb{E}_{P_{h}(\cdot|s,a)}\brs{\bar{V}_{t,h+1}(s') - \underaccent{\bar}{V}_{t,h+1}(s')} + \frac{50H^2S L_{t,\delta}}{n_{t-1,h}(s,a)\vee 1}\label{eq:3232bound32on32bp32UL32RL32relation321}, \end{align}\tag{37}\] by 36 . We bound the first term to establish the lemma.

Bound on the first term of 37 It holds that \[\begin{align} &\sqrt{2L_{t,\delta}}\sqrt{\frac{\mathrm{Var}_{\bar{P}_{t-1,h}(\cdot| s,a)}(\bar{V}_{t,h+1}) }{n_{t-1,h}(s,a)\vee 1}}\\ &=\underbrace{\sqrt{2L_{t,\delta}}\frac{\sqrt{\mathrm{Var}_{\bar{P}_{t-1,h}(\cdot| s,a)}(\bar{V}_{t,h+1})} - \sqrt{\mathrm{Var}_{P_{h}(\cdot| s,a)}(V^*_{h+1})} }{\sqrt{n_{t-1,h}(s,a)\vee 1}} }_{(i)} +\underbrace{\sqrt{2L_{t,\delta}}\frac{ \sqrt{\mathrm{Var}_{P_{h}(\cdot| s,a)}(V^*_{h+1})} - \sqrt{\mathrm{Var}_{P_{h}(\cdot| s,a)}(V^{\pi_t}_{h+1})}}{\sqrt{n_{t-1,h}(s,a)\vee 1}}}_{(ii)} \\ &\quad\quad +\frac{\sqrt{2L_{t,\delta}}\sqrt{\mathrm{Var}_{P_{h}(\cdot| s,a)}(V^{\pi_t}_{h+1})}}{\sqrt{n_{t-1,h}(s,a)\vee 1}}. \end{align}\] Term \((i)\) is bounded by Lemma 19 (by setting \(\alpha=32H\) and \((5H+ H\alpha/2)\leq 21H^2\)), \[\begin{align} \sqrt{2L_{t,\delta}}\frac{\sqrt{\mathrm{Var}_{\bar{P}_{t-1,h}(\cdot| s,a)}(\bar{V}_{t,h+1})} - \sqrt{\mathrm{Var}_{P_{h}(\cdot| s,a)}(V^*_{h+1})} }{\sqrt{n_{t-1,h}(s,a)\vee 1}} \leq \frac{1}{32H}\mathbb{E}_{\bar{P}_{t-1,h}(\cdot|s,a)}\brs*{\bar{V}_{t,h+1}(s')- V^*_{h+1}(s')} + \frac{21H^2L_{t,\delta}}{ n_{t-1,h}(s,a)\vee 1}. \end{align}\] Following the same steps as in 36 , we get \[\begin{align} &\mathbb{E}_{\bar{P}_{t-1,h}(\cdot|s,a)}\brs*{\bar{V}_{t,h+1}(s')- V^*_{h+1}(s')} \leq \frac{9}{8}\mathbb{E}_{P_{h}(\cdot|s,a)}\brs*{\bar{V}_{t,h+1}(s')- V^*_{h+1}(s')} + \frac{6H^2S L_{t,\delta}}{n_{t-1,h}(s,a)\vee 1}, \end{align}\] and, thus, \[\begin{align} (i) \leq \frac{9}{256H}\mathbb{E}_{P_{h}(\cdot|s,a)}\brs*{\bar{V}_{t-1,h+1}(s')- V^*_{h+1}(s')} + \frac{27 H^2S L_{t,\delta}}{ n_{t-1,h}(s,a)\vee 1}. \end{align}\] Term \((ii)\) is bounded as follows. \[\begin{align} &(ii)\leq \sqrt{2L_{t,\delta}}\frac{ \sqrt{\mathrm{Var}_{P_{h}(\cdot| s,a)}(V^*_{h+1} - V^{\pi_t}_{h+1})}}{\sqrt{n_{t-1,h}(s,a)\vee 1}} }\\ &\leq \sqrt{2L_{t,\delta}}\frac{ \sqrt{\mathbb{E}_{P_{h}(\cdot|s,a)}[(V^*_{h+1}(s') - V^{\pi_t}_{h+1}(s'))^2]}}{\sqrt{n_{t-1,h}(s,a)\vee 1}}\\ &\leq \sqrt{2L_{t,\delta}}\frac{ \sqrt{H\mathbb{E}_{P_{h}(\cdot|s,a)}[(V^*_{h+1}(s') - V^{\pi_t}_{h+1}(s'))]}}{\sqrt{n_{t-1,h}(s,a)\vee 1}} (s') - V^{\pi_t}_{h+1}(s')\leq H }\\ &\leq \frac{1}{64H}\mathbb{E}_{P_{h}(\cdot|s,a)}[(V^*_{h+1}(s') - V^{\pi_t}_{h+1}(s'))] + \frac{32H^2L_{t,\delta}}{n_{t-1,h}(s,a)\vee 1}. {\alpha}a^2 + \frac{\alpha}{4}b^2 for \alpha=64H} \end{align}\] Thus, applying \(\underaccent{\bar}{V}_{h+1}\leq V^{\pi_t}_{h+1}\leq V^*_{h+1}\leq \bar{V}_{h+1}\) (Lemma 13) in the bounds of \((i)\) and \((ii)\) we get \[\begin{align} &b^p_{t,h}(s,a)\leq \frac{1}{8H}\mathbb{E}_{P_{h}(\cdot|s,a)}[(\bar{V}_{t,h}(s') - \underaccent{\bar}{V}_{t,h}(s'))] +\frac{109H^2S L_{t,\delta}}{ n_{t-1,h}(s,a)\vee 1} + \frac{\sqrt{2L_{t,\delta}}\sqrt{\mathrm{Var}_{P_{h}(\cdot| s,a)}(V^{\pi_t}_{h+1})}}{\sqrt{n_{t-1,h}(s,a)\vee 1}}. \end{align}\] and summing over \(t\) concludes the proof. ◻

Proof. Applying Cauchy-Schwartz inequality we get \[\begin{align} &\sum_{t=1}^T\sum_{h=1}^H \frac{\sqrt{\mathrm{Var}_{P_h(\cdot|s_{t,h},a_{t,h})}(V^{\pi_t}_{h+1}) }}{\sqrt{n_{t-1,h}(s_{t,h},a_{t,h}) \vee 1}}\\ &\leq\sqrt{\sum_{t=1}^T\sum_{h=1}^H \mathrm{Var}_{P_h(\cdot|s_{t,h},a_{t,h})}(V^{\pi_t}_{h+1})} \sqrt{\sum_{t=1}^T\sum_{h=1}^H \frac{1}{n_{t-1,h}(s_{t,h},a_{t,h})\vee 1}} \\ &\leq \sqrt{\sum_{t=1}^T\sum_{h=1}^H \mathrm{Var}_{P_h(\cdot|s_{t,h},a_{t,h})}(V^{\pi_t}_{h+1})} \sqrt{SAH (2+\log(TH))} }\\ &\leq 2\sqrt{2\sum_{t=1}^T \mathbb{E}\brs*{\sum_{h=1}^H \mathrm{Var}_{P_h(\cdot|s_{t,h},a_{t,h})}(V^{\pi_t}_{h+1})| F_{t-1} } +4H^3\log\br*{\frac{4HT(T+1)}{\delta}}}\sqrt{SAH \log(TH+1)} } holds} \\ &\leq 3\sqrt{\sum_{t=1}^T \mathbb{E}\brs*{\sum_{h=1}^H \mathrm{Var}_{P_h(\cdot|s_{t,h},a_{t,h})}(V^{\pi_t}_{h+1})| F_{t-1}}} \sqrt{SAH \log(TH+1)} + 4H^2\sqrt{SA \log(TH+1) \log\br*{\frac{4HT(T+1)}{\delta}}} \leq \sqrt{a} + \sqrt{b}}\\ &=3\sqrt{\sum_{t=1}^T \mathbb{E}\brs*{\br*{ V_1^{\pi_t}(s_1) - \sum_{h=1}^H r_h(s_{t,h},a_{t,h})}^2 \bigg\vert F_{t-1}}} \sqrt{SAH \log(TH+1)} + 4H^2\sqrt{SA \log(TH+1)) \log\br*{\frac{4HT(T+1)}{\delta}}} , see Lemma~\ref{lemma:32law32of32total32variance32for32RL} }\\ &\leq 3\sqrt{ SAH^3 T \log(TH+1)} + 4H^2\sqrt{SA\log(TH+1) \log\br*{\frac{4HT(T+1)}{\delta}}} . (s)\in[0,H],\;r_h(s,a)\in[0,1]} \end{align}\] ◻

Proof. Conditioning on the first good event the following relations hold. \[\begin{align} & \abs*{\sqrt{\mathrm{Var}_{\bar{P}_{t-1,h}(\cdot| s,a)}(\bar{V}_{t,h+1})} - \sqrt{\mathrm{Var}_{P_h(\cdot| s,a)}(V^*_{h+1})}}\\ &\leq \abs*{\sqrt{\mathrm{Var}_{\bar{P}_{t-1,h}(\cdot| s,a)}(\bar{V}_{t,h+1})} - \sqrt{\mathrm{Var}_{\bar{P}_{t-1,h}(\cdot| s,a)}(V^*_{h+1})}} + \sqrt{\frac{12H^2 L_{t,\delta}}{n_{t-1,h}(s,a) \vee 1}} (t) holds} \nonumber\\ &\leq \sqrt{\mathrm{Var}_{\bar{P}_{t-1}(\cdot| s,a)}(V^*_{h+1} - \bar{V}_{t,h+1})} + \sqrt{\frac{12H^2 L_{t,\delta}}{n_{t-1,h}(s,a) \vee 1}} }\\ &\leq \sqrt{\mathbb{E}_{\bar{P}_{t-1,h}}\brs*{(V^*_{h+1}(s') - \bar{V}_{t,h+1}(s'))^2}} + \sqrt{\frac{12H^2 L_{t,\delta}}{n_{t-1,h}(s,a) \vee 1}} \\ &\leq \sqrt{H\mathbb{E}_{\bar{P}_{t-1,h}}\brs*{\bar{V}_{t,h+1}(s') - V^*_{h+1}(s')}} + \sqrt{\frac{12H^2 L_{t,\delta}}{n_{t-1,h}(s,a) \vee 1}} , \end{align}\] where the last relation holds since \(V^*_{h+1}(s'),\bar{V}_{t,h+1}(s')\in [0,H]\) (the first, by model assumption, and the second, by the update rule) and since \(V^*_{h+1}(s')\leq \bar{V}_{t,h+1}(s')\) by the assumption the value is optimistic. Thus, \[\begin{align} &\sqrt{2L_{t,\delta}}\frac{ \abs*{\sqrt{\mathrm{Var}_{\bar{P}_{t-1,h}(\cdot| s,a)}(\bar{V}_{t,h+1})} - \sqrt{\mathrm{Var}_{P_h(\cdot| s,a)}(V^*_{h+1})}}}{\sqrt{n_{t-1,h}(s,a)}}\\ &\leq \sqrt{\mathbb{E}_{\bar{P}_{t-1,h}}\brs*{\bar{V}_{t,h+1}(s') - V^*_{h+1}(s')}} \sqrt{\frac{2HL_{t,\delta}}{n_{t-1,h}(s,a)\vee 1}} + \frac{\sqrt{24}H L_{t,\delta}}{n_{t-1,h}(s,a) \vee 1}\\ &\leq \frac{1}{\alpha} \mathbb{E}_{\bar{P}_{t-1,h}}\brs*{\bar{V}_{t,h+1}(s') - V^*_{h+1}(s')} + \frac{(5H+H\alpha/2)L_{t,\delta}}{n_{t-1,h}(s,a) \vee 1} {\alpha}a^2 + \frac{\alpha}{4}b^2}. \end{align}\] ◻

Proof. First statement. Let \(X_{t} \stackrel{\text{def}}{=}\mathbb{E}[Y_t|F_{t-1}] - Y_t.\) Observe that \(X_{t}\) is a martingale difference sequence w.r.t. to \(\brc*{F_{t}}_{t\geq 0}\), and that \(|X_{t}|\leq C\) a.s.. Furthermore, observe that \[\begin{align} &\mathbb{E}[X^2_{t}|F_{t-1}] \leq 2\mathbb{E}[(\mathbb{E}[Y_t|F_{t-1}])^2|F_{t-1}] + 2\mathbb{E}[Y_t^2|F_{t-1}]\nonumber\\ &\leq 4\mathbb{E}[Y_t^2|F_{t-1}]\nonumber\\ &\leq 4C \mathbb{E}[Y_t|F_{t-1}], \label{eq:32second32moment32for32freedman} \end{align}\tag{38}\] where the last relation holds since \(Y_t\geq 0\) and \(Y_t\leq C\). Applying Freedman’s inequality we get that \[\begin{align} \sum_{t=1}^T \br*{\mathbb{E}[Y_t|F_{t-1}] - Y_t } = \sum_{t=1}^T X_{t} &\leq \eta\sum_{t=1}^T \mathbb{E}[X_{t}^2|F_{t-1}] + \frac{\log(1/\delta)}{\eta} }\\ &\leq \eta \sum_{t=1}^T 4C\mathbb{E}[Y_t|F_{t-1}] + \frac{\log(1/\delta)}{\eta}. } \end{align}\] Choosing \(\eta =\frac{1}{4C(2C+1)}\in (0,\frac{1}{C})\) and rearranging we get \[\begin{align} \sum_{t=1}^T \br*{1 - \frac{1}{2C+1}}\mathbb{E}[Y_t|F_{t-1}] &= \sum_{t=1}^T \br*{\frac{2C}{2C+1}}\mathbb{E}[Y_t|F_{t-1}]\\ &\leq \sum_{t=1}^T Y_t + 4C(2C+1)\log(1/\delta). \end{align}\] Thus, \[\begin{align} \sum_{t=1}^T \mathbb{E}[Y_t|F_{t-1}] \leq \sum_{t=1}^T \br*{1+\frac{1}{2C}}Y_t + 2(2C+1)^2\log(1/\delta). \end{align}\]

Second statement. Let \(X_{t} \stackrel{\text{def}}{=}Y_t - \mathbb{E}[Y_t|F_{t-1}].\) Similarly to before, it holds that \(X_{t}\) is a martingale difference sequence w.r.t. to the filtration \(F_{t-1}\), and that \(|X_{t,h}|\leq C\) a.s. . Similarly to 38 which is sign invariant we get \(\mathbb{E}[X^2_{t}|F_{t-1}] \leq 4C \mathbb{E}[Y_t|F_{t-1}]\). Applying Freedman’s inequality we get \[\begin{align} \sum_{t=1}^T Y_t- \mathbb{E}[Y_t|F_{t-1}] = \sum_{t=1}^T X_{t} &\leq \eta\sum_{t=1}^T \mathbb{E}[X_{t}^2|F_{t-1}] + \frac{\log(1/\delta)}{\eta} }\\ &\leq \eta\sum_{t=1}^T 4C \mathbb{E}[Y_t|F_{t-1}] + \frac{\log(1/\delta)}{\eta}. \end{align}\] Setting \(\eta = 1/4C\) and rearranging concludes the proof of the second statement. ◻

Proof. The following relations hold. \[\begin{align} \abs*{\Delta P_{h} (\cdot| s,a)Y} & \le \sum_{s'}\abs*{\Delta P_{h} (s'| s,a)}\cdot\abs*{Y(s')}\\ & \leq \sum_{s'}\br*{\sqrt{\frac{C_1 P_{1,h}(s'| s,a )}{n(s,a)\vee 1}}Y(s') + \frac{H C_2}{n(s,a)\vee 1}} }\\ & = \sum_{s'}\sqrt{\frac{C_1 P_{1,h}(s'| s,a)Y^2(s')}{n(s,a)\vee 1}} + \frac{H S C_2 }{n(s,a)\vee 1}\\ &\leq \sum_{s'}\sqrt{P_{1,h}(s'| s,a)Y(s')}\sqrt{\frac{HC_1}{n(s,a)\vee 1}} + \frac{H S C_2 }{n(s,a)\vee 1} \\ &\leq \sqrt{\sum_{s'} P_{1,h}(s'| s,a)Y(s')}\sqrt{\frac{S HC_1}{n(s,a)\vee 1}} + \frac{H S C_2 }{n(s,a)\vee 1} \tag{ Cauchy–Schwarz inequality}\\ &\overset{(*)}{\leq} \frac{1}{2\alpha }\sum_{s'} P_{1,h}(s'| s,a)Y(s')+ \frac{ \alpha S HC_1}{2n(s,a)\vee 1}+ \frac{H S C_2}{n(s,a)\vee 1}, \end{align}\] where \((*)\) is by Young’s inequality, namely, \(ab\leq \frac{a^2}{2\alpha} + \frac{\alpha}{2}b^2\) for any \(\alpha>0\). Re-scaling \(2 \alpha =\alpha'\) we conclude the proof. ◻

Proof. Let \(\eta = (1{\brc*{q_1}}\eta_1,.,,1{\brc*{q_t}}\eta_t)^T\) and denote \(X=X_t,Y=Y_t\). Observe that \[\begin{align} \hat{\theta}_t &= (X^TX+\lambda I_d)^{-1} X^T(X\theta^* + \eta)\\ &= (X^TX+\lambda I_d)^{-1} X^T\eta +\theta^* - \lambda(X^TX+\lambda I_d)^{-1}\theta^*. \end{align}\] Thus, for any \(x\in \mathbb{R}^d\) \[\begin{align} \inner{x, \hat{\theta}_t-\theta^*} = \inner{x, X^T\eta}_{V_t^{-1}} - \lambda\inner{x, \theta^*}_{V_{t}^{-1}}, \end{align}\] where \(V_t = X^TX+\lambda I\). Since \(V_t\) is positive definite and symmetric the inner product is well define. By Cauchy-Schwartz inequality, we get \[\begin{align} | \inner{x, \hat{\theta}_t-\theta^*}| &\leq \norm{x}_{V_t^{-1}} \br*{\norm{X^T\eta}_{V_t^{-1}} +\lambda\norm{\theta^*}_{V_t^{-1}}} \nonumber \\ & \leq \norm{x}_{V_t^{-1}} \br*{\norm{X^T\eta}_{V_t^{-1}} +\lambda^{1/2}\norm{\theta^*}}. \label{eq:32yassin32analysis321} \end{align}\tag{39}\]

We now apply Theorem 5 to bound \(\norm{X^T\eta}_{V_t^{-1}}\). Let \[\begin{align} X^T\eta = \sum_{s=1}^t x_t 1{\brc*{q_t=1}}^2 \eta_t = \sum_{s=1}^t x_t 1{\brc*{q_t=1}} \eta_t = \sum_{s=1}^t x'_t \eta_t \stackrel{\text{def}}{=}S_t, \end{align}\] where we defined \(x'_t = x_t 1{\brc*{q_t=1}}\). See that \(x'_t\) is \(F_{t-1}\) measurable since both \(x_{t}\) and \(1{\brc*{q_t=1}}\) are \(F_{t-1}\) measurable. Thus, we can apply Theorem 5 and get the following bound with probability greater than \(1-\delta\) for all \(t\geq 0\) \[\begin{align} \norm{X^T\eta}_{V_t^{-1}} \leq \sqrt{2\sigma^2 \log\br*{\frac{\text{det}\br*{V_t}^{1/2} \text{det}\br*{V}^{-1/2}}{\delta}}}. \end{align}\] Conditioning on the event this bound holds and setting \(x = V_t(\hat{\theta}_t -\theta^*)\) in 39 and using \(\norm{\theta^*}\leq D\) we get \[\begin{align} \norm{\hat{\theta}_t - \theta^*}_{V_t}^2 \leq \norm{V_t(\hat{\theta}_t - \theta^*)}_{V_t^{-1}} \br*{ \sqrt{2\sigma^2 \log\br*{\frac{\text{det}\br*{V_t}^{1/2} \text{det}\br*{V}^{-1/2}}{\delta}}} +\lambda^{1/2}D}. \end{align}\] Using \(\norm{V_t(\hat{\theta}_t - \theta^*)}_{V_t^{-1}} = \norm{\hat{\theta}_t - \theta^*}_{V_t}\) and rearranging leads to \[\begin{align} \norm{\hat{\theta}_t - \theta^*}_{V_t} \leq \sigma\sqrt{2\log\br*{\frac{\text{det}\br*{V_t}^{1/2} \text{det}\br*{V}^{-1/2}}{\delta}}} +\lambda^{1/2}D. \label{eq:32yassin32analysis322} \end{align}\tag{40}\]

To obtain the final form, we us bound the term \(\log\br*{\text{det}\br*{V_t}^{1/2} \text{det}\br*{V}^{-1/2}}.\) The trace of \(V_t\) is bounded by \(\text{trace}\br*{V} + tL^2\) since \(\norm{x_t'}\leq \norm{x_t}\leq L\). Hence, \(\text{det}\br*{V_t} = \prod_{i=1}^d \lambda_i\leq \br*{\frac{\text{trace}\br*{V} + t L^2}{d}}^d\) by the GM-AM inequality and \(\sum_{i} \lambda_i = \text{trace}\br*{V_t}\). Therefore, \[\begin{align} \log\br*{\text{det}\br*{V_t} \text{det}\br*{V}^{-1}}=\log \text{det}\br*{V_t} - d\log \lambda \leq d \log\br*{\frac{\lambda+t L^2}{d}} - d\log \lambda = d \log\br*{\frac{1+t L^2/\lambda}{d}}. \end{align}\] Plugging this back into 40 concludes the proof. ◻

Proof. The following relations hold. \[\begin{align} \max_{\theta\in C}\inner{x,\theta - \bar{\theta}} &= \max_{\theta\in C}\inner{A^{-1/2}x,A^{1/2}(\theta - \bar{\theta})}\\ &\leq \norm{x}_{A^{-1}} \max_{\theta\in C}\norm{\theta - \bar{\theta}}_{A} \\ &\leq \alpha \norm{x}_{A^{-1}} . \end{align}\] Setting \(\theta - \bar{\theta} = \frac{\alpha}{\norm{x}^2}A^{-1/2}x\) the above inequalities hold with equality (see that \(\norm{\theta - \bar{\theta}}_{A} =\alpha\) which implies that \(\theta - \bar{\theta}\in C\)). Thus, \[\begin{align} \max_{\theta\in C}\inner{x,\theta - \bar{\theta}} = \alpha \norm{x}_{A^{-1}}. \end{align}\] Lastly, since \(\norm{x}_{A^{-1}}= \norm{-x}_{A^{-1}}\) we conclude that \[\begin{align} \max_{\theta\in C}\inner{x,\bar{\theta} - \theta } = \max_{\theta\in C}\inner{-x,\theta -\bar{\theta} }= \alpha \norm{-x}_{A^{-1}} = \alpha \norm{x}_{A^{-1}}. \end{align}\] ◻