Optimistic Policy Optimization with Bandit Feedback

Introduction

Policy Optimization (PO) is among the most widely used methods in Reinforcement Learning (RL) (Peters & Schaal 2006; Peters & Schaal 2008; Deisenroth & Rasmussen 2011; Lillicrap et al. 2015; Levine et al. 2016; Gu et al. 2017). Unlike value-based approaches, e.g., Q-learning, these types of methods directly optimize the policy by incrementally changing it. Furthermore, PO methods span wide variety of popular algorithms such as policy-gradient algorithms (Sutton et al. 2000), natural policy gradient (Kakade 2002), trust region policy optimization (TRPO) (Schulman et al. 2015) and soft actor-critic (Haarnoja et al. 2018).

Due to their popularity, there is a rich literature that provides different types of theoretical guarantees for different PO methods (Scherrer & Geist 2014; Abbasi-Yadkori et al. 2019; Agarwal et al. 2019; Liu et al. 2019; Bhandari & Russo 2019; Shani et al. 2019; Wei et al. 2019) for both the approximate and tabular settings. However, previous results, concerned with regret or PAC bounds for the RL setting when the model is unknown and only bandit feedback is given, provide guarantees which critically depend on ‘concentrability coefficients’ (Kakade & Langford 2002; Munos 2003; Scherrer 2014) or on a unichain MDP assumption (Abbasi-Yadkori et al. 2019). However, these coefficients might be infinite and are usually small only for highly stochastic domains, while the unichain assumption is often very restrictive.

Preliminaries

where the expectation is with respect to the randomness of the transition function, the cost function and the policy. The $Q$-function of a policy given the state action pair $(s,a)$ at time-step $h$ is defined by

Unlike stochastic MDP, in adversarial MDP, we let the cost to be determined by an adversary at the beginning of every episode, whereas the transition function is fixed. Thus, we denote the MDP at the $k$-th episode by ${\mathcal{M}}^{k}=({\mathcal{S}},{\mathcal{A}},H,\{p_{h}\}_{h=1}^{H},\{c^{k}_{h}\}_{h=1}^{H})$. As in (2.1), (2.2), we define the value function and $Q$-function of a policy $\pi$ at the $k$-th episode by

Notably, $V_{h}^{k,\pi}$ and $Q_{h}^{k,\pi}$ satisfy the relations in relation (2.3).

where $t_{K}$ is a stepsize. In our case, $C$ is the unit simplex $\Delta$, and thus the optimization problem has a closed-form solution,

The MD algorithm ensures $\text{Regret}(K^{\prime})=\sum_{k=1}^{K^{\prime}}f(x_{k})-\min_{x}f(x)\in O(\sqrt{K})$ for all $K^{\prime}\in[K]$.

Related Work

A large body of work addresses the convergence properties of policy optimization algorithms from an optimization perspective. In Kakade & Langford 2002, the authors analyzed the Conservative Policy Iteration (CPI) algorithm, an RL variant of the Frank-Wolfe algorithm (Scherrer & Geist 2014; Vieillard et al. 2019), and showed it approximately converges to the global optimal solution. Recently, Liu et al. 2019 established the convergence of TRPO when neural networks are being used as the function approximators. Furthermore, Shani et al. 2019 showed that TRPO (Schulman et al. 2015) is in fact a natural RL adaptation of the MD algorithm, and established convergence guarantees. In (Agarwal et al. 2019), the authors obtained convergence results for policy gradient based algorithms. However, all of the aforementioned works rely on the strong assumption of a finite concentrability coefficient, i.e., $\max_{\pi,s,h}d_{h}^{\pi^{*}}(s;p)/d_{h}^{\pi}(s;p)<\infty$ . This assumption bypasses the need to address exploration (Kakade & Langford 2002), and leads to global guarantees based on the local nature of the policy gradients (Scherrer & Geist 2014).

There are two different methodologies for using MD updates in RL. The first and more practical one, is using MD-like updates directly on the policy. The second is based on optimizing over the space of state-action occupancy measures, that is, visitation frequencies for state-action pairs. An occupancy measure represents a policy implicitly. For convenience, previous results for regret minimization using MD approaches are summarized in Table 1.

As opposed to Policy-based methods, there is an extensive literature about regret minimization in episodic MDPs using value-based methods. The works of (Azar et al. 2017; Dann et al. 2017; Jin et al. 2018; Zanette & Brunskill 2019; Efroni et al. 2019) use the optimism in face of uncertainty principle to achieve near-optimal regret bounds. Jin et al. 2018 also establish a lower bound of $\Omega(\sqrt{SAH^{3}K})$.

Mirror Descent for MDPs

The empirical success of TRPO (Schulman et al. 2015) and SAC (Haarnoja et al. 2018) had motivated recent study of MD-like update rules for solving MDPs (Geist et al. 2019) when the model of the environment is known. Although not explicitly discussed in (Geist et al. 2019), such an algorithm can also provide guarantees – by similar proof technique – for the case where the cost function is adversarially chosen on each episode.

Policy Optimization by Mirror Descent (POMD) (see Algorithm 1) is conceptually similar to the Policy Iteration (PI) algorithm (Puterman 2014). It alternates between two stages: (i) policy evaluation, and (ii) policy improvement. Furthermore, much alike PI, POMD updates its policy on the entire state space, given the evaluated $Q$-function. However, as oppose to PI, the policy improvement stage is ‘soft’. Instead of updating according to the greedy policy, the algorithm applies soft update that keeps the next policy ‘close’ to the current one due to the KL-divergence term.

