Dueling RL: Reinforcement Learning with Trajectory Preferences

Introduction

Classical reinforcement learning (RL) with absolute reward feedback is a well-studied framework which is a sequential experience-driven learning process to optimize an accumulated long-term reward (Sutton and Barto, 2018; Auer et al., 2009; Singh et al., 2002). Over the years, several works have addressed RL in terms of both the optimal sample complexity for finding the best policy (Azar et al., 2013; Dann and Brunskill, 2015; Dann et al., 2017; Domingues et al., 2020a; Lattimore and Hutter, 2012) and minimizing regret via balancing exploration and exploitation (Zhang and Ji, 2019; Azar et al., 2017; Ortner, 2020; Talebi and Maillard, 2018; Efroni et al., 2020; Domingues et al., 2020b).

However, a major limitation of the standard RL setting is that its success crucially depends on the prior knowledge encoded into the definition of the reward function. The learned policy can often be sensitive to small changes of the reward, possibly yielding very different behaviors depending on the relative values of the rewards. The choice of reward function in applications such as robotics consequently entails a high amount of non-trivial effort in reward engineering, leading to challenges such as reward shaping, reward hacking, infinite rewards, and multi-objective outcomes (Wirth and Fürnkranz, 2013; Wirth et al., 2017).

The framework of Preference-based Reinforcement Learning (PbRL) (Busa-Fekete et al., 2014; Wirth et al., 2016, 2017) has been proposed as a fix to this problem, to enforce learning from non-numerical, relative feedback which need not suffer from issues due to the inaccuracy of reward modeling or engineering. This framework widely applies to multiple areas including robot training, stock-prediction, recommender systems, clinical trials, etc. (Novoseller et al., 2019; Sadigh et al., 2017; Christiano et al., 2017; Kupcsik et al., 2018; Jain et al., 2013; Wirth et al., 2017).

While the problem of PbRL was introduced almost a decade ago, most work in it has been primarily applied or experimental in nature (Jain et al., 2013; Busa-Fekete et al., 2014; Christiano et al., 2017; Wirth and Fürnkranz, 2013; Wirth et al., 2016, 2017; Kupcsik et al., 2018). There have also been attempts to design suitable algorithms based on varying preference models and problem objectives (Novoseller et al., 2019; Xu et al., 2020), but, to the best of our knowledge, existing theoretical guarantees on PbRL literature are sparse. The performance guarantees of most of the proposed algorithms are not well-understood (Wirth et al., 2017; Xu et al., 2020) except for some very recent attempts (Novoseller et al., 2019; Xu et al., 2020) as discussed below in the section on related work. We consider the problem of provably finding the best finite-horizon policy (i.e., one with highest expected reward) for an unknown Markov decision process (MDP), but with only relative preference feedback on $H$-length trajectories.

To the best of our knowledge, we are the first to formulate and analyze the finite time regret guarantee for preference-based linear bandits problem with non-Markovian reward models (Sec. 2).

We further generalize our algorithm to the case of unknown models and propose an algorithm with regret guarantee $\widetilde{\mathcal{O}}((\sqrt{d}+H^{2}+|\mathcal{S}|)\sqrt{dT}+\sqrt{|\mathcal{S}||\mathcal{A}|TH})$ (Sec. 4).

Related Work. Over the last two decades the problem of learning from preference feedback in bandits, known as dueling bandits, has gained much attention (Yue et al., 2012; Zoghi et al., 2014b, 2015). Dueling bandits generalizes the standard multi-armed bandit (MAB) (Auer et al., 2002). The goal is to identify a set of ’good’ arms from a larger fixed set of arms by querying preference feedback for pairs of actively chosen arms. Yue and Joachims (2009, 2011); Saha and Krishnamurthy (2022); Ghoshal and Saha (2022); Saha and Gopalan (2018a) The setting is relevant in various real-world systems which aim to collect information from user preferences, including recommender systems, retail management, search engine optimization, job scheduling, etc. Towards these goals, several algorithms have been proposed (Ailon et al., 2014; Zoghi et al., 2014a; Komiyama et al., 2015; Gajane et al., 2015; Saha and Gopalan, 2018b, 2019).

