On Lower Bounds for Regret in Reinforcement Learning

Introduction

This is a brief technical note to clarify the state of lower bounds on regret for reinforcement learning. In particular, this paper:

Reproduces a lower bound on regret for reinforcement learning, similar to the result of Theorem 5 in the journal UCRL2 paper Jaksch et al. (2010).

Clarifies that the proposed proof of Theorem 6 in the REGAL paper Bartlett and Tewari (2009) does not hold using the standard techniques without further work. We suggest that this result should instead be considered a conjecture as it has no rigorous proof.

Suggests that the conjectured lower bound given by Bartlett and Tewari (2009) is incorrect and, in fact, it is possible to improve the scaling of the upper bound to match the weaker lower bounds presented in this paper.

Problem formulation

We consider the problem of learning to optimize an unknown MDP $M^{*}=(\mathcal{S},\mathcal{A},R^{*},P^{*})$. $\mathcal{S}=\{1,..,S\}$ is the state space, $\mathcal{A}=\{1,..,A\}$ is the action space. In each timestep $t=1,2,..$ the agent observes a state $s_{t}\in\mathcal{S}$, selects an action $a_{t}\in\mathcal{A}$, receives a reward $r_{t}\sim R^{*}(s_{t},a_{t})\in$ and transitions to a new state $s_{t+1}\sim P^{*}(s_{t},a_{t})$. We define all random variables with respect to a probability space $(\Omega,\mathcal{F},\mathds{P})$.

A policy $\mu$ is a mapping from state $s\in\mathcal{S}$ to action $a\in\mathcal{A}$. For MDP $M$ and any policy $\mu$ we define the long run average reward starting from state $s$:

Let $\mathcal{H}_{t}=(s_{1},a_{1},r_{1},..,s_{t-1},a_{t-1},r_{t-1})$ denote the history of observations made prior to time $t$. A reinforcement learning algorithm is a deterministic sequence $\{\pi_{t}|t=1,2,..\}$ of functions each mapping $\mathcal{H}_{t}$ to a probability distribution $\pi_{t}(\mathcal{H}_{t})$ over policies, from which the agent sample policy $\mu_{t}$ at timestep $t$. We define the regret of a reinforcement learning algorithm $\pi$ up to time $T$

The regret of a learning algorithm shows how worse the policy performs that optimal in terms of cumulative rewards. Any algorithm with $o(T)$ regret will eventually learn the optimal policy. Note that the regret is random since it depends on the unknown MDP $M^{*}$, the random sampling of policies and, through the history $\mathcal{H}_{t}$ on the previous transitions and rewards. We will assess and compare algorithm performance in terms of the regret.

In a finite horizon MDP a typical policy may depend on both the state $s\in\mathcal{S}$ and the timestep $h$ within the episode. To be explicit, we define a policy $\mu$ is a mapping from state $s\in\mathcal{S}$ and period $h=1,..,H$ to action $a\in\mathcal{A}$. For each MDP $M=(\mathcal{S},\mathcal{A},R^{M},P^{M},H,\rho)$ and policy $\mu$ we define the state-action value function for each period $h$:

and $V^{M}_{\mu,h}(s):=Q^{M}_{\mu,h}(s,\mu(s,h))$. Once again, we say a policy $\mu^{M}$ is optimal for the MDP $M$ if $\mu^{M}\in\operatorname*{arg\,max}_{\mu}V^{M}_{\mu,h}(s)$ for all $s\in\mathcal{S}$ and $h=1,\ldots,H$.

Multi-armed bandit

We call the degenerate MDP with only one state $S=1$ a multi-armed bandit with independent arms Lai and Robbins (1985). In this setting the actions $a_{t}\in\mathcal{A}$ are often called “arms” and the optimal average reward is simply the average reward of the highest reward,

We now reproduce a lower bound on regret for any learning algorithm in a multi-armed bandit Bubeck and Cesa-Bianchi (2012).

