Model-Based Reinforcement Learning with Value-Targeted Regression

Introduction

Reinforcement learning (RL) enables learning to control complex environments through trial and error. It is a core problem in artificial intelligence (Russel & Norvig, 2003; Sutton & Barto, 2018) and recent years has witnessed phenomenal empirical advances in various areas such as: games, robotics and science (e.g., Mnih et al., 2015; Silver et al., 2017; AlQuraishi, 2019; Arulkumaran et al., 2019). In online RL, an agent has to learn to act in an unknown environment “from scratch”, collect data as she acts, and adapt the policy to maximize the reward collected. An important problem is to design algorithms that provably achieve sublinear regret in a large class of environments. Regret minimization for RL has received considerable attention in recent years (e.g., Jaksch et al. 2010; Osband et al. 2014; Azar et al. 2017; Dann et al. 2017, 2018; Agrawal & Jia 2017; Osband et al. 2017; Jin et al. 2018; Yang & Wang 2019a; Jin et al. 2019). While most of these existing works focus on the tabular or linear-factored MDP, only a handful of prior efforts have studied RL with general model classes. In particular, in a pioneering paper Strens (2000) proposed to use posterior sampling, which was later analyzed in the Bayesian setting by Osband & Van Roy (2014); Abbasi-Yadkori & Szepesvári (2015); Theocharous et al. (2017). The reader is referred to Section 5 for a discussion of these and other related works.

In this paper, we study episodic reinforcement learning in an environment where the unknown probability transition model is known to belong to a family of models, i.e., $P\in\mathcal{P}$. The model family $\mathcal{P}$ is a general set of models, and it may be either finitely parametrized or nonparametric. In particular, our approach accommodates working with smoothly parameterized models (e.g., Abbasi-Yadkori & Szepesvári, 2015), and can find use in both robotics (Kober et al., 2013) and queueing systems (Kovalenko, 1968). An illuminating special case is the case of linear parametrization when elements of $\mathcal{P}$ take the form $P_{\theta}=\sum_{i}\theta_{i}P_{i}$ where $P_{1},P_{2},\ldots,P_{d}$ are fixed, known basis models and $\theta=(\theta_{1},\dots,\theta_{d})$ are unknown, real-valued parameters. Model $P_{\theta}$ can be viewed as a mixture model that aggregates a finite family of known basic dynamical models (Modi et al., 2019). As an important special case, linear mixture models include the linear-factor MDP model of Yang & Wang (2019a), a model that allows the embedding of possible transition kernels into an appropriate space of finite matrices.

The main contribution of this paper is a model-based upper confidence RL algorithm where the main novelty is the criterion to select models that are deemed consistent with past data. As opposed to standard practice where the models are selected based on their ability to predict next states or raw observations there (cf. Jaksch et al. (2010); Yang & Wang (2019a) or (Strens, 2000; Osband & Van Roy, 2014; Abbasi-Yadkori & Szepesvári, 2015; Ouyang et al., 2017; Agrawal & Jia, 2017) in a Bayesian setting), we propose to evaluate models based on their ability to predict the values at next states as computed using the last value function estimate produced by our algorithm. In effect, the algorithm aims to select models based on their ability to produce small losses in a value-targeted regression problem.

Value-targeted regression is attractive for multiple reasons: (i) First and foremost, value-targeted regression holds the promise that model learning will focus on task-relevant aspects of the transition dynamics and can ignore aspects of the dynamics that are not relevant for the task. This is important as the dynamics can be quite complicated and modelling irrelevant aspects of the dynamics can draw valuable resources away from modelling task-relevant aspects. (ii) A related advantage is that building faithful probability models with high-dimensional state variables (or observations) can be challenging. Value-targeted regression sets up model learning as a real-valued regression problem, which intuitively feels easier than either building a model with maximum likelihood or setting up a vector-valued regression problem to model next state probabilities. (iii) Value-targeted regression aims at directly what matters in terms of the model accuracy or regret. Specifically the objective used in value-targeted is obtained from an expression that upper bounds the regret, hence it is natural to expect that minimizing this will lead to a small regret.

In addition, our approach is attractive as the algorithm has a modular structure and this allows any advances on components (optimistic planning, improvements in designing confidence sets) to be directly translated into a decreased regret. One may also question whether value-targeted regression is going “too far” in ignoring details of the dynamics. Principally, one may think that since the value function used in defining the regression targets is derived based on imperfect knowledge, the model may never be sufficiently refined in a way that allows the regret to be kept under control. Secondly, one may worry about that by ignoring the rich details of observations (in our simple model, the identity of the state), the approach advocated is ignoring information available in the data, which may slow down learning. To summarize, the main question, to which we seek an answer in this paper, is the following:

Is value-targeted regression sufficient and efficient for model-based online RL?

Based on the theoretical and the experimental evidence that we provide in this paper, our conclusion is that the answer is ‘yes’.

Firstly, the regret bounds we derive conclusively show that the despite the imperfection and non-stationarity of the value targets, the algorithm cannot get “stuck” (i.e., it enjoys sublinear regret). Our results also suggest that perhaps there is no performance degradation as compared to the performance of competing algorithms. We are careful here as this conclusion is based on comparing worst-case upper bounds, which cannot provide a definitive answer.

To complement the theoretical findings, our experiments also confirm that our algorithm is competitive. The experiments also allow us to conclude that it is value-targeted regression together with optimistic planning that is effective. In particular, if optimism is taken away (i.e., $\epsilon$-greedy is applied for the purpose of providing sufficient exploration), value-targeted regression performs worse than using a canonical approach to estimate the model. Similarly, if value-targeted regression is taken away, optimism together with the canonical model-estimation approach is less sample-efficient.

This still leaves open the possibility that certain combinations of value-targeted regression and canonical model building can be more effective than value-targeted regression. In fact, given the vast number of possibilities, we find this to be a quite plausible hypothesis. We note in passing that our proofs can be adjusted to deal with adding simultaneous alternative targets for constraining the set of data-consistent models. However, sadly, our current theoretical tools are unable to exhibit the tradeoffs that one expects to see here.

It is interesting to note that, in an independent and concurrent work, value-targeted regression has also been suggested as the main model building tool of the MuZero algorithm. The authors of this algorithm empirically evaluated MuZero on a number of RL benchmarks, such as the 57 Atari “games”, the game of “Go”, chess and shogi (Schrittwieser et al., 2019). In these benchmarks, despite the fact that MuZero does not use optimistic exploration or any other “smart” exploration technique, MuZero was found to be highly competitive with its state-of-the-art alternatives, which reinforces the conclusion that training models using value-targeted regression is indeed a good approach to build effective model-based RL algorithms. The good results of MuZero on these benchmark may seem to contradict our experimental findings that value-targeted regression is ineffective without an appropriate, ‘smart’ exploration component. However, there is no contradiction: Smart exploration may be optional in some environments; our experiments show that it is not optional on some environments. In short, for robust performance across a wide range of environments, smart exploration is necessary but smart exploration may be optional in some environments.

As to the organization of the rest of the paper, the next section (Section 2) introduces the formal problem definition. This is followed by the description of the new algorithm (Section 3) and the main theoretical results (Section 4). In particular, we first give a regret bound for the general case where the regret is expressed as a function of the “richness” of the model class $\mathcal{P}$. This analysis is based on the Eluder dimension of an appropriately defined function class and its metric entropy at an appropriate scale. It is worth noting that the regret bound does not depend on either the size of the state or the size of the action space. To illustrate the strength of this general technique, we specialize the regret bound for the case of linear mixture models,

