Your Policy Regularizer is Secretly an Adversary
Authors: Rob Brekelmans
Tim Genewein
Jordi Grau-Moya
Gregoire Detetang
Markus Kunesch
Shane Legg
Pedro A Ortega
Venue: Accepted by TMLR ()

Abstract: Policy regularization methods such as maximum entropy regularization are widely used in reinforcement learning to improve the robustness of a learned policy. In this paper, we unify and extend recent work showing that this robustness arises from hedging against worst-case perturbations of the reward function, which are chosen from a limited set by an implicit adversary. Using convex duality, we characterize the robust set of adversarial reward perturbations under KL- and $\alpha$-divergence regularization, which includes Shannon and Tsallis entropy regularization as special cases. Importantly, generalization guarantees can be given within this robust set. We provide detailed discussion of the worst-case reward perturbations, and present intuitive empirical examples to illustrate this robustness and its relationship with generalization. Finally, we discuss how our analysis complements previous results on adversarial reward robustness and path consistency optimality conditions.

Published in Transactions on Machine Learning Research (07/2022)
Your Policy Regularizer is Secretly an Adversary
Rob Brekelmans
brekelma Cusc eduu
University of Southern California
Information Sciences Institute
Tim Genewein
Jordi Grau-Moya
Grégoire Delétang
Markus Kunesch
Shane Legg
Pedro Ortega
pedro. Berteggg@maaiie com
Deed
Reviewed on OpenReview: https: openreview. net/ forum? id= XXXX
Abstract
Policy regularization methods such as maximum entropy regularization are widely used in reinforcement. learning to improve the robustness of a learned policy. In this paper, we unify and extend recent work showing that this robustness arises from hedging against worst-case perturbations of the reward function, which are chosen from a limited sot by an implicit adversary. Using convex duality, we characterize the robust set of adversarial reward perturbations under KI.- and a-divergence regularization, which includes Shannon special cases. Importantly, generalization guarantees
and Tsallis entropy regularization can be given within this robust set. We provide detailed discussion of the worst-case reward perturbations, and present intuitive empirical examples to illustrate this robustness and its relationship with gencralization. Finally, we discuss how our analysis complements previons results on adversarial reward robustness and path consistency optimality conditions.
1 Introduction
Regularization plays a crucial role various scttings across reinforcement learning (RL.), such as trust-region methods (Peters et al., 2010; Schulman et al., 2015; 2017; Bas-Serrano et al., 2021), offline learning (Levine et al., 2020; Nachum et al., 2019a;b; Nachum & Dai, 2020), multi-task learning (Teh et al, 2017; Igl et al., 2020), and soft Q-lcarning or actor-critic methods (Fox et al., 2016; Nachum et al., 2017; Haarnoja et al., 2017; 2018; Grau-Moya et al., 2018). Various justifications have been given for policy regularization, such as improved optimization (Ahmed et al., 2019), connections with probabilistic inference (Levine, 2018; Kappen et al., 2012; Rawlik et al., 2013; Wang et al., 2021), and robustness to perturbations in the environmental rewards or dynamics (Derman al., 2021; Eysenbach & Levine, 2021; Husain et al., 2021).
In this work, ularization in RL. In particular, we interpret regularized reward maximization as two-player game between the agent and an imagined adversary that modifies the reward function. For policy π (als) regularized with a convex function 2(TT) = F,, [+(]]] and regularization strength 1/3, we investigate statements of the form
convex duality to analyze the reward robustness which naturally arises from policy reg-
Σ n (1(a,..) [0(r(arl))))
Σ E'r 8t) (1)
max (1 - 7) r(lss)
max min (1 (1-7) ET-)) *(gls) (R.
where r'(a, s) indicates modified reward function chosen from an appropriate robust set Rr (see Fig. 2). Eq. (1) suggests that agent. may translate uncertainty in its estimate of the reward function into

---

Published in Transactions on Machine Learning Research (07/202) /202)
1.2
1.1
1.0
0.9
0.8
0.7
Qls,a)
0.6
Worst-Case
0.6
0.8
1.0
1.2
1.4
1.6
((
Figure I: Robust set Rs (red region) of perturbed reward functions to which a stochastic policy generalizes, in the sense of Eq. (2). Red star indicates the worst-case perturbed reward r' = r -rr. (Prop. 2) chosen by the adversary. The robust set also characterizes the set of reward perturbations Ar(a,)) that are feasible for the adversary, which differs based on the choice of regularization function, regularization strength 3 and reference distribution xo (see Sec. 4.1 and Fig. 2). We show the robust set for the optimal single-step policy with value estimates ((a,s) s) = s) and KL divergence regularization to uniform no, with B 1. Our robust set is larger and has a qualitatively different shape compared to the robust set of Derman et al. (2021) (dotted lines, see Sec. 5.2).
regularization of learned policy, which is particularly relevant in applications such as inverse RL (Ng al., 2000; Arora & Doshi, 2021) or learning from human preferences (Christiano et al., 2017).
This reward robustness further implies that regularized policies achieve a form of 'zero-shot' generalization to new environments where the reward is adversarially chosen. In particular, for any given T[als) and modified reward E Rr within the corresponding robust set, we obtain the following performance guarantee
((ar)))) 8t) f
(r(T)
Σ >'r' (at, st)
2 (T)(()))
Σ nd r(ar
(2)
Eq. (2) states that the expected modified reward under r(als), with r' R2 as in Fig. 1, will be greater than the value of the regularized objective with the original, unmodified reward. It is in this particular sense that we make claims about robustness and zero-shot generalization throughout the paper.
Our analysis unifies recent work exploring similar interpretations (Ortega & Lee, 2014; Husain et al., 2021; Eysenbach & Levine, 2021; Derman et al., 2021) as summarized in Sec. 5 and Table Our contributions include
A thorough analysis of the robustness associated with KL and a-divergence policy regularization, which includes popular Shannon entropy regularization as special case. Our derivations for the a-divergence generalize the Tsallis entropy RL framework of Lee et al. (2019).
We derive the worst-case reward perturbations Ar. r r- corresponding to any stochastic policy and fixed regularization scheme (Prop. 2).
For the optimal regularized policy in given enviromment, we show that the corresponding worst-case reward perturbations match the advantage function for any a-divergence. We relate this finding to the path consistency optimality condition, which has been used to construct learning objectives in (Nachum et al., 2017; Chow et al., 2018), and a game-theoretic indifference condition, which occurs at a Nash equilibrium between the agent and adversary (Ortega & Lee, 2014).
We visualize the set R2 of adversarially perturbed rewards against which a regularized policy is robust. in Fig. 1-2, with details Prop. 1. Our use of divergence instead entropy regularization to analyze the robust set clarifies several unexpected conclusions from previous work. In particular, similar plots in Eysenbach & Levine (2021) suggest that MaxEnt RL is not robust to the reward function of the training environment, and that increased regularization strength may hurt robustness. Our analysis in Sec. 5.1 and App. F.4 establishes the expected, opposite results.
We perform experiments for sequential grid-world task in Sec. 4 where, in contrast to previous work, we explicitly visualize the reward robustness and adversarial strategies resulting from our theory. We use the path consistency or indifference conditions to certify optimality of the policy.
2

---

Published in Transactions on Machine Learning Research (07/2022)
Ortega & Lee (2014)
Eysenhach Levine (2021)
Tasnin et al. (2021)
Derman et al. (2021)
Oars
Multi-Step Analysi
X
/ policy form /f (eee our App. F.4)
V
/ policy (via dual Eq. (11)
/ pohry V
Wonst-Case ar(e,s)
polcy
Robust Set
(Bexible specilication) derived from robust s(as)
Divergence Used
Shanmon entrogy (See. 5.1)
any conves
any cousex fl, o-Div examples
j(o, 9) or #t(ols) Reg.?
x(nls)
[(oss]
Both
Both
Indillerence
Path Consistoncy
X
X
Table 1: Comparison to related work.
2 Preliminaries
In this section, we review linear programming (LP) formulations of discounted Markov Decision Processes (MDP) and extensions to convex policy regularization.
Notation For a finite set X, let R denote the space of real-valued functions over X, with I& indicating restriction to non-negative functions. We let A denote the probability simplex with dimension equal to the cardinality of X. For u.g E R (v.g) = =2Ex ((z))(a)) indicates the inner product in Euclidean space.
2.1 Convex Conjugate Function
We begin by reviewing the convex conjugate function, also known as the Segendre-Fenchen transform, which will play crucial role throughout our paper. For convex function 2(μ) which, in context, has domain / E R the conjugate function Ω is defined via the optimization
(Arr
suup (n, 12p)) MER
(3)
where Ar x The conjugate operation is involution for proper, lower semi-contimuous, convex P (Boyd & Vandenberghe, 2004), so that (It)* = Ω and Q is also convex. We can thus represent U(u) via a conjugate optimization
Mpp
sup (r, - -AAr)-(((Ar))) ArER*
Differentiating with respect to the optimization variable in Eq. (3) or (4) suggests the optimality conditions
Par (Ar)
Arp V((u).
(5)
Note that the above conditions also imply relationships of the form Par (V12) This dual corre- spondence between values of μ and Ar will form the basis of our adversarial interpretation in Sec.
2.2 Divergence Functions
We are interested in the conjugate duality associated with policy regularization, which is often expressed using scal divergence 11(4) over joint density p(a,s) (as)=(als)) (see Sec. 2.3). In particular, we consider the family of a-divergences (Amari, 2016; Cichocki & Amari, 2010), which includes both the forward and reverse KL divergences as special cases. In the following, we consider extended divergences that accept unnormalized density functions as input (Zhu & Rohwer, 1995) so that we may analyze function space dualities and evaluate Lagrangian relaxations without projection onto the probability simplex.
KL Divergence The 'forward' KL divergence reference policy To(als) is commonly used for policy regularization in RI. Extending the input domain to unnormalized measures, we write the divergence as
Taals) To(a|s)
Dra (K) Ey(s) [KIIT: : nol]
Σ ((s) Σ T(als) log SES
(als)) ( no(als)).
(6)
aEA
Using a uniform reference no (als)) (a, we recover the Shannon entropy up to an additive constant.
a-Divergence The a-divergence Ep(s)) [D [To æI] over possibly unnormalized measures is defined
(1) a(1 a) SES
1 Σ ((s)) (1 (1-a) a) Σ To(als) + Σ T(als) - Σ (roaass)~~<(aap)) (7)
aEA
acA
aEA
3

---

Published in Transactions on Machine Learning Research (07/202)
Divergence
Conjugate
Conjugate Expression
Optimizing Argument (Far or par)
D mo)
To(als) (8 (8-Ar(a,s)
so(ale) exp (8 Ar(a, s))
ADalle po]
(Arr)
2 polo, 6) exp Ar(a, a)} -
polo, d) (8 Ar(a, s)]
3Dalmo :m]
10 (Ar)
31 Σ exp, & (Arla,)) -= (a.())) Tolals) {3 (Ar(a, s) )ar(o)8)1)
J.oboo :
Ba E. Hola,s) uxp, {B. sr(,, #
pola, 8) exp. {8- Ar(a,s)
Table 2: Conjugate Function expressions for KL and a-divergence regularization of cither the policy (als) occupancy s). See App. B.1-B.4 for derivations. The final column shows the optimizing argument in the definition of the conjugate function (Ar),,r,, for example Par = arg max, (H, Ar) - 3 (4). Note that each conjugate expression for ((ls) regularization also contains outer expectation over p(s).
Taking the limiting behavior, we recover the 'fowwrd'' KL divergence DKL(T: mol as a + 1 or the 'reverse' KL divergence D т] as a + 0.
To provide intuition for the a-divergence, we define the deformed a-logarithm as in Lee et al. (2019), which matches Tsallis's g-logarithm (Tsallis, 2009) for = 2 Its inverse is the a-cxponential, with
1 (u--1-1)
loga (u)
expa = [1 + (a 1) w|f
(8)
where [1- = max(.,0) 0) ensures fractional powers can be taken and suggests that exp, = for u < 1/(1 - a). Using the a-logarithm, we can rewrite the a-divergence similarly to the kL divergence Eq. (6)
2 (p) (p) (p)= - - m(s)
Σ
(als) loga
m(als) T(als) + mo(als))
To (als)
SES
cEAA
For uniform reference To, the a-divergence differs from the Thallis entropy by only the 1/a factor and additive constant (sce App. F.1).
2.3 Unregularized MDPs
A discounted MDP is a tuple dynamics P(5'ss, a) for 8,8 S, E A, initial state distribution us(s) E A in the probability simplex, and reward function r(a,s) : A- R. We also use a discount factor y E (0, (Puterman (1994) Sec 6).
r, consisting of a state space S, action space A, transition
We consider an agent that seeks maximize the expected discounted reward by acting according decision policy r(ass) A for each S. The expected reward is calculated over trajectories (T)) vo (so) II T P(se1//) dz), which begin from initial so vo(s) and evolve according to the policy <[als) and MDP dynamics a)
RC(r)= = max (1 - 7) R (rxx(T) s(als)
Σ z=
(9)
We assume that the policy is stationary and Markovian, and thus independent of both the timestep and trajectory history.
Linear Programming Formulation We will focus on a linear programming (LP) form for the objective in Eq. (9), which is common in the literature on convex duality. With optimization over the discounted state- action occupancy measure, p(a, s) = (1 ()())) 1E TTa(a = 0, = s)], we rewrite the objective as subject to m(a,s) 8) 2 v(a,8) E A
RC(r) max (1,r)
(10)
1
(1- + Σ (')ad,))) a',s'
E
We refer to the constraints the sccond line of Eq. (10) as the Bellman flow constraints, which force pla, s) respect the MDP dynamics. We denote the set of feasible i as M C RAXS For normalized vo(s) and P(s|a', 8'), show in App. A.2 that p(a, 8) E M implies p(a, 8) is normalized.
4

---

Published in Transactions on Machine Learning Research (07/2022)
It can be shown that any feasible p)a,s) E M induces a stationary x[als) s)aas)) where (u(s) == En ((a',s) ,)) and <(als) E AIAI is normalized by definition. Conversely, any stationary policy л A(ass) induces a unique state-action visitation distribution p(a,,) (Syed et al. (2008), Feinberg & Shwartz (2012) Sec. 6.3). Along with the definition of uu(a, s) above, this result demonstrates the equivalence of the optimizations in Eq. (9) and Eq. (10). We will proceed with the LP notation from Eq. (10) and assume jus)) is induced by (als) whenever the two appear together in an expression.
Importantly, the flow constraints in Eq. (10) lead to dual optimization which reflects the familiar Bellman equations (Bellman, 1957). To see this, introduce Lagrange multipliers V IS for each flow constraint and s(a,s) E RAxS for the nonnegativity constraints. Summing over 8 E S, and eliminating p(a, s) by setting d/dp(a s) = 0 yields the dual LP
RC* min - ()-0) v) subject to V(s) - r(a, BEd [V(')] + M(a V(a AxS, (11) V
where we have used Ei' [ss)) as shorthand for Ep(s' a, a (s') and reindexed the transition tuple from (s', a', 8) to (s, s') compared to Eq. (10). Note that the constraint applies for all (a, 8) E A S and that M(a s) 2 0. By complementary slackness, we know that M(a, s) for s) such that p(a, s) > 0.
2.4
Regularized MDPs
We now consider regularizing the objective in Eq. (10) using a convex penalty function 2(2)) with coefficient 1/3. We primarily focus on regularization using a conditional divergence Dr, (u) == (a(a))(als) [[(T]] between the policy and a normalized reference distribution mo(a))) as in Sec. 2.2 and (Ortega & Braun, 2013; Fox et al., 2016; Haarnoja et al., 2017; 2018). We also use the notation 2yg (u) = E ("(a)) to indicate regularization of the full state-action occupancy measure to a normalized reference uo(a, 8), which appears, for example, in Relative Entropy Policy Search (REPS) (Peters et al., 2010; Belousov & Peters, 2019). The regularized objective Rr), is then defined as
1
RL == max (1.r) - 2m (P) NEM
(12)
3
where 24, (1) contains an expectation under pla, 8) as in Eq. (0)-(7). We can also derive a dual version of the regularized LP, by first writing the Lagrangian relaxation of Eq. (12)
1
V. max min (1 - (o. V)+ (urr BB [V] V + X)-
- (1). B
(13)
Swapping the order of optimization under strong duality, we can recognize the maximization over juaa s) as a conjugate function z 1 no as in Eq. (3), leading to a regularized dual optimization
1 - (1 a.s [v] V +X)
RC) = min (1 - V.
(1--)((o)) (po. v) +
(14)
which involves optimization over dual variables (ss) only and is unconstrained, in contrast to Eq. (11). Dual objectives of this form appear in (Nachum & Dai, 2020; Belousov & Peters, 2019; Bas-Serrano et al., 2021; Neu et al., 2017). We emphasize the need to include the Lagrange multiplier Ma,s), with X(a, s) > 0 when the optimal policy has (als)) O, since important motivation for a-divergence regularization is to encourage sparsily in the policy (see Eq. (8), Lee et al. (2018; 2019); Chow el al. (2018)).
Soft Value Aggregation In iterative algorithms such as (regularized) modified policy iteration (Puterman & Shin, 1978; Scherrer et al., 2015), it is useful to consider the regularized Bellman optimality operator (Geist et al., 2019). For given estimates of the state-action value Q(a, 8) = r(a, 8) + >B;, [V()),, the operator Tan.. updates (s) as
1 V(s) + 3 Ωr (Q) = max
1 QT
3 200 (T).
(15)
REALA
Note that this conjugate optimization is performed in each state 8 E S and explicitly constrains each π (als) to be normalized. Although we proceed with the notation of Eq. (12) and Eq. (14), our later developments are compatible with the 'soft-value aggregation' perspective above. See App. C for detailed discussion.
5

