Decision-Aware Actor-Critic with Function Approximation and Theoretical Guarantees
Authors: Sharan Vaswani
Amirreza Kazemi
Reza Babanezhad Harikandeh
Nicolas Le Roux
Venue: NeurIPS 2023 poster (2023)
Keywords: Decision-aware reinforcement learning
Actor-Critic algorithm
Off-policy updates
General function approximation
Theoretical guarantees
TL;DR: Joint objective for training the actor and critic resulting in a theoretically-principled actor-critic algorithm with general function approximation

Abstract: Actor-critic (AC) methods are widely used in reinforcement learning (RL), and benefit from the flexibility of using any policy gradient method as the actor and value-based method as the critic. The critic is usually trained by minimizing the TD error, an objective that is potentially decorrelated with the true goal of achieving a high reward with the actor. We address this mismatch by designing a joint objective for training the actor and critic in a decision-aware fashion. We use the proposed objective to design a generic, AC algorithm that can easily handle any function approximation. We explicitly characterize the conditions under which the resulting algorithm guarantees monotonic policy improvement, regardless of the choice of the policy and critic parameterization. Instantiating the generic algorithm results in an actor that involves maximizing a sequence of surrogate functions (similar to TRPO, PPO), and a critic that involves minimizing a closely connected objective. Using simple bandit examples, we provably establish the benefit of the proposed critic objective over the standard squared error. Finally, we empirically demonstrate the benefit of our decision-aware actor-critic framework on simple RL problems.

Decision-Aware Actor-Critic with Function Approximation and Theoretical Guarantees
Sharan Vaswani
Amirreza Kazemi Simon Fraser University aka2088sfu.co
Simon Fraser University
vaswani. sharana gma com
Reza Babanezhad
Nicolas Le Roux Microsoft Research, Mila nicolas@le roux, name
Samsung SAIT AI Lab, Montreal labanezhade gmail com
Abstract
Actor-critic (AC) methods widely used in reinforcement learning (RL), and benefit from the flexibility of using any policy gradient method as the actor and value-based method as the critic. The critic is usually trained by minimizing the TD error, an objective that potentially decorrelated with the true goal of achieving a high reward with the actor. We address this mismatch by designing joint objective for training the actor and critic in decision-aware fashion. We use the proposed objective to design generic, AC algorithm that can easily handle any function approximation. We explicitly characterize the conditions under which the resulting algorithm guarantees monotonic policy improvement, regardless of the choice of the policy and critic parameterization. Instantiating the generic algorithm results in an actor that involves maximizing sequence of surrogate functions (similar TRPO, PPO), and a critic that involves minimizing a closely connected objective. Using simple bandit examples, we provably establish the benefit of the proposed critic objective over the standard squared error. Finally, we empirically demonstrate the benefit of our decision-awe aware actor-critic framework on simple RL problems.
Introduction
Reinforcement learning (RL) is framework for solving problems involving sequential decision- making under uncertainty, and has found applications in games [38, 50], robot manipulation tasks [55, 64] and clinical trials [45]. RL algorithms aim to learn policy that maximizes the long-term return by interacting with the environment. Policy gradient (PG) methods [59, 54, 29, 25, 47] are an important class of algorithms that easily handle function approximation and structured state-action spaces, making them widely used in practice. PG methods assume a differentiable parameterization of the policy and directly optimize the return with respect to the policy parameters. Typically, policy's 's return is estimated by using Monte-Carte samples obtained via environment interactions [59]. Since the environment is stochastic, this approach results in high variance the estimated return, leading to higher sample-complexity (number of environment interactions required to learn a good policy). Actor-critic (AC) methods [29, 43, 5] alleviate this issue by using value-based approaches [52, 58] in conjunction with PG methods, and have been empirically successful [20, 23]. In AC algorithms, a value-based method ("critic") is used to approximate a policy's 's estimated value, and a PG method ("actor") uses this estimate to improve the policy towards obtaining higher returns.
Though AC methods have the flexibility of using any method to independently train the actor and critic, it is unclear how to train the two components jointly in order to learn good policies. For example, the critic is typically trained via temporal difference (TD) learning and its objective is to minimize the value estimation emror across all states and actions. For large real-world Markov decision processes (MDPs), it is intractable to estimate the values across all states and actions, and
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

algorithms resort to function approximation schemes. In this setting, the critic should focus its limited model capacity to correctly estimate the state-action values that have the largest impact on improving the actor's policy. This idea of explicitly training each component of the RI system to help the agent take actions that result in higher returns is referred to as decision-aware RI.. Decision-awand RL [17, 16, 1, 10, 13, 14, 32] has mainly focused on model-based approaches that aim to learn a model of the environment, for example, the rewards and transition dynamics in an MDP. In this setting, decision-aware RL aims to model relevant parts of the world that are important for inferring good policy. This is achieved by (i) designing objectives that are aware of the current policy [1, 14] or its value [17. 16], (ii) differentiating through the transition dynamics to learn models that result in good action-valle value functions [13] or (iii) simultaneously learning value functions and models that are consistent [51, 40, 35J. In the model-free setting, decision-aware RL aims to train the actor and critic cooperatively in order to optimize the same objective that results in near-optimal policies. In particular, Dai et al. [10] use the linear programming formulation of MDPs and define joint saddle-poin objective (minimization w.r.t. the critic and maximization w.r.t the actor). The use of function approximation makes the resulting optimization problem non-convex non-concave leading to training instabilities and necessitating the use of heuristics. Recently, Dong et al. [11] used stochastic gradient descent- ascent to optimize this saddle-point objective and, under certain assumptions on the problem, proved that the resulting policy converges to a stationary point of the value function. Similar to Dong al. []]], we study a decision-aware AC method with function approximation and equipped with theoretical guarantees on its performance. In particular, we make the following contributions.
Joint objective for training the actor and critic: Following Vaswani et al. [57], we distinguish between policy's functional representation (sufficient statistics that define a policy) and its parame- terization (the specific model used to realize these sufficient statistics in practice). For example, policy can be represented by its state-action occupancy measure, and we can use a neural network parameterization to model this measure in practice (refer to Sec. 2 for more examples). In Sec. 3.2, we exploit a smoothness property of the return and design a lower-bound (Prop. 1) on the return of an arbitrary policy. Importantly, the lower bound depends on both the actor and critic, and immediately implies a joint objective for training the two components (minimization w.r.t the critic and maximiza- tion w.r.t the actor). Unlike Dai et al. [10], Dong et al. [11], the proposed objective works for any policy representation the policy could be represented as conditional distributions over actions for each state deterministic mapping from states to actions [21]. Another advantage of working in the functional space is that our lower bound does not depend on the parameterization of either the actor or the critic. Moreover, unlike Dai et al. [10], Dong et al. [11], our framework does not need to model the distribution over states, and hence results in a more efficient algorithm. We note that our framework can be used for other applications where gradient computation is expensive or has large variance [39], and hence requires a model of the gradient (e.g., variational inference).
Generic actor-critic algorithm: In Sec. 3.2, we use our joint objective to design generic decision- aware AC algorithm. The resulting algorithm (Algorithm 1) can be instantiated with any functional representation of the policy, and can handle any policy or critic parameterization. Similar to Vaswani et al. [57], the actor update involves optimizing a surrogate function that depends on the current policy, and consequently supports off-policy updates, i.c. similar to common PG methods such as TRPO [46], PPO [48], the algorithm can update the policy without requiring additional interactions with the environment. This property coupled with the use of critic makes the resulting algorithm sample-efficient in practice. In contrast with TRPO/PPO, both the off-policy actor updates and critic updates in Algorithm are designed to maximize the same lower bound the policy return.
Theoretical guarantees: In Sec. 4.1, we analyze the necessary and sufficient conditions in order to guarantee monotonic policy improvement, and hence convergence to stationary point. We emphasize that these improvement guarantees hold regardless of the policy parameterization and the quality of the critic (up to certain threshold that we explicitly characterize). This is in contrast to existing thcoretical results that focus on the tabular or linear function approximation settings or rely on highly expressive critics to minimize the critic eиror and achieve good performance for the actor. By exploiting the connection to inexact mirror descent (MD), we prove that Algorithm is guaranteed to converge to the neighbourhood of a stationary point where the neighbourhood term depends on the decision-aware critic loss (Sec. 4.2). Along the way, we improve the theoretical guarantees for MD on general smooth, non-convex functions [15, 12]. As additional contribution, we demonstrate way to use the framework of Vaswani et al. [57] to "lift" the existing convergence rates [61, 37, 24] for the tabular setting to use off- policy updates and function approximation (Appendix D.2 and D.3). This gives rise to a simple, black-box proof technique that might be of independent interest.

---

