Online Learning in MDPs with Linear Function Approximation and Bandit Feedback
Year: 2022

Abstract:
We consider the problem of online learning in an episodic Markov decision process, where the reward function is allowed to change between episodes in an adversarial manner and the learner only observes the rewards associated with its actions. We assume that rewards and the transition function can be represented as linear functions in terms of a known low-dimensional feature map, which allows us to consider the setting where the state space is arbitrarily large. We also assume that the learner has a perfect knowledge of the MDP dynamics. Our main contribution is developing an algorithm whose expected regret after T episodes is bounded by Õ (√ dHT ) , where H is the number of steps in each episode and d is the dimensionality of the feature map.

text: (√ dHT ) , where H is the number of steps in each episode and d is the
dimensionality of the feature map.

heading: 1 Introduction
text: We study the problem of online learning in episodic Markov Decision Processes (MDP), modelling a sequential decision making problem where the interaction between a learner and its environment is divided into T episodes of fixed length H . At each time step of the episode, the learner observes the current state of the environment, chooses one of the K available actions, and earns a reward. Consequently, the state of the environment changes according to the transition function of the underlying MDP, as a function of the previous state and the action taken by the learner. A key distinguishing feature of our setting is that we assume that the reward function can change arbitrarily between episodes, and the learner only has access to bandit feedback: instead of being able to observe the reward function at the end of the episode, the learner only gets to observe the rewards that it actually received. As traditional in this line of work, we aim to design algorithms for the learner with theoretical guarantees on her regret, which is the difference between the total reward accumulated by the learner and the total reward of the best stationary policy fixed in hindsight.
Unlike most previous work on this problem, we allow the state space to be very large and aim to prove performance guarantees that do not depend on the size of the state space, bringing theory one step closer to practical scenarios where assuming finite state spaces is unrealistic. To address the challenge of learning in large state spaces, we adopt the classic RL technique of using linear function approximation and suppose that we have access to a relatively low-dimensional feature map that can be used to represent policies and value functions. We will assume that the feature map is expressive enough so that all action-value functions can be expressed as linear functions of the features, and that the learner has full knowledge of the transition function of the MDP.
Our main contribution is designing a computationally efficient algorithm called ONLINE Q-REPS, and prove that in the setting described above, its regret is at most O (√ dHTD (µ∗‖µ0) ) , where d is the dimensionality of the feature map and D (µ∗‖µ0) is the relative entropy between the state-action distribution µ∗ induced by the optimal policy and an initial distribution µ0 given as input to the
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
algorithm. Notably, our results do not require the likelihood ratio between these distributions to be uniformly bounded, and the bound shows no dependence on the eigenvalues of the feature covariance matrices. Our algorithm itself requires solving a d2-dimensional convex optimization problem at the beginning of each episode, which can be solved to arbitrary precision ε in time polynomial in d and 1/ε, independently of the size of the state-action space.
Our work fits into a long line of research considering online learning in Markov decision processes. The problem of regret minimization in stationary MDPs with a fixed reward function has been studied extensively since the work of Burnetas and Katehakis [6], Auer and Ortner [2], Tewari and Bartlett [31], Jaksch et al. [14], with several important advances made in the past decade [9, 10, 4, 13, 15]. While most of these works considered small finite state spaces, the same techniques have been very recently extended to accommodate infinite state spaces under the assumption of realizable function approximation by Jin et al. [17] and Yang and Wang [33]. In particular, the notion of linear MDPs introduced by Jin et al. [17] has become a standard model for linear function approximation and has been used in several recent works (e.g., 22, 32, 1).
Even more relevant is the line of work considering adversarial rewards, initiated by Even-Dar et al. [12], who consider online learning in continuing MDPs with full feedback about the rewards. They proposed a MDP-E algorithm, that achieves O(τ2 √ T logK) regret, where τ is an upper bound on the mixing time of the MDP. Later, Neu et al. [25] proposed an algorithm which guarantees Õ (√ τ3KT/α )
regret with bandit feedback, essentially assuming that all states are reachable with probability α > 0 under all policies. In our work, we focus on episodic MDPs with a fixed episode length H . The setting was first considered in the bandit setting by Neu et al. [23], who proposed an algorithm with a regret bound of O(H2 √ TK/α). Although the number of states does not appear explicitly in the bound, the regret scales at least linearly with the size of the state space X , since |X | ≤ H/α. Later work by Zimin and Neu [35], Dick et al. [11] eliminated the dependence on α and proposed an algorithm achieving Õ( √ TH|X |K) regret. Regret bounds for the full-information case without prior knowledge of the MDP were achieved by Neu et al. [24] and Rosenberg and Mansour [30], of order Õ(H|X |K √ T ) and Õ(H|X | √ KT ), respectively. These results were recently extended to handle bandit feedback about the rewards by Jin et al. [16], ultimately resulting in a regret bound of Õ(H|X | √ KT ).
As apparent from the above discussion, all work on online learning in MDPs with adversarial rewards considers finite state spaces. The only exception we are aware of is the recent work of Cai et al. [7], whose algorithm OPPO is guaranteed to achieve Õ (√ d3H3T ) , assuming that the learner has access to d-dimensional features that can perfectly represent all action-value functions. While Cai, Yang, Jin, and Wang [7] remarkably assumed no prior knowledge of the MDP parameters, their guarantees are only achieved in the full-information case. This is to be contrasted with our results that are achieved for the much more restrictive bandit setting, albeit with the stronger assumption of having full knowledge of the underlying MDP, as required by virtually all prior work in the bandit setting, with the exception of Jin et al. [16].
Our results are made possible by a careful combination of recently proposed techniques for contextual bandit problems and optimal control in Markov decision processes. In particular, a core component of our algorithm is a regularized linear programming formulation of optimal control in MDPs due to Bas-Serrano et al. [5], which allows us to reduce the task of computing near-optimal policies in linear MDPs to a low-dimensional convex optimization problem. A similar algorithm design has been previously used for tabular MDPs by Zimin and Neu [35], Dick et al. [11], with the purpose of removing factors of 1/α from the previous state-of-the-art bounds of Neu et al. [23]. Analogously to this improvement, our methodology enables us to make strong assumptions on problem-dependent constants like likelihood ratios between µ∗ and µ0 or eigenvalues of the feature covariance matrices. Another important building block of our method is a version of the recently proposed Matrix Geometric Resampling procedure of Neu and Olkhovskaya [21] that enables us to efficiently estimate the reward functions. Incorporating these estimators in the algorithmic template of Bas-Serrano et al. [5] is far from straightforward and requires several subtle adjustments.
Notation. We use 〈·, ·〉 to denote inner products in Euclidean space and by ‖·‖ we denote the Euclidean norm for vectors and the operator norm for matrices. For a symmetric positive definite matrix A, we use λmin(A) to denote its smallest eigenvalue. We write tr (A) for the trace of a matrix A and use A < 0 to denote that an operator A is positive semi-definite, and we use A < B to denote
A−B < 0. For a d-dimensional vector v, we denote the corresponding d× d diagonal matrix by diag(v). For a positive integer N , we use [N ] to denote the set of positive integers {1, 2, . . . , N}. Finally, we will denote the set of all probability distributions over any set X by ∆X .