Extended Value Difference Lemma

The analysis of both stochastic and adversarial cases is built upon a central lemma which we now review. The lemma is a variant of (Cai et al. 2019)[Lemma 4.2], which generalizes classical value difference lemmas. Rewriting it in the following form, enables us to establish our results (proof in Appendix D).

Let $\pi,\pi^{\prime}$ be two policies, and ${\mathcal{M}}=(\sset,\aset,\left\{p_{h}\right\}_{h=1}^{H},\left\{c_{h}\right\}_{h=1}^{H})$ and ${\mathcal{M}}^{\prime}=(\sset,\aset,\left\{p^{\prime}_{h}\right\}_{h=1}^{H},\left\{c^{\prime}_{h}\right\}_{h=1}^{H})$ be two MDPs. Let $\hat{Q}_{h}^{\pi,{\mathcal{M}}}(s,a)$ be an approximation of the $Q$-function of policy $\pi$ on the MDP ${\mathcal{M}}$ for all $h,s,a$, and let ${\hat{V}_{h}^{\pi,{\mathcal{M}}}(s)=\left\langle\hat{Q}_{h}^{\pi,{\mathcal{M}}}(s,\cdot),\pi_{h}(\cdot\mid s)\right\rangle}$. Then,

where $V_{1}^{\pi^{\prime},{\mathcal{M}}^{\prime}}$ is the value function of $\pi^{\prime}$ in the MDP ${\mathcal{M}}^{\prime}$.

This lemma generalizes existing value difference lemmas. For example, in (Kearns & Singh 2002; Dann et al. 2017) the term ${V_{1}^{\pi,{\mathcal{M}}}(s)-V_{1}^{\pi,{\mathcal{M}}^{\prime}}(s)}$ is analyzed, whereas in (Kakade & Langford 2002) the term ${V_{1}^{\pi,{\mathcal{M}}}(s)-V_{1}^{\pi^{\prime},{\mathcal{M}}}(s)}$ is analyzed. In next sections, we will demonstrate how Lemma 1 results in a simple analysis of the POMD algorithm. Importantly, the resulting regret bounds do not depend on concentrability coefficients (see Section 3) nor on any other structural assumptions.

Policy Optimization in Stochastic MDPs

We are now ready to analyze the optimistic version of POMD for stochastic environments (see Algorithm 2). Instead of using the known model as in POMD, in Algorithm 2 we use the empirical model to estimate the $Q$-function of an empirical optimistic MDP, with the empirical transition function $\bar{p}$ and an optimistic cost function $\hat{c}$. The empirical transition function $\bar{p}$ and empirical cost function $\bar{c}$ are computed by averaging the observed transitions and costs, respectively, that is,

The optimistic cost function $\hat{c}$ is obtained by adding a bonus term which drives the algorithm to explore, i.e., $\hat{c}_{h}^{k-1}(s,a)=\bar{c}_{h}^{k-1}(s,a)-b_{h}^{k-1}(s,a)$, and we set

The two bonus terms compensate on the lack of knowledge of the true costs and transition model, and are

The following theorem bounds the regret of Algorithm 2. A full proof is found in Appendix B.2.

We start by decomposing the regret into three terms according to Lemma 1, and then bound each term separately to get our final regret bound. For any $\pi$,

Here $\Delta c^{k-1}_{h}(s,a)=c_{h}(s,a)-\bar{c}^{k-1}_{h}(s,a)$ and $\Delta p^{k-1}_{h}(\cdot\mid s,a)=p_{h}(\cdot\mid s,a)-\bar{p}^{k-1}_{h}(\cdot\mid s,a)$, are the differences between the true cost and transition model to the empirical cost and transition model. Applying Hoeffding’s bound and $L_{1}$ deviation bound (Weissman et al. 2003) we get that w.h.p. for any $s,a$

Term (ii) is the linear approximation used in MD optimization procedure. We bound it using an analysis of OMD. By applying usual OMD analysis (see Lemma 16) we have that for any policy $\pi$ and $s,h$,

We plug this back to Term (ii) and use the fact that $0\leq Q_{h}^{k}(s,a)\leq H$, to obtain

By choosing $t_{K}=\sqrt{2\log A/(H^{2}K)}$, we obtain $\text{Term (ii)}\leq\sqrt{2H^{4}K\log A}.$

The choice of the bonus term $b_{h}^{p,k}(s,a)$ is smaller than in (Cai et al. 2019) by a factor of $\sqrt{S}$. This translates to an improved regret bound by this factor, although (Cai et al. 2019) assumes full-information feedback on the cost function.

Unlike value-based algorithms (e.g., Jaksch et al. 2010) $V^{k}$, the value-function by which POMD improves upon, is not necessarily optimistic relatively to $V^{*}$. Instead, it is optimistic relatively to the value of $\pi_{k}$, i.e., $V^{k}\leq V^{\pi_{k}}$.

Policy Optimization in Adversarial MDPs

In this section, we turn to analyze an optimistic version of POMD for adversarial environments (Algorithm 3). Similarly to the stochastic case, Algorithm 3 follows the POMD scheme, and alternates between policy evaluation, and, soft policy improvement, based on MD-like updates.

