Actor-critic is implicitly biased towards high entropy optimal policies
Authors: Yuzheng Hu
Ziwei Ji
Matus Telgarsky
Venue: ICLR 2022 Poster (2022)
Keywords: implicit bias
reinforcement learning
actor-critic
policy gradient
mixing time
convergence rate
mirror ascent.

Abstract: We show that the simplest actor-critic method — a linear softmax policy updated with TD through interaction with a linear MDP, but featuring no explicit regularization or exploration — does not merely find an optimal policy, but moreover prefers high entropy optimal policies. To demonstrate the strength of this bias, the algorithm not only has no regularization, no projections, and no exploration like $\epsilon$-greedy, but is moreover trained on a single trajectory with no resets. The key consequence of the high entropy bias is that uniform mixing assumptions on the MDP, which exist in some form in all prior work, can be dropped: the implicit regularization of the high entropy bias is enough to ensure that all chains mix and an optimal policy is reached with high probability. As auxiliary contributions, this work decouples concerns between the actor and critic by writing the actor update as an explicit mirror descent, provides tools to uniformly bound mixing times within KL balls of policy space, and provides a projection-free TD analysis with its own implicit bias which can be run from an unmixed starting distribution.


ACTOR-CRITIC IS IMPLICITLY BIASED TOWARDS HIGH ENTROPY OPTIMAL POLICIES
Yuzheng Hu, Ziwei Ji, Matus Telgarsky University of Illinois, Strbana-Champer 4y446 ziwet j12, mjt 31 www.iiinnsee..em
ABSTRACT
We show that the simplest actor-critic method a linear softmax policy updated with TD through interaction with a linear MDP, but featuring no explicit regular- ization exploration
does not merely find an optimal policy, but moreover prefers high entropy optimal policies. To demonstrate the strength of this bias, the algorithm not only has regularization, no projections, and no exploration like c-greedy, but is moreover trained on a single trajectory with no resets. The key consequence of the high entropy bias that uniform mixing assumptions on the MDP, which exist in some form in all prior work, can be dropped: the implicit regularization of the high entropy bias is enough ensure that all chains mix and an optimal policy is reached with high probability. As auxiliary contributions, this work decouples concerns between the actor and critic by writing the actor up- date as an explicit mirror descent, provides tools to uniformly bound mixing times within KI. balls of policy space, and provides a projection-free TD analysis with its own implicit bias which can be run from unmixed starting distribution.
OVERVIEW
Reinforcement learning methods navigate an environment and seek to maximize their reward (Sut- ton & Barto 2018). A key tension is the tradeoff between exploration and exploitation: does learner (also called an agent or policy) explore for new high-reward states, or does exploit the best states it has already found? This is a sensitive part of RI algorithm design, as it is easy for methods to become blind to parts of the state space; to combat this, many methods have an explicit exploration component, for instance the e-greedy method, which forces exploration in all states with probability c (Sutton & Barto 2018 Tokic 2010). Similarly, many methods must use projections and regularization to smooth their estimates (Williams & Peng 1991 Mnih et al. 2016 Cen et al. 2020).
This work considers actor-critic methods, where policy (or actor) is updated via the suggestions of a critic. In this setting, prior work invokes a combination of explicit regularization and exploration avoid getting stuck, and makes various fast mixing assumptions to help accurate exploration. For example, recent work with a single trajectory in the tabular case used both an explicit e-greedy component and uniform mixing assumptions (Khodadadian al. 2021), neural actor-critic methods use combination of projections and regularization together with various assumptions on mixing and on the path followed through policy space (Cai al. 2019 Wang et al.) (2019), and even direct analyses of the TD subroutine in our linear MDP setting make use of both projection steps and an assumption of starting from the stationary distribution (Bhandari et al. 2018).
Contribution. This work shows that a simple linear actor-critic (cf. Algorithm 1 in linear MDP (cf. Assumption I.3) with a finite but non-tabular state space (cf. Assumption[L.] finds an e-optimal policy in (1/y(1/e) samples, without any explicit exploration or projections in the algorithm and without any uniform mixing assumptions on the policy space (cf. Theorem I.4). The algorithm and analysis avoid both via an implicit bias towards high entropy policies: the actor-critic policy path never leaves a Kullback- Kullback-Leibler (KL) divergence ball of the maximum entropy optimal policy, and this firstly ensures implicit exploration, and secondly ensures fast mixing. In more detail:

---

1. Actor analysis via mirror descent. We write the actor update explicit mirror descent. While on the surface this does not change the method (e.g.. in the tabular case, the method is identical to natural policy gradient (Agarwal et al. 2021b)), it gives clean optimization guarantee which carries a KI.-hased implicit bias consequence for free, and decouples concerns between the actor and critic.
2. Critic analysis via projection-free sampling tools within KL balls. The preceding mirror descent component guarantees that we stay within a small KL ball, if the statistical error of the critic is controlled. Concordantly, we stay within a small KL ball. Concretely, we provide useful lemmas that every policy in a KL. ball around the high entropy policy has uniformly upper bounded mixing times, and separately give a projection-fres (implicitly regularized!) analysis of the standard temporal-difee differeecee (TD) update from any starting state (Sutton) 1988), whereas the closest TD analysis in the literature uses projections and requires the sampling process to be started from the stationary distribution (Bhandari et al. 2018). The mixing assumptions here contrast general with prior work, which either makes explicit use of stationary distributions (Cai et al. [0119] Wang et al.,
sampling tools guarantee this statistical error is small, if
2019
Bhandari et al.) 2018), or makes uniform mixing assumptions on all policies (Xu et al,
2020
Khodadadian et al. 2021).
In addition to the preceding major contributions, the paper comes with many technical lemmas (e.g., mixing time lemmas) which we hope are useful in other work.
1.1 SETTING AND MAIN RESULTS
We will now give the setting, main result, and algorithm in full. Further details on MDPs can be found in Section 1.3, but the actor-critic method appears in Algorithm I To start, the environment and policies
tollows.
Assumption 1.1. The Markov Decision Process (MDP) has states & E Rd and finitely many actions
E A {ei, ......... ), and finite rewards E [0, 1]. States observed in some feature encoding 8 E Rdd but the state space S S {s E Rd 1/2 S | S 1} is assumed finite: |S] < cc.
Policies linear softmax policies: policy is parameterized by weight matrix W Rd* and given a state 8 E Rdd, uses a per-state softmax to sample a new action a:
exp(s'Wa) where o(s EsE exp(
a a~ (ss(ss)..
(1.1)
Let A, denote the set of optimal actions for given state 8. It is assumed that A, is nonempty for every s E S, and that there exists least one optimal policy which irreducible (Levin al. 2006 Chapter 1).
The choice of linear policies simplifies presentation and analysis, but the tools here should be appli- cable to other settings. This choice also allows direct comparison to the widely-studin implicit bias
Algorithm 1 Single-trajectory linear actor-critic.
Inputs: actor iterations i and step size A; critic iterations N and step size
Initialize: actor weights Wo = 0 E [gdxk, pre-softmax mapping po(s, = 8 Woa, policy To := <(po) (cf. eq. 111 )) sample initial state/action/rewarr triple (sa,0, 00.0, ro,0).
for = 0, 1,2.....
do
Critic update:
T. to interact with the MDP, obtaining state/action/reward triples (Si.j, (igii Fis)isN by continuing the existing trajectory, and form TD estimates
U = U2j - n78.j (sl, Ut.aaa - 781141 -ris) oh.3.
with initial condition U.o = 0. Set Ug == 1/2 EjeN ULs and @i(s,a) == s Ü.a and also (s1410, a,+10,, F1+1.0) := (SL,N, Ti,N) to continue the existing trajectory in next iteration.
Actor update: set W W, + 00, and pi+1 pt + 0 and T ((p+1)).
end for
2

---

of gradient descent in linear classification settings (Soudry et al. 2017 Ji & Telgarsky 2018), will be discussed further Section 1.2 The choice of finite state space is to remove wreasure-theorete
concerns and to allow a simple characterization of the maximum entropy optimal policy.
Lemma 1.2 (simplification of Le.maaA.1] Under Assumption [.]] there exists a unique maximum
eniropy policy which satisfies (s,,)) Uniform( A.) for every state 5, and moreover has stationary distribution ST.
To round out this introductory presentation of the actor, the last component is the update: Pi+1 == p: + 2i and *x+1 == o(p;-1), where O; is the TD estimate of the Q function, to be discussed shortly. This update explicitly mirror descent or dual averaging update of the policy, where we use a mirror mapping @ to obtain the policy Ti+1 from pre-softmax values P++1- As mentioned before, this update appears in prior work in the tabular setting with natural policy gradient and actor-critic (Agarwal al. 202 Khodadadian al. (02T). and will be related to other methods in Section 1.2 We will further motivate this update in Section 2
The final assumption and description of the critic are as follows. As will be discussed in Section 2 the policy becomes optimal if Q, is accurate estimate of the true Q function. We employ standard TD update with no projections or constraints. To guarantee that this linear model of Q
accurate, we make a standard linear MDP assumption (Bradtke & BartO 1996 Melo & Ribeiro 2007 Jin et al. (020).
Assumption 1.3. In words, the linear MDP assumption that the MDP rewards and transitions are modeled by linear functions. In more detail, for convenience first fix a canonical vector form
for state/action pairs as E Rd let & E Iedk denote the vector obtained via unrolling the matrix sa" row-wise (whereby vector inner products with Isa match matrix inner products with sa") ). The linear MDP assumption is then that there exists a fixed vector y E Rad and fixed matrix M E paxdk that for any state/action pair Zea and any subsequent state s' E R
Bir (s, a)] = xlay, and Bis' (8, = M Lastly, suppose 1/2 s ||||| - 1 for all s E S.
Though a strong assumption, is not only common, but note also that since TD must continually interact with the MDP, then it would have little hope of accuracy if it can not model short-term MDP dynamics. Indeed, as shown in Lemma C33 (but appears in various forms throughout the literature), Assumption 1.3 immplis that the fixed point of the TD update is the true Q function. This assumption and the closely related compatible linear function approximation assumption will be discussed in Section 1.2
We now state our main result, which bounds not just the value function (cf. Section 1.3p
also the KL divergence Kog(T,, (7, m:) Egg (ss a) In F(s'aa)
x;(e'aa) where Df is the visitation distribution of the maximum entropy optimal policy ग. when run from state (cf. Section I.3)
Theorem 1.4. Suppose Assumptions [.I and T.3 (which imply the (unique) maximum entropy opti- mal policy ßे is well-defined and has stationary distribution). Given iteration budget t, choose
0 -=
N N (fllt)
n=
(1
113/16 In(t)1/4
VN
where the constants hidden inside each ( depend only R and the MDP, but not on l. With these parameters in place, invoke Algorithm| 7 and let (m))ecs a be the resulting sequence of policies. Then with probability at least 1 - 1/2 simultaneously for every state s IRd and every i S t,
Kag (T,, (T, me) + 0(1
Σ (V+(s) 1,(+)))),))))))))))) v3)+)) S In + (1-7)² JAZ
Before outlining the proof structure and organization of the rest of the paper, a few comments on the interpretation of Theorem 1.4 [.44] are follows.
Remark 1.5 (Discussion of Theorem 1.4
1. Implicit bias. Since मे is optimal, the second term can be deleted, and the bound implies
max K (T, m:) S In l: +
(1 7)
<5t
sES
3

---

since this holds for all i I t, it controls the optimization path. This term is direct consequence of our mirror descent setup, and is used to control the TD errors at every iteration. This implicit bias of the policy path stands therefore in stark contrast to the worst-case KL divergence be- tween arbitrary softmax policies and я, which is infinite: e.g., a sequence of policies (m1)s21 which place vanishing probability on pair (s,a) a) which in turn receives positive probability under मे will have Koş & (T,, m.) + oc.
2. Mixing time constants. The critic iterations N and step size v hide mixing time constants; these mixing time constants depend only on the KL bound In k 1-(11>)) 7) there is no hidden growth in these terms with t. That is to say, mixing times are uniformly controlled over a fixed KI. ball that does not depend on t: prior work by contrast makes strong mixing assumptions (Wang et al., 2019 Xu et al. [020) Khodadadian et al. (021).
and in particular
3. High probability guarantee. Though prior work focuses on bounds in expectation, we chose high probability guarantee to emphasize that the bound does not blow up, despite an arguably more strenuous setting.
4. Single trajectory. A single trajectory through the MDP is used to remove the option of the algorithm escaping from poor choices with resets; only the implicit bias can save it.
5. Rate. To reach policy which whose value function is e-close to optimal, a trajectory length (number of samples) of 1/c" is sufficient, ignoring log factors (to obtain this from Theo- rem 1.4 it suffices divide both sides of the bound by t0(1 - 7), set = 1//2 and note the trajectory length is I.N). This is slower than the 1/c6 given in the only other single-trajectory analysis in the literature Khodadadian al. (2021), but by contrast that work makes uniform mixing assumptions (cf. Khodadadian et al. 22021 Lemma C.I)), requires the tabular setting, and uses e-greedy for explicit exploration in each iteration.
The proof of Theorem 1.4 and organization of the paper are as follows. After overviews of related work and notation in Sections 1.2 and 1.3 the first proof component, discussed in Section 2 is the outer loop of Algorithm|] [ namely the update to the policy T;. As discussed before, this part of the analysis writes the policy update as mirror descent, and conveniently decouples the suboptimality error into an actor error, which is handled by standard mirror descent tools and provides the implicit bias towards high entropy policies, and critic error, namely the error of the estimated Q function Q.. The second component, discussed in Section 3 is therefore the TD analysis establishing that the estimate Q₂ is accurate, which not only requires an abstract TD guarantee (which, as mentioned, is projection-free and run from arbitrary starting state, unlike prior work), but also requires tools to explicitly bound mixing times, rather than assuming mixing times are bounded.
This culminates in the proof of Theorem 1.4. which is sketched the end of Section and uses an induction combining the guarantees from the preceding two proof components at all times: is established inductively that the next policy Ti+11 has high entropy and low suboptimality because the previous Q function estimates (E)) were accurate, and simultaneously that the next estimate i is accurate because π₃-1 has high entropy, which guarantees fast mixing. Section 4 concludes with some discussion and open problems, and the appendices contain the full proofs.
1.2 FURTHER RELATED WORK
For the standard background in reinforcement learning, see the book by Sutton & Barto (0188) Standard concepts and notation choices are presented below in Section 1.3
Standard algorithms: PG/NPG and ACIACC. The [natural] policy gradient ([NJPG) and nat- ural actor-critic ([N]AC) are widely used in practice, and summarized briefly as follows. Policy gradient methods update the actor parameters W with gradient ascent on the value function (-(())
for some state distribution J (Williams) 1992 Sutton et al. 20000 Bagnell & Schneider [0033] Liu
et al. 2020; Fazel et al. 2018), whereas natural policy gradient multiplies Vw (4) by an inverse Fisher matrix with the goal of improved convergence via a more relevant geometry (Kakade 2001] Agarwal et al. 2021b). What policy gradient leaves open is how to estimate Vw Vi, (p); actor-critic methods go one step further and suggest updating the actor with policy gradient as above, but noting that V V. (1) can be written as function of Q., or rather estimate thereof, and making this
4