heading: 2 Preliminaries
text: An episodic Markovian Decision Process (MDP), denoted by M = (X ,A, H, P, r) is defined by a state space X , action space A, episode length H ∈ Z+, transition function P : X ×A → ∆X and a reward function r : X ×A → [0, 1]. For convenience, we will assume that both X and A are finite sets, although we allow the state space X to be arbitrarily large. Without significant loss of generality, we will assume that the set of available actions is the same A in each state, with cardinality |A| = K. Furthermore, without any loss of generality, we will assume that the MDP has a layered structure, satisfying the following conditions:
• The state set X can be decomposed into H disjoint sets: X = ∪Hh=1Xh, • X1 = {x1} and XH = {xH} are singletons, • transitions are only possible between consecutive layers, that is, for any xh ∈ Xh, the
distribution P (·|x, a) is supported on Xh+1 for all a and h ∈ [H − 1].
These assumptions are common in the related literature (e.g., 23, 35, 30) and are not essential to our analysis; their primary role is simplifying our notation.
In the present paper, we consider an online learning problem where the learner interacts with its environment in a sequence of episodes t = 1, 2, . . . , T , facing a different reward functions rt,1, . . . rt,H+1 selected by a (possibly adaptive) adversary at the beginning of each episode t. Oblivious to the reward function chosen by the adversary, the learner starts interacting with the MDP in each episode from the initial state Xt,1 = x1. At each consecutive step h ∈ [H − 1] within the episode, the learner observes the state Xt,h, picks an action At,h and observes the reward rt,h(Xt,h, At,h). Then, unless h = H , the learner moves to the next state Xt,h+1, which is generated from the distribution P (·|Xt,h, At,h). At the end of step H , the episode terminates and a new one begins. The aim of the learner is to select its actions so that the cumulative sum of rewards is as large as possible.
Our algorithm and analysis will make use of the concept of (stationary stochastic) policies π : X → ∆A. A policy π prescribes a behaviour rule to the learner by assigning probability π(a|x) to taking action a at state x. Let τπ = ((X1, A1), (X2, A2), . . . , (XH , AH)) be a trajectory generated by following the policy π through the MDP. Then, for any xh ∈ Xh, ah ∈ A we define the occupancy measure µπh(x, a) = Pπ [(x, a) ∈ τπ]. We will refer to the collection of these distributions across all layers h as the occupancy measure induced by π and denote it as µπ = (µπ1 , µ π 2 , . . . , µ π H). We will denote the set of all valid occupancy measures by U and note that this is a convex set, such that for every element µ ∈ U the following set of linear constraints is satisfied:∑
a∈A µh+1(x, a) = ∑ x′,a′∈Xh×A P (x|x′, a′)µh(x′, a′), ∀x ∈ Xh+1, h ∈ [H − 1], (1)
as well as ∑ a µ1(x1, a) = 1. From every valid occupancy measure µ, a stationary stochastic
policy π = π1, . . . , πH−1 can be derived as πµ,h(a|x) = µh(x, a)/ ∑ a′ µh(x, a
′). For each h, introducing the linear operators E and P through their action on a set state-action distribution uh as (ETuh)(x) = ∑ a∈A uh(x, a) and (P T huh)(x) = ∑ x′,a′∈Xh,A P (x|x ′, a′)uh(x ′, a′), the constraints can be simply written as ETµh+1 = P Thµh for each h. We will use the inner product notation for the sum over the set of states and actions: 〈µh, rh〉 = ∑ (x,a)∈(Xh×A) µh(x, a)rt,h(x, a). Using this notation, we formulate our objective as selecting a sequence of policies πt for each episode t in a way that it minimizes the total expected regret defined as
RT = sup π∗ T∑ t=1 H∑ h=1 (Eπ∗ [rt,h(X∗h, A∗h)]− Eπt [rt(Xt,h, At,h)]) = sup µ∗∈U T∑ t=1 H∑ h=1 〈µ∗h − µ πt h , rt,h〉 ,
where the notations Eπ∗ [·] and Eπt [·] emphasize that the state-action trajectories are generated by following policies π∗ and πt, respectively. As the above expression suggests, we can reformulate our online learning problem as an instance of online linear optimization where in each episode t, the
learner selects an occupancy measure µt ∈ U (with µt = µπt) and gains reward ∑H h=1〈µt,h, rt,h〉. Intuitively, the regret measures the gap between the total reward gained by the learner and that of the best stationary policy fixed in hindsight, with full knowledge of the sequence of rewards chosen by the adversary. This performance measure is standard in the related literature on online learning in MDPs, see, for example Neu et al. [23], Zimin and Neu [35], Neu et al. [24], Rosenberg and Mansour [30], Cai et al. [7].
In this paper, we focus on MDPs with potentially enormous state spaces, which makes it difficult to design computationally tractable algorithms with nontrivial guarantees, unless we make some assumptions. We particularly focus on the classic technique of relying on linear function approximation and assuming that the reward functions occurring during the learning process can be written as a linear function of a low-dimensional feature map. We specify the form of function approximation and the conditions our analysis requires as follows: Assumption 1 (Linear MDP with adversarial rewards). There exists a feature map ϕ : X ×A → Rd and a collection of d signed measures m = (m1, . . . ,md) on X , such that for any (x, a) ∈ X ×A the transition function can be written as
P (·|x, a) = 〈m(·), ϕ(x, a)〉 . Furthermore, the reward function chosen by the adversary in each episode t can be written as
rt,h(x, a) = 〈θt,h, ϕ(x, a)〉 for some θt,h ∈ Rd. We assume that the features and the parameter vectors satisfy ‖ϕ(x, a)‖ ≤ σ and that the first coordinate ϕ1(x, a) = 1 for all (x, a) ∈ X ×A. Also we assume that ‖θt,h‖ ≤ R.
Online learning under this assumption, but with a fixed reward function, has received substantial attention in the recent literature, particularly since the work of Jin et al. [17] who popularized the term “Linear MDP” to refer to this class of MDPs. This has quickly become a common assumption for studying reinforcement learning algorithms (Cai et al. [7], Jin et al. [17], Neu and Pike-Burke [22], Agarwal et al. [1]). This is also a special case of factored linear models (Yao et al. [34], Pires and Szepesvári [29]).
Linear MDPs come with several attractive properties that allow efficient optimization and learning. In this work, we will exploit the useful property shown by Neu and Pike-Burke [22] and Bas-Serrano et al. [5] that all occupancy measures in a linear MDP can be seen to satisfy a relaxed version of the constraints in Equation (1). Specifically, for all h, defining the feature matrix Φh ∈ R(Xh×A)×d with its action on the distribution u as ΦThu = ∑ x,a∈Xh,A uh(x, a)ϕ(x, a), we define UΦ as the set of state-action distributions (µ, u) = ((µ1, . . . , µH), (u1, . . . , uH)) satisfying the following constraints:
ETuh+1 = P T hµh (∀h), ΦThuh = ΦThµh (∀h), ETu1 = 1. (2) It is easy to see that for all feasible (µ, u) pairs, u satisfies the original constraints (1) if the MDP satisfies Assumption 1: since the transition operator can be written as Ph = ΦhMh for some matrix Mh. In this case, we clearly have
ETuh+1 = P T hµh = M T hΦ T hµh = M T hΦ T huh = P T huh, (3) showing that any feasible u is indeed a valid occupancy measure. Furthermore, due to linearity of the rewards in Φ, we also have 〈uh, rt,h〉 = 〈µh, rt,h〉 for all feasible (µ, u) ∈ UΦ. While the number of variables and constraints in Equation (2) is still very large, it has been recently shown that approximate linear optimization over this set can be performed tractably [22, 5]. Our own algorithm design described in the next section will heavily build on these recent results.