Instantiating the general AC framework: We instantiate the framework for two policy representa- tions - in Sec. 5.1, we represent the policy by the set of conditional distributions over actions ("direct" representation), whereas in Sec. 5.2, we represent the policy by using the logits corresponding to softmax representation of these conditional distributions ("softmax" representation). In both cases, we instantiate the generie lower-bound (Propositions 4, 6), completely specifying the actor and critic objectives in Algorithm 1. Importantly, unlike the standard critic objective that depends on the squared difference of the value functions, the proposed decision-aware critic loss (i) depends on the policy representation - it involves the state-action value functions for the direct representation and depends on the ad advantage functions for the softmax representation, and (ii) penalizes the under-estimation and over-estimation of these quantities in an asymmetric manner. For both representations, we consider simple bandit examples (Propositions 5, 7) which show that minimizing the decision-ave aware critic loss results in convergence to the optimal policy, whereas minimizing variants of the squared loss do not. In App. B, we consider a third policy representation involving stochastic value gradients [21] for continuous control, and instantiate our decision-ave aware actor-critic framework in this case.
Experimental evaluation: Finally, in Sec. 6, we consider simple RL environments and bench- mark Algorithm for both the direct and softmax representations with linear policy and critic parameterization. We compare the actor performance when using the squared critic loss vs the pro- posed critic loss, and demonstrate the empirical benefit of our decision-aware actor-critic framework.
2 Problem Formulation
We consider an infinite-horizon discounted Markov decision process (MDP) [44] defined by the tuple (S,A, P.r. p. 7) where S is the set of states, AA is the action set, P S x A + As is the transition probability function, م E As is the initial distribution of states, r 8 A + [0, is the reward function and 7 E [0, 1) is the discount factor. For state E S, a policy π induces a distribution (-1s) over actions. also induces a measure d' over states such that d' (s) = (1
7) E+= P(, = = 8o p. ar ~ p" (-(s+))) Similarly, we define μ² as the measure over state- action pairs induced by policy π, implying that μ (s, a) = (s) p² (als) and d' = E. n² as. The action-value function corresponding to policy π is denoted by Q S : xSXA + R such that (*(s,a) == E
I = ("r((,,aa, a-)] where 80 = 8, ag = a and for T 2 O, 8741 ~ P(+ss,,a ar) and ar+1 ~ (.(71)) The value function of stationary policy for the start state equal to is defined as (x( E (.) (Q (s, a)] and we define [(r) = E E
For a state-action pair (s, a). the advantage function corresponding to policy π is given by AT a) =- (" a) (T). Given a set of feasible policies II, the objective is to compute the policy that maximizes (TT)
F Functional representation work of Vaswani et al. [57], we differentiate between a policy's 's functional representation and its param- eterization. The functional representation of policy defines its sufficient statisties, for example, we may represent& a policy via the set of distributions p" (-|s) E A for state & E S. We will refer to this the direct representation. The same policy can have multiple functional representations, for exam- ple, since p" (-Is) is a probability distribution, one can write p" (a)ss) = exp(=" exp(="(e.a))/E / exp(=" (s,a"),, and represent by the set of logits =² (s,a) for each (s,a) a) pair. We will refer this as the softmax representation. On the other hand, the policy parameterization is determined by a model (with param- eters 0) that realizes these statistics. For example, we could use neural-network to parameterize the logits corresponding to the policy's i softmax representation, rewriting 2" z'(s a) =" (s, a (0) where the model is implicit in the 2=' 2= al@) notation. As another example. the tabular parameterization corresponds to having a parameter for each state-action pair [61. 37]. The policy parameterization thus defines the set II of realizable policies that can be expressed with the parametric model at hand. Note that the policy parameterization can be chosen independently of its functional representation. Next, we recap the framework in Vaswani et al. [57] and generalize it to the actor-critic setting.
Policy Parameterization: Similar to the policy optimization frame-
3 Methodology
We describe functional mirror ascent in Sec. 3.1, and use it to design a general decision-aware actor-critic framework and corresponding algorithm in Sec. 3.2.
3.1
Functional Mirror Ascent for Policy Gradient (FMAPG) framework
For a given functional representation, Vaswani et al. [57] update the policy by functional mirror ascent and project the updated policy onto the set II determined by the policy parameterization.
3

---

Functional mirror ascent is an iterative algorithm whose update at iteration t E 10. 1} is given as: T = arg max (T; (T.) - (T, mT) where Tr is the policy (expressed as its functional representation) at iteration 6, 1) the step-size in the functional space and Dp is the Bregman divergence (induced by the mirror map +) between the representation of policies π and Te. The FMAPG framework casts the projection step onto II as an unconstrained optimization w.r.t the parameters & E R" of a surrogate function: Bu+1 = arg max (0) := (T)) V (+)()) 1 (0)),, x (Q.)). Here, π T0) refers to the parametric form of the policy where the choice of the parametric model is implicit in the (0)) notation. The policy at iteration / is thus expressed as π (0t), whereas the updated policy is given by -T- = x 1). The surrogate function non-concave in general and can be approximately maximized using gradient-based method, resulting in nested loop algorithm. Importantly, the inner-loop (optimization of (e())) updates the policy parameters (and hence the policy), but does not involve recomputing V (TT) Consequently, these policy updates do not require interacting with the environment and are thus off-policy. This is a desirable trait for designing sample-cfficient PG algorithms and is shared by methods such as TRPO [46] and PPO [48].
With the appropriate choice of & and 17, the FMAPG framework guarantees monotonic policy improvement for any number of inner-loops and policy parameterization. A shortcoming of this framework is that requires access the exact gradient (T)) When using the direct or softmax representations, computing (=) involves computing either the action-value Q" or the advantage A" function respectively. complex real-world environments where the rewards and/or the transition dynamics are unknown, these quantities can only be estimated. For example, Q" can be estimated using Monte-Carle sampling by rolling out trajectories using policy ι resulting in large variance, and consequently higher sample complexity. Moreover, for large MDPs, function approximation is typically used to estimate the Q function, and the resulting aliasing makes it impossible to compute exactly in practice. This makes the FMAPG framework impractical in real-world scenarios. Next, we generalize FMAPG to handle inexact gradients and subsequently design an actor-critic framework. 3.2 Generalizing FMAPG to Actor-Critic
To generalize the FMAPG framework, we first prove the following proposition in App. C.
Proposition 1. For any policy representations т and n', any strictly convex mirror map 4, and any gradient estimator 9. for 0 and 17 such that J + 1 is convex in n,
"7
(x) 2 ((x') (G(())))) -x) (++
1 Da- (Ve(=') (o0''''c(J(((') - -(('))))))))))))))) V(T(T))
Do (T x')
where &- is the Fenchel conjugate of & and Dg- is the Bregman divergence induced by d'.
The above proposition is a statement about the relative smoothness [34] of J (w.r.t Dạ) in the functional space. Here, the brown term is the linearization of J around π', but involves ğ(T') which can be any estimate of the gradient at T'. The red term quantifies the distance between the representations of policies and T' in terms of Do, x'), whereas the blue term characterizes the penalty for an inaccurate estimate of , [m'') and depends on t. We emphasize that Prop. 1 can be used for any continuous optimization problem that requires model of the gradient, c.g., in variational inference which uses an approximate posterior in licu of the true one.
For policy optiiization with FMAPG, (=) involves the action-value or advantage function for the direct or softmax functional representations respectively (see Sec. 5 for details), and the gradient estimation error is equal to the error in these functions. Since these quantities are estimated by the critic, we refer to the blue term as the critic error. In order to use Prop. at iteration of FMAPG, we set n' = ne and include the policy parameterization, resulting in inequality (I):
((T) J(m.) 2 (g), (0) m.) - +)) (o m.) De. ((V)m))c(VJ(m))) 9.). VO(T)
where 9. := )...). We see that in order to obtain a policy π that maximizes the policy improvement J(T) - ( and hence the LHS, we should maximize the RHS i.e. (i) learn 9. minimize the blue term (equal to the critic objective) and (ii) compute π E IT that maximizes the green term (equal to the functional mirror ascent update iteration f). Using second-order Taylor series expansion of Dø-
(Prop. 14), we see that as decreases, the critic error decreases, whereas the (: + Do m.) term increases. Consequently, we interpret the scalar e as a trade-off parameter that relates the critic error to the permissible movement in the functional mirror ascent update.

---

Hence, both the actor and critic objectives are coupled through Prop. 1 and both components of the RL system should be jointly trained in order maximize policy improvement. We refer to the resulting framework as decision-aware actor-critic and present its pseudo-code in Algorithm 1.
Algorithm 1: Generic actor-critic algorithm
Input: æ (choice of functional representation), d (initial policy parameters), w(-1) (initial critic parameters), T (AC iterations), ma (actor inner-loops), mh (critic inner-loops), 7) (functional step-size for actor), e (trade-off parameter), 0g (parametric step-size for actor), de (parametric step-size for critic) Initialization: = (0o) for t - to T' - 1 do
Estimate (m.) and form Li(w) := Da- (D((T)) - e((V. de(w)), (T()))
Initialize inner-loop: tu = W for + 0 to m. do
Vk+1 Uh V. (+(vx) / Critic Updates +/ We Ume
gr de (wx))
Form (,) = (gc, (0) - Ti)
-0, - Do (T(()))
Initialize inner-loop: for 0 to m. do
0s
11
12
oct1= Mk+1 = Us + 0a V, (Mr) /a off-policy actor updates */ = Vnn ; T++1 = ((++1)
13
14
Return πт (0r)
Unlike Wu et al. [60], Konda and Tsitsiklis [29], Algorithm does not update the actor and critic in a two time-scale setting (one environment interaction and update to the critic followed by an actor update), but rather performs multiple steps to update the critic, then uses the critic to perform multiple steps to update the actor [2. 61]. At iteration i of Algorithm 1, 9t. (the gradient estimate at TT) parameterized by w and the parametric model for the critic is implicit in the ÿe (w) notation.
The algorithm interacts with the environment, uses these interactions to form the estimate V J(m,)
and construct the critic loss function (w). For the direct or softmax representations, (mm) corresponds to the empirical estimates of the action-value or advantage functions respectively. In practice, these quantities can be estimated using Monte- Carlo rollouts or bootstrapping. Given these estimates, the critic is trained (using me inner-loops) to minimize (w) and obtain 9e (Lines 5-8). Line 9 uses ge to construct the surrogate function (0) for the actor and depends the policy parameterization. The inner-loop (Lines 10 13) involves maximizing (#) and corresponds to m. off- off-policy updates. Next, establish theoretical guarantees the performance of Algorithm 1.
Theoretical Guarantees
We first establish the necessary and sufficient conditions to guarantee monotonic policy improvement in the presence of critic error (Sec. 4). In Sec. 4.2, we prove that Algorithm is guaranteed to converge to the neighbourhood (that depends on the critic error) of a stationary point.
4.1 Conditions for monotonic policy improvement
According to inequality (I), to guarantee monotonic policy improvement at iteration 4, one must find (0, c) pair guarantee that the RHS of (I) is positive. In Prop. 2 (proved in App. D), derive the conditions on the critic error to ensure that it possible to find such an (0, c) pair.
For any policy representation and any policy or critic parameterization, there exists a (0, c) pair that makes the RHS of inequality (I) strictly positive, and hence guarantees monotonic policy improvement (J (TT > J (xx)), if and only if
Proposition 2.
(b,, (1) > (TT) gr),
- grl)
where b, E R == E. EaEa Lōcle.a V Ve(I((:)]ss.. H. E gux= VoT((:)) V (on(O,)
and A! denotes the pseudo-inverse of H, For the special case of the tabular policy parameterization, the above condition becomes equal to,
@ (T) 9.) > ([VJ(TT,) -
9.l)
5

---

For the Euclidean mirror map with the tabular policy parameterization, this condition becomes equal to ll > (ma)) gell2 meaning that the relative error in estimating (T((T)) needs to be less than 1. For a general mirror map, the relative error is measured in a different norm induced by the mirror map. The above proposition also quantifies the scenario when the critic error is too large to guarantee policy improvement. In this case, the algorithm should either improve the critic by better optimization or by using more expressive model, or resort to using sufficiently many (high-variance) Monte-Carle samples as in REINFORCE [59]. Finally, we see that the impact of a smaller function class for the actor is a potentially lower value for (by, b.).), making it more difficult to satisfy the condition. The improvement guarantee in Prop. 2 holds regardless of the policy representation and parameterization of the policy or critic. This is in contrast to existing theoretical results [41, 28, 18] that focus on either the tabular or linear function approximation setting for the policy and/or critic, or rely on using expressive models to minimize the critic error and achieve good performance for the actor Moreover, this result only depends on the magnitude of the critic loss (after updates), irrespective of the optimizer, step-size or other factors influencing the critic optimization. The actor and critic are coupled via the threshold (on the critic loss) required to guarantee policy improvement.
4.2 Convergence of Algorithm
Prop. 2 holds when the critic error is small. We now analyze the convergence of Algo- rithm 1 for an arbitrary critic error. Define dc+1 == arg max, (0), #e+1 = ((p+11)
arg max (ō.. m,) (+ + +2) Do (TT m.)].
m,)
Note that u is the iterate obtained by us-
ing the inexact mirror ascent (MA) update (because it does not use the true gradient VzJ(m,)) starting from Tr, and that the inner-loop (Lines 10-13) of Algorithm approximates this update. This
connection allows us to prove the following guarantee (see App. D.1 for details) for Algorithm 1.
Proposition 3. For any policy representation and mirror map & such that (i) + 4 is convex in m, any policy parameterization such that (ii) (0) is smooth w.r.t @ and satisfies the Dolyak-Lojasiewice (PL) condition, for O, after T iterations of Algorithm I we have that,
Do (T(TRII, ARR
1 CT
((TO) +
Σ
-DD (T)(F)) - cōs, (T(
+ Elec] Tenm
Term
(R)
where & = (TT) - 9t. _ = 1 + 1. R is a random variable chosen uniformly from 10,1,2.....7 ... 1) and e, E ((epp((mmmm) is the projection error (onto II) at iteration t.
e.
Prop. 3 shows that Algorithm I converges to the neighbourhood of stationary point of J for an arbitrary critic error. The LHS of the above expression is a measure of sub-optimality similar to the one used in the analysis of stochastic mirror descent [65]. For the Euclidean mirror map. the LHS becomes equal to [=.((TT) the standard characterization of stationary point. Term (i) on the RHS is the initial sub-optimality, whereas Term (ii) is equal to the critic error and can be further decomposed into variance and bias terms. The variance decreases as the number of samples used to train the critic (Line 4 in Algorithm 1) increases. The bias can be decomposed into an optimization error (that decreases as m. increases) and a function approximation error (that decreases as use more expressive models for the critic). Finally, Term (iii) is the projection (onto II) error, is equal to zero for the tabular policy parameterization, and decreases as m. increases. Hence, the performance of Algorithm I improves as we increase both m. and m.-
In Sec. 5, we specify the step-size 17 such that Assumption (i) is satisfied for both the direct and softmax representations. Assumption (ii) is satisfied when using a linear and, in some cases, a neural network policy parameterization [33]. For the above proposition to hold, we require that step-sizes a and a. in Algorithm be set according to the smoothness of critic (w)) and actor (&e (0)) objectives respectively. These choice of step-sizes guarantee ascent for the actor objective, and descent for the critic objective (refer to the proof of Prop. 3 in App. D for details). In practice, we set both step-sizes using an Armijo line-search, and refer the reader to App. F for details. Since Algorithm does not update the actor and critic in a two time-scale setting, unlike [29, 60). the relative scales of the step-sizes and the number of inner iterations (Ma, m.) do not affect the algorithm's 's performance.
In contrast to Prop. 3, Dong et al. [11] prove that their proposed algorithm results in an 0 (1/T) convergence to the stationary point (not the neighbourhood). However, they make a strong unjustified

---

assumption that the minimization problem w.r.t the parameters modeling the policy and distribu- tion over states is jointly PL. Compared to [2, 61, 36] that focus on proving convergence to the neighbourhood of the optimal value function, but bound the critic error in the fg or ls norm, we focus on proving convergence to the (neighbourhood) of a stationary point, but define the critic loss in decision-aware manner that depends on Da-. Since Algorithm I is not two time-scale algorithm, unlike Konda and Tsitsiklis [29]. Wu et al. [60], the proof of Prop. 3 does not require analyzing coupled recursions between the actor and critic. Furthermore, the guarantees in Prop. 3 are independent of how the critic loss is minimized. We could use any policy evaluation method in order to estimate the value function. Hence, unlike the standard two time-scale analyses, we do not make assumptions about the mixing time of the underlying Markov chain.
Compared to the existing theoretical work on general (not decision-award AC methods [62, 60, 8, 28, 22, 30, 18, 41, 9] that prove convergence for the tabular or linear function approximation settings, (a) our theoretical results require fewer assumptions on the function approximation. For instance, Prop. 2 holds for any actor or critic parameterization (including complex neural networks), while the guarantees in Prop. 3 hold for any critic parameterization, but require that 4, the surrogate function for the actor satisfy smoothness and gradient domination properties. (b) On the other hand, since our analysis does not explicitly model how the critic error is minimized, we can only converge to the neighbourhood of a stationary point. This is in contrast to the existing two time-scale analyses that jointly analyze the actor and critic, and show convergence to stationary point [60]. (c) Finally, we note that the proposed algorithm supports off- off-policy updates i.e. the actor can re-use the value estimates from the critic to update the policy multiple times (corresponding to Lines 10-13 in Algorithm 1). This is in contrast to existing theoretically principled actor-critic methods that require interacting with the environment and gathering new data after each policy update. Hence, compared to the existing literature on AC methods, Algorithm is more practical, has weaker theoretical guarantees but requires fewer assumptions the function approximation.
Instantiating the generic actor-critic framework
We now instantiate Algorithm for the direct (Sec. 5.1) and softmax (Sec. 5.2) representation.
5.1 Direct representation
Recall that for the direct functional representation, policy π is represented by the set of distributions (-1s) over actions for each state E S. Using the policy gradient theorem [53], [T))(
dd (s) Q" (s,a). Similar to [57, 61], we use weighted (across states) negative entropy mir-
ror map implying that (x _p'') = Eses d= (s) Do(p" (+1s),p" (-1s) where "(p" (-Is) =
-Ea p" (als) (g(()((ass) and hence, Do p" (-1s) = (-(p"(-1s)] (-1s). We now instantiate inequality (I) in Sec. 3.2 in the proposition below (see App. E for the derivation).
Proposition 4. For the direct representation and negative entropy mirror map, c > 0, n S
(1-7)²
27 TT
p" (als) (alo)
(o"(s..) - ( log
(a(ss) (als)
(Tx - ((Te) 2 C + Eswdre Emppree (11+)
Egndae Pamppr (+14) (s, - (r a)] + 1 log (Fumspee-11)) [exp (-clQT (s, - T a)))
where C' a constant and QTee is the estimate of the action-value function for policy Wz.
For incorporating policy (with parameters 6) and critic (with parameters w) parameterization, we note that (-1s) = (-1s, 0) and Q" (s, a) = Q" (s, alwe where the model implicit in the notation. Using the reasoning in Sec. 3.2 with Prop. immediately gives us the actor and critic objectives (0) and (w(w) respectively) at iteration t and completely instantiates Algorithm 1. Observe that the critic error is asymmetric and penalizes the under/over-estimatoo of the Q" function differently. This is different from the standard squared critic loss: Ea-d Egwd (11s) IQ (Qm a) (s, a ) that does not take into account the sign of the misestimation.
To demonstrate the effectiveness of the proposed critic loss, we consider a two-armed bandit example in Prop. 5 (see App. E. for details) with deterministic rewards (there is no variance due to sampling), use the direct representation and tabular parameterization for the policy, linear function approximation
7

---

for the critic and compare minimizing the standard squared loss vs the decision decision-awaae loss in Prop. 4.
Proposition 5. Consider two-armed bandit example with deterministic rewards where arm 1 is optimal and has reward = Q1 = 2 whereas arm 2 has reward r2 Q2 = 1. Consider using linear function approximation to estimate the Q function i.e. Q = x w where w is the parameter to be learned and æ is the feature of the corresponding arm. Let # = -2 and z2 = implying that
@w(w) = 2w and Q2(w) = w. Let p: be the probability of pulling the optimal arm at iteration t and consider minimizing two alternative objectives to estimate wt
(1) Squared loss: w!!) = arg min 2t (4) QıI? + - (Q2(w) - 02]}
(2) Decision-aware critic loss: w/ (2) = arg min (w) == ps 1Q: - (2(0(((()) (w)) + +1 - p.) [Q: - Q2(w)] +
è log (pt exp (-c (1(w] (1 pt) exp (-c(0= Q2(w)))
For Po < 3/ minimizing the squared loss results in convergence to the sub-optimal action, while minimizing the decision-aware loss (for C. > 0) results in convergence to the optimal action.
Hence, minimizing the decision- aware critie loss results in better, more well-informed estimate of w which when coupled with the actor update results in convergence to the optimal arm. For this simple
example, at every iteration t, ) = O, while the standard squared loss is non-zero at w, though we use the same linear function approximation model in both cases. In Prop. 16, we prove that for 2-arm bandit with deterministic rewards and linear critic parameterization, minimizing the decision- aware critic loss will always result in convergence to the optimal arm.
5.2 Softmax representation
Recall that for the softmax functional representation, policy is represented by the logits = ='(ss, a) (x.a==
for each E S and a E A such that y (als) = E., (x.(=" Using the policy gradient theorem, [
s.a (s) (s, a) (als) where A the advantage function. Similar to Vaswani et al. [57]. we use a weighted (across states) log-sum-eet mirror map implying that D0(2,2)) = Eees d= (s) Dz(2(s,)) (s,,)) where ((z(s,) = log(E. exp(z(s, a))) and hence, Do(2(s,) ), ()) = (L(p" (-Is). (-|s) (see Lemma 11 for a derivation). We now instantiate inequality (I) Sec. 3.2 in the proposition below (see App. E for the derivation).
Proposition 6. For the softmax representation and log-sum-exp mirror map, c > 0, 11 1177
( (A +
1 + 7
:) log
(a(as)) (als)) ]
(xx) - ((x) 2 Exnare Bampte (Yl0)
Ex Bamps
[1 (1-cl c/ [A A (s. log (I '(A"'(s.a) (s.a))
where A is the estimate of the advantage function for policy ne.
For incorporating policy (with parameters 0) and critic (with parameters w) parameterization, we exp(=" exp(="(s,a00)
note that p" (als) = Σ. "x.a="("xa'00) and Å (sx, a) = As,s,, (s/a)) where the model is implicit in the notation. Using the reasoning in Sec. 3.2 with Prop. 6 immediately gives us the actor and critic objectives (0) and Le(w) respectively) at iteration and completely instantiates Algorithm 1. Similar to the direct representation, observe that L, is asymmetric and penalizes the under/over- estimation of the ad advantage function differently.
To demonstrate the effectiveness of the proposed critic loss, we construct a two-armed bandit example in Prop. 7 below (see App. E for details), use the softmax representation and tabu- lar parameterization for the policy and consider a discrete hypothesis class (with two hypothe- ses) as the model for the critic. We compare minimizing the squared loss on the advantage: Es-at, Baapp" (-Ix) [A (s, a) - (s, alw)] with minimizing the decision-awe aware loss. We see that minimizing the decision-awar critic loss can distinguish between the two hypotheses and choose the correct hypothesis resulting in convergence to the optimal action.
Propasition 7. Consider a two-armed bandit example and define p E |0, 1] as the probability of
pulling arm 1. Given p. let the advantage of arm be equal to A := 7 > O, while that of arm 2
is A₂ == - 2|ح < 0 implying that arm 1 is optimal. For E (2 1), consider approximating the advantage of the two arms using function approximation model with two hypotheses that
8

---

depend on p. Ho A + 1-p (2+ and H1 A1 = sgn p) A
I-p ( sgn ( - p)) where sgn is the signum function. If pt the probability of pulling arm at iteration t, consider minimizing two alternative loss functions to choose the hypothesis Hy:
(1) Squared loss: He arg (Hg. 22 [Ar A 1 [A2 Ár}}.
(2) Decision-aware critic loss with 1: H. arg m
{Pe [Ai Á!) log(1 [A, A.)) pp) (1 [A Az)) log(1 [A2 Aal)].
For Po S 1. the squared loss cannot distinguish between Ho and H., and depending how ties are broken, minimizing can result in convergence to the sub-optimal action. On the other hand, minimizing the divergence loss (for any Pa 0) results in convergence to the optimal arm.
In Prop. 13 in App. E, study the softmax representation with the Euclidean mirror map and instantiate inequality (I) for this case. Finally, in App. B, we instantiate our actor-critic framework to handle stochastic value gradients used for learning continuous control policies [21]. In the next section, we consider simple RI. environments to empirically benchmark Algorithm 1.
6 Experiments
MSE-eta- 0.01
MSE-ear 0.1
AdVMiSE-ela 0.01
Adri-SE-eta* 0.1
Ourt-etar 0.1
Ours-etar 1.0
2.5
d=80
d=60
d=40
3.5
2.34
0.2-
0.2
2.0-
30000
30500
12600
20200
30000
40500
73000
N0b02
3.5-
Softmax
0.3-
3.0-
200.00
33500 400.0
10000
20/00
30000
40000
100.00
20:00
300.0
dbentton
SITHOATION
Figure Comparison of decision-aware, Adv-MSE and MSE loss functions using a linear actor and linear (with three different dimensions) critic in the Cliff World environment for direct and softmax policy representations, For d = 80 (corresponding to an expressive critic), all algorithms have the same performance. For d 40 and d 60, MSE does not have monotonic improvement and converges to a sub-optimal policy. Adv-Mo MSE almost always reaches the optimal policy. Compared to the Adv-MSE and MSE, minimizing the decision- awarre loss always results in convergence the optimal policy at a faster rate, especially when using a less expressive critic (d = 40).
We demonstrate the benefit the decision-aware framework over the standard AC algorithm where the critic is trained by minimizing the squared error. We instantiate Algorithm for the direct and softmax representations, and evaluate the performance on two grid-world environments, namely Cliff World [53] and Frozen Lake [6] (see App. F for details). We compare the performance of three AC algorithms that have the same actor, but differ in the objective function used to train the critic.
Critic Optimization: For the direct and softmax representations, the critic's objective is to estimate the action-value (Q) and advantage (A) functions respectively. We use linear parameterization for the Q function implying that for each policy Q" (s,(s, a/w) = (w. ((s.a)), where X(s, a) E Rd are features obtained via tile-coding [53, Ch. 9]. We vary the dimension E {80, 60, 40} of the tile-coding features to vary the expressivity of the critic. Given the knowledge of p" and the estimate Q" (s, alw), the estimated advantage can be obtained as: (" alw) = Q*((s alw)
Ear" (aa((((s)) (c)ss) Q* (s)) We consider two ways estimate the Q function for training the critic: (a) using the known MDP to exactly compute the Q values and (b) estimating the Q function using Monte-Carlo (MC) rollouts. There are three sources of error for an insufficient critic- the bias due to limited model capacity, the optimization error due to an insufficient number of inner iterations (m.) and the variance due to Monte-Carlo sampling. We use a large value of m. and sufficiently large

---

Monte-Catt Carlo rollouts to control the optimization error and variance respectively (see App. F). This ensures that the bias dominates, and enables us to isolate the effect of the form of the critic loss.
We evaluate the performance of the decision-aware loss defined for the direct (Prop. 4) and softmax representations (Prop. 6). For both representations, we minimize the corresponding objective each iteration t (Lines 6-8 in Algorithm 1) using gradient descent with the step-size og determined by the Armijo line-search [4]. We use grid-search to tune the trade-off parameter c, and propose an alternative albeit conservative method to estimate e in App. F. We compare against two baselines (see App. F for implementation details) - (i) the standard squared loss on the Q functions (referred to as MSE in the plots) defined in Prop. 5 and (ii) squared loss on A function (referred to as in the plots) defined in Prop. 7. We note that the Adv-MSE loss corresponds to a second-order Taylor series expansion of the decision-
loss (see Prop. 14 for details), and is similar to the loss in Pan et al. [42]. Recall that the critic error consists of the variance when using MC samples (equal to zero when we exactly compute the Q function) and the bias because of the critic optimization error (controlled since the critic objective is convex) and error due to the limited expressivity of the linear function approximation (decreases as d increases). Since our objective is to study the effect of the critic loss and its interaction with function approximation, we do not use bootstrapping to estimate the Q" since it would result in a confounding bias term.
Actor Optimization: For all algorithms, we use the same actor objective defined for the direct (Prop. 4) and softmax representations (Prop. 6). We consider both the tabular and linear policy paramterization for the actor For the linear function approximation, features and set n = 60 for both environments. We update the policy parameters at each iteration in the off-policy inner-loop (Lines 11-13 in Algorithm 1) using Armijo line-search to set Og. For details about the derivatives and closed-form solutions for the actor objective, refer to [57] and App. F. We use grid-search to tune 7), and compare different values. Our experimental setup enables to isolate the effect of the critic loss, without non-convexity or optimization issues acting as confounders.
use the same tile-coded
For each environment, MC samples or the true dynamics to estimate the Q function, and (b) on the policy parameterization. We only show the plot corresponding to using the true dynamics for estimating the Q function and linear policy parameterization, and defer the remaining plots to App. G. For all experiments, we report the mean and 95% confidence interval of J(rr) averaged across runs. In the main paper, we only include values of r E {0.01, 0.1) and vary d E { [40, 60, 80), and defer the complete figure with broader range of 17 and d to App. G. For this experiment, c is tuned to 0.01 and we include sensitivity (of J (T)) to c) plot in App. G. From Fig. 1, we see that (i) with a sufficiently expressive critic (d 80), all algorithms reach the optimal policy at nearly the same rate. (ii) as we decrease the critic capacity, minimizing the MSE loss does not result in monotonic improvement and converges to sub-optimal policy, (iii) minimizing the Adv-MSE usually results in convergence the optimal policy, whereas (iv) minimizing the decision- aware loss results in convergence to better policies at a faster rate, and is more beneficial when using a less-expressive critic (corresponding to d = 40). We obtain similar results for the tabular policy parameterization or when using sampling to estimate the Q function (see App. G for additional results).
Results:
conduct four experiments that depend on (a) whether
7 Discussion
We designed generic decision-aware actor-critic framework where the actor and critic are trained cooperatively optimize a joint objective. Our framework can be used with any policy representation and easily handle general policy and critic parameterization, while preserving theoretical guarantees. Instantiating the framework resulted in an actor that supports off-policy updates, and a corresponding critic loss that can be minimized using first-order optimization. We demonstrated the benefit of our framework both theoretically and empirically. We note that Algorithm 1 can be directly used with any complex actor/critic parameterization in order to generalize across states/actions. The theoretical guarantees of Prop. 2 would still hold. From a practical perspective, w.r.t tuning hyper- parameters, does not depend on the actor/critic parameterization. On the other hand, aa and ae are set adaptively using an Armijo line-search that only requires the smoothness of actor/critic objectives, and does not depend on their convexity. However, Algorithm does require tuning hyper-pann syper-parameter e, and we will aim to investigate automatic adaptive ways to set it. In the future, we aim to benchmark Algorithm 1 for complex deep RL environments. Finally, we aim to broaden the scope our framework to applications such as variational inference.
'Code reproduce the experiments is available httpp:://githii con/ ami http:/aaaaraaaaaaaaaaaaaaa
10

---

Acknowledgements
We would like to thank Michael Lu for feedback on the paper. This research was partially supported by the Canada CIFAR AI Chair program, the Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grant RGPIN-2022-04816.
References
[1] Romina Abachi. Policy-aware model learning for policy gradient methods. PhD thesis, University of Toronto (Canada), 2020.
[2] Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in Markov decision processes. In Conference Learning Theory (COLT), pages 64-66, 2020.
[3] Shun-Ichi Amari. Natural gradient works efficiently learning. Neural Computation, 10(2):
251-276, February 1998.
[4] Larry Armijo. Minimization of functions having lipschitz continuous first partial derivatives. Pacific Journal of mathematics, 16(1):1-3, 1966.
[5] Shalabh Bhatnagar, Richard S Sutton, Mohammad Ghavamzadeh, and Mark Lee. Natural actor-critic algorithms. Automatica, 45(11):241-2248 2009.
[6] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016.
[7] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-357, 2015.
[8] Semih Cayci, Niao He, and Srikant. Finite-time analysis entropy-rreuularized neural natural actor-critic algorithm. arXiv preprint urXiv:2206.0083: 2022.
[9] Tianyi Chen, Yuejiao Sun, and Wotao Yin. Tighter analysis of alternating stochastic gradient method for stochastic nested problems. arXiv preprint arXiv:2106. 1eth21006.3777, 2021.
[10] Bo Dai, Albert Shaw, Niao He, Lihong Li, and Le Song. Boosting the actor with dual critic. arXiv preprini 1712. 10282, 2017.
[11] Jing Dong, Li Shen, Yinggan Xu, and Baoxiang Wang. Provably efficient convergence of primal- dual actor-critic with nonlinear function approximation. arXiv preprint arXIv:2202.13863, 2022.
[12] Ryan D'Orazio, Nicolas Loizou, Issam Laradji, and Ioannis Mitliagkas. Stochastic mirror descent: Convergence analysis and adaptive variants via the mirror stochastic polyak stepsize. arXiv preprint arXiv:2110.155 15412, 2021.
[13] Pierluca Oro and Wojciech Jaskowski. How learn a useful critic? model-based action- gradient- policy optimization. Advances in Neural Information Processing Systems, 33:313-324, 2020.
[14] Pierluca D' D'Oro, Alberto Maria Metelli, Andrea Tirinzoni, Matteo Papini, and Marcello Restelli. Gradient-aware model-basee policy search. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3801-3808, 2020.
[15] Radu Alexandru Dragomir, Mathieu Even, and Hadrien Hendrikx. Fast stochastic bregman gradient methods: Sharp analysis and variance reduction. In International Conference on Machine Learning, pages 2815-2825. PMLR, 2021.
[16] Amir-massoud Farahmand. Iterative value-aware model learning. Advances in Neural Informa- tion Processing Systems, 31, 2018.
[17] Amir-massoud Farahmand, Andre Barreto, and Daniel Nikovski. Value-aware loss function for model-based reinforcement learning. In Artificial Intelligence and Statisties, pages 1486-1494, PMLR, 2017.

---

[18] Zuyue Fu, Zhuoran Yang, and Zhaoran Wang. Single- timescale actor-critic provably finds globally optimal policy, arXiv preprint 0tt::22008000448. 2020.
[19] Gianluca Gorni. Conjugation and second-order properties of convex functions. Journal of Mathematical Analysis and Applications, 158(2):293-315, 1991.
[20] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. arXiv preprint arXiv:1801.01229. 2018.
[21] Nicolas Heess, Gregory Wayne, David Silver, Timothy Lillicrap, Tom Erez, and Yuval Tassa. Learning continuous control policies by stochastic value gradients. In Advances in Neural Information Processing Systems, pages 2944 2952, 2015.
[22] Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor- critic. SIAM Journal on Optimization, 33(1):147-180, 2023.
[23] Shariq lqbal and Fei Sha. ector-attention-crite for multi-agent reinforcement learning. In International conference machine learning, pages 2961-2970. PMLR, 2019.
[24] Emmeran Johnson, Ciara Pike-Burke, and Patrick Rebeschini. Optimal convergence rate for exact policy mirror descent in discounted markov decision processes. arXiv preprint arXiv:2302.11338 2023.
[25] Sham Kakade. natural policy gradient. In NIPS, volume 14, pages 1531-1538, 2001.
[26] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In International Conference on Machine Learning (ICML), pages 267-274, 2002.
[27] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-tojasiewicz condition. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part 16, pages 795-811. Springer, 2016.
[28] Sajad Khodadadian, Thinh T Doan, Justin Romberg, and Siva Theja Maguluri. Finite sample analysis of two-time-scale natural actor-critic algorithm. IEEE Transactions on Automatic Control, 2022.
[29] Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
[30] Harshat Kumar, Alec Koppel, and Alejandro Ribeiro. On the sample complexity of actor-critic method for reinforcement learning with function approximation. Machine Learning, pages 1-35, 2023.
[31] Jonathan Wilder Lavington, Sharan Vaswani, Reza Babanezhad, Mark Schmidt, and Nicolas Le Roux. Target-based based surrogates for stochastic optimization. arXiv preprint a7X0v22302.02607. 2023.
[32] Chongchong Li, Yue Wang, Wei Chen, Yuting Liu, Zhi-Ming Ma. and Tie- Yan Liu. Gradient information matters in policy optimization by back back-propagating through model. In International Conference Learning Representations, 2021.
[33] Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over- parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59:85-119 116, 2022.
[34] Haihao Lu, Robert M Freund, and Yurii Nesterov. Relatively smooth convex optimization by first-order methods, and applications. SIAM Journal on Optimization, 28(1):333-34, 2018.
[35] Yuping Luo, Huazhe Xu, Yuanzhi Li, Yuandong Tian, Trevor Darrell, and Tengyu Ma. Algo- rithmic framework for model-bbsed deep reinforcement learning with theoretical guarantees. arXiv preprint 1r0iv:1807. 03858, 2018.
12

---

[36] Jincheng Mei, Chenjun Xiao, Ruitong Huang, Dale Schuurmans, and Martin Müller. On principled entropy exploration policy optimization. In IJCAI, pages 3130-3136, 2019.
[37] Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global conver- gence rates of softmax policy gradient methods. arXiv preprint arXiv:2005.06399 2020.
[38] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529-533 2015.
[39] Shakir Mohamed, Mihaela Rosca, Michael Figurnov, and Andriy Mnih. Monte carlo gradient estimation in machine learning. The Journal of Machine Learning Research, 21(():5183-522 5244,, 2020.
[40] Junhyuk Oh, Satinder Singh, and Honglak Lee. Value prediction network. Advances in neural information processing systems, 30, 2017.
[41] Alex Olshevsky and Bahman Gharesifard. A small gain analysis of single timescale actor critic. arXiv preprint arXiv:2203.0259/ 2022.
[42] Hsiao-Ru Pan, Nico Gürtler, Alexander Neitz, and Bernhard Schölkopf. Direct advantage estimation. Advances in Neural Information Processing Systems, 35:1 35:11869-11888 2022.
[43] Jan Peters. Sethu Vijayakumar, and Stefan Schaal. Natural actor-critic. In Machine Learning: ECML 2005: 16th European Conference on Machine Learning, Porto, Portugal, October 3-7, 2005. Proceedings 16, pages 280-291. Springer, 2005.
[44] Martin L.. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., USA, 1994.
[45] Andrew J Schaefer, Matthew D Bailey, Steven M Shechter, and Mark S Roberts. Modeling medical treatment using Markov decision processes. In Operations research and health care, pages 593-612. Springer, 2005,
[46] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference Machine Learning (ICML), pages 1889-1897, 2015.
[47] John Schulman, Xi Chen, and Pieter Abbeel. Equivalence between policy gradients and soft q-learnig. arXiv preprint (eXiv:/704.06444 2017.
[48] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, abs/1777.00344) 2017.
[49] David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. Journal of Machine Learning Research, 2014.
[50] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484, 2016.
[51] David Silver. Hado Hasselt, Matteo Hessel, Tom Schaul, Arthur Guez, Tim Harley, Gabriel Dulac-Amold, David Reichert, Neil Rabinowitz, Andre Barreto, et al. The predictron: End-to- end learning and planning. In International Conference on Machine Learning, pages 3191-3199. PMLR, 2017.
[52] Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, 3(1):9 44, 1988.
[53] Richard Sutton and Andrew Barto. Reinforcement Learning: An Introduction. MIT Press, 2 edition, 2018.
13

---

[54] Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems (NeurIPS), pages 1057-1063, 2000.
[55] Jie Tan, Tingnan Zhang, Erwin Coumans, Atil Iscen, Yunfei Bai, Danijar Hafner, Steven Bohez, and Vincent Vanhoucke. Sim-to-real: Learning agile locomotion for quadruped robots, arXiv preprint arXiv: 10332, 2018.
[56] Manan Tomar, Lior Shani, Yonathan Efroni, and Mohammad Ghavamzadeh. Mirror descent policy optimization. arXiv preprint arXiv:2005.09884 2020.
[57] Sharan Vaswani, Olivier Bachem, Simone Totaro, Robert Müller, Shivam Garg, Matthieu Geist, Marlos C Machado, Pablo Samuel Castro, and Nicolas Le Roux. general class of surrogate functions for stable and efficient reinforcement learning. arXiv preprint urXiv:2108.05825 2021.
[58] Christopher John Cornish Hellaby Watkins. Learning from delayed rewards. 1989.
[59] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine learning, 8(3-4):229-25) 1992.
[60] Yue Frank Wu, Weitong Zhang, Pan Xu, and Quanquan Gu. A finite-time analysis of two time-scale actor-critic methods. Advances in Neural Information Processing Systems, 33: 17617-17628, 2020.
[61] Lin Xiao. On the convergence rates policy gradient methods. Journal of Machine Learning Research, 23(282): 2022.
[62] Tengyu Xu, Zhe Wang, and Yingbin Liang. Non-asymptotic convergence analysis of two time-scale (natural) actor-critic algorithms. arXiv preprint arXhv:2005.03553 2020.
[63] Rui Yuan, Robert Gower, and Alessandro Lazaric. general sample complexity analysis of vanilla policy gradient. In International Conference on Artificial Intelligence and Statistics, pages 3332-3380. PMLR, 2022.
[64] Andy Zeng, Shuran Song, Johnny Lee, Alberto Rodriguez, and Thomas Funkhouser. Tossingbot: Learning to throw arbitrary objects with residual physics. IEEE Transactions on Robotics, 36 (4):1307-1319, 2020.
[65] Siqi Zhang and Niao He. On the convergence rate of stochastic mirror descent for nonsmooth nonconvex optimization. arXiv preprini 18Xiv:1806.04788 2018.
14

---

Supplementary material
Organization of the Appendix
A Definitions
B Extension stochastic value gradients
C Proofs for Sec.
D Proofs for Sec.
E Proofs for Sec. 5
F Implementation Details
G Additional Experiments
Definitions
[Solution set]. We define the solution set X for a function f as X = {x*12* E arg min f(x)]
[Convexity]. A differentiable function f is convex iff for all e and w in dom(f)
f(v) ((w) + (Vf(w), --w)-
(Convexity)
[Lipschitz continuity]. differentiable function f is G-Lipschitz continuous, meaning that for all v and w and constant G
ff() - f(w) < G - w|l
[Vf(()) G.
(Lipschitz Continuity)
[Smoothness]. A differentiable function f L-smooth, meaning that for all and w and some constant L
L |l w
f(u) < f(w) + (Vf(w), w) 2
(Smoothness)
[Polyak-Lojasiewiizz inequality]. A differentiable function / satisfies the Polyak-Lojasiewicn (PL) inequality if there exists constant Up > 0 s.t. for v,
( [f(1))
(PL)
where f the optimal function value i.e. fr :- f(x²) for x² E X
[Restricted Secant Inequality]. A differentiable function f satisfies the Restricted Secant Incquality (RSI) inequality if there exists constant pr > 0 that for all
(Vf(v), v- 0p) pr 1|u
12
(RSI)
where Up is the projection of e onto X
[Bregman divergence]. For strictly-convex, differentiable function 4, we define the Bregman divergence induced by & (known as the mirror map) as:
Da v) == (ww) - ((v) (V) w v).
(Bregman divergence)
|Relative smoothness]. A function o-llltiivlyy smooth w.r.t. Do. iff f + p is convex. Furthermore, if is p-relatively smooth w.r.t. Φ then, (s(w) - (v) - (VS(v), w w-v)l | S DD Do(w, v).
[Miror Ascent]. Optimizing maxzex (z) using mirror ascent (MA). if is the current iterate, then the update at iteration & (0, 1...., T with step-size f) and mirror map given as:
Tt-1 = arg max (V](at)), x)
Do (z, 2it)
(MD update)
7

---

The ahove update be formulated into steps Bubeck [7, Chapter 4] as follows:
gt+ (V (V4(2t) + na (zx)))
(Move in dual space) (Projection step)
-t-1 1 = arg min (Do (x, M++1)
=ex
B Extension to stochastic value gradients
In Sec. 5, we have seen alternative ways to represent a policy's 's conditional distributions over actions p" (-|s) for each state s E S. On the other hand, stochastic value gradients [21] represent policy by a actions. Formally, s are random then policy ı is a deterministic map from S x X + A. This corresponds to
variables drawn from a fixed distribution the functional representation of the policy, and is particularly helpful for continuous control, i.e. when the action-space continuous. The action a chosen by π in state when fixing the random variable g = c, is represented as TTs, c), and the value function for policy æ is given as:
((x) Σ (s) (()==<d()
I r(s, ((, de Jeax
(1)
and Silver et al. [49] showed that 0J(T) d= (s) n² a)) a== In order characterize the dependence on the policy
(5(
parameterization, we note that (s, as,, c, where A are the model parameters. For a fixed we will use a Euclidean mirror map implying that (o m²) Exes d (s) (T c), rs,,,) and choose ((T((s, e)) = (s, <) implying that & (s, c), x' c) = [m(s c) - c)), In order to instantiate the generic lower bound in Prop. at iteration t, we
prove the following proposition in App. E.
Proposition 8. For the stochastic value gradient representation and Euclidean mirror map, > 0, such that J + 1 is convex in π.
1
( ( 1 (T. =(S,c))
(TT) J(T,) C E Eendr Beax
v.QTi (s, a) (=)) (s,E)
-
2 17
c
Es Bondri Eenx
VaQ" (=.) V.Q= (s, l== (
2
where C' is constant and VaQ lam is the estimate of the action-value gradients for policy at state and a (s( e).
For incorporating policy (with parameters 0) and critic (with parameters w) parameterization, we note that T(s, = T ((s, s and V.Q=i (.. (s.)) VaQT (s, alw))a=m(sse.)) where the model is implicit in the notation. Using the reasoning in Sec. 3.2 with Prop. 8 immediately gives us the actor and critic objectives (L,(0) and Lz(w) respectively) at iteration and completely instantiates Algorithm 1. The actor objective is similar to Eq (15) of Silver et al. [49], with the easier to compute QTe instead of Q", whereas the critic objective is similar to the one used in existing work on policy-aware model-based RL for continuous control [13].
16

---

C Proofs for Sec. 3
Proposition 1. For any policy representations т and v', any strictly convex mirror map D. and any gradient estimator 9. for <>> 0 and such that J + 1 is convex in π,,
( 2 ((x) --)) (++))) ) Do((,T') Da(t))
De- (V((=') -
- -(("') vQ(TT)
where &* is the Fenchel conjugate of & and Dx- is the Bregman divergence induced by o*.
Proof. For any such that J + L is convex, we use Lemma 2 to form the following lower-bound,
J(x) 2 ((7) (VJ(T'), (TT x)) 1 (T) = J( + (0(=))) (क - x²)) (VJ(=)) - -
77
1 (T(T,
71
Defining 8 = (=((=') 3( ) and assuming that cō small enough to satisfy the requirement for Lemma we use Lemma 1
with 6, = π and y/ = π¹
- (g( (TT T¹)) 1 DO(T, - 1 c
[Do(T, (') D&r -6,
(2) :)
Do D)((, - (Vo(T') -()"))))))(((--))) vo(TT)
J(T) -
Lemma 1 (Bregman Fenchel-Young Young). Let x E y" y V. 3/ V. Then, for sufficiently small c > 0 and x s.t.
(Vol') - cx] E V, we have
(ー 2 - _ Do((vv') (') + D&. (Volv) ca, vo(o')
(2)
For a fixed y/ this inequality is tight for y = arg min, {1r, 5¹) (v,
Proof. Define f(v) = (2, 1/) + Do(,v') If arg min ((y), then,
45(y" - Voly") Vo(y') cx
y (Vo) Voy')) - cxl = y" VVoVV'VV cz)
Note that according our assumption, y² E y. For any y.
f(v) 2 f())= = (x. - v1) + Do("",)))
(3)
In order to simplify (y"", ,,, ,.), we will use the definition of 0² (z). In particular, for any y.
o(y) = max [(2, v) o² (=)] : zz = arg max [(2, 4) x²(2) = y= Vz" = = x" =Voio(
= p(v) (Vo(v).v) v) 8² (Vo(v))
(4)
Po("".1) = -(() o(5)) (V - -/) = =I(Voly") ),²" )'(Vo((")) - - (Vol'') - -//
- (using Eq. (4) to simplify the first term)
Let us focus on the first term and simplify it,
(Vo(")) of (Vo("))) = (Vo (V - VoVV - cx)) -
(V6(V) - cx)))
=
cz)) (For any z. vo(Vo'(x)) = 2)

---

Using the above relations,
( - -o/ -
- -FV o11)
- - 5
(VVl))), (o>v)) -co]) - o Vo' - cxl}
='([Vo(y') cal) - (/69- - (V9()), 44 (Vdp)) -cx] - 1/)
Do(y" v/ c((x, V (Vo(y) - (le) - 80 (VV''( cx)) (000 + (Vo()).))
Using the above simplification with Eq. (3),
f(v)= 2 (r.v" v/) + -- - cx)) - x (VV()) cx)) -00) + (Vo()').)))
(x.15" - 1/> - (c, --(ax (x.1/) + (x, Vo
cm)) 16 (Vo()) czo) + 0(y') - (6(''), v)]
cxl) (2) (29AL- - (am 10 ((V((')) cx)) +
(x, ((Vo (o)) (06 (V9()),1)))
Using Eq. (4), Q(5') (V9()) -
( = )00) - -
= f(y) 2 la,, 9/) 1 66 (VOA -czl) (V9(1) = 1 - + + - -
1 c( v²) +V ((V) cm)) of (V961)) (Vo' Voly') Vo(9")
+ (V> vo(0) c vo(l))
+ = f()) -
lo v)
- cz, -z
-cx') - Vd
cr, vo(1))
Using the definition of (w)),
(v. - 8/) + -Do(v.')) 2- D' cor co,
Dí (Vo(')))) 1 - -
= (x,y s1) 2
cz, vo(y))
Lemma 2. Jf + 16 is convex, then, ((T 1 reelatively smooth w.r. to Da. and satisfies the following inequality,
J(T) 2 ((z) + (V)) - 1 D)(TTTT))
x--
Proof. If + 14 is convex.
7
J + Φ6) (T) 2 J 1 ()) (x)) + x, V
1 Φ (x))
J+
7 /
1
J(T)= 2 J(T') ( 7. J(T'))
(Φ(T) ((T') -V=0(="),=-=))) x')l
1
- 1
-
-D((T,T))) x')
11
18

---

D Proofs for Sec. 4
Proposition 2. For any policy representation and any policy or critic parameterization, there exists a (0,c) pair that makes
the RHS of inequality (I) strictly positive, and hence guarantees monotonic policy improvement (J (J(+++1) > ((Te)), if and only if
(b,, b.) (m)) 9.), ((m)) [V]
- -9e))-
where b, E R := E.Es EPEA l0. Vo Vel He E R := ((,) (TT) (oT and H. denotes the pseudo-inverse of Hee For the special case of the tabular policy parameterization, the above condition becomes equal to, ( ( 9t) (T. 9.). [V (V 9.])
Proof. As a warmup, let us first consider the tabular parameterization where z(0) = SAA In this case, the lower-bound in Prop. 1 is equal to,
- -0.00) Do. (v
((x) J(Te) (ec, -0)
(v+(0)) (V)( 2.). v
We shall do a second-order Taylor expansion of the critic objective (blue term) in e around 0 and a second-order Taylor expansion of the actor objective (green term) around 0 = 0.. Defining 8 = VJ(O.) gt.
[ + )) -0-0- 0.) ( 0.) (0, V (Vo(m))) + o(c) ol10 0ell2),
RHS (gr, 0 0z)
(Using Prop. 14)
where occ) and o[100 0z l12) consist of the higher order terms in the Taylor series expansion. A necessary and sufficient condition for monotonic improvement is equivalent finding a (0,c) such that RHS is positive. As c tends to the 0 maximizing the RHS is
8" = 0 + c c+
en
[V2
With this choice,
RHS-
(gt, [0)) 9t) - -
(6 8) + llc)
(o(1l0-011p) - -..1/3 is subsumed by o(c)
2
(0. [())
Φc) c - (V +
1
1
0)
(āc, [V2)(00)] 9.) +o(c)
2
1 1
o(c) term
(9. [+)) 9t) (8. (8. 6 (V)( +
(Subsuming the additional o(c) term)
2
(g., (0)) -1 9t) (6, (Vo((V(TTT) (T)) 8). i.c. there exists an e > Os.t. (Ôt, [+)(0))) 9.) = (6, v²o* 8) ce
e, then, RHS- 2 + o(c). For any fixed 0. since /cc)/c
0, there exists neighbourhood (0, cx) around zero such that for all e in this neighbourhood, ofc)/c and hence o(c) kc. Setting x ç. there is e such that
CE > 0
RHS
Hence, there exists a c E (0, min cx such that the RHS is positive, and is hence sufficient to guarantee monotonic policy improvement.
On the other hand, if (gr, [0,)) -1 9t) < (8, V (Vo 8), i.e. there exists an > s.t. (g., ( gt)
(8, 0 (Vo(m.)) 6) - e, then, RHS = 2 guaranteed. Hence, (gt. 22 ge) (5, V (Vo(T.) 8) is necessary and sufficient condition for improvement.
-x o(c) which can be negative and hence monotonic improvement can not be
Let us consider the more general case, and define SA, ÿe Rmm1, x(f) E IR is function of R Rewriting Prop. 1,
((T) - (TT) 2 (gr, (0) (0.)) ( 2-+ (0) Dx- (V)(m)) - c(v.(mm))) 9.). (

---

As before, shall do a second-order Taylor expansion of the critic objective (blue term) in e around 0 and a second-order Taylor expansion of the actor objective (green term) around 0 = Oz. Defining á = v.((,) - -r- From Prop. 14, we know that,
D ( - ((()(m)) 9el, V
c (ó. 2 (Vo( o(c)
2
In order to calculate the second-order Taylor series expansion of the actor objective, we define (or( E IRmxx as the Jacobian of the 0 : π map, and use [o]o(( Rixa for E [m] to refer to row
m
T
(0) - n (0.))
Σ Mc
Vo(m(O.))
0.) nx1
Lock 1x1
(0 (- +olll0 - 0.1l2)
1xn
18n
ax.
nxl
where o110 - 0z [2] consist the higher order terms in the Taylor series expansion. For expanding the divergence term, note that (=T) (0,)) - (()( (T(()))) (V)(T(0)), x0.))
( (() = V [ (OT(O))) (0- - 0c)
1mm
mXn
nx
1
m
0 0₂)
(o,) (TTTT) VoT
(0))l,
(0 (0-0.) +o 0ell))
2
1x1
1
x() - x00))
V Vo(TT))
V (o)((
(0 0.)
0 0e)
V Vo((T))
Volm(
(0 (0-0) 02) +o(110 0c112)
2
1x1
1xn
nx1
1xn
1x1
nxn
nx1
Putting everything together,
RHS-
Locls
V (o()(()))k
(0- 10-01 0i)
1x1
Ixn
nxl
1
m
-++1 c
!
(0 0²)
[ocls (o)T(
Ver(O.) (ZO(T))
VeT(
(0-a.
2
Ixn
nxn
nxm
mxm
mxn
nxl
c
(6, 2 50 ((((T)) 5) + o(110 - 0.112 + o(c)
2
Defining by : Σm loe]s Vo(T(())]: and H, == (oT(.,) (.O(T)) (OT(
1 Σ (l01l, VolT(0)1.)
(1++)
1 + ( (10 0.), H4, (0 0.)) - (8. (Vo(()) o(110 0.112) + o(c)
RHS- (be, 0 0.) 2
As a sanity check, can be verified that if x (0) 0, H, = ( + ! (2 and by = فr. and we recover the tabular result
above. Notice that (10-8)) 0z), [++1) Em (Lo.). (ll)()))) (0 0.) o(c) as goes to zero Subsuming this term in
o(c).
RHS- (b,,0- 1 1 + :) 0,, 0,) -
c (8, 4 ( -010 o(c)
where H, := VOT((,)) V (ZO(T)) (f)( As before, a necessary and sufficient condition for monotonic improvement is equivalent finding a (0, c) such that RHS is positive. As e tends to 0, the O maximizing the RHS
0- 0,
en
i1
b.
(c 1/)
With this choice,
RHS-
1
1
(bes
H1
b.)
c (6. V2 (V 8) + d(e)
(o[1l0 - 0.11)) subsumed in o()))
2
1
+
1
2
7
20

---

As in the tabular case, since + is o(c), can subsume it, and get that,
RHS 2 (be. He b,) 2 (ò. V (Vo(T)) + occ)
Using the same reasoning as in the tabular case above, we can prove that
(be: H. by) (6, V 65 (Vo(z.))
is necessary and sufficient condition for monotonic policy improvement. Finally, Gorni [19, Eq (1.5) which shows that 22 (V)(t)) = [v))(=)]] and complete the proof.
C
D.1 Proof of Prop. 3
The following proposition shows the convergence of inexact mirror ascent the functional space.
Proposition 9. Assuming that (i) J + is convex in æ, for a constant > 0, after T iterations of mirror ascent with
2 + we have
Du (T RR)
[J(TT) - [(TO]] +
T-1 Σ
ED Vd(T.)) -v))))))VV())----)) ((+.)), vo(
2
CT
where (= 2 and R is picked uniformly random from (0, 1,, ... T 1)..
Proof. We divide the mirror ascent (MA) update into two steps:
Vo(T(+1) V)((F) + ())()))))))))))) = [(TT) - [o( Vo(T.))
#t+1 arg min Dx (TT, #t+1).
We denote the above update as Tt+1 = MA(T,). Using Prop. with क = Ee+1, H/' = =mp-
{1 + 1 Da (a(
1 Do- (Vo(fe) - -( Vo(m.)
((T++1) 2 (wt + (( ( (( FT) -
(-+ Do Do (7142,,771) -
2 ((a.) + (Vo(H11) - - -i)) 7111
#et1
(Using the update)
( Da (T(+1.
((a) + T/
DDo ( Fe) + ( #1+1) - D& ( +(+1)}
(using Lemma 4)
Do (Fet1,,, #++1)+ (
-((t) +
(Do #1+1)
Do(ūrt1, tt) -
T/c
1/ c
=AA
1
2 J(+.) +
Do (Tt+11, 7t) -
(A 2 0 since #441 is the projection of # onto IT)
1/6
1
2 2(m) +
+
Ttr) -
(Sinc 1/1h = 2/n + 2/c)
21

---

Recursing for T iterations and dividing by 1/5, picking R uniformly random from 20, - 1} and taking expectation we get
D& (..
1
T-1
E
5²
=
2²T
BD
(T 11)
1=U
( [
+ E Ee
ÇT
T
[((*)) [[TO]]
Et=
T- EcG
+
ÇT
T
[((TT) -[TT)) [[(")))[TTo)))) +
Σ
ED
(( Vo(T.)
ÇT
1=
Compared to Dragomir et al. [15], D'Orazio al. [12] that analyze stochastic mirror ascent the smooth, non-convex setting, our analysis ensures that the (i) sub-optimality gap (the LHSS in the above proposition) is always positive, and (ii) uses a different notion of variance that depends on Dæ-
Similar to Vaswani et al. [57], we assume that each π E 1I is parameterized by 0. In Algorithm 1, we run gradient ascent (GA) (0) to compute T = 7 (02+1) and interpret the inner loop of Algorithm as an approximation to the projection step the mirror ascent update. We note that (0) does not have any additional randomness and is deterministic function w.r.t 0. Note that #++1 where π. = TT(a). Assuming that (0) is smooth, and satisfies the PL condition [27], we get the following convergence guarantee for Algorithm 1.
Proposition 3. For any policy representation and mirror map + such that (i) J+ L convex in æ, any policy parameterization such that (ii) (0) is smooth w.r.t and satisfies the Polyak-Lojasiewice (PL) condition, for > 0, after 7 iterations of Algorithm we have that,
E
Do (TRR +1, TR)
-
Σ t=0
1 ED- ( - cde, V + Biee]
Term
Torm
where 8, = V - gr. 1 =
a. R is a random variable chosen uniformly from 1,, - 1} and e E 4
Oeexp (-m.)) the projection error (onto IT) at iteration
Proof. For this proof, we define the following notation:
x (0t)
(2-+ -
(()) = =(m,)) + ((m,)) (T(()
- -T)) (=T()
Do (T(
0,41 == arg max (0)
1 DT T() = MA(TT)
Mt+1 = (0(+1) = arg max (g. π m.))
mEll
17
(Iterate obtained after running step of mirror ascent starting from TT)
811 GradientAssem((((().ee) m.)
M++1 := (8(+1))
where GradientAscent( (0), fc, m.) means running GradientAscent for m. iterattions on (0) with the initialization equal to
8, Since assume that é, satisfies the PL-condition w.r.t. 0 for all t, based the results from Karimi et al. [27], we get
(( (e(0++1) I exp(-c2ma) (le(0)+1) - (e())
22

---

where c12 '2 are problem-dependent constants related to the smoothness and curvature of &,, and ez is the approximation error diminishes as we increase the value of ma- Following the same steps as before,
1
J(T++1) 2 J(m)) + ((m)) T (m - TT)
+
Do (T (0++1),
(Using Prop. 1)
7
1
2 J(m)) + (m,)) ( (0(+1) - mt))
+
Do (T - cc
(Using the above bound for GA)
1
(1
= =m(m)) + (( (Te+1 T&)
-
+
è)
Do (=( Te) - -x
11
2 ((+)) + (+ - [T(T)), - -m)) - 1 -
1
Do (o - -G
(Using the MA update)
1 /t (D + (TT T(+1) De (Te+1: +++1)}
( (++ Do (Te+1, - El
2 ((T)) +
:) De ( - (using Lemma 4)
1
(4 1 - 1/2 " c)
= -((t) +
(Do(Tes T(11) - Do (T
T/1
--1) 1) Dæ (T((())) - - - Ee (A 2 0 since #441 is the projection of Ā441 into the simplex)
2 I(TT) +
1
2 ((T)) +
Do (1) - - Et
( (setting T/e s.t. 1/th 2 2/n + 2/c)
1
Recusing for I' iterations and dividing by L/C, picking R uniformly random from 10,1,2,... T 1} and taking expectation we get
Da (,R+I, )
1
T (T+11 Re)
E
ED
2T
1=
[[
J [mOO]
+ Ei=
I--
Res
Et=o Rei
+
CT
CT
CT
[J(**) -J(To)
21= Beg
2 T
0 Eee
--
<
7T
7T
7T
E
D& DT(TRRI,TT) TR)
<
[J(+T) - -m(o)]
EDo
((m.)), vo(T))
Σ Eer
CT
C
Note that is possible to incorporate a sampling error (in the distribution dm across states) for the actor update in Algorithm 1. This corresponds to additional error in calculating Dé, and we use the techniques from Lavington et al. [31] to characterize the convergence in this case.
23

---

D.2
Exact setting with Lifting (Direct representation)
Recall the mirror ascent update in the functional space.
R++1 = arg max J(Te) + ( to) Do( 9%
*Ell
For the direct representation, we define ाt = p=(()),, [(Te)(o,)) = (s) and (T(
Σ. dm)(s) Do(a" , m.) Rewriting the MA update.
J((Te) + Σ (s) (QTh -TTe) DT(TT" mT²))
T++1
arg max (TE
T
(8, T&²) Do(=",a=) (=(="===²)
1
arg max x'EAA
(Can decompose across states since (s)((s) 2 0)
T/2
For each state and Q (s..) we define the set II = { xt' E arg max, (Q" i.c. set of greedy policies
w.r.t. (**(s,.). .s, Similar to Johnson et al. [24] we define n/ as follows
T/
max min (T mi) FEllY
(5)
where > is constant. Now we consider the policy parameterization, x = (0). We assume that the mapping from 0 + is Lg Lipschitz continuous.
(())) = ((T)) + Σ (5) (s,,)))) -T(" T/e Do( TT²)
P.41 = arg max (0)
0. Gradient(sceen((((().. m)
#t+1 = (0++1)
Tr+11 10++1)
GradientAscent(/ (0), 0,, m) means that we run gradient ascent for iterations to maximize &, with 0g as the initial value. We assume that & satisfies Restricted Secant Inequality (RSI) and is smooth w.r.t. 0. Based on the convergence property of Gradient Ascent for RSI and smooth functions [27], we have:
0 oc+1 1|2 s O(exp(-m))
|l T1 (00+1) x x(eet1) s 12 | let1
2 S == =(exp(())
approximation enor
(since (ff) is Lipschitz continuous)
Furthermore, we assume that |[ tt4 by for all which represents the bias because of the function approximation. Before stating the main proposition of this section, we restate Johnson et al. [24, Lemma 2].
Lemma (Lemma Johnson et al. [24]). For all (s, a) E x A we have
R (8,a)= a) 2 QT (s,a).
24

---

Now we state the main proposition of this part.
Proposition 10 (Convergence of tabular MDP with Lifting). Assume that (i) (e) is smooth and satisfies RSI condition, (ii) (0) is Lx-Lisschizz continuous, (iii) the bias is bounded for all l i.e. || - 1112 s by. (iv) (sQ -)l S for all π and By setting 1/2 in Eq. (5) and running Gradient Ascent for iterations to maximize we have
[| (oT) "I"(((++))
1oo ( + ΣEr
9 - let - bu] (at + 1 --7
where x² is the optimal policy, x² refers to the optimal action in state s. Here, ea = O(exp(-m)) is the approximation error
Proof. This proof is mainly based on the proof of Theorem 3 of Johnson al. [24]. Using Lemma 3 and the fact that x 0, we have (Q**(s,))) -), mi-1) I (Q===(ss ai+1) = (= Using this inequality we get,
(Q (s, x # 2 (s. Jx(+++1)
(Q" (s, x 1Q" (s, - (T(42)) 2 -
(s, 1| + +z((T)) - (F++1) - (1I((T)) - J( + J=(TT) J3 (
(Holder's inequality)
The last inequality is from the definition of and J as follows. For any action a,
(7) - Q (s,a) = P((d(s, (
$ P ([[() - (TT )l
S { 1(T))
From the above inequality,
-711J(m)) - (1T)) + Jo(=") - (o(41))) S (Q (8, T- - ait1)
S (Q" .), Pi: #Ht1)
(For any pt E II;))
Do (pi, m²²) Dolpi 7f+1) - Do(Ti+1, T2²)
1/e (Using Lemma 5 with d Q* (s, -), y 78+11 př)
Do (pi, xT*)
Vk
Do Tt²)
>>][((TT) - ((T'(())))))) )I + Jo(=)) (1(+1) <
min
Sa a (Based on the definition of n/' in Eq. (5))
pt
Tk
- ->/[[(T)) - [[T')| + (T') (T(4)) S c + J. - (Te+1)
(Since s an arbitrary state, changing s s' for convenience)
= =a =a Σ d (8)
(Q) (Q*++1 (s, TH+1 T++1*) ")
(Using performance difference lemma 6 with the starting state equal to s')
1
sat
a (s) 11 (s. [|, Ts+1")
1-7
(Cauchy Schwartz)
<at +
9
Σ
d m= (s) || m++1"l
1 7
Sat +
q
Σ
m (8) [| # + |1 -T+11 I1]
g
<a +
(er + b.)
25

---

(PL) condition, we use the gradient ascent Since the above equation is true for all s' we have:
[|[(*)) J Sy11J(me) J(xx lloo + +
q
(et + be)
1 7
Recursing for iterations we get:
T
- - S S [|((+))- J (ee
q - les - bel)
+ 1 1-7
We control the approximation error e by using larger m. The bias term by can be small if our function approximation model is expressive enough. Ct an arbitrary value and if we set e = 7'c for some constant c 0, then ( = Te and therefore Te can diminish linearly. The above analysis relied on the knowledge of the true Q functions, but can be easily extended to using inexact estimates of Q? by using the techniques developed in [61, 24].
D.3 Exact setting with lifting trick (Softmax representation)
In the softmax representation in the tabular MDP, consider the case that is parameterized with parameter 0 R". In this setting & is the Euclidean norm. Using Prop. 1, for such that + 4 is convex we have for a given Tr,
1
((x) (m) + (VJ(T)), -ma)
D& ( mT)
17
1
((m) + (VJ(T))) π - -
|| TT 11
(Since o(.) = $111111 -1-112)
2m
hh(T))
we maximize h(x) w.r.t we get
#e+1 arg max (N(T))
Fe+1 me V
Mei et al. [37, Lemma 8] proves that (T) satisfies a gradient domination condition w.r. the softmax representation. In particular, if a" (s)) is the optimal action in state and == ming min, (a (s}[ss, they prove that for x,
vs
[V,]( 2 [ J(T)
Consider optimization in the parameter space where (x(0) = J(TT) (V) - x(0.)
(o(m)(),=(0.)).
0-1 arg max (0)
6
#.- 1 π (6++1)
0 == Greetent 0,, m)
Tc-1 (0.+1)
((ntientAscent(((()))) 02, m) means that gradient ascent for iterations to maximize & with 0, the initial value. Assuming that & is Lipschitz smooth w.r.t. 9 and satisfies the property for PL functions [27] to obtain,
h M(++1) MMT41)) (0.+1) ((0c-1) S e :=== ((xp(((mm
approximation error
26

---

Proposition 11 (Convergence of softmax+tabular setting with Lifting). Assume (i) J + J is convex, (ii) J satisfies gradient domination property above with μ 0, (iii) (0) is Lipschitz smooth and satisfies PI. condition, (iv) [1( (asia)--h(fh) h(a++1)l be for all t. Then after running Gradient Ascent for m iterations to maximize l we have
J(x)) - J(T)) + Di=0 fer + bn]
min [T(²T) -[=))) S tE|T-11
aT
where -4² and is the approximation error at iteration and IT' 1] :- 10,1,2, T
Proof. Since J 0 is convex,
1
1 2 h(TT+1)) = ((T)) + (VJ(Tt), T+41 - xz)
-x)- - 2n
Te+1
Tell2
h(T(+1) Et
(Using the GA bound from above)
2 h(T(+1) - -et - bt = J((t)) - (VJ(T=)) met1 - n²)
| - Tell2 Cz - be
2n
2 ((T)) + ? V [ )112 - Et be
(Since Tt+1 = Te + V)
2 ((T) + 112
[J(=') - -((e)) )1² - -b. be
(Using gradient domination of J)
2
n1²
= J(TT) ((++11) S J(TT) (
2 [J(T)) - [TT)]] + ex + b.
=b
81+1 S 81 - a + ct + bt
a S 6e - b + et + by
Summing up for T iterations and dividing both sides by T
1 T-1
a min -1]
8 S a
Σ
6
T 1=0
1 T-1
T
1
160 - 8r+1l
+
Σ
1 les + bel S T
[ul + T
Σ
le + bnl
T
T
t=
t=0
80 + ET- le + bil
min
(E(T-1]
al'
The above analysis relied on the knowledge of the exact gradient VJ(T), but can be easily extended to using inexact estimates of the gradient by using the techniques developed in [63].
D.4 Helper Lemmas
Lemma 4 (3-Point Bregman Property). For For.,,y, 2, E X,
(Vó(z) Voly), 2) = (z,2,2) + Dz(2,y) Dx(x,y)
Lemma 5 (3-Point Descent Lemma for Mirror Ascent), For any z E rint dom 6, and a vector d, let
1 11
y arg max (0xx((d,))) (d,
(x)
#EX
Then y E rint dom & and any E X
1 (d. y x) 2 [D(y,2)) 2)= + (x - (2,
17
27

---

Lemma 6 (Performance Difference Lemma [26]). For any n, x ETT,
J(*) - J(x'= = 1-7 Exndr (s.),,, - p (1s))
1
E Proofs for Sec.
Proposition 12 (State-wiss) lower bound). For (i) any representation æ that is separable across states i.e. there exists л E RA such that Ts,a [xr la. (ii) any strictly convex mirror map & that induces a Bregman divergence that is separable across states i.e. D& (IT, x²) E. d' (s) Do(T" T (iii) any 7) such that + 1 is convex, if (iv) V=((z) is separable across states i.e. [V[(T) 0.0 = dd' (s) ((T)(( where (TT) E R., then (v) for any separable (across states) gradient estimator و i.e. [](T)] 3.0 (s) (T)]a where (T) E RA, and E (0, oo)
J(T) 2 ((m.) + (TTT) m.)) - (s) 1 - 2 Do Σ d dd Dg) (Vo(T=") c2 07, Ve(TT=))
C4
Proof. Using condition (iii) of the proposition with Lemma 2,
[Tx 2 ((.)) (VJ(m.)) (m+), mz) 1 1)
D mx)
J + (T()))))))))))))))) π - mp) + (TT) - g(Te)) n - me) Do (T
Using conditions (iv) and (v), we know that [V = d (s) J and (),T,)),,a (s) Defining
83 = ((x) - (m+) E RAA Using conditions (i) and (ii), we can rewrite the lower-bound as follows.
(TT) 2 ((T.) + (0(=)), (át - m+) + Σ d (8) (8) - -m²²
d (s) Do("",m
= J( + (i(TT)) v - + Σ dr (08,5* - -T²") - 1 D&(T", mi²)
1
Using Lemma 1 with r 8t, y = n" and y¹ = n
Do. (VΦ(T;)) - -c, 57. Vo(T()))
11 (-+ D Dz De(tt)m(") m()
2 J(T)) (M( π m.) Σ (s)
Co
((T) 2 J(T.) + (0(T)), v m.) Σ (5)
(=+1) Co Da(T') - Σ
d (s) Do (Vo(Te") - c. 07, vo(T=)))
C2
Proposition 4. For the direct representation and negative entropy mirror map, c <> 0, 11 S
(1-7}²
27 TAT.
[T) ((T)) C Baware (aappi((ie)
p (alss) p (als)
(8.)
77 (++
log
p" (a(ass)
Banptel a) (QTh (s, + log (Ea)) eep
(-c (-c|QTt (s.
Q (s. (s.a))
where C' is constant and Q* is the estimate of the action-valle function for policy w.-
Proof. For the direct representation, Ts.a nT (als). Using the policy gradient theorem, [V) = (s) a). We choose ((T) such that [r(=)) (s) Q7 a) as the estimated gradient. Using Vaswani et al. [57, Proposition 21, + 14
is convex for 17 < 27 AAT Defining o3 == V - (TT.) = Q (s. (s, E RA, and using Prop. 12 with c. = c for all 8.
(1-21"
11 c) (T - ())(s) D3- (Vo(T=)) - co;, vo(T()))
(1-1)
J(T)= 2 J(T.) + (0(m)), क TI) - -- (s)
28

---

Since ((x²) = (11s) Ea p"' (als) lag(p"(als)) using Lemma 10, Dz( ;T())) KL-(pp (-Is)llp* (+1s). Hence,
J(x) 2 ((m)) + Σ d= (s) Σ (s) a) 10" (als) - (= { = c
Σ (s) KL, (-1a]ll" (-1s))
d (s) Dø- (VQ(TT") oūt Vo(Tx)))
Using Lemma 7 to simplify the last term,
Σ d (s) Dø. (Vo(==") co2, Vo(T)))
Σ d=c (8)
c-p"( + log Σ pm (als) exp(-c8; (al)
Ed Σ (als)) (aa(a))) 1m [s) + - log Σ p p (als) exp (-c10= Qt (s, (s.( (
Putting everything together,
- ( 1 Σ d (s) (Hs)
J(x) 2 ((T) + Σ (s)
- Σar drd (s) (ar(sss) (z5((s, (s. - log Σ Eaa((als) (als) exp (-elQ" - (= (s))
= (Tx) Eenaiec (aupt ( (s, a]] +Bondrr (amp-(tts
(0,()) - 11 p (a|s)
( log p (a((s)
+- Σ dm)(s) (s) Earealss (Qt)) (s,
1 log
Σ (als) exp (-c(Q (8, @T (s, a))
c
(als) (als)
(1
+ 1 log
p'(ass) (a((s
J(x) 2 J(TT)) C ++E, Bswnrre Eumpre(1s)
17
1 c
Egndes
(anppe((1)) (0, [s),
a)] + log (Baxpi((10) eep (=c(Q"((s,a)) Q (s,
Proposition 6. For the softmax representation and log-sum-exp mirror map, c <> 0, 5 1 - %
[( (s..) 0) + 1 -1 :) log
(aals)) (als)
(TT) J(Te)) 2 Eanani Ea (-14)
1 Eandtre Ea (-1e)
[[1 (1--o(A'(ss a) - À A (s,aa) log (1 - clA" (s, a) - (s,o)))
where A is the estimate of the advantage function for policy T..
Proof. For the softmax representation, Te. = =(s,a) s.t. (als) = exp(=(s,a)
Σ. exp(=ts.aa)) Using the policy gradient theorem, [V.J(m))a.. = d= (s) (a]s) (s, We choose ((T) such that [0(=)] = d d=(() n" (als) Á (s) as
the estimated gradient. Using Vaswani et al. [57, Proposition 31, J + _ is convex for 17 S 11 - 7. Define ò, E RAA such that 87[a] ==
J(Te) (m.) = n.x (a|s) [A (s. - As a)]. Using Prop. 12 with c, = c for all s,
J(T)= 2 J(T.)+ + (0(m)), क m.) - (s)
( (-+ :) Do Σ 8
d (s) D3- (Vo(m)") - co8, Vo(Tz)))
29

---

Since (b(x)) = (=(((,))) :)) log (Ea exp(=(s, a))), using Lemma 11, D2(TT" x²) = (1s))( (-16) where p" (als) exp(a(s,a)) En exp(=(s,a']] and n² (als) Ed exp(z((s.a")) Hence, the above bound can be simplified as,
(xp(2((a0))
(++ + - c
(TT) 2 ((T)) + Σ dh (s) Σ
- ==(s,a]]
Σ d (L (+1ss)
(Vo(T() - c c6t. Vo(a())
Using Lemma 8 to simplify the last term,
d=t (8) Da- (Vo(T²)) cot, Vc((T=)))
c
Σ (als) cof(al) log (als) c ( (als)
Σ t (s)
p (a|s) - p (als) [AT (s. A (s. a)]
Σ dm (s)
Σ (als) - c [a]) - À (s, (s,,a)) log
(=((als)
a
Σ nTh (als) [(1- (1- - (s.aal log [ (s) (000-AA-0 _0(0)
Σ TT (s)
Putting everything together,
(T) 2 (TT) + Ed (s) Σ [( z((s,a)] - Σ d (s) (L(p""((ssll
c Σ (5) Σ (alss) (1- (s.aa) log (1 cl-c(A((ss,)) Ath (c,0)))]
p (als) As =().)) (
11 + _ Th (als) log
p (c((s)
((Te)
Σ d (s)
(a)a))
1 Bendri (-1o))())s) (a
[11 (s, (1) Tth A log (1- (I-c(A"((s,a) - A=
Let us focus on simplifying En (als) A (s, (z)ss)) [s) for fixed s. Note that E. pr: (als) ÅT (s,a)
0 - log (Ear exp(=(s, a')))
Enp"(aa (als) AT (s)a)= =0.
Σ pr (als) Am (8, (8)
Σ (alss Án (2(8.a)- - -log Σ Exxp(e(e.d)))
Σ
pr (als) 1=(((,a))
(1o((xx((((s,a)) - logg Σ Eexp(z(s,d)))
exp(2(s.a))
)
Σ pr (als) A (s, log
(a)p)s((1s)) AM a) log(o" log(p((als))
En exp(((((s)))))
Similarly, simplifying
E. A (s, a) (1)))2((..0)
Σ nT (als)
ms] = (1me) (s)())) a) (og(o())ll)))
(s) a) log p= (als) n (a|s)
Σ 1 (s.0 - =1(3,a]] = Eumppe((e))
30

---

Using the above relations,
p" (alss
( 17 = log
p (als)
J(T) 2 ((Te) Σ d (s) (am A log
(
(=(ass)
Bondr Buwpre())) (1 (1-c|A
- -s (1 log - c(A - A (8, a)l
(( ( (33(),,)) _ + 1
7 :) log
(a(1))) p (a )
= =((e)) + Bendre Bampec(ie)
C (unpreeenerreeee [1 (s, (s, log
( c cAA A -
Proposition 8. For the stochastic value gradient representation and Euclidean mirror map, >> 0, 1) such that J + 1 is convex in
2 ( + 1 :) (T((s.)) -(,,)))
1
((T) (Tt) 2 C Egnd Benx
(s) (s,c)
2 -
E Bondte Benx VaQTi(s, ())) ( a) lamm)()))) ]
2
2
where C' is constant and V. l=m((see) is the estimate of the action-value gradients for policy state and (8,
Proof. For stochastic value gradients with fixed E, 0J(z)
(T(),E) =((ssVV ( We choose g(7) such that
a=x(e,))
[[T)),..a = dt (s) Va) (s, a)) mm- Define 83 E R such that 87(a] = V (8, (=))( ( a) m=me Using Prop. 12 with c. for all s.
Ed V= (s, a) Vs) lammm) (=(),))- - ne( Ed + D Da(T",m""
((z) 2 (m) EEWx
1j
d (s) Do- (Vo(T=") cds, Vo(T("))
For a fixed s, since d(**)= = (TT(s, e)) = [[) Do xx²)
f[(((s))) =T(ss Hence,
J(x) 2 J(T.) Bewx
(s)(ss) V.Q T. (s, (s.0)) (T(,E) mx)))))
1 1 + c
Σ (s) (=(,,)) (T(
2 7
(s) Dø- (Vo(TT") - cof. (T(T))))
Simplifying the last term, since d( c)) cs),
Dø- (Vo(T(") c0 Vo(m.)) [8:1 = C
(s.)) VaQui (8, a) (=mm())))) 2
2
c
31

---

Putting everything together,
J(x) 2 J(Ta) + Beex
[a (8,66) -
Ed (s) (8)
dm
(0,0) Te(
- -Bexx
1 +-- 1 Σ
(8),)) (r
C
Σ (s)
VaQ=* a) o=m.(..))
Vm (=x((s)))
2
2
[ 2 ((Ti) + + BEnx Exnaies
Valii ( (3,,))
(=
1
-
1
+ + (T(8,)) -s((s)))]
2
"
c Reax Bendie
(3)) - VaQuie( (8, (8,4))==0(((1))
2
2
Proposition 13. For the softmax representation and Euclidean mirror map, <> 0, S
(1-7)²
then
8
(T) 2 ((T)) + +C+ (s)
(ampr A (s, (s, a)
1
1 +
||z(s,)) 20(8, )11
2
17
c Esndro (unppet))))))
as)
where is a constant and A= is the estimate advantage function for policy Te.
Proof. For the softmax representation, Ts.a = =(s, s.t. (a(ss) exp(=(s.a))
E. explataaa)) Using the policy gradient theorem, (s, a). We choose (TT) such that [0(=) = (ss (T a) as the estimated (a p=)
[V),( = (s)
gradient. Define &, E RA such that [[[a]= == (TT)) (mx) (als) [AT (s Using Mei et al. [37, Lemma 7], J + L is convex for S
Using Prop. 12 with C2- = c all 8,
((T) 2 ((Fz) + (ā(T;), π - -()) - ( + Σ (5) DT m())
d (s) (Vo(T()) co.. Vd(T()))
"7
Since ((T0) = (((((,))))))))))))) )) E (2,,0 12 (T m( [|= -2 )1.. Hence,
(= + ! Σ d' | - 22, 2
J(z) 2 [(T)) + Σ dt (s) Σ AT (cls) 2(s,
- Σ (S) Dø- (Volz)") cof, Vo(T()))
Simplifying the last term, since o(z(, a)) = _| a)}²
Σ, d (s) DØ- (Vo(T:") cof Vo(T.)) Σ ds [))(())
c Σ (m))s) Σ pT (als)) AM (A - (s)
2
<
c
Σ
d" (s)(s Σ (als) (A'((s Ard
2
(Since pa (als) $ 1)
2
a
32

---

Putting everything together,
[(x) ((T.) + Le (s) Σ (al [(s,aa]]
1 ( + -
-
Σ d ds) [|z(s,)) - 2x. .12
2 c
Σ d' Σ pm as) (s.
2
-m()) Σ ()) Σ
( - 1=(8, - (x
Σ (8) Σ (((((
2 Σ d (s) Σpdi(als) (s) (s)
=(() + C + Bondd Bonpra((ss) (s 2(5,
1 (1
+ :) |1a(s,)) z0 20(
2 "
((ss,a))"((sssa))) 2
2 BeondiBauppeee
Proposition 14. For both the direct (with the negative-entropy mirror map) and softmax representations (with the log- sum-exp mirror map), for a fixed state s, if d RA = (TT) (Tx), the second-order Taylor expansion of f(c) = De- (Vo(Te") co, Vo(m;")) around = 0 is equal to
e Σ (als)A(ss,)))) a(s.a))²
f(c) ~
2
Proof.
f(c) D& (Vo(m)") co, Vo(T.")) f(0)= Dz(Vplm²) Vo(Te") =0
f(c) DE' (Vo(m)) cτ, Vo(T.)) =V((V((m') cσ) 6' (Vo(==") - (Vo')))(m Vo(m)) - - vp(TT))
fc(c (V (Vo(T;)) c0), -8) (mi", - (0 (T - ()) =0
(c) (6, V (Vo(Te") co)o) (0) (6, (Vo(m 0))
By the second-order Taylor series expansion of ((c) around c O.
f(c) ~ f'O(c- 0) + (0) (c 0)2 c²
2 (8. (Vo(m))
2
Let us first consider the softmax case with the log-sum-exp mirror map, where T" 2(s,-) and ((2(s,)) Lo exp(z(s, a))), (-(((()))) = Ea n" (als) (ag()"(a)s)) Since the negative entropy and log-sum-exp are Fenchel conjugates (see Lemma 9), Vo(z((8,)) .) = nd (-Is). Hence, we need to compute "200 (-)ss)).
V "p'(p" (-1s)) = 1 log(p" (-Is)
Ve0"( = diag (1/2*((1x))
For the softmax representation, using the policy gradient theorem, (8], = p (cls) Å(s, a)) and hence,
v `" (Vo(==))
Emm((as)A((ssa) A(s.a))².
Hence, for the softmax representation, the second-order Taylor series expansion around c = 0 is equal to.
f(c) ~ ? 2 (aa((as)A(ssss) A(s, 2)
Now let consider the direct case, where T² p" (+1s). 60p (11s) = Σ. logg) 0²(2(s,-)
log(E. exp(=(>, a))). Since the negative entropy and log-sum-exp are Fenchel conjugates (see Lemma 9), Vo(p=(((1)) =
33

---

(1,8,)). Hence, need compute V (=((((((8,)))
(x,
(V Ma E. ex)( = - (als)
[V90 pa ( = =iag) - pr (-1s) (-1s))"
- 10" (als)]
(2, (2((s,))aaa' ===
For the direct representation. using the policy gradient theorem, [6], = (= ( (s and hence,
(6. (V. = 1Q )) - QT (s.-)) 'I' [diag(p" " (-|s) - p-1ss) [1 [-15]]] 1QT (s, Q- (s. Σ ndh (als) [QT ( a]] (0 (als), (8, - (s,-)) } (e((T)) _m()
Σ p": (s)(ss (s.
(where (Txe) the estimated value function for starting state s)
Hence, for the direct representation, the second-order Taylor series expansion around = 0 is equal to,
c²
[cc)
p" (als)
(QT)(s (s, a)2 [m((me)) Jc(mme)
2
c²
Σ
as) - 2 (A((T)) - -sa(Te)) 2 Σ (als)) + [-.((m)) -..(m))
| (als)
" pm (als)
2
c²
Σ
(alsa))) ((*H) (s,a))) 2 (.((Ts) - -
2
[L((T) - (m()
Σ (als)
+
8
Σ TT (als) (0,a()) (=(((s 2 (T.((T) -Ss(me)) (s, - (s, + [J((=)) s.(mi))
2
2²
Σ (als) (s0 (s, a)] - (s)00 (J FL((ma)) 2
2
2
Σ p (als) as) (s) 2
2
34

---

E,1 Bandit examples to demonstrate the benefit of the decision-aware loss
Proposition 15 (Detailed version of Prop. 5). Consider a two-armed bandit example with deterministic rewards where arm
is optimal and has a reward rı Q1 = 2 whereas arm 2 has reward r2 Q2 = 1. Using linear parameterization for the critic, Q function is estimated as: Q w where is the parameter to be learned and z is the feature of the corresponding arm. Let æ1 = -2 and 222 = 1 implying that Q (w) 22 and (2(w) w. Let pt be the probability of pulling the optimal arm at iteration f, and consider minimizing two alternative objectives to estimate w:
(1) Squared loss: w¹Sh := arg min { P [Qi(w) Q1I² + 1 (Qa(w)- }ul²].
arg min (w) 1 log (p: exp [c|q] - Q (w)) + (1 - pi) exp (c( Qz(ww))
Decision-aware critic loss: u²²)
pi (Qi Q((w) + (1 -Po)
pp) Q² Q((w)]
Using the tabular parameterization for the actor, the policy update at iteration is given by: Pt+1
Pt exp(r(1)=(I-p)) exp(n(2)) where is the functional step-size for the actor. For po < f. minimizing the squared loss results
Pr. exp(nQ1)
in convergence to the sub-optimal action, while minimizing the decision-aware loss (for po 0) results in convergence to the optimal action.
Proof. Note that (w) 2 1) and Q2(w)) Q2 = w 1. Calculating (1)) for general policy s.t. the probability of pulling the optimal arm equal to p.
-Q
1 P (4: (w) Q11 + 1-P ((2(w)- Q21 = 4p (w + 1)2 (1 p) (w [ 2 MSB(() 4p (w + 1)+ +
MSE(w)
2
-p)
Setting the gradient to zero,
5p (1) = 3p + 1
Calculating (2) for general policy s.t. the probability of pulling the optimal arm equal to p.
Le(w) 2p (w + 1) (1 - p) (w - 1)+ log(p exp( 20 (w + 1)) + (1 - p) exp(c(w 1)))
(uLi(w) (3p 1) + 1 we [log(p exp(-2e (w + 1)) + - p) exp(c(w 1)))
Setting the gradient to zero,
V [log(p exp(-2c (w + 1)) + (1 - p) explc 1))) = (1 (p)
Define :=
== exp(-22 2c (w + 1)) and == exp(c (w - 1)))
2p A + (1
p p + p) = (1-3p)c P + (1 - p)
(2)
3
Now, let us consider the actor update,
Pt e
Pt+1
P++1 Pe exp(1)11) + (1 - pt) exp(1)2)
P: + (1 Pc) exp(y ( ((22-11) Q1)
Pt
Since arm is optimal, if pe+l < for all i, the algorithm will converge to the sub-optimal arm. This happens when
Q2 Q > 0 = > O. Hence, for any r) and any iteration t, if w2 > 0, Ptt1 < Pc-
(1-(1) exp(n (Q2- (1))
For the awaaee critic loss, w/!²) 3/2 for all t, implying that pc+1 Pt and hence the algorithm will converge to the 5p, 3p.-1 w/ > 0 < 5
optimal policy for any 17 and any initialization Pa > 0. However, for the squared MSE loss, w/
Hence, if po < + P1 < po < 5. Using the same reasoning, P2 < P1 < po < 1/5, and hence the policy will converge to the sub-optimal arm.
35

---

Proposition 16. Consider two-armed bandit problem with deterministic rewards- arm has a reward ri = Q1 whereas arm has reward r2- Q2 such that arm is the optimal, i... Q1 2 Q2. Using a linear parameterization for the critic, Q function is estimated as: Q = where is the parameter to be learned and x is the feature of the corresponding arm. Let pa be the probability of pulling the optimal arm at iteration t, and consider minimizing the decision-awasd aware critic loss to estimate wt wi ==
arg min (w) :- pe 1Q:-Q1 (1)pp))) [Q2 [2(+)]++ log (p= exp (-<=-
Q (w) + (1 pt) exp (-c (-c(Q=- +2(w))))
Using the tabular parameterization for the actor, the policy update at iteration is given by: Pc+1
Pt. exp(nQ11)
(xp()Q))=(1-pp exp(vQa)' where 77 is the functional step-size for the actor. For the above problem, minimizing the decision-awe aware loss (for c, Po > 0) results in convergence to the optimal action, and (((we) = 0 for any iteration t.
Proof. Define A == exp(-ciQ1 - (i(w))) and B = exp(-c(Q2 - Q2(w)])- Calculating the gradient of Lt w.r.t w and setting zero,
Vuhelw)= = Dt + (1 pc) 1 A + (1-pt) 22 B
0 Pt A + (1 pt) B
- Pt (1 pt) A (2) x2) = pt (1 - pt) B (I) x2))
Q1 Q1
= Q1 - I Wi = Q2 x2 wt = Wt T1 22
Observe that Q1 Qu(w)) = Q2 - @2(we) and thus (,(we) = 0 for all 4. Writing the actor update,
Pt exp(1) x1 Wa)
Po+1
Pt exp(1)=1 wa) + (1 pt) (2))
Pt+1
exp(n (Q2 Qi)) 21
Pt Pt - (1 - Pı) exp(( (12 x1)w)) Pt + (1 (1-11-00 (1--P)
Proposition 17 (Detailed version of Prop. 7). Consider a two-armed bandit example and define p [0, 1] as the probability
of pulling arm 1. Given p. let the advantage of arm 1 be equal to A₁ := 1/2 > O, while that of arm 2 is A2 == 2(1pp) :--2(1pp)
implying that arm 1 is optimal. For the critic, consider approximating the advantage of the two arms using a discrete
hypothesis class with two hypotheses that depend on p for: Ho Å 1/2 + E Ag
- (1 E) and H₂ Å
- (1 sgn (1 -0-)) p)) where sgn is the signum function and E ($. If pt is the probability of pulling arm 1 at iteration t, consider minimizing two alternative loss functions to choose the hypothesis H4:
1/ sgn [ p) A
(1) Squared (MSE) loss: H. = arg min (H) { //2 [A, - A 2 [A2 - A-13].
(2) Decision-aware critic loss (DA) with e = 1 H. arg min min (1)
Pt (1 [A1 Á.l) log(1 - [A1 - A.)) + (1 p.) (1 - [A_ - Aul) log(1 - [A2 - A
Using the tabular parameterization for the actor, the policy update at iteration is given by: Pt+1 =
p. (1+
pi (1+nA1)+L (1+ 12)
(1+z
For Po < 1, the squared loss cannot distinguish between Ho and Hi, and depending on how ties are broken, minimizing it can result in convergence to the sub-optimal action. On the other hand, minimizing the divergence loss (for any po 0) results in convergence to the optimal arm.
Proof. First note that when p > 1. Ho and Hi are identical, ensure that A, > Åg and the algorithm will converge to the optimal arm no matter which hypothesis is chosen. The regime of interest is therefore when p S 1/ and we focus on this case. Let us calculate the MSE and decision-awan (DA) losses for Ho.
A - A 2
1 = = ;
2 (
A2
P
[1 (1 (1+5)]
= P
1-p
1
2
E2p2
MSE MSE(A,, = p + (1 (1-p)
p
E = pe? +
1-p
1-
AA( = -1 log(1 + E) + +(1+ 1p)p) (1 1
Ep
Ep
log
1 - p
1 - p
36

---

Similarly, calculate the MSE and decision-aware losses for H1.
A A
1 1
2
= =E : A2 A2
p
p p
2
1 p
2
2
(
521²
MSE(A1, A2) 42)===p= pp² + +(1 -p) p)
1 1 E =pe- +
1 1-p p
DA(AI, A2) = p -
log(1 - E) + (1 (1-p) p)
(1+ 1 1-p) p
Ep
log
1 1 Ep
1 p
For both Ho and H1, the MSE loss is equal to pc² + 5²p² and hence it cannot distinguish between the two hypotheses. 1-p
Writing the actor update,
Pc (1 + A1) +1
Pt-1
1
P++1
Ps (1) pt) (1 + A2)
Pt. Pr. + (1 - pt) 14md2
I+nA1
Hence, in order to ensure that p++1 > Pt and eventual convergence to the optimal arm, we want that A < AI. For E (#.1). for Ho. À > 0 while A₂ < 0. On the other hand, for H4. A₁ < 0 and Å₃ > O. This implies that the algorithm should choose Ho in order to approximate the advantage. Since the MSE loss is the same for both hypotheses, convergence to the optimal arm depends on how the algorithm breaks ties. Next, we prove that for the decision-aware loss and any iteration such that Pt < 0.5, the loss for Ho is smaller than that for H1, and hence the algorithm chooses the correct hypothesis and pulls the optimal arm. For this, we define f() as follows,
f(p)= = p + log(1 +5 + (1 (p) 1 EP
ep 1 -
log
1-p p
1 - p EP
EP
=1 =) log(1 -) c) + (1 p1-p) 1+ 1 - p
log
1+
1 - p
For (p) be well-defined, we want that, 1- > 0 = <<> 1 and 1 1- I-p
> 0 - p T Since e E 11/211). < 1.2 1).
In order to prove that the algorithm will always choose Ho. we will show that f(p) s for all E [0, 2/2] next. First note that,
1+e log(1 + +. + (1 (1-e) log(1 - 5) - 1-8 log(1 -) - 1+8 log(1 + +) = =0
((0) 0 : S(1/2=
2
2
Next, we will prove that f(p) is convex. This combined with the fact f(0) = f(1/2) = 0 implies that fp) < 0 for all p E (0, 1/2). For this, we write f(p) g(p) + h1 (p) h2( where,
s(v) = (1 + 8) log(1 ( + + p1 8) log(1 - 8)
hi (p) = (1 pp) (1 1 1-p p)
1 - 6'p
log 1 - 1 p
= (1 - -6'p) log
(6'=1+0
1 1 p
h2(p) = pp 1+ 1- p
EP
log
1+ 1- p
EP
= (1 - pp)) log
1 1- p
11-
1- p
Differentiating the above terms,
g'()) = (1 + log(1 + +s) - (1 (1-8) s) log(1 - ; {"(p)= =0
1 p
+ 1 c-c'
(p(p) = -é' log
1 -
1-p
1)) (c' - 1)2 + ( -1]]
é' 1-6'
(1- 2
M()) = 1- e'p 1-p p
> 0
(1 p)²
(1 - c'p) (1 p)
Similarly,
(p) 11p [cd' - 1]22 + (1- -1]]
P <0
(1 pp) (1 p)2
> 0 for all p 1/2) and hence f(p) is convex. Hence, for all p < 2, minimizing the divergence loss results in choosing Ho and the actor pulling the optimal arm. Once the probability of
Combining the above terms, f"( (p) gp))p))p + hp) hp))) h1 1
37

---

pulling the optimal arm is larger than 0.5, both hypotheses identical and the algorithm will converge to the optimal arm regardless of the hypothesis chosen.
E.2 Lemmas
Lemma For probability distribution p E IR,,, the negalive entropy mirror map <(p) = Eips log(pi), d E IRA, e 0,
Dø- Volp) - cō, VolD) = c(p, + log Σ Ps exp( exp(-c6,)
Proof. In this case, [Vo()), = + log(p:). Hence, we need compute Dø- (z', where 2 := 1 + log(p:) co; and
= 1+Hog(P:). (p)) = Σ; Pa log(pi). using Lemma 6 (2) = log (E, exp( (4)) where log E, exp(z;)) = log(p:).
exp(1 cod.) Define distribution g such that q: == Σ, exp([++oo((s)) Using Lemma 11,
Dø- (z) kL(plla) = Σ Ps log
Pi
gi
Simplifying
q: = exp(1 log (p:) ] - c6,)
pi exp(-cd)
Ex (1 + log(p,) - cd,))
Ej Pj exp(-c6;)
Pi Enps (xp(-c66)
= Dø (5'12) = Σ Ps log
Σ pi log eep((c))) Ens Dy exp(- -od,)
pi exxpp
c Epi
pid; 8; + Eps ps log Σ ps exp(-ccd) = =c(p,) + +og Σ Pj exp(-cdd) -cd;)
Lemma 8. For z RAA, the log-sum-ent mirror map ((2) = log (E, exp(2:)), d RA s.t. E, 6, = c>
Dø- (Vo(=) co, (V6 = Σ (pr - coi) log
Di -c-dd
Pi
exp(=.) where p; Σ, ]x
Proof. In this case, [Vo(=)]; Σ, exp(2,) pt- Define distribution g s.t. Q: = Pt cōg. Note that since E, =0, E, 4= E.P. = 1 and hence, 9 is valid distribution. We thus need to compute Dø- (q.p). Using Lemma 9, (p) P. exp(x,) where pj Σ, exp(2)) Using Lemma 10,
exp(x.)
Ps cō.
(a. =
= Σ (p: - -o,)) log
Pi
C
Lemma 9. The log-sum-exp mirror map on the logits and the negative entropy mirror map on the corresponding probability
distribution Fenchel duals. In particular for Rdd, if Φ(z) log (E, exp(2,)), then d² (p) Σ, P; log(p:) where
exp(2.) e Similarly, if ((pp) = E; log(ps), then o² (z) log (E exp(zi)) where log( E, exp(z.) = log(p:).
Proof. If (()) log E exp(())),
(p) = sup Kp, 2) - [[2)] = sup Σ pizi - log Σ exp(=s)
38

---

Setting the gradient zero, we get that p;
E, exp(2]] for 2* E Z where 2 the set of maxima related by shift (i.e. if
exp(2;)
2", + C 2" for constant C). Using the optimality condition, we know that E, Pt and
log(p;) 2 -log Eexp(ez)
= o = =lo((p:) + +(2²))
Using this relation,
)]
(p) Σ piaj log
Σ Exxpl(2)
Σ pi log(p:) + +0(22) + pt -(2²)
o (p)
Σ Ps log(p))
The second statement follows since the o5 (x) Φ.
Lemma 10. For probability distributions, p and p', if d(p) = E; plog(p)), then Do(p.'') Kl((pl1)))
Proof. Note that [V<(p)]] = 1 + log(::). Using the definition of the Bregman divergence.
(p.p.' <(p) - <(p') - (Vo(p'), p- p¹)
= =E Ms log(p:) ppi log(r/) (1 + log(r!))(p: -V'il
[ppilos log
Pi pp
]
Σ Ps En
i
Since p and p' are valid probability distributions, E,pi Eipl 1, and hence, Dø(p,p') kL((plp')
expla;) Lemma 11. [f(() = log(E, exp(2.)). then Do(2, = (L(p'lll where p. == E, exp(2,)
and pt := Σ, exp(=)))
exp(=!)
Proof. Note that [Vc(())] expla:)
expp(s)) P4 where p= E, expp(,z))
exp(s.)
Using the definition of the Bregman divergence,
Dolz,z))== = 6(2) - o(z') - (Vo(2)),
exp(2.) Eg exp(=))
= log Σ exp(zs)
log Σ exxp(z))
Σ
(2: - z\))
Σ pk
log Σ exp(23)
log
Σ exp(2x)
23 + 2
(Since E.pl = 1)
Σni pl
log Σ exp(zz)
log
Σ exp(2/) (2/)
log(exp(=1)) log(exp(z/)) (z/))
exp(2/) Σ, (x)(21))
exp(zi)
Σrh log
pk
log
E, exp(2))
Σ pl (log(r)) -og((()) = Σrl log
pl
KL (p)
pi
39

---

F
Implementation Details
F1 Heuristic to estimate
We estimate to maximize the lower-bound on J(t). In particular, using Prop. 1,
J(x) 2 (m)) +(m)) (TT mT) (,+²) ++)) Do ne)
1 Dv. (VB(T)) 9(Te)), V
c
For a fixed ((T)). we need to maximize the RHS w.r.t v and e, i.e
max m + ((TT)) (-= me) - +++2) Do (T me) <>0 well
Da- (V((T)) - cV)) ((m)), (
(6)
Instead of maximizing w.r.t ग and will next aim to find an upper-bound the RHS that is independent of . and aim maximize it w.r. c. Using Lemma 1 with y' = n. y Te. x - and define c' such that 1 =
+ + t.
1
--(().))--.))) - D (V + d(( vd(T.))
1 ( 17 + !) Da( (t) ((m)) + ( v
= + m.)
Using the above upper-bound in Eq. (6),
max ((TT) 3 +d)(()))))))))).. vo(T.)) 1 Dr. -(V(() ((TO), VO(TT)
1
This implies that the estimate è can be calculated as:
(
D V + (1+ ((Te), (
1 Do. Dx
- -cV())))(V(()) - M(Te)), VO(TT)
é = arg max
-
6>0
In order to gain some intuition, let us consider the case where (o v) = I|u ull. In this case,
(l(()))l1 ((ā(T)) - vJ(m))
arg è
2 ( + +
e>0
If
0.
(
arg max e>0
c +0000
2
1 + 1
- -V()))))V(<>))3
غ arg max e>0
=
c+0
c
2
F.2 Environments and constructing features
Cliff World: We consider modified version of the CliffWorld environment [53, Example 6.6). The environment is deterministic and consists of 21 states and 4 actions. The objective is to reach the Goal state as quickly as possible. If the agent falls into Cliff, yields reward of -100, and then returned to the Start state. Reaching the Goal state yields a reward of +1, and the agent will stay in this terminal state. All other transitions are associated with a zero reward, and the discount factor is set to 7 = 0.9.
Frozen Lake: We Consider the Frozen Lake v environment from gym framework [6]. The environment is stochastic and consists of 16 states and actions. The agent starts from the Start state and according to the next action (chosen by the policy) and the stochastic dynamics moves to the next state and yields a reward. The objective is to reach the Goal state as quickly as possible without entering the Hole States. All the Hole states and the Goal are terminal states. Reaching the goal state yields +1 reward and all other rewards are zero, and the discount factor is set to = 0.9.
40

---

Sampling: We employ the Monte-Carlo method sample from both environments and we use the expected return to estimate the action-value function Q. Specifically, we iteratively start from a randomly chosen state-action pair (8, a), run a roll-out with specified length starting from that pair, and collect the expected return to estimate Q(s,, a).
Constructing features: Also, in order to use function approximation on the above environments, we use tile-coded features [53]. Specifically, tilde-coded featurization needs three parameters to be set: (t) hash table size (equivalent to the feature dimension) d, (ii) number of tiles N and (dit) size of tiles s. For Cliff world environment, we consider following pairs to construct features: {(d 40, .N- 5. s 1), (d 50, .N 6,
3). (d = 80, N 5, s 3). (d = 100, N = 6, s = 3)}. This means whenever we use d = 40, the number of tiles is N = 5 and the tiling size is 8 = 1.
1), (d 60. N 4,
The reported number of tiles and tiling size parameters are tuned and have achieved the best performance for all algorithms.
Similarly for Frozen Lake environment, we use the following pairs to construct features: {(d = 40, N = 3,88 = 3), (d
50, N 4, 8 13), (d 60, N 5,8 3), (d 100, N =8,8 =3)
F.3
Critic optimization
We explain implementation of MSE, Adv-MSE and decision-aware critic loss functions. We tile-coded features X(s, a) and linear function approximation estimate action-value function Q, implying that Q(s,, a) w X(, a) where w X(,, a) Rd.
Baselines: For policy т, the MSE objective is to return the w that minimizes the squared norm error of the action-value function Q across all state-actions weighted by the lateonction occupancy measure μ²" (s, (s,a).
MSE
arg min EE (s.a) (Q" w" x(s
wER
Taking the derivative with respect to a and setting it to zero:
(Q) - wn x(((,))) x() =0
Σ [5 = 1 10, (((,,))((ss)))(x.0)]]
k
Given features X, the true action-value function Q" and acte-nction occupancy measure μ², compute K, y and solve MSE
K-1y.
Similarly for policy the Iivantage-MSF. objective is to return w that minimizes the squared error of the advantage function A across all state-actions weighted by the state-action occupancy measure ,¹"
arg min ((s,a) (v.a) as - w7 (oon)--"((((ps (x(s,))- Σ Ex(s,d')) 2 -X(s)))_xx(sd)]
Adv-MSE
wERd
Taking the derivative with respect to and setting it to zero:
X(s,a) _ Ex(s,aa) _x(x,d))= =0
(AT(ss)) - - (X(s,a)->) Ex(s,a')
B(e,a)x (0.00
o'
x(s,s,))) ( X(s,a) -x((s =
Eu a) x(s,a) Ex(s, -(xs,))-x((ss))) X(s,a)-
- _x(osd))" w
2,0
5,0
Given features X, the true advantage function A and state-action occupancy measure ,², we ca compute K and y and solve AAA--MSE K- k
Decision-aware critic in direct representation: Recall that for policy æ, the decision aware critic loss in direct representation is the blue term in Prop. 4, which after linear parameterization on Q" would be as follows:
Egnad
Easp= (s, Wf X(s, + log (Banp (exp (-c [[" (s) - (s. (s))))
The above term is convex function of w for any 0. We minimize the term using gradient descent, where the gradient with respect to w is:
41

---

E Ba (-1a)
exp (-c Q" (s, a) w ((s,)))) X(s,a)
-B
E (1)
Bampp (exp (-c (Q* (8, (x,
The step-size of gradient ascent is determined using Armijo line-search [3] where the maximum step size is set to 1000 and it decays with the rate 3 = 0.9. The number of iteration for critic inner-loop, m. in Algorithm I, is set to 10000, and if the gradient norm becomes smaller than 10-6 we terminate the inner loop.
Decision-aware critic in softmax representation: Recall that for policy オ, the decision-aware critic loss in softmax representation is the blue term in Prop. 6, which after linear parameterization on Q" and substituting ÅT a) with "n (X(),a) Ea X(s,a)) would be as follows:
Bewdrr Bamprt (1 (1-0(AM(0.0- wf (X(ss))) Ex(s,a))) log ( (1- wx -xx(,d))
Similarly, the above term convex with respect to w and minimize it using gradient descent. The step-size is determined using Armijo line-search with the same parameters as mentioned in direct case. The number of iterations in inner loop is set to 10000 and we terminate the loop if the gradient norm becomes smaller than 10 10-$, The gradient with respect wt
(1+ log (1
Eeeedree Bamppr(-1))) (-1o)
1- 1-c (AT a) - (X((s,))
Σ Ex(ssd)))
((ss,)) Ex((,
F.4
Actor optimization
Direct representation: For all actor-critic algorithms, we maximize the green term Prop. 4 known as MDPO [56].
pd (als) (als)
(Qm(ss.)- (+++ log
p (als) p (als))
E Egnddtee
In tabular parameterization of the actor, a..- (s, a). the actor update exactly natural policy gradient [25] and can be solved in closed-form. We refer the reader to Appendix F.2 of [57] for explicit derivation. At iteration 4, given policy n. the estimated action-value function from the critic Q7²e and 1 as the functional step-size, the update at iteration t is:
nT (als) exp (1)=((8,))) (8, a1)
On exp (1Â²T TT (s,
p M4+s (a|s)
On.o
En pd (a'ls)
cxp exp (s,a'))))))
En 0, exp (1 (s,
When we linearly parameterize the policy, implying that for policy p" (als) and the actor expressivity, we use the off-policy update loop (Lines 10-13 in Algorithm 1) and we iteratively update the parameters using gradient ascent. The MDPO objective with linear parameterization will be:
= exp X(s.a))
En exp 18T X(s,a]) where 8, X(s,a) E R"
exp (6 X(s, a)) (als) E.. exp (BT X(s,a'))
exp (8 X(s a)) (0=1ss)))) ( (++ :) log (pt((as) exp (0T
And the gradient of objective with respect to 0 is:
p. (als)
x(s En exp( x(,, ()),a,)))) exp a'))
(Q~(s,0)- + log( p (als) n (als)
Esndet
E (asp)e(1s))
(als)
Softmax representation: For all actor-critic algorithms, we maximize the green term in Prop. 6 known as sMDPO [57].
(Am - + log
p (als)
Exdati E EampTr(-1b))
y (als)
In tabular parameterization of the actor, 0ne = p a), at iteration t given the policy me, the estimated advantage function from the critic A a) Q7 (s, a) EN (a(ss (s, a'), and functional step-size 77, the actor update can be solved in closed-form and is as follows:
42

---

n (als) max(1 1, (s,
0 max(1 7,4 (s, a), En 8 max + 74 (s, a)))
p p* (a|s) = Ee pr (a'|s) max(1 + 7, (s, a').0)
0x,a
We refer the reader to Appendix F.I of [57] for explicit derivation. When we linearly parameterize the policy, implying that for policy n. p" [a]s) = Enl (0" X(x,a"))' we need to maximize the following with respect to 0:
exp 16" x(s,o))
(( (A + 1] + + log (a))())) En exp (0 X(s,a'))
exp (0 ((s,)) a))
Similar to direct representation, we use the off-policy update loop and we iteratively update the parameters using gradient ascent. The gradient with respect to is:
[ + ++2) (x(3,0) En exp(("XX(xxx)) a)) ((),,)))((ss))) Ea exp(0" (xp((t"((soo) ((s,a))
Eg Bampii (-1b)
F.5
Parameter Tuning
Parameter
Value/Range
Sampling
# of samples
(1000, 5000)
length of episode
[20, 50}
Actor
Gradient termination criterion
(10-3, 10
1000, 10000}
Armijo max step-size
1000
Armijo step-size decay
0.9
Policy initialization (linear)
NO 0.1)
Policy initialization (tabular)
Random
Gradient termination criterion (direct)
Linear Critic
{10 10-83
Gradient termination criterion (softmax)
{10-8, 10 103
mc
1000. 10000}
Armijo max step-size
1000
Armijo step-size decay B
0.9
Others
in direct
(0.001, 0.005, 0.01, 0.1, 11
in direct
{0.001, 0.01,
17 in softmax
(0.001, 0.005, 0.01,
in softmax
(0.001, 0.01, 0.13
{ [40, 30, 60, 80, 100)
Table 1: Parameters for the Cliff World environment
43

---

Parameter
Value/Range
Sampling
# of samples
(1000, 10000)
length of episode
{20, 50}
Actor
Gradient termination criterion
{10 1104,110-5 53
ma
[100, 1000
Armijo max step-size
1000
Armijo step-size decay
0.9
Policy initialization (linear)
NOO, 0.1)
Policy initialization (tabular)
Random
Gradient termination criterion (direct)
Linear Critic
(10-6, 10-83
Gradient termination criterion (softmax)
(10-6, 10-
me
{10000, 1000000)
Armijo max step-size Armijo step-size decay B in direct
1000
0.9
Others
10,01,
in direct
(0.01,0.1,1]
Y) in softmax
01,,
in softmax
(0.01,0.))
d
{40, 50, 60, 100}
Table 2: Parameters for the Frozen Lake environment
44

---

G Additional Experiments
d=100
d=80
d=
d=40
X--0 01,
01-00),
1ye 0z, 1.0)
7t-0 1. c=0000
1p-0 1. 0.21
0.0
1, 1.00
2000G
0.6
Softmax
01, 0.00
0.2
01-0.1 c-0.3
10600
anhon
snkon
1ndon
takion
oolon
25400
40300
sráon
20000
undon
azfes
diteration
Afternttoo
Figure 2: Cliff World - Linear actor and Linear critic with exact Q computation Assessing the impact of (trade-off parameter in decision-awand aaarre framework) on the performance. We perform the experiment on the same setting as Fig. linear actor and linear (with four different dimensions) critic with known MDP on Cliff World environment. We consider two values of functional step-size 17 E {0.01, 0.1} and three values of {0.01, 0.1, 1} for direct and E {0.001, 0.01, 0.13 for softmax representations, and compare the performance of 6 combinations. Overall, among different critic capacities and step-sizes, the value of e 0.01 demonstrates superior performance in both policy representations.
45

---

AdMMSF-rtaa
MSE-sta= 0.01
MisE-eta= 1.0
AdVMSE eta= 0.01
AdVM 1.0
Ours-eta= 0.01
Ours-eta= 1.0
d-100
d-80
d-60
d-40
0.6
Direct
0.2
0.0
10000
20000
30000
40000
10000
20000
30000
4000c
5
10000
20000
30000
40000
6
10000
20000
30000
40600
0.6
Softmax
0.41
0.2
0.0-
10000
20000
30000
40000
10000
20000 siteration
30000
40000
5
10000
20000 #iteration
30000
40000 b
10000
20000 aiteration
30000
40000
#ftarationn
(a) Linear policy parameterization
MSE 0,001
MSE eto= 0.1
AdvMSE 0.001
AdVMSE cta= 0.1
Ours 0.001
Ours
sta= 0.01
MSE-cta=
AdvMSE
AdvMSE eta=
eta=
Ours- Ours-etar=
d=100
d=40
0.5
0.4-
Direct
25000
sodno
75500
25áco
soboa 75d00
6
2500n
sodoo
75630
b
z5óoc
sodce
75
0.8-
0.4
Softmax
0.2-
0.3-
25000
50000
75500
25600 5obog
75d00
6
25000
50000
75000
b
25000
50000
75000
#tieration
#tteration
#iteration
teration
(b) Tabular policy parameterization
Figure 3: Cliff World Linear/Tabular actor and Linear critic with exact Q computation: Comparison of decision- aware, AdV-MSE, and MSE loss functions using linear actor Fig. 3a and Fig. 3b coupled with linear (with four different dimensions) critic in the Cliff World environment for direct and softmax policy representations with known MDP, For d = 100 (corresponding to an expressive critic) in both actor parameterizations and have almost the same performance. In other scenarios, minimizing MSE loss function with any functional step-size leads to a sub-optimal policy. In contrast, minimizing Adv-MSE and decision-awar loss functions always result reaching the optimal policy even in the less expressive critic d 40. Additionally, decision-aware convergence is faster than Adv-MS MSE particularly when the critic has limited capacity (e.g. = 40 for direct and softmax representations and for both actor parameterizations, decision-awan reaches the optimal policy faster.)
80 in linear parameterization, all algorithms
46

---

MSE sta 0.01
MSE eta= 0.1
AdVMSS cta= 0.01
AdVMSE eta= 0.1
Ours eta= 0.1
Ours eta= 1.0
80
d=60
d=
0.5
0.4-
Direct
100
0.5-
0.2-
0.1
-0.1
10000
20000
30000
6
10000
20000
30000
6
10000
20000
30000
0.5-
0.4-
Softmax
0.3-
J(m)
0.2-
720
0.1
-0.1
0
10000
20000
30000
0
10000
20Č0U
30000
0
10000
20003
30000
#terratonn
#tteration
#iteration
(a) Linear policy parameterization
MSE cta= 0.01
MSE eta= 0.1
AdvMSE cta= 0.0
AdvMSE cta= 0.1
Ours cta= 0.1
Ours-cta= cta= 1.0
d= 80
d= 60
d=40
0.5
Direct
882
0.34
10d00
z000c
30000
10d0a
z0don
30d00
10000
2000a
30000
0.5
Softmax
0.24
10000
20000
30000
b
10000
20000
30000
10000
20000
30000
#lteration
#tteration
#iteration
(b) Tabular policy parameterization
Figure 4: Cliff World Linear/Tabular actor and Linear critic with estimated Q: Comparison decision-aware. Adv-MSE, and MSE loss functions using a linear actor Fig. 4a and Fig. 4b coupled with linear (with three different dimensions) critic in the Cliff World environment for direct and softmax policy representations with Monte-Carke sampling. When employing a linear actor alongside expressive critic (d 80), all algorithms have nearly identical performance. However, minimizing the MSE loss with a linear actor and a less expressive critic (d = 40, 60) leads to loss monotonic policy improvement and converging towards sub-optimal policy in both representations. Conversely, minimizing the decision-awar and Adv-MSE losses enables reaching the optimal policy. Notably, decision-awan demonstrates a faster rate of convergence when the critic has limited capacity (e.g., d 40) in both policy representations. The disparity among algorithms becomes more apparent when using tabular parameterization. In this case, the decision-aware loss either achieves faster convergence rate (in 80 and 60), it alone reaches the optimal policy (d 40).
47

---

AdvMSE-eta= 0.1
AdvMSEE-eta= 1.0
MSE-eta= 0.1
MSE-ela= 1.0
Ours-eta= 0.1
Ours-eta= 1.0
dl1000
dw60
d=50
d=40
0.07
0.05-
Direct
0.03
0.01
0.00
10000
30000
50000
10000
30000
50000
10000
300.0
50000
10000
30000
50002
Softmax
0.05
1881
0.03-
0.01
0.00
10000
30000
50000
10000
30000
50000
0
10000
30000
50000
10000
30000
50002
Alteration
alleration
Alteration
Alteralion
(a) Linear policy paramcterization
--- AdvMSE cta= 0.1
AdvMSE cta= 1.0
MSE cta= 0.1
MSE eta= 1,0
Ours cta= 0.1
Ours eta=
1.0
d=100
d=
d=50
d=40
0.07
Direct
[mm
0.01
0.00
10000
20000
30000
10000
20000
30000 0
10000
20000
30000
0
10000
20000
30000
0.07
Softmax
0.05
[tm1
0.00
10000
20000
30000 0
10000
20000
30000
b
10000
20000
30000 0
10000 # #lloration
2000C
30č00
#ileration
ditaration
iiteration
(b) Tabular policy parameterization
Figure 5: Frozen Lake Linear/Tabulat actor and Linear critic with exact Q computation: Comparison of decision- aware, M.V, and MSE loss functions using linear actor Fig. 5a and Fig. 5b coupled with linear (with four different dimensions) critic in the Frozen Lake environment for direct and softmax policy representations with known MDP. For d 100 (corresponding to an expressive critic) in both actor paramterizations and 60 in linear paramterization, all algorithms have the same performance. In other scenarios, minimizing MSE loss functions leads to worse performance than decision-ave awaare and Adv-MSE loss functions and for = 40 in linear parameterization MSE does not have monotonic improvement. Adv-MSE and decision-aware almost have similar performance for all scenarios except d 50 with tabular actor where decision-aware reaches a better sub-optimal policy.
Frozen Lake Linear/Tabulat actor and Linear critic with estimated Q: For the Frozen Lake environment, when estimating the Q functions using Monte Carlo sampling (all other choices being the same as Fig. 5), we found that the variance resulting from Monte Carlo sampling (even with 1000 samples) dominates the bias. As result, the effect of the critic loss is minimal, and all algorithms result similar performance.
48


Reviews:
[{"review_id": "KKs20N6wTN", "reviewer": "Reviewer_NBGk", "summary": "This research addresses the mismatched objectives in actor-critic (AC) methods used in reinforcement learning (RL). By introducing a joint objective for training the actor and critic in a decision-aware fashion, a generic AC algorithm is developed. The algorithm ensures monotonic policy improvement regardless of the policy and critic parameterization. The proposed approach offers advantages over traditional methods, as demonstrated through rigorous analysis and empirical evaluations.", "questions": "na", "limitations": "na", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "I think this work really pushes the RL community research efforts further by answering:\n\n> can we design a generic actor critic algorithm with joint objective?\n\nThe main contribution of generic actor critic algorithm with joint objective is a really nice idea worthy for publication at NeurIPS.", "weaknesses": "I have only have one minor weakness for this work as follows:\n\n> Using linear representations as \"general function approximation\" is a bit weak. I presume this is the reason why only simple RL problems have been demonstrated in this work.\n\nI am open to discussions with the authors and reviewers to increase my score. All the best for future decisions!", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback and address their questions below. \n\n[1] *Using linear representations as general function approximation is a bit weak. I presume this is the reason why only simple RL problems have been demonstrated in this work*\n\nWe emphasize that the main contribution of this work is to develop a theoretically principled framework for jointly training the actor and critic while being able to handle general function approximation. Consequently, our main theoretical results (Propositions 1-3) hold for function approximation schemes beyond linear models. For example, Proposition 2 holds for *any* actor or critic parameterization and demonstrates monotonic policy improvement for general function approximation. This is in contrast with existing work that focuses on tabular or linear parameterization for the actor and/or critic. \n\nFrom an experimental perspective, we chose to use simple RL problems to demonstrate the importance of being decision-aware. These simple experiments enable us to isolate and study the effect of the critic loss (the standard squared TD loss vs the decision-aware loss instantiated in Prop 4,6), without non-convexity or optimization issues acting as confounders."}, {"review_id": "HSGwVUxlZN", "reviewer": "Reviewer_os4C", "summary": "The authors develop a generic decision-award AC algorithm where both the actor and the critic take steps iteratively to optimize some “policy improvement lower bound” under the FMAPG framework. In essence, each step takes the gradient estimation error as the critic error, and characterizes the policy improvement in terms of the estimated gradient $\\hat g$. This result seems to come from the Taylor expansions of the Bregman divergence. The authors argue that since both the actor and the critic act in a cooperative manner, the critic therefore only focuses on parts of the state-action pairs that have the largest impact on the actor’s performance improvement. The authors provide the conditions for monotonic policy improvement and show that the algorithms converge to some stable points. Examples and experiments show that the proposed algorithm outperforms TD/AdvTD methods on certain tasks.", "questions": "1. In practice, buffers containing trajectories collected under history policies are commonly used. Is there any evidence showing that your algorithm can handle the distribution shift issue?\n\n2. Can you perform gradient steps for the actor/critic simultaneously? If so, what are the relative step sizes for the inner and the outer loops?", "limitations": "No concerns here.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The algorithm is interesting and well-motivated. Although the idea is not new to the RL community, the theoretical results in this work are sound and in general support the authors’ claims. Moreover, the paper is well written and I find most of the statements clearly presented. ", "weaknesses": "In order to perform GD/SGD, you at least need to rollout trajectories collected under $d^{\\pi_t}$. I didn’t find evidence supporting the sample efficiency of the proposed algorithm as you have claimed. Questions include:\n1. How many samples are used for each GD step in your experiment? \n2. How large is the variance of the proposed algorithm compared to TD/AdvTD when the sampling budget is limited, especially when the samples do not have sufficient coverage? \n4. How do the relative scales of $m_c$ and $m_a$ influence your results?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback and address their questions below. \n\n[1] *How many samples are used for each GD step in your experiment?*\n\nWe varied the number of samples -- $\\{1000, 5000\\}$ for Cliff World and $\\{1000, 10000\\}$ for Frozen Lake in order to estimate the $Q^\\pi, A^\\pi$ functions for a linear critic. These $Q^\\pi, A^\\pi$ estimates were then used to update the parameters of the linear actor. All details about the number of samples, step-sizes, and number of inner-loops are presented in Appendix F. \n\n[2] *How large is the variance of the proposed algorithm compared to TD/AdvTD when the sampling budget is limited, especially when the samples do not have sufficient coverage?*\n\nOur preliminary experiments reveal that the variance in the gradient estimator $\\hat{g}_t$ (and hence in the $Q^\\pi, A^\\pi$ functions) affects the performance of all the compared methods in a similar manner. While it is important to control the variance and evaluate the methods when the samples do not have sufficient coverage in practice, our experiments are designed to study and isolate the effect of the critic loss. The form of the critic loss becomes important when the bias (because of using function approximation with limited capacity) dominates the variance. Hence, we did not evaluate the methods in the small sample regime, but rather used the same number of samples for all methods, and compared their relative performance. We will clearly explain this in the final version of the paper.\n\n[3] *How do the relative scales of $m_a$ and $m_c$ influence your results?*\n\nNote that **we do not update the actor and critic in a two time-scale setting (one environment interaction and update to the critic followed by an actor update)**. Hence, the *relative* scales of $m_a$ and $m_c$ do not influence our results. \n\nThe proposed actor-critic algorithm is similar to the protocol in [2,60] in our references. Specifically, the critic interacts with the environment in *batch* and uses these interactions to form $\\nabla \\hat{J}(\\pi)$ and form the decision-aware critic loss (Line 4 in Alg. 1). The critic is then trained (using $m_c$ inner-loops) to minimize the critic loss and form $\\hat{Q}^\\pi, \\hat{A}^\\pi$ estimates (Lines 5-8 in Alg. 1). These estimates are used to train the actor (using $m_a$ inner-loops) to maximize the surrogate function and update the policy. The performance of Alg. 1 monotonically improves with increasing $m_c$ and $m_a$ -- increasing $m_c$ ensures smaller critic error while increasing $m_a$ ensures better surrogate optimization for the actor. This effect is captured in theory by Proposition 3 (please see lines 253-255)\n\n[4] *In practice, buffers containing trajectories collected under history policies are commonly used. Is there any evidence showing that your algorithm can handle the distribution shift issue?*\n\nFor the current paper, our experiments are designed to isolate and study the effect of the critic loss, without non-convexity, optimization, and distribution shift issues acting as confounders. Consequently, we did not perform large-scale experiments that require the use of replay buffers. \n\nHowever, we note that the proposed framework can systematically incorporate the use of a replay buffer. In particular, in our framework, the policy at which the gradient is computed can be any policy, not just the current one. Hence, a buffer containing trajectories from multiple history policies can be used to construct the surrogate $\\ell_t(\\theta)$ around that mixture of policies, which is perfectly valid. In order to incorporate a replay buffer with our framework, we can also make use of alternative algorithms such as dual-averaging in the policy space. This would enable us to utilize the gradient estimates from history policies and make use of the replay buffer. We aim to pursue this interesting direction in the future. \n\n[5] *Can you perform gradient steps for the actor/critic simultaneously? If so, what are the relative step sizes for the inner and the outer loops?*\n\nAs explained above, we do not perform gradient steps for the actor/critic simultaneously in a two time-scale setting. Hence, their relative step-sizes do not influence our results. In practice, we set $\\alpha_a$ and $\\alpha_c$ using an Armijo line search, and vary $\\eta$, the outer step-size used to instantiate the surrogate function for the actor. Please refer to Appendix F for further details. "}, {"review_id": "7Nu2JEWpKD", "reviewer": "Reviewer_odRi", "summary": "The paper addresses the issue of objective mismatch in Actor-Critic methods by designing a joint objective that enables training the actor and critic in a decision-aware manner. The proposed algorithm ensures monotonic policy improvement, irrespective of the chosen policy and critic parameterization.", "questions": "In complex real-world environments, $\\Delta_\\pi J(\\pi)$could only be estimated, e.g. using MC sampling. And for large MDPs, function approximation error of Q is unavoidable for large MDPs. The article provides experiments on two simple environments, Cliff World and Frozen Lake, using linear/tabular action and Linear cirtic. Thus, my questions are:\n\n(1) Can the algorithm be applied to more challenging environments, such as the standard benchmark tasks in MuJoCo? If so, how well does it perform in those environments? If there are limitations or challenges in applying the algorithm to more difficult tasks, it would be helpful to elaborate on those limitations.\n\n(2) Does the algorithm introduce significant extra time overhead compared to other methods? It would be useful to report the additional time required by the algorithm on the Cliff World and Frozen Lake environments.", "limitations": "Potential Challenges in Complex Environments: The applicability of the proposed algorithm to more complex environments, such as those found in the MuJoCo benchmark tasks, remains uncertain. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents an algorithm that guarantees monotonic policy improvement and has solid theoretical foundations.", "weaknesses": "The experimentation in the paper is somewhat limited, which may raise concerns about the algorithm's performance in more complex environments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback and address their questions below. \n\n[1] *Can the algorithm be applied to more challenging environments, such as the standard benchmark tasks in MuJoCo? If so, how well does it perform in those environments? If there are limitations or challenges in applying the algorithm to more difficult tasks, it would be helpful to elaborate on those limitations.*\n\nWe emphasize that the aim of this paper is to lay down the theoretical foundations of decision-aware actor-critic algorithms. Our experiments are designed to isolate and study the effect of the critic loss, without non-convexity or optimization issues acting as confounders. While we intend to evaluate the proposed algorithm on an extensive deep RL benchmark in the future, these experiments are beyond the scope of the current work. \n\nHowever, we note that the algorithm can be directly used for more challenging environments. In order to do so, we would require more complex actor/critic parameterization in order to better generalize across states/actions. Theoretically, the monotonic policy improvement guarantees in Proposition 2 would still hold.\n\nFrom a practical perspective, Alg. 1 can be directly used with any actor/critic parameterization. With respect to hyper-parameter tuning, $\\eta$ is only dependent on the smoothness of $J$ w.r.t $\\pi$ and does not depend on the actor/critic parameterization. On the other hand, $\\alpha_{a}$ and $\\alpha_{c}$ are set adaptively using an Armijo line search. The line-search procedure only requires the smoothness of the actor/critic objectives and does not rely on these objectives being convex. Finally, since our actor-critic framework does not involve a two time-scale algorithm, the relative scales of $m_a$ and $m_c$ (the number of actor/critic updates) do not influence our results, and the performance improves with increasing $m_a$ and/or $m_c$ (see the discussion in lines 253-255 following Proposition 3).   \n\nOne limitation of the proposed algorithm is setting the hyper-parameter $c$. While we have a heuristic to set $c$ (see Appendix F.1), its effect on the performance for challenging environments is unclear. However, we do note that such hyper-parameter tuning is a major issue even for the standard algorithms in practice. \n\n[2] *Does the algorithm introduce significant extra time overhead compared to other methods? It would be useful to report the additional time required by the algorithm on the Cliff World and Frozen Lake environments.*\n\nNo, compared to the other methods, the proposed algorithm involves minimizing a different loss function with respect to the critic and does not introduce significantly extra time overhead. \n"}, {"review_id": "OFlQ9VwLtL", "reviewer": "Reviewer_uLAb", "summary": "The authors present a decision aware actor-critic algorithm and then try to analyse the same. Subsequently they also provide some numerical results. ", "questions": "I have given my questions in detail above.", "limitations": "I think the analysis of convergence is flawed since there are no assumptions or results  regarding (a) Lipschitz continuity of the objectives, (b) step-sizes used in the actor-critic scheme, (c) stability of the two coupled recursions, (d) fast mixing nature of the Markov noise, etc., have been made or shown. Moreover, from my comments mentioned above, the paper lacks on several fronts and will require significant revision and re-review in order to be publishable.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The authors try and provide an analysis of an actor-critic algorithm. However, there are a number of questions that are unclear to me that I write in detail below.", "weaknesses": "I am writing down the entire list of comments on the paper below. One can call these weaknesses as these points have not been explained well or there are issues in the explanations provided.\n\n1. The authors say in the introduction that the objective of the critic is to minimize the value estimation error across all states and actions. This is incorrect since a critic's job is to estimate the expected TD error for any given policy provided by the actor and the actor's job is to find the policy that minimizes this expected TD error over policies. The authors seem to mention this at multiple places.\n\n2. Weird notation: J_s(\\pi) is well defined but what is J_s(\\rho)? Note that \\rho is the initial state distribution and then you say J(\\pi) = E[J_s(\\rho)]! \n\n3. Note that d^\\pi and \\mu^\\pi are not valid probability distributions. How do you then value sample states or state-action tuples from these?\n\n4. What does it mean to say that since p^\\pi(s,a) is a probability, you can write it in the Boltzmann form as you have written. Is it always possible to express any probability distribution as some Boltzmann distribution? Later you introduce a parameterization \\theta to this distributional form. Why not directly give a parameterized Boltzmann probability if that is what you want for the ramdomized policy instead of doing this in such a round about manner.\n\n5. In the definition of \\pi_{t+1} in Section 3.1, obviously \\eta plays a major role. What values can it take?\n\n6. For the blue term on page 4, you mention that as c decreases, critic error decreases. I don't see how? As c decreases, the first term inside D_{\\Phi^*}(.,.) will decrease as c decreases but that term is multiplied by 1/c which will blow up as c decreases. \n\n7. Algorithm 1: How do you compute $\\nabla_v L_t (v_k) and \\hat{g}_t?\n\n8. Step-sizes and stability of the algorithm: You use \\alpha_c and \\alpha_a as the step-sizes for the critic and actor respectively. I don't see any conditions written on these step-sizes. The reason is that actor-critic algorithms are meant to track policy iteration. This requires that the critic recursion moves on a faster timescale as compared to the actor recursion. When diminishing step-sizes are used, one requires that $\\alpha_a go to zero at a rate faster than \\alpha_c in order to get this effect of asymptotic convergence. Furthermore, the authors do not mention anything about the stability of their procedure. How does one ensure that this algorithm is stable - a precondition to ensuring convergence.\n\n9. Since you do not assume anything about mixing times of the underlying Markov process under any policy, how do you ensure that Markov noise does not create any problems in convergence of the scheme, see for instance,Sajad Khodadadian, Zaiwei Chen, Siva Theja Maguluri, \"Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm,\" ICML 2021.\n\n10. In Proposition 2, what are the terms \\tilde{H}_t^\\dagger and [\\hat{g}_t]_{s,a}?\n\n11. How does one interpret Proposition 3? Not clear at what rate the second term decreases and whether it even does so? In the absence of a proof of decrease and the rate at which it happens, the result is meaningless. \n\n12. In Section 4, you give a monotonic policy improvement result. TRPO also has a similar result. Which one is better - the improvement provided by your algorithm or TRPO?\n\n13. Mistakes: Section 5.1 - you say \\nabla_\\pi J(\\pi) = d^\\pi(s) Q^\\pi(s,a). What is s and what is (s,a) on the RHS since the LHS does not have any s or (s,a) tuple? Also, in Section 5.2, you say \\nabla_\\pi(J(\\pi)) = d^\\pi(s) A^\\pi(s,a) p^\\pi(a|s)? What are s, a on RHS. There is clearly a mistake since LHS does not depend on these quantities. Also, how do you reconcile these two definitions for the same object?\n\n14. The bandit proposition 5 and also 7 suddenly come in and appear crude with such assumptions as deterministic rewards, deterministic Q-value updates etc. It is not clear why these results have been provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Part 2 of the rebuttal (please refer to the global rebuttal for Part 1)**\n\n[4] *...don't see any conditions written on the step sizes...*\n\nBoth step-sizes $\\alpha_c$ and $\\alpha_a$ can be set according to the smoothness of the critic ($L_t(\\omega)$) and actor ($\\ell_t(\\theta)$) objectives. Using such step-sizes is enough for Proposition 3 to hold. Setting these step-sizes is orthogonal to the main message of the paper, and we relegated these details to the Appendix (see Lines 705-707) where we directly make use of the result and associated step sizes in [26]. In practice, we set both step-sizes adaptively using an Armijo line-search which, by definition, guarantees ascent (descent) for the actor (critic) objectives respectively. \n\n[5] *How does one interpret Proposition 3?*\n\nProposition 3 proves an $O(1/T)$ convergence of the policy to the *neighborhood* of a stationary point of $J$. Such results proving convergence to a neighborhood that depends on the critic error are common in the literature (see [2,23,60,61] in our references). As we explain in Lines 245-255, the second term is the critic error, which in turn, depends on the optimization error and the bias due to the function approximation. When using a large value of $m_c$ and a sufficiently expressive critic parameterization, the critic error in the second term can be driven to zero. \n\n[6] *...Is it always possible to express any probability distribution as some Boltzmann distribution? Later you introduce a parameterization $\\theta$ to this distributional form. Why not directly give a parameterized Boltzmann probability...?*\n\nIndeed, any distribution can be represented using a softmax transformation such that $p^\\pi(a|s) \\propto \\exp(z^\\pi(s, a))$. As explained in Section 2 (Functional representation vs Policy parameterization), we explicitly distinguish between the functional representation of a policy and its parameterization. Specifically, we can use any function approximation to parameterize either the distribution $p^\\pi(a|s)$ (the direct representation of a policy) or its logits $z^\\pi(s, a)$ (the softmax representation of a policy). This abstraction is important because it enables us to prove monotonic policy improvement results for *any* actor/critic parameterization (Proposition 2). \n\n[7] *What values can $\\eta$ take in the definition of $\\pi_{t+1}$*\n\nSection 3 considers a general functional representation of the policy. For Proposition 1 to hold, $\\eta$ needs to be set such that $J + \\frac{1}{\\eta} \\Phi$ is convex (please see the Proposition 1 statement). In Section 5, we instantiate the generic framework and this gives more concrete requirements on $\\eta$. For example, for the softmax representation in Proposition 6, $\\eta$ needs to be set to $1 - \\gamma$.  \n\n[8] *For the blue term on page 4, you mention that as c decreases, critic error decreases. I don't see how?*\n\nAs mentioned in Lines 194-195, in order to gain some intuition about the effect of $c$, we use a second-order Taylor series expansion (around $c = 0$) which shows that the $D_{\\Phi^*}$ term is proportional to $c$. As a simple example, choose $\\Phi$ to be the Euclidean mirror map, in which case the $D_{\\Phi^*}$ term becomes equal to $\\frac{c}{2} || \\nabla J(\\pi_t) - \\hat{g}_t ||^{2}$.\n\n[9] *Algorithm 1: How do you compute $\\nabla_v L_t (v_k)$ and $g_t$?*\n\nAlgorithm 1 is a *generic* algorithm and the computation of $\\nabla_v L_t (v_k)$ and $g_{t}$ depends on the choice of the functional representation. We instantiate both these quantities for the direct and softmax functional representations in Section 5. For example, for the direct representation (Line 278), $[g_t]_{s, a} = d^{\\pi_t}(s)  \\hat{Q}^{\\pi_t}(s, a)$. $L_t (\\omega)$ is defined in Proposition 4 and corresponds to the blue term. In practice, we use a sample-based approximation of $L_t(\\omega)$ and compute its gradient using automatic differentiation.\n\n[10] *The bandit proposition 5 and also 7 suddenly come in...*\n\nAs is explained in Lines 104-105, 283-284, we aim to demonstrate the effectiveness of using the proposed decision-aware critic loss over the squared critic loss typically used in practice. Consequently, we consider bandit examples to demonstrate that even for extremely simple examples (2-armed bandit with deterministic rewards, a special case of the multi-armed bandit, and hence RL problem), the **typical actor-critic algorithm that relies on minimizing the squared loss can fail to converge to the optimal policy, whereas the proposed decision-aware actor-critic algorithm converges to the optimal policy**.  \n\n[11] *Weird notation: $J_s(\\pi)$ is well defined but what is $J_s(\\rho)$?* \n\nThis is a typo, and it should be $J(\\pi) = E_{s \\sim \\rho}[J_s(\\pi)]$.\n\n[12] *Note that $d^\\pi$ and $\\mu^\\pi$ are not valid probability distributions.* \n\nThe definition of $d^\\pi$ has a missing normalization factor of $1 - \\gamma$, which makes $d^\\pi$ a valid probability distribution. With this correction, $\\mu^\\pi$ is also a valid distribution. \n\n[13] *In Proposition 2, what are the terms $\\tilde{H}_t^\\dagger$ and $g_t$?* \n\nAs explained in Section 3, $g_t \\in \\mathbb{R}^{SA}$ is any gradient estimator used to approximate $\\nabla J(\\pi_t)$, and $[g_t]_{s,a}$ is the $(s,a)$ component of this vector. The matrix $\\tilde{H}_t$ is defined in Proposition 2, and $\\tilde{H}_t^\\dagger$ denotes the matrix pseudo-inverse. We will clarify this in the final version of the paper. \n\n[14] *...you say $\\nabla_\\pi J(\\pi) = d^\\pi(s) Q^\\pi(s,a)$. What is s and what is (s, a) on the RHS...*  \n\n$\\nabla J(\\pi) \\in \\mathbb{R}^{SA}$ and the statement in Section 5.1 should be fixed to $[\\nabla J(\\pi)]_{s, a}$ $= d^\\pi(s) Q^\\pi(s, a)$. \n\nSimilarly, in Section 5.2, $[\\nabla J(\\pi)]_{s, a}$ $= d^{\\pi}(s) A^{\\pi}(s, a) p^{\\pi}(a|s)$ where the (s,a) subscript denotes the component corresponding to state $s$ and action $a$. "}]

Author rebuttal:
**We respond to the major comments in the review of Rev. uLAb here. We believe that it would be helpful for all the reviewers to go through this response as it highlights the paper's key contributions, addressing possible misunderstandings**

We thank the Rev. uLAb for their feedback. However, we note that **the weaknesses highlighted by the reviewer stem from a misunderstanding of the paper's setting, or consist of notational typos that do not affect the results. In this part, we address their major misunderstanding about the actor-critic setting studied in our paper. Due to constraints on the rebuttal length, we address the notational typos and other questions in Part 2 (the direct rebuttal to Rev. uLAb).**

[1] *... a critic's job is to estimate the expected TD error for any given policy provided by the actor and the actor's job is to find the policy that minimizes this expected TD error over policies...*

The reviewer's understanding is incorrect -- the critic's job is to estimate/learn a policy's value, whereas TD methods are one way to do so. For example, please refer to [Konda et al, Actor-Critic Algorithms], the original actor-critic paper which clearly says this as *The critic uses an approximation architecture and simulation to learn a value function* 

[2] *I think the analysis of convergence is flawed since there are no assumptions or results regarding (a) Lipschitz continuity of the objectives, (b) step-sizes used in the actor-critic scheme, (c) stability of the two coupled recursions, (d) fast mixing nature of the Markov noise, etc., have been made or shown.*

First, note that **Alg.1 does not update the actor and critic in a two time-scale setting (one environment interaction and update to the critic followed by an actor update)**. The proposed actor-critic algorithm is similar to the protocol in [2,60] in our references. Specifically, the critic interacts with the environment in *batch* and uses these interactions to form $\nabla \hat{J}(\pi)$ and form the decision-aware critic loss (Line 4 in Alg. 1). The critic is trained (using $m_c$ inner-loops) to minimize the critic loss and form $\hat{Q}^\pi, \hat{A}^\pi$ estimates (Lines 5-8 in Alg. 1). These estimates are used to train the actor (using $m_a$ inner-loops) to maximize the surrogate function and update the policy. **Since we are not in the two time-scale setting, the relative scales of the actor/critic step-sizes or the number of inner loops do not influence the performance of Alg 1**.  We now compare our results to the two time-scale analyses (for example, in [59] in our references) of actor-critic. 
1. Since we do not update or analyze the actor and critic in a two time-scale setting, we do not need to consider coupled recursions, nor do we need to set the two step-sizes at different scales.
2. We do not require Lipschitz continuity of either the actor or critic objectives but assume that the actor objective is smooth for our theoretical results in Proposition 3. Proposition 2 does not require any such smoothness assumption for either the actor/critic. 
3. **Both Propositions 2 and 3 are independent of how the critic loss is minimized** i.e. we could use TD or any other policy evaluation method in order to estimate the value function. Proposition 2 provides necessary and sufficient conditions on the magnitude of the critic error in order to ensure monotonic policy improvement (and hence convergence to a stationary point). On the other hand, Proposition 3 guarantees convergence to a *neighborhood* of a stationary point, where the neighborhood depends on the critic error. This result holds for *any* critic error and is similar to the results obtained in [2,23,60] (see Lines 259-262 for a discussion). Since these results are agnostic to how the critic error is minimized, we do not need to model the mixing of the Markov chain, and consequently make no assumptions. 
4. **Compared to the existing actor-critic analyses (for example [59,61]), our theoretical results require fewer assumptions on the function approximation.** For example, the monotonic policy improvement result in Proposition 2 holds for *any* actor or critic parameterization (including complex neural networks). In contrast, the typical analyses of actor-critic that utilize a two time-scale update only work with tabular or linear function approximation for the actor/critic. 
5. Since we do not explicitly model how the critic error is minimized, we can only prove convergence to the neighborhood of a stationary point. This is in contrast to the existing two time-scale analyses that jointly analyze the actor and critic, and show convergence to a stationary point (see [59] for example). Hence, we prove weaker results for a more general class of function approximation. We briefly explain this in Lines 255-265 and will add a more thorough comparison in the final version of the paper.
6. Finally, **our analysis supports off-policy updates i.e. the actor can re-use the value estimates (from the critic) to update the policy multiple times (corresponding to Lines 10-13 in Alg 1)**. This is possible because we explicitly distinguish between a policy's functional representation and its parameterization. This is in contrast to existing analyses of actor-critic methods that require interacting with the environment and gathering new data after each policy update. 

[3] *You give a monotonic policy improvement result. Which one is better - the improvement provided by your algorithm or TRPO?*

**The monotonic policy improvement result for TRPO only holds for the tabular setting, does not handle function approximation nor does it handle the critic error**. As explained in Lines 225, Proposition 2 presents a condition to ensure monotonic policy improvement *regardless of the policy representation and parameterization of the policy or critic*. Compared to TRPO, our result can thus handle the critic error and *any* function approximation for the actor/critic.  

Meta-review: The actor-critic algorithms are often developed by designing a "good" actor and a "good" critic. It is not, however, obvious what it means for an actor or critic to be good. Ideally the critic should be designed in order to be useful for the actor. This paper approaches the problem of finding good actor and critic by formulating it as a Mirror Descent optimization problem where the effects of both actor and critic jointly appear. The choice of mirror map determines the loss function for both actor and critic. This leads to perhaps unexpected result that the right loss function for critic should not necessarily be the squared error between the action-value function estimate and the true value function of the policy.

We have three Accepts and one Reject. We had some discussions between the authors and reviewers, but the negative reviewer (uLAb) was not convinced about some technical detail of the paper. Reviewer uLAb's main issue is that the they consider the algorithm as a two time-scale stochastic approximation procedure, and demanded guarantees for stability.

I read the paper myself. I believe this is an important work for the RL community, as it lays a new optimization-based foundation for how we approach designing actor-critic algorithms.

I also see why Reviewer uLAb, who raised several good questions, had some concerns about the paper that were not eventually resolved. My short summary of the reason is that some of the results of the paper, especially those in Section 4 (Theoretical Guarantees), are a bit opaque and need more discussions and explanations. For example, it is difficult to clearly see the effect of choice of the inner optimization of the critic and actor, specified by the choice of m_c and m_a, on the final results. Proposition 3 has a O(exp(-m_a)) dependency, without specifying the constants. And m_c does not appear, as far as I can see, except indirectly through delta_t.

Or the LHS of Proposition 3 is difficult to interpret. It shows how far one iteration of the exact MD vs. Inexact MD (with a critic error) performs. The consequence of this is only briefly, and not very concretely, discussed in the paragraph afterwards. I would love more explanation, discussions, and examples there.

Overall, I believe this a good paper that has important results and has some room to be improved by trying to address reviewers comments and concerns, especially those that are based on a misunderstanding.

Other minor comments:
- Please increase the number of runs from 5 to a much larger value, especially given that the environments are very simple and the overlap between some curves is substantial.

- Calling the standard squared loss on the Q function "TD" is inaccurate, as Q is either computed exactly or through Monte Carlo estimate. There is no bootstrapping here to warrant calling it TD. This is simply MSE error.
Decision: Accept (poster)