Though there has been a fair amount of research for preference-based bandits (no state information), few works consider incorporating preference feedback in the reinforcement learning (RL) framework, which considers the problem of long-term objectives over a markov decision process (Singh et al., 2002; Ng et al., 2006; Talebi and Maillard, 2018; Ortner, 2020; Zhang and Ji, 2019; Zanette and Brunskill, 2019). However the classical RL setup assumes access to reward feedback for each state-action pair which might be impractical in many real world scenarios. Few very recent works considered training RL agents based on general trajectory-based reward which are available only at the end of each trajectory (Efroni et al., 2021; Chatterji et al., 2021), but their setting still assumes access to absolute reward feedback, unlike the case in PbRL. Some initial works consider the applied PbRL problem inspired by the problems of reward hacking, reward shaping, difficulty to model infinite rewards or multi-objective trade-offs (Busa-Fekete et al., 2014; Wirth et al., 2016, 2017; Christiano et al., 2017) etc.

Novoseller et al. (2019) made the first attempt to analyze the finite $T$-round regret guarantee for the PbRL problem with trajectory preference feedback, where the learner is allowed to run two independent trajectories in parallel and receive $0/1$ preference feedback after every such $h$-length roll out. Assuming an underlying MDP model, the preference between two $h$-length trajectories is modeled as being proportional to the accumulated reward of the corresponding trajectories. The authors propose a Double Posterior Sampling (DPS) technique with asymptotically sublinear regret.

Xu et al. (2020) models reward-free trajectory preferences and analyses the sample complexity of finding the $\epsilon$-best-policy. Their proposed algorithm crucially depends on an underlying dueling bandit black box whose performance guarantee is restricted to preference structures like Strong Stochastic Transitivity and Stochastic Triangle Inequality. Furthermore, the algorithms proposed in this work are not shown to enjoy provably optimal sample complexity, and, moreover, the fundamental performance limit of sample complexity is also not explicitly analyzed.

The literature of multi-agent reinforcement learning in Markov games closely relates to the setup of PbRL which attempts the problem of reaching Nash equilibrium of a simultaneous move markov game based on per-state win-loss feedback of the two (or multiple) players. Bai and Jin (2020); Bai et al. (2020); Liu et al. (2021) address the problems from finite action two player markov games, while Xie et al. (2020) extended this setting to zero sum games with linear function approximation. However all these works analyzed the episodic sample complexity of the learning algorithm towards finding an $\epsilon$-approximate Nash equilibrium which is fairly unrelated to the regret objective of PbRL problem we considered in this paper.

Another closely related sub-field of RL, imitation learning, addresses the objective of learning optimal behavior from trajectories suggested by an expert. In Ng et al. (2000); Boularias et al. (2011); Neu and Szepesvári (2012); Wulfmeier et al. (2015), inverse reinforcement learning problems have been considered, where the objective is to extract (unknown) reward function from the trajectories given by an oracle or expert. Once the reward functions are computed, any RL algorithm could, in principle, be applied to compute the optimal policy. Ho and Ermon (2016) propose a generative adversarial network based imitation learning algorithm that computes the optimal policy directly from the trajectories of expert. Our work is fundamentally different in the sense that we do not receive trajectories or optimal actions from an expert. Instead, we get preferences over sample trajectories that are posed as queries to a system expert for preference feedback.

Problem Setup

Policy embedding. The above feature embedding also leads to a natural mean embedding of any policy $\pi:{\mathcal{S}}\mapsto{\mathcal{A}}$ given by $\phi(\pi):={\mathbf{E}}_{\tau\sim\pi}[\phi(\tau)]$.

Equation LABEL:eq:pref_logistic says the probability of any trajectory $\tau_{1}$ being preferred over $\tau_{2}$ is essentially proportional to the score difference of the individual trajectories, assuming the score for any trajectory $\tau$ is defined as the function

Non markovian policy class. The performance of all our algorithms will be measured against the policy that maximizes $s(\pi)$. Since $s(\tau)$ may be a non-markovian function of the trajectory, the policy optimizing this objective need not be markovian. We therefore set $\Pi$ as the set of all history dependent policies. In contrast with standard markovian RL works, this is one of the main sources of technical complexity of our setting.