heading: 3 Algorithm and main results
text: This section presents our main contributions: a new efficient algorithm for the setting described above, along with its performance guarantees. Our algorithm design is based on a reduction to online linear optimization, exploiting the structural results established in the previous section. In particular, we will heavily rely on the algorithmic ideas established by Bas-Serrano et al. [5], who proposed an efficient reduction of approximate linear optimization over the high-dimensional set UΦ to a low-dimensional convex optimization problem. Another key component of our algorithm is an efficient estimator of the reward vectors θt,h based on the work of Neu and Olkhovskaya [21]. For reasons that we will clarify in Section 4, accommodating these reward estimators into the framework of Bas-Serrano et al. [5] is not straightforward and necessitates some subtle changes.

heading: 3.1 The policy update rule
text: Our algorithm is an instantiation of the well-known “Follow the Regularized Leader” (FTRL) template commonly used in the design of modern online learning methods (see, e.g., 26). We will make the following design choices:
• The decision variables will be the vector (µ, u) ∈ R2(X×A), with the feasible set U2Φ defined through the constraints
ETuh = P T hµh (∀h), ΦThdiag(uh)Φh = ΦThdiag(µh)Φh (∀h). (4)
These latter constraints ensure that the feature covariance matrices under u and µ will be identical, which is necessary for technical reasons that will be clarified in Section 4. Notice that, due to our assumption that ϕ1(x, a) = 1, we have U2Φ ⊆ UΦ, so all feasible u’s continue to be feasible for the original constraints (1).
• The regularization function will be chosen as 1ηD(µ‖µ0) + 1 αDC(u‖µ0) for some positive
regularization parameters η and α, where µ0 is the occupancy measure induced by the uniform π0 with π0(a|x) = 1K for all x, a, and D and DC are the marginal and conditional relative entropy functions respectively defined as D(µ‖µ0) = ∑H h=1D(µh‖µ0,h) and
DC(µ‖µ0) = ∑H h=1DC(µh‖µ0,h) with
D(µh‖µ0,h) = ∑
(x,a)∈(Xh×A)
µh(x, a) log µh(x, a)
µ0,h(x, a) , and
DC(µh‖µ0,h) = ∑
(x,a)∈(Xh×A)
µh(x, a) log πµ,h(a|x) π0,h(a|x) .
With these choices, the updates of our algorithm in each episode will be given by
(µt, ut) = arg max (µ,u)∈U2Φ { t−1∑ s=1 H−1∑ h=1 〈µh, r̂s,h〉 − 1 η D(µ‖µ0)− 1 α DC(u‖µ0) } (5)
where r̂t,h ∈ RX×A is an estimator of the reward function rt,h that will be defined shortly. As written above, it is far from obvious if these updates can be calculated efficiently. The following result shows that, despite the apparent intractability of the maximization problem, it is possible to reduce the above problem into a d2-dimensional unconstrained convex optimization problem:
Proposition 1. Define for each h ∈ [H − 1], a matrix Zh ∈ Rd×d and let matrix Z ∈ Rd×d(H−1) be defined as Z = (Z1, . . . , ZH−1). We will write h(x) = h, if x ∈ Xh. Define the Q-function taking values QZ(x, a) = ϕ(x, a)TZh(x)ϕ(x, a) and define the value function
VZ(x) = 1
α log  ∑ a∈A(x) π0(a|x)eαQZ(x,a) 
For any h ∈ [H−1] and for any x ∈ Xh, a ∈ A(x), denotePx,aVZ = ∑ x′∈Xh(x)+1 P (x
′|x, a)VZ(x′) and ∆t,Z(x, a) = ∑t−1 s=1 r̂s,h(x)(x, a) + Px,aVZ − QZ(x, a). Then, the optimal solution of the optimization problem (5) is given as
π̂t,h(a|x) = π0(a|x)e α ( QZ∗t (x,a)−VZ∗t (x) ) ,
µ̂t,h(x, a) ∝ µ0(x, a)eη∆t,Z∗t (x,a),
where Z∗t = (Z ∗ t,1, . . . , Z ∗ t,H−1) is the minimizer of the convex function
Gt(Z) = 1
η H−1∑ h=1 log  ∑ x∈Xh,a∈A(x) µ0(x, a)e η∆t,Z(x,a) + VZ(x1). (6)
A particular merit of this result is that it gives an explicit formula for the policy πt that induces the optimal occupancy measure ut, and that πt(a|x) can be evaluated straightforwardly as a function of the features ϕ(x, a) and the parameters Z∗t . The proof of the result is based on Lagrangian duality, and mainly follows the proof of Proposition 1 in Bas-Serrano et al. [5], with some subtle differences due to the episodic setting we consider and the appearance of the constraints ΦThdiag(uh)Φh = ΦThdiag(µh)Φh. The proof is presented in Appendix A.1.
The proposition above inspires a very straightforward implementation that is presented as Algorithm 1. Due to the direct relation with the algorithm of Bas-Serrano et al. [5], we refer to this method as ONLINE Q-REPS, where Q-REPS stands for “Relative Entropy Policy Search with Q-functions”. ONLINE Q-REPS adapts the general idea of Q-REPS to the online setting in a similar way as the O-REPS algorithm of Zimin and Neu [35] adapted the Relative Entropy Policy Search method of Peters et al. [28] to regret minimization in tabular MDPs with adversarial rewards. While O-REPS would in principle be still applicable to the large-scale setting we study in this paper and would plausibly achieve similar regret guarantees, its implementation would be nearly impossible due to the lack of the structural properties enjoyed by ONLINE Q-REPS, as established in Proposition 1.
Algorithm 1 ONLINE Q-REPS Parameters: η, α > 0, exploration parameter γ ∈ (0, 1), Initialization: Set θ̂1,h = 0 for all h, compute Z1. For t = 1, . . . , T , repeat:
• Draw Yt ∼ Ber(γ), • For h = 1, . . . ,H , do:
– Observe Xt,h and, for all a ∈ A(Xt,h), set
πt,h(a|Xt,h) = π0,h(a|Xt,h)eα(QZt (Xt,h,a)−VZt (Xt,h)),
– if Y = 0, draw At,h ∼ πt,h(·|Xt,h), otherwise draw At,h ∼ π0,h(·|Xt,h), – observe the reward rt,h(Xt,h, At,h).
• Compute θ̂t,1, . . . , θ̂t,H−1, Zt+1.