Let $\sup$ be the supremum over all distributions of rewards such that for each $a=1,..,A$ the rewards $r(1)_{t},..,r(A)_{t}\in\{0,1\}$ are i.i.d. and let $\inf$ be the infimum over all reinforcement learning algorithms. Then

At a high level Theorem 1 says that no matter what learning algorithm you choose, there will always be some environment which gives your algorithm $\Omega(\sqrt{AT})$ regret. This is a pretty powerful result, since it means that if we can design an algorithm with upper bounds on regret $O(\sqrt{AT})$ then this algorithm is in some sense near-optimal Bubeck and Cesa-Bianchi (2012).

The intuition for the proof is relatively simple and presented in Bubeck and Cesa-Bianchi (2012). After any $T$ timesteps there must be some arm which is pulled less than $T/A$ times. Standard concentration results state that the estimates of a random variable can only be accurate up to $O\left(\frac{1}{\sqrt{n}}\right)$ where $n$ is the number of observations. Therefore, for the arm with $n\leq T/A$ it is difficult to distinguish between a ${\rm Ber}(1/2)$ and ${\rm Ber}(1/2+\sqrt{A/T})$. This means that, if every arm is ${\rm Ber}(1/2)$ but one ${\rm Ber}(1/2+\sqrt{A/T})$, any algorithm would incur $T\sqrt{A/T}=\sqrt{AT}$ regret. In the next section we will see how to make this argument more rigorous.

For all $\delta,\epsilon>0$ and all learning algorithms $\pi$,

For all $\delta,\epsilon>0$ and all learning algorithms $\pi$,

We can apply the chain rule of KL divergence Bubeck and Cesa-Bianchi (2012) to obtain

For all $\delta,\epsilon>0$ and all learning algorithms $\pi$,

To complete the proof of Theorem 1 we can use Lemma 20 from Jaksch et al. (2010).

For any $0\leq\delta\leq\frac{1}{2}$ and $\epsilon\leq 1-2\delta$ we have

We combine Proposition 1 with Lemma 3 to say,

We can choose $\delta=0.25$ to complete the proof of Theorem 1. We note that better constants are available through a more careful analysis, but this is not our focus in this work. ∎

Reinforcement learning

In this section we will work to extend the lower bound arguments from bandits to reinforcement learning with $S\geq 2$. As in common in the literature, we will begin with a simple two state MDP with known rewards and unknown transitions Jaksch et al. (2010); Bartlett and Tewari (2009); Dann and Brunskill (2015). It is relatively straightforward to extend this flavour of result to MDPs with $S>2$ simply by concatenating $\lceil S/2\rceil$ copies of these smaller systems.

State gives a reward of and state $1$ gives a reward of $1$. All actions from the state 0 follow the same law $P(0,a)=(1-\delta_{0},\delta_{0})$. In state 1 $P(1,a)=(\delta_{1},1-\delta_{1})$ for all actions apart from $P(1,a^{*})=(\delta_{1}-\epsilon,1-\delta_{1}+\epsilon)$. For this simple MDP we will distinguish policies in terms of their action upon $s=1$, since this is the only action which can influence the evolution of the MDP.

We define $\theta_{1}:=\frac{\delta_{0}}{\delta_{0}+\delta_{1}}$ to be the average expected reward under the policy $a\neq a^{*}$. For convenience we write $\delta^{*}_{1}:=\delta_{1}-\epsilon$ for the distinguished optimal action and correspondingly $\theta^{*}_{1}:=\frac{\delta_{0}}{\delta_{0}+\delta^{*}_{1}}$ for the average expected reward under the optimal policy $a^{*}$.

In this section we present a quick overview of the style of argument that attempts to solidify the lower bound of Theorem 6 in Bartlett and Tewari (2009). We assume that $\delta_{0}\geq\delta_{1}$ to bound the difference in optimal value,