[Bounded parameter] We assume that $\|{\mathbf{w}}^{*}\|\leq W$ for some known $W>0$.

[Bounded feature maps] For all trajectories $\tau$ we assume that $\|\phi(\tau)\|\leq B$ for some known $B>0$.Note $B$ could essentially depend on the trajectory-length $H$.

The degree of non-linearity of the sigmoid $\sigma$ over the parameter space (denoting the first derivative of $\sigma$ by $\sigma^{\prime}$) is given by

Objective: Alternative: The objective of the learner is to minimize regret by finding policies to maximize the sum of their expected scores over $T$ rounds. At each round $t$, the learner proposes two policies, $\pi^{1}_{t}$ and $\pi^{2}_{t}$, which are executed in the MDP generating trajectories $\tau_{t}^{1}$ and $\tau_{t}^{2}$. The learner then receives feedback in the form of the Bernoulli variable $o_{t}\in\{0,1\}$ which specifies whether $\tau^{1}_{t}$ is preferred ($o_{t}=1$) or $\tau^{2}_{t}$ is preferred ($o_{t}=0$). The preference feedback $o_{t}$ is distributed according to $P(\tau_{t}^{1}\succ\tau^{2}_{t})$. We measure the learner’s performance via its pseudo-regret w.r.t. policy class $\Pi$, which we define as:

where $\pi^{*}:=\max_{\pi\in\Pi}s(\pi)$. This essentially measures the performance of the learner at round $t$ in terms of average score of the played policies $\pi_{t}^{1},\pi_{t}^{2}$ w.r.t. the score maximizing policy $\pi^{*}$.

One may think of using our preference model (Equation LABEL:eq:pref_logistic_policies) to define an alternative notion of regret:

Fortunately, these two notions of regret can be shown to be ‘equivalent’ in the following sense,

Claim 1. Let $\pi^{*}\in\operatorname*{arg\,max}_{\pi\in\Pi}s(\pi)$. Then $\pi^{*}$ also achieves the $\max$ in Eqn. 4.

This argument can also be used to show $R_{T}^{\text{scr}}$ and $R_{T}^{\text{pref}}$ are equivalent up to constant factors when $B,W\leq 1$. The proof is given in Appendix A.

Claim 2. $\frac{R_{T}^{\text{scr}}}{2(e+1)}\leq R_{T}^{\text{pref}}\leq\frac{R_{T}^{\text{scr}}}{2}$.

We conclude that a strategy that attains sublinear $R_{T}^{\text{scr}}$ regret also has sublinear $R_{T}^{\text{perf}}$ regret.

Preference-Based Learning with Known Model

Then, the projected parameter, along with its confidence set, is given by

where $\beta_{t}(\delta)=\sqrt{\lambda}W+\sqrt{\log(1/\delta)+2d\log\left(1+\frac{tB}{\kappa\lambda d}\right)}$. We restate a bound by Faury et al. (2020) that shows the probability of ${\mathbf{w}}_{\star}$ being in $\mathcal{C}_{t}(\delta)$ for all $t\geq 1$ can be lower bounded.

2 Algorithm and Analysis

We are now ready to state the Logistic Preference based Reinforcement Learning (LPbRL) algorithm with known model, shown in Algorithm 1. Before any interaction or feedback, we initialize identical data matrices ${\mathbf{V}}_{1}=\overline{\mathbf{V}}_{1}=\kappa\lambda{\mathbf{I}}_{d}$, $\lambda>0$ being a regularization parameter. ${\mathbf{V}}_{t}$, as defined before, is designed to track the exact covariates used in the maximum likelihood estimation. $\overline{\mathbf{V}}_{t}$ (Line 10) on the other hand tracks a similar quantity, but instead uses the expected features under a given policy.