Unlike POMD for stochastic environments, the policy evaluation stage of Algorithm 3 uses different estimates of the instantaneous cost and model. The instantaneous cost is evaluated by a biased importance-sampling estimator, originally suggested by (Neu 2015), and recently generalized to adversarial RL settings by (Jin et al. 2019),

Here $\mathcal{P}^{k-1}$ is the set of transition functions obtained by using confidence intervals around the empirical model (see Appendix C.1.2).

Instead of using the empirical model and subtracting a bonus term, Algorithm 3 uses an optimistic model (Jaksch et al. 2010) for the policy evaluation stage. The model by which $Q^{k}$ is evaluated is the one which results in the smallest loss among possible models,

The solution to this optimization problem can be computed efficiently (see, e.g., Jaksch et al. 2010).

The following theorem bounds the regret of Algorithm 3. A full proof is found in Appendix C.2.

Central to the analysis are the following claims, formally established in Appendix C. The first is proved in (Jin et al. 2019)[Lemma 11], based upon (Neu 2015)[Lemma 1].

However, a tighter upper bound can be obtained by applying Claim 2 with $\alpha^{k}=2\gamma$ for all $k\in[K^{\prime}]$. We have that

where in the last relation we used the fact that for any $s,h$, $V^{\pi_{k}}_{h}(s)\leq H$. In the following proof sketch we apply the later upper bound and demonstrate its importance.

We decompose the regret as in Theorem 1 to (i) Bias term, (ii) OMD term, and (iii) Optimism term. We bound both the Bias and Optimism terms in the appendix while relying on both Claim 1 and Claim 2.

Similarly to the stochastic case, we utilize the usual OMD analysis (Lemma 16), which ensures that for any policy $\pi$ and $s,h$,

where the second relation holds since $0\leq Q_{h}^{k}(s,a)\leq\frac{H}{\gamma}$, and the third relation holds by applying Eq. (7.3). Plugging this in Term (ii) we get

Discussion

There are two prevalent approaches for policy optimization in practice, on-policy and off-policy. On-policy algorithms, e.g., TRPO (Schulman et al. 2015), update the policy based on data gathered following the current policy. This results in updating the policy only in observed states. However, in terms of theoretical guarantees, the convergence analysis of this approach requires the strong assumption of finite concentrability coefficient (Kakade & Langford 2002; Scherrer & Geist 2014; Agarwal et al. 2019; Liu et al. 2019; Shani et al. 2019). The assumption arises from the need to acquire global guarantees from the local nature of policy gradients.

The approach taken in this work, is fundamentally different than such on-policy approaches. In each episode, instead of updating the policy only at visited states, the policy is updated over the entire state space, by using all the historical data (in the form of the empirical model). Thus, the analyzed approach bears resemblance to off-policy algorithms, e.g., SAC (Haarnoja et al. 2018). There, the authors i) estimate the $Q$-function of the current policy by sampling from a buffer, which contains historical data, and ii) apply an MD-like policy update to states sampled from the buffer.

The uniform updates of policy-based methods analyzed in this work are in stark contrast to value-based algorithms, such as in (Jin et al. 2018; Efroni et al. 2019), where only observed states are updated. It remains an important open question, whether such updates could also be implemented in a provable policy based algorithm. In the case of stochastic POMD, this may be achieved by using optimistic $Q$-function estimates, instead of estimating the model with UCB-bonus, similarly to (Jin et al. 2019). There, the authors keep the estimates optimistic with respect to the optimal $Q$-function, $Q^{*}$. However, in approximate policy optimization, the policy improvement is done with respect to $Q^{\pi_{k}}$, as described in Algorithm 1. Therefore, differently than in (Jin et al. 2019), such off-policy version would require learning an optimistic $Q^{\pi_{k}}$ estimator, instead of $Q^{*}$.

In our work, we proposed algorithms which directly optimize the policy. In this scenario, the policy is updated independently at each time step $h$ and state $s$. That is, an optimization problem is solved over the action space in each $h,s$. Therefore, this method requires solving $HS$ optimization problems of size $A$, where each has a closed form solution in the tabular setting.

Alternatively, algorithms based on the O-REPS framework (Zimin & Neu 2013), follow a different approach and optimize over the state-action occupancy measures instead of directly on policies. In the case of unknown transition model, taking such an approach requires solving a constrained convex optimization problem, later relaxed to a convex optimization problem with only non-negativity constraints (Rosenberg & Mansour 2019b) of size $HS^{2}A$, in each episode. Unlike the policy optimization approach, this optimization problem does not have a closed form solution. Thus, the computational cost of optimizing over the state-action occupancy measures is much worse than the policy optimization one.

Another significant shortcoming in applying the O-REPS framework is the difficulty to scale it to the function approximation setting. Specifically, in case the state-action occupancy measure is represented by a non-linear function, it is unclear how to solve the constrained optimization problem as defined in (Rosenberg & Mansour 2019b). Differently than the O-REPS framework, the policy optimization approach scales naturally to the function approximation setting, e.g., Haarnoja et al. 2018. In this important aspect, policy optimization is preferable.

Acknowledgments

We thank the anonymous reviewers for providing us with very helpful comments.

References

Appendix A Additional Notation

