Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison

Introduction

We study value-function approximation for batch-mode reinforcement learning (RL), which is central to the success of modern RL as many popular off-policy deep RL algorithms find their prototypes in this literature. These algorithms are typically iterative, that is, they solve a series of optimization problems, aiming to mimic each step of value- or policy-iteration [Puterman, 2014].

In the setting of general function approximation, however, not only the iterative style causes instability in practice, but it also brings several theoretical issues, which have been made abundantly clear in existing analyses [e.g., Munos, 2003, 2007; Antos et al., 2008; Farahmand et al., 2010; Chen and Jiang, 2019]:

The performance loss of most iterative methods incur quadratic dependence on the effective horizon, i.e., $\mathcal{O}(\frac{1}{(1-\gamma)^{2}})$, and this is tight for the popular Approximate Value/Policy Iteration (AVI/API) [Scherrer and Lesner, 2012]. One typical way this occurs in AVI analyses is through the use of (some fine-grained variants of) the following result from Singh and Yee , that the performance loss of a policy greedy w.r.t. some $Q$ is bounded by

and translating $\|Q-Q^{\star}\|$ to the quantities that the algorithm actually optimizes incurs at least another factor of horizon. Such a quadratic dependence is significantly worse than the ideal linear dependence, the best one could hope for [Scherrer, 2014].

While linear-in-horizon algorithms exist, they often require interactive access to the environment (to collect new data using policies of the algorithm’s choice), or the knowledge of transition probabilities to compute the true expectation in the Bellman operators,At the minimum, two i.i.d. next-states must be drawn from the same state-action pair, known as the double sampling trick [Baird, 1995], which is unrealistic in non-simulator problems. and few of them apply to the batch learning setting.Exceptions exist when we are allowed to output complex non-stationary policies; see Section 3 for details. Are there batch algorithms for $Q^{\star}$ that incur linear-in-horizon dependence?

(B) Characterization of Distribution Shift

One of the central challenges in RL is the distribution shift, that the computed policy may induce a state (and action) distribution different from what it is trained on. Existing analyses characterize this effect using the concentrability coefficients [Munos, 2007], with a typical definition being the density ratio (or importance weights) between the state distribution induced at a particular time step by some non-stationary policy and the data distribution. These “per-step” definitions can be very loose even in the uncontrolled setting (Section 5.2) and sometimes very complicated [Farahmand et al., 2010]. Are there algorithms whose distribution shift effects are characterized by elegantly and tightly defined quantities?

(C) Function Approximation Assumptions

Existing analyses require strong expressivity assumptions on the function classes, such as approximate closedness under Bellman update [see inherent Bellman errors; Munos and Szepesvári, 2008]. Are there algorithms with provable guarantees under somewhat weaker conditions?

(D) Squared-to-Average Conversion

In this paper we present novel analyses of two algorithms, MSBO (which has been analyzed by Chen and Jiang ) and MABO (which is novel), and provide positive answers to all questions above. A simple telescoping argument (Section 4) shows that both algorithms enjoy linear-in-horizon error propagation—which immediately improves the previous bound of Chen and Jiang for MSBO—and the distribution shift effects can be characterized by simple notions of concentrability coefficients that are significantly tighter than previous per-step definitions, which address (A) and (B). By carefully examining the difference between the two algorithms, we further show that MABO, a novel algorithm that uses explicit importance-weighting correction and plain average objectives (without squared loss) does not suffer from the looseness of squared-to-average conversion, and comes with automatically augmented expressivity for its importance-weight class, addressing (C) and (D).

Preliminaries

An (infinite-horizon discounted) MDP [Puterman, 2014] is a tuple $(\mathcal{S}$, $\mathcal{A}$, $P$, $R$, $\gamma,d_{0})$: $\mathcal{S}$ and $\mathcal{A}$ are the finite state and the finite action spaces, respectively, whose cardinalities can be arbitrarily large. $P:\mathcal{S}\times\mathcal{A}\to\Delta(\mathcal{S})$ is the transition function (we use $\Delta(\cdot)$ to denote the probability simplex), $R:\mathcal{S}\times\mathcal{A}\rightarrow[0,R_{\max}]$ is the reward function, and $\gamma\in[0,1)$ is a parameter that characterizes how rewards are discounted over time. $d_{0}\in\Delta(\mathcal{S})$ is the initial state distribution.