At each round $t$, we then compute an estimate ${\mathbf{w}}_{t}^{L}$ and determine a set of candidate policies $\SS_{t}$ for which no other policy $\pi$ significantly outperforms a member of $\SS_{t}$. The threshold for what constitutes “significant” is determined by the uncertainty in the estimate of ${\mathbf{w}}_{t}^{L}$. We then search over this set to identify two policies, $\pi_{t}^{1}$ and $\pi_{t}^{2}$, with expected features that maximize the uncertainty determined by $\overline{\mathbf{V}}_{t}$, precisely by choosing $(\pi_{t}^{1},\pi_{t}^{2})=\arg\max_{\pi^{1},\pi^{2}\in\Pi_{t}}\|\phi(\pi^{1})-\phi(\pi^{2})\|_{\overline{\mathbf{V}}_{t}^{-1}}$. Both policies are deployed, inducing trajectories $\tau_{t}^{1}$ and $\tau_{t}^{2}$ and feedback $o_{t}$ is received. We then update the data matrices ${\mathbf{V}}_{t}$ and $\overline{\mathbf{V}}_{t}$ with the trajectory features $\phi(\tau_{t}^{1})-\phi(\tau_{t}^{2})$ and expected features $\phi(\pi_{t}^{1})-\phi(\pi_{t}^{2})$, respectively. The procedure is repeated for each round $t\in[T]$.

Let $\delta\leq 1/e$ and $\lambda\geq\frac{B}{\kappa}$. Then, with probability at least $1-\delta$, the expected regret of Algorithm 1 can be bounded by

Note there is no dependence on the size of the state or action spaces on account of the model being known in this setting. Furthermore, we note that any dependence on the horizon $H$ is effectively accounted for in the size of the constant $B$ that bounds the norm of the trajectory features $\phi(\tau)$. For example, if $\phi(\tau)$ decomposes in a per-timestep fashion as $\phi(\tau)=\sum_{h\in[H]}\phi(s_{h},a_{h})$ where each $h$ satisfies $\|\phi(s_{h},a_{h})\|\leq B^{\prime}$, then a trivial bound would give $B\leq B^{\prime}H$. However, Assumption 2 allows for greater generality.

Theorem 1 shows that for a sufficiently large choice of the regularization parameter $\lambda$, the pseudo-regret of Algorithm 1 is at most $R_{t}={\mathcal{O}}\left(\left(W\sqrt{\kappa B}+WB\right)d\log(TB/\kappa\delta)\sqrt{T}\right)$. Importantly, the regret scales nearly optimally with $d\sqrt{T}$ dependency given existing $\Omega(d\sqrt{T})$ lower bounds for linear bandits (Lattimore and Szepesvári, 2020) and known reductions between the standard and preference regret Saha (2021). Assuming $\kappa$ to be constant, we pay the additional factors in $B$ and $W$ due to non-Markovian rewards which are only indirectly revealed to the learner in terms of preferences.

3 Regret Analysis: Proof Sketch of Thm. 1

We now sketch the proof of Theorem 1. Details and proofs of supporting results can be found in Appendix B.1. The main idea of the proof is to ensure that $\Pi_{t}$ contains only candidate policies that are predicted to be “sufficiently good” under the learned model ${\mathbf{w}}_{t}^{L}$ using the size of the confidence set $\mathcal{C}_{t}(\delta)$. We must also verify that $\SS_{t}$ always contains the optimal policy $\pi^{*}$. Thus, as long as the set $\mathcal{C}_{t}(\delta)$ shrinks at a sufficiently fast rate, our algorithm will have sublinear regret.

However, in order to judge the uncertainty in predictions of the expected value $\phi(\pi)^{\top}{\mathbf{w}}_{t}^{L}$ of a policy $\pi$, we must relate the data matrix ${\mathbf{V}}_{t}$ that controls the accuracy of the learned parameter ${\mathbf{w}}_{t}^{L}$ (see Lemma 1), and its expected counterpart $\overline{\mathbf{V}}_{t}$ (used to define $\Pi_{t}$). The set $\Pi_{t}$ is characterized via $\overline{\mathbf{V}}_{t}$ because this way it allows us to relate it to the algorithm’s regret, a quantity that depends on the expected features of the played policies. Corollary 1 establishes that distances $\|{\mathbf{w}}_{t}^{L}-{\mathbf{w}}^{*}\|_{\overline{\mathbf{V}}_{t}}$ weighted by $\overline{\mathbf{V}}_{t}$ are not too far from the same distances $\|{\mathbf{w}}_{t}^{L}-{\mathbf{w}}^{*}\|_{{\mathbf{V}}_{t}}$ weighted by ${\mathbf{V}}_{t}$. Let

