Optimism in Reinforcement Learning with Generalized Linear Function Approximation
Authors: Yining Wang
Ruosong Wang
Simon Shaolei Du
Akshay Krishnamurthy
Venue: ICLR 2021 Poster (2021)
Keywords: reinforcement learning
optimism
exploration
function approximation
theory
regret analysis
provable sample efficiency

Abstract: We design a new provably efficient algorithm for episodic reinforcement learning with generalized linear function approximation. We analyze the algorithm under a new expressivity assumption that we call ``optimistic closure,'' which is strictly weaker than assumptions from prior analyses for the linear setting. With optimistic closure, we prove that our algorithm enjoys a regret bound of $\widetilde{O}\left(H\sqrt{d^3 T}\right)$ where $H$ is the horizon, $d$ is the dimensionality of the state-action features and $T$ is the number of episodes. This is the first statistically and computationally efficient algorithm for reinforcement learning with generalized linear functions.

Published as a conference paper at ICLR 2021
OPTIMISM IN REINFORCEMENT LEARNING WITH GENERALIZED LINEAR FUNCTION APPROXIMATION
Yining Wang
Ruosong Wang
University of Florida yining. wangewarringtow ufl.edu
Carnegie Mellon University
rucsongw@andrew, cmu edd
Simon S. Du
Akshay Krishnamurthy
University of Washington ssduêcs, washington. edu
Microsoft Research
akshaylrremicroooft.com
ABSTRACT
We design a new provably efficient algorithm for episodic reinforcement learning with generalized linear function upproximation. We analyze the algorithm under a new expressivity assumption that we call "optimistic closure," which is strictly weaker than assumptions from prior analyses for the linear setting. With opti-
mistic closure, prove that our algorithm enjoys regret bound of Ö H
where H is the horizon, d is the dimensionality of the state-action features and T the number of episodes. This is the first statistically and computationally efficient algorithm for reinforcement learning with generalized linear functions.
INTRODUCTION
We study episodic reinforcement learning problems with infinitely large state spaces, where the agent must use function approximation to generalize across states while simultaneously engaging in strategic exploration. Such problems form the core of modern empirical/deep- but relatively little work focuses on exploration, and even fewer algorithms enjoy strong sample efficiency guarantees.
On the theoretical side, classical sample efficiency results from the early 00s focus on "tabular" environments with small finite state spaces (Kearns & Singh 2002 Brafman & Tennenholtz (002 Strehl et al. 2006), but as these methods scale with the number states, they do not address prob- lems with infinite large state spaces. While this classical work has inspired practically effective approaches for large state spaces (Bellemare et al.) 2016,; Osband et al., 2016: Tang et al.) 2017), these methods do not enjoy sample efficiency guarantees. More recent theoretical progress has produced provably sample efficient algorithms for complex environments where function approxi- mation is required, but these algorithms relatively impractical (Krishnamurthy et al.) [016]] Jiang et al. 2017). In particular, these methods are computationally inefficient or rely crucially on strong dynamics assumptions (Du
2019b).
In this paper, with an eye toward practicality, we study a simple variation of Q-learning, where we approximate the optimal Q-function with generalized linear model. The algorithm is appealingly simple: collect trajectory by following the greedy policy corresponding to the current model, perform dynamic programming back-up update the model, and repeat. The key difference over traditional Q-learning-like algorithms is in the dynamic programming step. Here we ensure that the updated model optimistic the sense that always overestimates the optimal Q-function. This optimism is essential for our guarantees.
Optimism in the face of uncertainty is a well-understood and powerful algorithmic principle in short- horizon (e.g.. bandit) problems, as well as in tabular reinforcement learning (Azar et al. [011 Dann et al. 2017: Jin et al. 2018). With linear function approximation, Yang & Wang (019) and Jin et al. 2019) show that the optimism principle when the environment dynamics satisfy certain linearity properties. Their assumptions are always satisfied in tabular problems, but somewhat unnatural in settings where function approximation
also yield provably sample-effciien algorithms,

---

Published as a conference paper at ICLR 2021
is required. Moreover these assumptions directly on the dynamics, it is unclear how their anal- ysis can accommodate other forms function approximation, including generalized linear models.
In the present paper, replace explicit dynamics assumptions with expressivity assumptions the function approximator, and, by analyzing a similar algorithm to Jin et al. 2019), we show that the optimism principle succeeds under these strictly weaker assumptions More importantly, the laxed assumption facilitates moving beyond linear models, and we demonstrate this by providing the first practical and provably efficient RL algorithm with generalized linear function approximation.
The paper is organized as follows: In Secctonn 2] we formalize our setting, introduce the optimistic closure assumption, and diseuss related assumptions in the literature. In [Section 3 study opti- mistic closure in detail and verify that it is strictly weaker than the recently proposed Linear MDP assumption. Our main algorithm and results are presented in |Section 4| with the main proof in Scc- tion A We close with some final remarks and future directions in Section 5
2
PRELIMINARIES
We consider episodic reinforcement learning in a finite-horizon markov decision process (MDP) with possibly infinitely large state space S, finite action space A, initial distribution μ AS)) transition operator P S x A - ASS), reward function R S x A + A 1]) and horizon H. The agent interacts with the MDP in episodes and, in each episode, a trajectory ($1, 01, $2, 02, T2,.... .2...., SH. (H,TH) is generated where 81 ~ for h >> 1 we have Sn ~ P(- Sh-1: 1)-)), The R(sh, ah), and actions 01:b are chosen by the agent. For normalization, we assume that Σ E [0, almost surely.
A (deterministic, nonstationary) policy where n (sx) denotes the action to be taken at time point h if at state Sn E The value function for policy is collection of functions (V :-.., Vă) where VI S + R is the expected future reward the policy collects if it starts a particular state at time point h. Formally,
(.. TH) consists of H mappings TA S A,
(s) E E
Σ
Th Sh = 5,
The value for a policy i is simply V A ExjeH (s )}. and the optimal value is V* - max, V*, where the maximization is over all nonstationary policies. The typical goal is to find an approxi- mately optimal policy, and in this paper, we measure performance by the regret accumulated over T episodes,
T
H
Reg(T) (T) & TV E
Σ
The
h=1
Here The is the reward collected by the agent at time point in the thh episode. We seek algorithms with regret that is sublinear in T, which demonstrates the agent's ability act near-optimally over the long run.
2.1 Q-VALUES AND FUNCTION AAIECTTONNPPPIIE APPROXIMATION
For any policy n. the state-action value function, or the Q-function is a sequence of mappings Q = (QFT...,.. where Q7, : S A + R is defined as
H TW 8h = an = a, Oh+1:H ~ π
Q7 a) 2
The optimal Q-function is Q7 Q7 where T'' A argmax, V is the optimal policy.
In the value-based function approximation setting, we use function class & model Q". In this paper, we always take G to be class of generalized linear models (GLMs), defined as follows: Let d E N be dimensionality parameter and let B& 2 {o E Rd ||ج|| I 1} be the lg ball in Rd.
'This also mentioned remark in Jin al. 2019
2

---