Another concept crucial to this paper is the normalized discounted state occupancy:

The state-action occupancy $d_{\pi}(s,a)$ is defined similarly and satisfies $d_{\pi}(s,a)=d_{\pi}(s)\pi(a|s)$.

2 Batch Value-Function Approximation

We are concerned with approximating $Q^{\star}$ in the batch RL setting, where a dataset $\mathcal{D}$ consisting of $n$ $(s,a,r,s^{\prime})$ tuples is given, and we cannot interact with the MDP to obtain new data. We adopt the following data generation protocol from Chen and Jiang , that the tuples are i.i.d.In reality, the transition tuples extracted from the same trajectory are in general dependent, which can be handled by concentration inequalities for dependent processes with mixing assumptions [see e.g., Antos et al., 2008]. as $(s,a)\sim\mu$, $r=R(s,a)$, $s^{\prime}\sim P(\cdot|s,a)$, and $\mu$ is fully supported on $\mathcal{S}\times\mathcal{A}$.

Function Approximation

We assume access to a function class $\mathcal{Q}\subset[0,V_{\max}]^{\mathcal{S}\times\mathcal{A}}$, and focus on algorithms that approximate $Q^{\star}$ with some $Q\in\mathcal{Q}$ and output its greedy policy $\pi_{Q}$. This automatically implies a policy class $\Pi_{\mathcal{Q}}\coloneqq\{\pi_{Q}:Q\in\mathcal{Q}\}$, from which the output policy will be chosen. Some algorithms require additional function classes, which we introduce later. We assume all function classes have finite cardinalities for simplicity when analyzing statistical errors, as they are not our main focus and extension to continuous classes with e.g., finite VC-type dimensions [Natarajan, 1989] are standard.

A representative algorithm for this setting is Fitted Q-Iteration (FQI) [Ernst et al., 2005], which can be viewed as the theoretical prototype of the popular DQN algorithm [Mnih et al., 2015]: After initializing $Q_{0}\in\mathcal{Q}$ arbitrarily, we iteratively compute $Q_{t}$ as

We will discuss the relationship between FQI (and iterative methods in general) and algorithms we analyze.

Marginalized Importance Weights

We define the importance weight of any policy $\pi$ to be the ratio between its normalized discounted state-action occupancy and the data distribution:

Such functions are of vital importance to us, as in Section 6 we model them with function approximation to explicitly correct distribution mismatch. Their norms also characterize the exploratoriness of the data distribution, which are closely related to the concentrability coefficients in prior analyses [Munos, 2007; Antos et al., 2008; Farahmand et al., 2010; Chen and Jiang, 2019].

Additional Notations

Related Work

As mentioned in the introduction, most of the existing linear-in-horizon results do not apply to the setting of batch learning with general function approximation. For example, Munos [2007, Section 5.2] points out that AVI enjoys linear-in-horizon error propagation if it happens to converge.Our paper provides a novel explanation of this result: when FQI (which is a concrete instantiation of the abstract AVI procedure) happens to converge, Chen and Jiang shows that its solution coincides with that of MSBO, which we show enjoys linear-in-horizon error propagation whatsoever. Unfortunately, AVI—and iterative methods in general—has no convergence guarantees (and known to diverge with simple linear classes) unless used with very restricted choices of function approximators [see e.g., averagers; Gordon, 1995]. As another example, linear-in-horizon error can be achieved if one can directly minimize the Bellman error [e.g., Geist et al., 2017], but computing that requires knowledge of the transition probabilities. We refer the readers to Scherrer and the references therein for further results of this kind.

The only exceptions we are aware of are the non-stationary versions of AVI/API [e.g., Scherrer and Lesner, 2012], when the algorithm is allowed to output a periodic non-stationary policies consisting of $\Omega(\nicefrac{{1}}{{(1-\gamma)}})$ stationary policies. For a typical value of $\gamma=0.99$ this translates to $100$ policies, and we believe such a complexity is responsible for the clever idea not being picked up in practice despite its appealing theoretical properties. In contrast, we establish linear-in-horizon guarantees for batch algorithms that output simple stationary policies.

Clean and Tight Concentrability Coefficients