Under Assumption 1, conditioned on event $\mathcal{E}_{\delta}\cap\mathcal{E}_{prec}$, for any $t\in[T]$

The proof of above is given in Appendix B. Leveraging this relationship, we can establish that the confidence set of policies $\Pi_{t}$ defined in line 5 of Algorithm 1 will contain the optimal policy.

Conditioned on event $\mathcal{E}_{\delta}\cap\mathcal{E}_{prec}$, $\pi^{*}\in\SS_{t}$,

The remainder of the proof now consists of showing the instantaneous regret can be bounded in terms of the size of the confidence sets and the uncertainty values $\|\phi(\pi^{1}_{t})-\phi(\pi^{2}_{t})\|_{\overline{\mathbf{V}}_{t}}$. We defer the final details to Appendix B.3.

Unknown model: Algorithm and Analysis

Algorithm description. The LPbRL algorithm for unknown dynamics models works in a similar way to Algorithm 1. The main differences lay in the definition of the set $\Pi_{t}$. Whereas in Algorithm 1 this set of policies can be defined without taking into account the model uncertainty, in this case the set of policies to optimize over needs to be carefully constructed in such a way that it can be shown to contain $\pi_{\star}$ (see Lemma 4). With this in mind we start by introducing the necessary technical tools that will be used throughout this section to deal with model uncertainty.

Our confidence intervals will use a Mahalanobis norm defined by this covariance matrix. Throughout this section we will make heavy use of some of the results from Chatterji et al. (2021). With that in mind we will define a variety of bonus terms. Given any $\eta>0$ define,

Similar to the previous theorem, we must relate $\|{\mathbf{w}}^{*}-{\mathbf{w}}_{t}^{L}\|_{\widetilde{\mathbf{V}}_{t}}$ and $\|{\mathbf{w}}^{*}-{\mathbf{w}}_{t}^{L}\|_{\overline{\mathbf{V}}_{t}}$. We do this via a series of Lemmas.

The proof of Lemma 3 is in Appendix C.2. We now proceed to define the set $\Pi_{t}$. To do so, it will be useful to introduce the following confidence radius multiplier

Algorithm 2 shares the structure of Algorithm 1. The main difference lies in the definition of $\Pi_{t}$ and in the optimization problem to find $(\pi_{t}^{1},\pi_{t}^{2})$. We can prove a result similar to Lemma 2 and show that $\pi^{*}\in\Pi_{t}$.

The proof of Lemma 4 can be found in Appendix C.3. The next step in the proof is to exhibit a bound on the instantaneous regret,

Similarly, as a consequence of Lemma 12 and a union bound, setting $\eta=2WB$, with probability at least $1-2\delta$

Armed with the results of Lemma 4 we can show the following bound for the regret.

With probability at least $1-15\delta$ the regret is bounded by,

The proof of Lemma 6 can be found in Appendix C.4. The derivation follows from a repeated use of the instantaneous regret upper bound derived from Lemma 5.

The regret of $\mathbf{LPbRL}$ satisfies,

The complete version of Theorem 2 can be found in Appendix C. Similar to Theorem 1, the leading term in the regret scales as $\widetilde{\mathcal{O}}(d\sqrt{T})$ due to estimation based on the preferences. In addition to this, we now have dependence on $|\mathcal{S}|$ and $|\mathcal{A}|$ unlike before. These arise due to the tabular nature of the problem since the transition dynamics are unknown in this case.

Discussions and Future Scopes

In this work we addressed the problem of reinforcement learning from relative preference feedback where the agent does not get to see the absolute reward of actions taken at each state but instead observes the relative preferences between trajectories. We modeled the preference feedback in terms of the underlying non-Markovian linear reward model and proposed algorithms for both known as well as unknown MDP transition models. Precisely the regret guarantees of our proposed algorithms are analyzed to be respectively $\widetilde{\mathcal{O}}\left(d\log(T/\delta)\sqrt{T}\right)$ and $\widetilde{\mathcal{O}}((\sqrt{d}+H^{2}+|\mathcal{S}|)\sqrt{dT}+\sqrt{|\mathcal{S}||\mathcal{A}|TH})$ for the case of known and unknown transition models.