We denote, $\bar{c}$ and $\bar{p}$, the empirical estimators for $c,p$ respectively. In the adversarial case, we denote $\hat{c}$ as the importance sampling estimator for the costs and $\hat{p}$ as the optimistic model. When referring to the estimated MDP, we always denote $\hat{\mathcal{M}}$, regardless of the estimation method. When using the notation $Q_{h}^{\pi,p,c}$ and $V_{h}^{\pi,p,c}$, for some policy $\pi$, transition model $p$ and costs $c$, we refer to the expected Q-function and value function at the $h$-th step, of following the policy $\pi$ on the MDP defined by the transitions $p$ and costs $c$.

Appendix B Stochastic MDPs

First, we restate here Algorithm 2 for readability:

In the stochastic case, we use the empirical model:

The bonus term in Algorithm 2 is made of a bonus term dedicated to the uncertainty in the rewards and a second term dedicated to the uncertainty in the transition model (see (6.1)),

We choose the additive bonus terms as follows (this choice is guided by the need to keep the term in Lemma 5 negative):

For any $k,h,s,a$, $Q_{h}^{k}(s,a)\in[0,H]$ and $V_{h}^{k}(s)\in[0,H]$. To see that, first note that by the update rule, we have that for any $k,h,s,a$, $Q_{h}^{k}(s,a)\geq 0$. Moreover, using negative bonuses, $Q_{h}^{k}$ is always smaller than $Q_{h}^{\pi_{k},\bar{p},\bar{c}}$. Therefore, it is always upper bounded by $H$.

In the next section, B.1, we deal with all the failure events that can happen while running algorithm 2, and show that they happen with small probability. Then, in section B.2, we prove Theorem 1 which establishes the convergence of Algorithm 2.

Furthermore, the following relations hold.

Let $F^{c}=\bigcup_{k=1}^{K}F^{c}_{k}.$ Then $\Pr\left\{F^{c}\right\}\leq\delta^{\prime}$, by Hoeffding’s inequality, and using a union bound argument on all $s,a$, and all possible values of $n_{k}(s,a)$ and $k$. Furthermore, for $n(s,a)=0$ the bound holds trivially since $C\in$.

Let $F^{P}=\bigcup_{k=1}^{K}F^{p}_{k}.$ Then $\Pr\left\{F^{p}\right\}\leq\delta^{\prime}$, holds by (Weissman et al. 2003) while applying union bound on all $s,a$, and all possible values of $n_{k}(s,a)$ and $k$. Furthermore, for $n(s,a)=0$ the bound holds trivially.

Let $F^{N}=\bigcup_{k=1}^{K}F^{N}_{k}.$ Then, $\Pr\left\{F^{N}\right\}\leq\delta^{\prime}$. The proof is given in (Dann et al. 2017) Corollary E.4.

Setting $\delta^{\prime}=\frac{\delta}{3}$ then $\Pr\{F^{c}\bigcup F^{p}\bigcup F^{N}\}\leq\delta$. When the failure events does not hold we say the algorithm is outside the failure event, or inside the good event $G$.

B.2 Regret Analysis - Proof of Theorem 1

By conditioning our analysis on the good event which was formalized in the previous section (see Lemma 2), we are ready to prove the following theorem, which establishes the convergence of Algorithm 2.

First, we decompose the regret in the following way,

where the second relation holds by using the extended value difference lemma (Lemma 1).

By applying Lemmas 3, 4 and 5 to bound each of the above three terms, respectively, we get that conditioned on the good event, for any $K^{\prime}\in[K]$ and any $\pi$

In what follows we will analyze the each of the three terms separately: Term $(i)$ is a bias term between the value of the current policy and the estimation of that value, which we bound in Lemma 3. Term $(ii)$ is the linear approximation term used in the OMD optimization problem. This term will be bounded by the OMD analysis (see Lemma 4). Term $(iii)$ is an optimism term. It represents the error of our $Q$-function estimation w.r.t. to the $Q$-function obtained by having the real model, and thus, applying the true 1-step Bellman operator. By the optimistic nature of our estimators, this term is negative given the good event (see Lemma 5).

Conditioned on the good event, we have that

By the extended value diffrence lemma (Lemma 1), we get

where the second relation follows from the update rule of $Q_{h+1}^{k}$.

where the second relation is by the definition of minimum between two terms.

Conditioning on the good event, we have that for any $(h,k,s,a)$

See that the second relation is by the Cauchy-Schwartz inequality. The third is by the fact that for any $k,h,s$, $0\leq V_{h}^{k}(s)\leq H$. the last relation holds conditioned on the good event.

Plugging (B.3), (B.4) into (B.2) and then back to (B.1) we get

where in the fourth relation we used the fact that the expectations are equivalent, since at the $k$-th episode we follow the policy $\pi_{k}$ in the MDP $\mathcal{M}$.

This term accounts for the optimization error, bounded by the OMD analysis.

By standard analysis of OMD with the KL divergence used as the Bregman distance (see Lemma 17) we have that for any $h\in[H],s\in\sset$ and for policy $\pi$,

By the fact $0\leq Q_{h}^{k}(s,a)\leq H$ (see Remark B.1), we have

See that the first relation holds as the expectation does not depend on $k$. Thus, by linearity of expectation, we can switch the order of summation and expectation. The second relation holds since (B.5) holds for any $s$.