for which we prove that the expected cumulative regret is at most $O(d\sqrt{H^{3}T})$, where $H$ is the episode length, $d$ is the number of model parameters and $T$ is the total number of steps that the RL algorithm interacts with its environment. To complement the upper bound, for the linear case we also provide a regret lower bound $\Omega(\sqrt{HdT})$ by adapting a lower bound that has been derived earlier for tabular RL. After these results, we discuss the connection of our work to prior art (Section 5). This is followed by the presentation of our empirical results (Section 6), where, as it was alluded to earlier, the aim is to explore how the various parts of the algorithm interact with each other. Section 7 concludes the paper.

Problem Formulation

We study episodic Markov decision processes (MDPs, for short), described by a tuple $M=(\mathcal{S},\mathcal{A},P,r,H,s_{\circ})$. Here, $\mathcal{S}$ is the state space, $\mathcal{A}$ is the action space, $P$ is the transition kernel, $r$ is a reward function, $H>0$ is the episode length, or horizon, and $s_{\circ}\in\mathcal{S}$ is the initial state. In the online RL problem, the learning agent is given $\mathcal{S}$, $\mathcal{A}$, $H$ and $r$ but does not know $P$.Our results are easy to extend to the case when $r$ is not known. The agent interacts with its environment described by $M$ in episodes. Each episode begins at state $s_{\circ}$ and ends after the agent made $H$ decisions. At state $s\in\mathcal{S}$, the agent, after observing the state $s$, can choose an action $a\in\mathcal{A}$. As a result, the immediate reward $r(s,a)$ is incurred. Then the process transitions to a random next state $s^{\prime}\in\mathcal{S}$ according to the transition law $P(\cdot|s,a)$. The precise definitions require measure-theoretic concepts (Bertsekas & Shreve, 1978), i.e., $P$ is a Markov kernel, mapping from $\mathcal{S}\times\mathcal{A}$ to distributions over $\mathcal{S}$, hence, all these spaces need to be properly equipped with a measurability structure. For the sake of readability and also because they are well understood, we omit these technical details.

The agent’s goal is to maximize the total expected reward received over time.

If $P$ is known, the behavior that achieves this over any number of episodes can be described by applying a deterministic policy $\pi$. Such a policy is a mapping from $\mathcal{S}\times[H]$ into $\mathcal{A}$, where we use the convention that for a natural number $n$, $[n]=\{1,\dots,n\}$. Following the policy means that the agent upon encountering state $s$ in stage $h$ will choose action $\pi(s,h)$. In what follows, we will use $\pi_{h}(s)$ as an alternate notation, as this makes some of the formulae more readable. We will also follow this convention when it comes to other functions whose domain is $\mathcal{S}\times[H]$. We will find it convenient to move the stage $h$ into the index. In particular, for policies, we will also write $\pi_{h}(s)$ for $\pi(s,h)$ but we will use the same convention for other similar objects, like the value function, defined next.

In online RL, a good agent of course uses all past observations to come up with its decisions. The performance of such an agent is measured by its regret, which is the total reward the agent misses because they did not follow the optimal policy from the beginning. In particular, the total expected regret of an agent $\mathcal{A}$ across $K$ episodes is given by

where $T=KH$ is the total number of time steps that the agent interacts with its environment, $s_{1}^{k}=s_{\circ}$ is the initial state at the start of the $k$-th episode, and $s_{1}^{1},a_{1}^{1},\ldots,s_{H}^{k},a_{H}^{k},\ldots,s_{1}^{K},a_{1}^{K},\ldots,s_{H}^{K},a_{H}^{K}$ are the $T=KH$ state-action pairs in the order that they are encountered by the agent. The regret is sublinear of $R(T)/T\to 0$ as $T\to\infty$. For a fixed $T$, let $R^{*}(T)$ denote the worst-case regret. As is well known, no matter the algorithm used, $R^{*}(T)$, grows at least as fast as $\sqrt{T}$ (e.g., Jaksch et al., 2010).

In this paper, we aim to design a general model-based reinforcement learning algorithm, with a guaranteed sublinear regret, for any given family of transition models.

The unknown transition model $P$ belongs to a family of models $\mathcal{P}$ which is available to the learning agent. The elements of $\mathcal{P}$ are transition kernels mapping state-action pairs to signed distributions over $\mathcal{S}$.

That we allow signed distributions increases the generality; this may be important when one is given a model class that can be compactly represented but only when it also includes non-probability kernels (see Pires & Szepesvári 2016 for a discussion of this).

An important special case is the class of linear mixture models:

for all $(s,a)\in\mathcal{S}\times\mathcal{A}$.

Parametric and nonparametric transition models are common in modelling complex stochastic controlled systems. For one example, robotic systems are often smoothly parameterized by unknown mechanical parameters such as friction, or just parameters that describe the geometry of the robot.

The linear mixture model can be viewed as a way of aggregating a number of known basis models as considered by Modi et al. (2019). We can view each $P_{j}(\cdot|\cdot)$ as a basis latent “mode” and the actual transition is a probabilistic mixture of these latent modes. For another example, consider large-scale queueing networks where the arrival rate and job processing speed for each queue is not known. By using a discrete-time Bernoulli approximation, the transition probability matrix from time $t$ to $t+\Delta t$ becomes increasingly close to linear with respect to the unknown arrival/processing rates as $\Delta t\to 0$. In this case, it is common to model the discrete-time state transition as a linear aggregation of arrival/processing processes with unknown parameters Kovalenko (1968).

Another interesting special case is the linear-factored MDP model of Yang & Wang (2019a) where, assuming a discrete state space for a moment, $P$ takes the form

Upper Confidence RL with Value-Targeted Model Regression

Our algorithm can be viewed as a generalization of UCRL (Jaksch et al., 2010), following ideas of Osband & Van Roy (2014).

In particular, at the beginning of episode $k=1,2,\dots,K$, the algorithm first computes a subset $B_{k}$ of the model class $\mathcal{P}$ that contains the set of models that are deemed to be consistent with all the data that has been collected in the past. The new idea, value-targeted regression is used in the construction of $B_{k}$. The details of how this is done are postponed to a later section.

Next, the algorithm needs to find the model that maximizes the optimal value, and the corresponding optimal policy. Denoting by $V^{*}_{P}$ the optimal value function under a model $P$, this amounts to finding the model $P\in B_{k}$ that maximizes the value $V^{*}_{P,1}(s_{1}^{k})$. Given the model $P_{k}$ that maximizes this value, an optimal policy is extracted from the model as described in the next section (this is standard dynamic programming). At the end of the episode, the data collected is used to refine the confidence set $B_{k}$. The pseudocode of the algorithm can be found in Algorithm 1.

Upper confidence methods are prominent in online learning. In our algorithm, we will maintain a confidence set $B_{k}$ for the estimated transition model and use it for optimistic planning:

where $s_{1}^{k}$ is the initial state at the beginning of episode $k$ and we use $V^{*}_{P^{\prime},1}$ to denote the optimal value function of stage one, when the transition model is $P^{\prime}$. Given model $P_{k}$, the optimal policy for $P_{k}$ can be computed using dynamic programming. In particular, for $1\leq h\leq H+1$, define

where we with a measure $\mu$ and function $f$ over the same domain, we use $\langle\mu,f\rangle$ to denote the integral of $f$ with respect to $\mu$. Then, taking the action at stage $h$ and state $s$ that maximizes $Q_{h,k}(s,\cdot)$ gives an optimal policy for model $P_{k}$. As long as $P\in B_{k}$ with high probability, the preceding calculation gives an optimistic (that is, upper) estimate of value of an episode. Next we show how to construct the confidence set $B_{k}$.

2 Value-Targeted Regression for Confidence Set Construction

Every time we observe a transition $(s,a,s^{\prime})$ with $s^{\prime}\sim P(\cdot|s,a)$, we receive information about the model $P$. Instead of regression onto fixed target like probabilities or raw states, we will refresh the model estimate by regression using the estimated value functions as target.