As discussed in the introduction, preference-based reinforcement learning has applications in several fields including training robots, stock market, recommender systems, two player games, chatbot interactions, etc. Thus there are plenty of scopes to extend the above setup to incorporate the corresponding system requirements, e.g. generalizing dueling trajectory preferences to subsets, considering alternative preference feedback without assuming an underlying reward model, extending to infinite horizon settings with more complex state-actions spaces, etc. Analyzing the fundamental performance limits of the PbRL regret minimization problem and designing algorithms with tighter performance guarantees would also be another interesting direction to investigate.

Acknowledgment

AS gratefully thanks Aditya Gopalan and Raghuram Bharadwaj Diddigi (IISc Bangalore) for the initial discussions on preference based reinforcement learning literature.

References

Supplementary for \papertitle

Appendix A Appendix for Section 2

Claim 2. $\frac{R_{T}^{\text{scr}}}{2(e+1)}\leq R_{T}^{\text{pref}}\leq\frac{R_{T}^{\text{scr}}}{2}$.

Recall by Eq. (2), Eq. (4) and Claim $1$.

Now assume $S,B<1$. Then for any two policies $\pi_{1}$ and $\pi_{2}\in\Pi$, such that $s(\pi_{1})\geq s(\pi_{2})$, we have:

On the other hand denoting $x={s(\pi_{1})-s(\pi_{2})}\in(0,1)$ we get:

The claim now follows combining the above two inequalities and noting that by definition $\pi^{*}:=\arg\max_{\pi\in\Pi}s(\pi)$. ∎

Appendix B Appendix for Section 3

The primary mechanism behind Corollary 1 is the following lemma for matrix concentration.

Let $\delta\leq e^{-1}$. Then, with probability $1-\delta\log_{2}T$, for all $t\in[T]$, it holds that

Note that the conditional variance of the individual terms may be bounded above by

By (Bartlett et al., 2008, Lemma 2), we have, with probability at least $1-\delta\log_{2}T$,

where the third line applied the AM-GM inequality. Rearranging shows that

This holds for a fixed ${\mathbf{v}}$. We now show that it approximately holds for all ${\mathbf{v}}$ such that $\|{\mathbf{v}}\|_{2}=1$ via a covering argument.

Let $A=\frac{1}{2}{\mathbf{V}}_{T}-\widehat{\mathbf{V}}_{T}$. Note that $\|A\|\leq 4B^{2}T$ by definition. Let ${\mathbf{v}}\in\SS^{d-1}$ be arbitrary and let $u_{v}\in\mathcal{C}_{\epsilon}$ be the closest vector in the cover so that $\|{\mathbf{v}}-{\mathbf{u}}\|_{2}\leq\epsilon$. Then,

under the good event and choosing $\epsilon=1/T$. Since this holds for all ${\mathbf{v}}\in\SS^{d-1}$, we conclude that

with probability at least $1-\delta\log_{2}T$. Finally, by Jensen’s inequality we have $\overline{\mathbf{V}}_{T}\preceq\widehat{\mathbf{V}}_{T}$. Then, we apply the union bound over $t\in[T]$, which gives the result. ∎

The proof of the corollary now follows immediately as a consequence.

Assuming that $\mathcal{E}_{\delta}$ holds, we have that $\|{\mathbf{w}}^{*}-{\mathbf{w}}_{t}^{L}\|_{{\mathbf{V}}_{t}}\leq 2\kappa\beta(\delta)$. Furthermore, Lemma 7 gives

B.2 Proof of Lemma 2

Condition on $\mathcal{E}_{\delta}\cap\mathcal{E}_{prec}$. By definition of $\pi^{*}$, we have $\left(\phi(\pi^{*})-\phi(\pi)\right)^{\top}{\mathbf{w}}^{*}\geq 0$ for any arbitrary $\pi$. This implies

where the second line follows from Corollary 1. ∎

B.3 Proof of Theorem 1

We require a standard determinant bound to complete the proof.

Since $\lambda\geq B$, we have that $\|{\mathbf{v}}_{t}\|_{V_{t}^{-1}}\leq 1$. Therefore, from Lemma 19.4 of Lattimore and Szepesvári (2020)