Finally, by choosing $t_{K}=\sqrt{2\log A/(H^{2}K)}$, we obtain

Conditioned on the good event, we have that for any $\pi$

Now, by the fact that for any $a,b$, $\max\left\{a+b,0\right\}\leq\max\left\{a,0\right\}+\max\left\{b,0\right\}$, we have that

Conditioned on the good event, we have that for any $(k,h,s,a)$,

The first relation holds by Holder’s inequality. The second relation holds by the updating rule, which keeps $0\leq V_{h+1}^{\pi_{k},\hat{P},\hat{c}}\leq H$ (see Remark B.1). The third relation holds conditioning on the good event.

Appendix C Adversarial MDPs

First, we restate here Algorithm 3 for readability:

We define the costs of the online MDP at the $k$-th episode, for each $h\in[H],s\in\sset,a\in\aset$, and for any $\pi_{h}^{k}$

We also define the following optimistic model, $\hat{p}_{h}^{k}(\cdot\mid s,a)$, which is the solution to the following optimization problem:

where ${\mathcal{P}}_{h}^{k}(s,a)$ is defined in (C.3) Finally, as for the stochastic case, we denote the empirical estimator of the transition function as

For any $k,h,s,a$, $Q_{h}^{k}(s,a)\in[0,H/\gamma]$ and $V_{h}^{k}(s)\in[0,H/\gamma]$. To see that, first note that $\hat{c}_{h}^{k}(s,a)\in[0,1/\gamma]$. By the fact that the estimators for the Q-function and value function are always calculated w.r.t. to some transition model $\hat{p}$, we get that the estimators are bounded as suggested.

The following lemmas, Lemma 6 and Lemma 7, will be essential to establish regret bounds for Algorithm 3. In the main body of the paper, we refer to these lemmas as claim 1 and claim 2, respectively. Lemma 6 is a very close adaptation of (Jin et al. 2019)[Lemma 11], which in itself based on (Neu 2015)[Lemma 1]. Lemma 7 relies upon applying Lemma 6.

Let $\alpha^{1},...,\alpha^{K}$ be a sequence of functions, such that $\alpha^{k}\in[0,2\gamma]^{S\times A}$ is $\mathcal{F}_{k-1}$-measurable for all $k$. Let $u_{h}^{k}(s)>0$ for any $k,h,s$. Then, With probability of at least $1-\delta$, for any $h\in[H]$,

The full proof of Lemma 6 is given in section E.

Let $\alpha^{1},...,\alpha^{K}$ be a sequence of functions, such that $\alpha^{k}\in$ is $\mathcal{F}_{k-1}$-measurable for all $k$. Furthermore, assume that for all $k,h,s$ $u_{h}^{k}(s)>d_{h}^{k}(s)\geq 0$. Then, with probability of at least $1-\delta$, for any fixed $h\in[H]$ and $s\in\sset$,

where $V_{h}^{\pi_{k},p,\hat{c}}$ is the value of following the policy $\pi_{k}$ at the $h$-th step, on the MDP defined by the transitions $p$ and costs $\hat{c}$ (as defined in Appendix A).

The first relation holds by Corollary 1, as both value functions are measured w.r.t. the same dynamics and are defined over the same policy. The second relation holds by the fact $c_{h}^{k}(s,a)\geq 0$ and by the fact that by the assumptions of the lemma, for any $h,k,s$, $d_{h}^{k}(s)\leq u_{h}^{k}(s)$.

Now, observe that $\Pr(s_{h^{\prime}},a_{h^{\prime}}\mid s_{h}=s,\pi_{k},p)\in$ and are measurable functions w.r.t. $\mathcal{F}_{k-1}$. For any $h^{\prime}\in\left\{h,..,H\right\}$ we set $\alpha_{h^{\prime}}^{k}(s_{h^{\prime}},a_{h^{\prime}})=2\gamma\alpha^{k}\Pr(s_{h^{\prime}},a_{h^{\prime}}\mid s_{h}=s,\pi_{k},p)$ where $\alpha_{h^{\prime}}^{k}(s_{h^{\prime}},a_{h^{\prime}})\in[0,2\gamma]$. By this definition we have that

For any $h^{\prime}\in\left\{h,..,H\right\}$ we apply Lemma 6, take a union bound and bound $H-h\leq H$ to get

In this section we define the high probability bounds which are later in use in the proof of Theorem 2. We divide the failure event into two different kinds of failure event: basic failure events which are independent on each other, and conditioned failure event which holds conditioned on the basic failure event.

The next sections are ordered in the following way: we first define the basic failure event and the resulting basic good event. Then, we describe the consequences of this basic good event. Finally, we describe the conditioned failure events, which rely on the consequences of the basic good event. By combining all failure events, we define the global failure event. In the proof, we condition our analysis on the event the global failure event does not hold. We also refer to this event as the good event.

Furthermore, the following relations hold.

Let $F^{p}=\bigcup_{k=1}^{K}F_{k}^{p}$. Then, $\Pr\left\{F^{p}\right\}\leq\delta^{\prime}$, by (Maurer & Pontil 2009, Theorem 4) and union bounds.

Let $F^{N}=\bigcup_{k=1}^{K}F^{N}_{k}.$ Then, $\Pr\left\{F^{N}\right\}\leq\delta^{\prime}$. The proof is given in (Dann et al. 2017) Corollary E.4.