The situation of concentrability coefficients is very similar. The best definition is $\|w_{\nicefrac{{d_{\pi^{\star}}}}{{\mu}}}\|_{\infty}$, enjoyed by e.g., CPI [Kakade and Langford, 2002] (see also Agarwal et al. ). However, concrete instantiations of these abstract algorithms (in a way that preserve their theoretical properties) typically require on-policy Monte-Carlo roll-outs, which are not available in the batch setting. The same constant has been associated with an abstract Bellman error minimization procedure [Geist et al., 2017], but the algorithm only searches over valid value-functions (instead of arbitrary functions produced by the function approximator). While our definition is worse than theirs by a maximum over policies under consideration, it is still significantly tighter and cleaner than the per-step definitions in most previous analyses of AVI/API [Szepesvári and Munos, 2005; Munos, 2007; Antos et al., 2008; Farahmand et al., 2010]. In fact, we show in Appendix B that even in a simple uncontrolled setting, our occupancy-based definition can be $\nicefrac{{1}}{{(1-\gamma)}}$ multiplicatively tighter than any per-step definitions.

MSBO

The first algorithm we analyze, MSBO, is essentially the analogy of Modified BRM [Antos et al., 2008] (which approximates $Q^{\pi}$) in the context of approximating $Q^{\star}$. To our knowledge, the algorithm is first analyzed by Chen and Jiang , and we improve their loss bound by $\nicefrac{{1}}{{(1-\gamma)}}$ (which translates to $\nicefrac{{1}}{{(1-\gamma)^{2}}}$ improvement in sample complexity). It is also worth pointing out that Dai et al. has derived a closely related algorithm and demonstrated its empirical effectiveness with deep neural nets.

MABO

Our second algorithm, MABO, is presented and described in such a general form for the first time. That said, the algorithmic idea can be found in several recent works: Just as MSBO is the $Q^{\star}$-counterpart of Modified BRM, MABO is the $Q^{\star}$-counterpart of the MQL algorithm for off-policy evaluation [Uehara et al., 2019]. Another closely related work is kernel loss [Feng et al., 2019], which becomes similar to MABO when the implicit maximization in the RHKS is interpreted as searching over an importance weight class (this connection is pointed out by Uehara et al. ). Finally, the average Bellman error is first used by Jiang et al. for PAC-exploration with function approximation, and MABO can be viewed as the batch analogy of their OLIVE algorithm, using importance weights to mimic the data collected by different exploration policies.

Telescoping Performance Difference

We present the important telescoping lemmas that enable the nice guarantees of the algorithms to be introduced and analyzed later. We start with a simple telescoping lemma, which has also been used in recent off-policy evaluation literature [e.g., Uehara et al., 2019]. Unless otherwise specified, the full proofs of the results in the main text can be found in Appendix A.

We conclude this section with some useful corollaries of Theorem 2, which may also be of independent interest on their own.

Minimax Squared Bellman Optimality Error Minimization (MSBO)

We present the performance guarantee of the first algorithm, MSBO, which uses another helper class $\mathcal{F}\subset[0,V_{\max}]^{\mathcal{S}\times\mathcal{A}}$ to model $\mathcal{T}Q$ for any $Q\in\mathcal{Q}$, seeking to form an (approximately) unbiased estimate of the Bellman error $\|Q-\mathcal{T}Q\|_{2,\mu}^{2}$:

We now state the guarantee of the algorithm.

Let $\widehat{Q}$ be the output of MSBO. W.p. at least $1-\delta$,

This result improves over the bound of Chen and Jiang in several aspects, which we explain below. Furthermore, their bound for MSBO is structurally the same as that for FQI when $\mathcal{F}$ is set as $\mathcal{Q}$, and while we are able to improve the bound for MSBO, some of the improvements cannot be enjoyed by FQI (see the argument of Scherrer and Lesner ), creating a gap between performance guarantees of the two algorithms.

In the rest of this section, we explain the result and discuss its significance in detail. We also include a high-level sketch of the proof at the end, deferring the full proof to Appendix A.

2 Concentrability Coefficient

The second improvement, which is much more significant, is the departure from “per-step” definitions. In all analyses of AVI/API, the concentrability coefficient takes the form of