Broadly speaking, this indicates that the agent should obtain expected regret $\Omega(\epsilon/\delta_{0})$ every timestep it selects action $a_{t}\neq a^{*}$ whilst in state $s=1$. All other actions in any other state produce zero regret. We now note that the problem described by Figure 1 is quite similar to the bandit example from Section 3. The difference here is that actions of the suboptimal arm $a\neq a^{*}$ give expected regret $O(\frac{\epsilon}{\delta_{0}})$, rather than $\epsilon$.

In the environment of Figure 1, for all $\delta,\epsilon>0$ and all learning algorithms $\pi$,

We note that the uninformed agent can only incur regret when it makes a sub-optimal decision, which is only possible in state $s=1$. The proportion of the time the agent spends in state $s=1$ is lower bounded by $\theta_{1}$. The regret for any sub-optimal decision while in state $s=1$ is at least $\frac{\epsilon}{4\delta_{0}}$ by (7). We follow the arguments from Lemma 1 to obtain our desired result. ∎

We now note that the problem of learning a 2-state transition function is equivalent to estimating a Bernoulli reward. Therefore, we can use Lemma 4 in place of Lemma 1 and repeat a similar argument to the proof of Theorem 1 for multi-armed bandits. At a high level we can bound the regret of any agent in terms of the deviation in KL from the distribution of the uninformed agent. For $\epsilon$ small, and over a short enough time window $T$, the distribution of actions chosen by the learning algorithm cannot differ significantly from the actions chosen from the uninformative system. As such, using Pinsker’s inequality, the resulting regret from any learning algorithm cannot differ significantly from that of the uninformed algorithm.

To make this argument explicit, we use Lemma 2 and Lemma 3 together with Proposition 2 and optimize over the resulting bound over $\epsilon$. That is to say, for any learning algorithm $\pi$,

Now, we are left with a problem to complete the argument for Theorem 6 from REGAL. We introduce the notation, $T^{M}_{\mu}(s,s^{\prime})$ for the expected number of timesteps to get from state $s$ to $s^{\prime}$ in MDP $M$ under policy $\mu$. The one-way diameter of an MDP is defined

The claim in Theorem 6 of REGAL is that, for any learning algorithm $\pi$ there exists and MDP $M$ such that ${\rm Regret}(T,\pi,M^{*})\geq c_{0}D_{\rm ow}\sqrt{SAT}$ for some $c_{0}>0$.

From construction of the MDP in Figure 1 it is clear that $D_{\rm ow}=\frac{1}{\delta_{0}}$, since the only state with optimal value bias is $s=1$ and the expected time from $s=0$ to $s=1$ is $\frac{1}{\delta_{0}}$. We now examine behaviour of the remaining free parameters using the definition $\theta_{1}=\delta_{0}/(\delta_{0}+\delta_{1}):$

This completes the demonstration that the standard proof techniques for lower bounds do not address the problems in the proof REGAL Theorem 6. In fact, we are only able to establish a lower bound $\Omega(\sqrt{D_{\rm ow}SAT})$ and not $\Omega(D_{\rm ow}\sqrt{SAT})$ as Bartlett and Tewari (2009) had claimed. Further, these bounds are actually weaker than the established results in Jaksch et al. (2010) $\Omega(\sqrt{DSAT})$, where $D(M):=\max_{s,s^{\prime}}\min_{\mu}T^{M}_{\mu}(s,s^{\prime})\geq D_{\rm ow}$ is the diameter of the MDP.

2 Where do the lower bounds lie?

The arguments in Section 4.1 show that existing machinery is not sufficient to establish a proof of Theorem 6 in Bartlett and Tewari (2009). In light of this we suggest that this published result be considered a conjecture, rather than an established theorem. In this note we present another alternative conjecture, that the results of Theorem 6 in Bartlett and Tewari (2009) are not correct. The spirit of this conjecture is similar to Conjecture 1 of Osband and Van Roy (2016) given for finite horizon MDPs.