In the above regression procedure, the regret target keeps changing as the algorithm constructs increasingly accurate value estimates. This is in contrast to typical supervised learning for building models, where the regression targets are often fixed objects (such as raw observations, features or keypoints; e.g. Jaksch et al. (2010); Osband & Van Roy (2014); Abbasi-Yadkori & Szepesvári (2015); Xie et al. (2016); Agrawal & Jia (2017); Yang & Wang (2019a); Kaiser et al. (2019)).

For a confidence set construction, we get inspiration from Proposition 5 in the paper of Osband & Van Roy (2014). The set is centered at $\hat{P}_{k+1}$.Define

and the value of $\beta_{k}$ can be obtained using a calculation similar to that done in Proposition 5 of the paper of Osband & Van Roy (2014), which is based on the nonlinear least-squares confidence set construction from Russo & Van Roy (2014), which we describe in the appendix.

It is not hard to see that the confidence set can also be written in the alternative form

Note that the above formulation strongly exploits that the MDP is time-homogeneous: The same transition model is used at all stages of an episode. When the MDP is time-inhomogeneous, the construction can be easily modified to accommodate that the transition kernel may depend on the stage index.

3 Implementation of UCRL-VTR

Algorithm 1 gives a general and modular template for model-based RL that is compatible with regression methods/optimistic planners. While the algorithms is conceptually simple, and the optimization and evaluation of the loss in value-targeted regression appears to be at advantage in terms of computation as compared to standard losses typically used in model-based RL, the implementation of UCRL-VTR is nontrivial in general and for now it requires a case-by-base design.

Computation efficiency of the algorithm depends on the specific family of models chosen. For the linear-factor MDP model considered by Yang & Wang (2019a), the regression is linear and admits efficient implementation; further, optimistic planning for this model can be implemented in $\text{poly}(d)$ time by using Monte-Carlo simulation and sketching as argued in the cited paper. Other ideas include loosening the confidence set to come up with computationally tractable methods, or relaxing the requirement that the same model is used in all stages.

In the general case, optimistic planning is computationally intractable. However, we expect that randomized (eg Osband et al. (2017, 2014); Lu & Van Roy (2017)) and approximate dynamic programming methods (tree search, roll out, see eg Bertsekas & Tsitsiklis (1996)) will often lead to tractable and good approximations. As was mentioned above, in some special cases these have been rigorously shown to work. In similar settings, the approximation errors are known to mildly impact the regret Abbasi-Yadkori & Szepesvári (2015) and we expect the same will hold in our setting.

If we look beyond methods with rigorous guarantees, there are practical deep RL algorithms that implement parts of UCRL-VTR. As mentioned earlier, the Muzero algorithm of Schrittwieser et al. (2019) is a state-of-the-art algorithm on the Atari domain and this algorithm implements both value-targeted-regression to learn a model and Monte Carlo tree search for planning based on the learned model, although it does not incorporate optimistic planning.

Theoretical Analysis

We will need the concept of Eluder dimension. Let $\mathcal{F}$ be a set of real-valued functions with domain $\mathcal{X}$. To measure the complexity of interactively identify an element of $\mathcal{F}$, Russo & Van Roy (2014) defines the Eluder dimension of $\mathcal{F}$ at scale $\epsilon>0$. For $f\in\mathcal{F}$, $x_{1},\dots,x_{t}\in\mathcal{X}$, introduce the notation $f|_{(x_{1},\dots,x_{t})}=(f(x_{1}),\dots,f(x_{t}))$. We say that $x\in\mathcal{X}$ is $\epsilon$-independent of $x_{1},\dots,x_{t}\in\mathcal{X}$ given $\mathcal{F}$ if there exists $f,f^{\prime}\in\mathcal{F}$ such that $\|(f-f^{\prime})|_{(x_{1},\dots,x_{t})}\|_{2}\leq\epsilon$ while $f(x)-f^{\prime}(x)>\epsilon$.

The Eluder dimension $\operatorname{dim_{\mathcal{E}}}(\mathcal{F},\epsilon)$ of $\mathcal{F}$ at scale $\epsilon$ is the length of the longest sequence $(x_{1},\dots,x_{n})$ in $\mathcal{X}$ such that for some $\epsilon^{\prime}\geq\epsilon$, for any $2\leq t\leq n$, $x_{t}$ is $\epsilon^{\prime}$-independent of $(x_{1},\dots,x_{t-1})$ given $\mathcal{F}$.

Note that $\mathcal{F}\subset\mathcal{B}(\mathcal{X},H)$. For a norm $\|\cdot\|$ on $\mathcal{F}$ and $\alpha>0$ let $\mathcal{N}(\mathcal{F},\alpha,\|\cdot\|)$ denote the $(\alpha,\|\cdot\|)$-covering number of $\mathcal{F}$. That is, this if $m=\mathcal{N}(\mathcal{F},\alpha,\|\cdot\|)$ then one can find $m$ points of $\mathcal{F}$ such that any point in $\mathcal{F}$ is at most $\alpha$ away from one of these points in norm $\|\cdot\|$. Denote by $\|\cdot\|_{\infty}$ the supremum norm: $\|f\|_{\infty}=\sup_{x\in\mathcal{X}}|f(x)|$.

Now we analyze the regret of UCRL-VTR. Define the $K$-episode pseudo-regret as

Let Assumption 1 hold and let $\alpha\in(0,1).$ For $k\in[K]$, let $\beta_{k}$ be

where $d=\operatorname{dim_{\mathcal{E}}}(\mathcal{F},\alpha)$ is the Eluder dimension with $\mathcal{F}$ given by (5).

A typical choice of $\alpha$ is $\alpha=1/(KH)$. In the special case of linear transition model, Theorem 1 implies a worst-case regret bound that depends linearly on the number of parameters.

We also provide a lower bound for the regret in our model. The proof is by reduction to a known lower bound and is left to Appendix B.

For any $H\geq 1$ and $d\geq 8$, there exist a state space $\mathcal{S}$ and action set $\mathcal{A}$, a reward function $r:\mathcal{S}\times\mathcal{A}\to$, $d$ transition models $P_{1},\dots,P_{d}$ and a set $\Theta$ of diameter at most one such that for any algorithm there exists $\theta\in\Theta$ such that for sufficiently large number of episodes $K$, the expected regret of the algorithm on the $H$-horizon MDP with reward $r$ and transition model $P=\sum_{j}\theta_{j}P_{j}$ is at least $\Omega(H\sqrt{dK})$.

Rusmevichientong & Tsitsiklis (2010) gave a regret lower bound of $\Omega(d\sqrt{T})$ for linearly parameterized bandit with actions on the unit sphere (see also Section 24.2 of Lattimore & Szepesvári (2020)). Our regret upper bound matches this bandit lower bound in $d,T$. Whether the upper or lower bound is tight (or none of them) remains to be seen.

The theorems validate that, in the setting we consider, it is sufficient to use the predicted value functions as regression targets. That for the special case of linear mixture models the lower bound is close to the upper bound appears to suggest that little benefit if any can be derived from fitting the transition model to predict well future observations. We conjecture that this is in fact true when considering the worst-case regret. Of course, a conclusion that is concerned with the worst-case regret has no implication for the behavior of the respective methods on particular MDP instances.

We note in passing that by appropriately increasing $\beta_{k}$, the regret upper bounds can be extended to the so-called misspecified case when $P$ can be outside of $\mathcal{P}$ (for related results, see, e.g., Jin et al. 2019; Lattimore & Szepesvári 2019). However, the details of this are left for future work.

Related Work