heading: 3.2 The reward estimator
text: We now turn to describing the reward estimators r̂t,h, which will require several further definitions. Specifically, a concept of key importance will be the following feature covariance matrix:
Σt,h = Eπt [ϕ(Xt,h, At,h)ϕ(Xt,h, At,h)T] .
Making sure that Σt,h is invertible, we can define the estimator
θ̃t,h = Σ −1 t,hϕ(Xt,h, At,h)rt,h(Xt,h, At,h). (7)
This estimate shares many similarities with the estimates that are broadly used in the literature on adversarial linear bandits [18, 3, 8]. It is easy to see that θ̃t,h is an unbiased estimate of θt,h:
Et [ θ̃t,h ] = Et [ Σ−1t,hϕ(Xt,h, At,h)ϕ(Xt,h, , At,h) Tθt,h ] = Σ−1t,hΣt,hθt,h = θt,h.
Unfortunately, exact computation of Σt,h is intractable. To address this issue, we propose a method to directly estimate the inverse of the covariance matrix Σt,h by adapting the Matrix Geometric Resampling method of Neu and Olkhovskaya [21] (which itself is originally inspired by the Geometric Resampling method of 19, 20). Our adaptation has two parameters β > 0 andM ∈ Z+, and generates an estimate of the inverse covariance matrix through the following procedure1:
1The version we present here is a naïve implementation, optimized for readability. We present a more practical variant in Appendix B
Matrix Geometric Resampling Input: simulator of P , policy π̃t = (π̃t,1, . . . , π̃t,H−1). For i = 1, . . . ,M , repeat:
1. Simulate a trajectory τ(i) = {(X1(i), A1(i)), . . . , (XH−1(i), AH−1(i))}, following the policy π̃t in P , 2. For h = 1, . . . ,H − 1, repeat: Compute (a) Bi,h = ϕ(Xh(i), Ah(i))ϕ(Xh(i), Ah(i))T,
(b) Ci,h = ∏i j=1(I − βBj,h).
Return Σ̂+t,h = βI + β ∑M i=1 Ci,h for all h ∈ [H − 1].
Based on the above procedure, we finally define our estimator as
θ̂t,h = Σ̂ + t,hϕ(Xt,h, At,h)rt,h(Xt,h, At,h).
The idea of the estimate is based on the truncation of the Neumann-series expansion of the matrix Σ−1t,h at the M th order term. Then, for large enough M , the matrix Σ + t,h is a good estimator of the inverse covariance matrix, which will be quantified formally in the analysis. For more intuition on the estimate, see section 3.2. in Neu and Olkhovskaya [21]. With a careful implementation explained in Appendix B, θ̂t,h can be computed in O(MHKd) time, using M calls to the simulator.