---

Published in Transactions on Machine Learning Research (07 (0222)
3 Adversarial Interpretation
In this section, we interpret regularization as implicitly providing robustness to adversarial perturbations of the reward function. To derive our adversarial interpretation, recall from Eq. (4) that conjugate duality yields alternative representation of the regularizer
1 n (n)
1 max (1, Ar) 3 2 (Ar). AVERAxS
(16)
B
3
Using this conjugate optimization to expand the regularization term in the primal objective of Eq. (12),
1 oo 3 Ho. (Ar).
R max min (u,r Ar) PEM ARERANS
(17)
We interpret Eq. (17) as two-player minimax game between an agent and an implicit adversary, where the agent chooses an occupancy measure p(a,s) E M or its corresponding policy r(als), and the adversary chooses reward perturbations Ar(a, s) subject to the convex conjugate 20 (Ar) as penalty function (Ortega & Loe, 2014).
To understand the limitations this penalty imposes on the adversary, we transform the optimization over Ar in Eq. (17) to constrained optimization in Sec. 3.1. This allows to characterize the feasible set of reward perturbations available to the adversary or, equivalently, the set of modified rewards r'(a, s) Rr to which a particular stochastic policy is robust. In Sec. 3.2 and 3.4, we interpret the worst-case adversarial perturbations corresponding to an arbitrary stochastic policy and the optimal policy, respectively.
3.1 Robust Set of Modified Rewards
In order to link our adversarial interpretation to robustness and zero-shot generalization as in Eq. (1)-(2), we charactorize the feasible set of reward perturbations in the following proposition. We state our proposition for policy regularization, and discuss differences for p(a, 8) regularization in App. D.2.
Proposition 1. Assume normalized policy T(ass) for the agent is given, with E. <(als) 1 S. Under a-divergence policy regularization to normalized reference to(als), the optimization over Ar(a, s) in Eq. (17) can be written in the following constrained form
min (u, (aar-Ar) where R = E RAA orlo) 50].
(18)
AFERA
We refer to R C RAXS as the feasible set of reward perturbations available to the adversary. This translates to a robust set Rr of modified rewards s)) : = r(a, s) Ar(a, for the given policy. These sets depend on the didiveryence and regularization sirength B via the conjugate function.
For KL divergence regularization, the constroint is
Σ To(ass) exp Ar(a, s)} $1. aEA
(19)
(Ar) associated with various regularization schemes. The proof proceeds by evaluating the conjugate function at the minimizing argument Arz in Eq. (17) (see Sec. 3.2), with (Arr) = 0'a for normalized (aass) and (o(a))) The constraint then follows from the fact that (Ar,)) is convex and increasing in Ar (Husain et al., 2021). We visualize the robust set for a two-dimensional action space Fig. 2, with additional discussion in Sec. 4.1.
See App. D.1 for proof, and Table 2 for the convex conjugate function 4 (
As in Eq. (2), we can provide 'zero-shot' performance guarantees using this set of modified rewards. For any perturbed reward in the robust set r' E RR,, we have (u, 2 (n,r) - (μ4), so that the policy achieves an expected modified reward which is at least as large as the regularized objective. However, notice that this form of nobust sensitive the exact value of the regularized objective function. Although entropy regularization and divergence regularization with uniform reference induce the same optimal p(a, s), we highlight crucial differences in their reward robustness interpretations in Sec. 5.1.

---

Published in Transactions on Machine Learning Research (07 (07/2022)
3.2 Worst- Case Perturbations: Policy Form
From the feasible set in Prop. 1, how should the adversary select its reward perturbations? In the following proposition, we use the optimality conditions Eq. (5) to solve for the worst-case reward perturbations Arz(a, 8) which minimize Eq. (17) for an fixed but arbitrary stochastic policy T(ass).
Proposition 2. For given policy (a]ss) or state-action occupancy p(a,s), the worst-case adversarial reward perturbations ArT or Ar associated with concer function 92(p)) and regularization strength 1/3 are
Ar, 7(1)
(20)
See App. A.1 for proof. We now provide example closed form expressions for the worst-case reward per- turbations under common regularization schemes. We emphasize that the same stochastic policy aa s) or joint occupaney mcasure p(a,s) s) can be associated with different adversarial perturbations depending on the choice of a-divergence and strength 3.1
KL Divergence For KL. divergence policy regularization, the worst-case reward perturbations are
1 (als) (r,(u, = log
(21)
To ma(ss))
which corresponds to the pointwise regularization Arx(a, s) troo (I(aas) for each state-action pair, with 2mo (u) Eyta,s]S0x,, See App. B.1. We show an analogous result in App. B.2 for state-action occupancy regularization DKL[a: pol, where Arp(a, = log pla,s) = Q2 ()(a,
pola.s)
a-Divergence For KL divergence regularization, the worst-case reward perturbations had a similar expres- sion for conditional and joint regularization. However, we observe notable differences for the a-divergence in general. For policy regularization to a reference To,
1 (a,
loga T(ass) 3 no (a|s)
var((8 (8;
(22)
where we define (ar
(s; 8) = 3 a
11
Σ aaE
To(als) -
Σ REA
(23)
As we discuss in App. B.3, thar (s; 3) plays the role a normalization constant for the optimizing argument (ar(als) in the definition of 3 ( (Ar) (sce Eq. (3), Table 2). This term arises from differentiating 22 (n) with respect to p(a,s) instead of from an explicit constraint. Assuming the given (als) and reference To(a]s) s) are normalized, note that ('ar(s B) 1 all æ]. With normalization,
also observe that
(ar 3) = 0 for KL divergence regularization (a = 1), which confirms Eq. (21) is a special case of Eq. (22).
For any given state-action occupancy measure pla, s) and joint a-divergence regularization to reference po(als), the worst-case perturbations become
log u(a, s) Ary 8) = 3 [o(a, s)
(24)
with detailed derivations in App. B.4. In contrast to Eq. (22), this expression lacks an explicit normalization constant, as this constraint is enforced by the Lagrange multipliers V(s) and p(a,s) E M (App. A.2).
1 One exception that a policy with a' s.t. a(alls) (s) can only represented using kt. regularization mo(a'

---

Published in Transactions on Machine Learning Research (07 (07/2022)
3.3 Worst- Case Perturbations: Value Form
In the previous section, analyzed the implicit adversary corresponding to any stochastic policy rTals) for given Ω2 No. and B. We now take dual perspective, where the adversary is given access to a set of dual variables (s)) across states s E S and selects reward perturbations (ry s). We will eventually show in Sec. 3.4 that these perlurbations match the policy-form perturbations al optimality.
Our starting point is Theorem 3 of Husain et al. (2021), which arises from taking the convex conjugate (-))) of the entire regularized objective ( which is concave in p(a.s). s). See App. E.1.
Theorem 1 (Husain et al. (2021)). The optimal value of the regularized objective RLa,a(r) in Eq. (12), or its dual (r) in Eq. (14), is equal to
inf inf (1 - (v,, v) + 8 Staa (Arv)
1
(25)
V.A Arv
subject to V(s) r(a, 8) Ti [V(''] Arv(a, Ma, v(a,s)
Rearranging the equality constraint to solve for Arv s) and substituting into the objective, this opti- mization recovers the regularized dual problem in Eq. (14). We can also compare Eq. (25) the un- regularized dual problem in Eq. (II), which does not include an adversarial cost and whose constraint V(s) r() + [(s') + X(a, s) implics unmodified reward, or (ry = O. Similarly to Sec. 3.2, the adversary incorporates the effect of policy regularization via the reward perturbations Ary (a, 8).
3.4 Policy Form = Value Form at Optimality
In the following proposition, we provide a link between the policy and value forms of the adversarial reward perturbations, showing that Ar.. (a = Arv. (a, s) for the optimal policy T. and value (s).. As in Eysenbach & Levine (2021), the uniqueness of the optimal policy implies that its robustness may be associated with an environmental reward r(a, s) for a given regularized MDP.
Proposition 3. For the optimal policy x. (als) and value function V=(s) corresponding to a-divergence policy regularization with strength B, the policy and value forms of the worsl-case adversarial reward perturbations match, Ars, Arv,, and are related to the advantage function via
Arn. (a. 8) (a - V.(s) + (a,
(26)
where we define ()) == r(a, 8) +) [v'(')] and recall A. (a, S)T, (als) = 0 by complementary slackness.
Note that V.(s) depends on the regularization scheme via the conjugate function } (01 in Eq. (25).
Proof. See App. A.3. We consider the optimal policy in MDP with a-divergence policy regularization 1 1. (p), (p), which is derived via similar derivations as Lee et al. (2019) or by climinating p(a, s) Eq. (13). B
(als) =o(als) exp., {s (Q-(a, Vs(s) + X(a, var.. (s;
(27)
We prove Prop. 3 by plugging this optimal policy into the worst-case reward perturbations from Eq. (22).
Ar.. sa = a log, so(e]s) Vars, ensures normalization for the policy corresponding to Arm. In App. C.3, we also show tho (8; B) V.(s) + thrt. B), where Uo. (s: B) is Lagrange multiplier enforcing normalization in Eq. (15).
z=(ale) + vart, (s) We can also use Eq. (26) to verify ne (a]s) is normalized, since
Path Consistency Condition The equivalence between Arx. s) and Arv. (a, s) at optimality matches the path consistency conditions from (Nachum et al., 2017; Chow et al., 2018) and suggests generalizations to general a-divergence regularization. Indeed, combining Eq. (22) and (26) and rearranging,
T. (a]s) r(a, s) + BEC, [Vo(s') log.. (o(a))) Pare. (3: V.(s) - Aa
(28)
8

---

Published in Transactions on Machine Learning Research (07/2022)
21
06
16
26
36-
04
C2
14
24
14
(a) DKL,8= 0.1
B=L,B=1
(c) 3RL,8=10 10
(d) a -1, 10
(e) 0 3 3 10
5.s-
PeakieSe
Qhat
00.0
(1) D 0.1
(8) DRL, 3= =1
(h) D 10
(1 1,3 = 10
(1) a 3, = 10
Figure 2: Robust Set (red region) of perturbed reward functions to which a stochastic policy generalizes, in the sense that the policy is guaranteed to achieve an expected modified reward greater than or equal to the value of the regularized objective (Eq. (2)). The robust set characterizes the perturbed rewards which are feasible for the adversary. Red stars indicate the worst-case perturbed reward r'. - Ars, (Prop. 2). We show robust sets for the optimal (als) with fixed Q(a, s) = r(a,s) values (blue star), where the optimal policy differs based on the regularization parameters a., ,3, To (see Eq. (27)). The robust set is more restricted with decreasing regularization strength (increasing 3), implying decreased generalization. Importantly, the slope of the robust set boundary can be linked to the action probabilities under the policy (see Sec. 4.1).
for all 8 E S and a E A. This is a natural result, since path consistency is obtained using the KKT optimality condition involving the gradient with respect to μ of the Lagrangian relaxation in Eq. (13). Similarly, we have seen in Prop. 2 that Ar, 2o (p)). See App. A.4.
Path consistency conditions were previously derived for the Shannon entropy (Nachum et al., 2017) and Tsallis entropy with a 2 (Chow et al., 2018), but our expression in Eq. (28) provides generalization to a-divergences with arbitrary reference policies. We provide more detailed discussion in App. E.2.
Indifference Condition As Ortega & Lee (2014) discuss for the single step case, the saddle point of the minmax optimization in Eq. (17) reflects an indifference condition which is well-known property of Nash equilibria in game theory (Osborne & Rubinstein, 1994). Consider Q(a, r(a, 8) + + [V(s'] [V('s to be the agent's 's estimated payoff for each action in particular state. For the optimal policy, value, and worst-case reward perturbations, Eq. (28) shows that the pointwise modified reward (a, s) - Ar. = Vs(s) is equal to a constant. 2 Against the optimal strategy of the adversary, the agent becomes indifferent between the actions in its mixed strategy. The value or conjugate function V=(s) = x (Q=)) (see App. C) is known as the certainty equivolent (Fishburn, 1988; Ortega & Braun, 2013), which measures the total expected utility for an agent starting in state 8, in a two-player game against an adversary defined by the regularizer Ω with strength B. We empirically confirm the indifference condition in Fig. and 8.
4 Experiments
In this section, we visualize the robust set and worst-case reward perturbations associated with policy regularization, using intuitive examples to highlight theoretical properties of our adversarial interpretation.
4.1 Visualizing the Robust Set
In Fig. 2, we visualize the robust set of perturbed rewards for the optimal policy in a two-dimensional action space for the KL. or a-divergence, various 3, and a uniform or non-uniform prior policy xy. Since the optimal policy can be easily calculated the single-step case, we consider fixed (a 8) = r(a, x) = {1.1, and show the robustness of the optimal n. (a(s),, which differs based on the choice of regularization scheme using Eq. (27). We determine the feasible sct of Ar using the constraint in Prop. (see App. D.3 for details), and plot the modified reward T'e. (a, s) (a, s) Ar.. (a, s) for each action.
Inspecting the constraint for the adversary in Eq. (19), note that both reward increases Ar(a, s) < 0 and reward decreases Ar(a, 8) > 0 contribute non-negative terms at each action, which either up- or down-weight
2hhis holds for actions with n. (als) > 0 and X(a,s) O. Note that treat Q(a,s) as the reward in the sequential case.
9

---

Published in Transactions on Machine Learning Research (07/2022)
(1) 3 1.0
3
1.0
Palicy stajd
Policy maast
Peturtet -dayl
Parurbed
Agaat C- usi
Agert. Qla, Vauus
10 Penurbiiio -asjas
10
Policy
Fertrited
Policy Majal
Perturett -fryla
Perturbed
16-
(a) Optimal Policy
(b) Suboptimal Policy
Figure 3: Single-Step Reward Perturbations for KL regularization to uniform reference policy (a(as)) Q-values in left columns are used for each 3 in columns 2-4. We report the worst-case Arxx(a,,) (Eq. (22)). so negative values correspond to reward decreases. (a) Optimal policy (Q, s) = r(a, s)) using the environ- ment reward, where the perturbed r'(a, s) = e Va reflects the indifference condition. (b) Suboptimal policy where indifference does not hold. In all cases, actions with high Q(a, s) are robust to reward decreases.
the reference policy =a(a)s). The constraint on their summation forces the adversary to trade off ween perturbations of different actions in a particular state. Further, since the constraints in Prop. integrate over the action space, the rewards for all actions in a particular state must be perturbed together. While it is clear that increasing the reward in both actions preserves the inequality in Eq. (2), Fig. 2 also includes regions where one reward decreases.
For high regularization strength (G=0.1) we observe that the boundary of the feasible set is nearly lincar, with the slope mo(o)]e) boundary steepens for lower regularization strength. We can use the indifference condition to provide further geometric insight. First, drawing line from the origin with slope 1 will intersect the feasible set at the worst-case modified reward (red star) in each panel, with (a), = (a2, s). At this point, the slope of the tangent line yields the ratio of action probabilities in the regularized policy, as we saw for the 3 = 0.1 case. With decreasing regularization as B + oo, the slope approaches 0 or -00 for a nearly deterministic policy and a rectangular feasible region.
=a(aa[s) based on the ratio of action probabilities in a policy that matches the prior. The
Finally, we show the a-divergence robust set with a E {-1.3} and B 10 in Fig. 2 (d)-(e) and (i)-(), with further visualizations in App. H. Compared to the KI. divergence, we find wider robust set boundary for a -1. For a = 3 and 8 10, the boundary is more strict and we observe much smaller reward perturbations as the optimal policy becomes deterministic [s) = for both reference distributions. However, in contrast to the unregularized deterministic policy, the reward perturbations Arx (a, s) & 0 are nonzero. We provide a worked example in App. G, and note that indifference does not hold in this case, rr, (a1, * r/,, (u2, due to the Lagrange multiplier An (02, 8) > O.
4.2 Visualizing the Worst-Case Reward Perturbations
In this section, we consider KL divergence regularization to a uniform reference policy, which is equivalent to Shannon entropy regularization but more appropriate for analysis, as we discuss in Sec. 5.1.
Single Step Case In Fig. 3, we plot the negative worst-case reward perturbations - (Ar=(a s) and modified reward for single step decision decision-making case. For the optimal policy in Fig. 3(a), the perturbations match the advantage function as in Eq. (26) and the perturbed reward for all actions matches the value function (s(.. While we have shown in Sec. 3.2 that any stochastic policy may be given an adversarial interpretation, we see in Fig. 3(b) that the indifference condition does not hold for suboptimal policies.
The nearly-deterministic policy in Fig. (ia) also provides intuition for the unregularizod case as / co. Although we saw in Sec. 3.3 that. Arx. (a, 8) = 0 Va in the unregularized case, Eq. (11) and (26) suggest. that X(a, s) (s) (a, s) plays similar role to the (negative) reward perturbations in Fig. 3aa( with s(a 0 and X(a, s) > 0 for all other actions.
10

---

Published in Transactions on Machine Learning Research (07/2022)
so a ta
-00
00
(a) Environment (uniform (s(s;
22441
22 22403 23663 86600
r(a, s) = -1 for water,
r(a, s) for goal)
(b) 8 = 0.2 (High Reg.)
(c) 8 =
(d) 8 = 10 (Low Reg.)
Figure 4: Grid-World Reward Perturbations. (a) Sequential task. (b)-(d) Policies trained with Shan- non entropy regularization of different strength. Action probabilities are indicated via relative arrow lengths; the goal-state is gray and without annotations. Colors indicate worst-case ad adversarial reward perturbations s(ass)
(r= s) = 3 log mo(a]e) for each state and action (up, down, left, right) against which the policy is robust. Red (or positive (rz(a,s) implies that the policy is robust to reward decreases (up to the value shown) imposed by the adversary. These decreases are balanced by adversarial reward increases (blue) for other actions in the same state. We confirm the optimality of each policy using path consistency in App. H Fig. 8.
Sequential Setting In Fig. 4(a), we consider grid world where the agent receives +5 for picking up the reward pill, -1 for stepping in water, and zero reward otherwise. We train an agent using tabular Q-learning m(als]
and a discount factor 7 0.99. We visualize the worst-case reward perturbations Arx(a, 8) = J log sola in each state-action pair for policies trained with various regularization strengths in Fig. 4(b)-(d). While it
is well-known that there exists a unique optimal policy for a given regularized MDP, our results additionally display the adversarial strategies and resulting Nash equilibria which can be associated with a regularization scheme specified by 22 no, a, and 3 a given MDP.
Each policy implicitly hedges against an adversary that perturbs the rewards according to the values and colormap shown. For example, inspecting the state to the left of the goal state in panel Fig. 4(b)-(c), we see that the adversary reduces the immediate reward for moving right (in red, Arn, > 0). Simultaneously, the adversary raises the reward for moving up or down towards the water (in blue). This is in line with the constraints on the feasible set, which imply that the adversary must balance reward decreases with reward increases in each state. In App. E.4 Fig. 8, we certify the optimality of each policy using the path consistency conditions, which also confirms that the adversarial perturbations have rendered the agent indifferent across actions in each state.
Although we observe that the agent with high regularization in Fig. 4(b) is robust to strong adversary, the value of the regularized objective is also lower in this case. As expected, lower regularization strength reduces robustness to negative reward perturbations. With low regularization in Fig. 4(d), the behavior of the agent barely deviates from the deterministic policy in the face of the weaker adversary.
5 Discussion
Our analysis in Sec. 3 unifies and extends several previous works analyzing the reward robustness of regular- ized policies (Ortega & Lee, 2014; Eysenbach & Levine, 2021; Husain et al., 2021), as summarized in Table 1. We highlight differences in the analysis of entropy-regulariized policies in Sec. 5.1, and provide additional discussion of the closely-related work of Derman et al. (2021) Sec. 5.2.
5.1 Comparison with Entropy Regularization
As argued in Sec. 3, the worst-case reward perturbations preserve the value of the regularized objective function. Thus, we should expect our robustncss conclusions to depend on the exact form of the regularizer.
When regularizing with the Tsallis or Shannon (a 1) entropy, the worst-case reward perturbations become
Arz 8) = log, (als)) + _ [
1
(29)
a
11

---

Published in Transactions on Machine Learning Research (07/2022)
See App. F.2, we also show that for 0 < I 1, these perturbations cannot decrease the reward, with - -Ar s) 2 0 and (a, s) 2 r(a,s) In the rest of this section, argue that this property leads to several unsatisfying conclusions in previous work (Lee et al., 2019; Eysenbach & Levine, 2021), which are resolved by using the KI and a-divergence for analysis instead of the corresponding entropic quantities." 3
First, this means that a Shannon entropy-regularized policy is only 'robust' to increases the reward function. However, for useful generalization, we might hope that a policy still performs well when the reward function decreases in at least some states. Including the reference distribution via divergence regularization resolves this issue, and we observe in Fig. 2 and Fig. 4 that the adversary chooses reward decreases in x. (als)
some actions and increases in others. For example, for the KL divergence, Ar.. (a, s) = log (o(aas) (a 8) - Vs()) implies robustness to reward decreases when x. (als)) > mn(als) or Q. 8) > V.(8). Similarly, Lee al. (2019) note that for
any a,
T 0 (2)
max (TT, Q) + (.(())) 2 (uamax; 8) TEA Al
where amax = arg max, Q(a, and the Tsallis entropy Ha(r) oquals the Shannon entropy for a 1. This soft value aggregation yields a result that is larger than any particular Q-value. By contrast, for the a- divergence, we show App. F.3 that for fixed 3 and a > 0,
11 logz-a a Ba
T (amaa||s) S go (Q) & ((amax: 8).
Q(amax: 8) +
(30)
This provides more natural interpretation of the Bellman optimality operator V(s) - 3 To.3 (Q) as soft maximum operation. As a function of 3, we see in App. C.4 and F.3 that the conjugate ranges between (
En, EnoIQ(aunn) [Q(mmax s)] S / ( (Q) S Q(Cmaxx
Finally, using entropy instead of divergence regularization also affects interpretations of the feasible set. Eysenbach & Levine (2021) consider the same constraint as in Eq. (19), but without the reference To Ta(als)
Σexp exp (B- Ar(a, 8)} s V.
(31)
aEA
This constraint suggests that the original reward function (Ar 0) is not feasible for the adversary. More surprisingly, Eysenbach & Levine (2021) App. A8 argues that incrensing regularization strength (with lower (3) may lead to less robust policies based on the constraint in Eq. (31). In App. F.4, we discuss how including (o(a)s) ) in the constraint via divergence regularization (Prop. 1) avoids this conclusion. As expected, Fig. 2 shows that increasing regularization strength leads to more robust policies.
5.2 Related Algorithms
Several recent works provide algorithmic insights which build upon convex duality and complement or extend our analysis. Derman et al. (2021) derive practical iterative algorithms based on a general equivalence between robustness and regularization, which can be used to enforce robustness both reward perturbations (through policy regularization) and changes in environment dynamics (through value regularization). For policy regularization, Derman et al. (2021) translate the specification of desired robust set into regularizer using the convex conjugate of the set indicator function. In particular, Derman et al. (2021) associate KL divergence or (scaled) Tsallis entropy policy regularization with the robust set RA = (Ar Ar(a, s) E P 1 loga, sola oo) V (), E A x 8}. Our analysis proceeds in the opposite direction, from regularization to robustness, using the conjugate of the divergence. While the worst-case perturbations result in the same modified objective, our approach yields a larger robust set with qualitatively different shape (sce Fig. 1).
x(ala)
Zahavy et al. (2021) analyze general 'meta-algorithmt which alternates between updates of the occupancy measure p(a, s) and modified reward r'( in online fashion. This approach highlights the fact that the modified reward r or worst-case perturbations Ar, change as the policy or occupancy measure is optimized. The results of Zahavy et al. (2021) and Husain et al. (2021) hold for general convex MDPs, which encompass common exploration and imitation learning objectives beyond the policy regularization setting we consider.
Entropy regularization corresponds to divergence regularization with the uniform reference distribution no(a]s).
12

---

Published in Transactions on Machine Learning Research (07 (2022)
As discussed in Sec. 3.4, path consistency conditions have been used to derive practical learning objectives in (Nachum et al., 2017; Chow et al., 2018). These algorithms might be extended to general a-divergence regularization via Eq. (28), which involves an arbitrary reference policy (o(as) that can be learned adaptively as in (Tch et al., 2017; Grau-Moya et al., 2018).
Finally, previous work has used dual optimizations similar to Eq. (14) to derive alternative Bellman error Josses (Dai et al., 2018; Belousov & Peters, 2019; Nachum & Dai, 2020; Bas-Serrano al., 2021), highlighting how convex duality can be used to bridge between policy regularization and Bellman error aggregation (Belousov & Peters, 2019; Husain et al., 2021).
6 Conclusion
In this work, we analyzed the robustness of convex-regularized RL policies to worst-case perturbations of the reward function, which implics generalization adversarially chosen reward functions from within a particular robust set. We have characterized this robust set of reward functions for KL and a-divergence regularization, provided unified discussion of existing works reward robustness, and clarified apparent differences in robustness arising from entropy versus divergence regularization. Our advantage function interpretation of the worst-case reward perturbations provides complementary perspective on how Q-values appear as dual variables in convex programming forms of regularized MDPs. Compared to a deterministic, unregularized policy, a stochastic, regularized policy places probability mass on a wider set of actions and requires state-action value adjustments via the advantage function or adversarial reward perturbations. Conversely, a regularized agent, acting based on given Q-value estimates, implicitly hedges against the anticipated perturbations of an appropriate adversary.
References
Zafarali Ahmed, Nicolas Le Roux, Mohammad Norouzi, and Dale Schuurmans. Understanding the impact entropy on policy optimization. In International Conference on Machine Learning. PMLR, 2019.
Shun-ichi Amari. Information geometry and its applications, volume 194. Springer, 2016.
Saurabh Arora and Prashant Doshi. A survey of inverse reinforcement learning: Challenges, methods and progress. Artificial Intelligence, 297:103500, 2021.
Arindam Banerjee, Srujana Merugu, Inderjit Dhillon, Joydeep Ghosh, and John Lafferty. Clustering with bregman divergences. Journal of machine learning research, 6(10), 2005.
Joan Bas-Serrano, Sebastian Curi, Andreas Krause, and Gergely Neu. Logistic q-learning. In International Conference on Artificial Intelligence and Statistics, pp. 3610-3618 PMLR, 2021.
Richard Bellman. markovian decision process. Journal of mathematics and mechanics, 6(5):679 684, 1957.
Boris Belousov. Bregman divergence of alpha-divergence. Blog post, 2017. URL http://www.
boris-belousov.
Boris Belousov and Jan Peters. Entropic regularization of markov decision processes. Entropy, 21(7), 2019.
Stephen Boyd and Lieven Vandenberghe. Conver optimization. Cambridge university press, 2004.
Yinlam Chow, Ofir Nachum, and Mohammad Ghavamzadch. Path consistency learning in tsallis entropy regularized idps. In International Conference on Machine Learning, pp. 979 988. PMLR, 2018
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Logg, and Dario Amodei. Deep reinforce- ment learning from human preferences. Advances in neural information processing systems, 30, 2017.
Andrzej Cichocki and Shun-ichi Amari. Families of alpha-beta-and gamma-divergences: Flexible and robust
measures of similarities. Entropy, 12(6):1532-1568 1568, 2010.
Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao Hc, Zhen Liu, Jianshu Chen, and Le Song. Sbeod: Convergent reinforeement learning with nonlinear function approximation. In International Conference on Machine Learning, pp. 1134-113.. PMLR, 2018.
13

---

Published in Transactions on Machine Learning Research (07/2022)
Esther Derman, Matthieu Geist, and Shie Mannor. Twice regularized mdps and the equivalence between robustness and regularization. In Thirly- Fifth Conference on Newral Information Processing Systems, 2021.
Steven Diamond and Stephen Boyd. CVXPY: A Python-embedded modeling language for convex optimiza- tion. Journal of Machine Learning Research, 17(83):1-5, 2016.
Benjamin Eysenbach and Sergey Levine. Maximum entropy RL (provably) solves some robust RL problems. In International Conference Learning Representations, 2021. URL https: https: http::://pperrevee..nntttee id=PtSAD3caaA2.
Eugene A Feinberg and Adam Shwartz. Handbook of Markov decision processes: methods and applications, volume 40. Springer Science & Business Media, 2012.
Peter Fishburn. Nonlinear preference and ulility theory. Number Johns Hopkins University Press, 1988.
Roy Fox, Ari Pakman, and Naftali Tishby. Taming the noise in reinforcement learning via soft updates. In Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence, pp. 202-211, 2016.
Matthicu Gcist, Bruno Scherrer, and Olivier Pictquin. A theory of regularized markov decision processes. In ICML 2019- Thirly-sirth International Conference on Machine Learning, 2019.
Jordi Grau-Moya, Felix Leibfried, and Peter Vrancx. Soft q-learning with mutual-information regularization. In International Conference on Learning Represenlations, 2018.
Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy- based policies. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1352-1361. PMLR, 06-11 Aug 2017.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International Conference on Machine Learning, pp. 1861 1870. PMLR, 2018
Hisham Husain, Kamil Ciosek, and Ryota Tomioka. Regularized policies are reward robust. International Conference Artificial Intelligence and Statistics, 2021.
Maximilian Igl, Andrew Gambardella, Jinke He, Nantas Nardelli, Siddharth, Wendelin Böhmer, and Shimon Whiteson. Multitask soft option learning. In Conference on Uncertainty in Artificial Intelligence, pp. 969 069, 2020.
Hilbert J Kappen, Vicenç Gómez, and Manfred Opper. Optimal control as a graphical model inference problem. Machine learning, 87(2):159 182, 2012.
Kyungjae Lee, Sungjoon Choi, and Songhwai Oh. Sparse markov decision processes with causal sparse tsallis entropy regularization for reinforcement learning. IEEE Robotics and Automation Letters, 3(3):1466 1473, 2018.
Kyungjae Loe, Sungyub Kim, Sungbin Lim, Sungjoon Choi, and Songhwai Oh. Tsallis reinforccment learning: A unified framework for maximum entropy reinforcement learning. ar preprint arxiv:1902, 00137, 2019.
Sergey Levine. Reinforcement lcarning and control as probabilistic inference: Tutorial and review. arXiv preprinl XrX:::1805.00 00909, 2018.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.0160 01643, 2020.
Ofir Nachum and Bo Dai. Reinforcement learning via fenchel-rockafellar duality. arXiv preprint 00X.v:2001.01866, 2020.
Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans. Bridging the gap between value and policy based reinforcement. learning. Xr preprint ar 102.:102.000..00 08892, 2017.
14

---

Published in Transactions on Machine Learning Research (07/2022)
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. Reinforcement Learning for Real Life Workshop (ICML), 2019a.
Ofrr Nachum, Bo Dai, Ilya Kostrikov, Yinlam Chow, Lihong Li, and Dale Schuurmans. Algaedice: Policy gradient from arbitrary experience. orXiv preprint urXi:1912.020774 2019b.
Jan Naudts. Generalised thermoslatisties. Springer Science & Business Media, 2011.
Gergely Neu, Anders Jonsson, and Vicenç Gómez. A unified view of regropy-regularized markov decision processes. Niv preprint 1rXiu:1705.07770 2017.
Andrew Ng, Stuart J Russell, et al. Algorithms for inverse reinforcement learning. In International
Conference on Machine Learning, 2000.
Pedro Ortega and Daniel Lee. An adversarial interpretation of information-theoreic bounded rationality. Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014.
Pedro A Ortega and Daniel A Braun. Thermodynamics theory of decision-making with information- processing costs. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 469(2153), 2013.
Martin Osborne and Ariel Rubinstein. A course in game theory. 1994.
Jan Peters, Katharina Mulling, and Yasemin Altun. Relative entropy policy search. In Proceedings of the AAAT Conference on Artificial Intelligence, volume 24, 2010.
Martin L Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., 1994.
Martin T, Puterman and Moon Chirl Shin. Modified policy iteration algorithms for discounted markov decision problems. Management Science, 24(11), 1978.
Konrad Rawlik, Marc Toussaint, and Sethu Vijayakumar. On stochastic optimal control and reinforcement Icarning by approximate inference. In International Joint Conference on Artificial Intelligence, 2013.
Bruno Scherrer, Mohammad Ghavamzadeh, Victor Gabillon, Boris Lesner, and Matthieu Geist. Approximate modified policy iteration and its application to the game of tetris. Journal of Machine Learning Research, 16(49):1629 1676, 2015.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889 1897. PMLR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimiza- tion algorithms. arXiv e-prints, pp. arXiv-1707, 2017.
Umar Syed, Michael Bowling, and Robert E Schapire. Apprenticeship learning using linear programming. In Proceedings of the 25th international conference on Machine learning, pp. 1032-1039, 2008.
Yee Whye Teh, Victor Bapst, Wojciech Marian Czarnecki, John Quan, James Kirkpatrick, Raia Hadsell, Nicolas Heess, and Razvan Pascanu. Distral: robust multitask reinforcement learning. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 4499-4509, 2017.
Coustantino Tsallis. Introduction to nonextensive slabislical mechanics: approuching compler world.
Springer Science & Business Media, 2009.
Ziyi Wang, Oswin So, Jason Gibson, Bogdan Vlahov, Manan S Gandhi, Guan-Horng Liu, and Evangelos A Theodorou. Variational inference mpc using tsallis divergence. arXie preprint orXiv:2104 0oe:2104400241 1, 2021.
Tom Zahavy, Brendan O'Donoghue, Guillaume Desjardins, and Satinder Singh. Reward is enough for convex mdps. Advances in Neural Information Processing Systems, 2021.
Huaiyu Zhu and Richard Rohwer. Information geometric measurements of generalisation. Technical report, Aston University, 1995.
15

---

Published in Transactions on Machine Learning Research (07 (07/202) 2022)
Appendix
Table of Contents
A Implications of Conjugate Duality Optimality Conditions
A.1 Proof of Prop. 2: Policy Form Worst-Case Reward Perturbations
17
A.2 Optimal Policy in Regularized MDP
17
A.3 Proof of Prop. Policy Form Worst-Case Perturbations match Value Form at Optimality
18
A.4 Path Consistency and KKT Conditions
19
A.5 Modified Rewards and Duality Cap for Suboptimal Policies
19
B Convex Conjugate Derivations
20
B.1 KL Divergence Policy Regularization: 4 ((rr)
20
B.2 KL Divergence Occupancy Regularization: 3 (Ar)
21
B.3 a- a-Divergence Policy Regularization: 1.2% (Ar)
22
B.4 a- Diveergence Occupancy Regularization: 12
................................
24
C Soft Value Aggregation
24
C.1 KL Divergence Soft Value Aggregation: 10%.,(9))
25
C.2 a- Divergence Soft Value Aggregation: 3 (Q)
26
C.3 Relationship between Normalization Constants Parr., MiQ. and Value Function V.(s)
27
C.4 Plotting Value Function Function of Regularization Parameters a, 9
29
D Robust Set of Perturbed Rewards
D.1 Proof of Prop. 1: Robust Set of Perturbed Rewards for Policy Regularization
30
D.2 Robust Set for a- Diveergencce under μ(a, s) Regularization
31
D.3 Plotting the o-Divergence Feasible Set
32
E Value Form Reward Perturbations
32
E.1 Proof of Thm. (Husain al. (2021))
32
E.2 Path Consistency (Comparison with Nachum et al. (2017); Chow et al. (2018))
33
E.3 Indifference Condition
34
E.4 Confirming Optimality using Path Consistency and Indifference
35
Comparing Entropy and Divergence Regularization
35
F.1 Tsallis Entropy and a-Divergence ................................
F.2 Non-Positivity of (r, for Entropy Regularization
36
F.3 Bounding the Conjugate Function
F.4 Feasible Set for Entropy Regularization
Worked Example for Deterministic Regularized Policy (a 2, 3 = 10)
39
Additional Feasible Set Plots
40
16

---

Published in Transactions on Machine Learning Research (07/2022)
A Implications of Conjugate Duality Optimality Conditions
In this section, we show several closely-related results which are derived from the conjugate optimality conditions. We provide additional commentary in later Appendix sections which more closely follow the sequence of the main lext.
First, recall from Section 2.1 the definition of the conjugate optimizations for functions over X Ax x S. We restrict μ R to be nonnegative function over X, that
1 (Ar): sup (u, 1 sa(w). B
2(M)= = sup
(n, 3 ((())))
(32)
g
MER
B
ArERAXS
and the implied optimality conditions are
Ar = 3 v.((()) = (VAr St (n)
1 (A.T -V (Ar).
(33)
p= B
A.1 Proof of Prop. 2 Policy Form Worst-Cast Reward Perturbations
Proposition 2. For given policy =[als) or state-action occupancc pla, 8), the worst-case adversarial reward perturbations Art or Ary associated with conver function (2(p) and regularization strength 1/8 are
Ar. v V
(20)
Proof. The reward perturbations are defined via conjugate optimization for M(() in Eq. (32), where Ar e RAXS The proposition follows directly from the optimality condition in Eq. (33), and we focus on the Ar = = 1,((()) condition for convenience.
In App. B, we derive the explicit forms for the worst-case reward perturbations for KL and a-divergence regularization from Sec. 3.2 of the main text. See App. B Table for references to particular derivations.
Note that we do not consider further constraints l in the conjugate optimization. Instead, we view the Bellman flow constraints s(a,s) E M (and normalization constraint p(a, s) E A as arising from the overall (regularized) MDP optimization in Eq. (10) or (12), as we discuss in the next subsection.
A.2 Optimal Policy in a Regularized MDP
In Lemma 1 below, we show that the Bellman flow constraints Eq. (10), which are enforced by the optimal Lagrange multipliers (s),, ensure that the optimal (a, s) is normalized. This suggests that an explicit normalization constraint is not required. In Prop. 4, we then proceed to derive the optimal policy a regularized MDP using the conjugate optimality conditions in Eq. (33).
Lemma 1 (Flow Constraints Ensure Normalizzaion), Assume that the initial state distribution vo(s) and (aslla,)) s) = If state-occupancy measure satisfies the Bellman flow constraints p(a.s) E M,, then it is normalized distribution ula. e AlA|x S
transition dynamics P(s'aa, 8) normalized, with E, vo(s) and Es P(s'
Proof. Starting from the Bellman flow constraints Ea u(a, s) s)= = (1--))o(s))++ + 2 s')dd' s'), we consider taking the summation over states E S
Eula, x)= = (1-7) Σ vo(s) + ΣΣ P(sla', (a(d' '') 12 (1-7) 7) + Σ M(sla',s) s') Σ m(ddss) 2 (1-))++ + Σ mldd's)
where (1) uses the normalization assumption on vo(s) and the distributive law, and (2) uses the normalization assumption P(s)a',s)) s'). Finally, we rearrange the first and last equality to obtain
(1 - 7) Σ ula,s) s) = (1-7)
Eu(a,s) =
(34)
8.s
4,8
17

---

Published in Transactions on Machine Learning Research (07/2022)
which shows that pla, s) is normalized joint distribution over A, S, desired.
Proposition (Optimal Policy in Regularized MDP). Given the optimal value function V. Vs(s) and Lagrange multipliers Xa (a, s), the optimal policy in the regularized MDP is given by
1 Vs* (r+ P.. 8
-V v.)
-V.
(v)
(r+ [.] V. -V
This matches the conjugate conditions in Eq. (33) using the arguments Ar(a, 8) + r(a, 8) + E [v.'') (s(s) + (a,a,)).
Proof. In Soc. 2.4, we moved from the regularized primal optimization (Eq. (12)) to the dual optimization (Eq. (14)) via the regularized Lagrangian
1 min (1 - (vo. V) + (u, ju, BB [v] - + -00000000 V.
Note that the Lagrange multipliers X(a,s) enforce p(a, 2 0 while V(s) enforces the flow constraints and thus, by Lemma 1, normalization of (u(ass) s). We recognized the final two terms conjugate optimization
1 3 1 (r ( [v] V max (p, r + -V 1 3 ((o(())
(35)
to yield dual optimization over V(s) and Ma, s) only in Eq. (14). After solving the dual optimization for the optimal (s), (a, 8), we can recover the optimal policy in the MDP using the optimizing argument of Eq. (35). Differentiating Eq. (35) and solving for μ yields Vzz0(u) = = + [V] -V + À which we invert 7
to obtain Prop. 4. The other equality follows from the conjugate optimality conditions in Eq. (33).
For a-divergence regularization, the optimal policy or slate-action occupancy is given by the 'optimizing argument' column Table 2, up to reparameterization of Ar(a, < r(a, +) [V.(>]] - Vv((s) + (a, 8)
as the dual variable. In this case, note that the argument to the conjugate function accounts for the flow and nonnegativity constraints via (s) and (a, s). In particular, we have
Policy Reg., App. B.3 Eq. (63)
(=(a,s) (us) (als) exp, {3. (r(a,s) ()( +2 vv.()))))))))))))))))))))))))))) + +(a - (.r.. (s: [8
(36)
Occupancy Reg., App. B.4 Eq. (68)
p+(a,s) po mo 8) expa .3. (r(a,s) + [v]])[ -v vv(s) ((ass)
(37)
where darre (s; (1 (1- E. (a)s)) appears from differentiating 2T (u) as in Eq. (23)
App. B.3. This means that the optimal policy is only available in self-consistent fashion, with the normalization constant. inside the exPa: which can complicate practical applications (Tee et al., 2019; Chow
et al., 2018).
A.3 Proof of Prop. 3: Policy Form Worst- Case Perturbations match Value Form at Optimality
The substitution Ar(a,s) +- r(a, s) + Ey [v')] V.(s) (a, above already anticipates the result in Prop. 3, which links the reward perturbations for the optimal policy Arx. or state-action occupancy Arp. to the advantage function. See the proof of Thm. 1 in App. F.1 for additional context. in relation to the value-form form reward perturbations Ary s).
Proposition 3. For the optimal policy n. (als) and value function Vz(8) corresponding to a-divergence policy regularization with strength B, the policy and value forms of the worst-case adversarial reward perturbations match, Arr. = Arv, and are related to the advantage function via
Arn. (a, 8)
(a)ss) (c.as)) Vs(s) + (a,as)),
(26)
where we define Q. s) = r(a, s) B5 [v.(s')] and recall >eo (a, s) S) (als) by complementary slackness. Note that Vs(s) depends the regularization scheme via the conjugate function 1 (Ar)) in Fq.. (25).
18

---

Published in Transactions on Machine Learning Research (07/2022)
Proof. The result follows by combining Prop. 2, which states that Ar, Vp)((1), and Prop. 4, which implies VuzD(u))
r(a,s) + + [V. V.(s) + Xa as condition for optimality of (u, s), (s(,,, (a, s)}. Thus, for the optimal policy Ty (als) and Lagrange multipliers Ax we have Arn, (a, 8) r(a, s) + >E [V.'') (s) + (a, s) and similarly for Arp. (a. s).
We can confirm this using the expression for the optimal policy in Eq. (36) and the worst-case reward perturbations in Sec. 3.2. For example, recalling (a,a, s) = (())) we can write the a-divergence policy regularization case Ar., (a, I loga motals) X(a, s) + (s,7).
(a(ass) + WAr.. (s: = r(a, s) + (Bi..(..(s)) - V.(s) +
A.4 Path Consistency and KKT Conditions
Finally, note that the KKT optimality conditions (Boyd & Vandenberghe, 2004) include the condition that we have used in the proof of Prop. 3. At optimality, we have
r(a, 8) + 7 0, [v((')] - (s(s) + (a,ss)) V - > = 0.
2(n²)
(38)
This KKT condition is used to derive path consistency objectives in Nachum et al. (2017); Chow al. (2018).
For general a-divergence policy regularization, we substitute Vi (u.) = Ar. (a, = log, x_(ola)
mo(als) +
arr.. () using Eq. (22) (see App. B.3 for detailed derivations). This leads to the condition
(als)) var., (8: = 0, 8(a,8) + B [V.(''] (s()) + 8.( loga (a(a)s)
1
(39)
which matches Eq. (28). We compare our a-divergence path consistency conditions to previous work in App. E.2.
A.5 Modified Rewards and Duality Gap for Suboptimal Policies
We can also use the conjugate duality of state-action occupancy mcasures and reward functions (r(a, s) or r' *(a,))) 8)) to express the optimality gap for suboptimal p(a, 8). Consider the regularized primal objective (constrained) conjugate optimization,
1 ((p)
RL 3=:0=000000 (r)) WEM
max (R,T)
(40)
B
2 (up, r)
2(4))
(41)
B
where the inequality follows from the fact that any feasible po E M provides lower bound on the objective. We use the notation p to anticipate the fact that, assuming appropriate domain considerations, we would like to associate this occupancy measure with a modified reward function using the conjugate optimality conditions in Eq. (33) (with r' as the dual variable). In particular, for a given 2 we use the fact that pr- = V22 (r') to recognize the conjugate duality gap as a Bregman divergence. Rearranging Eq. (41),
1 (r)
- (pr,r)
Mpr) 20
(42)
3
1 1 (r) - -(prr) + (1rr,"")
(r)))) 20 8
(43)
1
((())- 8 (r)(()) - ((r-r', 1
(r)) 20
(44)
A2
Dr. Da
(45)
where the last line follows from the definition of the Bregman divergence (Amari, 2016). For example, using the KL divergence 1(H)) DKI(p pul, one can confirm that the Bregman divergence generated by Ω is also a KI. divergence, D pr-] (Belousov, 2017; Banerjee et al., 2005).
19

---

Published in Transactions on Machine Learning Research (07/2022)
B Convex Conjugate Derivations
In this section, derive the convex conjugate associated with KL and a-divergence regularization of the policy (als) or state-action occupancy p(a,s), s). We summarize these results in Table 2, with equation references in Table 3. In both cases, we treat the regularizer }((u) as function of u(a, 8) and optimize over all states jointly,
1 (()))
01()== = sup (u,)) MERAES
(46)
These conjugate derivations can be used to reason about the optimal policy via 10 (r argued in App. A.2, the worst reward perturbations using / (22 We use Ar the argument or dual variable throughout this section.
[v] V
In App. C, we derive alternative conjugate functions which optimize over the policy in each state, where x (als) E AlAl is constrained to be normalized probability distribution. This conjugate ariscs in considoring soft value aggregation or regularized iterative algorithms as in Sec. 2.4. See Table for equation references.
Divergence Ω
(Ar)
Ar)(a,s)
s)
DKL(T:: mul
Eq. (47)
Eq. (50)
Eq. (51)
3 DKI[U: [o]
Eq. (55)
Eq. (53)
Eq. (54)
Divergence
Qa(a, (()
aq s)
3 DD [TO m
Eq. (56)
Eq. (62)
Eq. (63)
1 DKLIT mul
Eq. (78)
Eq. (75)
Eq. (76)
Da [M0 p4
Eq. (66)
Eq. (67)
Eq. (68)
Da(mo:
Eq. (82)
Eq. (81)
Eq. (80)
Table 3: Equations for Ar or 'MDP Optimality' Conjugate Table 4: Equations for 'Soft Value' V.(s) Conjugates
(p Optimization, No Normalization Constraint)
(ær Optimization, Normalization Constraint)
B.1 KL Divergence Policy Regularization:
The conjugate function for KI. divergence from the policy v(als) to reference (a(as) has the following closed form
1
Σ u(s) Σ (aalss exp (B Ar(a, -1)
ºr ((r. 3
(47)
Proof. We start from the optimization in Eq. (3) or (32), using conditional KL divergence regularization
Qxo (1) = (D ma]] as in Eq. (6).
1
1 ( (Ar) = max (M. Ar) Enla, ula, log u(a,s) 1 Eu(a,s) Σ ((s)To((as)
(48)
3
((s)Tolals) a.s
a.
1 Σ u(a, log p(a.s) + p(aas)) 1 Σ ((s)Fo((aas) ((s)TT(als)
Ar V
(49)
Worst-Case Reward Perturbations (r=(a We can recognize Eq. (49) as an instance of Prop. 2. Noting that the marginal pls) depends on p(a,s), s), make use of the identity Σ. a )pla.)u(ss))
Es' apla.o (((a',s)) Ev.r ò(a', s' a.s) as in (Neu et al,, 2017: Lee al., 2019). Differentiat-
20

---

Published in Transactions on Machine Learning Research (07 2022)
ing, we obtain
pla, s) Ar(a, log ((s)Ta(aas)
Bula. 8)
u(a,s)
0 uua" .8
8 3
Ege ulaa ,s)
mu(als)
B
Oplaa' 5')
l(s)
Opla''
Ōulal, ,')
6(e=8))
6(s=o))
log
pla, 8) 14 (als)
u(a,s)
Σ 3
1
Ta(ass)
((3)
= log pla,s) s)
(50)
(()))
Σ pla,s)
In the last line, we assume (a)ss) = and note that En
pla.s)
p(a)
1.
p(s)
M(s)
p(s)
Optimizing Argument (ar(als) We derive the conjugate function by solving for the optimizing argument
p)a,s) in terms of Ar(a, s) and substituting back into Eq. (48). Defining Tar(als) = (ar(a.s) as the policy
induced by the optimizing argument (ar(a, s) in Eq. (50), we can solve for war to obtain (a)(a)
(al())s) mo(ass) exp {B- Ar(a,
(51)
(Ar) We plug this back into the conjugate optimization Eq. (48), with (a)(a, = u(s)Tar(a, s). Assuming To (als) is normalized, we also have Ee,s ((s)mo(als) = and
Conjugate Function /
B D ((rr) = Σ ((s)mar(als) (rlaa((()))a-a... 5 Σ ((o)mar(ole) 1o 16 e)} - ((s)mo(ols) (par(a. + u(s)xo(a(s))
1 Σ m(s) Σ so(als) exp {s. Ar(a, -1 B
(52)
as desired. Note that the form of the conjugate function also depends on the regularization strengthh B.
Finally, verify that our other conjugate optimality condition Ar, (VAr (Mar), or MAr Var A 2 f (Arz) holds for this conjugate function. Indeed, differentiating with respect to Ar(a, 8) above, we see that pār(a.)) 2 1 (Ar) = (os)to(a(s) exp Ar(a, s)} matches par(a, s) p(s) via Eq. (51).
Although regularization Sgoo (1)) pp)) [ =o]] applies at each to(als), we saw that performing the conjugate optimization over pla, s) led to expression for a policy (ar(als) (ar(a,))/u(s that is normalized by construction Σ. TAr (a|s) = Σ. man(a.s) 1. Conversely, for a given normalized T[als), the u(*)
above conjugate conditions yield Ar (a, 8) such that Eq. (51) is also normalized.
B.2 KL Divergence Occupancy Regularization: (Arr)
Nearly identical derivations as App. B.1 apply when regularizing the divergence Sua (H) DRL.e Hol between the joint state-action occupancy p(a,s) and reference uo(a, s). This leads the following results
Arp(a, 1
log m(a,s) 8)
Worst-Case Perturbations:
(53)
3
mu(a, s)
Optimizing Argument:
(ar(a, no(a, 8) exp {8 Ar(a,s))-
(54)
1 Σ Hola, 8) exp (3 Ar(a, s)} Σ mo(a,s)
Conjugate Function:
- Ω*
(Ar)
(55)
3
Such regularization schemes appear in REPS (Peters et al., 2010), while Bas-Serrano et al. (2021) consider both policy and occupancy regularization.
21

---

Published in Transactions on Machine Learning Research (07 (222))
B.3 o-Divergence Policy Regularization: 10 (Ar)
The conjugate for a-divergence regularittinnn of the policy (alss) to a reference To(als) takes the form
(Ar = 11 3 a
Σ m(3)
mo(alo) 1 + B(a (1)((a())))) - (
-1 Σ p(s) (s)();)) (56)
where (s; B) is a normalization constant for the optimizing argument (ar(a]s) corresponding to Ar(a, s).
We provide explicit derivations of the conjugate function instead of leveraging f-divergence duality (Belousov & Peters, 2019; Nachum & Dai, 2020) in order to account for the effect of optimization over the joint distribution u(a,s) s). We will see in App. C.2 see that the conjugate in Eq. (56) takes a similar to form as the conjugate with restriction to normalized r[lls) E A where this constraint is not captured using f-divergence function space duality.
Proof. We begin by writing the a-divergence 2. (1) = Buc (ro x]] as function of the occupancy measure n, with ([lss)- = Mage As in Prop. 2, the conjugate optimization implics an optimality condition for sr.
(r(()) (Ar) max Ar) aall-a) (1 a) Σ 8
1
((s)mo(als)) I Euaa, s)
Σ R..
((s))ooaass) (m aa (57)
)
a
a,a
a,a
= V a(1 - a)
1
(1 (1-a) Σ ((s)ro(als) + a Σ p(a, 8) -
Σ
u(s)ma(ale)t-a (Mla.s) (u(s)
(58)
Worst-Case Reward Perturbations (als) We now differentiate with respect to ula, 8), using similar derivations as in Lee et al. (2019). While we have already written Eq. (58) using pla, s) (()) s), we again emphasize that u(s) depends on s)a,s) Differentiating, we obtain
sr(a, VH n (w)
(59)
Σ
su(a, (1- )oool))) + app(a'
8 a(l - a) d'.a'
1 (1 (1-a) a)
2 Evd o(a
Σ nold'ls) 1 Σ dp(a',s')
Ball a)
Öpla,,) 8)
ap(a,
5(6=o!)
6l0', o'=.e)
E
,u(a',8')
Σ m(s')
Evs uld'ss)) 0u(a,
aa)
s)
d',s'
a'.e'
6ia',a'== =a,z)
b(e=x()
8 all a) (a (1-a)) Σ mu(als) t
( m(a,s) a-1
(1 ②) Σ no(als)2-a (u(a, 8) a m(s)
11
x(ass)
(a(ss))
aa 31-a 31-a mo(a|s)
Ba
m(aas) mo(a|s)
11
1 Σ
= *x(a)s)a
(60)
8 1
3a
where we have rewritten (1) in terms of the policy (als))
mla.s) m(a) and assumed To(als) is normalized.
Letting (ass) indicate the policy which is in dual correspondence with Ar(a, s), we would eventually like to invert the equality in Eq. (60) to solve for x[ass) in each (a, However, the final term depends on a sum over all actions. To handle this, we define
Var B)
11 3a
Σ To(als) -
Σ
(61)
22

---

Published in Transactions on Machine Learning Research (07 (07/2022)
Since (als) (a=(a.s) is normalized by construction, the constant (sr () with respect to actions has p(s)
appeared naturally when optimizing with respect to μu s). In App. C.2-C.3, we will relate this quantity to the Lagrange multiplier used to enforce normalization when optimizing over x(als) AlA!
Finally, Eq. (60) to write (rz(a, 8) as
1 (als)
Arx(a, 8) = 3 mo(als) + (s:
loga
(62)
Optimizing Argument (als) Solving for the policy in Eq. (62) and denoting this as (ar(s)s),
Tar(a]s) = no(als) expa {B- (Ar(a, +s; mo(as) [1 + 3(a 1) (Ar(a, 8) (s 3)) (3)]
(63)
Note that (al(s is defined in self-consistent fashion due to the dependence of ( (3) on (al(s) in Eq. (61). Further, (sr(s; B) does not appear as a divisive normalization constant for general a, which is inconvenient for practical applications (Lee et al., 2019; Chow et al., 2018).
Conjugate Function 1 3o. (Ar) Finally, we plug this into the conjugate optimization Eq. (57). Although we eventually need to obtain function of Ar(a, s) only, we write (ar(a)s) in initial steps to simplify notation.
20 (Ar) = Σ (al))) Ar(a,s)
1
(1 (1-a) Σ u(s)molala) +
Σ ((s))ar(al)) - Σ ((l))
[ar(a]s)
B
B all a)
To(a|s]
Σ (al))) Ar(a,s)
11
Σ
((s)molals)
31-a Σ (())aa((aas)
(64)
Ba
0,
(()))ar(a(s) I (+ (Ar(a,s) -aalo:
8 a(1 - a)
Σ (cls) Ar(a,s) B Σ m(s))o(a)s)
Σ ((s)sa 1 (an(199)
8 a a(1 ac)
B (ar(s: Par(s:)) (())) + 33-11 Σ ((s)=ar(als) (a(a)) a
11 Σ H(s) s)
B a
a
a
Ba
where in (1) we note that a(1-a) ((a -1 1) 1)= In (2), we add and subtract the term in blue, which will allow to factorize an additional term of [1 + 3(3a Ar csr 8)) and obtain a function of Ar(a, s) only
(o (Ar)
11 Σ ((a)man(alo) 1 $(a (1 - a- + 1 (ar((;)) - 3a
11 Σ (())t((a)s))
3a
1 1
Σ p(s) - -a - 1) Σ m(s) (a.()
(65)
B
1 where in (1) we have used Fq. (63) and - + 1 along with E. To(ass) =
Conftrming Conjugate Optimality Conditions
Finally, we confirm that differentiating Eq. (65) with
respect to Ar(a,s) s) yields the conjugate condition TA. = V V (Ar). Noting that 1
v Vio (Ar) (Ar) da I Em(r) E na(als) [1 3(a 111-111400 1)(Arr(,)) atr
(aanta
BeA sart
Σ m(*)
AWa-temn Jarte
which simplifies to (ar(a)s) = var(a.e) 3 (0 (Ar) = To(als) B(a 1l0)))++ ()) and matches Eq. (63).
8
23

---

Published in Transactions on Machine Learning Research (07 (222))
B.4 (e-Divergence Occupancy Regularization: 1 (Ar)
The conjugate function # 2 #0.3 (Ar) for a-divergence regularization of the stale-action occupancy pla, 8) to reference po(a, s) can be written in the following form
1 vo(a, 01 3(a 1)Ar(a, })] प (Ar) B c a.
1 1
3 No.d (Ar)
(66)
3
Note that this conjugate function can also be derived directly from the duality of general f-divergences, and matches the form of conjugate considered in (Belousov & Peters, 2019; Nachum & Dai, 2020).
Proof. Worst-Case Reward Perturbations Arp(als)
Ar(a,
1 1
Vx (a-a) Σ mo(a, 9) + +aEm(a,,) -)(a,s)-E mo(a,s))
")o(aas)""_p( p(aa 8)*²
(67)
3 a1 - a)
0,6
a,e
1 1
1
31-a mo(a,
31-a a
Optimizing Argument (a. Solving for par(a,
(ar(a, = po(a, s) exp, (3. Ar(a, $)} = po s) + 3(1 - aa)aaa) $)
(68)
Conjugate Function 10pbo Plugging this back into the conjugate optimization, we finally obtain
1 (xtaa) B pard
= Σ
s))
1
(1-a) Σ s) + Σ Harla, 8) - Σ Har(a,s)
[ar(a, 8)
B Ba(1 Ba(1-a) -a)
Ho(a, 3)
u.a
a,a
0,a
0,a
(10la-1)Ar(aa)(BB) (G8))
- -(1- 1 d) Σ (ar(a,s) ())(aa)))))
11
Σ
Hola,s) s)+
1 -1 Σ (ar(a,s) 8 aa) -
(69)
8a
811
0,5
0,8
a,*
Σ s)( [1 + A(a 1)
Ar(a,)) _T.
11
Σ no(a:s) [1+B(a - 1)ar(a,s)
ao(a, a)
3a
3a
0.5
Σ (ala, + 3(a 1)
11
(1+ 3(a 11 1)Ar(a,s))
11 Σ uo(a,s)
(70)
3a
Ba
11 Σ
[o(a,s) + 8(a 1)ar(a, 8)
a=1
po 8)
(71)
3
3a
0,5
where, to obtain the exponent in the last line, note that
1 +
1 = a-1
a-1
C Soft Value Aggregation
Soft value aggregation (Fox al., 2016; Haarnoja et al., 2017) and the regularized Bellman optimality operator (Neu et al., 2017; Geist et al., 2019) also rely the convex conjugate function, but with slightly different setting than our derivations for the optimal regularized policy or reward perturbations in App. B. In particular, in each state we optimize over the policy (aas)) E A (Al using an explicit normalization constraint (Eq. (74)).
We derive the regularizod Bellman optimality operator from the primal objective in Eq. (12). Factorizing p(a,s) = (al)s can imagine optimizing over pls) and T(ass) E Aldi separately,
=M ((( V(8) max max min (1 - (0=))(ooss) + (p(a,s), r(a, 8) TR [V - V(s)) - 3 (1).
(72)
24

---

Published in Transactions on Machine Learning Research (07 (07/2022)
Eliminating (us) (by setting d/du(s) 0) leads to constraint on the form of V(s), since both may be viewed as enforcing the Bellman flow constraints.
V(s) = (a(ls),
r(s, + BB [V(')]) - 3 (T)).
(73)
3
We define Q(s,a)== = r(s, a) + [V
[V(')] and write V(s) = (TT, Q) - 20 moving forward.
As an operator for iteratively updating V(s), Eq. (73) corresponds to the regularized Bellman operator Tr and may be used to perform policy evaluation for a given ([als) (Geist et al., 2019). The regularized Bellman optimality operator Tá_ which can be used for value iteration or modified policy iteration (Geist
et al., 2019), arises from including the maximization over <alss) E A from Eq. (72)
1 s (
1 ()
V(s)
max TEA AI
(74)
Comparison of Conjugate Optimizations Eq. (74) has the form of a conjugate optimization 1 * (Q) (Geist et al., 2019). However, in contrast to the setting of App. A.2 and App. B, optimize over the policy in cach state, rather than the state-action occupancy p(a,s). Further, we must include normalization and nonnegativity constraints T(ass) E A which can be enforced using Lagrange mult ipliers (h; 3) and ((ass) s). We derive expressions for this conjugate function for the KI. divergence in App. C.1 and a-divergence in App. C.2, and plot the value (s) as a function of and B in App. C.4.
Compared with the optimization for the optimal policy in Eq. (35), note that the argument of the conjugate function does not include the value function V(s) in this case. We will highlight relationship between the normalization constants the (s; B), Darn. (); and Vs(s) in App. C.3, where too (s; V.(s) (s; B) as in Lee et al. (2019) App. D.
C.1 KL Divergence Soft Value Aggregation: (
We proceed to derive closed form for the conjugate function of the KL divergence 2n (τ) function of (als) AHA,, which we write using the Q-values input
F (Q) max (5, Q2) m(als)
Σ s(als) log s(als) sola a)
Σ <a|ss) Σ (o(als)
Σ x(als)) -1 +
A(a,
1 a(a|s) Q(a.)) 8) = log xo(a 8)
+ 0) - N(a,
(75)
Optimizing Argument Solving for क yields the optimizing argument
(a|s))) mo(as)) exp {s (Q(a, s) the (s;
(76)
where we can ignore the Lagrange multiplier for the nonnegativity constraint X(a, s) since exp } 2 0 ensures (a(s))) 0. We can pull the normalization constant out of the exponent to solve for
( B) log Σ mo(als) exp {B Q(a,
(77)
Plugging Eq. (76) into the conjugate optimization,
0. (Q) = (nq. - Σ (ala))) log Tolajot p0(ale) 2o00 8. (Q(a, e) -vo(e:))) Σ mo(a))) -1)
Σ
mo(aas) -1
25

---

Published in Transactions on Machine Learning Research (07 (07/2022)
Conjugate Function
We finally recover the familiar log-mean-exp form for the KL-regularized value
function
V(s) 1
8 ( = vs(::
log Σ To(als) exp {3 Q(a, s)).
(78)
B
Notice that the conjugate value function V(s) 1 m is exactly equal to the normalization constant of the policy (h)(s; (). We will show in App. C.2 that this property does not hold for general a-divergences, with example visualizations in App. C.3 Fig. 5.
C.2 C-Divergence Soft Value Aggregation: =Q)
We now consider soft value aggregation using the a-divergence, where in contrast to App. B.3, we perform the conjugate optimization over r(ass) A in each state, with Lagrange multipliers th B) and X(a, s) to enforce normalization and nonnegativity.
B Pt (Q) = max (T, m(ala)
11
Σ nu(als)
81 x(als)+ +
E
3 a(1 - E To(als)"~>>((0 "aalss
(79)
8
(s; 33
Σ s(als) -1) + Σ s(a,s)
saas) ((a log,, no(a|s)
+ (= M(. 8)
(80)
Optimizing Argument Solving for a yields the optimizing argument for the soft value aggregation con- jugate,
(als) = mo(als) exp.. (s- (Q(a, s) + M(a, s) v)(s;
(81)
Unlike the case of the standard exponential, we cannot easily derive closed-form solution for (h B).
Note that the expressions in Eq. (80) and Eq. (81) are similar to the form of the worst-case reward perturba- tions (aa(a)s) in Eq. (62) and optimizing policy (al(s in Eq. (63), except for the fact that tho(s; (8) arises Lagrange multiplier and does not have the same form (s; 3) = {1 - Da m] as in Eq. (23) and Eq. (61). We will find that (); and (s; () differ by a term of (s) in App. C.3 (Eq. (86)).
Conjugate Function Plugging Eq. (81) into the conjugate optimization, we use similar derivations as in Eq. (64)-Eq. (65) to write the conjugate function, or regularized Bellman optimality operator as
1 (ss) + - 0%
11 3a
11 + (s
(Q)
Ta(als) 1 +(a ((ao) (((
3 To.
Ba
(82)
+ To (als)) expa {8. (Q(a, + M(a - -+)(s;3))
11 + (3;
B
Comparison with KL Divergence Regularization Note that for general a, the conjugate or value function (ss) 1 ( in Eq. (82) is not equal to the normalization constant of the policy (); We discuss this further in the next section.
We also note that the form of the conjugate function is similar using two different approaches: optimizing over π with an explicit normalization constraint, as in Eq. (82), or optimizing over μ with regularization of и but no explicit normalization constraint, as in App. B.3 or Table 2. This contrast the KL divergence, where the normalization constraint led a log-mean-exp conjugate in Eq. (75) which is different from App. B Eq. (47).
26

---

Published in Transactions on Machine Learning Research (07/2022)
C.3 Relationship between Normalization Constants VAr., sq.. and Value Function Vs(s)
In this section, we analyze the relationship between the conjugate optimizations that we have considered above, either optimizing over p(a, s) as in deriving the optimal policy, optimizing over T(als) E A as in the regularized Bellman optimality operator or soft-value aggregation. Using Q(a, r(a,,) [V(')]
Optinal Policy (or WorsttCase Reward Perturbalions) (App. B.3) (15T + [ -V V
(83)
1 (1a(a) yT [V] -V-- V+1)=
1 1 (1)
B mp.3
p(a,))EF
max
Soft Value Aggregation (App. C.2),
(84)
1 (x(() ]
r ( (v])
1 2 ( tur [v])
V(s)
max HEA
B
Note that the arguments differ by term of V(s). We ignore the apparent difference in the M(a 8) term, which can be considered as an argument of the conjugate in Eq. (84) since linear term of (μ, X) appears when enforcing x E AIAI, Evaluating the optimizing arguments,
Optimal Policy (or Worst-Case Reward Perturbations) (App. B.3, Eq. (63), Table 2)
T(als) to(ass) expa {B. (Q(a, 8) Ma, V(s) (x) }
(85)
Soft Value Aggregation (App. C.2, Eqg (82)):
<(als)= (alss expa B (Q(a, 8) Ma,s) (s)
For the optimal (s) and = r(a, 8) + y [V=))_ Vs(,, the two policies match. This can be confirmed using similar reasoning as in Lee et al. (2019) App. D-E or (Geist et al., 2019) to show that iterating the regularized Bellman optimality operator leads to the optimal policy and value.
Relationship between (s) and do. (s This implies the condition which is the main result of this section.
vQ. (s: (s(s) + varr. (s:
(86)
In Fig. 5 we empirically confirm this identity and inspect how each quantity varies with 3 and a (App. C.4)
Eq. (86) highlights distinct roles for the value function V²(s) and the Lagrange multiplier too (s; B) enforcing normalization of rals)) in soft-value aggregation ( Eq.. (79) Eq. (84)). Tt is well known that these coincide in the case of KL divergence regularization, with (s)s v.. (s; as in App. C.1. We can also confirm that AAr... () Jo (E, (a(uss) E. ro(u|s)'=9 "ma))""""(aappp)pp (als)))) 0 vanishes for KL regularization (a 1)
and normalized xo and the normalized optimal policy ...
However, in the case of a-divergenco regularization, optimization over the joint pla, s) in Eq. (83) introduces the additional term vrrr.. (s: B), which not. equal to in general.
Relationship between Conjugate Functions We might also like to compare the value of the conjugate functions in Eq. (83) and Eq. (84), in particular to understand how including (x()) as an argument and optimizing over æ versus μ affect the optima. We write the expressions for the conjugate function in each
4Note that Parn. (s: = 1 (E, To(als) E. to y (App. R.3 Eq. (61)). We also write this as war.. (8: }1(11111 (z) Da) [Tr n.] for normalized mo and R..
appears from differentiating } 4ol (n) with respect
27

---

Published in Transactions on Machine Learning Research (07 (0222)
8 = 0.5
1.0
2
B
V- by
Value F'n (x
Value Fn V-(s) by
Vallue F' V-1s)
1.0
30 125
30 12-
16-
1.0
1
0
2
2
2
2
Normelization
Normalization Wols, by
Normalization
Normalization wyls:
1.5
KJ5 61:
16
2
(1 atDaammm
by
(1 am m-
24
3a 00.
H e00
301
40 c0.
0.00
-1.5
1
22
V.ls) 11 a1o
3//0 V6(60 31 610
V.la) BID mm
9d 10 -I. mm:mmm
1.0
0.81
0301
DM
Dm
0/03
0.81
(a) 0.5
(b) B =
(c) =
(d) B
Figure 5: Value Function Vs(8) -0 (Q+) (first row) and Normalization Constant th (s: B) (second row) as function of for various regularization strengths B. We the same rewards Fig. 7 and uniform reference. We plot ( B) }(1 a1
Fig. 3 and R.] in the third row, and confirm the identity Vs(s) vQ. (s; B) (s from Eq. (86) and (90) in the last row. We find that this equality holds for all up to small optimization errors on the order of 10-3
s(a.s)
sfa.
==11 KL[n:||m]
Vis)=
V(s)
KLInf m;1
Ola.s) Values
KL [L[nl/n
2
Prior Rylags
(r(a.s))
0.001
100
0.001 0.01
0.1
10
100
1/88
3/8
(a) Uniform (a(a)
(b) To (a (s) x r(a, s)
Figure 7: Value function (ss) = 2 (Q) as a function of 3 (x-axis) and a (colored lines), using Q(a, and To (als) from the left inset. See Eq. (78) and Eq. (82) for closed forms.
no.
28

---

Published in Transactions on Machine Learning Research (07 (07/2022)
case, highlighting the terms from Eq. (86) in blue. Optimal Policy (or Worst-Case Reward Perturbations) (App. B.3, Eq. (56), Table 2)
1
(r (
[v.] v.+
(87)
11
Tolals)exp. {s- (Q.((aa,)) (a V.(s) (s)[))))) ())
11
+ -ar.. (8)
3 3
3 3a
Soft Value Aggregation (App. C.2, Eq. (82)),
(s) - [ 2
(r ( [v.]]
(88)
3
11 Σ 3
Tolals)exp, {o (Q+(a, + -
Ba + (4(3;)
Note that have rewritten Vs(s) + 3 - f + yRg V.l) directly as V.(s). To further simplify, note that the optimal policy matches as in Eq. (85), with
(als)) To (als) expa 1B (Q. + (a, - (s:
= (alas) expa {B (a. + A.(a, - V.(s)) werr.. (8;
Since T. (als) = (alss) expat:) we can write terms of the form mo(als) exp, . in Eq. (87)-(88) as To(a|s) s>a the value function expression in Eq. (88), eventually recovering the equality in Eq. (86)
n. (a|s)), where the exponents of no(als) add to 1. Finally, we use this expression to simplify
o0(0) R (+ ( [v]) (s) 3a
11
Σ To(als)-~<
1
+ (s;
(89)
B
[s; B) - Marr. (3)
(90)
In the second linc, we use the fact that Par.. (s:
11 E. Ta(a
11 E. =u(a|s)\_< (als)) from
B a
Ba
Eq. (61). We can use the same identity to show that the conjugate in Eq. (87)
evaluates to zero,
(n(a)) B x0.0 r + BB [=] V. + + = Ba
11 Σ
To (a (als)
1
tua (8; =
(91)
B a
War. (e:3)
In Lemma 2, we provide a more detailed proof and show that this identity also holds for suboptimal policies and their worst-case reward perturbations, 3 10 (Ar=) = 0, where Eq. (91) is special case for Arr. (a, r(a,s) + MB [V. (s')] - V.(s) + (a, s).
Finally, note that the condition in Eq. (91) implics that for the optimal V. (s), the regularized dual objective (r) = miny, (1 - (Po. V/ + + 2 (r BBy' V- V + + in Eq. (14) reduces to the value function averaged over initial states, g = (1 (1- V.). This is intuitive since Vs(s) measures the regularizod objective attained from running the optimal policy for infinite time in the discounted MDP.
C.4 Plotting Value Function as Function of Regularization Parameters o,
Confirming Relationship between Normalization d'ar.. (s: 3), th. (s; B) and Value Function (s(s) In Fig. 5, we plot both (s(s) and vi.. (8,3) for various values of a (x-axis) and 3 (in each panel). We also plot whrr. (s: = } (1- - D. [To m.) in the third row, and confirm the identity in Eq. (86) in the fourth row.
As we also observe in Fig. 7, the soft value function or certainty equivalent Vs(s) = 1 (Q) is not monotonic in for this particular set of single-step rewards (the same r(a,s) as in Fig. 3 or Fig. 7). Note the small scale of the y-axis in the top row of Fig. 5.
While can be shown that (s 5) is convex as a function of 8, we see that (s B) is not necessarily convex in a and appears to be monotonically decreasing in a. Finally, we find that the identity in Eq. (86)- (90) holds empirically, with only small numerical optimization issues.
29

---

Published in Transactions on Machine Learning Research (07 (07/2022)
Value (s)s) as Function of 3, a In Fig. 7, we visualize the optimal value function Vs(s) = 3 (Q). for KL or a-divergence regularization and different choices of regularization strength 1/3. The choice of divergence particularly affects the aggregated value at low regularization strength, although we do not observe clear pattern with respect to a. In all cases, the value function ranges between max, Q(a, s) for unregularized deterministic policy as 3 - o0, and the expectation under the reference policy E [Q(a, 8)) for strong regularization as 3 + O. We also discuss this property in Sec. 5.1.
D Robust Set of Perturbed Rewards
In this section, we characterize the robust set of perturbed rewards which a given policy T(als) pla, 8) is robust, which also provides performance guarantees as in Eq. (2) and also describes the set of strategies available to the adversary. For proving Prop. 1, we focus our discussion on policy regularization with KL or a-divergence regularization and compare with slale-occupancy regularization in App. D.2.
D.1 Proof of Prop. 1: Robust Set of Perturbed Rewards for Policy Regularization
We begin by stating two lemmas, which will use characterize the robust set of perturbed rewards. All proofs are organized under paragraph headers below the statement of Prop. 1.
Lemma 2. For the worst-case reward perturbation Ara(a, s) associated with a given, normalized policy (als) and or Ki-diveryence regularizalion, the conjugate function evaluales to zero,
2 (Arz) = =0.
(92)
Lemma 3. The conjugale function (n) - (Ar) is increasing in Ar. In other words, if Ar(a, 8) Ar(a, (0
for all (a, 8) E A S, then I To.8 (Ar) 2 1 (Ar)
Proposition 1. Assume normalized policy <(als) for the agent is given, with E. T(ass) IVs E S. Under a-divergence policy regularization to a normalized reference To(als), the optimization over Ar(a, in Eq. (17) can be written in the following constrained form
R = Ar {
BAXS 1 so).
min (U, -arr-Ar) where ArERa
(18)
We refer to R C RAXS as the feasible set of reward perturbations available to the adversary. This translates to a robust set Rr of modified rewards r' s) = r(a, s) - Ar(a, s) for the given policy. These sets depend on the u-divergence and vegularization sirength B via the conjugate function.
For KL divergence regularization, the constroint is
Σ
(xxp (B. s)(a,)) $
(19)
aEA
Proof. Recall the adversarial optimization in Eq. (17) for fixed u(a, s) ((s)
min r -- - + { m (
(93)
Ar
which we would like to transform into a constrained optimization. From Lemma 2, we know that B (0% = for the optimizing argument Ar, in Eq. (93), but it is not clear whether this should appear as an equality or inequality constraint. We now show that the constraint 40 (Ar) 2 0 changes
Seee Belousov & Peters (2019); Lee et al. (2018; 2019), or Appendix C.4 additional discussion the effect of a-divergence regularization learned policies.
30

---

Published in Transactions on Machine Learning Research (07/2022)
the value of the objective, whereas the constraint 1 mization.
(Ar) To.33 (Ar)
S 0 does not change the value of the opti-
2 Incquality First, consider the optimization minar Ar) subject to 1 x0.0 (Ar) 2 0. From the
optimizing argument Arx, consider an increase in the reward perturbations AF(a, 2 (rz(a, s) V(a s) where 3(a, s) s.t. p(a,s) s) >> and Añ(a, s) > (rx(a, s). By Lemma 3, we have 0 3 (Ar) 2 1 (Arr)
0. However, the objective now satisfies (1,, Ar) < (u,r Arx) for fixed u(a, which is contradiction since Ar, provides a global minimum of the convex objective in Eq. (93).
& Inequality We would like to show that this constraint does not introduce a different global minimum of Eq. (98). Assume there exists AF(a, s) with 3 1.0 (Ar) < 0 and (uz,r - AF) < (Mr, Arx) for (Ar), we know that first-order Taylor approximation around Ar, everywhere underestimates the function, 3 (Ar) > 10
the occupancy measure Mr associated with the given policy By convexity of 3 (Ar),
Kond ( (Arx) + (Ar - Arx, V ( Fa.g (Arx)). Noting that Me = Vi (Ara) by the conjugate optimality conditions (Eq. (5), App. A), we have ( - 10 (Ara) 2 (Mr, AP) - Arx) This now introduces contradiction, since we have assumed both that 1 (AF) 42 (Arx) < 0, and that Añ(a, s) provides a global minimum, where (Mm. r Ar) (Mo. Arx) implies (ur, Ar) - (px, Arr) > 0. Thus, including the inequality constraint 3 3 (Ar) S 0 cannot introduce different minima.
This constraint is consistent with the constrained optimization and generalization guarantee in Eq. (1)- (2), where it is clear that increasing the modified reward away from the boundary of the robust set (i.c. ( decreasing Ar(a, s) and 9 no.9 (Ar)) is feasible for the adversary and preserves our performance guarantec.
See Eysenbach & Levine (2021) A2 and A6 for alternative reasoning.
Proof of Lemma 2 For a-divergence policy regularization and a given r[ass), we substitute the worst-case reward perturbations (r s) = i log,, mo(ale] + (s: 9) (Eq. (22) or Eq. (62)) in the conjugate function Arx)) (Eq. (56) or Table 2). Assuming E. (als)) = E. to(als) = 1, we have
s(als)
I
B xo.0
1 (Ar=)
1 1
Σ
To(als) exp, {-- (Arr(a, -
( (s) 1o
11
+ ():1))
3
B a
B Ba
11
To(als) 1 + (1)
1) 1)
1 1 x(a's) m-1
-1) + (s)(s; 3) var
-
11 ga
+ +ar(s;
B 0z
3 3a-1
(o(a|s)
11
1
+ (sr(3)
8 a
8 a
=0 0.
In the last line, we recall that (s; = 11 Σ. To(als) 11
Ba Ea
from Eq. (23) or (61).
3
For KL regularization, we plug (rx = log salas) Table 2,
(Eq. (51), into the conjugate in Eq. (47) or
1 L ( B Σ
1 molels) exp (s (a)r
Σ
ma(ass) exp {o} log <(als)
mu(als} 5 3 Σ x(als)
B
3
Proof of Lemma 3 See Husain et al. (2021) Lemma 3.
D.2 Robust Set for a-Divergence under p(a, 8) Regularization
For state-action occupancy regularization and KL divergence, Lemma 2 holds with B 1
(Ar,) = O for
pla.e) normalized ((a, and (r, 3/4 log po(a.s) However, the reasoning in App. D no longer holds for a- divergence regularization to reference po(a,s). 8). Substituting the worst-case reward perturbations (Fq. (24)
31

---

Published in Transactions on Machine Learning Research (07 (022)
(67)) into the conjugate function (Eq. (66) Table 2)
11 (Ar
11
= Σ Ho(a, expx (8- {))
(94)
3
3
1
no(a, 8) 31a (
m(aa))) a-1
-1))
11
3
Hola, 8)
B
1
no(a, (a-(a,))-~11a s)a,8) s)a==)
B
8
whose value not equal to 0 in general and instead is a function of the given μla, 8). This may result in the original environmental reward not being part the robust set, since substituting Ar(a, s) = 0 into Eq. (94) results in f n 2 (A)) 0.
D.3 Plotting the a- c-Divergence Feasible Set
To plot the boundary of the feasible set in the single step case, for the KL divergence regularization two dimensions, we can simply solve for the Ar(a2, s) which satisfies the constraint E. To(als) exp Ar(als)) for given Ar(aj,s)
1 Ar(az, s) = log
To(a2]s) (1 - To(alls) exp {3 Ar(ai,
(95)
The interior of the feasible set contains Ar(ai, 8) and Ar(a2, 8) that are greater than or equal to these values. However, we cannot analytically solve for the feasible set boundary for general a-divergences, since the conjugate function g 1 (Ar) depends on the normalization constant of (a, Instead, we perform exhaustive search over range of Ar(a1, s) and Ar(a2, 8) values. For each pair of candidate reward per- turbations,
CVX-PY (Diamond & Boyd, 2016) to solve the conjugate optimization and evaluate (2*(() Ar). We terminate our exhaustive search and record the boundary of the feasible set when we find B Ro.0
that B To.0 (Ar) = within appropriate precision.
5 r(a)
E
Value Form Reward Perturbations
E.1 Proof of Thm. (Husain al. (2021))
We rewrite the derivations of Husain al. (2021) for our notation and setting, where Q(n) represents a convex regularizer. Starting from the regularized objective in Eq. (12),
1 Mk))
max RL), max (U, MEM
(96)
PEM
note that the objective is concave, as the sum of a linear term and the concave -Ω. Since the conjugate is involution for convex functions, rewrite RLa,s(r) -(RRRn,((r) -((-RRn,)))) which
32

---

Published in Transactions on Machine Learning Research (07 (0722222)
yields
RCa,0(r)
sup -(( ((-RCa,))"")
NEM
(1)
sup (1,T²) - (-RLn PERAAX
sup
MEM
inf NEM r'ERAXS
sup
(11, -r²) + (-R(a,,)
(2)
inf (u, + (-R MEM r'ENA
sup
sup inf
(1,r) sup (n' -r') RLo
WEM MERAXS
(4)
WEM r'ERA (u,r" +
sup inf
sup (p', -r') + (//,)) 1
= (0()))
sup inf
(U, r') +
sup (pl 8- (r-r")) -s(()))
NEM r'EAAK
3
V
(5)
sup inf
(1, +
1
( (r-)))
NEM r'ERA
3
(6) inf sup (u, r²) + 22' (B. (r-r)) -r))
(97)
r'EAAxS
PEM
3
where (1) applies the definition of the conjugate of (RR (2) reparameterizes the optimization in terms of r' + -r', (3) is the conjugate for (-RCn,,); and (4) uses the definition of the regularized RL objective for occupancy measure sa) with the reward r(a, s). Finally, (5) recognizes the inner maximization the conjugate function for modified reward and (6) swaps the order of inf and sup assuming the problem is feasible.
Note that Eq. (97) is a standard unregularized RL problem with modified reward r' s). As in Sec. 2, introducing Lagrange multipliers (ss) to enforce the flow constraints and X(a, s) for the nonnegativity constraint,
RLn,((r) = inf inf sup (1, + T a. [V] V + 2) + pd V.A
{ o (B (r - (r- + +1 (1- (po.
(98)
Now, eliminating p(a,s) s) yields the condition
sa) + [V (+') (s) + M(, =) 0
V(s) = r + [v(')) + A(a, s).
(99)
Letting Arv(a, = r(a, r'aa, 8), we can consider Eq. (99) constraint and rewrite Eq. (98) as
(r = inf inf (1 - 7) v) + Arv V.A
1 r
fr (B Arv)
(100)
3
subj. to (ss) r(a, s) DB [vs')] - Arv(a, + X(a,s)
which matches Theorem 1. See Husain et al. (2021) for additional detail.
See App. A.3 for the proof of Prop. 3, which equates the form of Arv(a, and (a, at optimality in the regularized MDP.
E.2 Path Consistency (Comparison with Nachum et al. (2017): Chow et al. (2018))
We have seen in Sec. 3.3 and App. E.2 that the path consistency conditions arise from the KKT conditions. For KI. divergence regularization, Nachum et al. (2017) observe the optimal policy (a(a)) and value V.(s)
33

---

Published in Transactions on Machine Learning Research (07 (07/202) 2022)
satisfy
T. (als))
r(a, s) + +.B [V((s']
log
= Va(s).
(101)
To (alss)
where the Lagrange multiplier (a, s) is not necessary since the n. (a|s) > 0 unless To(a)s) = 0 or the rewards values are infinite. This matches our condition in Eq. (39), where we can also recognize Arz, (a, 8)
[=(als) = r(a,s) + [v. - (s) - (a, s) as the identity from Prop. 3. Nachum et al. (2017) use 1 log no(als)
Eq. (101) to derive learning objective, with the squared error Ea,s, 8) () [V(+)] 3 log x(eao)
(a|a)
[[ used loss for learning It (alss) and V(s) (or simply Q(a, Nachum et al. (2017) Soc. 5.1) using function approximation.
Similarly, Chow et al. (2018) consider a (scaled) Tsallis entropy regularizer, }.((T) = Bata-1 (Ea T(als) -
Σ. {a))s))). For a 2, the optimal policy and value function satisfy
1 r(a,s) 8) + B.. [V.(''] + M(a,)) 8) + B Ba(a- 1) 3a- (a= Vv(+)+ + A(8)
(102)
where A(s) a Lagrange multiplier whose value is learned in Chow et al. (2018). However, inspecting the proof of Theorem 3 in Chow et al. (2018), we see that this multiplier is obtained via the identity A(s) = vQ. (s; - (s) = varr, (s; (see Eq. (23), App. C.3). Our notation in Eq. (102) differs from Chow et al. (2018) in that we use 3 as the regularization strength (compared with their a). We have also written Eq. (102) to explicitly include the constant factors appearing in the a-divergence.
In generalizing the path consistency equations, we will consider the a-divergence, with Q(x)) ad- ((1 a) Σ. (a(a)s) + +. T(als)- - E. (((a)))=~=<((())))) Note that this includes an additional a factor which multiplies the Σ. (aa s) term, compared to the Tsallis entropy considered in Chow et al. (2018). In particular, this scaling will change the 1 ai additive constant term in Eq. (102), to a term of 3 a-
Our expression for a-divergence path consistency, derived using the identity r(a, 8) +) (V. s_(a)) (s) + thrr.. (5 in Eq. (39), becomes 1 loga to(a|s)
1 (als)) r(a, s) + tB [v') + X(a, s) 3 (a(ass)
loga
= Vz(s) + +War.. ()
(103)
where we have rearranged terms from Eq. (28) in the main text to compare with Eq. (102). Note that we can recognize (rx 8) = y log, (als) ma(a]s) + thar.. (8; (3) and we substitute A(s) == vh. (8; - Vs()) = .haar. (8: (3)
compared to Eq. (102).
E.3 Indifference Condition
In the single step setting with KL divergence regularization, Ortega & Lee (2014) argue that the perturbed reward for the optimal policy is constant with respect to actions
r(a) Arn. (a) Va E A,
(104)
when Ars, (a) are obtained using the optimal policy (als). Ortega & Lee (2014) highlight that this is a well-known property of Nash equilibria in game theory where, for the optimal policy and worst-case adversarial perturbations, the agent obtains equal perturbed reward for each action and thus is indifferent between them.
In the sequential setting, we can consider Q(a, = r(a, 8) + 7E,." [VE.. as the analogue of the single-step reward or utility function. Using our advantage function interpretation for the optimal policy in Prop. 3, we directly obtain an indifference condition for the sequential setting
(a, Arz. (a. Vs(s)
(105)
34

---

Published in Transactions on Machine Learning Research (07/202) /022)
(a) Environment
(r(a,s) s) = -1 for water,
r(a,s) s) = for goal)
(b) 8 = 0.2 (High Reg.)
(c) 8-1
(d) 10 (Low Reg.)
Figure 8: Confirming Optimality of the Policy. We show the perturbed rewards ra .) Q(a,s) Ar(a, s) for policies trained with KL divergence regularization. The indifference condition holds in all cases, with ra s) c(s) for each state-action pair, with c(s) = (s)) for KL regularization. This confirms that the policy is optimal (Ortega & Lee, 2014; Nachum et al., 2017).
for actions with (a, s) = O and nonzero probability under T.(als) Observe that V.(s) is constant with respect to a E A for a given state s E S. Recall that our notation for (s(s) omits its dependence on B and a. This indifference condition indeed holds for arbitrary regularization strengths 3 and choices of a-divergence, since our proof of the advantage function interpretation in App. A.3 general. Finally, we emphasize that the indifference condition holds only for the optimal policy with a given reward r(a, s) (see Fig. 3).
E.4 Confirming Optimality using Path Consistency and Indifference
In Fig. 4, we plotted the regularized policies and worst-casc reward perturbations for varions regularziation strength and KL divergence regularization. In Fig. 8, we now seek to certify the optimality of each policy using the path consistency or indifference conditions. In particular, we confirm the following equality holds
1 r(a, 8) + WEd [V(')]
[[as)) 3 To (als)
log
(ss)
AAx
(106)
which aligns with the path consistency condition in (Nachum et al., 2017). Compared with Eq. (28) or Eq. (103), Eq. (106) uses the fact that X(a,s) 0 and (s; 0 in the case of KL diver- gence regularization. This equality also confirms the indifference condition since the right hand side (s) is constant with respect to actions. Finally, we recognize our advantage function interpre- tation (a, s) - Ar., (a, = (s) in Eq. (106), by substituting (a, = r(a,s) + YTE [V. (s')) and Ar.. (a, 8) = log mo[a|e]
m_(as) for KL divergence regularization.
=(als) In Fig. 8, we plot r(a, s) + YB,, [V(s'] log zo(als) = Q(a - (a, s) for cach statc-action pair to confirm that it yields a constant value and conclude that the policy and values optimal. Note that this constant is different across states based the soft value function V.(s), which also depends the regularization strength.
F Comparing Entropy and Divergence Regularization
In this section, we provide proofs and discussion to support our observations in Section 5.1 on the benefits of divergence regularization over entropy regularization.
F.1 Tsallis Entropy and a-Divergence
To show a relationship between the Tsallis entropy and the a-divergence, we first recall the definition of the g-exponential function log, (Tsallis, 2009). We also define log, (u); with = 2 q, so that use of log, (u)
35

---

Published in Transactions on Machine Learning Research (07 (022)
matches Lee et al. (2019) Eq. (5)
log, (u) = I - w (
loga (u) = log2-of a
(
(107)
The Tsallis entropy of order q (Tsallis, 2009; Naudts, 2011) can be expressed using either log, loga
[[][(aa]]
1 1 (1-
x(a)²
Σ
T(a)
(108)
9 q-1 aEA
T(a)
aEA
Σ
T(a) log2-g (T(())
(109)
aAA
Eq. (108) and Eq. (109) mirror the two equivalent ways of writing the Shannon entropy for q 1. In particular, have 2 - and H1 [T(())] Σ (a)) log स(ब) - Σ (a) log T(a). See Naudts (2011) Ch. 7
for discussion of these two forms of the deformed logarithm.
To connect the Tsallis entropy and the a-divergence in Eq. (7), we can consider a uniform reference measure To(a) 1 Va. For normalized Ea (a) =
Da(Fo(a) = a(1 - a)
1
(1-cl a) Σ To(a) + ta Σ x(a) Σ
to(a) [(((s))))
(110)
aed
aed
acd
1
a+ - a) Σ
T(als)"
(1-a) Σ mo(a)
(111)
a(1 - a)
a(1 - a)
REA
asA
Ha [
(112)
which recovers the negative Tsallis entropy of order o, up multiplicative factor 1 and additive constant. a Note that including this constant factor via a-divergence regularization allows to avoid inconvenient 1 factor in optimal policy solutions (Eq. (27)) compared with Eq. 8 and 10 of Lee et al. (2019).
F.2 Non-Positivity Arx (a, 8) for Entropy Regularization
We first derive the worst-case reward perturbations for entropy regularization, before analyzing the sign of these reward perturbations for various values of a in Prop. 5. In particular, we have Ar=(a, 8) S 0 for entropy regularization with < a S 1, which includes Shannon entropy regularization at a = 1. This implies that the modified reward (a, s) 2 r(a,s) for all (a, s).
Lemma The worst-case reward perturbations for Tsallis entropy regularization correspond
Ar 8) loga (a|s)) 3a (1
1
Σ x(als))).
(113)
aEA
with limiting behavior of (ra 8) = log n (als) for Shannon entropy regularization as a +
Proof. We write the Tsallis entropy using additional constant k with k = mirroring the a-divergence
H
k
Σ
r(als) Ex(als)3 asA
(114)
Note that we use negative Tsallis entropy for regularization since the entropy is concave. Thus, the worst reward perturbations correspond to the condition (rz(a, s) V 2 entiating with respect to p(a,s) 8) using similar steps as in App. B.3 Eq. (59)-(60), we obtain
(Ha) (n) VEn(o) [*]]]] Differ-
1
Ar Ar (a, 8) = z log, r(als) + (a 1)H
(115)
For k and (a (m Ea =(als) =(lss))),, we obtain Eq. (113).
7
36

---

Published in Transactions on Machine Learning Research (07 (07/2022)
1 and > the worst-case reward perturbations with Tsallis entropy regularization from Lemma 4 are non-positive, with (rx(a, 8) S 0. This implies that the entropy--egularized policy is robust to only pointwise reward increases for these values of a.
Proposition 5. For 0
Proof. We first show loga x(als) S 0 for 0 < x(aas) S and any a. Note that we may write
log, m{ass) /
(((ol)) u du
((aas)
1 (T(als)=-1
a na-1
(116)
a
Since u²-2 a non-negative function for x(ass) S 1, then f (T(())) a0-2du s 0.
To analyze the second term, consider 0 a S 1. We know that {{als) x(als) for < =(dss) S 1,
that La {(als) 2 Ea ttaas) = 1. Thus, have Ea {(lss) - En {a I and > 0 implics
(E. (als) E. (aals))) S O. Since both terms are non-positive, we have Ar, (a. s) 0 for 0 < a S desired.
However, for a > 1 or a < O, we cannot guarantee the reward perturbations are non-positive. Writing the second term in Eq. (113) as -=1 [T][], we first observe that that H [m] 2 O. Now, a > 1 or a < 0 implies that O, so that the second term is non-negative, compared the first term, which is non-positive. ]
a
F.3 Bounding the Conjugate Function
Conjugate for a Fixed 3; We follow similar derivations Lee et al. (2019) to bound the value function for general a-divergence regularization instead entropy regularization. We are interested providing a bound for 10 (Q) with fixed a, B. To upper bound the conjugate, consider the optimum over each term separately
(0)
(=, DD(FFo
1
max
TEalA
(5, -min 1 Da(Fo:m0 x]
max
HEAlAl
max (x, -0 -0 HEalAl
Q(amax, 8)
where we let dmax arg max, ((a, 8).
We can also lower bound the conjugate function in terms of max, ((a, 8). Noting that any policy (als) provides lower bound on the value of the maximization objective, we consider (a)s) = 5(a- mmax).
For evaluating (a)x(a)s) we assume 0 0 for a > and undefined otherwise. Thus, we restrict our attention to >> 0 to derive the lower bound
1 1orte) (Q)
max TEAlA!
(T,
1
Da [no m]
3
1 Dalato (iTo Tmax]]
A (Tmax, Q)
3
Q (amaxx
1
To no((maxls))
13 aa
a(1 a) (To(Amax/ a
1 1
1
Q Qaamaxx s)
+
3 a 1-
11 1
= Q(amax 8) + logz.n To(Amax s).
3
where (1) uses Tmax (als) 8(a amax) and simplifics terms the a-divergence. One can confirm that
1 log2-a To(omax) s) a I (ro(amaxll (s) 1-a 1) < O for a > O. Combining these bounds, we can write a
1
1 log To (mmamx))s) s ( (Q) S Q (Amaaxx s). 8
For a > 0, Quamaxx +)+ 3a
(117)
37

---

Published in Transactions on Machine Learning Research (07 (07/2022)
=
B ==100 1.0
B= 0.5
3.0
2.5
2.0
2.0
1.3
1.0-
1.2
0.5
0.5
0.0
0.5
1.0
2.0
2.5
0.0
0.5
1.0
1.5
2.0
2.5
3.0
0.3
0.5
1.0
1.5
2.0
2.5
3.0
(a) Fig. 2 or Fig, 9 (left) of Eysenbach & Levine (2021)
(b) Shifted p'=r- Ar- In(2)
(c) With prior mo(als) u(a) =
Constraint: Σ. exp(3Ar(a)) <
Constraint Σ ma(a) Tx(a) exp(33r(a)) S
Constraint: >n exp(3Ar(a)) $
Figure 9: Analyzing the feasible set for entropy regularization (a) versus divergence regularization (b,c).
Conjugate as a Function of 3: Finally, we can analyze the conjugate as a function of B. As 3 + 0 and 1/3 - oo, the divergence regularization forces <{als) = To(als) for any a and the conjugate B 1 (Q) (=rass), ((a, s)} [((T) (T(aas), Q(a, As B - 20 and 1/B - O, the unregularized objective yields a deterministic optimal policy with T(als) = max, Q(a, In this case, the conjugate [n (Q) max s(a,s). Thus, treating the conjugate as a function of B, we obtain p $0.0
1 00 (Q) S max ((a,
E Exo(a(s) (Q(a, s)] S
(118)
3
For negative values of 3, the optimization becomes a minimization, with the optimal solution approaching a deterministic policy with क [[ass) min, ((a, s) 3 -c, 1/3 0.
F.4 Feasible Set for Entropy Regularization
In this section, compare feasible sets derived from entropy regularization (Fig. 9a) with those derived from the KL divergence (Fig. 2, Fig. 9b,Fig. 9c), and argue that entropy regularization should be analyzed as special case of the KI. divergence to avoid misleading conclusions.
In their App. A8, Eysenbach & Levine (2021) make the surprising conclusion that policies with higher entropy regularization are less robust, as they lead to smaller feasible or robust sets than for lower regularization. This can be seen in the robust set plot for entropy regularization in Fig. 9a, where higher / indicates lower regularization strength (1/3). The left panels in Eysenbach & Levine (2021) Fig. or Fig. match our Fig. 9a. See their App. A8 for additional discussion.
To translate from Shannon entropy to KL divergence regularization, we include an additional additive con- stant of 1 log |A| corresponding to the (scaled) entropy of the uniform distribution, with D2 mol 3
1 HT)) 1 log AA). We obtain Fig. 9b by shifting cach curve in Fig. by this scaled constant This 8
highlights the delicate dependence on the feasible set on the exact form of the objective function, as the constant shifts the robust reward set by ('(a1),r'(az))
(r'(a)) 1/2 2,g 2, raz)) log For KL diver- gence regularization, the feasible set now includes the original reward function. As expected, we can see that policies with higher regularization strength are more robust with larger feasible sets.
An alternative approach to correct the constraint set to include the uniform reference distribution as in Prop. and Eq. (19), so that we calculate En (a]ss) exp (B. Ar) < 1. Similarly, the constraint in Eysen- bach & Levine (2021) can be modified to have Σn exp {3 Ar} s [A] in the case of entropy regularization.
Our modifications to the feasible set constraints clarify interpretations of how changing regularization strength affects robustness. We do not give detailed consideration to the other question briefty posed in Eysenbach & Levine (2021) App. A8, of 'if reward function r' is included in robust set, what other reward
38

---

Published in Transactions on Machine Learning Research (07 (07/2022)
functions are included in that robust set?', whose solution is visualized in Eysenbach & Levine (2021) Fig. 9 (right panel) without detailed derivations. However, this plot matches our Fig. 9b and 9c. This suggests that the constraint arising from KL divergence regularization with strength B, Σ (o(as)) {3- Ar(a, = 1, is sufficient to define both the robust set for a given reward function and to characterize the other reward functions to which an optimal policy is robust. The key observation that the original reward function is included in the robust set when explicitly including the reference distribution *o(a|s) as divergence regularization.
G Worked Example for Deterministic Regularized Policy (a 2, 3 =10)
We consider the single-step example in Sec. 4.1 Fig. 2 or App. H Fig. 10-11, with two-dimensional action space, optimal state-action value estimates, Q= s) r(a,s) (1.1, 0.8), and uniform prior To(a)s).
The case of policy regularization with a 2 and 3 10 is particularly interesting, since the optimal policy is deterministic with T., (r, (s) = 1. 6 First, we solve for the optimal policy for Q+ 8) r(a, s) as in App. C.2,
1
0 (Q..) = max
(T.
3 (10 - vo(s; 8)
1
Σ x(ass) -1 + Σ
Ma.
3
TEAl-l
(als)) = no(als)
1 + 3(a (), + sa
V.(s) Wark. (8;
=vq. (5:8) (see App. C.3)
where for a 2, we obtain n. (als)) no(a|s} (Q, (a. (a, V=(8) aar.. (s:3))]
Using CVX-PY (Diamond & Boyd, 2016) to solve this optimization for = 2, 3 10, To(als) Va, and the given (a, we obtain
(a 8) = 1.1
Q. (a2,8) 8) = 0.8
A (a1, 8) 0
Tu (a1 8) = 1
T. (ag 8) = 0
(az, 8) = 0.1
(s) = 1.05
Arr. () = 0.05
vq. (s: 1.0.
(119)
Our first observation is that, although the policy is deterministic with n. (a1 (s) = 1, the value function (s)s 1.05 is not equal to max, (a, = 1.1 it would be in the case of unregularized policy. Instead, we still need to subtract the a-divergence regularization term, which is nonzero. With a = 2 and -a- 1, we have
(s) = (a.s) (a.)
11 1
1 Σ To(a|s) - T. (als))
111 1 (1-.5-) 12 -5- =1.1
5- 0²)
B lal-a - a
102
1. Do [=0om]]
1.1 + .05 (1 2) 1.05
Recall that for normalized Tu, n, we have whrr. ( confirm Eq. (119) for = 2.
= -o)) n. [a|s)] -0.05, so that we
Finally, we confirm the result of Prop. 3 by calculating the reward perturbations in two different ways. For 01, we have
Ars. (ai, 8)= 3a-1
(ai (s) a-1 To Is) -1 + var.. (s:
1 1
1
-1) - 005- = .05
10
.5
= sQ)
Va(s) + (a = 1.1 1.1.-.00 .05
and for d2
Arr. (02,8) = a
n. (az 8) a-1
-1) war.. (s: 10 I .5
1
-1
- -.05 -15
Ro(a2
= Qa 8) V.(8) + A. 0.8 1.05 0.1 -.15
We a instead in Fig. for simplicity of caleulations. See App. Fig. for 2 robust set plots.
39

---

Published in Transactions on Machine Learning Research (07 (07/2022)
that have Arx. (a1. s) 0.05 and Arn. (02, 8) -0.15.
We can observe that the indifference condition does not hold, since - (01, = 1.1 0.05 = 1.05 does not match (02, s) - Arx. (a2, 5) = 0.8 (-0.15) = 0.95.
However, adding the Lagrange multiplier (az, 8) 0.1 accounts for the difference in these values. This allows us to confirm the path consistency condition (Eq. (28)),
r(a,s) + B [v(())
1
log,
T. (a
WArn. (v; B) = (.) - (. v(a,s)
(120)
3
To (aaa])]
Q-(a,s)
Are. (a,6)
with Q-(a1, 8) - Ar.. (01, 8) (s) + A. (11, = 111 0.05 - 1.05 + 0 and (a2, - Arn. (a2, (a(s) + (a2, 8) = 0.8 (-0.15) - 1.05
Additional Feasible Set Plots
Fig. 10 and 11, we provide additional feasible set plots for the a-divergence with a E (-1, and I (0.1, 5, 10) with r(a, 8) = 0.8) As Fig. 2, we show the feasible set corresponding the single-step optimal policy for (a. r(a, for various regularization schemes. Since cach policy is optimal, can confirm the indifference condition for the divergence, with Q. Arx, (a, (s))))))))))))) constant across actions and equal to the soft value function, certainty equivalent, conjugate function (s) 3 Ro. ( (Q). When the indifference condition holds, we can obtain the ratio of action probabilities in the regularized policy by taking the slope of the tangent line to the feasible set boundary at r (a, 8), as in Sec. 4.1.
However, indifference does not hold in cases where the optimal policy sets (=(a)))) 0, which occurs for (a 2, 10), (a=33 3, B E {5, 10)) for uniform reference policy and additionally for (a = 2, 5) with the nonuniform reference in Fig. 11. In these cases, cannot ignore the Lagrange multiplier in Eq. (28), rh (a, (a, Ar.. (a, 8) = Vs) X. (a, 8), and X. (a2, 8) > 0 results in a different perturbed reward Tx (a), # rr s).
For a = - and low regularization strength (B = 10), we observe a wider feasible set boundary than for KL divergence regularization. For a and 3, the boundary more restricted and the worst-case reward perturbations become notably smaller when the policy is deterministic. For example, we can compare 3 = 5 versus 10 for 2. However, in Fig. 7, we do not observe notable differences in the robust sets lower regularization strengths based on the choice of a-divergence.
40

---

Published in Transactions on Machine Learning Research (07/2022)
10
10
Y60
21x
Stua
04
Okar
34
36
34
12
34
32
15
34
LE
(a)
1, 0.1
(b) a
1,
cc)
a
11
(d) at
11
10
Ve5
700
E5
Ecc
260
Tearbl
68
24
26
25
24
22
14
10
14
(e) DEL, 3 0.1
D
(g) DEL, 3 =5
(h) DKL, 3 10
12
1.2
13
12
Cos
Aeut Sat
Icaa Se
SctuiSe:
Gh
Went-aus
24
25
24
22
15
14
2, 0.1
(i) 2, =1
O 2,
2, 8 10
12
12
11
13
200
200
201
67
Bok S4
Roxe WeniCas
WentCoo
36
An
(m) 3,3 0.1
(0) 3,8
(p) 3, 10
Figure 10: Reference distribution To = ( 2) See caption of Fig. 11.
12
21
141
13
11
38.
16
Sca-
Ioxa Wenscass
Eotutie Manscans
Weri-Cos
Weri-Ca
1, = 0.1
(b) -1,
1,,3
(c)
11,8
1,
10
11-
12
2nx
Teaill Set
Poluted
35
1/
14
36
(e) DKL, 0.1
(f) 8=1
DKL, 3 =5
(h) DKL, 3 10
32
1.2
13
32
11
13
Tos
Ecc
20c
Teut Stt
Bous Stt
Ioue Se
EotutSe: Manican
WhniCas
WemtCan
24
3, 0.1
(i) 2,
(k) 2,9
2, 10
21
1.1
12
11
8ox
67
Werd Ca0
(m) 3 0.1 (n) a0a=3 0,8
(0) = 3,3
(p) a 3, 10
Feasible Set (red region) of perturbed rewards available to the adversary, for KL (a = 1) and a-divergence (a = (-1,2,3)) regularization, various 3, and fixed (a, s) = r(a,s) s) values (blue star). We consider the optimal n. (als) with regularization parameters a, B, m and the given Q-values. Red star indicates worst-case perturbed reward r' = =r- - Arr. for optimal policy.
Figure 11: Reference distribution To
41


Reviews:
[{"review_id": "k6tUFyM7eh", "reviewer": "Reviewer_drrf", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n(1) The understanding of regularizers are ways to create robust reward perturbation is interesting. The main results (Propositions 1 and 2) tell a novel and reasonable understanding of the effect of regularizers in reinforcement learning (RL).\n\n(2) The techniques are not highly novel but are cleverly used.\n\nThis work and its techniques are mainly based on regularized policy optimization, which is a relatively well-studied line of work in RL. The authors used existing techniques in a meaningful way. Relations with existing results of path consistency and indifference conditions are well discussed, which I appreciate.\n\n(3) Simulations are conducted to support the results.\n\nWeakness:\n\n(1) The theory seems a bit weak. It gives me a sense that \"to not hurt the performance we would just make reward value larger\", which is reasonable but not quite surprising. I added some comments in the below question part.\n\n(2) The experiments seem not enough to show that the robust sets in the theory is a very useful result. If there could be some theoretical/empirical results showing that the robust perturbation sets cover a number of practical perturbations/noises, then that would be great.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The first main contribution of this work is to show robustness of regularization policy optimization, i.e., there exists a robust set of reward perturbation, such that for any perturbed reward in this set, solving the regularized value maximization problem does not harm the regularized optimality (Proposition 1). The authors also did provide results for KL divergence, alpha-divergence, Shannon entropy and Tsallis entropy regularizers.\n\nThe second main contribution is the calculation of the worst-case reward perturbations. The results match existing work of path consistency conditions and an indifference condition in game theory literature.\n\nThe authors then visualized the robust reward sets under simple cases (Figures 1 and 2), and conducted simulations to verify the theory.\n\n\n\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Please clarify the following questions.\n\n(1) In Figure 1, it seems that both $r(s, a)$ and the red star (Prop. 2) are on a frontier (it looks to me all the points on the same frontier are kind of the same in terms of they are on the boundary of being robust). Why is the red star called the worst-case?\n\n(2) The main results give me the following intuition: if we do not want to hurt the performance (which is the maximum regularized value), then only adding reward could achieve that (make a larger $r^\\prime$), e.g. as shown in Eq. (19)\n\nHowever, if we define $r^\\prime = r - 100$, then Eq. (19) would not hold, but arguably this reward shift should not change the performance/robustness of the the algorithm (since it does not change the problem's nature). Does the theory support this? Or if this does hurt robustness, how come this would happen?\n\n(3) Following the above (if the case is sometimes even if conditions like Eq. (19) is not satisfied, robustness can still be preserved), I think a more interesting question would be to investigate the robustness for perturbations beyond the robust sets (or show the robust sets in this work is practical enough).\n\nSince a larger $r^\\prime$ would always intuitively make the value large, and in practice an environment noise probably would not satisfy this. It would be ideal if the authors could discuss whether the calculated robust perturbation sets in this work could cover e.g. a Gaussian noise, or what would be the robustness result beyond the robust sets.\n\n", "broader_impact_concerns": "This work contains mostly theoretical results and simulations. As far as I can see, I did not see any ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ysNUMuRtXi", "reviewer": "Reviewer_sL7p", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very well written, and the text is very easy to follow.  I have some concerns about the relevance of the results presented in this work. Most of the derivations are standard consequences of convex analysis and are to my understanding present in other works in the literature. Regularization in MDPs and the properties of their dual, and primal problems have a long and rich literature. Nonetheless, there is some value in presenting these simple derivations in a single place and with a unified story. As for the robustness explanation advanced by the authors, I am not extremely convinced this angle is more than by noting the Lagrangian can (obviously) be written as a min -max objective. My main concern here is how the constraints on the adversary’s perturbations are a property of the regularizer. This means the adversary here is more of a semantic devise than a true model for potential adversarial behavior. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the use of regularizers in reinforcement learning. The main objective of the submission is to give a unified explanation that divergence regularization in reinforcement learning / both in the policy and the state visitation settings can be interpreted as finding a solution that is robust to reward perturbations. These results had been alluded to in the existing literature, but there had not been a thorough study and explanation of these phenomena before. The authors provide mathematical derivations of these claims and some experimental results to provide visual explanation of their findings. The main ‘insight’ is that by writing regularized RL as a saddle point problem, one can interpret the solution as a ‘game’ between a learner and an adversary. The adversary’s objective can be written as producing a perturbation of the reward within a feasibility set determined by the nature divergence regularizer.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I believe the work has enough merits to deserve publication.  That being said, I would really like to see addressed the concerns expressed above around the nature of the adversary and how that links with the claims made by the paper.", "broader_impact_concerns": "This work does not pose any ethical concerns.  ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "vaHhIyUXuk", "reviewer": "Reviewer_1MHa", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The topic of the paper, regularized RL, should be of great interest to the RL / ML community in general. It is also widely used in modern RL practice and so practitioners may benefit from the understandings provided in this paper.\n\n* Overall, the paper is well-executed, and may provide a better entry point for this topic compared with the aforementioned two papers: \n  - Eysenbach and Levine (2021), Theorem 4.1 first proves this result for the entropy regularizer. However, their paper did not spell out convex conjugacy as the main underlying reason for this result. \n  - Husain et al (2021) is more similar to the present paper in that they also use convex conjugacy to obtain this result, and they present a generic result that holds for general convex regularizers. The improvement of the present paper over Husain et al. (2021) is perhaps a bit more marginal. However, given this generic result, the present paper contains more concrete specializations (e.g. $\\alpha$-divergence) and discussions, which could make it more digestible. \n\n* I also like the visualization experiments, in particular the grid-world experiment in Figure 4. It is interesting to see how various regularization strengths correspond to qualitatively different worst-case reward perturbations.\n\n* The main claims within this paper are justified in my opinion. I did not go through all the Appendix, but I checked a few main proofs and they appear to be correct.\n\nWeaknesses:\n* The paper seems like an “understanding” paper in my opinion, as opposed to either an RL theory paper or an algorithms / empirical RL paper. While that itself may not be a concern, one may argue that the understanding presented in this paper is not new, as the essence is already in the aforementioned two papers. Therefore, even though I like the execution of this paper, I am not sure how to judge the worthiness of such a contribution.\n\n* The mathematical statements in some results / discussions are often not self-contained and could be confusing. A few examples are, \n  - The statement of Proposition 1, “the feasible set of adversarial reward perturbations is defined by the constraint xxx”, does not seem to have a subject. I wonder whether the authors mean “The regularized problem (12) is equivalent to the constrained problem (1) with feasible set xxx”. \n  - Section 5.1, difference between Shannon entropy (used in Eysenbach & Levine 2021) vs. KL. Why is there a difference? I am confused here because on Page 3 the authors consider the KL divergence to be wrt unnormalized measures, so I think they are equal up to an additive constant. Perhaps the authors could have the formula for Shannon entropy vs. the particular KL they are referring to side-by-side to highlight the difference. \n\n* Related to the first point, I feel like the overall claim of this paper (in particular the title/abstract) may be slightly overclaiming and needs to be tuned. In particular, the abstract sounds like the equivalence result itself is new, which does not properly reflect existing work. The main text suffers less from this issue, e.g. Table 2 seems like a rather fair comparison with prior work.\n\nGiven the above, my overall feeling about this paper is weakly positive, with the main advantage being the practical importance of the topic and the good execution, and main concerns being on the worthiness of the contribution.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies policy regularization algorithms (such as entropy regularization) that are widely used in RL practice. The main focus is an equivalence result showing that the regularized RL problem is equivalent to a robust reward maximization problem with the reward perturbation lying in a certain set depending on the regularizer, which are first established in Eysenbach and Levine (2021) and Husain et al. (2021). \n\nThe main contribution of this paper is a generalized and more unified version of this result:\n\n* spells out clearly the underlying reason (convex conjugacy) that enables this result\n* covers new regularizers ($\\alpha$-divergence)\n* a visualization of the worst-case reward perturbation corresponding to the optimal policy with various regularizers, in toy and grid-world environments\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "* Perhaps the authors could revise the mathematical statements to make them more self-contained. Adding references to equation numbers (and adding new equations when necessary) may help. \n\n* I also suggest the authors carefully revise the claims in the abstract and introduction to better acknowledge existing work. Maybe consider moving Table 2 to the beginning (e.g. Page 2 / 3) to the paper. \n\n* I find the barplot visualizations in Figure 3 not that easy to digest (also, perhaps not much more informative over Figure 1 / 2). Maybe consider moving it to the Appendix or improving its presentation.\n", "broader_impact_concerns": "I don’t see any broader impact or ethical concerns regarding this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers were all in favor of accepting the paper. During the reviewer discussion (whose contents were summarized to the authors in a direct discussion), there were some concerns raised regarding the validity of the robustness notions considered in the paper, but eventually it was deemed that a detailed study of these issues probably goes way beyond the scope of this work. Thus, given the overall positive evaluation of the work by the reviewers, I am eventually happy to recommend this paper for acceptance at TMLR.
Decision: Accept (poster)