where $d_{\pi,t}$ is the marginal distribution of $(s_{t},a_{t})$. $\beta(t)$ is a series of non-negative coefficients that sum up to $1$. Different versions of $C_{\textrm{per-step}}$ differ in $\beta(t)$, the policy space considered in $\max_{\pi}$ (typically non-stationary policies concatenated using policies from $\Pi_{\mathcal{Q}}\bigcup\{\pi^{\star}\}$), and sometimes replacing $\|\cdot\|_{\infty}$ with $\|\cdot\|_{2}^{2}$; see Farahmand et al. for a detailed discussion. While it is difficult to directly compare this quantity to ours due to its complication, we show that in a simplest uncontrolled scenario where there is no distribution shift at all, any per-step definition will be at least $1/(1-\gamma)$ looser than ours. We include an intuitive but informal statement below, and defer the detailed discussions to Appendix B.

3 Horizon Dependence

4 Proof Sketch

The last step follows from Cauchy-Schwarz for random variables, and the term $\|\mathcal{T}\widehat{Q}-\widehat{Q}\|_{2,\mu}$ is well-studied by Chen and Jiang and we directly use their result.

Minimax Average Bellman Optimality Error Minimization (MABO)

Let $\widehat{Q}$ be the output of MABO. W.p. $1-\delta$,

In the rest of this section, we explain the bound and discuss its significance.

2 Concentrability Coefficients

3 Horizon Dependence

4 Proof Sketch of Theorem 8

Further Comparisons and Discussions

In the previous sections we have analyzed MSBO and MABO, showing that they enjoy linear-in-horizon error propagation and cleanly and tightly defined concentrability coefficients, which answers (A) and (B) in the introduction. Still, MSBO bears significant similarities to classical AVI/API algorithmsRecall that FQI coincides with MSBO using $\mathcal{F}=\mathcal{Q}$ when FQI converges [Chen and Jiang, 2019], and in this sense MSBO can be viewed as a best-case scenario for FQI. in the use of squared loss and the expressivity requirement on function approximation ((C) and (D)). In this section we compare its guarantee (Theorem 5) to that of MABO (Theorem 8), and discuss the potential advantages of MABO (which is novel and understudied), as well as its limitations, compared to currently popular algorithms. The recurring theme of the comparisons—as we will see below—is the pros and cons of implicit (e.g., FQI and MSBO) and explicit (MABO) distribution corrections.

Here the second step follows from Cauchy-Schwarz, which we also used in Section 5.4. As we can see, if $\mathcal{W}$ is specified “just right”, MABO’s guarantee never suffers more than that of MSBO on misspecified $\mathcal{Q}$, and any looseness from Cauchy-SchwarzSee (D) in the introduction. enters the gap. On the other hand, such an advantage of MABO may be weakened if $\mathcal{W}$ includes additional functions that do not correspond to real importance weights.

2 Statistical Rates

3 Assumptions on the Helper Classes

A characteristic shared by MSBO and MABO is the use of a helper class ($\mathcal{F}$ for MSBO and $\mathcal{W}$ for MABO) to assist the estimation of the Bellman error. These helper classes also take the heaviest expressivity burdens in their corresponding algorithms: while $\mathcal{Q}$ is only required to capture $Q^{\star}$, $\mathcal{F}$ and $\mathcal{W}$ are required to capture $\mathcal{T}Q$ and $w_{\nicefrac{{d_{\pi_{Q}}}}{{\mu}}}$, respectively, for all $Q\in\mathcal{Q}$.

Suppose the rank of the MDP’s transition matrix is $k$. Then,

Conclusions

We analyze two algorithms, MSBO and MABO, which enjoy linear-in-horizon error propagation, a property established for the first time for batch algorithms outputting stationary policies. MABO uses a novel importance-weight correction to handle the difficulty of Bellman error estimation, and our analyses reveal its distinct properties and potential advantages compared to classical squared-loss-based algorithms.

Acknowledgement

The authors thank Aditya Modi for providing the references to some important related works.

References

Appendix A Detailed Proofs

where the first equation follows from the definition of $d_{\pi}$, the second equation follows from the definition of $Q(s,\pi(s))$. ∎

These three terms can be bound separately as follows.

The second equation follows from Lemma 1, and the last step follows from marginalizing out $r$ and $s^{\prime}$ by conditioning on $(s,a)$ using law of total expectation.