heading: 3.3 The regret bound
text: We are now ready to state our main result: a bound on the expected regret of ONLINE Q-REPS. During the analysis, we will suppose that all the optimization problems solved by the algorithm are solved up to an additive error of ε ≥ 0. Furthermore, we will denote the covariance matrix generated by the uniform policy at layer h as Σ0,h, and make the following assumption: Assumption 2. The eigenvalues of Σ0,h for all h are lower bounded by λmin > 0.
Our main result is the following guarantee regarding the performance of ONLINE Q-REPS: Theorem 1. Suppose that the MDP satisfies Assumptions 1 and 2 and λmin > 0. Furthermore, suppose that, for all t, Zt satisfies Gt(Zt) ≤ minZ Gt(Z) + ε for some ε ≥ 0. Then, for γ ∈ (0, 1), M ≥ 0, positive η ≤ 1σ2β(M+1)H and any positive β ≤ 1 2σ2 √ d(M+1) , the expected regret of ONLINE Q-REPS over T episodes satisfies
RT ≤2TσRH · exp (−γβλminM) + γHT + ηTH(3 + 5d) + 1
η D(µ∗‖µ0)
+ 1
α DC(u
∗‖µ0) + √ αεTH(1 + η(M + 1)2).
Furthermore, letting β = 1 2σ2 √ d(M+1)
, M = ⌈ σ4d log2( √ THσR)
γ2λ2min
⌉ , η = 1√
TdH , α = 1√ TdH and
γ = 1√ TH and supposing that T is large enough so that the above constraints on M,γ, η and β are satisfied, we also have
RT =Õ (√ dHT (1 +D(µ∗‖µ0) +DC(u∗‖µ0)) + √ ε(TH)9/4d5/4 1
λ4min
) .
Thus, when all optimization problems are solved up to precision ε = (TH)−7/2d−3/2λ8min, the regret of ONLINE Q-REPS is guaranteed to be of O (√ dHTD(µ∗‖µ0) ) .