---

estimation the job of separate subroutine, called the critic Konda & Tsitsiklis (2000). (Natural actor-critic uses natural policy gradient in the actor update (Peters & Schaal 2008).) Actor-critic methods are perhaps the most widely-used instances of policy gradient, and come in many forms; the use of TD for the critic step is common (Williams) 1992. Sutton et al. 2000 Bagnell & Schneider,
2003
Liu et al. 2020
Fazel et al. 2018).
Linear MDPs and compatible function approximation. The linear MDP assumption (cf. As- sumption| 1.3) is used here to ensure that the TD step accurately estimates the true Q function, and is somewhat common assumption in the literature, even when TD is not used (Bradtke & Barto 1996
Melo & Ribeiro 2007 Jin et al. 2020). As an example, the tabular setting satisfies Assumption 1.3
simply by encoding states as distinct standard basis vectors, namely S {er. (el....,. G|s) } (Jin al. 2020 Example 2.1); moreover, in this tabular setting, the actor update of Algorithm | agrees with NPG AAgaraal al. 2021b). Interestingly, another common assumption, compatible linear function approximation, also guarantees our analysis goes through and that Algorithm D agrees with NPG, while being non-tabular in general. In detail, the compatible function approximation setting firstly requires that the actor update agrees with 2, in a certain sense (which holds in our setting by con- struction), and secondly that there exists choice of critic parameters U that the exact Q function Qx can be represented with these parameters (Silver) 2015). If this assumption holds for every pol- icy n, (and corresponding Qi) encountered in the algorithm, then the policy update of Algorithm agrees with NPG and NAC (this is a standard fact; see for instance Silver (2015), or (Agarwal et al. (2021a Lemma 13.1)). Additionally, the proofs here also go through under this arguably weaker assumption: Assumption 1.3 is only used to ensure that TD finds not just a fixed point but the true Q function (cf. Lemma C.4). which is also guaranteed by the compatibility assumption. However, since this is an assumption on the trajectory and thus harder to interpret, we prefer Assumption I.3 which explicitly holds for all possible policies.
Regularization and constraints. It is standard with neural policies to explicitly maintain a con- straint on the network weights (Wang et al. 2019] Cai et al. 2019). Relatedly, many works both in theory and practice use explicit entropy regularization to prevent small probabilities (Williams & Peng 1991] Mnih et al. 2016 Abdolmaleki et al. 2018), and which can seem to yield convergence rate improvements (Cen al. 2020p.
NPG and mirror descent. (For background mirror descent, see Section 2 and appendix B
The original and recent analyses of NPG had a mirror descent flavor, though mirror descent and its analysis were not explicitly invoked (Kakade 2001; Agarwal et al.. 2021b). Further connections to mirror descent have appeared many times Geist et al.) 2019 (Shani et al. 2020), though with
a focus on the design of new algorithms, and not for any implicit regularization effect or proof.
Mirror descent is used heavily throughout the online learning literature (Shalev- Shwarzz 20111 and
in work handling adversarial MDP settings (Zimin Neu 2013).
Temporal-difference update (TD). As discussed before, the TD update, originally presented by (Sutton 1988), is standard in the actor-critic literature (Cai et al. 2019 Wang et al., 2019). and also appears many other works cited in this section. As was mentioned, prior work requires various projections and initial state assumptions (Bhandari et al. 2018), or positive eigenvalue assumptions
(Zou et al. 2019, Srikant & Ying 2019 Bhandari et al. 2018).
Implicit regularization in supervised learning. A pervasive topic in supervised learning is the implicil regularization effect of common descent methods; concretely, standard descent methods prefer low or even minimum norm solutions, which can be converted into generalization bounds. The present work makes use of a weak implicit bias, which only prefers smaller norms and does not necessarily lead to minimal norms; arguably this idea was used in the classical perceptron method (Novikoff, 1962). but was then shown in linear and shallow network cases of SGD applied to logistic regression (Ji & Tel Telgarsky 2018 2019), which was then generalized to other losses (Shamir 2020), and also applied to other settings (Chen et al.] 2019). The more well-known strong implicit bias, namely the convergence to minimum norm solutions, has been observed with exponentially-taiin
losses together with coordinate descent with linear predictors (Zhang & Yu 2005; Telgarsky 2013)) gradient descent with linear predictors (Soudry et al. 2017 & Telgarsky| 2018). and deep learning
in various settings (Lyu & Li 2019 Chizat & Bach 2020). just to name few.
5

---