A number of prior efforts have established efficient RL methods with provable regret bounds. For tabular MDPs with $S$ states and $A$ actions, building on the pioneering work of Jaksch et al. (2010) who studied the technically more challenging continuing setting, a number of works obtained results for the episodic setting, both with model-based (e.g., Osband et al. 2014; Azar et al. 2017; Dann et al. 2017, 2018; Agrawal & Jia 2017), and model-free methods (e.g., Jin et al. 2018; Russo 2019; Zhang et al. 2020), both for the time-homogeneous case (i.e., the same transition kernel governs the dynamics in all stages of the $H$-horizon episode) and the time-inhomogeneous case. Results developed for the time-inhomogeneous case apply to the time-inhomogeneous case and since in this case the number of free parameters to learn is at least $H$ times larger than for the time-homogeneous case, the regret bounds are expected to be $\sqrt{H}$ larger.

As far as regret lower bounds are concerned, Jaksch et al. (2010) established a worst-case regret lower bound of $\Omega(\sqrt{DSAT})$ for the continuing case for MDPs with diameter bounded by $D$ (see also Chapter 38 of Lattimore & Szepesvári 2020). This lower bound can be adapted to the episodic by setting $D=H$. This way one obtains a lower bound of $\Omega(\sqrt{HSAT})$ for the homogeneous, and $\Omega(\sqrt{H^{2}SAT})$ for the inhomogeneous case (because here the state space size is effectively $HS$). This lower bound, up to lower order terms, is matched by upper bounds both for the time-homogeneous case (Azar et al., 2017; Kakade et al., 2018) and the time inhomogeneous case (Dann et al., 2018; Zhang et al., 2020). Except the work of Zhang et al. (2020), these results are achieved by algorithms that estimate models. With a routine adjustment, the near-optimal model-based algorithms available for the homogeneous case are also expected to deliver near-optimal worst-case regret growth in the inhomogeneous case. A further variation is obtained by considering different scalings of the reward (Wang et al., 2020a).

As for RL with a general model class, the seminal paper Osband & Van Roy (2014) provided a general posterior sampling RL method that works for any given classes of reward and transition functions. It established a Bayesian regret upper bound $O(\sqrt{d_{K}d_{E}T})$, where $d_{K}$ and $d_{E}$ are the Kolmogorov and the Eluder dimensions of the model class. In the case of linearly parametrized transition model (Assumption 2 of this paper), this Bayesian regret becomes $O(d\sqrt{T})$, and our worst-case regret result matches with the Bayesian one. Abbasi-Yadkori & Szepesvári (2015); Theocharous et al. (2017) also considered the Bayesian regret and in particular Abbasi-Yadkori & Szepesvári (2015) considered a smooth parameterization with a somewhat unusual definition of smoothness. To the authors’ best knowledge, there are no prior works addressing the problem of designing low-regret algorithms for MDPs with a general model family. In particular, while Osband & Van Roy (2014) sketch the main ideas of an optimistic model-based optimistic algorithm for a general model class, they left out the details. When the details are filled based on their approach for the Bayesian case, unlike in the present work, the confidence sets would be constructed by losses that measure how well the model predict future observations and not by the value-targeted regression loss studied here. A preliminary version of the present paper appeared at L4DC 2020, which included results for the linear transition model only.

Numerical Experiments

The algorithms that we compare have a model-fitting objective which is either used to fit a nominal model or to calculate confidence sets. The objective is either to minimize mean-squared error of predicting next states (alternatively, maximize log-likelihood of observed data), which leads to standard frequency based model estimates, or it is based on minimizing the value targets as proposed in our paper. The other component of the algorithms is whether they implement optimistic planning, or planning with the nominal model and then implementing an $\epsilon$-greedy policy with respect to the estimated model (“dithering”). We also consider mixing value targets and next state targets. In the case of optimistic planning, the algorithm that uses mixed targets uses a union bound and takes the smallest value upper confidence bounds amongst the two bounds obtained with the two model-estimation methods. These leads to six algorithms, as shown in Table 1. Results for the “mixed” variants are very similar to the variant that uses value-targeted regression. As such, the results for the “mixed” variants are shown in the appendix only, as they would otherwise make the graphs overly cluttered.

In the experiments we use confidence bounds that are specialized to the linear case. For the details, see Appendix C. For $\epsilon$-greedy, we optimize the value of $\epsilon$ in each environment to get the best results. This gives $\epsilon$-greedy an unfair advantage; but as we shall see despite this advantage, $\epsilon$-greedy will not fair particularly well in our experiments.

We compare these algorithms on the episodic RiverSwim environment due to Strehl & Littman (2008) and a novel finite horizon MDP we tentatively call WideTree. The RiverSwim environment, whose detailed description is given below in Section 6.3, is chosen because it is known that in this environment “dithering” type exploration methods (e.g., $\epsilon$-greedy) are ineffective. We vary the number of states in the RiverSwim environment in order to highlight some of the advantages and disadvantages of Value-Targeted Regression.

WideTree is designed in order it highlight the advantages of Value-Targeted Regression when compared with more tradition frequency based methods. In this environment, only one action effects the outcome thus the other actions are non-informative. The detailed description of WideTree is given in Section 6.4.

2 Measurements

We report the cumulative regret as a function of the number of episodes and the weighted model error to indicate how well the model is learned. The results are obtained from $30$ independent runs for the $\epsilon$-greedy algorithms and $10$ independent runs for the UC algorithms, The weighted model error reported is as follows. Given the model estimate $\hat{P}$, its weighted error is

where $N(s,a)$ is the observation-count of the state-action pair $(s,a)$, $N(s,a,s^{\prime})$ is the count of transitioning to $s^{\prime}$ from $(s,a)$, and $P^{*}(s^{\prime}\mid s,a)$ is the probability of $s^{\prime}$ when action $a$ is chosen in state $s$, according to the true model. Here, for the algorithms that use value-targeted regression the estimated model $\hat{P}$ is the model obtained through Eq. (4). The weighting is introduced so that an algorithm that discards a state-action pair is not penalized. This is meant to prevent penalizing good exploration algorithms that may quickly discard some state-action pairs. We are interested in this error metric to monitor whether UCLR-VTR, which is not forced to model next-state distributions, will learn the proper next state distribution. In fact, we will see one example both for the case when this and also when this does not happen.

3 Results for RiverSwim

The schematic diagram of the RiverSwim environment is shown in Figure 1. RiverSwim consists of $S$ states arranged in a chain. The agent begins on the far left and has the choice of swimming left or right at each state. There is a current that makes swimming left much easier than swimming right. Swimming left with the current always succeeds in moving the agent left, but swimming right against the current sometimes moves the agent right (with a small probability of moving left as well), but more often than not leaves the agent in the current state. Thus smart exploration is a necessity to learn a good policy in this environment.

We experiment with small environments with $S\in\{3,4,5\}$ states and set the horizon to $4S$ for each case. The optimal values of the initial state are $5.72$, $5.66$ and $5.6$, respectively, in these cases. The initial state is the leftmost state ($s_{1}$ in the diagram). The value that we found to work the best for $\epsilon$ greedy is $\epsilon=0.01$.

Results are shown in Figure 2, except for UCRL-Mixed and EG-Mixed, whose results are given in Appendix D. As noted before, the results of these algorithms are very close to those of the VTR-versions, hence, they are not included here. The columns correspond to environments with $S=3$, $S=4$ and $S=5$, respectively, which are increasingly more challenging. The first row shows the algorithm’s performance measured in terms of their respective cumulative regrets, the second row shows results for the weighted model error as defined above. The regret per episode for an algorithm that “does not learn” is expected to be in the same range as the respective optimal values. Based on this we see that $10^{5}$ episodes is barely sufficient for the algorithms other than UCRL-VTR to learn a good policy. Looking at the model errors we see that EGRL-VTR is doing quite poorly, EG-Freq is also lacking (especially on the environment with $5$ states), the others are doing reasonably well. That EG-Freq is not doing well is perhaps surprising. However, this is because EG-Freq visits more uniformly than the other methods the various state-action pairs.