heading: 3.4 Implementation
text: While Proposition 1 establishes the form of the ideal policy updates πt through the solution of an unconstrained convex optimization problem, it is not obvious that this optimization problem can be
solved efficiently. Indeed, one immediate challenge in optimizing Gt is that its gradient takes the form
∇Gt(Z) = ∑ x,a µ̃Z(x, a) ϕ(x, a)ϕ(x, a)T −∑ x′,a′ P (x′|x, a)πZ(a′|x′)ϕ(x′, a′)ϕ(x′, a′)T  ,
where µ̃Z(x, a) = µ0(x,a) exp(η∆Z(x,a))∑
x′,a′ µ0(x ′,a′) exp(η∆Z(x′,a′))
. Sampling from this latter distribution (and thus ob-
taining unbiased estimators of∇Gt(Z)) is problematic due to the intractable normalization constant. This challenge can be addressed in a variety of ways. First, one can estimate the gradients via weighted importance sampling from the distribution µ̃Z and using these in a stochastic optimization procedure. This approach has been recently proposed and analyzed for an approximate implementation of REPS by Pacchiano et al. [27], who showed that it results in ε-optimal policy updates given polynomially many samples in 1/ε. Alternatively, one can consider an empirical counterpart of the loss function replacing the expectation with respect to µ0 with an empirical average over a number of i.i.d. samples drawn from the same distribution. The resulting loss function can then be optimized via standard stochastic optimization methods. This approach has been proposed and analyzed by Bas-Serrano et al. [5]. We describe the specifics of this latter approach in Appendix C.