Armed with the supporting results, we now focus on completing the proof of Theorem 1. The result may be shown by bounding the instantaneous regret. Condition on the event $\mathcal{E}_{\delta}$. Then,

The last two terms in the above sum can be bounded using Corollary 1 as follows:

The first two terms leverage the optimistic bonus, using the fact that $\pi^{1}_{t},\pi^{2}_{t}\in\mathcal{S}_{t}$:

In summary, we have that the instantaneous regret is upper bounded as

where the last inequality follows from the fact that $\pi^{*}\in\mathcal{S}_{t}$ by Lemma 2 and since $\pi^{1}_{t}$ and $\pi^{2}_{t}$ were chosen the maximizer of the weighted difference $\|\phi(\pi_{t}^{1})-\phi(\pi_{t}^{2})\|_{\overline{\mathbf{V}}_{t}}$. The regret is therefore

where the second inequality follows from Cauchy-Schwarz and the last inequality applies Lemma 8. ∎

Appendix C Appendix for Section 4

In this section we will use the notation $N_{t}(s,a)$ to denote the number of times action $a$ was executed at state $s$ up to time $t-1$. Recall the bonus terms,

and the empirical average of $\xi^{(t)}_{s,a}(\eta,\delta)$ bonuses,

Additionally we also define the error terms

In contrast with the definition of bonus $\xi^{(t)}_{s,a}(\eta,\delta)$ this quantity depends on an extra parameter $\epsilon$. These erorr terms induce the the following ‘bonus’ function,

Here the expectation is under the true MDP dynamics.

Once we have established the validity of Lemma 6, and therefore that with probability at least $1-15\delta$,

it remains to show the $\widehat{B}_{t}()$ terms are small. We’ll do so by showing that for any $\eta>0$ and $\delta\in(0,1)$ and for all policies $\pi$ simultaneously we can bound the empirical expected bonuses $\widehat{B}_{t}(\pi,\eta,\delta)$ in terms of the population quantities $B_{t}(\pi,\eta H,\delta)$,

Since $\xi^{(t)}_{s,a}(\epsilon,\eta,\delta)\geq\xi_{s,a}^{(t)}(\eta,\delta)$ for all $\epsilon>0$, $s,a\in\mathcal{S}\times\mathcal{A}$ and $\xi^{(t)}_{s,a}(\epsilon,\eta,\delta)$ is monotonic in $\eta$ we conclude that,

Combining these inequalities the result follows.

Where $\mathbf{I}=128HSB\sqrt{TH\log\left(\frac{6\log(TH)}{\delta}\right)}$. In order to bound the remaining empirical error terms, we to the following standard result,

For $i\in\{1,2\}$ the empirical sum of errors satisfies the following bound

Let’s rewrite this sum by instead summing over states and actions,

We will use Lemma 10 with $\epsilon=1/T$. As a consequence of Lemma 10 and Lemma 6 we see that when $\mathcal{E}_{\delta}\cap\mathcal{E}_{2}\cap\bar{\mathcal{E}}_{0}\cap\bar{\mathcal{E}}_{-1}\cap\bar{\mathcal{E}}_{2}\cap\bar{\mathcal{E}}_{3}$ holds

Therefore with high probability for $i\in\{1,2\}$,

Therefore with probability $1-2\delta^{\prime}$,

Let’s rewrite this sum by instead summing over states and actions,

Therefore with probability $1-2\delta^{\prime}$,

The main takeaway from this lemma is that the sum of the square errors grows only logarithmically in $T$. Applying this bound to $\gamma_{T}$ and setting $\epsilon=O(1/T)$ we obtain,

Applying this bound to $\gamma_{T}$ and setting $\epsilon=1/96T$ we obtain,

Combining these observations we can derive our main result,

If $\mathcal{E}_{\delta}\cap\mathcal{E}_{2}\cap\bar{\mathcal{E}}_{0}\cap\bar{\mathcal{E}}_{-1}\cap\bar{\mathcal{E}}_{2}\cap\bar{\mathcal{E}}_{3}\cap\bar{\mathcal{E}}_{4}\cap\bar{\mathcal{E}}_{5}(\frac{\delta}{2})$ holds then the regret of $\mathbf{LPbRL}$ satisfies,