The results clearly indicate that (i) fitting to the state-value function alone provides enough of a signal for learning as evident by UCRL-VTR obtaining low regret as predicted by our theoretical results, and that (ii) optimism is necessary when using value targeted regression to achieve good results, as evident by UCRL-VTR achieving significantly better regret than EGRL-VTR and even in the smaller RiverSwim environment where EG-Freq performed best.

It is also promising that value-targeted regression with optimistic exploration outperformed optimism based on the “canonical” model estimation procedure. We attribute this to the fact that value-targeted regression will learn a model faster that predicts the optimal values well than the canonical, frequency based approach.

That value-targeted regression also learns a model with small weighted error appears to be an accidental feature of this environment. Our next experiments are targeted at further exploring this effect.

4 WideTree

We introduce a novel tabular MDP we call WideTree. The WideTree environment has a fixed horizon $H=2$ but can vary in the number of states. A visualization of an eleven state WideTree environment is shown in Figure 3.

In WideTree, an agent starts at the initial state $s_{1}$. The agent then progresses to one of the many bottom terminal states and collects a reward of either 0 or 1 depending on the action selected at state $s_{1}$. The only significant action is whether to transition from $s_{1}$ to either $s_{2}$ or $s_{3}$. Note that the model in the second layer is irrelevant for making a good decision: Once in $s_{3}$, all actions lead to a reward of one, and once in $s_{2}$, all actions lead to a reward of zero. We vary the number of bottom states reachable from states $s_{2}$ and $s_{3}$ while still maintaining a reward structure depending on whether the algorithm choose to transition to either $s_{2}$ or $s_{3}$ from the initial state $s_{1}$.

We set $\epsilon=0.1$ in this environment, though choosing smaller $\epsilon$ but as long as $\epsilon>0$ then both EGRL-VTR and EG-Freq will incur linear regret dependent on the choice of $\epsilon$. One could also change the reward function in order to make learning for a given $\epsilon$ hard.

The results are shown in Figure 4, except for UCRL-Mixed and EG-Mixed, whose results are given in Appendix D. Both UCRL-VTR and EG-VTR learn equally poor models (their graphs are ‘on the top of each other’). Yet, UCRL-VTR manages to quickly learn a good policy, as attested by its low regret.

EG-Freq and EG-VTR perform equally poorly and UC-MatrixRL is even slower as it keeps exploring the environment. These experiments clearly illustrate that UCRL-VTR is able to achieve good results without learning a good model – its focus on values makes pays off swiftly in this well-chosen environment.

Conclusions

Acknowledgements

Csaba Szepesvári gratefully acknowledges funding from the Canada CIFAR AI Chairs Program, Amii and NSERC.

References

Appendix A Proof of Theorem 1

In this section, we provide the regret analysis of the UCRL-VTR Algorithm (Algorithm 1). We will explain the motivation for our construction of confidence sets for general nonlinear squared estimation, and establish the regret bound for a general class of transition models, $\mathcal{P}$.

Given any policy $\pi$ (which may or may not use the history), its value function is

where $E_{\pi,\delta_{s}}$ is the expectation operator underlying the probability measure $P_{\pi,\delta_{s}}$ induced over sequences of state-action pairs of length $H$ by executing policy $\pi$ starting at state $s$ in the MDP $M$ and $s_{h}$ is the state visited in stage $h$ and action $a_{h}$ is the action taken in that stage after visiting $s_{h}$. For a nonstationary Markov policy $\pi=(\pi_{1},\dots,\pi_{H})$, we also let

be the value function of $\pi$ from stage $h$ to $H$. Here, $\pi_{h:H}$ denotes the policy $(\pi_{h},\dots,\pi_{H})$. The optimal value function $V^{*}=(V^{*}_{1},\dots,V^{*}_{H})$ is defined via $V^{*}_{h}(s)=\max_{\pi}V^{\pi}_{h}(s)$, $s\in\mathcal{S}$.

For simplicity assume that $r$ is known. To indicate the dependence of $V^{*}$ on the transition model $P$, we will write $V^{*}_{P}=(V^{*}_{P,1},\dots,V^{*}_{P,H})$. For convenience, we define $V^{*}_{P,H+1}=0$.

Algorithm 1 is an instance of the following general model-based optimistic algorithm:

Specific instances of Algorithm 2 differ in terms of how $\mathcal{B}_{k+1}$ is constructed. In particular, UCRL-VTR uses the construction described in Section 3.2.

Recall that $V_{k}=(V_{1,k},\dots,V_{H,k},V_{H+1,k})$ (with $V_{H+1,k}=0$) in Algorithm 2. Let $\pi_{k}$ be the nonstationary Markov policy chosen in episode $k$ by Algorithm 2. Let

be the pseudo-regret of Algorithm 1 for $K$ episodes. The following standard lemma bounds the $k$th term of the expression on the right-hand side.

Assuming that $P\in\mathcal{B}_{k}$, we have

Note that $(\xi_{2,1},\xi_{3,1},\dots,\xi_{H,1},\xi_{2,2},\xi_{3,2},\dots,\xi_{H,2},\xi_{2,3},\dots)$ is a sequence of martingale differences.

Because $P\in\mathcal{B}_{k}$, $V_{1}^{*}(s_{1}^{k})\leq V_{1,k}(s_{1}^{k})$ by the definition of the algorithm. Hence,

Fix $h\in[H]$. In what follows we bound $V_{h,k}(s_{h}^{k})-V_{h}^{\pi_{k}}(s_{h}^{k})$. By the definition of $\pi_{k}$, $P^{k}$ and $a_{h}^{k}$, we have

Therefore, by induction, noting that $V_{H+1,k}=0$, we get that

A.2 The confidence sets for Algorithm 1

The previous lemma suggests that at the end of the $k$th episode, the model could be estimated using

For a confidence set construction, we get inspiration from Proposition 5 in the paper of Osband & Van Roy (2014). The set is centered at $\hat{P}_{k}$:

Note that this is the same confidence set as described in Section 3.2. To obtain the value of $\beta_{k}$, we now consider the nonlinear least-squares confidence set construction from Russo & Van Roy (2014). The next section is devoted to this construction.

A.3 Confidence sets for general nonlinear least-squares

We have the following theorem, the proof of which is given in Section A.6.

The proof follows that of Proposition 6, Russo & Van Roy (2014), with minor improvements, which lead to a slightly better bound. In particular, with our notation, Russo & Van Roy stated their result with

While $\beta_{t}(\delta,\alpha)\leq\beta_{t}^{\text{RvR}}(\delta,\alpha)$, the improvement is only in terms of smaller constants.

To use this result in our RL problem recall that $\mathcal{P}$ is the set of transition probabilities parameterized by $\theta\in\Theta$. We index time $t=1,2,\dots$ in a continuous fashion. Episode $k=1,2,\dots$ and stage $h=1,\dots,H-1$ corresponds to time $t=(k-1)(H-1)+h$:

Note that the transitions at stage $h=H$ are skipped and the time index at the end of episode $k\geq 1$ is $k(H-1)$.

Let $V_{(t)}$ be the value function used by Algorithm 1 at time $t$ ($V_{(t)}$ is constant in periods of length $H-1$), while let $(s_{(t)},a_{(t)})$ be the state-action pair visited at time $t$.

