summaries: The paper studies the performance of the classic Relative Entropy Policy Search (REPS) algorithm of Peters et al. (2010) in the context of tabular reinforcement learning, focusing on the effect of optimization errors on the quality of the policy extracted from the solution. REPS is based on formulating the policy optimization problem as a regularized linear optimization problem which is equivalent to an unconstrained convex optimization problem, and calculating policy updates via approximately minimizing the dual function. The current paper sets out to understand the optimization issues surrounding solving these problems, and provides the following contributions:  - Showing that the policy suboptimality can be controlled in terms of the gradient norm associated with the approximate solution and some problem-dependent constants. - Showing that the dual REPS objective is smooth, which implies that bounds on the additive optimization errors can be translated to bounds on the gradient norm at the approximate solution. - Providing concrete performance bounds for an accelerated gradient descent method when the gradients of the objective can be evaluated exactly. This setting is rather unrealistic, but the results are insightful in that they shed light on the best attainable performance to be expected from this approach.  - Providing concrete performance bounds for a stochastic gradient descent method that uses a generative model to obtain estimates of the gradients. The challenge here is that one cannot straightforwardly obtain unbiased gradient estimates, and one has to take several sample transitions to make sure that the bias in the updates is small enough. The authors address this challenge thoroughly and obtain guarantees that are polynomial in the desired accuracy level. The paper studies the convergence of the relative entropy policy search (REPS) method for solving LP-formulated MDP problems. The authors first assume the exact computation of gradients and prove the sublinear convergence of REPS regarding the regularized primal objective function and the policy. Second, the authors propose to estimate gradients using samples and prove the convergence or sample-complexity of sample-based REPS.  The main contribution is a convergence theory of REPS in both exact and stochastic settings.  In this paper the authors the sample complexity of the relative entropy policy search (REPS). This algorithm aims at finding the optimal policy in an MDP using linear programming formulation. First the authors consider the planning setting where they assume access to the exact model of the environment. For this result they show that near stationary policies result in a near optimal policy. Next they provide the convergence when the updates are being performed by biased stochastic gradients.  This paper goes back to a well known algorithm, Relative Entropy Policy Search (REPS) and provides convergence guarantees for REPS by exploiting its relationship of RL via duality. Recently, there has been a surge of work exploiting the dual formulation of RL objectives, and this paper exploits that relation to performance convergence analysis of the REPS algorithm. Besides, very recently, a number of works has provided convergence of policy search and policy gradient algorithms - and the contributions of this work can be seen in light of recent works. The major contributoon of this work is to provide convergence guarantees for the dual objective of REPS, relying solely on on-policy samples and using accelerated gradient ascent on the dual formulation (whereas prior works exploiting duality often need to rely on off-policy samples, estimating distribution ratios).  
abstractText: Since its introduction a decade ago, relative entropy policy search (REPS) has demonstrated successful policy learning on a number of simulated and real-world robotic domains, not to mention providing algorithmic components used by many recently proposed reinforcement learning (RL) algorithms. While REPS is wellknown in the community, there exist no guarantees on its performance when using stochastic, gradient-based solvers. In this paper we aim to fill this gap by providing guarantees and convergence rates for the sub-optimality of a policy learned using first-order optimization methods applied to the REPS objective. We first consider the setting in which we are given access to exact gradients and demonstrate how near-optimality of the objective translates to near-optimality of the policy. We then consider the setting of stochastic gradients and introduce a technique that uses generative access to the underlying Markov decision process to compute parameter updates that maintain favorable convergence to the optimal regularized policy.
authors.name: Aldo Pacchiano
authors.name: Jonathan Lee
authors.name: Peter L. Bartlett
references.authors: A. Abdolmaleki R. Lioutikov J.R. Peters N. Lau L.P. Reis G. Neumann
references.title: Modelbased relative entropy stochastic search
references.venue: In Advances in Neural Information Processing Systems,
references.authors: A. Abdolmaleki J.T. Springenberg Y. Tassa R. Munos N. Heess M. Riedmiller
references.title: Maximum a posteriori policy optimisation
references.venue: arXiv preprint arXiv:1806.06920,
references.authors: Z. Allen-Zhu L. Orecchia
references.title: Linear coupling: An ultimate unification of gradient and mirror descent
references.venue: arXiv preprint arXiv:1407.1537,
references.authors: J. Bas-Serrano G. Neu
references.title: Faster saddle-point optimization for solving large-scale markov decision processes
references.venue: arXiv preprint arXiv:1909.10904,
references.authors: A. Beck M. Teboulle
references.title: Mirror descent and nonlinear projected subgradient methods for convex optimization
references.venue: Operations Research Letters,
references.authors: B. Belousov J. Peters
references.title: f-divergence constrained policy improvement
references.venue: arXiv preprint arXiv:1801.00056,
references.authors: A. Boularias J. Kober J. Peters
references.title: Relative entropy inverse reinforcement learning
references.venue: In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics,
references.authors: Y. Chen M. Wang
references.title: Stochastic primal-dual methods and sample complexity of reinforcement learning
references.venue: arXiv preprint arXiv:1612.02516,
references.authors: Y. Chen L. Li M. Wang
references.title: Scalable bilinear ⇡ learning using state and action features
references.venue: arXiv preprint arXiv:1804.10328,
references.authors: Cheng C.-A R.T. Combes B. Boots G. Gordon
references.title: A reduction from reinforcement learning to no-regret online learning
references.venue: In International Conference on Artificial Intelligence and Statistics,
references.authors: C. Daniel G. Neumann J. Peters
references.title: Hierarchical relative entropy policy search
references.venue: In Artificial Intelligence and Statistics,
references.authors: R. Fox A. Pakman N. Tishby
references.title: Taming the noise in reinforcement learning via soft updates, 2017
references.authors: M. Geist B. Scherrer O. Pietquin
references.title: A theory of regularized markov decision processes
references.venue: arXiv preprint arXiv:1901.11275,
references.authors: T. Haarnoja A. Zhou K. Hartikainen G. Tucker S. Ha J. Tan V. Kumar H. Zhu A. Gupta P Abbeel
references.title: Soft actor-critic algorithms and applications
references.venue: arXiv preprint arXiv:1812.05905,
references.authors: S.R. Howard A. Ramdas J. McAuliffe J. Sekhon
references.title: Uniform, nonparametric, nonasymptotic confidence sequences
references.venue: arXiv preprint arXiv:1810.08240,
references.authors: Y. Jin A. Sidford
references.title: Efficiently solving mdps with stochastic mirror descent
references.venue: In International Conference on Machine Learning,
references.authors: I. Kostrikov O. Nachum J. Tompson
references.title: Imitation learning via off-policy distribution matching, 2019
references.authors: O. Nachum B. Dai
references.title: Reinforcement learning via fenchel-rockafellar duality
references.venue: arXiv preprint arXiv:2001.01866,
references.authors: O. Nachum M. Norouzi K. Xu D. Schuurmans
references.title: Bridging the gap between value and policy based reinforcement learning
references.venue: In Advances in Neural Information Processing Systems,
references.authors: O. Nachum B. Dai I. Kostrikov Y. Chow L. Li D. Schuurmans
references.title: Algaedice: Policy gradient from arbitrary experience, 2019
references.authors: G. Neu A. Jonsson V. Gómez
references.title: A unified view of entropy-regularized markov decision processes
references.venue: arXiv preprint arXiv:1705.07798,
references.authors: J. Peters K. Mülling Y. Altun
references.title: Relative entropy policy search
references.venue: In AAAI,
references.authors: M.L. Puterman
references.title: Markov decision processes: discrete stochastic dynamic programming
references.authors: J. Schulman S. Levine P. Abbeel M. Jordan P. Moritz
references.title: Trust region policy optimization
references.venue: In International conference on machine learning,
references.authors: N. Vieillard T. Kozuno B. Scherrer O. Pietquin R. Munos M. Geist
references.title: Leverage the average: an analysis of regularization in rl
references.venue: arXiv preprint arXiv:2003.14089,
references.authors: M. Wang
references.title: Primal-dual ⇡ learning: Sample complexity and sublinear run time for ergodic markov decision problems
references.venue: arXiv preprint arXiv:1710.06100,
references.authors: M. Wang
references.title: Randomized linear programming solves the discounted markov decision problem in nearly-linear (sometimes sublinear) running time
references.venue: arXiv preprint arXiv:1704.01869,
sections.heading: 1 Introduction
sections.text: Introduced by Peters et al. [23], relative entropy policy search (REPS) is an algorithm for learning agent policies in a reinforcement learning (RL) context. REPS has demonstrated successful policy learning in a variety of challenging simulated and real-world robotic tasks, encompassing table tennis [23], tether ball [12], beer pong [1], and ball-in-a-cup [8], among others. Beyond these direct applications of REPS, the mathematical tools and algorithmic components underlying REPS have inspired and been utilized as a foundation for a number of later algorithms, with their own collection of practical successes [13, 25, 20, 22, 15, 2, 18, 21].
  At its core, the REPS algorithm is derived via an application of convex duality [22, 19], in which a Kullback Leibler (KL)-regularized version of the max-return objective in terms of state-action distributions is transformed into an logsumexp objective in terms of state-action advantages (i.e., the difference of the value of the state-action pair compared to the value of the state alone, with respect to some learned state value function). If this dual objective is optimized, then the optimal policy of the original primal problem may be derived as a softmax of the state-action advantages. This basic derivation may be generalized, using any number of entropic regularizers on the original primal to yield a dual problem in the form of a convex function of advantages, whose optimal values may be transformed back to optimal regularized policies [7].
  While the motivation for the REPS objective through the lens of convex duality is attractive, it leaves two main questions unanswered regarding the theoretical soundness of using such an approach. First, in practice, the dual objective in terms of advantages is likely not optimized fully. Rather, standard gradient-based solvers only provide guarantees on the near-optimality of a returned candidate solution. While convex duality asserts a relationship between primal and dual variables at the exact optimum,
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  it is far from clear whether a near-optimal dual solution will be guaranteed to yield a near-optimal primal solution, and this is further complicated by the fact that the primal candidate solution must be transformed to yield an agent policy.
  The second of the two main practical difficulties is due to the form of the dual objective. Specifically, the form of the dual objective as a convex function of advantages frustrates the use of gradient-based solvers in stochastic settings. That is, the advantage of a state-action pair consists of an expectation over next states – an expectation over the transition function associated with the underlying Markov decision process (MDP). In practical settings, one does not have explicit knowledge of this transition function. Rather, one only has access to stochastic samples from this transition function, and so calculation of unbiased gradients of the REPS objective is not directly feasible.
  In this paper, we provide solutions to these two main difficulties. To the first issue, we present guarantees on the near-optimality of a derived policy from dual variables optimized via a first-order gradient method, relying on a key property of the REPS objective that ensures near-optimality in terms of gradient norms. To the second issue, we propose and analyze a stochastic gradient descent procedure that makes use of a plug-in estimator of the REPS gradients. Under some mild assumptions on the MDP, our estimators need only sample transitions from a behavior policy rather than full access to a generative model (where one can uniformly sample transitions). We combine these results to yield high-probability convergence rates of REPS to a near-optimal policy. In this way, we show that REPS enjoys not only favorable practical performance but also strong theoretical guarantees.