heading: 4 Analysis
text: This section gives the proof of Theorem 1 by stating the main technical results as lemmas and putting them together to obtain the final bound. In the first part of the proof, we show the upper bound on the auxiliary regret minimization game with general reward inputs and ideal updates. Then, we relate this quantity to the true expected regret by taking into account the properties of our reward estimates and the optimization errors incurred when calculating the updates. The proofs of all the lemmas are deferred to Appendix A.
We start by defining the idealized updates (µ̂t, ût) obtained by solving the update steps in Equation (5) exactly, and we let ut be the occupancy measure induced by policy πt that is based on the near-optimal parameters Zt satisfying Gt(Zt) ≤ minZ Gt(Z) + ε. We will also let µt be the occupancy measure resulting from mixing ut with the exploratory distribution µ0 and note that µt,h = (1−γ)ut,h+γµt,h. Using this notation, we will consider an auxiliary online learning problem with the sequence of reward functions given as r̂t,h(x, a) = 〈ϕ(x, a), θ̂t,h〉, and study the performance of the idealized sequence (µ̂t, ût) therein:
R̂T = T∑ t=1 H−1∑ h=1 〈µ∗h − ût,h, r̂t,h〉.
Our first lemma bounds the above quantity: Lemma 1. Suppose that θ̂t,h is such that ∣∣η · 〈ϕ(x, a), θ̂t,h〉∣∣ < 1 holds for all x, a. Then, the auxiliary regret satisfies
R̂T ≤ η T∑ t=1 H−1∑ h=1 〈µ̂t,h, r̂2t,h〉+ 1 η D(µ∗‖µ0) + 1 α DC(u ∗‖µ0).
While the proof makes use of a general potential-based argument commonly used for analyzing FTRLstyle algorithms, it involves several nontrivial elements exploiting the structural results concerning ONLINE Q-REPS proved in Proposition 1. In particular, these properties enable us to upper bound the potential differences in a particularly simple way. The main term on contributing to the regret R̂T can be bounded as follows: Lemma 2. Suppose that ϕ(Xt,h, a) is satisfying ‖ϕ(Xt,h, a)‖2 ≤ σ for any a, 0 < β ≤
1 2σ2 √ d(M+1) and M > 0. Then for each t and h,
Et [ 〈µ̂t,h, r̂2t,h〉 ] ≤ 3 + 5d+ (M + 1)2 ‖ût,h − ut,h‖1 .
The proof of this claim makes heavy use of the fact that 〈µ̂t,h, r̂2t,h〉 = 〈ût,h, r̂2t,h〉, which is ensured by the construction of the reward estimator r̂t,h and the constraints on the feature covariance matrices
in Equation (4). This property is not guaranteed to hold under the first-order constraints (2) used in the previous works of Neu and Pike-Burke [22] and Bas-Serrano et al. [5], which eventually justifies the higher complexity of our algorithm.
It remains to relate the auxiliary regret to the actual regret. The main challenge is accounting for the mismatch between µt and ut, and the bias of r̂t, denoted as bt,h(x, a) = Et [r̂t,h(x, a)]− rt,h(x, a). To address these issues, we observe that for any t, h, we have
〈µt,h, rt,h〉 = 〈(1− γ)ut,h + γµ0,h, rt,h〉 = 〈(1− γ)ût,h + γµ0,h, rt,h〉+ (1− γ) 〈ut,h − ût,h, rt,h〉 ≥ Et [〈(1− γ)ût,h + γµ0,h, r̂t,h〉] + ‖bt,h‖∞ + (1− γ) ‖ut,h − ût,h‖1 ,
where in the last step we used the fact that ‖rt,h‖∞ ≤ 1. After straightforward algebraic manipulations, this implies that the regret can be bounded as
RT ≤ (1− γ)E [ R̂T ] + T∑ t=1 H∑ h=1 E [ γ 〈µ0,h − µ∗h, rt,h〉+ ‖ût,h − ut,h‖1 + ‖bt,h‖∞ ] . (8)
In order to proceed, we need to verify the condition ∣∣η · 〈ϕ(x, a), θ̂t,h〉∣∣ < 1 so that we can apply
Lemma 1 to bound R̂T . This is done in the following lemma: Lemma 3. Suppose that η ≤ 1σ2β(M+1)H . Then, for all, t, h, the reward estimates satisfy η ‖r̂t,h‖∞ < 1.
Proceeding under the condition η(M + 1), we can apply Lemma 1 to bound the first term on the right-hand side of Equation (8), giving
RT ≤ D(µ∗‖µ0)
η + DC(u ∗‖µ0) α + (3 + 5d)ηHT + γHT
+ ∑ t,h E [ (η(M + 1)2 + 1) ‖ût,h − ut,h‖1 + ‖bt,h‖∞ ] .
It remains to bound the bias of the reward estimators and the effect of the optimization errors that result in the mismatch between ut and ût. The following lemma shows that this mismatch can be directly controlled as a function of the optimization error: Lemma 4. The following bound is satisfied for all t and h: ‖ût,h − ut,h‖1 ≤ √ 2αε.
The final element in the proof is the following lemma that bounds the bias of the estimator: Lemma 5. For M ≥ 0, β = 1σ2β(M+1)H , we have ‖bt,h‖∞ ≤ σR exp (−γβλminM).
Putting these bounds together with the above derivations concludes the proof of Theorem 1.