by Lemma 6 w.p. $1-\delta^{\prime\prime}$ for any $h$. Taking union bound on $s,a$ and setting $\delta^{\prime\prime}=\frac{\delta^{\prime}}{SAK}$, we get that $\Pr\left\{F_{k^{\prime}}^{c}\right\}\leq\frac{\delta^{\prime}}{K}$. Finally, let $F^{c}=\bigcup_{k^{\prime}=1}^{K}F_{k^{\prime}}^{c}$. By union bound, $\Pr\left\{F^{c}\right\}\leq\delta^{\prime}.$

Finally, setting $\delta^{\prime}=\frac{\delta}{6}$, and denote $F^{\text{basic}}:=F^{p}\bigcup F^{N}\bigcup F^{c}$. Then, by union bound $\Pr\{F^{\text{basic}}\}\leq\frac{\delta}{2}$.

Denote $G^{\text{basic}}:=\neg F^{\text{basic}}$, then $Pr\{G^{\text{basic}}\}\geq 1-\frac{\delta}{2}$. When $G^{\text{basic}}$ occurs, we say that the basic good event holds.

C.1.2 Consequences Conditioning on the Basic Good event

First, for any $k,h,s,a$, we define the set

By using this definition conditioned on the basic good event, we get the following lemma from (Jin et al. 2019)[Lemma 8],

Conditioned on the basic good event, for all $k,h,s,a,s^{\prime}$ and for all $\hat{p}_{h}^{k}(\cdot\mid s,a)\in{\mathcal{P}}_{h}^{k-1}(s,a)$, there exists constants $C_{1},C_{2}>0$ for which we have that

Conditioned on the basic good event, for any $(s,a)\in\mathcal{S}\times\mathcal{A}$, $h\in[H],k\in[K]$

where $V_{h}^{\pi_{k},p,\hat{c}}$ is defined in Appendix A.

By the description of the algorithm, for each value, we solve the following minimization problem, for any $k,h,s,a$

Therefore, by conditioning on the good event and by lemma 9, for any $k,h,s,a$ the following holds

Now, note that for $h=H$ using the fact that $V_{H+1}^{k}=0$ for any $k,s$, we obtain,

and therefore, for any $k,s$ and policy $\pi_{k}$

Using the above inequality, by backward recursion on $h=H,H-1,...,1$ on (C.6), we get for any $k,h,s,a$

where in the second inequality we used the fact that $p_{h}$, $V_{h+1}^{k}$ and $V_{h+1}^{\pi_{k},p,\hat{c}}$ are all non-negative.

C.1.3 Conditioned failure events

Fix $h$ and let $\delta^{\prime}>0$. Conditioning on the the basic good event $G^{\text{basic}}$ for any $k,h$,

where we conditioned on the event $G^{\text{basic}}$ in which $d_{h}^{k}(s)\leq u_{h}^{k}(s)$, Therefore, $\sum_{s}\sum_{a}d_{h}^{k}(s)\pi_{h}^{k}(a\mid s)\hat{c}_{h}^{k}(s,a)\in$. Furthermore, observe

is a martingale-difference sequence. Thus, by Azuma-Hoeffding and taking union bound for all $H$, we have that for any $K$, $Pr\left\{F^{\hat{c}}\mid\neg F^{\text{basic}}\right\}\leq\delta^{\prime\prime}=\frac{\delta^{\prime}}{H}$.

Fix $k^{\prime}\in[K],h,s$ and let $\delta^{\prime\prime}>0$. Now, set for any $k\in[k^{\prime}]$, $\alpha^{k}=1\in$ (constant and thus measurable). Furthermore, conditioned on the basic good event, we have that for any $k,h,s$, $u_{h}^{k}(s)>d_{h}^{k}(s)\geq 0$. Thus, by applying Lemma 7, we get that w.p. $1-\delta^{\prime\prime}$

Now, conditioned on the basic good event, by Lemma 10 we have

Taking union bounds on $h,s$ and setting $\delta^{\prime\prime}=\frac{\delta^{\prime}}{HSK}$, we get that $\Pr\left\{F_{k^{\prime}}^{v,MD}\right\}\leq\frac{\delta^{\prime}}{K}$. Finally, let $F^{v,MD}=\bigcup_{k^{\prime}=1}^{K}F_{k^{\prime}}^{v,MD}$. By union bound, $\Pr\left\{F^{v,MD}\right\}\leq\delta^{\prime}.$

Fix $k^{\prime}\in[K],s,a,s^{\prime},h$ and let $\delta^{\prime\prime}>0$. Now, set for any $k\in[k^{\prime}]$,

and note that it is $\mathcal{F}_{k-1}$-measurable. Furthermore, conditioned on the basic good event, we have that for any $k,h,s$, $u_{h}^{k}(s)>d_{h}^{k}(s)\geq 0$. Thus, by applying Lemma 7, we get that w.p. $1-\delta^{\prime\prime}$, for any fixed $s^{\prime}$

Now, conditioned on the basic good event, by Lemma 10 we have

w.p. $1-\delta^{\prime\prime}$. Taking union bound on $s^{\prime},h$ and setting $\delta^{\prime\prime}=\frac{\delta^{\prime}}{SHK}$, we get that w.p. $1-\frac{\delta^{\prime}}{K}$