sections.heading: 2 Related Work
sections.text: As REPS is a popular and influential work, there exist a number of previous papers that have studied its performance guarantees. These previous works predominantly study REPS as an iterative algorithm, where each step comprises of an exact optimization of the REPS objective and then the derived policy is used as the reference distribution for the KL regularization of the next step. This iterative scheme may be interpreted as a form of mirror descent or similar proximal algorithms [6], and this interpretation can provide guarantees on convergence to a near-optimal policy [29, 22]. However, because this approach assumes the ability to optimize the REPS objective exactly, it still suffers from the practical limitations discussed above; specifically (1) translation of near-optimality of advantages to near-optimality of the policy and (2) ability to compute unbiased gradients when one does not have explicit knowledge of the MDP dynamics. Our analysis attacks these issues head-on, providing guarantees on first-order optimization methods applied to the REPS objective. To maintain focus we do not consider iterative application of REPS, although extending our guarantees to the iterative setting is a promising direction for future research.
  In a somewhat related vein, a number of works use REPS-inspired derivations to yield dynamic programming algorithms [13, 14, 26] and subsequently provide guarantees on the convergence of approximate dynamic programming in these settings. Our results focus on the use of REPS in a convex programming context, and optimizing these programs via standard gradient-based solvers.
  The use of convex programming for RL in this way has recently received considerable interest. Works in this area typically propose to learn near-optimal policies through saddle-point optimization [9, 28, 10, 4, 11, 17]. Instead of solving the primal or dual max-return problem directly, these works optimize the Lagrangian in the form of a min-max bilinear problem. The Lagrangian form helps to mitigate the two main issues we identify with advantage learning, since (1) the candidate primal solution can be used to derive a policy in a significantly more direct fashion than using the candidate dual solution, and (2) the bilinear form of the Lagrangian is immediately amenable to stochastic gradient computation. In contrast to these works, our analysis focuses on learning exclusively in the dual (advantage) space. The first part of our results is most comparable to the work of [4], which proposes a saddle-point optimization with runtime O(1/✏), assuming access to known dynamics. While our results yield a O(1/✏2) rate, we show that it can be achieved via optimizing the dual objective alone.
  More similar to our work is the analysis of Bas-Serrano et al. [5], which considers an objective similar to REPS, but which is in terms of Q-values as opposed to state (V ) values. Beyond these structural differences, our proof techniques also differ. For example, our result on the suboptimality of the policy derived from dual variables (Lemma 4), is arguably simpler from the analogous result in Bas-Serrano et al. [5], which uses a two-step process to first connect suboptimality of the dual variables to constraint violation in the primal, and then connects this to suboptimality of the policy.
