GENERALIZED LINEAR FUNCTION APPROXIMATION
Year: 2021

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 Õ ( H √ d3T ) whereH 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.

text: ( H √ d3T ) whereH 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.

heading: 1 INTRODUCTION
text: 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-RL, 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, 2002; Strehl et al., 2006), but as these methods scale with the number of states, they do not address problems with infinite or 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 approximation is required, but these algorithms are relatively impractical (Krishnamurthy et al., 2016; Jiang et al., 2017). In particular, these methods are computationally inefficient or rely crucially on strong dynamics assumptions (Du et al., 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 a generalized linear model. The algorithm is appealingly simple: collect a trajectory by following the greedy policy corresponding to the current model, perform a dynamic programming back-up to 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 is optimistic in the sense that it 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 shorthorizon (e.g,. bandit) problems, as well as in tabular reinforcement learning (Azar et al., 2017; Dann et al., 2017; Jin et al., 2018). With linear function approximation, Yang & Wang (2019) and Jin et al. (2019) show that the optimism principle can also yield provably sample-efficient algorithms, when the environment dynamics satisfy certain linearity properties. Their assumptions are always satisfied in tabular problems, but are somewhat unnatural in settings where function approximation
is required. Moreover as these assumptions are directly on the dynamics, it is unclear how their analysis can accommodate other forms of function approximation, including generalized linear models.
In the present paper, we replace explicit dynamics assumptions with expressivity assumptions on 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.1 More importantly, the relaxed 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 Section 2 we formalize our setting, introduce the optimistic closure assumption, and discuss related assumptions in the literature. In Section 3 we study optimistic 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 Section A. We close with some final remarks and future directions in Section 5.

heading: 2 PRELIMINARIES
text: 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 µ ∈ ∆(S), transition operator P : S × A → ∆(S), reward function R : S × A → ∆([0, 1]) and horizon H . The agent interacts with the MDP in episodes and, in each episode, a trajectory (s1, a1, r1, s2, a2, r2, . . . , sH , aH , rH) is generated where s1 ∼ µ, for h > 1 we have sh ∼ P (· | sh−1, ah−1), rh ∼ R(sh, ah), and actions a1:H are chosen by the agent. For normalization, we assume that ∑H h=1 rh ∈ [0, 1] almost surely.
A (deterministic, nonstationary) policy π = (π1, · · · , πH) consists of H mappings πh : S → A, where πh(sh) denotes the action to be taken at time point h if at state sh ∈ S The value function for a policy π is a collection of functions (V π1 , . . . , V π H) where V π h : S → R is the expected future reward the policy collects if it starts in a particular state at time point h. Formally,
V πh (s) , E
[ H∑
h′=h
rh′ | sh = s, ah:H ∼ π ] .
The value for a policy π is simply V π , Es1∼µ [V π1 (s1)], and the optimal value is V ? , maxπ V π , where the maximization is over all nonstationary policies. The typical goal is to find an approximately optimal policy, and in this paper, we measure performance by the regret accumulated over T episodes,
Reg(T ) , TV ? − E [ T∑ t=1 H∑ h=1 rh,t ] .
Here rh,t is the reward collected by the agent at time point h in the tth episode. We seek algorithms with regret that is sublinear in T , which demonstrates the agent’s ability to act near-optimally over the long run.

heading: 2.1 Q-VALUES AND FUNCTION APPROXIMATION
text: For any policy π, the state-action value function, or the Q-function is a sequence of mappings Qπ = (Qπ1 , . . . , Q π H) where Q π h : S ×A → R is defined as
Qπh(s, a) , E
[ H∑
h′=h
rh′ | sh = s, ah = a, ah+1:H ∼ π ] .
The optimal Q-function is Q?h , Q π? h where π ? , argmaxπ V π is the optimal policy.
In the value-based function approximation setting, we use a function class G to model Q?. In this paper, we always take G to be a class of generalized linear models (GLMs), defined as follows: Let d ∈ N be a dimensionality parameter and let Bd , { x ∈ Rd : ‖x‖2 ≤ 1 } be the `2 ball in Rd.
1This is also mentioned as a remark in Jin et al. (2019).
Definition 1. For a known feature map φ : S × A → Bd and a known link function f : [−1, 1] 7→ [−1, 1] the class of generalized linear models is G , {(s, a) 7→ f(〈φ(s, a), θ〉) : θ ∈ Bd}.
As is standard in the literature (Filippi et al., 2010; Li et 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 < κ < K <∞ and M <∞ such that κ ≤ |f ′(z)| ≤ K and |f ′′(z)| ≤M for all |z| ≤ 1.
For intuition, two example link functions are the identity map f(z) = z and the logistic map f(z) = 1/(1 + e−z) with bounded z. It is easy to verify that both of these maps satisfy Assumption 1.

heading: 2.2 EXPRESSIVITY ASSUMPTIONS: REALIZABILITY AND OPTIMISTIC CLOSURE
text: To obtain sample complexity guarantees that scale polynomially with problem parameters in the function approximation setting, it is necessary to posit expressivity assumptions on 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 at least well-approximated by G. Realizability alone suffices for provably efficient algorithms in the “contextual bandits” setting where H = 1 (Li et al., 2017; Filippi et al., 2010; Abbasi-Yadkori et al., 2011), but it does not seem to be sufficient whenH > 1. Indeed in these settings it is common to make stronger expressivity assumptions (Chen & Jiang, 2019; Yang & Wang, 2019; Jin et al., 2019).
Following these works, our main assumption is a closure property of the Bellman update operator Th. This operator has type Th : (S ×A → R)→ (S ×A → R) and is defined for all s ∈ S, a ∈ A as
Th(Q)(s, a) , E [rh + VQ(sh+1) | sh = s, ah = a] , VQ(s) , max
a∈A Q(s, a).
The Bellman update operator for time point H is simply TH(Q)(s, a) , E [rH | sH = s, aH = a], which is degenerate. To state the assumption, we must first define the enlarged function class Gup. For a d × d matrix A, A 0 denotes that A is positive semi-definite. For a positive semi-definite matrix A, ‖A‖op is the matrix operator norm, which is just the largest eigenvalue, and ‖x‖A ,√ x>Ax is the matrix Mahalanobis seminorm. For a fixed constant Γ ∈ R+ that we will set to be polynomial in d and log(T ), define
Gup , { (s, a) 7→ 1 ∧ f(〈φ(s, a), θ〉) + γ ‖φ(s, a)‖A : θ ∈ Bd, A 0, ‖A‖op ≤ 1 } ,
Here we use a∧b , min{a, b}. The class Gup contains G in addition to 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 2 (Optimistic closure). For any 1 ≤ h < H and g ∈ Gup, we have Th(g) ∈ G.
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 a 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, we will prove in Section 3 that optimistic closure is actually strictly weaker than previous assumptions used in our RL setting where exploration is required. Before turning to these discussions, we mention two basic properties of optimistic closure. Fact 1 (Optimistic closure and realizability). Optimistic closure implies that Q? ∈ G (realizability).
Proof. We will solve for Q? via dynamic programming, starting from time point H . In this case, the Bellman update operator is degenerate, and we start by observing that TH(g) ≡ Q?H for all g. Consequently we have Q?H ∈ G. Next, inductively we assume that we have Q?h+1 ∈ G, which implies that Q?h+1 ∈ Gup as we may take the same parameter θ and set A ≡ 0. Then, by the standard Bellman fixed-point characterization, we know that Q?h = Th(Q?h+1), at which point Assumption 2 yields that Q?h ∈ G.
Fact 2 (Optimistic closure in tabular settings). If S is finite and φ(s, a) = es,a is the standard-basis feature map, then under Assumption 1 we have optimistic closure.
Proof. We simply verify that G contains all mappings from (s, a) 7→ [0, 1], 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) 7→ [0, 1] can be written as a vector v ∈ [0, 1]|S|×|A|. For such a vector v, if we define θs,a , f−1(vs,a) we have that f(〈es,a, θ〉) = vs,a. Hence G contains all functions, so we trivially have optimistic closure.

heading: 2.3 RELATED WORK
text: 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 number 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 indeed our algorithm can be viewed as a generalization of the canonical tabular algorithm (Azar et al., 2017; Dann et al., 2017; Simchowitz & Jamieson, 2019) to the function approximation setting.2
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, 2003; Farahmand et al., 2010) and the “batch RL” setting where the agent does not control the data-collection process (Munos & Szepesvá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) ∈ G for all g ∈ 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 et 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 our own.
Most closely related to our work are the recent results of Yang & Wang (2019) and Jin et al. (2019). 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. (2019) hint at optimistic closure as a 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 to theirs. However we emphasize 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 importantly, 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 a 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., 2020) study an incomparable class of dynamics models that permit linear function approximation. Others study weakenings of the Linear MDP assumptions. In particular, 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
2The description of the algorithm looks quite different from that of Azar et al. (2017), but via an equivalence between model-free methods with experience replay and model-based methods (Fujimoto et al., 2018), they are indeed quite similar.
weaker than our optimistic closure assumption. However, their algorithm is not computationally efficient. Computational efficiency is addressed in Zanette et al. (2020b) in the reward-free setting with reachability assumptions. As we do not require reachability assumptions, this latter result is incomparable to ours. None of these results considers generalized linear models.

heading: 3 ON OPTIMISTIC CLOSURE
text: For a 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 ψ : S×A → Rd, unknown signed measures µ : S → Rd, and an unknown vector η ∈ Rd such that (1) P (s′|s, a) = 〈ψ(s, a), µ(s′)〉 holds for all states s, s′ and actions a, and (2) E[r | s, a] = 〈ψ(s, a), η〉.
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 a linear MDP. Proposition 1. If an MDP is linear then Assumption 2 holds with G = {(s, a) 7→ 〈w,ψ(s, a)〉 : w ∈ Bd} .
Proof. The result is implicit in Jin et al. (2019), and we include the proof for completeness. For any function g, observe that owing to the linear MDP property
Th(g)(s, a) = E [ r + max
a′ g(s′, a′) | s, a
] = 〈ψ(s, a), η〉+ ∫ 〈ψ(s, a), µ(s′)〉max
a′ g(s′, a′)ds′,
which is clearly a linear function in ψ(s, a). Hence for any function g, which trivially includes the optimistic functions, we have Th(g) ∈ G.
Thus the linear MDP assumption is stronger than Assumption 2. Next, we show that it is strictly stronger. Proposition 2. There exists an MDP with H = 2, d = 2, |A| = 2 and |S| =∞ such that Assumption 2 is satisfied, but the MDP is not a linear MDP.
Thus we have that optimistic closure is strictly weaker than the linear MDP assumption from Jin et al. (2019). Thus, our results strictly generalize theirs.
Proof. Fix the link function to be f(z) = z. We first construct the MDP. Set the action space A = {a1, a2}. We use ei to denote the ith standard basis element, and let x = (0.1/Γ, 0.1/Γ) be a fixed vector where Γ appears in the construction of Gup. Recall that s1 is the first state in each trajectory. In our example, for all a ∈ A, φ(s1, a) is sampled uniformly at random from the set {αe1 + (1− α)e2 : α ∈ [0, 1]}. The transition rule is deterministic and given by:
∀a ∈ A : φ(s2, a) = αx if φ(s1, a) = αe1 + (1− α)e2. Moreover, for the reward function, R(s1, a) = 0 and R(s2, a) = 0.1α/Γ.
We first show that the Linear MDP property does not hold for the constructed MDP and the given feature map φ. Let s(1)1 be the state with φ(s (1) 1 , a) = e2 and s (2) 1 be the state with φ(s (2) 1 , a) = e1. Notice that we deterministically transition from s(1)1 to a state s (1) 2 with φ(s (1) 2 , a) = 0, and we deterministically transition from s(2)1 to a state s (2) 2 with φ(s (2) 2 , a) = x, which already fixes the whole transition operator under the linear MDP assumption. Thus, under the linear MDP assumption, we must therefore have a randomized transition for any state s1 with φ(s1, a) = αe1 + (1 − α)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 2 holds. Consider an arbitrary optimistic Q estimate of the form g(z) = min{1, z>θ + γ √ z>Az} ∈ Gup. Notice that for x = (0.1/Γ, 0.1/Γ), we always have that
Algorithm 1 The LSVI-UCB algorithm with generalized linear function approximation. 1: Initialize estimates Q̄h,0 ≡ 1 for all h ≤ H and Q̄H+1,t ≡ 0 for all 1 ≤ t ≤ T ; 2: Set γ = CKκ−1 √ 1 +M +K + d2 ln((1 +K + Γ)TH) for a universal constant C;
3: for t = 1, 2, · · · , T do 4: Commit to policy π̂h,t(s) , argmaxa∈A Q̄h,t−1(s, a); 5: Use policy π̂·,t to collect one trajectory {(sh,t, ah,t, rh,t)}Hh=1; 6: for h = H,H − 1, · · · , 1 do 7: Compute xh,τ , φ(sh,τ , ah,τ ) and yh,τ , rh,τ + maxa′∈A Q̄h+1,t(sh+1,τ , a′) for all τ ≤ t; 8: Compute ridge estimate
θ̂h,t , argmin ‖θ‖2≤1 ∑ τ≤t (yh,τ − f(〈xh,τ , θ〉))2; (1)
9: Compute Λh,t , ∑ τ≤t xh,τx > h,τ + I;
10: Construct Q̄h,t(s, a) , min { 1, f(φ(s, a)>θ̂h,t) + γ ‖φ(s, a)‖Λ−1h,t }
; 11: end for 12: end for
x>θ + γ √ x>Ax ≤ 1 for any θ ∈ Bd and A with ‖A‖op ≤ 1. Moreover, for all s2, i.e., the second state in the trajectory, we always have φ(s2, a) = αx for some α ∈ [0, 1]. Hence we can ignore the first term in the minimum, and, by direct calculation, we have that when φ(s, a) = αe1 + (1−α)e2:
T1(g)(s, a) = αx>θ + γ √ α2x>Ax
= α(x>θ + γ √ x>Ax) = αc0.
Hence we can write T1(g) = 〈φ(s, a), (c0, 0)〉, which verifies Assumption 2.

heading: 4 ALGORITHM AND MAIN RESULT
text: We now turn to presenting our algorithm and main results. We study a least-squares dynamic programming style algorithm that we call LSVI-UCB, with pseudocode presented in Algorithm 1. 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, it should be considered as a generalization.
The algorithm uses dynamic programming to maintain optimistic Q function estimates {Q̄h,t}h≤H,t≤T for each time point h and each episode t. In the tth episode, we use the previously computed estimates to define the greedy policy π̂h,t(·) , argmaxa∈A Q̄h,t−1(·, a), which we use to take actions for the episode. Then, with all of the trajectories collected so far, we perform a dynamic programming update, where the main per-step optimization problem is (1). Starting from time point H , we update our Q function estimates by solving constrained least squares problems using our class of GLMs. At time point H , the covariates are {φ(sH,τ , aH,τ )}τ≤t, and the regression targets are simply the immediate rewards {rH,τ}τ≤t. For time points h < H , the covariates are defined similarly as {φ(sh,τ , ah,τ )}τ≤t but the regression targets are defined by inflating the learned Q function for time point h+ 1 by an optimism bonus.
In detail, the least squares problem for time point h + 1 yields a parameter θ̂h+1,t and we also form the second moment matrix Λh+1,t of all the covariates at time h + 1 that we have seen so far. Using these, we define the optimistic Q function Q̄h+1,t(s, a) ,
min { 1, f(〈φ(s, a), θ̂h+1,t〉) + γ ‖φ(s, a)‖Λ−1h+1,t }
. In our analysis, we verify that Q̄h+1,t is optimistic 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,τ + maxa′∈A Q̄h+1,t(sh+1,τ , a′), which is a natural stochastic approximation to the Bellman backup of Q̄h+1,t. Applying this update backward from
time point H to 1, we obtain the Q-function estimates that we use to define the policy for the next episode.
The main conceptual difference between Algorithm 1 and the algorithm of Jin et al. (2019) is that we allow non-linear function approximation with GLMs, while they consider only linear models. On a more technical level, we use constrained least squares for our dynamic programming backup which we find easier to analyze, while they use the ridge regularized version.
On the computational side, the algorithm is straightforward to implement, and, depending on the link function f , it can be easily shown to run in polynomial time. For example, if f is the identity map, then (1) is equivalent to standard least square ridge regression, which can be solved in closed form. Moreover, we can use the Sherman-Morrison formula to amortize matrix inversions, and, by doing so, we obtain a running time of O ( d2|A|HT 2 ) . 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 a non-trivial link function f , even though (1) may be non-convex.

heading: 4.1 MAIN RESULT
text: Our main result is a regret bound for LSVI-UCB when the link function satisfies Assumption 1 and the function class satisfies Assumption 2.
Theorem 1. For any episodic MDP, with Assumption 1 and Assumption 2, and for any T , the cumulative regret of Algorithm 1 is3
O ( HKκ−1 √ (M +K + d2 ln(KTH)) · Td ln(T/d) ) = Õ ( H √ d3T ) ,
with probability 1− 1/(TH).
The result states that LSVI-UCB enjoys √ T -regret 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 1 is one of the most general results we are aware of for provably efficient exploration with function approximation.
Nevertheless, to develop further intuition for our bound, it is worth comparing to prior results. First, in the linear MDP setting of Jin et al. (2019), we use the identity link function so thatK = κ = 1 and M = 1, and we also are guaranteed to satisfy Assumption 2. In this case, our bound differs from that of Jin et al. (2019) 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 as a strict generalization.
To capture the tabular setting, we use the standard basis featurization as in Fact 2 and the identity link function, which gives d = |S||A|, K = κ = 1, and M = 1. Thus, we obtain the following corollary:
Corollary 2. For MDPs with finite state and action spaces, using feature map φ(s, a) , es,a ∈ R|S|×|A|, for any T , the cumulative regret of Algorithm 1 is Õ ( H √ |S|3|A|3T ) , with probability
1− 1/(TH).
Note that this bound is polynomially worse than the near-optimal Õ(H √ SAT + H2S2A log(T )) bound of Azar et al. (2017). However, a refined analysis specialized to the tabular setting can be shown to obtain a better regret bound of Õ ( H √ |S|2|A|2T ) . Of course, our algorithm and
analysis address problems with infinitely large state spaces and other settings that are significantly more complex than tabular MDPs, which we believe is more important than recovering the optimal guarantee for tabular MDPs.
3We use Õ (·) to suppress factors of M,K, κ,Γ and any logarithmic dependencies on the arguments.

heading: 5 DISCUSSION
text: This paper presents a provably efficient reinforcement learning algorithm that approximates the Q? function with a generalized linear model. We prove that the algorithm obtains Õ(H √ d3T ) regret under mild regularity conditions and a 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 algorithms for reinforcement learning with generalized linear function approximation, without explicit dynamics assumptions.
We close with some open problems. First, using the fact that Corollary 3 applies beyond GLMs, can we develop algorithms that can employ general function classes? While such algorithms do 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 is to investigate weaker assumptions that enable provably efficient reinforcement learning with function approximation. We look forward to studying these questions in future work.

heading: A PROOF OF THEOREM 1
text: We now provide the proof of Theorem 1, deferring some technical details to later sections in this appendix. The proof has three main components: a regret decomposition for optimistic Q learning, a deviation analysis for least squares with GLMs to ensure optimism, and a potential argument to obtain the final regret bound.
Regret decomposition. The first step of the proof is a regret decomposition that applies generically to optimistic algorithms.4 The lemma demonstrates concisely the value of optimism in reinforcement 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 t and let {Q̄h,t−1}h≤H denote the current estimated Q functions. The precondition is that Q̄h,t−1 is optimistic and has controlled overestimation. Precisely, we assume that there exists a function cnfh,t−1 : S ×A → R+ such that
Q?h(s, a) ≤ Q̄h,t−1(s, a) (2) Q̄h,t−1(s, a) ≤ Th(Q̄h+1,t−1)(s, a) + cnfh,t−1(s, a) (3)
We will verify that our estimates Q̄h,· satisfy these properties subsequently. Before doing so, we state the regret decomposition lemma and an immediate corollary. Lemma 1. Fix episode t and let Ft−1 be the filtration of {(sh,τ , ah,τ , rh,τ )}τ<t. Assume that Q̄h,t−1 satisfies (3) for some function cnfh,t−1. Then, if πt = argmaxa∈A Q̄h,t−1(·, a) is deployed we have
V ? − E [ H∑ h=1 rh,t | Ft−1 ] ≤ ζt + H∑ h=1 cnfh,t−1(sh,t, ah,t),
where E [ζt | Ft−1] = 0 and |ζt| ≤ 2H almost surely. Corollary 3. Assume that for all t, Q̄h,t−1 satisfies (3) and that πt is the greedy policy with respect to Q̄h,t−1. Then with probability at least 1− δ, we have
Reg(T ) ≤ T∑ t=1 H∑ h=1 cnfh,t−1(sh,t, ah,t) + O(H √ T log(1/δ)).
Proof of Lemma 1. Observe that V ? = E [Q?(s1, π?(s1))] ≤ E [ Q̄1,t−1(s1, π ?(s1)) ]
≤ E [ Q̄1,t−1(s1, πt(s1)) ] ≤ E [cnf1,t−1(s1, πt(s1))] + E [ T1(Q̄2,t−1)(s1, πt(s1))
] = E [cnf1,t−1(s1, πt(s1))] + E [r1 | s1, a1 = πt(s1)] + Es2∼πt [ Q̄2,t−1(s2, πt(s2))
] 4Related results appear elsewhere in the literature focusing on the tabular setting, see e.g., Simchowitz &
Jamieson (2019).
Throughout this calculation, s1 ∼ µ. The first step here is by definition, the second uses the optimism property for Q̄1,t−1. The third uses that πt is the greedy policy with respect to Q̄1,t−1 while the fourth uses the upper bound on Q̄1,t−1. Finally we use the definition of the Bellman operator and the fact that πt is the greedy policy yet again. Comparing this upper bound with the expected reward collected by πt we observe that r1 cancels, and we get
V ?−E [ H∑ h=1 rh,t | Ft−1 ] ≤ Eπt [cnf1,t−1(s1, πt(s1))] + Eπt [ Q̄2,t−1(s2, πt(s2))− H∑ h=2 rh,t | Ft−1 ] .
At this point, notice that Q̄2,t−1(s2, πt(s2)) is precisely what we alreacy upper bounded at time point h = 1 and we are always considering the state-action distribution induced by πt. Hence, repeating the argument for all h, we obtain
V ?−E [ H∑ h=1 rh,t | Ft−1 ] ≤ H∑ h=1 Eπt [cnfh,t−1(sh, ah)] = H∑ h=1 cnfh,t−1(sh,t, ah,t) + ζt,
where ζt , ∑H h=1 ζh,t and
ζh,t , Eπt [cnfh,t−1(sh, πt(sh))]− cnfh,t−1(sh,t, ah,t),
which is easily seen to have the required properties.
The lemma states that if Q̄h,t−1 is optimistic and we deploy the greedy policy πt, then the perepisode regret is controlled by the overestimation error of Q̄h,t−1, up to a stochastic term that enjoys favorable concentration properties. Crucially, the errors are accumulated on the observed trajectory, or, stated another way, the cnfh,t−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 cnf function will decrease on these arguments. This can yield one of two 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-exploitation tradeoff in the multi-step RL setting, analogously to the bandit setting.
Note that Lemma 1 does not assume any form for Q̄h,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 Assumption 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 to design the cnf function and ensure that (3) holds, with high probability. This is the contents of the next lemma. Lemma 2. Under Assumption 1 and Assumption 2, with probability 1 − 1/(TH), we have that ∀t, h, s, a: ∣∣∣f(〈φ(s, a), θ̂h,t〉)− Th(Q̄h+1,t)(s, a)∣∣∣ ≤ γ ‖φ(s, a)‖Λ−1h,t where γ,Λh,t are defined in Algorithm 1.
A simple induction argument then verifies that (3) holds, which we summarize in the next corollary. Corollary 4. Under Assumption 1 and Assumption 2, with probability 1−1/(TH), we have that (3) holds for all t, h with cnfh,t−1(s, a) = min{2, 2γ ‖φ(s, a)‖Λ−1h,t−1}.
As the proof of Lemma 2 is 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 to account for the dependency structure in the data sequence. The intuition is that, thanks to Assumption 2 and the fact that Q̄h+1,t ∈ Gup, we know that there exists a parameter θ̄h,t such that f(〈φ(s, a), θ̄h,t〉) = Th(Q̄h+1,t)(s, a). It is easy to verify that θ̄h,t is the Bayes optimal predictor for the square loss problem in (1), and so with a uniform convergence argument we can expect that θ̂h,t is close to θ̄h,t, which is our desired conclusion.
There are two subtleties with this argument. First, we want to show that θ̄h,t and θ̂h,t are close in a data-dependent sense, to obtain the dependence on the Λ−1h,t-Mahalanobis norm in the bound. This can be done using vector-valued self-normalized martingale inequalities (Peña et al., 2008), as in prior work on linear stochastic bandits (Abbasi-Yadkori et al., 2012; Filippi et al., 2010; AbbasiYadkori et al., 2011).
However, the process we are considering is not a martingale, since Q̄h+1,t, which determines the regression targets yh,τ , depends on all data collected so far. Hence yh,τ is not measurable with respect to the filtration Fτ , which prevents us from directly applying a self-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 regression targets yh,τ , but as the covering is deterministic, we do obtain martingale structure. Then, we show that the error term for the random Q̄h+1,t that we need to bound is close to a 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 a straightforward inductive argument. Assuming Q̄h+1,t dominates Q?, it is easy to show that Q̄h,t also dominates Q?, and the upper bound is immediate. Combining Corollary 4 with Corollary 3, all that remains is to upper bound the confidence sum.
Potential argument. To bound the confidence sum, we use a standard potential argument that appears in a number of works on stochastic linear bandits. We summarize the conclusion with the following lemma, which follows directly from Lemma 11 of Abbasi-Yadkori et al. (2012). Lemma 3. For any h ≤ H we have that
T∑ t=1 ‖φ(sh,t, ah,t)‖2Λ−1h,t−1 ≤ 2d ln(1 + T/d).
Wrapping up. Equipped with the above results, we are now prepared to prove Theorem 1.
Proof of Theorem 1. Assume that Corollary 4 holds for all 1 ≤ h ≤ H and 1 ≤ t ≤ T . Applying Lemma 1 and the definition of cnfh,t−1 implied by Corollary 4, the cumulative expected regret is at most
TV ? − E [ T∑ t=1 H∑ h=1 rh,t ]
≤ T∑ t=1 ζt + T∑ t=1 H∑ h=1 min { 2, γ ‖φ(sh,t, ah,t)‖Λ−1h,t−1 } ≤ T∑ t=1 ζt + H∑ h=1 √ Tγ2 · √√√√ T∑ t=1 ‖φ(sh,t, ah,t)‖2Λ−1h,t−1 ≤ T∑ t=1 ζt + H∑ h=1 √ Tγ2 · √ 2d ln(1 + T/d).
Here, the second step follows from the Cauchy-Schwarz inequality, and the last step is an application of Lemma 3. The first term forms a martingale, and we know that |ζt| ≤ 2H . Therefore, by Azuma’s inequality, we have that with probability at least 1− 1/TH
T∑ t=1 ζt ≤ √ 8TH2 ln(TH).
Finally, using the definition of γ, the final regret is upper bounded by Reg(T ) ≤ O ( H √ T ln(TH) +HKκ−1 × √ (M +K + d2 ln((K + Γ)TH)) · Td ln(1 + T/d) ) ≤ Õ ( H √ d3T ) ,
which proves the result.

heading: B PROOF OF LEMMA 2 AND COROLLARY 4
text: To facilitate our analysis we define the following important intermediate quantity: θ̄h,t ∈ Bd : f(〈φ(s, a), θ̄h,t〉) , E [ rh + max
a′∈A Q̄h+1,t(s
′, a′) | s, a ] .
In words, θ̄h,t is the Bayes optimal predictor for the squared loss problem at time point h in the tth episode. Since by inspection Q̄h+1,t ∈ Gup, by Assumption 2 we know that θ̄h,t exists for all h and t. Lemma 4. For any θ, θ′, x ∈ Rd satisfying ‖θ‖2, ‖θ′‖2, ‖x‖2 ≤ 1,
κ2 |〈x, θ′ − θ〉|2 ≤ |f(〈x, θ′〉)− f(〈x, θ〉)|2 ≤ K2 ‖θ′ − θ‖22 .
Proof. By the mean-value theorem, there exists θ̃ = θ + λ(θ′ − θ) for some λ ∈ (0, 1) such that f(〈x, θ′〉)− f(〈x, θ〉) = 〈 ∇θf(〈x, θ̃〉), θ′ − θ 〉 . On the other hand, by the chain rule and Assump-
tion 1, ∇θf(〈x, θ̃〉) = f ′(〈x, θ̃〉) · x. Hence,
|〈∇θf(x>θ̃), θ′ − θ〉|2 ≤ f ′(〈x, θ̃〉)2 · |〈x, θ′ − θ〉| 2 ≤ K2 ‖x‖22 ‖θ ′ − θ‖22 ≤ K 2 ‖θ′ − θ‖22 ; |〈∇θf(x>θ̃), θ′ − θ〉|2 ≥ κ2 |〈x, θ′ − θ〉| 2 ,
which are to be demonstrated.
Lemma 5. For any 0 < ε ≤ 1, there exists a finite subset Vε ⊂ Gup with ln |Vε| ≤ 6d2 ln(2(1 + K + Γ)/ε), such that
sup g∈Gup min v∈Vε sup s,a |g(φ(s, a))− v(φ(s, a))| ≤ ε. (4)
Proof. Recall that for every g ∈ Gup, there exists θ ∈ Bd, 0 ≤ γ ≤ Γ and ‖A‖op ≤ 1 such that g(x) = min{1, f(〈x, θ〉) + γ ‖x‖A}. Let Θε ⊆ Bd, Γε ⊆ [0,Γ] andMε ⊆ {M ∈ S + d : ‖M‖op ≤ 1} be finite subsets such that for any θ, γ, A, there exist θ′ ∈ Θε, γ′ ∈ Γε, A′ ∈Mε such that
max { ‖θ − θ′‖2 , |γ − γ ′| , ‖A−A′‖op } ≤ ε′,
where ε′ ∈ (0, 1) will be specified later in the proof. For the function g ∈ Gup corresponding to the parameters θ, γ, A the function g′ corresponding to parameters θ′, γ′, A′ satisfies
sup s,a |g(φ(s, a))− g′(φ(s, a))| ≤ sup x∈Bd |g(x)− g′(x)|
≤ sup x∈Bd |f(〈x, θ〉)− f(〈x, θ′〉) + γ ‖x‖A − γ ′ ‖x‖A′ | ≤ K ‖θ − θ′‖2 + |γ − γ ′|+ Γ |‖x‖A − ‖x‖A′ |
≤ K ‖θ − θ′‖2 + |γ − γ ′|+ Γ
√ |x>(A−A′)x|
≤ Kε′ + ε′ + Γ √ ε′ ≤ (1 +K + Γ) √ ′.
In the last step we use ε′ ≤ 1. Therefore, if we define the class Vε , {(s, a) 7→ min{1, f(〈φ(s, a), θ′〉) + γ′ ‖φ(s, a)‖A′ : θ′ ∈ Θε, γ ∈ Γε, A ∈ Mε}, we know that the covering property is satisfied with parameter (1 +K + Γ) √ ε′. Setting ε′ = ε2/(1 +K + Γ)2 we have the desired covering property.
Finally, we upper bound ln |Vε|. By definition, we have that ln |Vε| ≤ ln |Θε| + ln |Γε| + ln |Mε|. Furthermore, standard covering number bounds reveals that ln |Θε| ≤ d ln(2/ε′), ln |Γε| ≤ ln(1/ε′) and ln |Mε| ≤ d2 ln(2/ε′). Plugging in the definition of ε′ yields the result.
For the next lemma, let Ft−1 , σ({(sh,τ , ah,τ , rh,τ )}τ<t) be the filtration induced by all observed trajectories up to but not including time t. Observe that Q̄·,t−1 and our policy π̂h,t are Ft−1 measurable.
Lemma 6 (Restatement of Lemma 2). Fix any 1 ≤ t ≤ T and 1 ≤ h ≤ H . Then as long as πt is Ft−1 measurable, with probability 1− 1/(TH)2 it holds that∣∣∣f(〈φ(s, a), θ̂h,t〉)− f(〈φ(s, a), θ̄h,t〉)∣∣∣ ≤ min{2, γ ‖φ(s, a)‖Λ−1h,t} , ∀s, a. for γ ≥ CKκ−1 √ 1 +M +K + d2 ln((1 +K + Γ)TH) and 0 < C <∞ is a universal constant.
Note that this is precisely Lemma 2, as θ̄h,t is defined as f(〈φ(s, a), θ̄h,t) = Th(Q̄h+1,t)(s, a).
Proof. The upper bound of 2 is obvious, since both terms are upper bounded by 1 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 xτ , yτ for xh,τ and yh,τ . We also abbreviate θ̂ , θ̂h,t and θ̄ , θ̄h,t.
Since ∥∥θ̄∥∥
2 ≤ 1, the optimality of θ̂ for (1) implies that∑
τ≤t
( f(〈xτ , θ̂〉)− yτ )2 ≤ ∑ τ≤t ( f(〈xτ , θ̄〉)− yτ )2 .
Decomposing the squares and re-organizing the terms, we have that
∑ τ≤t ( f(〈xτ , θ̂〉)− f(〈xτ , θ̄〉) )2 ≤ 2 ∣∣∣∣∣∣ ∑ τ≤t ξτ (f(〈xτ , θ̂〉)− f(〈xτ , θ̄〉)) ∣∣∣∣∣∣ , (5) where ξτ , yτ − f(〈xτ , θ̄〉). By the fundamental theorem of calculus, we have
f(〈xτ , θ̂〉)− f(〈xτ , θ̄〉) = ∫ 〈xτ ,θ̂〉 〈xτ ,θ̄〉 f ′(s)ds = 〈xτ , θ̂ − θ̄〉 ∫ 1 0
f ′(〈xτ , sθ̂ + (1− s)θ̄〉)ds︸ ︷︷ ︸ ,Dτ .
Using this identity on both sides of (5), we have that
∑ τ≤t D2τ ( 〈xτ , θ̂ − θ̄〉 )2 ≤ 2 ∣∣∣∣∣∣ ∑ τ≤t ξτDτ 〈xτ , θ̂ − θ̄〉 ∣∣∣∣∣∣ . (6) Note also that, by Assumption 1, Dτ satisfies κ2 ≤ D2τ ≤ K2 almost surely for all τ . The difficulty in controlling (6) is that θ̄ itself is a random variable that depends on {(xτ , yτ )}τ≤t. In particular, we want that E[ξτ | Dτ 〈xτ , φ〉 ,Fτ−1] = 0 for any fixed φ, but this is not immediate as θ̄ depends on xτ . To proceed, we eliminate this dependence with a uniform convergence argument. Let ε ∈ (0, 1) be a covering accuracy parameter to be determined later in this proof. Let Vε be the pointwise covering for Gup that is implied by Lemma 5. Let gε ∈ Vε be the approximation for Q̄h+1,t that satisfies (4). By Assumption 2, there exists some θ] ∈ Bd such that
∀s, a : f(〈φ(s, a), θ]〉) = E [ r + max
a′∈A gε(s
′, a′) | s, a ] .
Now, define y]τ and ξ ] τ as
y]τ , rh,τ + max a′∈A gε(sh+1,τ , a ′), ξ]τ , y ] τ − f(〈xh,τ , θ]〉).
The right-hand side of (6) can then be upper bounded as
2 ∣∣∣∣∣∣ ∑ τ≤t ξτDτ 〈xτ , θ̂ − θ̄〉 ∣∣∣∣∣∣ ≤ 2 ∣∣∣∣∣∣ ∑ τ≤t ξ]τDτ 〈xτ , θ̂ − θ̄〉 ∣∣∣∣∣∣+ ∆, (7) where |∆| ≤ Kt×maxτ≤t |ξ]τ − ξτ | almost surely.
Upper bounding ∆ in (7). Fix τ ≤ t. By definition, we have that∣∣ξ]τ − ξτ ∣∣ ≤ ∣∣y]τ − yτ ∣∣+ ∣∣f(〈xτ , θ̄〉)− f(〈xτ , θ]〉)∣∣ ≤ max
a∈A ∣∣gε(sh+1,τ , a)− Q̄h+1,t(sh+1,τ , a)∣∣+K ∥∥θ̄ − θ]∥∥2 (8) ≤ +K ≤ (K + 1) , (9)
where (8) holds by Lemma 4 and (9) follows from Lemma 5. In particular, the bound on ∥∥θ̄ − θ]∥∥
2
can be verified by expanding the definitions and noting that gε is pointwise close to Q̄h+1,t. Therefore, we have
|∆| ≤ (K + 1)2t . (10)
Upper bounding (7). Note that Dτ is a function of xτ , θ̂, and θ̄. For clarity, we define Dτ (θ, θ ′) := ∫ 1 0 f ′(〈xτ , sθ + (1 − s)θ′)〉)ds. As |f ′′(z)| ≤ M for all |z| ≤ 1 and ‖xτ‖2 ≤ 1, we have that for every θ, θ′, θ̃, θ̃′ ∈ Bd∣∣∣Dτ (θ, θ′)−Dτ (θ̃, θ̃′)∣∣∣ ≤ ∫ 1 0
∣∣∣f ′(〈xτ , sθ + (1− s)θ′〉)− f ′(〈xτ , sθ̃ + (1− s)θ̃′〉)∣∣∣ds ≤M(‖θ − θ̃‖2 + ‖θ′ − θ̃′‖2).
Hence, for any (θ, θ′) and (θ̃, θ̃′) pairs, we have for every τ that∣∣∣ξ]τ 〈xτ , Dτ (θ, θ′)(θ − θ′)−Dτ (θ̃, θ̃′)(θ̃ − θ̃′)〉∣∣∣ ≤ ∣∣Dτ (θ, θ′)−Dτ (θ̃, θ̃′)∣∣× ‖θ − θ′‖2 + ∣∣Dτ (θ̃, θ̃′)∣∣× (‖θ − θ̃‖2 + ‖θ′ − θ̃′‖2)
≤M(‖θ − θ̃‖2 + ‖θ′ − θ̃′‖2)× 2 +K(‖θ − θ̃‖2 + ‖θ′ − θ̃′‖2) ≤ (2M +K)(‖θ − θ̃‖2 + ‖θ′ − θ̃′‖2).
Here we are using that |ξτ | ≤ 1. We are now in a position to invoke Lemma 8. Consider a fixed function gε, which defines a fixed θ]. We will bound
∣∣∣∑τ≤t ξ]τ 〈xτ , Dτ (θ, θ′)(θ − θ′)〉∣∣∣ uniformly over all pairs (θ, θ′). With gε, θ] fixed and since πt is Ft−1 measurable, we have that {xτ , ξ]τ}τ≤t are random variables satisfying E[ξ]τ | x1:τ , ξ ] 1:τ−1] = 0. For φ = (θ, θ
′) we define the function q(xτ , φ) = 〈x,Dτ (φ)(θ − θ′)〉, which as we have just calculated satisfies |q(xτ , φ)− q(xτ , φ′)| ≤ (2M + K) ‖φ− φ′‖2. For δ′ ∈ (0, 1/2) with probability 1− δ′ we have ∀φ = (θ, θ′) ∈ B2d:∣∣∣∣∣∣ ∑ τ≤t ξ]τ 〈xτ , Dτ (φ)(θ − θ′)〉 ∣∣∣∣∣∣ ≤ (2M +K) + 2 ( 1 + √ V (φ) )√ 2d ln(4T ) + ln(1/δ′)
≤ 4 max { M +K + √ 2d ln(4T ) + ln(1/δ′), √ V (φ) √ 2d ln(4T ) + ln(1/δ′) } , (11)
where V (φ) , ∑ τ≤t〈xτ , Dτ (φ)(θ− θ′)〉2. The last inequality holds because a+ b ≤ 2 max{a, b}.
Next, take a union bound over all gε ∈ Vε so (11) holds for any gε and any subsequently induced choice of ξ]τ with probability at least 1 − |Vε|δ′. In particular, this union bound implies that (11) holds for the choice of gε that approximates Q̄h+1,t. Therefore, combining (6), (7), (10) with (11) for this choice of gε, we have that with probability at least 1− |Vε|δ′ ∑ τ≤t D2τ 〈xτ , θ̂ − θ̄〉2 ≤ 2∆ + 2 ∣∣∣∣∣∣ ∑ τ≤t ξ]τ 〈xτ , Dτ (θ̂ − θ̄)〉
∣∣∣∣∣∣ ≤ 2(K + 1)2tε+ 8 max { M +K + √ 2d ln(4T ) + ln(|Vε|/δ′), √ V (θ̂, θ̄) · √ 2d ln(4T ) + ln(|Vε|/δ′) } .
Observe that the left hand side is precisely V (θ̂, θ̄). Now, set ε = 1/(2(K + 1)2T ) and δ′ = 1/(|Vε|T 2H2) and use the bound on ln |Vε| from Lemma 5 to get√
2d ln(4T ) + ln(|Vε|/δ′) ≤ √ 2d ln(4T ) + 12d2 ln(2(1 +K + Γ)/ε) + 2 ln(TH)
≤ √ 4d ln(2TH) + 24d2 ln(2(1 +K + Γ)T ) ≤ √ 28d2 ln(2(1 +K + Γ)TH)
Therefore, we obtain V (θ̂, θ̄) ≤ 1 + 8 max { M +K + √ 28d2 ln(2(1 +K + Γ)TH), √ V (θ̂, θ̄) · √ 28d2 ln(2(1 +K + Γ)TH) } ≤ 16 max { 1 +M +K + √ 28d2 ln(2(1 +K + Γ)TH), √ V (θ̂, θ̄) · √ 28d2 ln(2(1 +K + Γ)TH) } .
Subsequently, V (θ̂, θ̄) = ∑ τ≤t D2τ 〈xτ , θ̂ − θ̄〉2
≤ 16 max { 1 +M +K + √ 28d2 ln(2(1 +K + Γ)TH), 448d2 ln(2(1 +K + Γ)TH) }
≤ C2V (1 +M +K + d2 ln((1 +K + Γ)TH)),
where 0 < CV <∞ is a universal constant. Next, note that D2τ ≥ κ2, thanks to Assumption 1. We then have√
(θ̂ − θ̄)>Λh,t(θ̂ − θ̄) ≤ κ−1 √ V (θ̂, θ̄) ≤ CV κ−1 √ 1 +M +K + d2 ln((1 +K + Γ)TH),
where Λh,t = ∑ τ<t xτ , x > τ . Finally, for any (s, a) pair, invoking Lemma 4 and the Cauchy-Schwarz inequality we have∣∣∣f(〈φ(s, a), θ̂〉)− f(〈φ(s, a), θ̄〉)∣∣∣ ≤ K ∣∣∣〈φ(s, a), θ̂ − θ̄〉∣∣∣ ≤ K √ (θ̂ − θ̄)>Λh,t(θ̂ − θ̄)× √ φ(s, a)>Λ−1h,tφ(s, a)
≤ CVKκ−1 √
1 +M +K + d2 ln((1 +K + Γ)TH)× ‖φ(s, a)‖Λ−1h,t which is to be demonstrated.
Corollary 5 (Restatement of Corollary 4). With probability 1 − 1/(TH), Q̄h,t(s, a) ≥ Q?h(s, a) holds for all h, t, s, a.
Proof. Fix 1 ≤ t ≤ T . We use induction on h to prove this corollary. For h = H+1, Q̄H+1,t(·, ·) ≥ Q?H+1(·, ·) clearly holds because Q̄H+1,t ≡ Q?H+1 ≡ 0. Now assume that Q̄h+1,t ≥ Q?h+1, and let us prove that this is also true for time step h.
Since Q̄h+1,t(s′, a′) ≥ Q?h+1(s′, a′) for all s′, a′, we have that f(〈φ(s, a), θ̄h,t〉) ≥ f(〈φ(s, a), θ?h〉) for all (s, a) pairs. Then, by the definition of Q̄h,t and Lemma 6, with probability 1 − 1/(TH)2 it holds uniformly for all (s, a) pairs that Q̄h,t(s, a) ≥ f(〈φ(s, a), θ̄h,t〉). Hence, with the same probability, we have Q̄h,t(s, a) ≥ Q?h(s, a) for all (s, a) pairs. A union bound over all t ≤ T and h ≤ H completes the proof.

heading: C TAIL INEQUALITIES
text: Lemma 7 (Azuma’s inequality). Suppose X0, X1, X2, · · · , XN form a martingale (i.e., E[Xk+1|X1, · · · , Xk] = Xk) and satisfy |Xk −Xk−1| ≤ ck almost surely. Then for any > 0,
Pr [∣∣Xn −X0∣∣ ≥ ] ≤ 2 exp{− 2
2 ∑N k=1 c 2 k
} .
Lemma 8. Fix t,D ∈ N. Let {ξτ , uτ}τ≤t be random variables such that E[ξτ |u1, ξ1, · · · , uτ−1, ξτ−1, uτ ] = 0 and |ξτ | ≤ 1 almost surely. Let q : (u, φ) 7→ R be an arbitrary deterministic function satisfying |q(u, φ)− q(u, φ′)| ≤ C‖φ− φ′‖2 for all u, φ and φ′, where φ, φ′ ∈ RD. Then for any δ ∈ (0, 1) and R > 0,
Pr [ ∀φ ∈ BD(R) : ∣∣∣∣∣ t∑
τ=1
ξτq(uτ , φ) ∣∣∣∣∣ ≤ C + 2 ( 1 + √ Vq(φ) )√ D ln(2tR) + ln(1/δ) ] ≥ 1− δ,
where BD(R) , {x ∈ RD : ‖x‖2 ≤ R} and Vq(φ) , ∑ τ≤t q 2(uτ , φ).
Proof. Let > 0 be a small precision parameter to be specified later. LetH ⊆ BD(R) be a finite - covering of BD(R) such that supx∈BD(R) minz∈H ‖x− z‖2 ≤ . Using standard covering number arguments, such a covering exists with ln |H| ≤ D ln(2R/ ). For any φ ∈ BD(R) let φ′ , argminz∈H ‖φ− z‖2. By definition, ‖φ− φ′‖2 ≤ . This implies∣∣∣∑tτ=1 ξτ [q(uτ , φ)− q(uτ , φ′)]∣∣∣ ≤ Ct because |ξτ | ≤ 1 almost surely. Subsequently, for any ∆ > 0,
Pr [ ∃φ ∈ BD(R) : ∣∣∣∣∣ t∑
τ=1
ξτq(uτ , φ) ∣∣∣∣∣ > Ct + ∆ ] ≤ Pr [ ∃φ′ ∈ H : ∣∣∣∣∣ t∑
τ=1
ξτq(uτ , φ ′) ∣∣∣∣∣ > ∆ ]
≤ ∑ φ′∈H Pr [∣∣∣∣∣ t∑ τ=1 ξτq(uτ , φ ′) ∣∣∣∣∣ > ∆ ] ,
where the last inequality holds by the union bound.
For any fixed φ′ ∈ H, h(uτ , φ′) only depends on uτ , and therefore E[ξτ | q(uτ , φ′)] = 0 for all τ . Invoking Lemma 7 with Xτ , ∑ τ ′≤τ ξτ ′q(uτ ′ , φ ′) and cτ ′ = |q(uτ ′ , φ′)|, we have
Pr [∣∣∣∣∣ t∑
τ=1
ξτq(uτ , φ ′) ∣∣∣∣∣ > ∆ ] ≤ 2 exp { −∆2 2 ∑ τ≤t q 2(uτ , φ′) } = 2 exp { −∆2 2Vq(φ′) } Equating the right-hand side of the above inequality with δ′ and combining with the union bound application, we have
Pr [ ∃φ ∈ Bd(R) : ∣∣∣∣∣ t∑
τ=1
ξτh(uτ , φ) ∣∣∣∣∣ > Ct +√2Vq(φ′) ln(2/δ′) ] ≤ δ′|H|. (12)
Further equating δ′ = δ/|H| and using the fact that ln |H| ≤ D ln(2R/ ), we have
Pr [ ∃φ ∈ Bd(R) : ∣∣∣∣∣ t∑
τ=1
ξτq(uτ , φ) ∣∣∣∣∣ > Ct +√2DVq(φ′) ln(2R/ ) + 2Vq(φ′) ln(1/δ) ] ≤ δ.
Finally, as |q(uτ , φ′)− q(uτ , φ)| ≤ , we have Vq(φ′) ≤ 2Vq(φ) + 2t 2 and so
Pr [ ∃φ ∈ BD(R) : ∣∣∣∣∣ t∑
τ=1
ξτq(uτ , φ) ∣∣∣∣∣ > Ct + 2 √Dt ln(2R/ δ) + 2√Vq(φ)(D ln(2R/ ) + ln(1/δ) ] ≤ δ.
Setting = 1/t in the above inequality completes the proof.

Review summaries:
This 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.   

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.