heading: 5 Discussion
text: This paper studies the problem of online learning in MDPs, merging two important lines of work on this problem concerned with linear function approximation [17, 7] and bandit feedback with adversarial rewards [23, 25, 35]. Our results are the first in this setting and not directly comparable with any previous work, although some favorable comparisons can be made with previous results in related settings. In the tabular setting where d = |X ||A|, our bounds exactly recover the minimax optimal guarantees first achieved by the O-REPS algorithm of Zimin and Neu [35]. For realizable linear function approximation, the work closest to ours is that of Cai et al. [7], who prove bounds of order √ d2H3T , which is worse by a factor of √ dH than our result. Their setting, however, is not exactly comparable to ours due to the different assumptions about the feedback about the rewards and the knowledge of the transition function.
One particular strength of our work is providing a complete analysis of the propagation of optimization errors incurred while performing the updates. This is indeed a unique contribution in the related literature, where the effect of such errors typically go unaddressed. Specifically, the algorithms of Zimin and Neu [35], Rosenberg and Mansour [30], and Jin et al. [16] are all based on solving convex optimization problems similar to ours, the effect of optimization errors or potential methods for
solving the optimization problems are not discussed at all. That said, we believe that the methods for calculating the updates discussed in Section 3.4 are far from perfect, and more research will be necessary to find truly practical optimization methods to solve this problem.
The most important open question we leave behind concerns the requirement to have full prior knowledge of P . In the tabular case, this challenge has been successfully addressed in the adversarial MDP problem recently by Jin et al. [16], whose technique is based on adjusting the constraints (1) with a confidence set over the transition functions, to account for the uncertainty about the dynamics. We find it plausible that a similar extension of ONLINE Q-REPS is possible by incorporating a confidence set for linear MDPs, as has been done in the case of i.i.d. rewards by Neu and Pike-Burke [22]. Nevertheless, the details of such an extension remain highly non-trivial, and we leave the challenge of working them out open for future work.

Review summaries:
This paper studies online learning in linear MDPs with bandit feedback and adversarial losses, and a known transition kernel. The regret bound against the best policy is of order $\sqrt{dHT}$. The proposed algorithm is an extension of Q-REPS of Bas-Serrano et al. which previously only works for the standard tabular setting. The authors claim that Q-REPS has computational advantages over O-REPS: despite the fact that the state and action space can be arbitrarily large, solving the optimization problem in each step only requires poly(d) computation. 

This paper studies the problem of online learning in a finite horizon MDP with known transition function and adversarially changing rewards at each episode and only bandit feedback from those rewards. In particular, the authors consider the case when the state space is large warranting linear function approximation with the assumption that the MDP is a linear MDP with a known feature map. The proposed method is essentially a follow-the-leader algorithm using estimated rewards, which are found by estimating the parameter of the reward function.

This paper presents a theoretical approach for online learning in Markov decision processes (MDPs) with time-varying adversarial rewards and infinite, and possibly continuous, state spaces. The proposed approach is based on linear assumptions on the structure of the MDP and approximate solutions of a linear programming problem. Theoretical regret bounds and discussions on the implementation of a tractable algorithmic solution are provided.