Finally, (III), which is handled similarly to (I).

where the third equation follows from the definition of $\pi_{Q}$ being greedy w.r.t. $Q$. The result follows by putting all three parts together. ∎

Let $\widehat{Q}$ be the output of MSBO. W.p. at least $1-\delta$,

We then directly adopt the upper bound on $\left\|\widehat{Q}-\mathcal{T}\widehat{Q}\right\|_{2,\mu}$ from Chen and Jiang :

By substitute Eq.(58) into Eq.(61) and adapt the the proof of Theorem 17 in Chen and Jiang , we have

Let $\widehat{Q}$ be the output of MABO. W.p. $1-\delta$,

We now bound $\left|\mathcal{L}_{\mu}(\widehat{Q},w_{\nicefrac{{d_{\pi}}}{{\mu}}})\right|$ for any policy $\pi\in\Pi_{\mathcal{Q}}$. Let

At this point, we peeled off all the approximation errors from $\left|\mathcal{L}_{\mu}(\widehat{Q},w_{\nicefrac{{d_{\pi}}}{{\mu}}})\right|$, and it remains to bound the estimation error

where (a) follows form $\sup_{x}|f(x)|-\sup_{x}|g(x)|\leq\sup_{x}|f(x)-g(x)|$ and (b) follows from Eq.(75) and the following argument:

Now, since the only difference between term (I) and term (II) is the choice of $Q$ and $w$, it suffices to provide a uniform deviation bound that applies to all $w\in\mathcal{W}$ and $Q\in\mathcal{Q}$. Before applying concentration bounds, it will be useful to first verify the boundedness of the random variables: $w(s,a)\in[-C,C]$, and $r+\gamma\max_{a^{\prime}}Q(s^{\prime},a^{\prime})-Q(s,a)\in[-V_{\max},V_{\max}]$ (recall that we assumed $Q\in[0,V_{\max}]$). Therefore, by Bernstein’s inequality and the union bound, w.p. at least $1-\delta$ we have that for any $w\in\mathcal{W}$ and $Q\in\mathcal{Q}$,

where (a) is obtained by the following argument:

Appendix B Comparison between Per-step vs. Occupancy-based Concentrability Coefficients

We provide an example to illustrate the limitation of the per-step concentrability coefficients (Proposition 6). Consider a deterministic chain MDP, where there are $L+1$ states, $\{s_{0},s_{1},s_{2},\dotsc,s_{L}\}$. There is only one action, which we omit in the notations. $s_{0}$ is the deterministic initial state, and each $s_{l}$ transitions to $s_{l+1}$ under the only action for $0\leq l<L$. $s_{L}$ is an absorbing state (i.e., it transitions to itself). The reward function is inconsequential.

There is only one possible policy $\pi$ for this MDP, and we let the data distribution $\mu=d_{\pi}$. The occupancy-based concentrability coefficient is always $1$ (either $C_{\infty}$ or $C_{\text{eff}}$), which agrees with the intuition that there is no distribution shift. Since the per-step definitions (Eq.(17)) are always the convex combinations of $C_{t}=\max_{\pi}\|w_{\nicefrac{{d_{\pi,t}}}{{\mu}}}\|_{\infty}$ for $t\geq 0$, we can assert that it is never lower than $\min_{t}C_{t}$ however the combination coefficients are chosen.

Replacing $\|\cdot\|_{\infty}$ with $\|\cdot\|_{2,\mu}^{2}$ gives exactly the same results. (When the distribution on the enumerator is a point mass, $\|\cdot\|_{2,\mu}^{2}$ of the importance weight is the same as $\|\cdot\|_{\infty}$.) Therefore, as long as $L$ is sufficiently large so that $\frac{1}{\gamma^{L}}\geq\frac{1}{(1-\gamma)}$, we have $C_{t}\geq\nicefrac{{1}}{{1-\gamma}}$ for all $t$, and the per-step concentrability coefficient is at least $\nicefrac{{1}}{{1-\gamma}}$. As a final remark, since the MDP only has 1 policy, the result has no dependence on the choice of policy class in $\max_{\pi}$ in the definition of concentrability coefficient, so we have virtually covered all existing definitions in the AVI/API literature.

Appendix C On Iterative Methods’ Lack of Control of Bellman Errors