or in other words, $\Pr\left\{F_{k^{\prime}}^{v,1}\right\}\leq\frac{\delta^{\prime}}{K}$. Finally, let $F^{v,1}=\bigcup_{k^{\prime}=1}^{K}F_{k^{\prime}}^{v,1}$. By union bound, $\Pr\left\{F^{v,1}\right\}\leq\delta^{\prime}.$

By following the same proof of event $F^{v,1}$ (i.e., by applying Lemma 7), but using $\alpha^{k}(s^{\prime})=\sum_{s,a}\frac{\Pr(s_{h}=s,a_{h}=a\mid s_{1},\pi_{k},p)}{(n_{h}^{k-1}(s_{h},a_{h})-1)\vee 1}\in$ for any $s^{\prime}$, we get that $\Pr\left\{F^{v,2}\right\}\leq\delta^{\prime}$.

Now, denote the conditioned event, $F^{\text{conditioned}}:=F^{\hat{c}}\bigcup F^{v,MD}\bigcup F^{v,1}\bigcup F^{v,2}$.

Next, we set $\delta^{\prime}=\frac{\delta}{8}$. Then, by union bound $\Pr\{F^{\text{conditioned}}\mid\neg F^{\text{basic}}\}\leq\frac{\delta}{2}$.

Denote $G^{\text{conditioned}}:=\neg F^{\text{conditioned}}$, then $\Pr\{G^{\text{conditioned}}\mid G^{\text{basic}}\}\geq 1-\frac{\delta}{2}$.

C.1.4 Global Failure Events

In this section, we combine both the basic and conditioned failure events into a single global failure event. The global failure event accounts for all failure events which can occur in the adversarial MDP case. Specifically, in our analysis we will always assume that none of the failure events occurs, which happens with probability of at least $1-\delta$ since

where we used the facts that $\Pr\{\neg F^{\text{basic}}\}\geq 1-\frac{\delta}{2}$ by Lemma 8, and $\Pr\{\neg F^{\text{conditioned}}\mid\neg F^{\text{basic}}\}\geq 1-\frac{\delta}{2}$ by Lemma 11.

Denote $G:=G^{\text{conditioned}}\bigcap G^{\text{basic}}=\neg F^{\text{conditioned}}\bigcap\neg F^{\text{basic}}$, then $Pr\{G\}\geq 1-\delta$. When $G$ occurs, we say the algorithm outside the failure event or inside the good event.

C.2 Regret Analysis - Proof of Theorem 2

By conditioning our analysis on the good event which was formalized in the previous sections (see Lemma 12), we are ready to prove the following theorem, which establishes the convergence of Algorithm 3.

First, we decompose the regret in the following way

where the second relation holds by using the extended value difference lemma (Lemma 1).

By applying Lemmas 13, 14 and 15 to bound each of the above three terms, respectively, we get that conditioned on the good event (see Lemma 12), for any $K^{\prime}\in[K]$,

The decomposition in the proof of Theorem 2 is the same as in the stochastic case. The analysis is different here due the different nature of the estimators for the costs and transition model. Again, term $(i)$ is a bias term between the value of the current policy and the estimation of that value, which is bounded in Lemma 13. Term $(ii)$ is the linear approximation term used in the OMD optimization problem. This term will be bounded by the OMD analysis (see Lemma 14). Term $(iii)$ is an optimism term. It represents the error of our $Q$-function estimation w.r.t. to the $Q$-function obtained by having the real model, and thus, applying the true 1-step Bellman operator. By the optimistic nature of our estimators, this term is (almost) negative given the good event (see Lemma 15).

First, by Lemma 1, the following relations hold,

By plugging back to the first term of (C.7),

First, we deal with the first term in (C.8),

where in the inequality we use the fact that by conditioning on the good event, for any $k,h,s$, $d_{h}^{k}(s)\leq u_{h}^{k}(s)$, and therefore for any $k,h,s,a$, $\frac{d_{h}^{k}(s)\pi_{h}^{k}(a\mid s)}{u_{h}^{k}(s)\pi_{h}^{k}(a\mid s)+\gamma}\leq 1$

As for the second term in (C.8), conditioning on the good event we have that

where the last relation follows from Lemma 20.

Now, its left to address the second term of (C.7). Consider the following,

The second transition is by the fact $V_{h}^{k}$ is positive and by the conditioning on the good event and applying Lemma 9. The third transition is by the fact for any $k,h,s,a$, $n_{h}^{k-1}(s,a)\leq n_{h}^{k-1}(s,a)$.

First, we deal with the first term. Conditioning on the good event, we have for any $(k,s,a,h)$

In the first transition we used the fact that $V_{h}^{\pi_{k}}$ is positive and bounded by $H$ for any $k,h,s^{\prime}$. The second transition is by Jensen’s inequality and the fact that the square root is concave.

Note that in the first relation we used the fact that the expectations are equivalent, since at the $k$-th episode we follow the policy $\pi_{k}$ in the MDP $\mathcal{M}$. The third relation holds by the fact that for any $n\geq 0$, it holds that $\frac{1}{(n-1)\vee 1}\leq\frac{2}{n\vee 1}$.

Finally, applying Lemma 19 and Lemma 18 and excluding constant and logarithmic factors in $K$, we get

Next, conditioned on the good event, and specifically on events $F^{v,1},F^{v,2}$ we have that