Published as a conference paper at ICLR 2021
Definition 1.
For a known feature map 8 A BB and known link function [|-1,1] + [-1,1] the class of generalized linear models is G _ {(8, a) (((((s,))) Ba).
As is standard in the literature (Filippi al.) 2010 Li al. 2017). we assume the link function satisfies certain regularity conditions.
Assumption 1. f()) is either monotonically increasing or decreasing. Furthermore, there exist absolute constants 0 < R < K < oo and M < co such that k S (f) - K and (f" s M for all |2| S
For intuition, two example link functions are the identity map f() = 2 and the logistic map f(z) = 1/(1 + =) with bounded z. is easy to verify that both of these maps satisfy Assumption
2.2 EXPRESSIVITY ASSUMPTIONS: REALIZABILITY AND OPTIMISTIC CLOSURE
To obtain sample complexity guarantees that scale polynomially with problem parameters in the function approximation setting. it is necessary posit expressivity assumptions the function class G (Krishnamurthy et al., 2016 Du et al. 2019a). The weakest such condition is realizability, which posits that the optimal Q function is in G, or least well-approximated by G. Realizability alone suffices for provably efficient algorithms in the "contextual bandits" setting where H = 1 (Li al., 2017 Filippi al. 2010: Abbasi- Yadkori al. [00I]) but it does not seem to be sufficient Indeed in these settings it is common to make stronger expressivity assumptions (Chen
when H
Jiang 2019 Yang & Wang 2019: Jin et al. 2019).
Following these works, our main assumption is a closure property of the Bellman update operator (S x A- R.) and defined for all s E S,a E A
Th. This operator has type Th (S A R
as
Tr(Q)ss, a) A E [r + Vo(*n+1) 8h = s,an an = =]
Vi((s A max Qss aEA
The Bellman update operator for time point H is simply (Q) a) - B = =s = a). which is degenerate. To state the assumption, we must first define the enlarged function class Gup- For a d x d matrix A, A d 0 denotes that A is positive semi-definite. For a positive semi-definite matrix A, || is the matrix operator norm, which is just the largest eigenvalue, and || - Vx Az is the matrix Mahalanobis seminorm. For a fixed constant I E RR, that we will set to be polynomial in d and log(T), define
gup {
(s..a) + 1 f(()(s;))))) + (l)((,))))) :0 e Ba, A2 0, 11 $1
Here we use aAb A muinfa,b) b). The class Gup contains G in addition all possible upper confidence bounds that arise from solving least squares regression problems using the class G. We now state our main expressivity assumption, which we call optimistic closure.
Assumption (Optimistic closure). For any 1 < h < H and E Gup. we have (T(9) E EG.
In words, when we perform a Bellman backup on any upper confidence bound function for time point h + 1, we obtain a generalized linear function at time h. While this property seems quite strong, we note that similar notion is mentioned informally in Jin et al. (2019) and that related closure-type assumptions are common in the literature (see (Section 2.3] for detailed discussion). More importantly, will prove in Section that optimistic closure is actually strictly weaker than previous assumptions used in our RL setting where exploration is required. Before turning to these discussions, mention two basic properties of optimistic closure.
Fact 1 (Optimistic closure and realizability). Optimistic closure implies that Q* E 9 (realizability)
Proof. We will solve for Q* via dynamic programming, starting from time point H. In this case, the Bellman update operator degenerate, and we start by observing that (g) = QH for all g- Consequently we have Q E g. Next, inductively we assume that have Qi E G, which implies that 1 E Gup as we may take the same parameter 0 and set A = 0. Then, by the standard Bellman fixed- meedt characterization, we know that Q = Tv (Q at which point Assumption yields that Q E g.
3

---

Published as a conference paper at ICLR 2021
Fact 2 (Optimistic closure in tabular settings). S is finite and ((s,a) Cs,a is the standard-bau feature map, then under Assumption I we have optimistic closure.
Proof. We simply verify that contains all mappings from (s. a) + [0, 1J, at which point the result is immediate. To see why. observe that via Assumption 1 we know that f is invertible (it is monotonic with derivative bounded from above and below). Then, note that any function (s. a) H [0, 1] can be written as a vector & E [o, 1] [AA, For such vector v, if we define 22 _ ( have that f((e,,a 0)) Us.a. Hence G contains all functions, so we trivially have optimistic closure.
2.3 RELATED WORK
The majority of the theoretical results for reinforcement learning focus on the tabular setting where the state space is finite and sample complexities scaling polynomially with [S] are tolerable (Kearns) & Singh 2002 Brafman & Tennenholtz 2002 Strehl et al. 2006). Indeed, by now there are a num- ber of algorithms that achieve strong guarantees in this setting (Dann et al. 2017 Azar et al. 2017 Jin et al.) 2018: Simchowitz Jamieson 2019). Via Fact 2 our results apply to this setting, and in-
deed our algorithm can be viewed as generalization of the canonical tabular algorithm (Azar et al.) 2017 Dann et al. 2017 Simchowitz & Jamieson 2019) to the function approximation setting
Turning to the function approximation setting, several other results concern function approximation in settings where exploration is not an issue, including the infinite-data regime [Munos][003] 2003 Farah- mand et al. (2100) and the "batch RL" setting where the agent does not control the data-collection
process (Munos & Szepesvári] 2008 Antos et al.] 2008 Chen & Jiang 2019). While the details differ, all of these results require that the function class satisfy some form of (approximate) closure with respect to the Bellman operator. As an example, one assumption is that T(g) E G for all E G. with an appropriately defined approximate variant (Chen & Jiang 2019). These results therefore provide motivation for our optimistic closure assumption. While optimistic closure is stronger than the assumptions in these works. we emphasize that we are also addressing exploration, so our setting is also significantly more challenging.
A recent line of work studies function approximation in settings where the agent must explore the environment (Krishnamurthy et al., 2016; Jiang et al.] 2017: Du et al., 2019b). The algorithms developed here can accommodate function classes beyond generalized linear models, but they are still relatively impractical and the more practical ones require strong dynamics assumptions (Du) jet al., 2019b). In contrast, our algorithm is straightforward to implement and does not require any explicit dynamics assumption. As such, we view these results as complementary to
Most closely related to our work are the recent results of Yang & Wang (219 and Jin et al. (2119). Both papers study MDPs with certain linear dynamics assumptions (what they call the Linear MDP assumption) and use linear function approximation to obtain provably efficient algorithms. Jin et al. (019)) hint at optimistic closure as weakening of their Linear MDP assumption and remark that their guarantees continues to hold under this weaker assumption. One of our contributions is to formalize this remark. Indeed, our algorithm is almost identical theirs. However we empha- size that optimistic closure is strictly weaker than their Linear MDP assumption, which in turn is strictly weaker than the assumption of Yang Wang (2019). Further, and perhaps more impor- tantly, by avoiding explicit dynamics assumptions, we enable approximation with GLMs, which are incompatible with the Linear MDP structure. Hence, the present paper can be seen as significant generalization of these recent results.
Since the initial version of this paper appeared, several other works have studied linear function approximation in reinforcement learning. A number of papers (Cai et al. 2019: Ayoub et al. 2020 Modi et al. 2020 Zhou et al., (020) study an incomparable class of dynamies models that permit linear function approximation. Others study weakenings of the Linear MDP assumptions. In partic- ular, Agarwal et al. (2020) only require small transfer error for linear regression, which formalizes out-of-distribution generalization and is always zero in Linear MDPs. Zanette et al. (2020a) only require that the Bellman operator is closed with respect to linear functions, which is considerably
"The description of the algorithm looks quite different from that Azar et al. 2017). but via an equivalence hetween model-free methods with experience replay and model-based methods ( (Fujimoto et al. 2018 they are indeed quite similar.
4

---

Published as a conference paper at ICLR 2021
weaker than optimistic closure assumption. However, their algorithm is not computationally efficient. Computational efficiency is addressed in Zanette et al. (2020b) in the reward- setting with reachability assumptions. As do not require reachability assumptions, this latter result is incomparable to ours. None of these results considers generalized linear models.
ON OPTIMISTIC CLOSURE
For more detailed comparison to the recent work of Yang & Wang (2019) and Jin et al. (2019). we define the linear MDP model studied in the latter work.
Definition 2. An MDP is said to be a linear MDP if there exist known feature map 1/2 S x A - Rd unknown signed measures p S R.a. and an unknown vector 1) E TR such that (1) P(s P(s'(s,a)
knownfeaaure
(wbss, a), u(s')) holds for all states s, s' and actions a, and (2) Bir s, s,a] (v(s, a).n)
Linear MDPs are studied by Jin et al. (2019), who establish a -T-type regret bound for an optimistic
algorithm. This assumption already subsumes that of Yang Wang (2019), and related assumptions
also appear elsewhere in the literature (Bradtke & Barto] 1996, Melo & Ribeiro 2007 Zanette
et al. 2019). In this section, we show that optimistic closure (Assumption 2) is strictly weaker than assuming the environment is linear MDP.
Proposition 1. If an MDP is linear then Assumption 2 holds with G = {(s,a) + (w, (8,,)) E [Ba).
Proof. The result is implicit in Jin et al. (019)) and we include the proof for completeness. For any function g, observe that owing to the linear MDP property
g(s,, , a') s, a = ((((sa).)) n) + / / a), u(s')) max g(s', ga' a d')ds', a'
(g) a) =
max
o'
which is clearly linear function in (s, a). Hence for any function g. which trivially includes the optimistic functions, we have (g) E G.
Thus the linear MDP assumption is stronger than Assumption 2 Next, we show that it is strictly stronger.
There exists an MDP with H 2, d 2, |A| 2 and |S] oo such that Assump- nion 2 is satisfied, but the MDP is not a linear MDP.
Proposition
Thus we have that optimistic closure is strictly weaker than the linear MDP assumption from Jin et al. (019).. Thus, our results strictly generalize theirs.
Proof. Fix the link function to be f(=) = 2. We first construct the MDP. Set the action space A = (a1,02); We use e, denote the 7th standard basis element, and let x (0.1/T, 0.T/T) be a fixed vector where I appears in the construction of Gup- Recall that 81 is the first state in each trajectory. our example, for all a A, 0(s1, a) is sampled uniformly at random from the set {ae; + (1 a)e2: a E [0, 1]}. The transition rule is deterministic and given by:
Va A: ((82, a) if (ds1, a) a01 + (1 a)ee-
Moreover, for the reward function, R(s1, a) = 0 and R(s2. a) = 0.la/T.
We first show that the Linear MDP property does not hold for the constructed MDP and the given feature map cb Let s be the state with d(s a) e2 and s(2) be the state with o6s (2) a) e1. Notice that we deterministically transition from (1) to a state s/ with ((s a) 0, and we de- terministically transition from (2) to state sf?) with p(s ,a) ær which already fixes the whole transition operator under the linear MDP assumption. Thus, under the linear MDP assumption, we must therefore have randomized transition for any state 81 with ((s),a) ae + (1 a)e2 where (0, 1). This contradicts the fact that our constructed MDP has deterministic transitions everywhere, so the linear MDP cannot hold.
We next show that Assumption holds. Consider an arbitrary optimistic Q estimate of the form g(2) min 0 VV2 Az) Gup- Notice that for 0.1/T)) we always have that
5