sections.heading: 3 Contributions
sections.text: The main contributions of this paper are the following:
  1. We prove several structural results regarding entropy regularized objectives for reinforcement learning and leverage them to prove convergence guarantees for Accelerated Gradient Descent on the dual (REPS) objective under mild assumptions on the MDP (see Theorem 2). For discounted MDPs we show that an ✏-optimal policy can be found after O(1/(1 )2✏2) steps and an ✏ optimal regularized policy can be found in O(1/(1 )2✏) steps.
  2. Similarly we show that a simple version of stochastic gradient descent using biased plug-in gradient estimators can be used to find an ✏ optimal policy after O(1/(1 )8✏8) iterations (see Theorem 3) and an ✏-optimal regularized policy in O(1/(1 )8✏4) steps. Although our rates are short of the ones achievable by alternating optimization methods, we are the first to show meaningful convergence guarantees for a purely dual approach based on on-policy access to samples from the underlying MDP.
  3. In Appendix I, we extend our results beyond the REPS objective and consider the use of Tsallis Entropy regularizers. Similar to our results for the REPS objective we show that for discounted MDPs an ✏ optimal policy can be found after O(1/(1 )2✏2) steps and an ✏ optimal regularized policy can be found in O(1/(1 )2✏) steps.
sections.heading: 4 Background
sections.text: In this section we review the basics of Markov decision processes and their Linear Programming primal and dual formulations (see section 4.1) and some facts about the geometry of convex functions.
sections.heading: 4.1 RL as an LP
sections.text: We consider a discounted Markov decision process (MDP) described by a tuple M = (S,A, P, r,µ, ), where S is a finite state space, A is a finite action space, P is a transition probability matrix, r is a reward vector, µ is an initial state distribution, and 2 (0, 1) is a discount factor. We make the following assumption regarding the reward values {rs,a}. Assumption 1 (Unit rewards). For all s, a 2 S ⇥A, the rewards satisfy, rs,a 2 [0, 1].
  The agent interacts with M via a policy ⇡ : S ! A. The agent is initialized at a state s0 sampled from an initial state distribution µ and at time k = 0, 1, . . . it uses its policy to sample an action ak ⇠ ⇡(sk). The MDP provides an immediate reward rsk,ak and transitions randomly to a next state sk+1 according to probabilities Pa(sk+1|sk). Given a policy ⇡ we define its infinite-horizon discounted reward as V⇡ := E⇡ ⇥P1 k=0 krsk,ak ⇤ , where we use E⇡ to denote the expectation over trajectories induced by the MDP M and policy ⇡. In RL, the agent’s objective is to find an optimal policy ⇡?; that is, find a policy maximizing V⇡ over all policy mappings ⇡ : S ! A. We denote the optimal policy as ⇡? := argmax⇡ V⇡ .
  We now review the definitions of state value functions and visitation distributions: Definition 1. We define the value vector v⇡ 2 R|S| of a policy ⇡ as v⇡s := E⇡ ⇥P1
  k=0 k rsk,ak |s0 = s
  ⇤ .
  Definition 2. Given a policy ⇡ we define its state-action visitation distribution ⇡ 2 R|S|⇥|A| as, ⇡s,a := (1 )E⇡ ⇥P1 k=0 k1(sk = s, ak = a) ⇤ . Notice that by definition P s,a s,a = 1.
  We note that any vector of nonnegative entries may be used to define a policy ⇡ as:
  ⇡ (a|s) := s,aP
  a02A s,a0 . (1)
  Note that ⇡ ⇡ = ⇡, while the visitation distribution ⇡ of ⇡ is not necessarily . Definition 3. Given a policy ⇡ we define its state visitation distribution as, ⇡s := (1 )E⇡ ⇥P1 k=0 k1(sk = s) ⇤ . Notice that ⇡s = P a ⇡ s,a and ⇡ s,a = ⇡ s · ⇡(a|s).
  The optimal visitation distribution ⇤ is defined as ⇤ := argmax ⇡ P
  s,a ⇡ s,ars,a. It can be
  shown [24, 9] that solving for the optimal visitation distribution is equivalent to the following linear program:
  max s,a2 S⇥A
  X
  s,a
  s,ars,a, s.t. X
  a
  s,a = (1 )µs + X
  s0,a
  Pa(s|s0) s0,a 8s 2 S. (Primal- )
  Where we write P 2 R|S||A|⇥|S| to denote the transition operator. Specifically, the |S| constraints of Primal- restrict any feasible to be the state-action visitations for some policy ⇡ (given by ⇡ ). The dual of this LP is given by,
  min v
  (1 ) X
  s2S µsvs, s.t. 0 A v s,a 8s 2 S, a 2 A, (Dual-v)
  where Avs,a = rs,a vs + P s0 Pa(s 0 |s)vs0 is the advantage evaluated at s, a 2 S ⇥A. It can be shown [24, 9] that the unique primal solution ⇤ is exactly ⇡⇤ and the unique dual solution v⇤ is v⇡⇤ .
  We finalize this section by defining the notion of suboptimality satisfied by the final policy produced by the algorithms that we propose. Definition 4. Let ✏ > 0. We say that policy ⇡ is ✏-optimal if maxs2S |v⇡s v⇡?s |  ✏.
  Our objective is to design algorithms such that for any ✏ > 0, can return an ✏ optimal policy.
