Online learning in MDPs with linear function approximation and bandit feedback. 
Authors: Gergely Neu
Julia Olkhovskaya
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
online learning
Markov decision processes
bandit feedback

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 $\widetilde{\mathcal{O}}(\sqrt{dHT})$, where $H$ is the number of steps in each episode and $d$ is the dimensionality of the feature map.

Online Learning in MDPs with Linear Function Approximation and Bandit Feedback
Gergely Neu
Julia Olkhovskaya Universitat Pompeu Fabra Barcelona, Spain o com
Universitat Pompeu Fabra Barcelona, Spain
gergely. neuê gma com
Abstract
We consider the problem of online learning in 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 known low-dimensional feature map, which allows us consider the setting where the state space is arbitrarily large. We also assume that the learner has a perfect knowledge of the MDP dynamies. Our main contribution is developing an algorithm whose expected regret after T' episodes is bounded by O(v where H. is the number of steps in each episode and d is the dimensionality of the feature map.
Introduction
We study the problem of online learning in episodic Markov Decision Processes (MDP), modelling sequential decision making problem where the interaction between learner and its environment divided into T episodes of fixed length H. At each time step of the episode, the learner observes of the K available actions, and earns reward.
the current state of the environment, chooses Consequently, the state of the environment changes according to the transition function of the underlying MDP, 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 observe the reward function at the end of the episode, the learner only gets to observe the rewards that actually received. As traditional in this line of work, we aim 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 the size of the state space, bringing theory one step closer to practical scenarios where assuming finite state spaces unrealistic. To address the challenge of learning in large state spaces, 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.
adopt the classic RL technique of using linear function
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 ((VdHT( (4r ((4))), where is the dimensionality of the feature map and D) (μ* (l/)) is the relative entropy between the state-action distribution j² induced by the optimal policy and an initial distribution Nl given input to the
35th Conference on Neural Information Processing Systems (NcurIPS 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 d df-dimensional convex optimization problem at the beginning of each episode, which can be solved to arbitrary precision e in time polynomial in d and 1/c, 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 [ Auer and Ortner (2). Tewari and Bartlett
[1] Jaksch et al. [14], with several important advances made in the past decade [9 10, 4 T3 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
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 log K) regret, where T is an upper bound on the mixing time of the MDP. Later, Neu et al. 25 proposed an algorithm which guarantees OVFKKT/a regret with bandit feedback, essentially assuming that all states are reachable with probability a > 0 under all policies. In our work, we focus on episodic MDPs with 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 OHH2 /a). 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| S H/a. Later work by Zimin and Neu (35). Dick et al. [II] climinated the dependence on a and proposed an algorithm achieving Ö D(VTH) for the cull-information case without prior knowledge of the MDP were achieved by Neu al. [24] and Rosenberg and Mansour [30), of order ( (T)) and (H) /K)). respectively. These results were recently extended to handle bandit feedback about the rewards by Jin et al. [16). ultimately resulting in regret bound of Ö(H) KKT).
regret. Regret bounds
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. M. whose algorithm OPPO is guaranteed achieve (VVd3 H²T), 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 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, core component of our algorithm is a regularized linear programming formulation of optimal control in MDPs due to Bas-Serrano al. (5). which allows 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. [T., with the purpose of removing factors of 1/a from the previous state-of-the Analogously to this improvement, our methodology enables us to make strong assumptions on problem-ddependet constants like likelihood ratios between je" and μi or cigenvalues 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 (2 that enables us to efficiently estimate the reward functions. Incorporating these estimators in the algorithmic template of -aa--erranoo et al. S is far from straightforward and requires several subtle adjustments.
bounds of Neu et al. (23).
Notation.
We use ( to denote inner products in Euclidean space and by ||-I| we denote the Euclidean norm for vectors and the operator norm for matrices. For a symmetric positive definite matrix A, we use Amin( ( (A) to denote its smallest eigenvalue. We write tr (A) for the trace of a matrix A and use A d 0 to denote that an operator A is positive semi-definite, and we use A b B to denote
2

---

A- >> O. For d-dimensional vector v, we denote the corresponding d x d diagonal matrix by diag(v). For positive integer N, we use [N] to denote the of positive integers 21.2..... ... J.. Finally, we will denote the set of all probability distributions over any set A' by Ax.
2 Preliminaries
An episodic Markovian Decision Process (MDP), denoted by M = -X, P.rr defined by a state space X, action space A, episode length H E __, transition function P: X A Ax and reward function X x A + [0, 1]. For convenience, we will assume that both X' and A are finite sets, although allow the state space X' 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 layered structure, satisfying the following conditions:
The state set X' can be decomposed into H disjoint sets: 1
X1 = {-1} and Xy = {rH} } are singletons,
transitions are only possible between consecutive layers, that is, for any Th. E Xn, the distribution P(- a) is supported on 2 for all a and / E [H -
These assumptions are common in the related literature (e.g.. analysis; their primary role is simplifying our notation.
23 35
30)
and are not essential to our
In the present paper, we consider online learning problem where the learner interacts with its envi- ronment in a sequence of episodes ( = 1, .,, T, facing a different reward functions r-. 1+ selected by a (possibly adaptive) adversary at the beginning of each episode t. Oblivious the reward function chosen by the adversary, the learner starts interacting with the MDP in each episode from the initial state X Tj. At each consecutive step h E [H] 1] within the episode, the learner observes the state Xt,r picks an action A and observes the reward rr. a. (Xe,h, Ar..). ). Then, unless h H, the learner moves to the next state Xth++1, which generated from the distribution P( Ar,a)- At the end of step H, the episode terminates and 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 behaviour rule the learner by assigning probability <aasr) to taking action at state r. Let -M = ((X1, A1), A2). (XH, AH)) be a trajectory generated by following the policy through the MDP. Then, for any Dy Xn, an E A we define the occupancy measure J.,, (z, a) = Pxx [(x, a) E r" We will refer to the collection of these distributions across all layers h as the occupancy measure induced by and denote as n= (pī, po...... ........ .. We will denote the set of all valid occupancy measures by 2 and note that this is convex set, such that for every element μ E l the following set of linear constraints is satisfied:
Σ (m+1(2r,)) aEA
Σ P(x|a', (aee,aa))uua (')uulz' o'), Vx X h E H 1]] a',0'
(1)
as well as En /1 (II, a) = 1. From every valid occupancy measure μ, stationary stochastic
policy 11 TH-1 can be derived as (alx( Mn (n, a)/ Ea (n a'). For each h, introducing the linear operators E and P through their action on set state- distribution un as Ee oeee. P(r|z', a' a')un Jun''', a'), the constraints can be simply written as E ju+11 PAun for each h. We will use the inner product notation for the sum over the set of states and actions: (un,ru) = ((raaj((, x.A) (I a)r,, a (2. a). Using this notation, we formulate our objective selecting a sequence of policies for each episode / in way that it minimizes the total expected regret defined as
(E"u,, un (z) ELEA un (2, a) and (P) (P,,))())
T
H E (X,, AD E., [re(Xe,,, Act))) = sup
T
H
Ry = sup
(p - 14 Te,.)
1 El
where the notations Er. [1] and E,,, [-] emphasize that the state-action trajectories are generated by following policies "' and n, respectively. As the above expression suggests, we can reformulate online learning problem an instance of online linear optimization where in each episode t, the
3

---

learner selects an occupancy measure Mu E U (with μ4, = =* and gains reward Σm=1 (He rr.k)) 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 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. 77.
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 as- sumptions. 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-dimenss -iw-deensional feature map. We specify the form of function approximation and the conditions our analysis requires as follows:
Assumption (Linear MDP with adversarial rewards). There exists a feature map ip : A - Rd and a collection of d signed measures m (Ml)....,M.)) on X, such that for any (5,a) E X A the transition function can be wrillen as
P(-1z, (m((),,((zz)))
Furthermore, the reward function chosen by the adversary each episode can be written as
(1,, a) (8e,n: spxx, a)}
for some 8r, E Rd. We assume that the features and the parameter vectors satisfy (1, a)ll S a and that the first coordinate yp 1i(2x, a) fofo all (x,a) E X x A. Also we assume that ||0,.all S R.
Online learning under this assumption, but with 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 this class of MDPs. This has quickly become a common assumption
for studying reinforcement learning algorithms (Cai et al. 77]. Jin et al. [77). Neu and Pike-Burke
[22 Agarwal al. M This is also 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 al. (5) that all occupancy measures in a linear MDP can be seen to satisfy a relaxed version of the constraints in Equation []. Specifically, for all h, defining the feature matrix D,, E R(X x.A)xd with its action on the distribution u as 47 = Ex,exx (z, (), a). we define Up as the set of (H), (u1...., (H)) satisfying the following constraints:
state-action distributions (1, u) =
ET UTTu+11 = PMAA (vh), D7,ux, = =1,4 (4h), ETu1= =1
(2)
It is easy to see that for all feasible (u, u) pairs, u satisfies the original constraints ① if the MDP satisfies Assumption[] since the transition operator can be written as P/. Mr for some matrix My. In this case, we clearly have
ETun+1 Pl M. M, P/
(3)
showing that any feasible u is indeed a valid occupancy measure. Furthermore, due to linearity of the rewards in Φ we also have (u,, Te,a. = (14, (t,h)) for all feasible (H, E Us. 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 5.. Our own algorithm design described in the next section will heavily build on these recent results.
3 Algorithm and main results
This section presents our main contributions: new efficient algorithm for the setting described above, along with its performance guarantees. Our algorithm design is based on a reduction online linear optimization, exploiting the structural results established in the previous section. In particular, we will heavily rely on the algorithmic ideas established by mas-Serrano al. [5]. who proposed an efficient reduction of approximate linear optimization over the nigh-dimensional set Ulg to -ow-dimessional convex optimization problem. Another key component of our algorithm an efficient estimator of the reward vectors Or, 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.

---

and 3.1 The policy update rule
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 (4, u) E (2(XXA), with the feasible set set defined through the constraints
E
Pi (vh);
di,diag(u,,) 1, d)daag(m)))) th
(vh).
These latter constraints ensure that the feature covariance matrices under and y will be identical, which is necessary for technical reasons that will be clarified in Section[4 4 Notice that, due our assumption that (21(x, a) we have Uig Us, all feasible u's continue
to be feasible for the original constraints ①
The regularization function will be chosen 2 ((pllpp)) + 1. DD (w) for some positive regularization parameters and a, where Po is the occupancy measure induced by the uniform To with TT(a(z) = 1 for all æ; a, and D and De are the marginal and conditional к relative entropy functions respectively defined D(ul(po) Σ Em=1 D(Halluo,n) and De(lllma) = Σmn (o( with
Pn(z,a)
D(unllpo,N)
Σ (Z,4)
( log
Mo, (x,
tr (a(z)
De(pullpoN))
E (x.a)E(XxXA))
pn a) log
To, (a|z)
With these choices, the updates of our algorithm each episode will given by
(pe, uz) = arg max (paa)e
Σ h=1
(Pn,Fa.N)
D(ullro)= "Do(ulllo))
(5)
17
where Fr.h E XxA is an estimator of the reward function Tr, 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, is possible to reduce the above problem into a d? -imensioonl unconstrained convex optimization problem:
Proposition Define for each h E [H 1), a matrix Zn. E R and let matrix Z E Bdxd(H-11 be defined 7 = (7,....,7m - We will write h(x) = h, i E Xn, Define the Q-function taking values Qz (xx a) = (f(,aa) 7nte)s((ar, a) and define the value function
V2(x) log Σ
1
aEAlz)
For any [H-1] for any Xh. A(x), denote Pæ.VV2 =E P(z'|z, 22'))z'
and (1, a) = Σ == (a, + Pz.VV - Q2(z,a). Then, the optimal solution of the optimization problem is given
(alx) To(a|z)e (Rx, (2x)( Dr, a) x po(x, a)e" 2 (v.a)
where Zi = (Zi,
-i,H-1) is the minimizer of the convex function
1 #-1
91(Z) = 1
Σ log Σ
Molx, 2(02)
+ Vz()).
(6)
5

---

A particular merit of this result is that it gives an explicit formula for the policy that induces the optimal occupancy measure ur and that T, [a]x)) can be evaluated straightforwardly as function of the features s0(x, a) and the parameters Zí The proof of the result is based on Lagrangian duality, and mainly follows the proof of Proposition 1 in Bas-Serrano al. [5), with some subtle differences due to the episodic setting we consider and the appearance of the constraints Φ7 di,giag ) " diag (p 1 The proof is presented in Appendix A.1
The proposition above inspires a very straightforward implementation that is presented as Algorithm Due to the direct relation with the algorithm of Bas-Serrane et al. [5], we refer to this method as ONLINE Q- Q-REPS, where Q- 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 similar way as the
O-REPS algorithm of Zimin and Neu [B5] adapted the Relative Entropy Policy Search method of Peters 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 nearly impossible due the lack of the structural properties enjoyed by ONLINE Q- Q-REPS, as established in Proposition I
Algorithm 1 ONLINE Q-REPS
Parameters: 7). > 0, exploration parameter y E (0, 1),
Initialization: Set 01,5 for all h, compute Z1.
For / = 1,..., T, repeat:
Draw Y, ~ Ber(y).
For l.................. H. do:
Observe X and, for all A(X,,)), set
T (r,,) = To,n =e
(X+,))
y = 0, draw AtA (t.,(((/-e,))) otherwise draw Ar, (- observe the reward re, (X,,((,, Ar,))
Compute 0......,,......... Z--1-
3.2
The reward estimator
We now turn to describing the reward estimators Fr. which will require several further definitions. Specifically, a concept key importance will the fealoinggeeauree covariance matrix:
Ee E,,,
Making sure that E,,, is invertible, we can define the estimator
0.,- E (.n))re,((ee Aek))
This estimate shares many similarities with the estimates that are broadly used in the literature on adversarial linear bandits [18 3 g. It easy see that de, is an unbiased estimate of fr.
01, E.
2 An,))(( 0,. -TT 02,
Unfortunately, exact computation of Σr,h is intractable. To address this issue, we propose method to directly estimate the inverse of the covariance matrix Σ,, by adapting the Matrix Geometric Resampling method of Neu and Olkhovskaya [21] (which itself is originally inspired by the Geometric and M Z.,, and generates
Resampling method 19 20). Our adaptation has two parameters an estimate of the inverse covariance matrix through the following procedure [T]
'The version we present here is naive implementation, optimized for readability. We present more practical variant in Appendix B

---

Matrix Geometric Resampling
Input:
simulator of P. policy मे = (Tt,l, -1)
For = 1..... M, repeat:
1. Simulate trajectory
T(i) {(1 (0), (1)),,.... (Xn-1(0) 1)) following the
policy n. P.
2. For 1.... H repeat:
Compute
(a) BL = ((),(1), (x))
(b) Ci = I1 - BB
Return D 3I B EE= Ci.A for all h E [H 1].
Based on the above procedure, we finally define our estimator as
0,, E A (Xe,, Ar,)).
The idea of the estimate is based on the truncation of the Neumann-series expansion of the matrix Ey at the .th order term. Then, for large enough M, the matrix Σ is good estimator of the inverse covariance matrix, which will be quantified formally in the analysis. For more intuition on the estimate, sec section 3.2. in Neu and Olkhovskaya (2I] With careful implementation explained in Appendix B or,b can be computed in O(MHKd time, using M calls to the simulator.
3.3 The regret bound
We now ready state our main result: bound 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 additive error of 0. Furthermore, will denote the covariance matrix generated by the uniform policy at layer as Σo,s. and make the following assumption:
Assumption 2. The eigenvalues of Lo for all h are lower bounded by Amin > 0.
Our main result is the following guarantec regarding the performance of ONLINE Q-REPS:
Theorem 1. Suppose that the MDP satisfies Assumptions / and 2 and Amin O. Furthermore, suppose that, for all t, 74 satisfies Gi (Zx) minz (Z) + for some e 2 O. Then, for y E (0, 1), M 2 O, positive 1) S "3S(M+ and any positive 3 S 20 /UMMA)) the expected regret of ONLINE
Q-REPS over T episodes satisfies
1 [pp0))po))
My 22ToRH exp exp (-7BAmin M) + +TH (3 + 5d) +
7)
Do(u" (P0) + VaETH(1 + MMM 1)
To'dlog'
Furthermore, letting
2nd fa(M+1) M
VTaH' a VTaH and
x2X² mii
== .TH and supposing that T is large enough so that the above constraints on M, Y, n7 and are satisfied, we also have
Ry = (VHHT (1 D(n"))(a)) + (o(u"((po)) + 2
X
Thus, when all optimization problems are solved precision = (TH) 17/2--22,"" 77/2 3/2 regret of ONLINE Q-REPS is guaranteed to be of O /dHTD( (|ao)).
Amin the
3.4 Implementation
While Proposition I estabbishes the form of the ideal policy updates म, through the solution of an unconstrained convex optimization problem, it is not obvious that this optimization problem can be
7

---

solved efficiently. Indeed, one immediate challenge in optimizing Gr is that its gradient takes the form
VQ.(2) = Eūz(e, (( -
E P(x' (a (a')a) "'(l'"''')'( d')
3,0
where (z u) Lz'.a' Po a (xxp(nz((""aa)))) Sampling from this latter distribution (and thus ob- taining unbiased estimators of (Z)( is problematic due to the intractable normalization constant.
This challenge be addressed in variety of ways. First, importance sampling from the distribution fiz 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 e-optimal policy updates given polynomially many samples in 1/s. Alternatively, one can consider an empirical counterpart of the loss function replacing the expectation with respect to AA with an empirical average over 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 We describe the specifics of this latter approach in Appendix C al. [5]
estimate the gradients via weighted
Analysis
This section gives the proof of Theorem by stating the main technical results lemmas and putting them together to obtain the final bound. 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 deferred to Appendix|A A
We start by defining the idealized updates (ft (e) obtained by solving the update steps in Equation (5) exactly, and we let uy be the occupancy measure induced by policy n, that is based on the near- near-optimal parameters Ze satisfying G. (Z,) < minz (Z) + We will also let μ4 be the occupancy measure resulting from mixing u, with the exploratory distribution Ho and note that Mr,1 (1-7)uu, + Using this notation, we will consider auxiliary online learning problem with the sequence of reward functions given (2, a) (p(x1, a), dc,t), and study the performance of the idealized sequence (ft, ū.) therein:
T
11
Rt
(uh - Rn.n,Fr.p))
h=1
Our first lemma bounds the above quantity:
Lemma 1. Suppose that Be, is such that In (p((,,)),00 0c.10 < 1 holds for all x, Then, the auxiliary regret satisfies
Ri
Σ
(P P,,)
1 - Do("" (ppo) a
While the proof makes use of a general potential-based argument commonly used for analyzing FTRL- style algorithms, it involves several nontrivial elements exploiting the structural results concerning ONLINE Q-REPS proved in Proposition]] I In particular, these properties enable us to upper bound the potential differences in particularly simple way. The main term on contributing to the regret Ry can be bounded as follows:
Lemma 2. Suppose that <p(X,,n; a) is satisfying [lsp(Xen,, a)ll, I for any a, 0 B <
20 (d(M+1) and M 0. Then for each and
E, [Pe, (.,)1] <
5d + (M + 1)a 1| u4,h
The proof of this claim makes heavy use of the fact that (Tr ((,)) = (ūe, Fi,)) which is ensured by the construction of the reward estimator fr.,. and the constraints on the feature covariance matrices
8

---

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. [ which eventually justifies
the higher complexity of our algorithm.
It remains relate the auxiliary regret to the actual regret. The main challenge is accounting for the mismatch between and Uz and the bias of fr, denoted as br, (2r, a) = E, (Fr, a)] - (2, a).
To address these issues, we observe that for any i, h. we have
(M TE,h) ((1 u + YPO Te, {(1 ue, + YA F(,A) + (1 7) (we, Re Me,))
2 E. [((1 - 7) u + 740, Fr,n)]
] + |6, + (1 7) Ilue - ūe,
where in the last step we used the fact that ||r,,ill.s I After straightforward algebraic manipula- tions, this implies that the regret can be bounded as
H
Ri S (1 - 11
Ri
E l7 (Mo, 1h, re,) + l we,nll + l
(8)
1=
In order to proceed, we need verify the condition In- (1p(2, a), Ocnii < 1 so that we can apply
Lemma to bound Ry. This is done in the following lemma:
Lemma Suppose that nl S "(M Then, for all, t, h, the reward estimates satisfy 7 11 < 1.
Proceeding under the condition (M + 1), we can apply Lemma tto bound the first term on right-hand side of Equation (8. giving
Ri S D( (1)o)
(c(w"|lpo) + (3 + 5d)nHT + +THT
7
Σ E [GT(M + 1)² 1) 1[te, - u. 1|bb,,lllo]]
It remains to bound the bias of the reward estimators and the effect of the optimization errors that result in the mismatch between U, and ūr The following lemma shows that this mismatch can be directly controlled as a function of the optimization emror:
Lemma 4. The following bound is satisfied for all t and h: 1 ue,i S 22a..
The final element in the proof is the following lemma that bounds the bias of the estimator:
Lemma 5. For M 2 0, 3 न we have [|br, ol S Rxeexp (-73Xmin M).
Putting these bounds together with the above derivations concludes the proof of Theorem 1
Discussion
This paper studies the problem of online learning MDPs, merging two important lines of work on this problem concerned with linear function approximation [17 ( and bandit feedback with adversarial rewards (23 25 33). 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. the tabular setting where d = [ 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 that of Cai et 7 who prove bounds of
order vd H which is worse by a factor of vdH 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 complete analysis of the propagation of optimization emrors incurred while performing the updates. This is indeed 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 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 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 al. [16], whose technique is based on adjusting the constraints (I) with 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-Bun 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.
References
[1] A. Agarwal, S. Kakade, A. Krishnamurthy, and W. Sun. FLAMBE: Structural complexity and representation learning of low rank MDPs. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[2] P. Auer and R. Ortner. Logarithmic online regret bounds for undiscounted reinforcement learning. B. Schölkopf, Platt, and T. Hoffman, editors, Advances in Neural Information Processing Systems, volume 19, pages 49-56. MIT Press, 2007.
[3] B. Awerbuch and R. D. Kleinberg. Adaptive routing with end-to-end feedback: distributed learning and geometric approaches. In STOC 2004, pages 45-53, 2004.
[4] M. G. Azar, I. Osband, and R. Munos. Minimax regret bounds for reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning, pages 263-272, 2017.
[5] J. Bas-Serrano, S. Curi, A. Krause, and G. Neu. Logistic Q-learning. In AI & Statistics, pages 3610-3618, 2021.
[6] A. N. Burnetas and M. N. Katchakis. Optimal adaptive policies for Markov Decision Processes. Mathematics of Operations Research, 22:122222- 1997.
[7] Q Cai, 7. Yang, C. Jin, and 7. Wang. Provably efficient exploration in policy optimization. arXiv e-prints, art. arXiv: 11XXvv199222 191.00580.. Dec. 2019.
[8] V. Dani, S. M. Kakade, and T. P. Hayes. The price of bandit information for online optimization.
In Advances in Neural Information Processing Systems 20, pages 345-352. 2008.
[9] C. Dann and Brunskill. Sample complexity of episodic fixed-horizon reinforcement learning.
In Advances in Neural Information Processing Systems, pages 28 318 2--222, 2015.
[10] C. Dann, T. Lattimore, and E. Brunskill. Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems 30, pages 5713-5723. 2017.
[11] T. Dick, A. György, and Cs. Szepesvári. Online learning in Markov decision processes with changing cost sequences. In International Conference on Machine Learning, pages 512-520, 2014.
[12] E. Even-Dar, S. M. Kakade, and Y. Mansour. Online Markov decision processes. Math. Oper. Res., 34(3):726-736 2009.
[13] R. Fruit, M. Pirotta, A. Lazaric, and R. Ortner. Efficient bias-span conntrcontt exploration- exploitation in reinforcement learning. In International Conference on Machine Learning, pages 1573-1581, 2018.
[14] T. Jaksch, R. Ortner, and Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 19:1563-1600, August 2010. ISSN 1532-4435.
[15] C. Jin, Z. Allen-Zhu, S. Bubeck, and M. I. Jordan. Is Q-learnig provably efficient? In Advances in Neural Information Processing Systems, pages 4863-4873, 2018.
[16] C. Jin, T. Jin, H. Luo, S. Sra, and T. Yu. Learning adversarial MDPs with bandit feedback and unknown transition. In International Conference on Machine Learning, 2020.
[17] C. Jin, Z. Yang, Z. Wang, and M. I. Jordan. Provably efficient reinforcement learning with linear function approximation. Proceedings of the 33rd Annual Conference on Learning Theory (COLT 2020), pages 2137-2143, 2020.
10

---

[18] H. B. McMahan and A. Blum. Online geometric optimization in the bandit setting against an adaptive adversary. COLT 2004, pages 109-123, 2004.
[19] G. Neu and G. Bartók. An efficient algorithm for learning with semi-bandit feedback. In Proceedings of the 24th International Conference on Algorithmic Learning Theory (ALT 2013), pages 234-248, 2013.
[20] G. Neu and G. Bartók. Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits. Journal of Machine Learning Research, 17:1-21, 2016.
[21] G. Neu and J. Olkhovskaya. Efficient and robust algorithms for adversarial linear contextual bandits. In Proceedings of the 33rd Annual Conference on Learning Theory (COL.T 2020), pages 3049-3068, 2020.
[22] G. Neu and C. Fike-Burke. A unifying view of optimism in episodic reinforcement learning, In Advances in Neural Information Processing Systems (NeurIPS). 2020.
[23] G. Neu, A. György, and Cs. Szepesvári. The online loop-free stochastic shortest-pate problem. In Proceedings of the 23rd Annual Conference on Learning Theory (COLT 20/0), pages 231-243, 2010.
[24] G. Neu, A. György, and Cs. Szepesvári. The adversarial stochastic shortest path problem with unknown transition probabilities. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, pages 805-813. 2012.
[25] G. Neu, A. György, Cs. Szepesvári, and A. Antos. Online Markov decision processes under bandit feedback. volume 59, pages 1804-1812, 01 2013. doi: 10. 10.11099TAC22003222211111..
[26] F. Orabona. A modern introduction online learning. arXiv preprint arXiv: /9/2. 132113 2019.
[27] A. Pacchiano, J. Lee, P. Bartlett, and O. Nachum. Near optimal policy optimization via REPS.
arXiv preprint wrXiv:2103.09733 2021.
[28] Peters, K. Mülling, and Altun, Relative entropy policy search. In AAAI 2010, pages 1607-1612, 2010. ISBN
[29] B. Á. Pires and Cs. Szepesvári. Policy error bounds for model-based reinforcement learning with factored linear models. In Conference Learning Theory, pages 121-151, 2016
[30] A. Rosenberg and Y. Mansour. Online convex optimization in adversarial Markov decision processes. In Proceedings of the 36th International Conference on Machine Learning, pages 5478-5486 2019.
[31] A. Tewari and P. L. Bartlett. Optimistic linear programming gives logarithmic regret for irreducible MDPs. In Advances Neural Information Processing Systems 20, pages 1505- 1512.
[32] C.-Y. Wei, M. Jafarnia Jahromi, H. Luo, and R. Jain, Learning infinite-horizon average-reward MDPs with linear function approximation. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, pages 3007-3015, 2021.
[33] L. F. Yang and M. Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In Proceedings of the 36th International Conference Machine Learning, 2020.
[34] H. Yao, Cs. Szepesvári, B. Pires, and X. Zhang. Pseudo-MDPP and factored linear action models. 10 2014. doi: 10.110/// 7.100633.
[35] A. Zimin and G. Neu. Online learning in episodic markovian decision processes by relative entropy policy search. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q Weinberger, editors, Advances in Neural Information Processing Systems 26, pages 1583-1591. Curran Associates, Inc., 2013.
11


Reviews:
[{"review_id": "xV_5KLSxcr6", "reviewer": "Reviewer_9trB", "summary": "The authors study the adversarial linear bandit problem under bandit feedback. When the dynamics is known, the authors propose a computationally efficient algorithm to achieve low regret.", "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": "I have read an earlier version of this paper, where the authors assume access to a simulator to conduct matrix geometric resampling without assuming known dynamics. Although assuming knowing the dynamics sounds weaker, I actually like the new version since the assumption is clear and more reasonable -- Actually, I think assuming a simulator in an online problem with adversarial reward sounds super wired. Also I think authors may want to add more discussion to highlight the improvement in the new version, which would be very helpful for reviewers like me.\n\nI have some other comments:\n \n1. When assuming the known dynamics, in principle we can compute the \"covariance matrix\" explicitly. The authors claim this is hard. They may want to add some explanation to at least convince the reader this is hard, which is not clear to me at first glance. This will also highlight the significance of the resampling procedure.\n\n2. When finding Z_t, a minimization problem (6) needs to be solved. It would be great if the authors can add some intuition in the main text why this can be done in a computationally efficient manner. In particular, since it contains a summation of S terms and S could be very large, why the overall complexity only depends on d?\n\n3. The decision variable used is a pair (mu,u). Why using this pair is superior to only using mu? Since both of them are constrained by some linear constraints, I can't see intuitively this is the case.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed them.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "hID-IS6Utqr", "reviewer": "Reviewer_a6uC", "summary": "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.", "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": "Overall, I think this is a good paper. It is very well-written and tackles an interesting open problem in the field. The related work and introduction are detailed and comprehensive and do a good job of making the contributions of the paper clear. The assumptions are repeatedly described. The regret bound is interesting and significant in that the authors show that sqrt{dHT} regret is possible in this difficult setting. Although the proposed method combines ideas from several prior works, I do not think that this is necessarily bad and it does not seem to detract from the quality of the result.\n\nAs the authors point out, the main limitation is that the results apply only in the case where the transition function is exactly known and it is not clear how this might extend beyond. That being said, I still think this setting is important to understand.\n\nThe other limitation is that the regret bound depends on the divergence between the initial and optimal distributions, which I do not think is always needed in tabular cases, so this would be interesting to address in future work. It is pointed out that the bound has no dependence on the minimum eigenvalue, but I actually think this would be preferable to the divergence since the latter is asking for something akin to “good coverage” which is immutable in the problem while the former is asking only for a good model, which could be chosen by a practitioner even without good coverage.\n\nOther questions & suggestions:\n\nWhile it is not strictly necessary, I think that the result of Theorem 1 would feel more complete if one could see exactly the effect of the optimization error of solving G, for example, in terms of samples as described in Appendix C. Right now there is an epsilon that represents this in the main theorem. However, since a great deal of the motivation is tractability, perhaps a corollary would be helpful even though this would just be a simple calculation.\n\nIn Lemma 8 in the appendix, doesn’t one need a uniform convergence guarantee since the goal is to minimize over \\hat{G}? The statement looks like it holds only for a single Z, but the proof seems to handle it more generally. Also, when can one expect that Delta is bounded? \n\nIs there anything wrong with simply plugging the optimization problem (5) into an off-the-shelf solver if one were to implement this practically instead of solving the unconstrained optimization problem? It is my understanding that many solves can handle relative entropy objectives and the constraints seem tame enough. There is some discussion already about it potentially being intractable, but in what way is this the case? Too many states/actions? or something inherent about objective/constraints?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review for limitations and suggestions.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "PudXhFFbeKY", "reviewer": "Reviewer_LP1g", "summary": "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.", "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": "The paper is mostly well written and presents the solution to a problem relatively unexplored in the literature: online learning in MDPs with adversarial rewards over infinite/continuous state spaces. The presentation of the method is mostly rigorous in its mathematical formulations with clear theoretical justifications. However, the paper still has a few remaining clarity issues, which I elaborate below.\n\nIssues:\n- The first half of the introduction lacks citations/references to back up some of the claims (e.g., lines 21 and 24).\n- The second half of the introduction (line 41 onwards) could be labelled as a \"related work\" section to better structure the paper.\n- $K$ is introduced without prior definition in line 52.\n- The notation $\\tilde{O}$ is not defined, though it's commonly applied to indicate suppression of log-factors in the big-$O$ notation.\n- In the preliminaries section, the reward function is first introduced as if it was stationary (see line 97), but it is later on considered to be varying across time step and episode.\n- It is not totally clear whether the algorithm can achieve a vanishing regret as $T \\to \\infty$, since this would imply that both $\\eta \\to 0$ and $\\alpha\\to 0$, i.e., the optimisation problem in Theorem 1 would have to be solved up to arbitrary precision. Could the authors comment on that?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are discussed in Sec. 5. Societal impact is not directly applicable, as this is a purely theoretical work.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "6LZeRpoq2A", "reviewer": "Reviewer_hYYK", "summary": "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. ", "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": "Although the strong assumption on the known transition kernel simplifies the problem a lot, the setting of adversarial bandit linear MDP has not been studied before, and the authors propose an interesting algorithm to tackle it. I like the fact that the authors make the algorithm as transparent as possible by detailing every sub-procedure e.g. Matrix Geometric Resampling and how to solve the convex programming using gradient descent. However, I suspect that there is some mis-presentation in the main result, as I pointed out below. I would like to see authors address it in the rebuttal (either modifying the algorithm, or weakening the claimed bounds). \n\nAs I can see, the regret bound should actually scale with $\\sqrt{\\frac{T}{\\lambda_{\\min}}}$, but not the $\\sqrt{T}$ given in Theorem 1. The reason is that in Lemma 1, it is required that $\\eta$ is smaller than the order of $\\frac{1}{\\beta M}$ (because the magnitude of $\\widehat{\\theta}$ can be as large as $\\beta M$). A similar condition (i.e., $\\eta\\leq \\frac{2}{(M+2)H}$) is also specified in Theorem 1. Then the $\\frac{1}{\\eta}D(\\mu^*\\|\\mu_0)$ will scale at least with $\\beta M$. Now in order to make the first regret term $2T\\sigma RH\\exp(-\\gamma \\beta\\lambda_{\\min}M)$ sublinear, one must pick $M=\\Omega\\left(\\frac{1}{\\gamma\\beta\\lambda_{\\min}}\\right)$. So the regret term $\\beta M$ is at least $\\Omega\\left(\\frac{1}{\\gamma \\lambda_{\\min}}\\right)$. Further considering another regret term $\\gamma HT$, the regret will scale at least with $\\sqrt{\\frac{T}{\\lambda_{\\min}}}$. \n\nIn practice the learner has no way to know $\\lambda_{\\min}$ and set $M$ and $\\epsilon$ properly.  The authors should discuss how the algorithm works when $\\lambda_{\\min}$ is unknown. \n\n\n========== after the discussion phase ==========\n\nThe authors agreed to write their bound in the clearer form of $\\sqrt{\\frac{T}{\\lambda_{\\min}}}$, and discuss the difficulties of removing $\\lambda_{\\min}$ assumption in the MDP setting.  These make the paper more complete, so I slightly raised my score.  \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The assumption on $\\lambda_{\\min}$ and the related statistical or computational issue are not emphasized or discussed in detail. It should be more emphasized in e.g. introduction section. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Several reviewers increased their scores after the discussion phase.
Overall, we agree that this paper makes solid contribution to the direction of online learning MDPs.
Please do implement the promised revisions, especially those related to the discussion with Reviewer hYYK. 

Decision: Accept (Poster)