---

Published as a conference paper at ICLR 2021
Algorithm The LSVI-UCB algorithm with generalized linear function approximation.
1: Initialize estimates Qn,0 = for all S H and QH+1, = 0 for all 1 1 T:
2: Set 7 C'K' k / + M + K + d² In((1 + K +TTH) for a universal constant C:;
3: for t-= = 1, ... _T' do
4: Commit to policy fn.e - argmax Qn,c-1(s,a):
5: Use policy _t to collect one trajectory {(p,,r, Cn,e The M==
6: for h = H, H 1,..., do
7:
Compute Th,r - @(sh.r: ah,7) and yhur & Thet + max Qu+La(Sn+L..d)) for all
I
8:
Compute ridge estimate
One - argmin [un, ((2),,;0)))
(I)
10012511 rst
9: Compute An, Erse Th +1;
Construct (n, a) 2 min (1,5(0(s,a) (()))) + 11((s, +
10:
end for
12: end for
r TV Ar I 1 for any 0 Ba and A with || I 1. Moreover, for all $2, i.e., the second state in the trajectory, we always have @(52, a) az for some E [0, 1J. Hence first term in the minimum, and, by direct calculation, we have that when ((s, a) = de1 + (1 a2)2
ignore the
(1)) a) ox 0 + v Axr
= a(x To + YV x Az) aco-
Hence we can write Ti(g) = (Ø(s, a). (co, 0)}, which verifies Assumption
ALGORITHM AND MAIN RESULT
We now turn to presenting our algorithm and main results. We study a least-squares dynamic pro- gramming style algorithm that we call LSVI-UCB, with pscudocode presented in in/Aogrithhm I The algorithm is nearly identical to the algorithm proposed by Jin et al. (2019) with the same name. A similar algorithmic template has also been extensively studied in the tabular setting [Azar et al.) 2017;; Dann et al. (2017); Simchowitz & Jamieson| (2019). albeit with slightly different confidence bounds. As our algorithm applies to all of these settings, should be considered as generalization.
The algorithm uses dynamic programming to maintain optimistic Q function estimates (Qn,) for each time point h and each episode t. In the {th episode,
the previ- ously computed estimates define the greedy policy (-) è argmax, 1 which we use to take actions for the episode. Then, with all of the trajectories collected so far, we perform dynamic programming update, where the main per-step optimization problem is (1) Starting from time point H, update using our class of GLMs. At time point H, the covariates are {ő(sH,r aH (.,,))rrs Dr and the regres- sion targets are simply the immediate rewards (r.,-)rst- For time points H, the covariates
Q function estimates by solving constrained least squares problems
defined similarly as (Ø($I,T (h,T))rse but the regression targets are defined by inflating the learned Q function for time point h by optimism bonus.
In detail, the least squares problem for time point h 1 yields parameter 0 and we also form the second moment matrix AstLe of all the covariates at time h + 1 that we have seen so far. Using these, we define the optimistic Q function Q841, a) A min {1. f(((((((())))) a), 1,)) + (lo(s, a) A. }. In our analysis, we verify that Qu+1, is op- timistic in the sense that it over-estimates Q" for every (s,a). Then, the regression targets for the least squares problem at time point h are rh,r + maxo'eA 201+1,(sh+1..7 a'), which natural stochastic approximation to the Bellman backup of Q1+1. Applying this update backward from

---

Published as a conference paper at ICLR 2021
time point H to 1, we obtain the Q-function estimates that to define the policy for the next episode.
The main conceptual difference between Algorithm 1 and the algorithm Jin et al. (019)) is that we allow non-linear function approximation with GLMs, while they consider only linear models. On more technical level, which we find easier to analyze, while they use the ridge regularized version.
constrained least squares for dynamic programming backup
On the computational side, the algorithm is straightforward to implement, and, depending the link function ʃ, it can be easily shown to run in polynomial time. For example, if f is the identity map, then i equivalent
standard least square ridge regression, which can be solved in closed form. formula to amortize matrix inversions, and, by doing
Moreover, we can use the Bberman-Morriise so, we obtain a running time of O (d ( The dominant cost in this calculation is evaluating the optimism bonus when computing the regression targets. In practice, using an epoch schedule or incremental optimization algorithms for updating Q would yield an even faster algorithm. Of course, with modern machine learning libraries, it is also straightforward to implement the algorithm with non-trivial link function f. even though (1) may non-convex.
4.1
MAIN RESULT
Our main result a regret bound for LSVI-UCB when the link function satisfies Assumption and the function class satisfies Assumption 2
Theorem 1. For any episodic MDP, with Assumption 7 and Assumption 2 and for any T, the cumulative regret of Algoorith 1
o (HKK T + K de (n(KH)) Tdin(T/dd) ō (HV
with probability 1 1 1/(TH).
The result states that LSVI-UCB enjoys vT -Terreret for any episodic MDP problem and any GLM, provided that the regularity conditions are satisfied and that optimistic closure holds. As we have mentioned, these assumptions are relatively mild, encompassing the tabular setting and prior work on linear function approximation. Importantly, no explicit dynamics assumptions are required. Thus. Theorem is one of the most general results we are aware of for provably efficient explo- ration with function approximation.
Nevertheless, to develop further intuition for our bound, it worth comparing prior results. First, in the linear MDP setting of et al. (2019), we use the identity link function so that K = K = 1 and M = and we also are guaranteed satisfy Assumption 2 In this case, our bound differs from that of et al. (019) only in the dependence on H, which arises due to a difference in normalization. Our bound is essentially equivalent to theirs and can therefore be seen strict generalization.
To capture the tabular setting, we use the standard basis fcaturization as in Fact 2 and the identity link function, which gives |S][AA, K = = 1, and M 1. Thus, we obtain the following corollary:
Corollary 2. For MDPs with finite state and action spaces, using feature map o(s, & Ca.a E RISIXIAI, for any T, the cumulative regret of Algorithm 1 Ö (H (HVISPAA)TT) with probability HTH.
Note that this bound is polynomially worse than the near-optimal Õ(H /SA + 42 bound of Azar et al. (2017). However, refined analysis specialized to the tabular setting can be shown to obtain a better regret bound of Ö [ (ISRIAPPT) Of course, our algorithm and analysis address problems with infinitely large state spaces and other settings that significantly more complex than tabular MDPs, which we believe is more important than recovering the optimal guarantee for tabular MDPs.
We use Ō (-) suppress factors of M, K, H., and any logarithmic dependencies the arguments.
7

---

Published as a conference paper at ICLR 2021
5 DISCUSSION
This paper presents a provably efficient reinforcement learning algorithm that approximates the Q' function with generalized linear model. We prove that the algorithm obtains O(Hvd)) (dT) regret under mild regularity conditions and new expressivity condition that we call optimistic closure. These assumptions generalize both the tabular setting, which is classical, and the linear MDP setting studied in recent work. Further they represent the first statistically and computationally efficient al- gorithms for reinforcement learning with generalized linear function approximation, without explicit dynamics assumptions.
We close with some open problems. First, using the fact that Corollary appplis beyond GLMs, can we develop algorithms that can employ general function classes? While such algorithms exist for the contextual bandit setting (Foster et al. (2018). it seems quite difficult to generalize this analysis to multi-step reinforcement learning. More importantly, while optimistic closure is weaker than some prior assumptions (and incomparable to others), it is still quite strong, and stronger than what is required for the batch RL setting. An important direction to investigate weaker assumptions that enable provably efficient reinforcement learning with function approximation. We look forward to studying these questions in future work.
REFERENCES
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, 2011.
Yasin Abbasi- Yadkori, David Pal, and Csaba Szepesvari. Online-to-comfidenee- conversions and application to sparse stochastic bandits. International Conference on Artificial Intelligence and Statistics, 2012.
Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pe-pg: Policy cover directed explo- ration for provable policy gradient learning. arXiv preprini (.XXx:2007.08455: 2020.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 2008.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin F Yang. Model-based reinforce- ment learning with value-targeted regression. arXiv preprint arXiv:2006.01 107, 2020.
Mohammad Gheshlaghi Azar, Ian Oshand, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference on Machine Learning, 2017.
Marc Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. In Advances in Neural Information Processing Systems, 2016.
Steven J Bradtke and Andrew Barto. Linear least-squares algorithms for temporal difference learning. Machine Learning, 1996.
Ronen I. Brafman and Moshe Tennenholtz. R-MAX A general polynomial time algorithm for near-optimal reinforcement learning. The Journal of Machine Learning Research, 2002.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy opti- mization. arXiv preprint arXiv:
2019.
Jinglin Chen and Nan Jiang. information-theoretr considerations in batch reinforcement learning. In International Conference on Machine Learning, 2019.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning. In Advances in Neural Information Processing Sys- tems, 2017.
Simon Du, Sham M Kakade, Ruosong Wang, and Lin F Yang. Is good representation sufficient for sample efficient reinforcement learning? 190.0:191, 2019a.
8

---

Published as a conference paper at ICLR 2021
Simon S Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Lang- ford. Provably efficient RL with rich observations via latent state decoding. In International Conference on Machine Learning, 2019b.
Amir-massoud Farahmand, Csaba Szepesvári, and Rémi Munos. Error propagation for approximate policy and value iteration. In Advances in Neural Information Processing Systems, 2010.
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In Advances in Neural Information Processing Systems, 2010.
Dylan J Foster, Alekh Agarwal, Miroslav Dudík, Haipeng Luo, and Robert E Schapire. Practical contextual bandits with regression oracles. In International Conference on Machine Learning, 2018.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. arXiv: /8/.:2///2.02900, 2018.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Con- textual decision processes with low Bellman rank PAC-Icarnable. In International Conference on Machine Learning. 2017.
Chi Jin, Zeyuan Allen -hu, Sebastien Bubeck, and Michael I Jordan. Is Q-lcarning provably effi- cient? In Advances in Neural Information Processing Systems, 2018.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. arXiv:1907.05388. 2019.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning polynomial time. Ma- chine learning, 2002.
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. PAC reinforcement learning with rich observations. In Advances in Neural Information Processing Systems, 2016.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contex- tual bandits. In International Conference on Machine Learning, 2017.
Francisco S Melo and M Isabel Ribeiro. Q-learning with linear function approximation. In Confer- ence on Learning Theory, 2007.
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pp. 2010-2020, 2020.
Rémi Munos. Error bounds for approximate policy iteration. In International Conference on Ma- chine Learning, 2003.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. The Journal of Machine Learning Research, 2008.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped DQN. In Advances in neural information processing systems, 2016.
Victor H Peña, Tze Leung Lai, and Qi-Man Shao. Self-normalized processes: Limit theory and Statistical Applications. Springer Science Business Media, 2008
Max Simchowitz. and Kevin Jamieson. Non-asymptotic gap-dependent regret bounds for tabular
mdps. arXiv: 2019.
Alexander L. Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L. Littman. PAC
model-free reinforcement learning. In International Conference on Machine Learning, 2006.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAI Xi Chen, Yan Duan, John Schul- man, Filip DeTurck, and Pieter Abbeel. #Exploration: A study of count-based exploration for deep reinforcement learning. In Advances in Neural Information Processing Systems, 2017.

---

Published as a conference paper at ICLR 2021
Lin F Yang and Mengdi Wang. Reinforcement leaning in feature space: Matrix bandit, kernels, and regret bound. arXiv:I905. 10389, 2019.
Andrea Zanette, David Brandroobrenner, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. arXiv preprint arXiv: 1rXiv:191..00500 2019.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman emror. arXiv preprini wrXiv:2003.00155 2020a.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Provably efficient reward-agnostic navigation with linear value iteration. arXiv preprint 20Xiv:2008.07737,, 2020b.
Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for dis- counted mdps with feature mapping. arXiv preprint 2XXv:20006.13663. 2020.
A PROOF OF THEOREM
We now provide the proof of Theorem deferring some technical details to later sections in this appendix. The proof has three main components: regret decomposition for optimistic Q learning, deviation analysis for least squares with GLMs to ensure optimism, and potential argument to obtain the final regret bound.
Regret decomposition. The first step of the proof is regret decomposition that applies generi- cally to optimistic algorithms The lemma demonstrates concisely the value optimism in rein- forcement learning, and is the primary technical motivation for our interest in optimistic algorithms.
We state the lemma more generally, which requires some additional notation. Fix round / and let (Qı,e-)AssH denote the current estimated Q functions. The precondition is that Qh,c-1 is optimistic and has controlled overestimation. Precisely, we assume that there exists a function enf 8 A R4 such that
(7(s,a) Qn.-I((sa))
Qn,1-1(s,a) S (h((ntLo-)(ssaa)) + cnf
(3)
We will verify that estimates Qu. satisfy these properties subsequently. Before doing so, state the regret decomposition lemma and an immediate corollary.
Lemma 1. Fix episode and let Fi-1 be the filtration of (Sh,r Ch,r, (rer)rre Assume that
Qua-1 satisfies (3) (3) for some function cnf Then, if n. argmax 1h,t- (1, a) is deployed
we have
H Σ 1=
V*
Thes
Fe-1
S +
1 an.),
where LE [Se| Fe-1l= and (Sel S 2H almost surely.
Corollary 3. Assume that for all Qr,1-1 satisfies and that ni is the greedy policy with respect to Qh,t-1- Then with probability at least - 8, we have
Reg (T)
enf 1 O
Proof of Lemma
Observe that
V* E (s) < E ((....(((1,
E (11
E (cnf E (T(Q m())))
E [cnf];=-((91 + Eri $1, aj = m((s:)
Egyem Q2,1-1(52 (s
'Related results appear elsewhere in the literature focusing on the tabular setting, see e.g. Simchowitz. &
Jamieson 2019).
10

---

Published as a conference paper at ICLR 2021
Throughout this calculation, $1 μ.. The first step here is by definition, the second uses the opti- mism property for Q1,t-1. The third uses that ny is the greedy policy with respect to Q1,--1 while the fourth uses the upper bound on Q1.-1- Finally we use the definition of the Bellman operator and the fact that Te is the greedy policy yet again. Comparing this upper bound with the expected reward collected by Re we observe that r1 cancels, and we get
H
H Σ The [i h=2
Σ The Fr-1 S Er,, [onfi, TT - Em 122-1 Te
V--E E
At this point, notice that Q2.c-1(2,, (s2)) is precisely what we alreacy upper bounded at time point h = and we are always considering the state-action distribution induced by Tt. Hence, repeating the argument for all h, we obtain
V E
Thet Ft-1 Σ 1=1
Ex, (enfa,e-1(0))) an); = Σ (1f,, an,1) Sta
h=1
where Se A Em=
Shie
and
Sn,e A En, [enfa,r-1 (8h+ me(sn))) - -cf...-1(9h..
which is easily seen to have the required properties.
The lemma states that if Qa.r-1 is optimistic and we deploy the greedy policy Tr, then the per- episode regret is controlled by the overestimation error of Qt, 1, up a stochastic term that enjoys favorable concentration properties. Crucially, the errors are accumulated on the observed trajectory, or, stated another way, the enf 1 is evaluated on the states and actions visited during the episode. As these states and actions will be used to update Q, we can expect that the enf function will decrease on these arguments. This can yield one of outcomes: either we will incur lower regret in the next episode, or we will explore the environment by visiting new states and actions. In this sense, the lemma demonstrates how optimism navigates the exploration-exploiiai multi-step RL setting, analogously to the bandit setting.
tradeoff in the
Note that Lemma 1 does not assume any form for Qu.t-1 and does not require Assumption 2 In particular, they are not specialized to GLMs. In our proof, we use the GLM representation and |Assumptio 2 to ensure that (3) holds and to bound the confidence sum in Corollary 3] We believe these technical results will be useful in designing RL algorithms for general function classes, which is a natural direction for future work.
Deviation analysis. The next step of the proof is design the enf function and ensure that (3) holds, with high probability. This is the contents of the next lemma.
Lemma 2. Under Assumption and Assumption 2 with probability 1/(HH), we have that ht,
[(((s,,) On.))) Ta (s, S (1bb(s,)))) (1)(())))))
where y, Ar. are defined in Algorithm 1
simple induction argument then verifies that (3) holds, which we summarize in the next corollary.
Corollary 4. Under Undumpisnumtiion 1 AsndAAssumption with probability 1 1- H)THH,,, we have that (3)
holds for all i, h with cul h,t-1 (8, = 22 2 [0(s -
As the proof Lemma i rather long and technical, we defer the details to the appendix and instead explain the high-level argument here. The proof requires an intricate deviation analysis account for the dependency structure in the data sequence. The intuition is that, thanks to Assumption 2) and the fact that Q Gup- we know that there exists parameter θy,; such that f((((s, a), 0n,t)) Tr. (Q)++1))(ss.....))))))))))))))) (s, a).
easy to verify that Or, r is the Bayes optimal predictor for the square loss problem in (1) and so with a uniform convergence argument we can expect that d, is close to 0,,.. which is our desired conclusion.
11

---

Published as a conference paper at ICLR 2021
There two subtleties with this argument. First, want to show that Pn.e and 0v.e close in data-dependent sense, to obtain the dependence the A Mahhalllaoo norm in the bound. This can be done using vector-valued self-normalized martingale inequalities (Peña al.) 2008). in
prior work on linear stochastic bandits (Abbasi- Yadkori et al. 2012 Filippi et al. 2010 Abbasi- Yadkori al. 2011).
However, the process we are considering is not a martingale, since Q4+1, which determines the regression targets yh.r, depends all data collected far. Hence !/,, is not measurable with respect to the filtration Fr. which prevents us from directly applying a seff-normalized martingale concentration inequality. To circumvent this issue, we use a uniform convergence argument and introduce a deterministic covering of Gup. Each element of the cover induces a different sequence of do obtain martingale structure. Then,
regression targets ,,, but the covering is deterministic, show that the error term for the random Qi++1. that need to bound close to corresponding term for one of the covering elements, and we finish the proof with a uniform convergence argument over all covering elements.
The corollary is then obtained by straightforward inductive argument. Assuming Q4+1. dominates Q*, it is easy to show that Qn. also dominates Q", and the upper bound is immediate. Combin- ing Corollary 4 with Corollary all that remains upper bound the confidence
Potential argument. To bound the confidence sum, we use a standard potential argument that appears in number of works stochastic linear bandits. We summarize the conclusion with the following lemma, which follows directly from Lemma 11 AlAbaaii-Yadiae et al. (2012).
Lemma 3. For any h H have that
T
(1blsh,aann)ll S 2d1n(1 + T/d).
Wrapping up. Equipped with the above results, now prepared prove Theorem
of Theorem 1 Assume that Corollary 4 holds for all 1 < h S H and 1 s s T. Apply- ing Lemma I andd the definition cul implied by Corollary the cumulative expected regret at most
Proof
T Thet
TV
1=1
T
+
min 2, (10
}
1=1
t=1 h=1
H
T (o..),eran..))le
5
Σ
G +
T22
h=1
Σ
Σ
T
22d 2n(11((1 T/d).
Here, the second step follows from the Cauchy-Schwarz inequality, and the last step an application Lemma 3) The first term forms martingale, and we know that (Sel S 2H. Therefore, by Azuma's inequality, have that with probability least 1/TH
T
EGS WSST
Finally, using the definition of 7, the final regret is upper bounded by
Reg(T) < (TI(T)) HKK-1 V(M K di In((K TYTH)) Tdln(1 ( TTd))
Ō (HIVdT))
which proves the result.
12

---

Published as a conference paper at ICLR 2021
B PROOF OF LEMMA 2 AND COROLLARY 4
To facilitate our analysis we define the following important intermediate quantity:
B Ba: f((o(s.a), (n,)) e E rh + max 1n+1, s, a'EAA
In words, On is the Bayes optimal predictor for the squared loss problem at time point in the (dh episode. Since by inspection Qu+1, Sup. by Assumption 2 t.
we know that On exists for all h and
Lemma 4, For any 0, 0', E IRd satisfying 110112 1001 |=112 1
x² Kxx, O' 0 [5((,, 0')) [((2, 0)) K² 10' 012
Proof.
By the mean-value theorem, there exists = 0 + 2(0' - 0) for some À E (0, 1) such that f((x, 0')) - f((xx)))))))))))))))))))))))ff = (Vef( 0)), - ))) On the other hand, by the chain rule and Assump-
tion
Vos((x,0) ((x 0) Hence,
(Vaf(=T0), 0 0)|² < f( 03) 1x,0'' -01²² < 1= 01 s K2 100 01 (Vof(x 0 - 0)1² 2 x² (xx 0' - 0)1
which are to be demonstrated.
Lemma 5. For any 0 E S L, there exists a finite subset V. C. Gup with In 1// s 6dc In(2(1 +
K + +T)EE), such that
sup min sup lø(0(s, a)) v(o(s, ()(ss,))ssse gEgng vEVe
Proof. Recall that for every g E Gup. there exists 0 E Ba, 0 < S r and ||Allop S such that
g(z) f((z,, 0)) + r [|= Let O2 S. Ba. I' S [0.1] and MM S [M S ||A <
1} be finite subsets such that for any 8, 7, A, there exist f' E O o E Te, A' M, such that
max {10- 0'1 17 71, llloop) Se'
where e' E 10 will be specified later in the proof. For the function g Gup corresponding to the parameters 0, 7, A the function g' corresponding to parameters 0' 0',7, A' satisfies
sup (o(((()))) g' (é(s,a))) s sup 1g(x) g'(x)) s.a
< sup [/((z, 0)) f((x, 02)) + ||0l ||=
xE2,
< ||0 - 01112 + 1 - - + ||| - ||==||Ar|
< K |10 01112 + 11 / Tx (A - AA)aa
< KE' Ks' +I'' < (1+K+1)+
In the last step we use E < 1. Therefore, if we define the class Ve {(s.a) + min(1, f(o(s, a), 0*) 7 [|o(s, a) 0' Oe, T,, A E Mel. know that the ering property satisfied with parameter (1 + K+ Setting s' = e² /(1 (1 + K + r)2 we have the desired covering property.
Finally, we upper bound in [Vzl. By definition, we have that In V4 < In O + In Tel M Furthermore, standard covering number bounds reveals that In |0,1 < d In(2/e"), In [Tal In(1/e) and In MM] S d² l2(e'').. Plugging in the definition of e' yields the result.
For the next lemma, let F,-1 2 o (f(shr an,r, The Fre)) be the filtration induced by all observed trajectories up to but not including time t. Observe that Q.,-1 and our policy thet are F, mea- surable.
13

---

Published as a conference paper at ICLR 2021
Lemma 6 (Restatement of Lemma 2). Fix any 1 St T and 1 S H. Then long m, is Fi-1 measurable, with probability 1 {/ holds that
[()((s,)), 0n,,) - [((6(8, a), 0n.e)) $ min (2.7 |0 a)lla??)>
Vs,a.
yor 2 CKK V1+ M da In ((1 K тYTH) and 0 < C is universal constant.
Note that this is precisely Lemma as O,.e is defined as f((((s, a), 0n, = Tn (((
Proof. The upper bound of 2 is obvious, since both terms are upper bounded by in absolute value. Therefore we focus on the second term in the minimum. To simplify notation we omit the dependence on h in the subscripts and write Tr. Vr for 2h,5 and Hh.r. We also abbreviate 0 - 0r.c and 0 On.e.
Since ||0| | S the optimality of for implies that
6)) ((((E,)))) 8)) 8)) U+) S Σ (f((E,)0)) y=)²
rst
TSt
Decomposing the squares and re-organizing the terms, we have that
Σ
(S((cT,))
22
(((((())))))))))))) (
(5)
TSt
where & - yr [((xT: 0)). By the fundamental theorem of calculus, we have
((2..8) -
(0000) f((sdss (x,, 1 8) S/' f'((IT, s0 + (1 s)8))ds.
f((z,,0) 0)) - f((x,, 0)) =
DD
Using this identity both sides of (5) we have that
Σ DZ 0 (0r. 2 Σ
(6)
rst
55t
Note also that, by Assumption
D, satisfies x² $ D2 < K2 almost surely for all T.
The difficulty in controlling (6 is that 0 itself is a random variable that depends on {(E,, Vr wr)rrs In particular, want that Eks, D, (I,, _F-1]] O for any fixed o, but this is not immediate as i depends on Ty. To proceed, we eliminate this dependence with a uniform convergence argument. Let E 1) be covering accuracy parameter be determined later in this proof. Let V. be the pointwise covering for Gup that is implied by [emma 5) Let Ja E V. be the approximation for Qh+1,e that satisfies
(4) By Assumption there exists some 0F E B& such that
Vs [((((,a)))0)) E
max (e(6'aa') 1,0 a'EA
Now, define 3 and { as
u a rh. + max (5
$ a yo f((zh,r, 88))
E'EA
The right-hand side of (6) can then be upper bounded as
2
Σ E Dr (z,, 0 0)
2 Σ
DD 0 +4.
(7)
rSt
rSt
where A < KL x max
5 Erl almost surely.
14

---

Published as a conference paper at ICLR 2021
Upper bounding A in (7) Fix T I t. By definition, we have that
|ef 2 - 10 - yr + [ 8)) f((((,, (1)1
< max I (81+1,7, Qut1, a)) + K 110 -0il2 aEA
(8)
+ KE (K 1)e,
(9)
where (8) holds by Lemma 4 and (9) follows from Lemma 5 In particular, the bound on |10
0+
can be verified by expanding the definitions and noting that 9s pointwise close Q1+1,e- There- fore, we have
| S (K + 1)
(10)
Upper bounding (7) Note that D, is function of Ir. 0, and 0. For clarity, we define (,,00') := So (I s0 (1 s))))))))sss As If(())] s M for all |a| I 1 and || S 1, we have that for every 0,0',0,' E Ba
D+(00,0- - D= 0) S ! [(((r 50 + (1 -)00)) 8 (( s0 + (1 -=)0))))) do
S M(10 0||2 + 110' - 0' (12)-
Hence, for any (0, 8") and (0, 0') pairs, we have for every r that
< (5., (+0,0'') 0') D. -0)0- (0,
$ ( 8¹)
8) -
x 1112+ (. 8') (Ile - 0||2 + +116' -8' -1112)
< M(1 Ó||2 + 110' - (1 x 2 0112 10' 01112)
< (2M + <] 0||2 110' (12)
Here we are using that |5+1 S
We are now in position to invoke Lemma 8 Consider fixed function Je, which defines fixed OF We will bound Erge 38 (1e,, (0, (0 (0- - 0')) uniformly over all pairs (0, 0'). With gr. 0z fixed and since is Fi-1 measurable, we have that {ar, Str. are random variables satisfying Eisž Pirrsii--1
O. For (0, (') we define the function ( Φ) (x. D, ( p*)) which as have just calculated satisfies 19(ø,, Φ) g(x,, d')l (2M + K) lló 0'112- For
5' E (0, 1/2) with probability 1 - 8' we have Ve (0, 0') E B3:
Σ (E,, (+ 8') S (2M+ +2 + vV(0) rst
(2dln(4T) + 1n(/8")
<4max M + K 2ddn(44) + (n(88'), V (V( + In(1/8))
(11)
where ((0) 2 Ergr
2 The last inequality holds because a + s max b).
Next, take union bound over all gr V. (11) holds for any Ie and any subsequently induced
choice of E with probability at least 1 - L 8" In particular, this union bound implies that (11)
holds for the choice of 9s that approximates Q4+1, Therefore, combining (6) (7) (10) with
for this choice of Ic, we have that with probability at least 1 |
Σ P5t
0 0- 2A +
Σ r
(,, Ø))
2(K 1) 8 max
M + K /
15

---

Published as a conference paper at ICLR 2021
Observe that the left hand side is precisely V(6.0). 8). Now, set 1/(2(K 1)2T) and 8' 1/(1=[T222) and use the bound on In V4l from Lemma 5 to get
2ndn(44)++ -
12d - ryT) S 2
S v (4d 24d In 2n
Therefore, we obtain
V(O. 1 ++88m max
M K 28d In + K K V(0, 0) / [ +)TH
S max
M + K + 28
V(0,0) 12 K -T)HH)
Subsequently,
V(0,0) Σ DZ 0
$ 16 max {1 + M + K 28d In(2(1 + K +TTH), 448 1n((1 + K ++D)TH)
s C M + K + df In K + r)TH)),
where 0 < Cv < oo is universal constant.
Next, note that D 2 x², thanks to Assumption
We then have
(0 - 0) ( 0) v K V(0,0) s Cvx V +
where AR, Erer T x.y Finally, for any (s, pair, invoking Lemma 4|and the Cauchy-Schwar inequality we have
[((((s, ())((s,)),))) 0)) - a(o(s,a)) 81) S (),ss,),00-1 0)
$ K <K (0- -) A,,, 8) ((s a) (s.00s
$ CvKKn / 1+ + M K In + K +TTHH x 110(s, a)
which is be demonstrated.
Corollary& 5 (Restatement of Corollary 4). With probability 1 1- 1/(HH,, Qn,(ss,a) (s, holds for all h, s,
Proof. Fix 1 S 6 S. T. We induction h to prove this corollary. For h H+,, Qm+1,(()))))))) 2 Q#+1( ((.)) clearly holds because QH+1,t Qir+1 O. Now assume that Qx+1, Qi+1. and let us prove that this is also true for time step h.
Since Q a')) Qi+ a') for all s',a', have that f((d(s, a), Bn,1)) f((((s, 0;))
for all as pairs. Then, by the definition of Qn, and Lemma 6 with probability 1- (TH2 it holds uniformly for all (s, a) pairs that Qr, a) > =[(Ø(s, a), ln.))). Hence, with the same probability, we have Qs. a) 2 (i,s, a) for all (s, a) pairs. A union bound over all t < T and < H completes the proof.
C TAIL INEQUALITIES
Lemma 7 (Azuma's inequality). Suppose Xo, X1, X2........5 .x form a martingale (i.e,
3[X Xx] = X&) and satisfy [X+ -x Cb almost surely. Then for any >> 0.
Pr |X, - Xol 2 2exp
2
2Σ
N 1=1
16

---

Published as a conference paper at ICLR 2021
Lemma 8. E
Let {5r, Ur5r be random variables such that
Eis, 1 2.-1,65-1. and &r Σ 1 almost surely. Let q : (u, Φ) + R be
an arbitrary deterministic function satisfying ig u, Φ) q(u, 0')l S ClI o' for all and d',
where o, & E TR.P. Then for any ò E (0, 1) and R 0,
Pr Vo E (b(
+ Eqquu,o の)) SC+2 + Vo(() (DIn(2tR)++m(1))
21-6,
where (D(R) _ far E RD, ||0|| S RJ and (g(0) - Erg (u
Proof. Let > 0 be a small precision parameter to be specified later. Let H. C Bp(R) be a finite 6- covering of (R) such that SuPaEBp(R) min || 2|12 I e. Using standard covering number arguments, such a covering exists with In [H] _ (2R//c)).
This implies For any (D( let d' & argmin |1 = 2112- By definition, 100-0'1 S
E Er (r(g(ur,)) Φ) a(u,, o''l 0.
Cte because |erl s almost surely. Subsequently, for any
Pr
3Ø E (R(R):
Σ Er((u,,0)
> Cte A
Pr
Ee E :
Σ Ea(u,, (8) >
Σ Pr
Σ Erlu,, r=1
> A
YEH
where the last inequality holds by the union bound.
For any fixed d' E H, Muur, o3) only depends on uy, and therefore [E(Er g(ur, d')] = 0 for all т. Invoking
Lemma 7 with X, Er'er (rrg 0²) and C, = Ig(u,', d')l. we have
}
A
A
Pr Σ Ea(uu, 25)
A
s 2xp
2exp
2 2
(ur
(u,, o)
(V)(
Equating the right-hand side of the above inequality with 8' and combining with the union bound application, we have
Pr
Oe E Ba(R):
Σ Er 6) Cte + / (V)(d)) In(/6'))
8
(12)
Further equating 8' 8/| and using the fact that In |7| < D (2(2//),, we have
Pr 3 Ba(R): Σ Erg(ur, x)) Cle
(V()) 5.
Finally, as Ig(u,, Φ¹) a(ur, 6)1 S.e we have Vi(o") - (v) 21e and so
Σ Era(ur > Cle + / +2 +n(1/))) 26.
Pr 76 E BD(R):
Setting = 1/t in the above inequality completes the proof.
17


Reviews:
[{"review_id": "fwYSy-IrnS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors studies an episodic MDP learning problem, where they propose to study an Optimistic Closure assumption which allows the Q function to be expressed as a generalized linear function plus a positive semi-definite quadratic form. They motivate the assumption by showing that the assumption allows the tabular MDP case to be modeled, and that the Optimistic Closure is in fact a strictly weaker assumption than the linear MDP assumption made in previous related works. The authors then proceed to the design and analysis of the LSVI-UCB algorithm, which involves estimating the the parameter of the GLM model by a ridge estimator and adding an optimistic exploration bonus to the Q function. The authors propose a regret bound for the algorithm.\n\nThe proposed work is an interesting development to the line of research on RL with function approximation, and is large well written. I am in favor of acceptance, given that it provides a non-trivial extension to what is known and the Optimistic Closure assumption seems to me to be closer to the reality than the linear MDP assumption. One suggestion is to investigate if other large scaled but structured MDP models, such as the Factored MDP model by Osband and Van Roy 2014 : https://papers.nips.cc/paper/5445-near-optimal-reinforcement-learning-in-factored-mdps, and the LQG model, satisfy the Optimistic closure assumption with appropriate choices of $\\phi, f$.\n\n\nMinor comments:\n\nIn the abstract, brackets are missing for the d^3\\sqrt{T} regret bound.\n\nOn page 3, $\\Gamma$ should be replaced by $\\gamma$.\n\nOn page 5, MPD -> MDP", "extra_scores": {}, "extra_text": {}}, {"review_id": "Z2GWArKY92Z", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The backdrop for this work is the linear MDP model. In linear MDPs, typically the transition function is assumed to be a low rank matrix in the span of d feature vectors (over S, A); such an assumption lends itself to regret bounds that only scale with d (and not explicitly with the size of the state space). \n\nThe first contribution here is to establish that it is enough to assume that the function approximation class (for Q functions) is closed under an optimistic (~inverse covariance bonus) version of Bellman update. Qualitatively, this is desirable because this is an assumption on the Q-function class and does not present an explicit assumption on dynamics, unlike linear MDPs. The paper establishes that this is strictly more general the linear MDP assumption, where the above-discussed closure holds for backups of all functions (and not just linear Q functions). It must be noted that Jin et al had already noted & observed that such an assumption is enough, and that their proofs accommodate this. \n\nThe second contribution is that the Q function class is generalized here to accommodate generalized (vs just) linear models.\n\nStrengths:\n+ I think this is an important relaxation in assumptions to point out. Bellman closure of the policy class seems like a necessary precondition; optimistic variant is a bit further, yet more palatable than a factorization of the dynamics matrix.\n+ The GLM part of the extension could be significant in practice, given similar observations in supervised learning.\n+ The proof exposition (Appendix A) here is potentially cleaner that Jin et al.\n\nComments:\n+ Regarding the first contribution, did the authors think it was necessary to modify any part of the proof from Jin et al? From my reading, since all concentration arguments were always made on backups, it seemed their proof did indeed go through.\n+ Regarding the second contribution, what changes did does this work introduce to handle GLMs? I understand part of the answer may be in Lemma 6.\n+ Typo: Page 5 > linear MPD?", "extra_scores": {}, "extra_text": {}}, {"review_id": "NJpYxFkocwu", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary  \nThis paper analyses an existing algorithm (LSVI-UCB) with generalized linear function approximation instead of conventional linear function approximation.  Under this generalized linear setting, they propose a so-called “optimistic closure” assumption which is shown to be strictly weaker than the expressivity assumption in the conventional linear setting. The paper then proves that LSVI-UCB still enjoys sub-linear regret in the generalized linear setting with strictly weaker assumptions. The paper also derives a general error propagation through steps that do not require a closed-form expression of the empirical dynamic and reward functions as in the linear case; this could be applicable to general function approximations.   \n### Strong points \n-\tNovelty: The generalized linear setting appears novel and generalizes the linear settings. \n-\tSignificance: The optimistic closure appears novel and is strictly weaker than the linear MDP assumption in the prior works. \n-\tCorrectness: A complete analysis that successfully retains a sublinear regret and honest comments on the limitations of the present work.   \n\n### Weak points \n-\tThe work is almost merely about analysis of an existing algorithm with modest algorithmic contribution (which however is not a big problem). There are some parts of the proofs pointed out in the Minor comment section that potentially require some attention (but I believe these are minor points which could be fixed if there is any issue)\n\n### Minor comments     \n-\tPeriod ‘.’ after the first sentence of the second paragraph of section 2.\n-\tFirst sentence of section 3: ‘MPD’ -> ‘MDP’\n-\tLemma 1: Should it be $\\pi_{h,t}$ instead of $\\pi_t$ there?\n-\tIn Appendix A: “We believe these technical results will be useful in designing RL algorithms for general function classes”. It seems that an analysis of LSVI-UCB with general function classes has recent done in [1] (?)  \n-\tIn Corollary 4, shouldn’t it be **2** $\\gamma \\| \\phi(s,a) \\|$ instead of $\\gamma \\| \\phi(s,a) \\|_{…}$?\n-\tAt the end of Page 12: “The first term forms a martingale” -> shouldn’t it be a “difference martingale” instead?\n-\tThe equation between eq. (5) and eq. (6) on page 14 does not look very right. I think the correct one should be the one with the RHS replaced by $\\langle x_{\\tau}, \\hat{\\theta} - \\bar{\\theta} \\rangle f’(\\langle x_{\\tau}, s \\hat{\\theta} + (1-s) \\bar{\\theta} \\rangle)$ for some $s \\in [0,1]$ (according to the mean value theorem). If this is true, I am afraid the bounds of the difference between $D_{\\tau}$ (after Eq. (10)) might not be precise. \n-\tThe second paragraph on page 12: “Hence $y_{h, \\tau}$ is not measurable with\nrespect to the filtration $F_{\\tau}$ ,  which prevents us from directly applying a self-normalized martingale\nconcentration inequality”. Should it be $F_{\\tau-1}$ instead of $F_{\\tau}$?\n\n-\tOn page 15, the paper says that E[   xi_tau^# | x_{1:tau}, xi_{1 : tau-1}^#   ] = 0. Do we really need that martingale structure when we already consider a fixed g_{epsilon}? Given a fixed g_{\\epsilon}, we already have E[   xi_tau^# | x_tau   ] = 0.   \n\n\n### Questions for the authors \n-\tIn Chi Jin et al. 2019, the regret is the difference between the optimal value function and the value function estimate while in the present paper, the regret is the difference between the optimal value function and the expected value of the cumulative rewards by the algorithm. What is the difference between these two notions of regret? Can it make the two results comparable? \n-\tIn the proof of ‘Fact 1’, why Q^*_H \\in \\mathcal{G}? For that to hold, it seems to require that the expected reward \\mathbb{E}[r_H] has a generalized linear form of \\mathcal{G}? If so, one way to fix it is maybe letting 1 <= h <= H (instead of 1 <= h < H) in Assumption 2? \n-\tIt seems that [1] already analyses LSVI-UCB with general function approximations which means that [1] is more general than the present work (?) If so, could the authors comment on the benefit of this work for a generalized linear function class given that an analysis for a general function class has been done? For example, does the present work give a tighter bound when considering generalized linear function as compared to the bound for a general function class in [1]?\n\n\n### My initial recommendation \nOverall, I vote for accepting. An extension from linear settings to generalized linear settings is novel and natural, and it must be done at some point. I think this work is nice for filling in that gap. \n\n### My final recommendation \n\nI remain my initial score after the discussion. \n\n### References\n[1] Ruosong Wang et al. “Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension”\n\n\n### Additional comments about the correctness of the proof of Lemma 8\n\nI have recently checked their proof of Lemma 8 and noticed one thing that looks a bit strange to me. Since the discussion is over, I hope the authors will clarify/fix it in their final paper. That is, in the proof of Lemma 8 in the step where they applied Lemma 7 (Azuma's),  they used $c_{\\tau'} = |q(u_{\\tau'}, \\phi')|$, but the Azuma's inequality requires that $c_{\\tau'}$ is a constant while here $|q(u_{\\tau'}, \\phi')|$ is a random variable (depending on the random variable $u_{\\tau'}$). How is this possible to apply Azuma's inequality here when $c_{\\tau'} = |q(u_{\\tau'}, \\phi')|$ is random? ", "extra_scores": {}, "extra_text": {}}, {"review_id": "0CNPIETK54n", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary After Discussion Period:\n-----------------------------------------------\nAfter corresponding to the authors and reading other reviews, my assessment hasn't changed much, which is that the paper is a good line of research but still needs improvement readability and strictness of assumptions.\n\nThe authors and reviewers all point out that this work is a relaxation over some previous works, e.g. Jin et al. Yet [1] has assumptions which are relaxed further than in this paper, and show that at regret bounds are possible with weaker assumptions. \n\nThe author's correctly point out their algorithm is computational efficiency while [1]'s algorithm isn't, which is a point in favor of the author's algorithm. Unfortunately, the benefits in computational efficiency were not clear to me and none of the other reviewers highlighted computational efficiency as one of the algorithm's strengths. If indeed one of the author's algorithm's main advantage over other work wasn't clear to the reviewers, then the paper still has room for improvement in readability.\n\nSummary: \n--------\nIn this paper, the authors propose a Q-learning method to solve episodic RL problems. Key to their method is assuming the Q-function takes the form of a generalized linear function plus an optimism term. Once this assumption has been made, they demonstrate that their algorithm, The LSVI-UCB algorithm provably finds a policy with bounded regret.\n\nPros:\n-----\nI like that the authors were able to show that using generalized linear functions for the Q function opens the doors to many theoretical analysis possibilities, and I like the modification they made to allow the Q-function to be optimistic. I thought a further strong point of the paper was the proof which shows that using general linearized q functions isn't a stricter assumption than the linear MDP assumption.\n\nAnd in general, I like the idea. I think it's a good line of research, and an idea which will yield important progress in the field of RL research.\n\nCons:\n-----\nI found this paper hard to follow. After multiple readings, I was still confused in multiple areas. This included \n\n  - What is the motivation of the function set $G_\\text{op}$?\n  - What are some examples of common RL problems for which the Q-function is / is not a generalized linear function\n  - Where does the matrix $A$ come from in $G_\\text{op}$?\n  - What is the motivation for the $\\Lambda_{h,t}$ in the algorithm\n  - Links to previous work, for example using the generalized linear models as a Q function, it's unclear if this is a new idea or is already present in previous work.\n  - It would be good to point out links not just in the related work section, but also while introducing concepts.\n\nTo discover why the author's algorithm is optimistic, we need to look at the details of the LSVI-UCB algorithm, a clear explanation isn't given anywhere else.\n\n\nThe other issue I had was with assumption 2. It is a fairly strong assumption, and although the author's show it holds for the linear MDP setting, it isn't nicely motivated why this assumption is realistic for other settings.\n\nIn any modeling setting, there's always a bias-variance tradeoff. As the model becomes more complex, it better captures the observations but is more prone to fitting the noise. By assuming the model can perfectly fits the true Q-function, the author's have assumed there's no \"bias\" in this bias variance tradeoff, and it is not surprising that they can then report lower regret as compared to other methods.\n\nI feel a better analysis should be more along the lines of [1], where they introduce the \"inherent bellman error,\" an error stating how far the true Q function is from the best estimate. One sees that this inherent bellman error then factors prominently in the regret bounds they show. There, they recognize that such a bellman error is generally non-zero, and prove their results by splitting the regret into an approximation and a variance term (like the bias variance trade-off).\n\n\nMinor concern:\n---------------------\nIn theorem 1, you state the regret is $O(H\\sqrt{d^3T})$ while in the abstract it's $O(\\sqrt{d^3T})$.\nPlease keeps it consistent.\n\nIn the bibliography, many of the works have been published. It's nice to cite the published version (i.e. the ICML or NeurIPS version) instead of the Arxiv version.\n\nConclusion:\n----------------\nIf the authors could better address assumption 2 (ideally by doing an analysis akin to [1]), this\nwould make the theory a good contribution to RL research. And if the authors could write their paper to tell a compelling story, where the different facts, assumptions, definitions and theorems nicely flow into one another, and one understands where things are coming from and where they are going, then this would be a good submission. But in it's current form, with an assumption which masks a large source of regret and a story which is hard to follow, I don't believe this paper is ready for submission.\n\n[1] Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near\noptimal policies with low inherent bellman error. arXiv preprint arXiv:2003.00153, 2020a\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper analyzes a version of optimistic value iteration with generalized linear function approximation.  Under an optimistic closure assumption,  the algorithm is shown to enjoy sublinear regret.  The paper also studies error propagation through backups that do not require closed-form characterization of dynamics and reward functions.

Overall, this is a solid contribution and the consensus is to accept.
Decision: Accept (Poster)