We will make use of the following Lemma (see Lemma B.1 in Chatterji et al. (2021)),

We will also make use of the following Lemma (see Lemma B.2 from Chatterji et al. (2021) ) corresponding to the uniform version of lemma 12.

We will make use of the following standard bound on the covering number of the $l_{2}$ ball.

C.2 Proof of Lemma 3

Recall that as a result of assumption 1 and the definition of ${\mathbf{w}}_{t}^{L}$ we can bound $\|{\mathbf{w}}_{t}^{L}-{\mathbf{w}}^{*}\|\leq 2S$. Let ${\mathbf{v}}$ be such that $\|{\mathbf{v}}\|\leq 2S$.

Let’s consider ${\mathbf{v}}^{\top}\widetilde{\mathbf{V}}_{t}{\mathbf{v}}$,

Invoking Lemma 14 and setting $\delta^{\prime}=\frac{\delta}{\left(\frac{1+4S}{\epsilon}\right)^{d}}$ applying it to ${\mathbf{w}}_{t}^{L}-{\mathbf{w}}_{*}$

Setting $\epsilon=\frac{1}{t^{2}\kappa\lambda+4B^{2}t^{3}}$ and using the fact that all $a,b,c\geq 0$ we have $\sqrt{a^{2}+b^{2}+c^{2}}\leq a+b+c$,

C.3 Proof of Lemma 4

By definition of $\pi_{*}$, $(\phi(\pi^{*})-\phi(\pi))^{\top}{\mathbf{w}}^{*}\geq 0$ for any arbitrary $\pi$. Therefore,

In particular this implies that with probability at least $1-\delta$ for $\pi^{*}$ and any $\pi$,

Since $\bar{\mathcal{E}}_{0}$ holds, by Lemma 3

Since $\mathcal{E}_{\delta}\cap\mathcal{E}_{2}$ is assumed to hold Corollary 1 implies that $\|{\mathbf{w}}_{t}^{L}-{\mathbf{w}}_{*}\|_{\widetilde{{\mathbf{V}}}_{t}}\leq 4\kappa\beta_{t}(\delta)+\alpha_{d,T}(\delta)$ and therefore,

Thus implying $\pi^{*}\in\Pi_{t}$. Taking a union bound between $\mathcal{E}_{\delta}\cap\bar{\mathcal{E}}_{0}\cap\mathcal{E}_{2}$ and the $1-\delta$ probability event from Equation 25 yields the result.

C.4 Proof of Lemma 6

If $\mathcal{E}_{\delta}\cap\mathcal{E}_{2}\cap\bar{\mathcal{E}}_{0}\cap\bar{\mathcal{E}}_{-1}\cap\bar{\mathcal{E}}_{2}$ the regret is bounded by,

We first condition on $\mathcal{E}_{\delta}\cap\mathcal{E}_{2}\cap\bar{\mathcal{E}}_{0}\cap\bar{\mathcal{E}}_{-1}$. Let’s start by showing the following bound on the instantaneous regret,

Since we are conditioning on $\bar{\mathcal{E}}_{2}$, by Lemma 5 follows that for all $t$,

Since $\mathcal{E}_{\delta}\cap\mathcal{E}_{2}\cap\bar{\mathcal{E}}_{0}$ holds, the last two terms in the sum above can be bounded using Lemma 3 and Corollary 1 by

The first two terms on the right hand side of inequality 26 leverage the optimistic bonus, using the fact that $\pi_{t}^{1},\pi_{t}^{2}\in\Pi_{t}$ and therefore,

Putting these together we can conclude that,

Recall that whenever $\bar{\mathcal{E}}_{-1}$ holds, $\pi^{*}\in\Pi_{t}$ and that as a result of how $\pi_{t}^{1},\pi_{t}^{2}$ are chosen (see Algorithm 2)

The regret is therefore upper bounded by,

Where the last inequality follows from Lemma 8.

Appendix D Miscelaneous Technical Lemmas

Observe that $\frac{\left|x_{t}\right|}{\zeta}\leq 1$. By invoking a time-uniform Hoeffding-style concentration inequality (Howard et al., 2020, Equation (11)) we find that

Rounding up the constants for the sake of simplicity we get