Let $\mathcal{V}$ be the set of optimal value functions under some model in $\mathcal{P}$: $\mathcal{V}=\{V^{*}_{P^{\prime}}\,:\,P^{\prime}\in\mathcal{P}\}$. Note that $\mathcal{V}\subset\mathcal{B}(\mathcal{S},H)$, where $\mathcal{B}(\mathcal{S},H)$ denotes the set of real-valued measurable functions with domain $\mathcal{S}$ that are bounded by $H$. Note also that for all $t$, $V_{(t)}\in\mathcal{V}$. Define $\mathcal{X}=\mathcal{S}\times\mathcal{A}\times\mathcal{V}$. We also let $X_{t}=(s_{(t)},a_{(t)},V_{(t)})$, $Y_{t}=V_{(t)}(s_{(t+1)})$ when $t+1\not\in\{H+1,2H+1,\dots\}$ and $Y_{t}=V_{(t)}(s_{H+1}^{k})$, and choose

Note that $\mathcal{F}\subset\mathcal{B}_{\infty}(\mathcal{X},H)$.

Let $\phi:\mathcal{P}\to\mathcal{F}$ be the natural surjection to $\mathcal{F}$: $\phi(P)=f$ where $f(s,a,v)=\int P_{a}(ds^{\prime}|s)v(s^{\prime})$ for $(s,a,v)\in\mathcal{X}$. We know show that $\phi$ is in fact a bijection. If $P\neq P^{\prime}$, this means that for some $(s,a)\in\mathcal{S}\times\mathcal{A}$ and $U\subset\mathcal{S}$ measurable, $P_{a}(U|s)\neq P_{a}^{\prime}(U|s)$. Choosing $v$ to be the indicator of $U$, note that $(s,a,v)\in\mathcal{X}$. Hence, $\phi(P)(s,a,v)=P_{a}(U|s)\neq P_{a}^{\prime}(U|s)=\phi(P^{\prime})(s,a,v)$, and hence $\phi(P)\neq\phi(P^{\prime})$: $\phi$ is indeed a bijection. For convenience and to reduce clutter, we will write $f_{P}=\phi(P)$.

Let $t=k(H-1)$ for some $k\geq 1$. Thus, this time step corresponds to finishing episode $k$ and thus $V_{(t)}=V_{k}$. Furthermore, letting $\hat{f}_{t}=\operatorname{argmin}_{f\in\mathcal{F}}\sum_{p=1}^{t}(f(X_{p})-Y_{p})^{2}$, since $\phi$ is an injection, we see that $\hat{f}_{t}=f_{\hat{P}_{k}}$ where $\hat{P}_{k}$ is defined using (8). For $P^{\prime},P^{\prime\prime}\in\mathcal{P}$, we have $L_{k}(P^{\prime},P^{\prime\prime})=\sum_{p=1}^{t}(f_{P^{\prime}}(X_{p})-f_{P^{\prime\prime}}(X_{p}))^{2}$ and thus

Then, with probability $1-\delta$, for any $k\geq 1$, $P\in\mathcal{B}_{k}$ where $\mathcal{B}_{k}$ is defined by (9).

A.5 Regret of Algorithm 1

Let $\mathcal{F}\subset B_{\infty}(\mathcal{X},C)$ be a set of functions bounded by $C>0$, $(\mathcal{F}_{t})_{t\geq 1}$ and $(x_{t})_{t\geq 1}$ be sequences such that $\mathcal{F}_{t}\subset\mathcal{F}$ and $x_{t}\in\mathcal{X}$ hold for $t\geq 1$. Then, for any $T\geq 1$ and $\alpha>0$ it holds that

where $\delta_{T}=\max_{1\leq t\leq T}\operatorname{diam}(\mathcal{F}_{t}|_{x_{1:t}})$ and $d=\operatorname{dim_{\mathcal{E}}}(\mathcal{F},\alpha)$.

Let $\alpha>0$ and $d=\operatorname{dim_{\mathcal{E}}}(\mathcal{F},\alpha)$ where $\mathcal{F}$ is given by (10). Then, for any nondecreasing sequence $(\beta_{k}^{2})_{k=1}^{K}$, on the event when $P\in\cap_{k\in[K]}\mathcal{B}_{k}$,

Note that for any $k\in[K]$ and $h\in[H-1]$, $\xi_{h+1},k\in[-H,H]$. As noted beforehand, $\xi_{2,1},\xi_{3,1}$, $\dots,\xi_{H,1},\xi_{2,2},\xi_{3,2},\dots,\xi_{H,2},\xi_{2,3},\dots$ is a martingale difference sequence. Thus, with probability $1-\delta$, $\sum_{k=1}^{K}\sum_{h=1}^{H-1}\xi_{h+1,k}\leq H\sqrt{2K(H-1)\log(1/\delta)}$. Consider the event when this inequality holds and when $P\in\cap_{k\in[K]}\mathcal{B}_{k}$. By using Corollary 6 and a union bound, this event holds with probability at least $1-2\delta$. On this event, by (11) and Lemma 8, we obtain

Using $\alpha\leq 1$, which holds by assumption, finishes the proof. ∎

A.5.2 Proof of Corollary 2

For $\alpha>0$ let $\mathcal{N}(\mathcal{P},\alpha,\|\cdot\|_{\infty,1})$ denote the $(\alpha,\|\cdot\|_{\infty,1})$-covering number of $\mathcal{P}$. Then we have

with some universal constant $C>0$. Let $f:(\Theta,\|\cdot\|)\to(\mathcal{P},\|\cdot\|_{\infty,1})$ be defined by $\theta\mapsto\sum_{j}\theta_{j}P_{j}$. Note that $\|f(\theta)-f(\theta^{\prime})\|_{\infty,1}\leq\sup_{s,a}\sum_{j}\|(\theta_{j}-\theta_{j}^{\prime})P_{j,a}(s)\|_{1}=\sum_{j}|\theta_{j}-\theta_{j}^{\prime}|=\|\theta-\theta^{\prime}\|_{1}$. Hence, any $(\epsilon,\|\cdot\|_{1})$ covering of $\Theta$ induces an $(\epsilon,\|\cdot\|_{\infty,1})$-covering of $\mathcal{P}$ and so $\mathcal{N}(\mathcal{P},\alpha/H,\|\cdot\|_{\infty,1})\leq\mathcal{N}(\Theta,\alpha/H,\|\cdot\|_{1})\leq C^{\prime}(RH/\alpha)^{d}$ with some universal constant $C^{\prime}>0$.

Now, choose $1/\alpha=K\sqrt{\log(KH/\delta)}$. Hence,

Suppressing $\log$ factors (e.g., $\log(RH)$), $\log\log$ terms and constants, we have $\beta_{K}=H^{2}(d+\log(1/\delta))$.

Plugging into Theorem 1 gives the desired result. ∎

A.6 Proof of Theorem 5

The proof of the next couple of statements is standard and is included only for completeness.

If $X$ is $\sigma$-subgaussian, then for any $\lambda>0$, with probability at least $1-\delta$,

Choosing the $\lambda$ that minimizes the right-hand side of the bound gives the usual form:

Suppose that $X$ is $\sigma$-subgaussian and $X_{1}$ and $X_{2}$ are independent and $\sigma_{1}$ and $\sigma_{2}$-subgaussian, respectively, then:

$X_{1}+X_{2}$ is $\sqrt{\sigma_{1}^{2}+\sigma_{2}^{2}}$-subgaussian.

A standard calculation gives that $S_{t}=\sum_{p=1}^{t}Z_{p}$ is $\sqrt{t}\sigma$-subgaussian (essentially, a refinement of the calculation that is need to show Part (3) of Lemma 10) and thus, in particular, for any $t\geq 1$ and $\lambda>0$, with probability $1-\delta$,