1.3 NOTATION
This brief notation section summarizes various concepts and notation used throughout; modulo a few inventions, the presentation mostly matches standard ones in RL (Sutton & Barto 2018) and policy gradient (Agarwal et al. 2021b). A policy т : I2d x R + k maps state-action pairs to reals, and (s. -) will always be probability distribution. Given state, the agent samples an action from a π -s.-), ) the environment returns some random reward (which has a fixed distribution conditioned on the observed (s, a) pair), and then uses a transition kernel to choose a new state given (s, a).
Taking т to denote a random trajectory followed by a policy æ interacting with the MDP from an arbitrary initial state distribution ja, the value V and Q functions are respectively
Va (u) ==
E Sprepa 0..."".11"""
Ex're
(x,aa) ==
E
Σ Yrr = Brg=(s.a) (ro + 7e
80 400,0000000 .10
+2.0
where the simplified notation (+) Vx for Dirac distribution 6, state will often be used,
as well as the shorthand V; = =v; and O = Ωr,. Additionally, let Az a) == (x, (s) f function; note that the natural policy gradient update could interchangeably use A or Q; since they only differ by an action-inddpendee normalizes out, As in Assumption 1.1 the state space
denote the advantage
constant, namely V2 (s), which the softmax
finite but subset of R. specifically S S. ( E Rd : 1/2 < ||s|| < J. and the action space A is just the k standard basis vectors Cc.....,c.]. The other MDP assumption, namely of linear MDP (cf. Assumption 1.3), will be used whenever TD guarantees are needed. Lastly, the discount factor Y E (0, 1) has not been highlighted, but is standard in the RL literature, and will be treated as given and fixed throughout the present work.
common tool in RL is the performance difference lemma (Kakade & Langford 2002): letting b/ denote the visitation distribution corresponding policy starting from μ., meaning
1
y /Pris: s|so = s'),
$20
the performance difference lemma can be written as
1 (s) =: 1-7 (Qn, x - -²)
V=(n) - (+)( = 1 B o!
E
(1.2)
where the final inner product notation will often be employed for convenience.
In few places, we need the Markov chain states, Ps. which is induced by policy :: that is, the chain where given a state 8, we sample a ~ ((s -), and then transition to s² ~ (8, a), where the latter sampling via the MDP's transition kernel.
As mentioned above, S will denote the stationary distribution of policy whenever it exists. The only relevant assumption we make here, namely Assumption I.] is that the maximum entropy optimal policy म is aperiodic and irreducible, which implies it has a stationary distribution with positive mass on every state (Levin et al.) [006] Chapter 1). Via Lemma [3.1] it follows that all policies in KL ball around मे also have stationary distributions with positive mass every state.
The max entropy optimal policy æ is complemented by a (unique) optimal Q function Q and op- timal advantage function A. The optimal Q function Q dominates all other Q functions, meaning ((s, a) 2 Qa (s, a) for any policy म; for details and a proof, see Lemma A.1
We use !|リ-~||Tv suprrcs Iu(U) - to denote the total variation distance, which is pervasive mixing time analyses (Levin et al. 2006).
MIRROR DESCENT TOOLS
To see how nicely mirror descent and its guarantees fit with the NPG/NAC setup, first recall our updates: Pe+1 pt Ô. and met1 d(pit)) (e.g., matching NPG in the tabular case (Kakade

---

2001 Agarwal al. 2021b)). In the online learning literature (Shalev-Shwarr Shwartzz 201 Lattimore & Szepesván 2020). the basic mirror ascent (or dual averaging) guarantee of the form
m. -
(vi).
where notably O can be arbitrary matrix. The most common results are stated when Q is the gradient of some convex function, but here instead we can use the performance difference lemma (cf. eq. (1.2)): recalling the inner product and visitation distribution notation from Section 1.3
(Q1, π )) =Qi, -mo + ( @ Qi, TT. (TT) 7 /
(1 (01->) (vi(k) (n)) (0:-
- Q.
The term 2 --2 is exactly what we will control with the TD analysis, and thus the mirror descent approach has neatly decoupled concerns into actor term, and critic term.
In order to apply the mirror descent framework, we need to choose a mirror mapping. Rather than using Φ, for technical reasons we bake the measure Dz into the mirror mapping and corresponding dual objects (cf. Appendix B and the proof Lemma 2.1). This may seem strange, but it does not change the induced policy (it scales the dual object for each state by constant), and thus is degree of freedom, and allows us to state guarantees for all possible starting distributions for free.
Our full mirror descent setup is detailed in Appendix B but culminates in the following guarantee.
Lemma 2.1. Consider step size >> O, any reference policy n, any starting measure μ4, and two trealments of the error ② - Qi.
1. (Simplified bound.) Define C sup,,a (2,(s, a)) for all i < Then
K Kay(T (T, ne) + 0(1 7) Σ
(Va(H) - V(u) I Kog (T,, To) + 02 E C/
ict
ict
Q. Qs Te - /
ixt
2. (Refined bound.) Define é; := sup,,a 1u 22(,, a)l. Then
0
Koe(n, mT) + 0(1 7) Σ
(V*(u) - Vi(14) - K (I,, тo) +
1-
i<
27 + é + Eim1).
0
1-7
and additionally V; and Qn are approximately monotone: for any state and action
22, 1-7
Vs+1(s) 2 (s(s)
and 2.+1(s, 2 (s.
è ê1+1
1-7
Remark 2.2 (Regarding the mirror descent setup, Lemma 2.1
1. Two rates. For the refined bound, it is most natural to set 1, which requires O1/s)) itera- tions to reach accuracy c > 0; by contrast, the simplified guarantee requires (1/22) iterations for the same > 0 with step size since its TD error term is less stringent; indeed, the TD analysis we provide in Section will not be able to give the uniform control needed for the refined bound. Still, we feel the refined bound is promising, and include it for sake of completeness, future work, and comparison to prior work.
1/VE. We use the simplified form to prove Theorem 1.4
2. Comparison to standard rates. Comparing the refined bound (with all é terms set zero) to the standard NPG rate the literature (Agarwal et al.) 20211), the rate exactly recovered; as such, this mirror descent setup at the very least has not paid price in rates.
7

---

3. Implicit regularization term, A conspicuous difference between these bounds and both the standard NPG bounds (Agarwal et al., 2021b Theorem 5.3). but also many mirror descent treatments, is the term Koy (T,, Te); one could argue that this term is nonnegative and moreover we care more about the value function, so why not drop it, as is usual? It is precisely this term that gives implicit regularization effect: instead, uniformly upper bound the right hand side to get Kay ( Tt) S Ink + 1/(1 =))², which is how we control the entropy of the policy path, and prove Theorem 1.4
drop the value function term and
3 SAMPLING TOOLS
Via Lemma 2.1 above, our mirror descent black box analysis gives us a KL bound and a value function bound: what remains, and is the job of this section, is to control the Q function estimation error, namely terms of the form
Our analysis here has two parts. The first part, as follows immediately, is that any bounded KL ball policy space has uniformly controlled mixing times; the second part, which comes shortly thereafter, is our TD guarantees.
Let policy it be given, and suppose the induced transition kernel on states P3 is irre- ducible and aperiodic (Levin al. 2006 Section 1.3). Then t has stationary distribution 5g. and moreover for any > () 0and any measure u which is positive on all states and corresponding set of policies
Lemma 3.1.
Pe:=
= { (T) S sc
there exist constants C, m, m2 so that mixing is uniform over Pe. meaning for any I, and any E Pe with induced transition probabilities Px.
sup (s, Sx lTv S mie mmemmaa mat
and for any state and any Par and any action with #(s a) O.
#(8 a) C T(s
2
3z (s)
C and
C - s5) (s)
S.
Remark 3.2 (Implicit vs explicit exploration). On the surface, Lemma 3.1 might seem quite nice. Worrying about it little more, and especially after inspecting the proof, it is clear that the constants C, mi, and my can be quite bad. On the one hand, one may argue that this is inherent to implicit exploration, and something like e-greedy is preferable, as it arguably gives explicit control on all these quantities.
Some aspects of this situation unavoidable, however. Consider combination lock MDP, where a precise, hard-to- find sequence of actions must be followed to arrive at some good reward. Suppose this sequence has length and we have reference policy स which takes each of these good actions with probability 1- 1/n, whereby the probability of the sequence is (1 - 1/n)" xs 1/e; policy drop the probability of this good sequence
Pe with (s, af/ff(, a) 1/2 for all actions of actions all the way down to 1/2"!
Next present our TD analysis. As discussed in Section [ by contrast with prior work, our TD method does not make use of any projections, and does not require eigenvalue assumptions. The following guarantee is specialized Algorithm [ it is corollary of more general TD guarantee, given in Appendix C which is stated without reference to Algorithm [ and can be applied in other settings.
Suppose the MDP and linear MDP assumptions (cf. Assump- tions 1.7 and I.3). Consider a policy ni in some iteration of Algorithum 7 and suppose there exist mixing constants 2 1 and c 0 so that the induced transition kernel Pr, S satisfies
Lemma 3.3 (See also Lemma C.4).
sup pt (8, ST. II I me
Suppose the TD iterations N and step size satisfy
In + In m
N2 2 k.
n 400VKN
where ks =
8

---

Then letting E, denote expectation over the trajectory (SLj. (1 dig)ssN and letting Uj denote the expected TD fixed point given in Lemma C33 (which satisfies ||U:|| S 2/(1 - 7), the average TD
iterate Ü; t/ Ejen Uig satisfies
E. E.|lU 10---,, 0.1l" +(N (sa",Ui-U.)
54
(1 7)2
where (sa), - - = -((,)) -00 2i(8, u) for almost every (8,a).
The proof is intricate owing mainly to issues of statistical dependency. It not merely an issue that the chain is not started from the stationary distribution; dropping the subscript i for convenience and letting ==-1 and z; denote the vectorized forms of 8 and sya,, and similarly letting uj denote the vectorized form of Jj. notice that E3. Uj are all statistically dependent. Indeed, even 2, is sampled from the stationary distribution (which also means +1+1 is distributed according to the stationary distribution as well), the conditional distribution of zj+1 given zj is not the same as that æj! To deal with such issues, the proof chooses a very small step size which ensures the TD estimate evolves much more slowly than the mixing time of the chain. On more technical level, whenever the proof encounters an inner product of the form (zj, uz), introduces a gap and instead considers (uz-k, ITy) ) where u Uj is small due to the small step size, and these two are nearly independent due to fast mixing and the corresponding choice of k.
A second component of the proof, which removes projection steps from prior work (Bhandari et al., 2018), an implicit bias of TD, detailed as follows. Mirroring the MD statement in Lemma 2.1 the left hand side here has not only a 2 O term as promised, but also norm control ||ú; - U,| : in fact, this norm control holds for all intermediate TD iterations, and is used throughout the proof to control many eтror terms. Just like in the MD analysis, this term is an implicit regularization, and is how this work avoids the projection step needed in prior work (Bhandari et al. 2018).
All the pieces are now in place to sketch the proof of Theorem 1.4 which is presented in full in Appendix D. To start, instantiate Lemma 3.1 3.1 with KI. divergence upper bound In k + 1/(1 - 7) which gives the various mixing constants used throughout the proof (which we need to instantiate now, before seeing the sequence of policies, to avoid any dependence). With that out of the way, consider some iteration i, and suppose that for all iterations j < i, we have a handle both on the TD error, and also guarantee that we are in small KL ball around (specifically, of radius In + 1/(1 - ?)) The right hand side of the simplified mirror descent bound in Lemma 2.1 only needs control on all previous TD errors, therefore it implies both bound on Ejer (,(s) and on Koς (,, m.). But this KL control on Tú means that the mixing and other constants we assumed at the start will hold for ,,, and thus we can invoke Lemma 3.3 to bound the error Q Qi which will use in the next loop of the induction. In this way, the actor and critic analyses complement each other and work together in each step of the induction.
4 DISCUSSION AND OPEN PROBLEMS
This work, in contrast to prior work in natural actor-critic and natural policy gradient methods, dropped many assumptions from the analysis, and many components from the algorithms. The analysis was meant to be fairly general purpose and unoptimized. As such, there are many open problems.
What are some situations where one is better than the other, and vice versa? The analysis here only says you can get away with doing everything implicitly, but not necessarily that this is the best option.
Implicit vs explicit regulariattion/eplloattoo
More general settings. The paper here is for linear MDPs, linear softmax policies, finite state and action spaces. How much does the implicit bias phenomenon (and this analysis) help in more general settings?

---

ACKNOWLEDGMENTS
MT thanks Alekh Agarwal, Nan Jiang, Haipeng Luo, Gergely Neu, and Tor Lattimore for valuable discussions, well as the detailed comments from the ICLR 2022 reviewers. The authors are grateful the NSF for support under grant 115-1750051.
REFERENCES
Abbas Abdolmaleki, Jost Tobias Springenberg, Yuval Tassa, Remi Munos, Nicolas Heess, and Mar- tin Riedmiller. Maximum posteriori policy optimisation. arXiv preprint 2018.
Alekh Agarwal, Nan Jiang, Sham M. Kakade, and Wen Sun. Reinforcement learning: Theory and al- gorithms. hhtpps: / /tt.oootrryoook...ooo/ github..hhhhh.. htw.hh/.....//ttheoooooo..o AJKS, pdf 2021a. Version: November 11, 2021.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021b.
J Andrew Bagnell and Jeff Schneider. Covariant policy search. 2003.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. finite time analysis of temporal difference learning with linear function approximation. arXiv preprint arXiv:1806.024933 2018.
Steven J Bradtke and Andrew Barto. Linear least-squares algorithms for temporal difference learning, Machine learning, 22(1):33-57, 1996.
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning. 2015.
Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. Neural tewporal defferal- and q-learning provably converge to global optima. arXiv preprint arXiv:1905.1002: 2019.
Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. arXiv preprint wrXiv:2007.06558 2020.
Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much over ver-paraatttrizztionnn is suffi- cient to learn deep relu networks? arXiv preprint arXiv: 123600, 2019.
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. arXiv preprint arXiv:2002.04486. 2020.
Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence of policy gradi- methods for the linear quadratic regulator. International Conference Machine Learning, pp. 1467-1476. PMLR, 2018.
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized markov decision processes. In International Conference on Machine Learning, pp. 2160-2169, PMLR, 2019.
Mark Jerrum and Alistair Sinclair. Conductance and the rapid mixing property for markov chains: The approximation permanent resolved. In STOC, pp. 235-244, 1988.
Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint wwXiv:1803.0730022 2018.
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent achieve arbi- trarily small test error with shallow relu networks. 2019, arXiv: 1909. 12292 [CS.LG].
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2144 PMLR, 2020.
10

---

Sham M Kakade. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
Sham M. Kakade and John Langford. Approximately optimal approximate reinforcement learning. In ICML, 2002.
Sajad Khodadadian, Thinh T Doan, Siva Theja Maguluri, and Justin Romberg. Finite sample anal- ysis of two-time-scale natural actor-critic algorithm. arXiv preprint arXiv:2101.10066, 2021.
Vijay R Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances in neural information processing systems, pp. 1008-1014, 2000.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020. doi: 10.101779781108571440))
David A. Levin, Yuval Peres, and Elizabeth L. Wilmer, Markov chains and mixing times. American Mathematical Society, 2006.
Yanli Liu, Kaiqing Zhang. Tamer Basar, and Wotao Yin. An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. In NeurIPS, 2020.
L. Lovasz and M. Simonovits. The mixing rate of markov chains, an isoperimetric inequality, and computing the volume. In FOCS, pp. 346-354, 1990.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint arXiv: 1906: 906605890, 2019.
Francisco Melo and M Isabel Ribeiro. Q-learning with linear function approximation. In Interna- fional Conference on Computational Learning Theory, pp. 308-322. Springer, 2007.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. International conference on machine learning, pp. 1928-1937. PMLR, 2016.
Albert B.J. Novikoff. On convergence proofs perceptrons. In Proceedings of the Symposium the Mathematical Theory of Automata, 12:615-622, 6622, 1962.
Jan Peters and Stefan Schaal. Natural actor-critic. Neurocomputing, 7107-9):1180-11 2008.
Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and trends in
Machine Learning, 4(2):107-194, 2011.
Ohad Shamir. Gradient methods never overfit on separable data. [cs. LG], 2020.
arxiv:2007.0002
Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. (1668-5675, 2020.
David Silver. Introduction to reinforcement learning: Lecture 7.
www. 2015. Accessed:
https: //www
davidsi iver..verr.. http://ww.ccooeeeer///p///////// November 13, 2021.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data. arXiv preprint arXiv:/710.10345, 2017.
R. Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation and TD lear- ing. In COLT, 2019.
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, (1):9-44, 1988.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
11

---

Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in neural informa- fion processing systems. pp. 1057-1063, 2000.
Matus Telgarsky. Margins, shrinkage, and boosting. In ICML, 2013.
Michel Tokic. Adaptive e-greedy exploration in reinforcement learning based on value differences. In Anmual Conference on Artificial Intelligence, pp. 203-210. Springer, 2010.
Cèdric Villani. Optimal Transport: Old and New. Springer Science & Business Media, 2008.
Lingxiao Wang. Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. arXiv preprint arXiv: 150, 2019.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3):229 256, 1992.
Ronald J Williams and Jing Peng. Function optimization using connectionist reinforcement learning algorithms. Connection Science, 3(3):241-268, 1991.
Tengyu Xu, Zhe Wang. and Yingbin Liang. Non-asymptotic convergence analysis of two time-scale (natural) actor-critic algorithms. arXiv preprint 20x5::2005.03557, 2020.
Tong Zhang and Bin Yu. Boosting with early stopping: Convergence and consistency. The Annals of Statistics, 13:1558-1579, 2005.
Alexander Zimin and Gergely Neu. Online learning in episodic markovian decision processes by relative entropy policy search. In NIPS, 2013.
Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for SARSA with linear function approximation. Advances in neural information processing systems, 32, 2019.
12

---

A BACKGROUND PROOF: EXISTENCE OF π
The only thing in this section is the expanded version of Lemma 1.2 namely giving the unique maximum entropy optimal policy, and some key properties.
Lemma A.I. If| < co, then there exists unique maximum entropy optimal policy n and corre- sponding Q and A which satisfy the following properties.
1. For any state let As denote the set of actions taken by optimal policies. Define (s.,-) == Uniform(A.), which is unique; then म is also optimal policy, and let A and Q denote its advantage and Q functions.
2. For every state and every action a, then ((s,a) max, (r a). where the maximum is taken over all policies. Moreover, maXaEA, Q(s,a) > maXaşAA @(s,a).
3. lim (r.))
4. If there exists an irreducible optimal policy, then ß is irreducible as well, and moreover has a stationary distribution 5
Proof of Lemmas
1. Let (S1,..., 8|S)) denote any enumeration of the state space S. This proof will inductively construct sequence of optimal policies (T.) where each H, is optimal and satisfies () = Uniform(A,,) for j S i. For the base case, let To denote any optimal policy, which satisfies the desired conditions since the indexing states starts from 1. For the inductive step, define (8, = -s,,)) for 8 & 8i41 and ( UAs,orm(As.1) By the performance difference lemma, for any state 8,
1.2 andd A.7
1 V (8) - V=.,, (8) (8)= 1-7 Re (Q,, (s.)))))
) Ti+1(s(.))
By construction, the inner product is for any * 8441- When s' = 8/41. since ,, is optimal, then (s") must be optimal for every state s", which turn means (x, (s',.) must be maximized at each A... and therefore the inner product is 0 in this case well. This completes the induction, and the desired claim follows by noting क ग
2. For any with corresponding Q function 2x and value function V4 and any (s, a), then
(ss ax E, (F.0) ((s,a) + +>V(ss) r(s, [V+''')
-ot))v'(''))
0.
It follows that @(s, 2 sup, 2x (s, a), and since Q Q=. then in fact ((s,
max, (s,
3. By the previous point, for any state s and any a E A,, then A(s,a) = [(s - V(ss
0 whereas for any b & A., then A(s,b) = ((s,b) - V(s) S maxbgA, Q(s, mingEA. a(s,a) < O. It follows that
lim ((rA(s,))) Uniform(A, (s..)) n-000
4. Let ı denote an arbitrary irreducible optimal policy. Since ग is uniform on the of optimal actions in any state, then for any pair (s, 8') and time > O with P (s, > 0, then (t s') > 0 well. Since æ is irreducible, this holds for all pairs (s, s'), which means π is irreducible as well (Levin et al. 2006, Proposition 1. 1.14), and has a stationary distribution Sş.
13

---

B FULL MIRROR DESCENT SETUP AND PROOFS
This section first gives a basic mirror descent setup. This characterization is somewhat standard (Bubeck 2015), though written with extra flexibility and with equalities to preserve implicit biases terms, which are dropped in most treatments.
First, here the basic notation (which, unlike the paper body, will allow subscripted step size 0, which can differ between iterations):
Pi+1 ps 0.9
0, > 0, closed proper convex 10, bilinear pairing, primal Bregman divergence, dual Bregman divergence.
9: = (pb(
(:-)):
D(p, pt) = (p) - [x((p)) + k4. p=ll]]
D- q:) :-= (1) (v(()))) Kp:, 9 q:31
One nonstandard choice here that the Bregman divergence bakes in conjugate element, rather than using Víd and Vyd"; this gives easy way handle certain settings (like the boundary of the simplex) which run into non-uniqueness issues. Secondly, ( -) is just a bilinear form, and does not need be interpreted standard inner product.
The standard Bregman identities used in mirror descent proof's are as follows:
Dz 4)) Dz(g, 9++1) D. (1b+11100 9:) (p; Pi+1, 4+11 9))
(B.1)
D. (1(4+1: qi) = D(p:,Pi+1)
(B.2)
D.(0++1. 9:) + D. (9:: (1+1) (p: Pi+1, 9++1))
(B.3)
D. q:) = " + x((p) - (pps 9 2
(B.4)
With these in hand, the core mirror descent guarantee is as follows. The bound is written with equalities to allow for careful handling of error terms. Note that this version of mirror descent does not interpret the "gradient" 9: in any way, and treats it as a vector and no more.
Lemma B.1. Suppose 0: > O. For any t and where E dom()²).
0g Klgr 4s 9)} = DD. 90) Dz 90) + Σ D(ps+1,Pi)
ist.
= D. 90) Dz 90) + Σ [Kpt P1+1. 91+1 - D+(9+1.94))
ist
(0( + 0 f.90. .o)) - D. 9r) - 02-1 (e) Σ (.
ist
Σ Kgr 9.9 (0, 0--1) Σ
0, K0ii1 9r. 9++1)
ict
Moreover, for any i, (gg,, Q+ 1 (gg,, 9.9
Proof. For any fixed iterate < f, by eqs.
B. to B.3
0, (gg, 4) (pp: Pi+1, qi q})
(pP. - Ps+1: 4: 1(+1) } + H... Pi+1: li+1
98
(pi: pi+1, qi 1 ) + D.(g. 4)) - Da(g, ((41) D. (x(+1,
eq. B.
Do(g, q:) D- 91+1) + D.(g,g4++1.
eq. B.3
D.(g, q.) Du 9:11) + D(p.+1,P)),
eq. B.2
and additionally note
(p. Pi+1. 4++1 (g 9:
41+1) >) (g941 Iis l:+1 (g 4.+1 >)
(g 9:)
0
The first equalities now follow by applying E to both sides, telescoping, and using the various earlier Bregman identities (cf. eqs. [B.1 to B.4
14

---

For the second part, for any i, by convexity of 2/.
Kpp P1-1; Vpp(p,) V 0, Kg:. 2: 9+11., which rearranges to give (gg. 9++1 / - Kge. q:3) since 0, > 0.
All that remains is instantiate the various mirror descent objects match Algorithm and control the resulting terms. This culminates in Lemma 2.1 its proof is as follows.
Proof of Lemma
The core of both parts of the proof is apply the mirror descent guarantees B. using the following choices. To start, the primal update is given by
2.
from Lemma
9: : 2.:
P++1 p: 0y: = pt + 0
The mirror mapping and corresponding dual variables (with by baked in) are
(T)) == Eswo; In
Σ exp(p(s,a)) = Σ (5()) In exp(p(s.a)) a)),
aEA
#ES aEA
[V(())(s, = (5)) exp(p(s,))
Ever exe(xx)((ss Vi(ui),
(s a) == (s)))
The primal Bregman divergence, which uses dual iterate rather than the mirror map, Dpp.pt) p:) (p) [v(p)) (g., p:l
The inner product the standard one, meaning
(p, 4) (p. a)
ΣΣ #ES
p(s,
Lastly, the dual Bregman divergence is given by
(g) (4, (n - E, (s)), g ASXA, o.w.,
100 D2 q:) (1) [ (4) Up:, q:3l]
(1g. In 9) (g: 4x)
Σ
In(gi(s, a)) + (s) + In Eexp(re(s.b) (a(s,a)- - (s)))))
4, In q Kag (T, ms).
qi
key consequence of these constructions that gi treated for any fixed s as an unnormalized policy, agrees with π; == @(p;) after normalization; that is to say, it gives the same policy, and the choice of by baked into the definition not needed by the algorithm, is only used in the analysis;
the "gradient" = Q, makes no use of it.
Plugging this notation in to Lemma B.1 but making use of two of its equalities, and the performance difference lemma (cf. eq. (1.2) ), then for any μ.,
0(1 - 7) Σ (V)(4) V=())) Σd 0 (Qi, me
T)pE
k<t
Σ
Q - - T. ) + Σ 1 n.
-x) ) 7/06
Kt
ist
0 Q - 2. πT) vt
Σ
(0.g. 9x
(B.5)
i<t
The proof now splits into the two different settings.
15

---

1. (Simplified bound.) By the above definitions and the first equality in Lemma B.1
(0.g. 9: 9x (q. qt) D=(q. 9o)
Σ D(p++1.P)).
iCt
where the last term may be bounded in way common in the online learning literature (Shalev- Shwartz 2011): since e 1 + z + =² when = 1, setting Z(s,a) == 2,(s,a) a) C. for
convenience (whereby (8, a) S 0 S 1 as needed by the preceding inequality),
D(p++1,P)
= -E
hn
exp(pit1(5,a)) In Σ exp(pi(s.a))
E Im(s.a/DDHts..a)ppll
Σ a) exp (0α((s.a)) 0 E ((.())((().))))
In
= E E
In
Σ 1 ax (xx,) 3 Ti(s, (((8,))(ss00
< E
In
-=1ss00(+++(2s0++0)000))0 3 (5. ((s,))
- Egyoot
Σ (t( + (
Σ (8, a) ((.
EEgwot Σ ni(s, (() s C2
which together with the preceding as well as eq. B.5 gives
0(1 - 7) Σ (Vi(1) V=(1))
Σ 0 20: 2,, m) 0/
Σ (0,g.. q: 9x.
ict
2 Σ Q: θ, n.
)
+ K (1) - Kot mo) - 0² Σ Cf,
K<1
sct
which gives the desired bound after rearranging.
2. (Refined bound.) By Lemma B. with the above choices and any measure w then
(Ō., T(+1) oz
(... 2 Kg.,, 9:3) ( @ nT) 05
(B.6)
and also
(.gg. qi - anl) = Dz go) - 0 kgo. qo)) + D. 9e) + Kgc + Σ
D.
K<
Σ 0 fl.t+11 - gis q++1))
1- + Eo - C 2, T+t1)
2 Kap (T, - Kog (IT, mo) (T,
i<t
To simplify these further, first note by eq. B.6 with measure bi for any state and the performance difference lemma that
Q T++1 TT. )
Q. -Qi, 1:+1 T3
+ (Qn, T,+1 - -Ts)
26, (1 7) (Vi+1 (6.) 139---11 Vi((.))
16

---

which rearranges to give
26:
Vi+1(5)) 2 Vi(d.)
V8,
1-7
which itself in turn implies
(ōitz Li, kxt1) of
2 (Qi+1 Qi Tit1) - -2 - Ei+1
=rB swatt
(Vi+1(0s) - Vi(6..)) - - E
uNT(+1((s.)) s'm(s,))
27:4
2 1
E - E1+1-
(The preceding derivation works if by replaced with any measure on states.) Plugging this all back in to eq. (B.5) gives
(1-( (+(
(Mi(1) - V=(1))
Σ
2(1 + i)e;
t(1 7)
ist
iet
Koy (T,, mp) Koy (T, To)
1
E
27c E(1-)
+ + + c+41
t0(1 - 7)
t(1 [)2
t(1 ()) ict
1-
2( + i)6s
((1 x)
i<t
where the last term may be omitted for the summation version, and these expressions rearrange to give the final bounds.
C
SAMPLING PROOFS
As in the body, this section both provides tools to control mixing times, and also a generalized TD analysis.
C.1 MIXING TIME CONTROLS WITHIN KI. BALLS
To control mixing times, these lemmas will use the notion of conductance:
4 (S), where 2s) E.es Eves 5 (5)
h SC
Sx(S)
This quantity was shown to control mixing times of reversible chains by Jerrum & Sinclair (9988) (for more discussion, see Levin et al. (2006) eq. (7.7), Theorem 12.4. Theorem 13.10)), but later proof due to Lovasz Simonovits (1990) requires chains to only be lazy, and does not need reversibility. Our chains can be made lazy by flipping coin before each step, but in our setting we can avoid this and directly use the mixing time the lazy chains to control the mixing time of the original chains.
As a first tool, note that policies are similar, then their stationary distributions and conductances also similar.
Lemma C.1. Let constant e >> O and an aperiodic irreducible policy म be given, and define a set of policies whose action probabilities are similar:
a(. 7(s
p:= Vs,a, >0.
Then there exists a constant C O so that the stationary distributions and conductances are also similar: for any E P and any state s,
1
< 5 (s. a)
SC,
> + Φ-
C 5; (3 a)
C
17

---

Proof. First note that since f is aperiodic and irreducible, it has stationary distribution 5 where necessarily (s) > for all states s. Next, recall that the stationary distribution can be characterized in terms of hitting times (Levin et al. 2006 Proposition 1.19), meaning
(8)
E miin > 0: = 8) 50
As discussed in proofs that the denominator is finite (Levin et al. 2006, proof of Lemma 1.13), let-
ting Pa and Pa corresponding the state transitions induced by taking step by and म respectively and then using the MDP dynamies to get to state, there exist r > 0 and for any states s' and any 2 therefore Pa (s, s') 2 ec 5. In fact, for a fixed s, letting Js denote the smallest exponent that (s, (s, s) > 0, then E3 [min > 0 8t meanwhile, as in Levin et al. 2006, proof of Lemma 1.13), defining of == min (t > 0: St 8).
0 so that Pa (s, >
|/000 s) Ja.
E x 80 - se Σ
Pr(T t/50 = 8]
120
joPr[T= > kjols0 =
k20
1s
jo (s)
k:0
js
J. P (s, s)
E + 80 = s)
c P (s,
where the denominator does not depend on a and thus the ratio uniformly bounded over P. (We can produce a bound in the reverse direction trivially, by using sn (s)/sa (s) I (/)) Let Co denote the maximum of this ratio and c.
Bounding the conductance is an easy consequence of the definition of Co: using Co to swap various terms depending on ı with terms depending on ât, it follows that
The proof is now complete by taking C == C3 as the chosen constant.
Next, we use the preceding fact to obtain mixing times; the proof will need to convert lazy chains to invoke the mixing time bound due to Lovasz & Simonovits (1990), but then will use characterization of mixing times via coupling times to reason about the original chain (Levin al.) 2006 Theorem 5.4).
Lemma C.2. Let constant c >>> O and an aperiodic irreducible policy ग be given, and define a set of policies
p:= Ns,a,ã(s,a) > 0. T(s π (s, a)
S se )
Then there exist constants mi, m2 > 0 so for every E P and every sup (s, sx lrv S mie mat
Proof. For any policy म, let vs denote the corresponding lazy chain: that is, any state, 2s does nothing with probability 1/2 (it stays in the same state but does not interact with the MDP to reccive any reward or transition), and otherwise with probability 1/2 uses म to interact with the MDP in its current state. Equivalently, if # s'. then P., (s, (1 + Pz (s, s)2 Define == Vs for convenience, and a new set of nearby policies:
P. (s s')/2, whereas P., s)
Py == { π V 0. J I
1
(s,
$ c).
Po(s,8')
18

---

where it will be shown that c' can be chosen that Pe 2 P. Indeed, by definition of P, since π bounded, then so is Ps/ Pr/ and in particular pick any c' O so that for any π and any pair of states ss, with Pa (s s >> 0, it holds that
Pr(s, pr(s,
è' $
sd.
To show that this choice of d' suffices, first consider the case of pair of different states states + s': then
1 Pa (s 2Pz, (s,5) (s,(s, P=(s,') e' (a 80) 2Po(8,88 P)(8,8)
-
sd;
S
P=(8,8")
whereas in the case
s if Pa (s 2 (s. then
d z Ps (s. s)
+1+ Px s))/2
(u.(s, 21,
(s
(1+ (s s))/2
8)
with an analogous relationship when Pa (s, s) S P=(8, (), which implies
d Pv, (8.8)
z c'
(s(s,s)
Consequently, it follows that Pa 2 P, and by Lemma C.1 every E P satisfies
that there exists a constant C so that
1 Su- (s.a)
C S
SC C,
$5(8,a)
(One reason for the prevalence of lazy chains is that they always have unique stationary distribu- tions (see, c.g., (Levin et al.) 2006; Lovasz & Simonovits 1990)), but as in the preceding, in our setting always have stationary distributions automatically; thus did not need to use laziness algorithmically. and can use it analytically.)
Since the conductance is uniformly bounded for every element of Pe, there exist positive constants my, my so that for every π E Pu. (Lovasz Simonovits 1990).
sup Pt (8, S2, 11 S m3 (esp(-ma)..
O, whereby holds by the above that Pmin < inf, min, Sv, (s). As such, by the preceding mixing bound, there exists to so that, simul- taneously for every π E Pv, for all 2 to. by the definition of total variation (instantiated on singletons), for every s', sup, Pt. (s, 2 Pmin/ > 0. Now consider some fixed E P. which also satisfies æ P. since Pe 3 P as above, and consider the coupling time of two sequences (zo, #1,.......) and (Vo. ......) which start from some arbitrary pair of states (xi, 9o). and thereafter each steps according to Pa (Levin et al. 2006, Section 5.2). Instead of rumning P, directly, simulate it follows: use Py.. but discard from the sequence any steps which invoke the lazy option. Then, for t 2 tg. the probability of both chains not choosing the lazy option and jumping to the same state is at least p == E. (Pmin/ /2)2 /4 >> O. As such, for any & > to, the probability that the two chains did not land on the same state somewhere between tg and f is at most
Now define Pmin
min, (s(s//C
(1 -) < (1 - p) to exp(-pt)
But this is exactly upper bound the coupling time, meaning by (Levin al. 2006 Theorem 5.4) that
sup (2o. -) (wo. 11Tv S (1 (6-p) - exp(-ppl
20.300
which in turn directly bounds the mixing time (Levin et al. 2006 Corollary 5.5), indeed with con- stants my p) too and m2 = p. Since these constants not depend on the specific policy m in any way, the mixing time has been uniformly controlled as desired.
With these tools in hand, we may now control mixing times uniformly over KI. balls.
19

---

Proof of Lemma 3.7
By definition of K, and Pe. for any Pa. letting (s', a') denote any pair
which maximizes गt a)/T(s (s, a) (which implies T('', a') > 0), and since La 9a qa 2 IIn k for any probability vector over actions,
Evss) v(s) as) a(s.a)
K,(
[(S
#ES
2 ((5))((s' In A(s'aa)
E v(s)ā(s, a) In a(s.a)
T(S,a)
(s
2 2ndd) In A(s'dd) + +v(ss)
a(sss a) #($.0)
Σ
a()
a
ata'
ass a') v(s') In
2 ((s')
then
T(s',a') a') TT8,, a²)
((s')i(s',,) a') + lnk
S exp
a(s'
#(s", a")) ) #(s", d") o).
k
< max
exp
7l6", a") min, v()) +
where the final expression does not depend on π; it follows that i(s, a)/ (s, a) is uniformly upper bounded over P.. On the other hand, f(s, 00/TTS, a) 2 # (s. a), so the ratio uniformly bounded in both directions over Pe. and let Cu denote this ratio.
This in turn completes the proof: via Lemma C.I. the ratio of stationary distributions is also uni- formly controlled, and via Lemma C.2 the mixing times are uniformly controlled. To obtain the final constants, suffices take the maximum of the relevant constants given by the preceding. Ll
C.2 TD GUARANTEES
The first step is to characterize the fixed points of the TD update, which in turn motivates the linear MDP assumption (ef. Assumption 1.3), and fairly standard (Bhandari et al.) 2018).
Lemma C.3. Let any policy æ be given, and suppose x ~ (sx, T) is sampled from the stationary distribution (in vectorized state/action form), and x' is a subsequent sample. Then, letting (Exxx" y+ denote the pseudoinverse of Exx",
(7 [Exx"] Ex(x')) [Exx"
Exr
is a fixed point of the expected TD update, meaning
ā - aa (aa- i = E
ya', ()) 70a--)))---11 ()))-r)
Moreover, under the linear MDP assumption (cf. Assumption 1.3 then x u Qx,s, ()s,,) almost every (8,a), a). Lastly, |لl|| < 2/(1 - 7).
Proof. Let X denote the span of the support of x according to its stationary distribution; since Exx" symmetric and real, then ExxT (Eax") + Hx, where 1I denotes orthogonal projection onto X.
For the form of the fixed point, it suffices to show
Ex (s 7u', vi -r) =
20

---

To this end, first note that
Erx
E
u
Err!
[Eax"]]
(xxxz))))
[Exxx']
Ezr
t2:0
Err
Exx
Err
[Exx'
Exr') + Ex(x')") [Exx') "] Err
Σ (7 [Rax"]] Bx(a'))) [Eex"] + Eer
1x Ear + [Rax" > [Eaxr"] [Ex((''))]
120
1xyErr + ylxx [Ex(x')"] ū.
Eer + [Ea(a')"] u.
This completes the fixed point claim, since
Ex ((r 72, ū) r) Eer""
[Ex(2'
(x')']
Exr
For the claims under the linear MDP assumption, using the notation from Assumption 1.3 letting X x denote the transition mapping induced by n, note by the tower property that
E (x(x')) E (E [=x))
E
xE [(X (X==)))(=] E (x(Xx Exxx' M XX
and therefore, for any Esa in the support of (which implies Tsa E 2), and since x' E X' as well,
x
x
E
[Exx"
Ex(('))) [Eax"]] Ear
120
(y [Exx"
Exx M M [Exx']] Exx'y
sa
120
E (" 1xy
120
x
(7M'x;)'
120
(s,
Lastly, since ū E x, and since (x, a)l $ 1/(1-11 due to rewards lying within [0, 1], and since 1/2 S |||| s 1, then
[ Tsal
2x a)
|||||
sup 2 2
sup 2aa F. EX
<
||||
1 1-9
Now comes the core TD guarantee. In comparison with prior work (Bhandari et al. 2018), the need for projections and starting from the stationary distribution are both dropped.
Lemma C.4. Let a policy π be given which interacts with an MDP whose states E Rd satisfy ||s|| < 1, and whose action set finite and represented as {ei...., ex}: for convenience, let x vec(se]) denote a canonical vectorization of state/action pairs, as in the body of the paper. Let Pa be the Markov chain on states induced by policy n, and assume it satisfies the following mixing time bound:
sup (t - sxllTV S me-o.
Let state/action/rewward triples (5j. Gj. j<N be sampled via interaction of with the MDP, where the initial state So is arbitrary, the random rewards satisfy E [0, almost surely, and write Iz- vec(s,a?), and let Eg denote the expectation over this trajectory.
Consider the stochastic TD updates defined recursively via uh = and thereafter
Uj+1 = =tg- -Jtt (u x. yuu 25511 r3)
21

---

and let u be fixed point of the corresponding expected TD updates with stationary samples, mean- ing
Ex (10-7'''0)) u) -r) 0,
x'-z
where x is sampled from the stationary distribution and x' is a subsequent sample, and assume
|all| $ 2/1(1-9) 7).
If the TD parameters N and are chosen according to
In N + Ium
N ki n 400 400v KN
where
c
then the average TD iterate á = N EjeN us satisfies
Ex,7 (Il - úl|² +
(E u 1)²) 3 (1 7)2
54
Proof. The structure and primary concerns the proof are as follows. The main issue is that Uj, #1 are statistically dependent; in fact, even in the unlikely but favorable situation that z is distributed according to the stationary distribution (5y, T). the conditional distribution of æy+1 given I, can still be far from stationary, even though 2 without conditioning is again stationary. The main trick used here is that 1j is so small relative to the mixing time that u, evolves much more slowly than Ty, and thus any interaction between 2; and uj can be replaced with an interaction between z; and ky-k. which are approximately independent. The structure of the proof then is to first establish few deterministic worst-case estimates on the behavior in any consecutive k iterations, and then to perform an induction from & to N.
For notational convenience, since is fixed in this proof, s is written for a. Additionally, EgN denotes the expectation over ((z),r))) replacing the Eg,r from the statement and allowing further flexibility by allowing the subscript to change.
Worst case control between any Wj and uj-k- Proceeding with this first part of the proof, define
(u) == 2, (z, ro.+1, u) IzTj,
whereby
Uj+1 U2 -TTT((ug))
||us+1 u, = n||z, (x,, - yIj, uz) - æ,رررر S n ((1 1 + 1),
[lu - x
||u+41 mill < kn (11 + 7)
Σ ||lll-
(C.1)
These inequalities will be useful in the induction as well, but now consider the first k iterations.
Controlling the first A iterations. Specifically, for any i S k, it will be established via induction
that
2 11-7) + (1 (1+ (/(0002))))) (1-7)- (1
llu; - all (1 + 1//(0000))
I<i
The base case follows since 0 and || < 2/(1 - -)). For the inductive step, since 17(1 + +7) S 1/(200k),
||u+41
x|| = ||u; ū- - yr: (x; 71 ŭ ū) Tpas:
< (1 + (11+l11 + 7)) - all + 17(1 + | +
2 2 1
< (1+ 11++1(200)))
+ +
+ 1/ 1(00k)))
+
1 -
-
1 1-7
Izi
< (1+ 1/(200)))++
+
Σ
(1 + 12000))
I 1-
I 1-
22

---

Since (1 + 1/(200))) I 2 for all i S k, then
+
8km
5
||u, ū||
- 1
(C.2)
1
This concludes the proof for the initial k iterations.
Controlling the remaining iterations via induction. The rest of the proof now proceeds via
induction on on iterations k and higher: specifically, given E {k - I,..., N- - 13, it will be shown that
26
E N [1+1 a|| + nBgN
Σ () (z a) 5 (1 11-7) 7) j=k
(C.3)
The base case = k- 1 follows from eq. an empty sum), thus consider i+1 with 1. The remainder of this inductive step will first introduce a variety of inequalities which need to hold for all j E (k,..., i), before returning to consideration of at the end.
(since the second term in the left hand side here
Before continuing with the core argument for a fixed j, there are few useful inequalities to estab- lish, which will be used many times.
Combining the inductive hypothesis with eq. (C.I
El|u, ui u) S 22 + 2n)
+ +
El|uy u + a/I2.
56
2
S 2k²17 + 2n7² (1 (1+
(1 71-
(1 (1- 7)2
i=j k
50 (1 1 71-
(C.4)
This is the explicit expression that will appear when moving between uj and uj- to introduce (approximate) statistical independence.
Next come variety of bounds on Tj. First, for any S i, using the inductive hypothesis and ||ق| < 2/(1 7), for any (x,x', r) and using the notation Tz,=', (u)) x (xc 7a'' u²) 2r,
1|10 o0 (x- ,y uj + ūi zr 2
EgN |T .r (2,))1 = EgN
< EgN4 ((1 (1 ++)))111 - x||² + (1 + 71
(C.5)
4 (26(1 + 7)² + +(1 + 7)1 + +1--))²
71
500
(C.6)
71-
Separately, making use of eq.
(C.4.
Egn](Ts(ug) TT
= EgN/ 1z (2z ug - Uy x)
S BgNNlaa 12. ||ar - 71 |lu - u1-
2,
< (1 - 7)2
(C.7)
Lastly, the convenience inequality which abstracts the application of mixing. Let B denote the expectation of (2,. Tft,,,)))) ry) conditioned on all information up through time j K, meaning (z), r.) By the coupling characterization of total variation distance (Villani 2008 Equa- tion 6.), there exists a joint distribution p over two triples (Ir 13)1) and (x, r) where
23

---

the marginal distribution of (2,,
r3) is Bij-R. k. and the marginal distribution of (2,21, is (s, rT,, and crucially the choice of lo implies
sup Pr, (e + (a, x', ,.)_,r))== - sup || (5) k.)) - 5||Tv= I me &meekk -ck S
*j-M
8j-h
(Note that (Hj) inherit the mixing time for (sy)رgN since I; vec(s,a)), and (a,)sen
are conditionally independent given (e))) Using this inequality, and moreover making use of || S 2/(1- and eqs. (C.5) and C.6), and defining Tg == Ex,x'' r,, Tz,x'r y to denote the update at stationarity,
EgN (u,-x - ū. (u Tj( ()))
= -Egj- [μj* - û, To xx) - B TT (uj- (uj-b))
= Rgg-+ {uj=+ ū, B Tx r (uj- 1) - T Taa (1g-
I Egg + 1| - ū p To, 1 (uy- To r (1)=
$ Bgs - [ ull all BBy x Ep Ta TT ( (Uj-k) - Ta (u (1]=
500A2172
V (1 11))
# (1,,²,,)) r)] II (U)-)))))) x)) - Ta
1600(1 - 7)
1 (41lug== x1|2 + 41|T||2 + 1) PE,, [1 (54111)))))))))))) # (2r, r)))
5
1600(1 - 2)) V N - (41lu)=* 16 u/l2 + 4|1u||2 +
5
2000
1600(1 7)2 V NN( 7)
3
(C.8)
(1 7)VN
Now comes the main part of the inductive step. Expanding the square and making one appeal to eq. (C.).
EgNllugHt - al|2 = EgN u, - aal2 21IlE (u, - ū, (u;)) + E TT
< REN |0 - x||2 2n7 (wj - ū. (uz)) + 500
(C.9)
7)2
To lower bound the middle term, making extensive use of eqs. (C4), (C.)) and C.7 combined with the Schwarz inequality, and the inductive hypothesis to control EgN juj=
BęN (ug ú. Tz(z))) 2 BgN (uj-k ū, T, (u1)) BeNllujee Uzl [TT5
2 E&N (uy- ū. T, x))) EgNl|uy-- u,l IIT, (u,))l
EsN| |1 u||| ([T)) (u)
2 BeN (uz-x ū, (1))))))) - > [BENNIuU5 Un 112 E.N (1;)))1
-BENN || Ui - =||" BSN [T((x) - T, TT((u=+)) 2
500kn)
250kg
2 RgN (uj-k - ū, (1)
(1- 7)²
(1 - 7)
750kg)
2 BeN (uj-k ū, Ts (1)-
(1-7)²
24

---

Now comes the key step of the proof, which uses the mixing time and introduced gap of size &o to replace ()( with Ts (uz=x); this reasoning is captured in eq. (C.8) which gives
EgN (uy-x - 0, (u)( EgN (uz-k - U, Ts (u)
EgN (uy-* ū. To(ug-b) (z())=
3
2 Eg ("j-k- ū. To (1 (1- 7)3
Again continuing with the non-constant term, and using the general incquality 2ab - a² + 62 which holds for any reals a, b, letting x ~ (s, л)) and x' ~ x and r a random reward (i.e., all the random quantities used construct Ta though will cancel), and lastly introducing T, (t) via the fixed point property in the form To (ū) = O, and the fact that x' has the same distribution as x when it appears alone.
(uj-k- - ú, To (u)
(uj-k - ú, (ug-xk)) - Ta (u))
= Eggna Uj u) (2 qe', Uj-k -u)
Eg,na' (I, Ui u)² - 7 Uz - u) ( - u)
2 Eg, (I, Ug a)² - 7/2 ((zz uz- - u) + uy - 8)²)
(1 E) (I), Uj, u)?
where
EgN Eg (I, Uj-h 1)² EgNE, (2, Ujj u)²² 2EgN (I, - 1 (2) - -us)
+ EgNEE, (Ir, Uj- - -w²)²
EggEE (z) Uj 0)²² -2 EESN sieulluj- - 0u12
EgN B| 1
2 Eg 22 Uly - a)² 2/266 1660002227
(1-
800kn
2 Eg 22 Uj u)² (1 - 7)²
Plugging all of this back in to eq.
C.9 gives
Egglluj+1 - a 12 < Egallu, u||2 t111 Bg (1, ug n)² 1600 + /
(1
which after summing over all j i and telescoping and re-arranging gives
1600kn7 + 3n/ VN
EgN (ue11 - -all²= + Σ 711 B (r, - w)² S BENN - a||² +
(1-7) 7-
j=k
f=k
25
1600kT7² + +3n/ VN
+N
(1 - 7-)
71
26
<
7)
which establishes the inductive hypothesis stated in eq.
C.3
Final cleanup. To finish the proof, a tiny amount of cleanup is needed. Adding the missing prefix of the sum from the conclusion of the induction gives
26
Esn JuN- a|12
Σ n11 E E. (z, uj 2) < JKN
+
Σ n(1 T) B. E.g. (I. - -1)²
(1
7)2
jck
26
25km7(1 - 7)
<
+
(1 7)
(1 71-
27
(1 7)
25

---

The final bound now follows by using Jensen's inequality to introduce üN in the summation term, and introducing ü within the norm term by noting the bound held for all i < and thus the triangle incquality implies || - क|| < Eien I|u, - a|//N & v27/(1 7), whose square can be added to both sides to give the final bound.
These proof' immediately imply Lemma
3.3
Proof of Lemma 3.3
Lemma 3.3
restatement Lemma C.4 but using a combination of As- (and in particular the fixed point defined in the latter) to simplify
sumption 1.3 and Lemma
C.3
Lemma
D PROOF OF THEOREM 1.4
Combining the mirror descent and sampling tools, we can finally prove Theorem 1.4
Proof of Theorem 1.4 Throughout this proof, let 8 0 denote unit of failure probability; the final bound will use the choice 5 := t 9/8 /2, although most of the proof will simply write 8 for sake of interpretation.
Define the following KL-bounded subset of policy space:
P := NPs #ES
where P. = Kuz (R, S Ink + (1 7)2
By [8] applications of Lemma 3.1 (one for each P,) and taking maxima/minima of the resulting
constants, since 5 is positive for every state, then there exist constants Pmin > 0, C1 > 0, and C2 2 so that, for any E P and any state and any optimal action E As.
(8,a)
Pmin S (s),
T(s
C2
and letting Px denote the transition matrix the induced chain on S, for any time q, (2 sxll I C2 exp(-C1g).
max SES
(D.1)
Lastly, the fully specified parameters N and 1 are
10 In Pinn Ci
N + In C2
N
where :=
Piri Ci
400 KN
Ci
which after expanding the choice of 0 satisfy
N o
Piii
N
N1
41C;
where the first two match the desired statement, and the last inequality is used below. The proof establishes the following inequalities inductively: defining Ey for convenience as
E sup (i,(s, ())ss,))2:145 (..s,)))) ()() ( 1/NTB( (Q.(s,a) 21(s)
then with probability least 1 - 2268,
Kop (T, m4) + 0(1 - 7) Σ (V) 1 Va(s))
lnk +
(IH.MD)
(1 7)3
54
E E3
Vj S
(IH.TD.I)
(1 - 7)
54
(I..TD.2
8(1 - 7)22
26

---

where a denotes the expectation over the N examples used to construct 2, but conditions the prior samples. The first inequality, eq. (HHMD), implies R, P directly, and moreover implies the final statement when i = after plugging in á = t 9/8 /2 and rearranging.
To establish the inductive claim, consider some > 0 (the base case = 0 comes for free), and suppose the inductive hypothesis holds for 1 namely, discard its 2( 1) failure probability, and suppose the three inequalities hold. This induction will first handle the mirror descent guarantee eq. (IHMD), and then establish the TD guarantees in eqs. (IH.TD.I) and (IH.TD.2) together.
The first inequality, eq. (IHMDD), is established via the simplified mirror descent bound in Lemma 2.1 To start, since (T, (T) < In for any measure v, then instantiating the simplified bound in Lemma 2.1 for the first iterations for any starting state gives
Kag (T) + 0(1 7) Σ
(V+(s) V2(s))
jei
s lak +
- - of +
+
Σ jCz
sup (5()
(D.2)
5,a
Upper bounding the second two terms will make use of upper bounds on (5j)icts but rather than using only eq. (I..TD.2), here is a more refined approach. For each j < define an indicator random variable
54vE Ej (1 - 7)
Pj P=:=11
which by eq. [H.TD.II and Markov's inequality (since 2 0) satisfics
1 S Pro, [j viE E3 VE
Pro, (
By Azuma's 's inequality applied to the i binary random variables (Fz)jei (where F, - E3, Fj forms Martingale difference sequence since Es, conditions the old sequence and takes the expectation the N new samples), with probability at least 6, and plugging in the choice 5 t 9/8 9 /2,
E Pr( +
i In S
1
Vi
1
In 2t
S 3tttnn In
2
16
henceforth discard this failure probability, bringing the total failure probability (2i 1)6. Com- bining this with eq. (I..TD.2) gives
Σ& S
Σ
83
Ej
j
1=
P==0
54vi
< Σ
+
Σ
8(1 7)2
7)
1
F
54
V3t In!
<
+ 3//2
(1 - 7)2
5
270 13/8 /T/
1
(1 7)
80 7)²
27

---

Turning back eq. (.2
this gives a way to control the middle term: since (Ts, 0 b & As,
Σ 0g
2g.
7)
max
(2 -.j.TTy Th TT 6.
jci
1
(0, -2g "jj π 5n,
Pmii
jzi
(( (Q)(s, -(,(,))
Pmin jki
(s,4)~(33:75))
+ E
Σ 8N33 dEA,
a(s.a)( (e) -Q)(,)))))(()
2C2
-
E
Pmin JJL (8)
202vi
E (Qj a) - (s))))
Pmin
Jel (1,0))((3557))
2C2vi
Σ j<b
Eg
Pmii VN1
1
28 7)
Meanwhile, for the last term in eq.
D.2). since sup,,a 2j(5,a) S 1 -),,
2,(s,a}² + (0)(s,0) - -2((,)) 27
Σ
sup (s,,
< 2
sup j<i 8.a
jai 5.
2t
+2 2 Σe
< (1 7)2
jci
20 (1 --)
Plugging all of this back in to eq.
D.2 gives
K ,T, k4)
0(1 7) Σ (v)(() Vy(s))
jzi
Ink + 0
Σ
(0, Q, -
- x)
+0
Σ sup as,
tZi
0z
J<b
s.a
In
(1 (1-
thus concluding the proof of eq. (H.MD) and the mirror descent part of the inductive step.
The TD part of the inductive step is now direct: by eq. (IHMD)) then n; P, and thus eq. (H.. follows directly from Lemma 3.3, and eq. (IH.TD.2) follows via Markov's 's inequality after discard- ing another 5 failure probability, bringing the total failure probability 2i0, and completing the inductive step and overall proof.
28


Reviews:
[{"review_id": "ppYHlmYHYuo", "reviewer": "Reviewer_UirM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written, fairly simple to follow, and provides good justifications and reminders about the overall story to the reader when going into mathematical details. I was able to follow the main story but not the specific details for proving the different lemmas. Overall, I think the motivation is strong and a cleaner analysis is definitely much appreciated. On the downside, there aren't any algorithmic insights I could gather from the paper. Particularly, is there anything a practitioner can take away from this? This might not be a concern if the paper was offering a novel result, however the question in this case is what exactly do we gain from this alternate analysis. Right now, I don't think we learn much but hopefully the authors can comment more on this point. Finally, below are some questions I hope the authors can reply to for me to understand the work better:\n\n- So the assumption that the optimal maximum entropy policy places a positive mass on every state + the KL bound allows us to use the same assumption on any policy within the KL bound. How should one contrast this with the assumption that the softmax parameterization itself places a positive mass on each state (+ is that even true)?\n\n- The KL is upper bounded by the number of actions k. Can you say something about how growing number of actions affects the KL bound? Moreover, wouldn't the horizon term dominate for common cases here? How tight is this KL bound overall? Intuitively, it seems like the KL ball should be growing smaller as we explore more of the MDP, whereas here it is fixed across all 't'. Can you provide an intuitive explanation for why this is still fine?", "summary_of_the_paper": "The paper provides a novel analysis to the linear MDP setting through an actor critic setup where the policy is softmax-parameterized. The claim is that we can avoid mixing time and exploration based assumptions by using this analysis. This is attractive since its much simpler/cleaner, but also comes with a slower convergence rate. The main steps include bounding the policy within a KL ball of the maximum entropy optimal policy through a mirror descent style analysis, followed by controlling the critic approximation error given the policy is within the KL ball.", "summary_of_the_review": "The paper is nicely written and provides an interesting alternative to analysing a linear MDP with an actor critic setup. I have some doubts about how much insight can be gained from this analysis for future work, especially algorithmically and therefore I am currently advocating for a weak accept. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "me_yYOy1xcq", "reviewer": "Reviewer_3pPx", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "With a very slow convergence rate 1/epsilon^{14}, the provided algorithm is strictly theoretical and is not intended to be applied (the authors are clear and honest on that ground).\nDespite the real author's efforts, the paper is very hard to read and requires an advanced mathematical background coupled with a vast culture on theoretical aspects of RL. The main paper and the few pages of proof that I checked seemed solid but I must admit that this paper is behind my reach.\nThat said, I find interesting for the community to get a few theoretical results on actor-critic, and I do not expect such results to be easy to handle. \n\nMinor remarks:\npage 12 line 3 \"is just ... and need not be\" -> is just ... and needs not to be\"\n", "summary_of_the_paper": "This heavily technical theoretical paper main contribution is to show that Natural Actor-Critic is \"philosophically\" implicitly biased toward high entropy policies. \nMore precisely, the key result is to show that Actor-Critic, when set as a batched  mirror descent algorithm applied on a linear finite states and linear finite actions MDP with linear softmax policies, without regularization or explicit exploration, but with properly chosen parameters, maintains its policies in a KL ball of radius 1+ ln(k) + 1/(1-gamma)^2 around the maximum entropy optimal policy (the optimal policy which samples uniformly the optimal actions) with high probability (Theorem 1.4).\nIt is worth noting that this result is obtained without global mixing assumptions on the MDP (only with a mixing assumption on the target policy). \nThis is an improvement from previous work (Khodadadian 2021) who assumed uniform mixing and provided only expectation bounds.\n\nDropping these assumption is however costly: with a step size set to 1/sqrt(t), the number of iterations required to obtain and epsilon-optimal policy is epsilon^{-14}.\n\nThe core of the paper is in the detailed proof which spans 11 pages of appendix.", "summary_of_the_review": "A highly theoretical paper underlying an interesting result on the bias of actor critic toward high entropy policies. The proofs are long and technical and assessing their correctness is behind my reach. But my bet is that it is a good and correct paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "gUrFayuP2JH", "reviewer": "Reviewer_gsmP", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the paper makes a reasonable contribution to the field. \nFirst, it explicitly uses the results from mirror descent to analyze their actor update, which confirms that once the policy is within the ball of the maximum entropy optimal policy, it remains there forever provided that the critic is sufficiently accurate. This result appears novel to my knowledge and is useful in eliminating previously used strong assumptions. \nSecond, it analyzes the converge of linear TD without using a projection, which also appears novel to my knowledge.\n\nHowever, I do have some concerns. I find the proofs are not very reader-friendly. I cannot really verify the proof of Lemma C.2, though I tend to believe it is correct. I think the coupling used in page 18 is not clearly defined. What is the distribution of z_{i, j} and can E_{i, j} be clearly defined? And I cannot get why the inequality leading to 32m / B ... holds. This is the major concern for my score 5; I'd like to raise my score if  this concern is clarified. In general, I think there are many skipped steps in the proofs, it would be good if all the proofs can be verified directly by looking at the pdf without doing extra computation.\n\nA possible improvement: I am not sure if linear MDP is a necessary ingredient for this work. In my understanding, it's used only to ensure that the TD fixed point is the true value function. I think this can also be ensured by either considering tabular setting or linear function approximation with compatible features. It would be good if the authors can briefly discuss this, after all linear MDP is a very strong assumption.\n", "summary_of_the_paper": "The paper proposes and analyzes the convergence rate and optimality of a natural-actor-critic-like actor critic with linear function approximation in linear MDPs. The most important discovery is that once the policy is within the ball of the maximum entropy optimal policy, it remains there forever provided that the critic is sufficiently accurate. Consequently, one now needs to make ergodicity assumption for only the optimal policy, instead of all policies along the optimization path.", "summary_of_the_review": "I think the paper makes reasonable contribution but the presentation of the proofs can be improved.\n\n==============\n\nThe authors successfully addressed my concerns and I increased my score accordingly.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper makes a significant contribution in the rather sparse and challenging field of convergence analyses of actor-critic style algorithms, under the linear MDP structural assumption, showing that there is a natural bias towards being high-entropy. As one of the reviewers points out, although it is unlikely that the strategy actually proposed is amenable to implementation, the paper nevertheless provides a clean and novel analysis of convergence of learning by eschewing the usual mixing time type assumptions often found in the theoretically-oriented RL literature. Based on this strength of the paper, I am glad to recommend its acceptance.
Decision: Accept (Poster)