Finally, by combining the bounds, we get that

The result holds by combining the two above terms.

Conditioned on the good event, for any $pi$,

This term accounts for the optimization error, bounded by the OMD analysis when the KL-divergence is used as the Bregman divergence.

By Lemma 17, we have that for any $h\in[H],s\in\sset$ and for policy $\pi$,

Now, conditioning on the good event, the following holds,

Note that the second relation holds by $(a+b)^{2}\leq 2a^{2}+2b^{2}$. The third relation is by the fact that both terms are bounded by $\frac{H}{\gamma}$. The fourth relation is by the definition of the update rule.

Plugging this into (C.14) we get for any $s\in\mathcal{S},h\in[H]$

The second relation holds by definition. The third relation holds by conditioning on the good event, specifically, event $F^{v,MD}$. The fourth relation holds since the value function of the true MDP is bounded by $H$.

Conditioned on the good event, for any $\pi$,

We shall prove that, conditioned on the good event,

We have that for any $s,a,h$, conditioning on the good event

where we used that fact that conditioned on the good event, $0\leq d_{h}^{k}(s)<u_{h}^{k}(s)$ for any $k,h,s$.

since $p_{h}(\cdot\mid s,a)\in\mathcal{P}_{h}^{k}(s,a)$ conditioning on the good event.

The result follows by combining the two above terms

Appendix D Difference Lemmas

The following lemma is similar to the analysis of the first term, in (Cai et al. 2019)[Lemma 4.2]. See 1

For any two policies $\pi,\pi^{\prime}$, and for any $h$ and $s$, by the definition $\hat{V}_{h}^{\pi,{\mathcal{M}}}(s)=\left\langle\hat{Q}_{h}^{\pi,{\mathcal{M}}}(s,\cdot),\pi_{h}(\cdot\mid s)\right\rangle$ and by the definition of $V_{h}^{\pi^{\prime},{\mathcal{M}}^{\prime}},Q_{h}^{\pi^{\prime},{\mathcal{M}}^{\prime}}$,

where in the last relation we used the fixed-policy Bellman equation on the MDP ${\mathcal{M}}^{\prime}$. I.e., for any $s,a$, we have that $Q_{h}^{\pi^{\prime},{\mathcal{M}}^{\prime}}(s,a)=c^{\prime}_{h}(s,a)+\sum_{s^{\prime}}p^{\prime}_{h}(s^{\prime}\mid s,a)V_{h+1}^{\pi^{\prime},{\mathcal{M}}^{\prime}}(s^{\prime})$.

Now, by adding and subtracting $\sum_{s^{\prime}}p^{\prime}_{h}(s^{\prime}\mid s,\cdot)\left(\hat{V}_{h+1}^{\pi,{\mathcal{M}}}(s^{\prime}),\pi^{\prime}_{h}(\cdot\mid s)\right)$, we get

By using the above relation recursively, we obtain,

By using the fact that for any policy $H$-horizon MDP ${\mathcal{M}}$ and for any policy $\pi$ and state $s$, $\hat{V}_{H+1}^{\pi,{\mathcal{M}}}(s)=0$, we get

By replacing the approximation in the last lemma with the real expected value, we get the following well known result:

Let ${\mathcal{M}},{\mathcal{M}}^{\prime}$ be any $H$-finite horizon MDP. Then, for any two policies $\pi,\pi^{\prime}$, the following holds

Appendix E Useful Lemmas

In each iteration of Online Mirror Descent (OMD), the following problem is solved:

The following lemma, (Orabona 2019)[Theorem 10.4], provides a fundamental inequality which will be used in our analysis.

Assume for $g_{k,i}\geq 0$ for $k=1,...,K$ and $i=1,...,d$. Let $C=\Delta_{d}$ and $\eta>0$. Using OMD with the KL-divergence, learning rate $t_{K}$, and with uniform initialization, $x_{1}=[1/d,...,1/d]$, the following holds for any $u\in\Delta_{d}$,

In our analysis, we will be solving the OMD problem for each time-step $h$ and state $s$ separately,

Therefore, by adapting the above lemma to our notation, we get the following lemma,

Let $t_{K}>0$. Let $\pi_{h}^{1}(\cdot\mid s)$ be the uniform distribution for any $h\in[H]$ and $s\in\sset$. Then, by solving (E.2) separately for any $k\in[K],h\in[H]$ and $s\in\sset$, the following holds for any stationary policy $\pi$,

First, observe that for any $k,h,s$, we solve the optimization problem defined in (E.2) which is the same as (E.1). By the fact that the estimators used in our analysis are non-negative, we can apply Lemma 16 separately for each $h,s$ with $g_{k}=Q_{h}^{k}(s,\cdot)$ and $x_{k}=\pi_{h}^{k}(s,\cdot)$. ∎

E.2 Bounds on the Visitation Counts

In both Zanette & Brunskill 2019; Efroni et al. 2019 these results were derived for MDPs with stationary dynamics. Repeating their analysis, in our case, an additional $H$ factor emerges as we consider MDPs with non-stationary dynamics.

E.3 Bias Lemmas

For any $k$ and state-action pair $(s,a)$ we have

Now, we use the above relation and apply Markov inequality to obtain

for every $(s,h,k)\in\sset\times[H]\times[K]$. With probability at least $1-\delta^{\prime}$,