In fact, by slightly strengthening the argument, one can show that the above inequality holds simultaneously for all $t\geq 1$:

Splitting $\|f_{*}-f\|_{t}^{2}$ and rearranging gives

Recall that $\hat{f}_{t}=\operatorname{argmin}_{f\in\mathcal{F}}\|Y-f\|_{t}^{2}$. Plugging $\hat{f}_{t}$ into 15 in place of $f$ and using that thanks to $f_{*}\in\mathcal{F}$, $\|Y-\hat{f}_{t}\|_{t}^{2}\leq\|Y-f_{*}\|_{t}^{2}$, we get

Thus, it remains to bound $E(\hat{f}_{t})$. For this fix some $\alpha>0$ to be chosen later and let $\mathcal{G}(\alpha)\subset\mathcal{F}$ be an $\alpha$-cover of $\mathcal{F}$ in $\|\cdot\|_{\infty}$. Let $g\in\mathcal{G}(\alpha)$ be a random function, also to be chosen later. We have

We start by bounding the last term above. A simple calculation gives that for any fixed $f\in\mathcal{F}$, w.p. $1-\delta$, $2\langle Z,f-f_{*}\rangle_{t}$ is $2\sigma\|f-f_{*}\|_{t}$-subgaussian. Hence, with probability $1-\delta$, simultaneously for all $t\geq 1$,

where the equality follows by choosing $\lambda=1/(4\sigma^{2})$ (which makes the first and last terms cancel). (Note how splitting $\|f-f_{*}\|_{t}^{2}$ into two halves allowed us to bound the “error term” $E(f)$ independently of $t$.) Now, by a union bound, it follows that with probability at least $1-\delta$, the second term is bounded by $4\sigma^{2}\log(|\mathcal{G}(\alpha)|/\delta)$.

Let us now turn to bounding the first term. We calculate

It remains to bound $\|Z\|_{t}$. For this, we observe that with probability $1-\delta$, simultaneously for all $t\geq 1$,

Indeed, this follows because with probability $1-\delta$, simultaneously for any $s\geq 1$, $|Z_{p}|^{2}\leq 2\sigma^{2}\log(2s(s+1)/\delta)$ holds because of a union bound and Eq. (13). Therefore, for the above choice $g$, with probability $1-\delta$, simultaneously for all $t\geq 1$, it holds that

Merging this with Eqs. (16) and (17) and with another union bound, we get that with probability $1-\delta$, for any $t\geq 1$,

where $N_{\alpha}$ is the $(\alpha,\|\cdot\|_{\infty})$-covering number of $\mathcal{F}$. ∎

Appendix B Proof of Theorem 3

In this section we establish a regret lower bound by reduction to a known result for tabular MDP.

We assume without loss of generality that $d$ is a multiple of 4 and $d\geq 8$. We set $S=2$ and $A=d/4\geq 2$. According to Azar et al. (2017), Osband & Van Roy (2016), there exists an MDP $\mathcal{M}(\mathcal{S},\mathcal{A},P,r,H)$ with $S$ states, $A$ actions and horizon $H$ such that any algorithm has regret at least $\Omega(\sqrt{HSAT})$. In this case, we have $|\mathcal{S}\times\mathcal{A}\times\mathcal{S}|=d$. We use $\sigma(s,a,s^{\prime})$ to denote the index of $(s,a,s^{\prime})$ in $\mathcal{S}\times\mathcal{A}\times\mathcal{S}$. Letting

and $\theta^{i}=P(s^{\prime}|s,a)$ if $\sigma(s,a,s^{\prime})=i$, we will have $P(s^{\prime}|s,a)=\sum_{i=1}^{d}\theta^{i}P_{i}(s^{\prime}|s,a).$ Therefore $P$ can be parametrized using (2). Therefore, the known lower bound $\Omega(\sqrt{HSAT})$ implies a worst-case lower bound of $\Omega(\sqrt{H\cdot d/2\cdot T})=\Omega(\sqrt{HdT})$ for our model.

Appendix C Implementation

In the implementation of UCRL-VTR used in Section 6, we used different confidence intervals then the ones stated in the paper. The confidence intervals used in our implementation are the ones introduced in Abbasi-Yadkori et al. (2011). These confidence intervals are much tighter in the linear setting than the ones introduced in Section 3 and thus have better practical performance. The purpose of this section is to formally introduce the confidence intervals used in our implementation of UCRL-VTR as well as show how these confidence intervals were adapted from the linear bandit setting to the linear MDP setting.

For our implementation of UCRL-VTR we used different confidence then was introduced in the paper. These are the tighter confidence bounds from the seminal work done by Abbasi-Yadkori et al. (2011) and further expanded upon in Chapter 20 of Lattimore & Szepesvári (2020). Now we will state some assumptions in the MDP setting, then we will state the equivalent assumptions from the linear bandit setting, and lastly we will make the connections between the two that allow us to use the confidence bounds from the linear bandit setting in the RL setting.

$P^{*}(s^{\prime}\mid s,a)=\sum_{i=1}^{d}(\theta_{*}^{\textit{MDP}})_{i}P_{i}(s^{\prime}\mid s,a)$

$s_{h+1}^{k}\sim P^{*}(\cdot\mid s_{h}^{k},a_{h}^{k})$

where $t$ is defined in the table of A.4. Also note that in this section $(\cdot)_{*}$ denotes the true parameter or model, $(\cdot)^{\textit{MDP}}$ denotes something derived or used in the linear MDP setting, and $(\cdot)^{\textit{LIN}}$ denotes something derived or used in the linear bandit setting. Now, under 1-3 of C.1.1 we hope to construct a confidence set $\mathcal{C}_{t}^{\textit{MDP}}$ such that

with high probability. Now the choice of how to choose both $\mathcal{C}_{t}^{\textit{MDP}}$ and $\beta_{t}$ comes from the linear bandit literature. We will introduce the necessary theorems and assumptions to derive both $\mathcal{C}_{t}^{\textit{LIN}}$ and $\beta_{t}$ in the linear bandit setting and then adapt the results from the linear bandit setting to the linear MDP setting.

C.1.2 Tighter Confidence Bounds for Linear Bandits

where $\lambda>0$ is the regularizer. This loss function is minimized by

notice how this linear bandit problem is very similar to the linear MDP problem introduced in section 3 of our paper. In our linear MDP setting, it is convenient to think of $M$ and $W$ as serving equivalent purposes (storing rank one updates) thus it is also convenient to think of $A_{t}$ and $X_{t}^{\textit{MDP}}$ as serving equivalent purposes (the features by which we use to make our predictions), where $X_{t}^{\textit{MDP}}$ is defined in section 3 of our paper with some added notation to distinguish it from the $X_{t}^{\textit{LIN}}$ used here in the linear bandit setting. We will now build up some intuition by making some simplifying assumptions.

No regularization: $\lambda=0$ and $W_{t}$ is invertible.

Independent subgaussian noise: $(\eta_{s})_{s}$ are independent and $\sigma$-subgaussian

Fixed Design: $A_{1},...,A_{t}$ are deterministically chosen without the knowledge of $X_{1}^{\textit{LIN}},...,X_{t}^{\textit{LIN}}$

Since $(\eta_{s})_{s}$ are independent and $\sigma$-subgaussian, by Lemma 5.4 and Theorem 5.3 (need to be stated),

A little linear algebra shows that $\sum_{s=1}^{t}\langle x,W_{t}^{-1}A_{s}\rangle^{2}=\|x\|_{W_{t}^{-1}}^{2}$ and so,

We now remove the limiting assumptions we stated above and use the newly stated assumptions for the rest of this section

The noise is conditionally $\sigma$-subgaussian:

where $\mathcal{F}_{t-1}$ is such that $A_{1},X_{1}^{\textit{LIN}},...,A_{t-1},X_{t-1}^{\textit{LIN}}$ are $\mathcal{F}_{t-1}$-measurable.

The inclusion of $A_{t}$ in the definition of $\mathcal{F}_{t-1}$ allows the noise to depend on past choices, including the most recent action. Since we want exponentially decaying tail probabilities, one is tempted to try the Cramer-Chernoff method:

Sadly, we do not know how to bound this expectation. Can we still somehow use the Cramer–Chernoff method? We take inspiration from looking at the special case of $\lambda=0$ one last time, assuming that $W_{t}=\sum_{s=1}^{t}A_{s}A_{s}^{\top}$ is invertible. Let

Recall that $\hat{\theta}_{t}^{\textit{LIN}}=W_{t}^{-1}\sum_{s=1}^{t}X_{s}^{\textit{LIN}}A_{s}=\theta_{*}^{\textit{LIN}}+W_{t}^{-1}S_{t}$. Hence,

The next lemma shows that the exponential of the term inside the maximum is a supermartingale even when $\lambda\geq 0$.

The proof for this Lemma can be found in Chapter 20 of the book by Lattimore & Szepesvári (2020). For simplicity, consider now again the case when $\lambda=0$. Combining the lemma and the linearisation idea almost works. The Cramer–Chernoff method leads to

The proof of Lemma 13 can, again, be found in Chapter 20 of the book by Lattimore & Szepesvári (2020). Now the following theorem is the key result from which the confidence set will be derived.

For all $\lambda>0$, and $\delta\in(0,1)$

The proof of Theorem 14 can be found in Chapter 20 of the book by Lattimore & Szepesvári (2020).

C.1.3 Adaptation of the Confidence Bounds to our Linear MDP Setting

Now with the Lemmas and Theorems introduced in the previous section we are ready to derive the confidence bounds used in our implementation of UCRL-VTR. Now using the notation from the linear bandit setting we set

The target $X_{t}^{\textit{MDP}}=\int_{j}V_{t}(s^{\prime})P_{j}(ds^{\prime}\mid s_{t},a_{t})$

$\mathcal{F}_{t-1}=\sigma(s_{1},a_{1},...,s_{t-1},a_{t-1})$, which just means the filtration is set to be the sigma-algebra generated by all past states and actions observed.

$\eta_{t}=Y_{t}-\langle X_{t}^{\textit{MDP}},\theta_{*}^{\textit{MDP}}\rangle=V_{t}(s_{t+1})-\int_{j}V_{t}(s^{\prime})P_{j}^{*}(ds^{\prime}\mid s_{t},a_{t})$, since $\theta_{*}^{\textit{MDP}}$ is the true model of the MDP.

$M_{t}$ in the linear MDP setting is defined equivalently to $W_{t}$ in the linear bandit setting, i.e. they are both the sums of a regularizer term and a bunch of rank one updates.

The fundamental theorem of calculus yields

where here in the linear MDP setting $M_{t}$ replaces $W_{t}$ from the linear bandit setting and $\|\theta_{*}^{\textit{MDP}}\|_{2}\leq m_{2}$. The justification of using these bounds in the linear MDP setting follow exactly from the justification given above for using these bounds in the linear bandit setting.

C.2 UCRL-VTR

In the proceeding subsections we discuss the implementation of the algorithms studied in Section 6 of the paper. The first algorithm we present is the algorithm used to generate the results for UCRL-VTR.

The iterative Q-update for Algorithm 3 is

C.3 EGRL-VTR

In this section we discuss the algorithm EGRL-VTR. This algorithm is very similar to UCRL-VTR expect it performs $\varepsilon$-greedy value iteration instead of optimistic value iteration and acts $\varepsilon$-greedy with respect to $Q_{h,k}$.

The iterative value update for EGRL-VTR is

C.4 EG-Frequency

In this section we discuss the algorithm EG-Frequency. This algorithm is the $\varepsilon$-greedy version of UC-MatrixRL Yang & Wang (2019a).

The iterative Q-update for EG-Frequency is

Note that $\mathbf{\Psi}$ is a $|\mathcal{S}|\times|\mathcal{S}|$ whose rows are the features $\psi(s^{\prime})$ and $\mathbf{\Phi}$ is a $|\mathcal{S}||\mathcal{A}|\times|\mathcal{S}||\mathcal{A}|$ whose rows are the features $\phi(s,a)$. In the tabular RL setting both $\mathbf{\Psi}$ and $\mathbf{\Phi}$ are the identity matrix which is what we used in our numerical experiments. In the tabular RL setting, EG-Frequency stores the counts of the number of times it transitioned to next state $s^{\prime}$ from the state-action pair $(s,a)$ and fits the estimated model $M_{k}$ accordingly.

In this section, we include some further details on how we implemented Algorithms 3, 4, and 5. All code was written in Python 3 and used the Numpy and Scipy libraries. All plots were generated using MatPlotLib. In Algorithm 3, Numpy’s logdet function was used to calculate the determinate in step 15 for numerical stability purposes. No matrix inversion was performed in our code, instead a Sherman-Morrison update was performed for each matrix in which a matrix inversion is performed at each $(k,h)$ in order to save on computation. To read more about the Sherman Morrison update in the context of RL, we refer to the reader to Eqn (9.22) of Sutton & Barto (2018). When computing the weighted L1-norm, we added a small constant to each summation in the denominator to avoid dividing by zero. Finally, when computing UC-MatrixRL we also used the self-normalize bounds introduced in the beginning of this section. Some pseudocode for using self-normalized bounds with UC-MatrixRL can be found in step 5 of Alg 6.

Appendix D Mixture Model

In this section, we introduce, analyze, and evaluate a Linear model-based RL algorithm that used both the canonical model and the VTR model for planning. We call this algorithm UCRL-MIX.

We are now using multiple models instead of a single model, we must adjust our confidence sets accordingly. By using a union bound we replace $\delta$ with $\delta/2$ for our confidence parameter. This updated confidence parameter changes the term inside the logarithm. We now have $\log(2/\delta)$ where as before we had $\log(1/\delta)$.

D.2 Numerical Results

We will include the cumulative regret and the weighted L1 norm of UCRL-MIX on the RiverSwim environment as in Section 6. We also include a bar graph of the relative frequency with which the algorithm used the VTR-model for planning and the canonical model for planning.

If we compare the results of Figure 5 with the results of Figure 2 from Section 6.3 we see that the cumulative regret of UCRL-MIX is almost identical to the cumulative regret of UCRL-VTR. The model errors of both the VTR and the canonical models are almost identical to the model errors of UCRL-VTR and UC-MatrixRL respectively.

From Figure 6, we see that on the RiverSwim environment, UCRL-MIX almost always uses the VTR-model for planning. We calculate this frequency by counting the number of times Step 7 of Alg 6 was observed up until episode $k$ and by counting the number of times Step 9 of Alg 6 was observed up until episode $k$. We then divide these counts by the sum of the counts to get a percentage. We believe the reason the algorithm overwhelming chose the VTR-model was due to the fact that the confidence intervals for the VTR-model shrink much faster than the confidence intervals for the canonical model. The canonical model is forced to explore much longer than the VTR-model as its objective is to learn a globally optimal model rather than a model that yields high reward. Thus, the canonical model is forced to explore all state-action-next state tuples, even ones that do not yield high reward, in order to meet its objective of learning a globally optimal model while the VTR-model is only forced to explore state-action-next state tuples that fall in-line with its objective of accumulating high reward. The set of all state-action-next state tuples is much larger then the set of state-action-next state tuples that yield high reward which means the confidence intervals for the canonical model shrink slower than the confidence sets of the VTR-model on the RiverSwim environment.