sections.heading: 4.2 Regularized Policy Search
sections.text: Following Belousov & Peters [7], we consider regularizing Primal- with a convex function F : |S|⇥|A| ! R [ {1}. The resulting regularized LP is given by,
  max s,a2 S⇥A
  X
  s,a
  s,ars,a F ( ) := JP ( ), s.t. X
  a
  s,a = (1 )µs + X
  s0,a
  Pa(s|s 0) s0,a.
  (PrimalReg- ) Henceforth we denote the primal objective function as JP ( ) = P s,a s,ars,a F ( ). Any feasible
  that satisfies the |S| constraints in this regularized LP is the (true) state-action visitation distribution for some policy ⇡; therefore, the optimal ⇤ of this problem can be used to derive an optimal F - regularized max-return policy ⇡F,⇤ := ⇡ ⇤ . To simplify our derivations, we introduce the definition of the convex conjugate of a convex function, oftentimes referred to as the Fenchel conjugate: Definition 5 (Fenchel Conjugate). Let F : D ! R be a convex function over a convex domain D ✓ Rd. We denote its D constrained Fenchel conjugate as F ⇤ : Rn ! R defined as F ⇤(u) = maxx2D hx,ui F (x).
  The dual JD of the regularized problem is given by the following optimization problem [7, 19]:
  min v
  JD(v) := (1 ) X
  s
  vsµs + F ⇤ (Av) , (2)
  where F ⇤ is the S⇥A-constrained Fenchel conjugate of F . The vector quantity inside F ⇤ is known as the advantage. That is, it quantifies the advantage (the difference in estimated value) of taking an action a at s, with respect to some state value function v. Using Fenchel-Rockafellar duality, the optimal solution v⇤ of the dual function JD may be used to derive an optimal primal solution ⇤ as:
  ⇤ 2 rF ⇤ ⇣ Av ? ⌘ . (3)
  Algorithm 1 Relative Entropy Policy Search [Sketch]. Input: Initial iterate v0, accuracy level ✏ > 0, gradient optimization algorithm O.
  1. Optimize the objective in 2 using O to yield a candidate dual solution v̂⇤ where F satisfies Equation 4.
  2. Use the candidate dual solution to derive a candidate primal solution ̂ ⇤ using 3.
  3. Extract a candidate policy ⇡̂⇤ from ̂ ⇤
  via Equation 1. Return: ⇡̂⇤ .
  Relative Entropy Policy Search (REPS) is derived by setting F ( ) := DKL( kq), the KL-divergence of from some reference distribution q 2 |S||A|. The reader should think of q as the visitation distribution of a behavior policy. As we can see, the derivation we provide here further generalizes to arbitrary regularizers F . We focus on a specific F given by
  F ( ) := 1
  ⌘
  X
  s,a
  s,a
  ✓ log ✓ s,a qs,a ◆ 1 ◆ , (4)
  for some scalar ⌘ > 0. In this case F ⇤ : R|S|⇥|A| ! R equals F ⇤(u) = 1 ⌘ log ⇣P s,a exp (⌘us,a)qs,a ⌘ + 1⌘ , its gradient satisfies [rF ⇤(u)]s,a = exp(⌘us,a)qs,aP
  s0,a0 exp(⌘us0,a0 )qs0,a0
  and therefore the dual function equals:
  JD(v) := (1 ) X
  s
  vsµs + 1
  ⌘ log
  X
  s,a
  exp ⌘Avs,a qs,a
  ! + 1
  ⌘ , (DualReg-v)
  And the dual problem equals the unconstrained minimization problem:
  min v JD(v) (5)
  The objective of REPS is to find the minimizer v? of DualReg-v (with regularization level ⌘).
  Algorithm 1 raises two practical issues discussed in Section 1. Specifically, optimization algorithms applied to REPS will typically only give guarantees on the near-optimality of v̂⇤. We will need to translate near-optimality of v̂⇤ to near-primal-optimality (w.r.t. JP ( ?)) of ̂ ⇤ , and then translate that to near-optimality of the final returned policy ⇡̂⇤ . Secondly, first-order optimization of the REPS objective requires access to a gradientrvJD(v), which involved computingrF ⇤(Av). Exact computation of this quantity is often infeasible in practical scenarios where one does not have access to P, but rather only stochastic generative access to samples from P. We show how to compute approximate (biased) gradients of JD(v) using samples from a distribution qs,a (here thought of as a behavior policy) and how to use them to derive convergence rates for Relative Entropy Policy Search.
sections.heading: 5 Relative Entropy Policy Search
sections.text: We start by deriving some general results regarding the geometry of regularized linear programs. Our first result (Lemma 2) characterizes the smoothness properties of a regularized LP. This will prove crucial in later sections where we make use of this result to derive convergence rates for the REPS objective. We start by recalling the definitions of both strong convexity and smoothness of a function.
  Definition 6. A function f : Rn ! R is strongly convex w.r.t norm k · k if f(x) f(y) + hrf(y),x yi+ 2 kx yk 2.
  Let’s also define smoothness: Definition 7. A function h is ↵ smooth1 w.r.t. norm k · k? if:
  h(u)  h(w) + hrh(w),u wi+ ↵
  2 ku wk2?. (6)
  We will now characterize the smoothness properties of the dual of a regularized linear program. Let’s start by considering the generic linear program:
  max 2D hr, i, s.t. E = b,
  where r 2 Rn, E 2 Rm⇥n, and b 2 Rm and D is a convex domain. Let’s regularize this objective using a function F that is -strongly convex with respect to norm k · k:
  max 2D hr, i F ( ), s.t. E = b. (RegLP)
  1Smoothness is independent of the convexity properties of h.
  The Lagrangian of problem RegLP is given by gL( ,v) = hr, i F ( )+ Pm
  i=1 vi (bi (E )i) . Therefore, the dual function gD : Rm ! R with respect to the original primal regularized LP is,
  gD(v) = hv,bi+max 2D h , r v>Ei F ( ) = hv,bi+ F ⇤(r v>E),
  where the last equality follows from the definition of the Fenchel conjugate of F . It is possible to relate the smoothness properties of F ⇤ with the strong convexity of F . A crucial result that we will use in our results is the following: Lemma 1. If F is -strongly convex w.r.t. k · k over D then F ⇤ is 1 -smooth w.r.t the dual k · k?.
  Definitions 6 and 7 are stated in terms of a generic norm k · k and its dual k · k?. When applied to the REPS objective in Equation 2, using these general norm definitions of smoothness and strong convexity allow us to obtain guarantees with a milder dependence on S and A than would be possible if we were to use their `2 norm characterization instead. We can use the result of Lemma 1 to characterize the smoothness properties of the dual function JD of a generic regularized LP. Lemma 2. Consider the regularized LP RegLP with r 2 Rn, E 2 Rm⇥n, b 2 Rm, and where F is strongly convex w.r.t. norm k · k. The dual function gD : Rm ! R of this regularized LP is kEk2·,? -smooth w.r.t. to the dual norm k · k?, where we use kEk·,? to denote the k · k norm over the k · k? norm of E0s rows.
  As a consequence of Lemma 2 we can bound the smoothness parameter of JD in the REPS objective: Lemma 3. The dual function JD(v) is (|S|+ 1)⌘-smooth in the k · k1 norm.
sections.heading: 5.1 Structural results for the REPS objective
sections.text: Armed with Lemma 2 we are ready to derive some useful structural properties of the REPS objective. In this section we present two main results. First we show that under some mild assumptions it is possible to relate the gradient magnitude of any candidate solution to JD with its suboptimality gap and second, we show an l1 bound for the norm of the optimal dual solution v?. For most of the analysis we make the following assumptions: Assumption 2. There is > 0 such that qs,a 8s, a 2 S ⇥A.
  We introduce the following assumption on the discounted state visitation distribution of arbitrary policies ⇡ in the MDP, paraphrased from Wang [27]: Assumption 3. There exists ⇢ > 0 such that for any policy ⇡, the discounted state visitation distribution ⇡ defined as ⇡s = P a ⇡ s,a satisfies ⇡ s ⇢ for all states s 2 S .
  Suppose we have a candidate dual solution ev forJD(v) in DualReg-v with its corresponding candidate primal solution e = exp(⌘A
  ṽ)·q eZ
  where the operators exp and · act pointwise and eZ = P a,s exp(⌘A
  ṽ)qs,a. We denote the corresponding candidate policy (computed using Equation 1) associated with ev as e⇡(a|s). This candidate policy induces a discounted visitation distribution e⇡ that may be substantially different from e . We now show that it is possible to control the deviation of primal objective value of e⇡ from JP ( ) in terms of krJD(ev)k1: Lemma 4. Let ev 2 R|S| be arbitrary and let e be its corresponding candidate primal variable. If krvJD(ev)k1  ✏ and Assumptions 2 and 3 hold then whenever |S| 2:
  JP ( e⇡) JP ( ? ⌘) ✏
  ✓ 1 + c
  1 + kevk1
  ◆ ,
  where c = 1+log( 1 ⇢3 )
  ⌘ and ? ⌘ is the JP optimum.
  We finish this section by proving a bound on the norm of the dual variables. This bound will inform our optimization algorithms as it will allow us to set up the right constraints. Lemma 5. Under Assumptions 1, 2 and 3, the optimal dual variables are bounded as
  kv⇤k1  1
  1
  1 + log |S||A| ⇢ ⌘
  ! =: D. (7)
  From now on we use the notation D to refer to the quantity on the RHS of Equation 7.
sections.heading: 5.2 Convergence rates
sections.text: As a warm up we derive convergence rates for the case when we have access to exact knowledge of the transition dynamics P and therefore exact gradients. We analyze the effects of using Accelerated Gradient Descent (see Section F for a full description of the algorithm) on the REPS objective JD(v). Theorem 1 (Accelerated Gradient Descent for general norms. Theorem 4.1 in Allen-Zhu & Orecchia [3]). Let D? be an upper bound to kx0,x?k22. Given an ↵ smooth function h w.r.t. the k · k? norm over domain D, then T iterations of Algorithm 4 ensure h(yt) h(x?)  4↵D⇤T 2 .
  We want to find almost optimal solutions (in function value). Let’s define an ✏ optimal solution: Definition 8. Let ✏ > 0. We say that x is an ✏ optimal solution of an ↵ smooth function h : Rd ! R if h(x) h(x?)  ✏, where h(x?) = minx2Rd h(x).
  We can also show the following bound on the gradient norm for any ✏ optimal solutions of h. Lemma 6. If x is an ✏ optimal solution for the ↵ smooth function h : Rd ! R w.r.t. norm k · k? then the gradient of h at x satisfies krh(x)k  p 2↵✏.
  When h = JD the DualReg-v function in the reinforcement learning setting, we set k · k? = k · k1 and k · k = k · k1. We are ready to prove convergence guarantees for Algorithm 4 when applied to the objective JD.
  Lemma 7. Let Assumptions 1, 2 and 3 hold. Let D = {v s.t. kvk1  D} and c0 = log |S||A| ⇢
  ⌘ . After T steps of Algorithm 4, the objective function JD evaluated at the iterate vT = yT satisfies:
  JD(vT ) JD(v ⇤)  4⌘(|S|+ 1)2
  (1 + c0)2
  (1 )2T 2 ,
  Proof. This result follows simply by invoking the guarantees of Theorem 1, making use of the fact that JD is (|S|+ 1)⌘ smooth as proven by Lemma 3, observing that as a consequence of Lemma 5, v? 2 D and using the inequality kxk22  |S|kxk21 for x 2 R|S|.
  Lemma 7 can be easily turned into the following guarantee on the final dual function value:
  Corollary 1. Let ✏ > 0. If Algorithm 4 is ran for at least T rounds where T 2⌘1/2(|S|+1) (1+c 0)
  (1 ) p ✏
  then vT is an ✏ optimal solution for the dual objective JD.
  If T satisfies the conditions of Corollary 1 a simple use of Lemma 6 allows us to bound the k · k1 norm of the dual function’s gradient at vT :
  krJD(vT )k1  p 2(|S|+ 1)⌘✏
  If we denote as ⇡T to be the policy induced by vT , and ?⌘ is the candidate dual solution corresponding to v?. A simple application of Lemma 4 yields:
  JP ( ⇡T ) JP ( ? ⌘)
  p 2(|S|+ 1)⌘✏
  1
  2 +
  1 + log |S||A| 2⇢4
  ⌘
  !
  The following is the equivalent version of optimality for regularized objectives:
  Definition 9. Let ✏ > 0. We say ⇡̃ is an ✏ optimal regularized policy if JP ( e⇡) JP ( ?⌘) ✏.
  This leads us to the main result of this section: Corollary 2. For any ⇠ > 0, and let c00 = 1+log |S||A| 2⇢4
  ⌘ . If T 4⌘ (|S|+ 1) 3/2 (2+c00) 2
  (1 )2⇠ then JP ( ⇡T ) JP ( ? ⌘) ⇠.
  Thus Algorithm 4 achieves an O(1/(1 )2✏) rate to an ✏ optimal regularized policy. We proceed to show that an appropriate choice for ⌘ can be leveraged to obtain an ✏ optimal policy.
  Theorem 2. For any ✏ > 0, let ⌘ = 1 2✏ log( |S||A| )
  . If T (|S| + 1)3/2 (2+c 00)2
  (1 )2✏2 , then ⇡T is an
  ✏ optimal policy.
  The main difficulty in deriving the guarantees of Theorem 2 lies in the need to translate the function value optimality guarantees of Accelerated Gradient Descent into ✏-optimality guarantees for the candidate policy ⇡T . This is where our results from Lemma 4 have proven fundamental. It remains to show that it is possible to obtain an ✏ optimal policy when access to the true model is only via samples.
sections.heading: 6 Stochastic Gradients
sections.text: In this section we show how to obtain stochastic (albeit biased) gradient estimators brvJD(v) for rvJD(v) (see Algorithm 2). We use brvJD(v) to perform biased stochastic gradient descent steps on JD(v) (see Algorithm 3). In Lemma 8 we prove guarantees for the bias and variance of this estimator and show rates for convergence in function value to the optimum of JD(v) in Lemma 10. We turn these results into guarantees for ✏ optimality of the final candidate policy in Theorem 3. Let’s start by noting that:
  (rvJD(v))s = (1 )µs + E(s0,a,s00)⇠q⇥Pa(·|s0) h Bvs0,a ( 1(s 00 = s) 1(s0 = s)) i ,
  Where Bvs,a = exp(⌘Avs,a) Z and Z = P s,a exp ⌘Avs,a qs,a. We will make use of this characterization to devise a plug-in estimator for this quantity:
  Algorithm 2 Biased Gradient Estimator Input Number of samples t. Collect samples {(s`, a`, s0`)} t `=1 such that (s`, a`) ⇠ q while s 0 ` ⇠ Pa`(·|s`) for (s, a) 2 S ⇥A do Build empirical estimators bAv(t) 2 R|S|⇥|A| and bq(t) 2 R|S|⇥|A|. Compute estimators bBvs,a(t) = exp(⌘ bAvs,a(t)) bZ(t) .
  Where bZ(t) = P
  s,a exp(⌘ bAvs,a(t))bqs,a(t).
  end Produce a final sample (st+1, at+1) ⇠ q and s0t+1 ⇠ Pat+1(·|st+1). Compute brvJD(v) such that: ⇣ brvJD(v) ⌘
  s = (1 )µs + bBst+1,at+1 (t)
  ⇣ 1(s0t+1 = s) 1(st+1 = s) ⌘ .
  Output: brvJD(v).
  We now proceed to bound the bias of this estimator: Lemma 8. Let , ⇠ 2 (0, 1) with ⇠  min( , 14 ). With probability at least 1 for all t 2 N such that tln ln(2t) 120(ln 41.6|S||A| +1) ⇠2 max 480⌘2 2kvk21, 1 , the plugin estimator brvJD(v) satisfies:
  max u2{1,2,1}
  kĝ Et+1[ĝ]ku  8 ; max
  u2{1,2,1} kEt+1[ĝ] gku  8⇠ ;
  E h kĝ Et+1[ĝ]k22 bBv(t) i  8 ,
  where ĝ = brvJD(v), g = rvJD(v), and Et+1[·] = Est+1,at+1,s0t+1 [·|bB v(t)].
  We will now make use of Lemma 8 along with the following guarantee for projected Stochastic Gradient Descent to prove convergence guarantees for Algorithm 3.
  Algorithm 3 Biased Stochastic Gradient Descent Input Desired accuracy ✏, learning rates {⌧t}1t=1, and number-of-samples function n : N! N . Initialize v0 = 0 for t = 1, · · · , T do
  Get brvJD(v) with n(t) samples via Algorithm 2. Perform update: v0t vt ⌧t brvJD(v); vt ⇧D(v0t), where ⇧D denotes the projection to D = {v s.t. kvk1  D}.
  end Output: vT .
  The following holds: Lemma 9. Let f : Rd ! R be an L smooth function. We consider the following update:
  x0t+1 = xt ⌧ (rf(xt) + ✏t + bt) ; xt+1 = ⇧D(x 0 t+1).
  If ⌧  2L then:
  f(xt+1) f(x?)  kxt x?k2 kxt+1 x?k2
  2⌧ + 2⌧krf(xt)k2 + 5⌧kbtk2 + 5⌧k✏tk2
  + kbtk1kxt x?k1 h✏t,xt x?i.
  Lemma 8 implies the following guarantee for the following projected stochastic gradient algorithm with biased gradients brvJD(v)R:
  Lemma 10. We assume ⌘ 4 . Set ⇠t = 8|S|⌘Dp t and ⌧t = 116|S|⌘pt . If we take t gradient steps using n(t) samples from q⇥P (possibly reusing the samples for multiple gradient computations) with n(t)
  satisfying n(t) 525t
  ✓ ln 100|S||A|t 2 +1 ◆3
  |S|2 . Then for all t 1 we have that with probability at least
  1 3 and simultaneously for all t 2 N such that t 64|S| 2⌘2D2 :
  JD
  ✓ 1
  t
  Pt `=1 v` ◆  JD(v?) + eO ✓ D
  2 |S|⌘ p t
  ◆ .
  Lemma 10 implies that making use of N samples it is possible to find a candidate v̄N such that JD(v̄N )  JD(v?) + eO ⇣ D2⌘ p N ⌘ . This in turn implies by a simple use of Lemma 6 that krJD(v̄N )k1  eO ⇣ |S|1/2D⌘p N1/4 ⌘ . If we denote as ⇡̄N to the policy induced by v̄N , a simple application of Lemma 4 yields:
  JP ( ⇡̄N ) JP ( ? ⌘) eO
  ✓ |S| 1/2 D⌘
  (1 ) p N1/4
  ◆
  Thus Algorithm 3 achieves an O(1/(1 )8✏4) rate of convergence to an ✏ optimal regularized policy. We proceed to we can set ⌘ to obtain an ✏ optimal policy:
  Theorem 3 (Informal). For any ✏ > 0 let ⌘ = 1 2✏ log( |S||A| )
  . If N eO ⇣
  1 ✏8(1 )8 2
  ⌘ , then with
  probability at least 1 it is possible to find a candidate v̄N such that ⇡̄N is an ✏ optimal policy.
sections.heading: 7 Conclusion
sections.text: This work presents an analysis of first-order optimization methods for the REPS objective in reinforcement learning. We prove convergence rates of O(1/✏2) for accelerated gradient descent on the dual of the KL-regularized max-return LP in the case of a known transition function with convergence rate. For the unknown case, we propose a biased stochastic gradient descent method relying on samples from behavior policy and show that it converges to an optimal policy with rate O(1/✏8). There are several interesting questions that remain open. First, while directly optimizing the dual via gradient methods is convenient from an algorithmic perspective, prior unregularized saddle-point methods have been shown to achieve a faster O(1/✏) convergence [4]. An important open direction is thus to understand if faster rates are possible in order to bridge this gap, or if optimizing the regularized dual directly is fundamentally limited. Second, we only considered MDPs with finite state and action spaces. It is therefore of interest to see if these ideas readily extend to infinite or very large spaces through function approximation.
  Acknowledgments and Disclosure of Funding
  This research was supported by the Google-BAIR Commons program. JL is supported by NSF GRFP.
title: Near Optimal Policy Optimization via REPS