We demonstrate that iterative methods fail to directly control the Bellman error on the data distribution $\mu$. Consider a two-state deterministic MDP with just 1 action, where $s_{1}$ transitions to $s_{2}$, and $s_{2}$ is absorbing. The reward is always .

We use the tabular representation for this MDP, where $Q=[Q(s_{1},a),Q(s_{2},a)]^{\top}$. Assume our batch data $\mathcal{D}$ only contains transition tuples of form $(s_{1},a,0,s_{2})$, and no data points from $(s_{2},a_{2})$ are present. We first show how FQI behave on this example. Given the update rule of FQI (Eq.(3)),

Therefore, with very update, $Q(s_{1},a)$ will obtain the old value of $\gamma Q(s_{2},a)$ from the previous iteration, whereas the new value of $Q(s_{2},a)$ will be set arbitrarily. Since the mean square Bellman error is $\|Q_{t}-\mathcal{T}Q_{t}\|_{2,\mu}^{2}=(Q_{t}(s_{1},a)-\gamma Q_{t}(s_{2},a))^{2}$, its value can be arbitrarily away from and do not become smaller over iterations. In comparison, it is easy to verify that MSBO and MABO do not suffer from this issue: although there is also arbitrariness in their outputs due to insufficient data coverage, their outputs will always satisfy $Q(s_{1},a)=\gamma Q(s_{2},a)$ and hence imply zero Bellman error on $\mu$.

Appendix D Existence of Simple 𝒲𝒲\mathcal{W} in Low-rank MDPs (Proposition 10)

Since $\mu$ is supported on the entire $\mathcal{S}\times\mathcal{A}$, we have $w_{\nicefrac{{d_{\pi}}}{{\mu}}}=\text{diag}(\mu)^{-1}d_{\pi}$. Putting all results together, it suffices to choose $\mathcal{W}=\{\text{diag}(\mu)^{-1}(\eta_{i}^{\prime}\times\pi_{Q}):i\in[k^{\prime}],Q\in\mathcal{Q}\}$, and $|\mathcal{W}|\leq(k+1)|\Pi_{\mathcal{Q}}|$.

Remark on the |𝒬|𝒬|\mathcal{Q}| Dependence in the General Case

The annoying dependence on $|\mathcal{Q}|$ comes from the fact that we hope the state-action occupancy vectors of different policies to have low-rank factorization (which is satisfied in the more restricted case; see Claim 2). In general low-rank MDPs, however, only state occupancy factorizes and the state-action one does not; a counter-example can be easily shown in contextual bandits:

Consider an MDP with 2 actions per state. $d_{0}$ is uniform among $|\mathcal{S}|-1$ states, all of which transition deterministically to the last state, which is absorbing. This MDP essentially emulates a contextual bandit. Since all states share exactly the same next-state distribution, the rank of the transition matrix is $1$ regardless of how large $|\mathcal{S}|$ is. Now consider a policy space $\Pi_{\mathcal{Q}}$, where each policy takes action $a_{1}$ in one of the $|\mathcal{S}|-1$ states, and takes $a_{2}$ in all other states; there are $|\mathcal{S}|-1$ such policies. It is easy to show that the matrix consisting of state-action occupancy $d_{\pi}$ for all policies in $\Pi_{\mathcal{Q}}$ has full-rank $|\mathcal{S}|-1$, which cannot be bounded by the rank of the transition matrix when $|\mathcal{S}|$ is large.

Given this difficulty, our strategy is to first find the policies whose state occupancy vectors span the entire low-dimensional space, and take their Cartesian product with $\Pi_{\mathcal{Q}}$ to handle the actions, which results in the $|\mathcal{Q}|$ dependence. As we will see below, we can avoid paying $|\mathcal{Q}|$ when the $\mathcal{Q}$ class is more structured.

Claim 2: Restricted Case of Knowing the Left Factorization Matrix as Features [Yang and Wang, 2019]

Remark

Since $\mathcal{Q}$ is closed under Bellman update in this setting, one may also use $\mathcal{Q}$ as the helper class $\mathcal{F}$ for MSBO. However, the complexity of $\mathcal{F}$ in this case only matches that of $\mathcal{W}$ in the more general case (Claim 1) and is significant worse than what we can achieve here ($|\mathcal{W}|\leq k+1$).