The lower bounds of Jaksch et al. (2010) $\Omega\left(\sqrt{DSAT}\right)$ are unimprovable in the sense that there exists some learning algorithm $\pi$ such that, for any MDP $M^{*}$ and any $\delta>0$

In order for Conjecture 1 to be true, the sketched proof in Bartlett and Tewari (2009) must be false. Although the arguments of Section 4.1 show that this proof is not yet rigorous, they do not pinpoint any step of the appealing sketched argument which is incorrect. However, we will now present an intuitive argument for what may be going wrong in the sketched proof:

For every timestep $t$ in state $s=1$ the worst possible decision the agent could make will contribute regret $O(D{\rm ow})$ in terms of the value. The proposed sketch proof argues that the agent effectively incurs this regret every timestep until it learns the optimal arm.

If we measure regret in terms of actual shortfall in the instantaneous regret $\lambda^{*}_{*}-r_{t}$ must be bounded $O(1)$ per timestep. The bad decisions in state $s=1$ are just worth $O(D_{\rm ow})$ value because it might lead to $O(D_{\rm ow})$ of these $O(1)$ instantaneous regret steps to occur in a row.

Alternatively, we might think of regret in terms of the future value $O(D_{\rm ow}$ which a bad decision at $s=1$ may be worth - this is the argument that REGAL uses Bartlett and Tewari (2009). However, if we do this then that means this bad decision must be followed by $O(D_{\rm ow})$ timesteps in which we count no additional regret.

At the moment, the argument for Theorem 6 in Bartlett and Tewari (2009) is doing a type of double-counting for regret. It assigns the maximum $O(D_{\rm ow}(M^{*}))$ regret in terms of value at each timestep. However, this analysis ignores that for every one of these bad actions there will be $O(D_{\rm ow})(M^{*})$ periods of time within $s=0$ where, in terms of the value shortfall, these actions will not incur further regret than has been counted already.

2.2 Comparison to existing tight PAC bounds

The analysis for LUCFH in finite horizon MDPs implies that the number of episodes required for $\epsilon$-optimal episodes is $\Theta(\frac{H^{2}}{\epsilon^{2}})$, where we view all variables other than $H$ and $\epsilon$ as fixed. According to their definition, this would imply $\Theta(\frac{H^{3}}{\epsilon^{2}})$ timesteps until $\epsilon$-optimal episodes, which is roughly equivalent to $\Theta(\frac{H}{\epsilon^{2}})$ timesteps until $\epsilon$-optimal timesteps.

At a high level the algorithm and analysis from Dann and Brunskill (2015) leverages the sort of phenomenon we describe in Section 4.2.1. This essential argument is refined and made more rigorous through the Bellman equation for local variance, first used in Lattimore and Hutter (2012). It is not generally possible to go from PAC bounds to regret guarantees, however, the spirit of previous analyses and comparable results suggest that the tight bounds $\Theta(\frac{H}{\epsilon^{2}})$ timesteps until $\epsilon$-optimal timesteps are suggestive of a tight regret scaling $\Theta(\sqrt{HT})$.

Conclusion

This technical note aims to clarify the current state of lower bounds for regret in reinforcement learning. We reproduce a clear step by step argument for the lower bound on regret given in Bartlett and Tewari (2009). We show that, using standard machinery, this leads to a provable lower bound $\Omega(\sqrt{D_{\rm ow}SAT})$ and currently there is no proof available for the bound $\Omega(D_{\rm ow}\sqrt{SAT})$ as conjectured in that earlier work. To stimulate thinking on this topic, we present Conjecture 1, that the lower bound $\Omega(\sqrt{D_{\rm ow}SAT})$ is in fact unimprovable. Definitively proving these results one way or another is an exciting area for future research.

Acknowledgements

We would like to thank the authors of Bartlett and Tewari (2009) for their help and dialogue in the discussion of these delicate technical issues. We would also like to thank Daniel Russo for the many hours of discussion and analysis spent in the office on issues like these.

References