If MaxEnt RL is the Answer, What is the Question?
Authors: Benjamin Eysenbach
Sergey Levine
Venue:  (2020)
Keywords: reinforcement learning
maximum entropy
POMDP

Abstract: Experimentally, it has been observed that humans and animals often make decisions that do not maximize their expected utility, but rather choose outcomes randomly, with probability proportional to expected utility. Probability matching, as this strategy is called, is equivalent to maximum entropy reinforcement learning (MaxEnt RL). However, MaxEnt RL does not optimize expected utility. In this paper, we formally show that MaxEnt RL does optimally solve certain classes of control problems with variability in the reward function. In particular, we show (1) that MaxEnt RL can be used to solve a certain class of POMDPs, and (2) that MaxEnt RL is equivalent to a two-player game where an adversary chooses the reward function. These results suggest a deeper connection between MaxEnt RL, robust control, and POMDPs, and provide insight for the types of problems for which we might expect MaxEnt RL to produce effective solutions. Specifically, our results suggest that domains with uncertainty in the task goal may be especially well-suited for MaxEnt RL methods.

Under review as a conference paper at ICLR 2020
IF MAXENT RL IS THE ANSWER, WHAT IS THE QUESTION?
Anonymous authors Paper under double-blind review
ABSTRACT
Experimentally, it has been observed that humans and animals often make de- cisions that do not maximize their expected utility, but rather choose outcomes randomly, with probability proportional to expected utility. Probability matching, as this strategy is called, is equivalent to maximum entropy reinforcement learning (MaxEnt RL). However, MaxEnt RL does not optimize expected utility. In this paper, we formally show that Max RI. does optimally solve certain classes of control problems with variability in the reward function. In particular, we show (1) that MaxEnt RI. can be used to solve a certain class of POMDPs, and (2) that MaxEnt RL is equivalent reward function. These results suggest deeper connection between MaxEnt RL, robust control, and POMDPs, and provide insight for the types of problems for which we might expect MaxEnt RL to produce effective solutions. Specifically, our results suggest that domains with uncertainty the task goal may be especially well-suited for MaxEnt RL methods.
two-player game where an adversary chooses the
INTRODUCTION
Reinforcement learning (RL) searches for a policy that maximizes the expected, cumulative reward. In fully observed Markov decision processes (MDPs), this maximization always has a deterministic policy as a solution. Maximum entropy reinforcement learning (MaxEnt RI. is a modification of the RL objective that further adds an entropy term to the objective. This additional entropy term causes MaxEnt RL to seek policies that (I) are stochastic, and (2) have non zen-zero probability of sampling every action. MaxEnt RL. can equivalently be viewed as probability matching between trajectories visited by the policy and distribution defined by exponentiating the reward (See Section 2). MaxEnt RL has appealing connections to probabilistic inference (Dayan Hinton [997| Neumann et al. 2
Todorov | Kappen] 2005 Toussaint 2009 Rawlik et al. 2013]] Theodorou et | 20100 Ziebart
2010), prompting a renewed interest in recent years (Haarnjja al. 2018b; Abbollmall et al. 2018
Levine 2018). MaxEnt RL can also be viewed using Thompson sampling (Thompson 1933)
to collect trajectories, where the posterior belief is given by the exponentiated return. Empirically, MaxEnt RL algorithms achieve good performance
number of simulated (Haarnoja et al.. (018h)
and real-world (Haarnoja et al. 2018a Singh et al. 2019) control tasks, and can be more robust to perturbations (Haarnoja et al.) 2018c).
There is empirical evidence that behavior similar MaxEnt RL is used by animals in the natural world. While standard reinforcement learning is often used as a model for decision making (Scott) 2004 Liu & Todorov 2007 Todorov & Jordan 2002), many animals, including humans, do not consistently make decisions that maximize expected utility. Rather, they engage in probability matching, choosing actions with probability proportional to how much utility that action will provide. Examples include ants (Lamb & Ollason 1993). bees (Greggers & Menzel 1993). fish (Bitterman et al.) 1958), ducks (Harper 1982). pigeons (Bullock & Bittermann 1962, Graf et al., 1964), and humans, where it has been documented so extensively that Vulkan 2000) wrote a survey of surveys of the field. This effect has been observed not just in individuals, but also in the collective behavior of groups of animals (see Stephens Krebs (1966), where it is often described as obtaining the ideal free distribution. Probability matching is not merely reflection of youth ignorance. Empirically more intelligent creatures are more likely to engage in probability matching. For example, in a comparison of Yale students and rats, Gallistel (1990) found that the students nearly always performed probability

---

Under review as a conference paper at ICLR 2020
matching, while rats almost always chose the maximizing strategy. Similarly, older children and adults engage in probability matching more firquently than young children (Stevenson & Odom 1964 Weir 1964). While prior work has offered number of explanations of probability matching (Vulkan 2000 Gaissmaier & Schooler 2008 an open problem.
Wozny et al. 2010: Sakai & Fukai 2008), its root cause remains
The empirical success of MaxEnt RL algorithms on RL problems is surprising. as MaxEnt RL optimizes a different objective than standard RL. The solution every MaxEnt RL problem is stochastic, while deterministic policies can always be used to solve standard RL problems (Puterman 2014). While RL can be motivated from the axioms of utility theory (Russell & Norvig [0166]. MaxEnt RL has no such fundamental motivation. It remains an open question as to whether the standard MaxEnt RL. objective actually optimizes some well-defined notion of risk or regret that would account for its observed empirical benefits. This paper studies this problem, and aims to answer the following question: if MaxEnt RL is the solution, then what is the problem? Answering this question is first step towards understanding the empirical success of MaxEnt RL algorithms, and our analysis will suggest that MaxEnt RL might be applicable to problems typically considered to be much more complex than standard RL.
In this paper, we show that MaxEnt RL provides the optimal control solution in settings with uncertainty and variability in the reward function. More precisely, show that MaxEnt RL is equivalent to two more challenging problems: (1) regret minimization in a meta-POMDPP and (2) robust-reward control. The first setting, the meta-POMDP. is a partially observed MDP where the reward depends on an unobserved portion of the state, and where multiple episodes in the original MDP correspond to single extended trial in the meta-POMDP. While seemingly Byzantine, this type of problem setting arises in a number of real-world settings discussed in Section 3 Optimal policies for the meta-POMMP must explore at test-time, behavior that cannot result from maximizing expected utility. In the second setting, robust-reward control, we consider an adversary that chooses some aspects of the reward function. Intuitively, we expect stochastic policies to be most robust because they are harder to exploit, as we formalize in Section [] Even if the agent will eventually be deployed in setting without adversaries, the adversarial objective bounds the worst-case performance of that agent. Our result in this setting can be viewed as extension of prior work connecting the principle of maximum entropy to two-player games (Ziebart et al. 2011 Grünwald et al. 2004). While both robust-reward control and regret minimization in meta- POMDP are natural problems that arise in many real-world scenarios, neither is an expected utility maximization problem. so we cannot expected optimal control to solve these problems. In contrast, solutions to both. In summary, our analysis suggests that the empirical benefits of MaxEnt RL arise by implicitly solving control problems with variability in the reward.
show that MaxEnt RL provides
PRELIMINARIES
We begin by defining notation and discussing some previous motivations for MaxEnt RL. An agent observes states st, takes actions at ~ π (a, st), and obtains rewards r(st, at). The initial state is sampled 81 ~ PI (s1), and subsequent states are sampled s' p(s') s, a,)). Episodes have T steps, which we summarize as trajectory т e ($1,01," assume that rewards are undiscounted, as any discount can be addressed by modifying the dynamics to transition to an absorbing state with probability 1-7- The RL objective is:
88; UT). Without loss of generality, we can
Σ r(se, an)
T
] - { T
pi (( (
T II p(5 I st, (T) st)dr.
arg max Ex
In fully observed MDPs, there always exists a deterministic policy as a solution (Puterman, 2014). The MaxEnt RL problem, also known the mntropy-regulatiy control problem, is to maximize the sum of expected reward and conditional action entropy. H. [a s):
T Σ r(s a + HH s) = E Σ
T
arg max ET
r(se, (z) - log (a, st)
The MaxEnt RL objective results in policies that are stochastic, with higher-entropy action distribu- tions in states where many different actions lead to similarly optimal rewards, and lower-entropy
2

---

Under review as a conference paper at ICLR 2020
distributions in states where single action is much better than the rest. Moreover, MaxEnt RL results in policies that have non-zero probability of sampling any action. MaxEnt RL can equiva- lently be defined as a form of probability matching, minimizing reverse Kullback Leibler (KL) divergence (Rawlik et al. 2013):
T Σ r ar) + Hx(a| s] = min D pr))),
max 1E
-
where the policy distribution (T() and the target distribution (r((T) are defined
T
T
(r( x (1( p(s41 8r, ((raa)) Mena)))
*(7) _ pi II p(s |s, se, (() 8t)-
Prior work on MaxEnt RL offers slew of intuitive explanations for why one might prefer MaxEnt RL. We will summarize three common explanations and highlights problems with each.
Exploration: MaxEnt RL is often motivated performing good exploration. Unlike many other RL algorithms, such as DQN (Mnih et al., 2015) and DDPG (Liliicrap et al., 2013). MaxEnt RL performs exploration and policy improvement with the same (stochastic) policy. One problem with this motivation that stochastic policies can be obtained directly from standard RL, without adding an entropy term (Heess et al., 2015). More troubling, while MaxEnt RL learns stochastic policy, many MaxEnt RL papers evaluate the corresponding deterministic policy (Haarnoja et al., (018b)), suggesting that the stochastic policy is not what should be optimized. While improved exploration may be an ancillary benefit of MaxEnt RL, it remains unclear why we should expect MaxEnt RL to explore better than standard RL algorithms that learn stochastic policies.
Probabilistic inference: Connections with probabilistic inference offer second motivation for MaxEnt RL (Abdolmaleki et al. 20188] Haarnoja al.) 2018b Todorov 2007 Levine 2018 Toussaint 2009). These approaches cast optimal control as an inference problem by defining additional optimality binary random variables O₁ equal one with probability proportional to exponentiated reward. These methods then maximize the following log-likelihood:
T log (O,) = log pı (31) II MMo = 82, (5,0))p(544) | st ar)T((a st)dT
log / pi (i(s)ee Ei r(srae))
p(s141 se,, ac)T(a st)dT
T Er an)
log Ex
e r(sraa))
Ex,
Σ r(s ae)
+ Var,
(1)
The last term is cumulant generating function (i.e., the logarithm of a moment generating func- tion (Gut) 2013] Chpt. 6)), which can be approximated as the sum of expected reward and variance of returns (Mihatsch & Neuneier 2002). ) Thus, directly maximizing likelihood leads to risk-secking behavior, not optimal control. Equation T can also be directly obtained by considering an agent with risk-seeking utility function (O D'onoghue] 2018). While risk seeking behavior be avoided by maximizing a certain lower bound on Equation Levine 2018), artificially constraining algorithms to maximize a lower bound suggests that likelihood not what actually want maximize.
Easier optimization: Finally, some prior work (Ahmed et al., 2018 Williams & Peng 1991) argues that the entropy bonus added by MaxEnt RL makes the optimization landscape smoother. However, it does not suggest why optimizing the wrong but smooth problem yields a good solution to the original optimization problem.
WHAT PROBLEMS DOES MAXENT RL SOLVE?
MaxEnt RL produces stochastic policies, first discuss when stochastic policies may be optimal. Informally, the two strengths of stochastic policies are that they (1) are guaranteed to eventually try every action sequence and (2) do not always choose the same sequence of actions.
3

---

Under review as a conference paper at ICLR 2020
3.1 ANSWER 1: PARTIALLY OBSERVED ENVIRONMENTS
The first strength of stochastic policies guarantees that they will not have to wait infinitely long to find good outcome. Imagine that cookie is hidden in one of two jars. A policy that always chooses to look in the same jar (say, the left jar) may never find the cookie if it is hidden in the other jar (the right jar). Such a policy would incur infinite regret. This need to try various approaches arises in many realistic settings where we do not get to observe the true reward function, but rather have belief over what the true reward is. For example, in a health-care setting, consider the course of treatment for patient. The desired outcome is to cure the patient. However, whether the patient is cured by different courses of treatment depends on their illness, which is unknown. A physician will prescribe medications based on his beliefs about the patient's illness. If the medication fails, the patient returns to the physician the next week, and the physician recommends another medication. This process will continue until the patient is cured. The physician's ' aim is to minimize the number of times the patient returns. Another example is a robot that must perform chores in the home based on a user's commands. The true goal in this task is to satisfy the user. Their desires are never known with certainty, but must be inferred from the user's behavior. Indeed, arguably the majority of problems to which we might want apply reinforcement learning algorithms are actually problems where the true reward is unobserved, and the reward function that is provided to the agent represents an imperfect belief about the goal. In Section we define meta-level POMDP for describing these sorts of tasks and show that MaxEnt RL minimizes regret in such settings.
3.2 ANSWER 2: ROBUSTNESS TO EXPLOITATION
The second strength of stochastic policies is that they are harder to exploit. For example, in the game rock-paper-scissors ('ro-sham-bo"), it is bad to always choose the same action (say, rock) because an adversary can always choose an action that makes the player perform poorly (e.g.. by choosing paper). Indeed, the Nash existence theorem (Nash et al. 1950) requires stochastic policies guarantee that Nash equilibrium exists. In RL, we might likewise expect that a randomized policies are harder to exploit than deterministic policies. To formalize the intuition that MaxEnt policies are robust against adversaries, we define the robust-reward control problem.
Definition 3.1. The robust-reward control problem for set of reward functions R {rr} is
T Σ
r an)
arg max min r'ER
E
We can think of this optimization problem as a two-player, zero-sum game between a policy player and an adversarial reward player. The policy player chooses the sequence of actions in response to observations, while the reward player chooses the reward function against which the states and actions will be evaluated. This problem is slightly different from typical robust control (Zhou & Doyle 1998), as it considers perturbations to rewards, not dynamics. Typically, solving the robust-reward control problem is challenging because it is saddle-point problem. Nonetheless, in Section 5 show that MaxEnt RL is exactly equivalent to solving a robust-reward control problem.
3.3 SUMMARY
Together, these two properties suggest that stochastic policies, such as those learned with MaxEnt RL, can be robust to variability in the reward function. This variability may be caused by (1) a designer's uncertainty about what the right reward should be, (2) the presence of perturbations the reward (e.g., for an agent that interacts with human users, who might have different needs and wants in each interaction), or (3) partial observability (e.g., robot in a medical setting may not observe the true cause for a patient's 's illness). In this paper, we formally show that MaxEnt RL algorithms produce policies that are robust to two distinct sources of reward variability: unobserved rewards in partially observed Markov decision processes (POMDPs) and adversarial variation in the rewards.
4 MAXIMUM ENTROPY RL AND PARTIALLY OBSERVED ENVIRONMENTS
In this section, we formalize the intuition from Section 3 that stochastic policies are preferable in settings with unknown tasks. We first describe the problem of solving unknown task as a special
4

---

Under review as a conference paper at ICLR 2020
class of POMDPs, and then show that MaxEnt RL provides the optimal solution for these POMDPs. Our results in this section suggest a tight coupling between MaxEnt RL and regret minimization.
We begin by defining the meta- PeMa- Solving a task might mean reaching a particular goal state or performing a particular sequence of actions. We will use the most general definition of success simply matching some target trajectory, r" Crucially, the agent does not know which task it must solve (i.e., r" is not observed). Rather, the agent has access to a belief p(T) over what the target trajectory may be. This results POMDP. where the agent's ss ignorance of the true task makes the problem partial observed.
MDP with many possible tasks that could be solved.
Each meta-step of the meta-POMDP corresponds one episode of the original MDP. A meta-episode is a sequence of meta-steps, which ends when the agent solves the task in the original MDP. Intuitively, each meta-episode in the meta-POMDP corresponds multiple trials in the original MDP, where the task remains the same across trials. The agent keeps interacting with the MDP until it solves the task. While the Peta- might seem counter-intuitive it captures many practical scenarios. For example, in the health-care setting in Section 3 the physician does not know the patient's 's illness, and may not even know when the patient has been cured. Each meta-step corresponds to one visit to the physician, which might entail running some tests, performing an operation, and prescribing new medication. The meta-episode is the sequence of patient visits, which ends when the patient is cured. As another example, Appendix A.2 describes how meta-learning can also be viewed as meta-POMDP.
Before proceeding, we emphasize that defining the meta-POMMP in terms of trajectory distributions is strictly more general than defining it in terms of state distributions. However, Section 4.3 will discuss how goal-reaching. a common problem setting in current RL research (Lee et al. 2019b Warde-Farles et al. 2018 Pong et al.. 2019). can be viewed as a special case of this general formulation.
4.1 REGRET IN THE
The meta-POMDP has a simple reward function: +1 when the task is completed, and 0 otherwise. Since the optimal policy would solve the task immediately, its reward on every meta-step would be one. Therefore, the regret is given by 1 0 = for every meta-step when the agent fails to solve the task, and 1 regret of an agent is the expected number of meta-steps required to complete the task. For example, in the health-care example, the regret is the number of times the patient visits the physician before being cured.
for the (final) meta-step when the agent solves the task. Thus, the cumulative
Our analysis of the meta-POMIP will consider policies that are Markovian within a meta-episode: while the policy can be updated between meta-episodes, the policy cannot use information from one meta-step to take better actions a future meta-step within the same meta-episode. Our results will therefore be lower bounds on the performance of non-Mark non-Markovian policies. The Markovian assumption is equivalent to saying that agents lack memory, and might be seen as an instantiation of bounded rationality. That MaxEnt RL is optimal under this assumption suggests that the probability matching observed in nature is optimal under memory constraints.
Mathematically, use T(=") to denote the probability that policy æ produces target trajectory r". Then, the number of episodes until it matches trajectory T" is a geometric random variable with parameter π (7").. The expected value of this random variable is 1/ / (r"), so we can write the regret of the meta-POMDP as:
Regret, = Er-rop
Note that this regret is function of particular policy x(a s), evaluated over potentially infinitely many steps in the original MDP. A policy that never replicates the target trajectory incurs infinite regret. Thus, we expect that optimal policies for the meta-POMDP will be stochastic.
4.2 SOLVING THE
We solve the meta-POMDP by finding an optimal distribution over trajectories:
min Regret,,T)) s.t. f ((())d==1. - 1, T(r) > 0.
5

---

Under review as a conference paper at ICLR 2020
Using Lagrange multipliers (see Appendix A.1 find that the optimal policy is:
VP(T)
This policy is stochastic and matches the unnormalized distribution v pP(r) This result suggests that we can find the optimal policy by solving a MaxEnt RL problem, with a trajectory-level reward function r, (r) & loggpt p(T). To make this statement precise, we consider the bandit setting and MDP setting separately. If the underlying MDP is bandit, then trajectories
equivalent to actions. We can define a reward function as r(a) = 2 log p(a). Applying MaxEnt RL to this reward function yields the following policy, which is optimal for the meta- meta-POMDP: x(a) /pla). For MDPs with horizon lengths greater than one, we can make a similar statement:
Lemma 4.1. Let a goal trajectory distribution P(T) be given, and assume that there exists a policy π whose trajectory distribution is proportional to the square-root of the target distribution: T()) x v V.(T). Then there exists reward function r(s, a) such that the MaxEnt RL problem with r(s, a) and the meta-POMDP have the same solution(s).
Proof. Let म- be the solution to the meta- Peta-POMDD, so must satisfy x²( x /p(r). Thus, is the solution the MaxEnt RL problem with the trajectory- reward r(T) log
n E arg min E,
log log + H. s) = (T((T( 2
-V((T) P(T)) + (()) x vP(T) Vr.
The normalizing constant which is independent from n², is introduced to handle the fact that /p(T) does not integrate to one. The implication comes from the fact that the KL is minimized when its arguments are equal. We show in Appendix |..3 that trajectory-level reward r(T) can always be decomposed into an state-action reward r82,, dz) with the same MaxEnt RL solution. Thus, there exists a reward function such that MaxEnt RL solves the meta-POMDP:
π² arg min Ex
Σ r at)
H4
x (T( VP(T) VT.
The obvious criticism of the proof above is that it is not constructive, failing to specify how the MaxEnt RL reward might be obtained. Nonetheless, our analysis illustrates why MaxEnt RL methods might work well: regret in some meta- meta-POMDP. which could account for their good performance, particularly in the presence of uncertainty and perturbations.
when the meta-POMDP is unknown, MaxEnt RL methods will minimize
4.3 GOAL REACHING META-POMDPS
We make the connection between MaxEnt RL and meta-POMDPs more precise by considering a special class of meta-POMMDE meta-POMDPs where the target distribution defined only in terms of the last state in trajectory, corresponding to goal-reaching problems. While prior work goal-reaching (Kaelbling) [993] Schaul et al.) 2015 Andrychowicz et al. 2017)) assumes that the goal state is observed, the goal-reaching meta- PoMaa only assumes that the policy has a belief about the goal state.
Lemma 4.2. Let a meta-POMDr with target distribution that depends solely on the last state and action the trajectory be given. That is, the target distribution p(T) satisfies
ST (T) = ST(T') and aT(T) = =ar(r)) = p(T) p(r') Vr,
where ST(T) and (T( are functions that extract the last state and action in trajectory We can thus write the density of trajectory under the goal trajectory distribution as a function of the last state and action: p(7) p(sT(T (r(()), where p(sT, ((ST,aT) is an unnormalized density. Assume that there ex- ists a policy whose marginal state density at the last time step, pT (s, a). satisfies PI (s, a) x / V a) for all states s. Then the MaxEnt RL problem with reward r(se. a:) & 11(t = T) log p(s,, az) and the meta- PPMDP have the same solutions.

---

Under review as a conference paper at ICLR 2020
Proof. We simply combine Lemma 4.1 with the definition of the reward function
T Σ r(s ar) = Σ
T
1(t - logp(s; a²) = log p(sT, ST) = (r)
While our assumption that there exists policy that exactly matches some distribution (v p(ST. aT) may seem somewhat unnatural, we provide sufficient condition in Appendix [A.4] Further, while the analysis so far has considered the equivalence of MaxEnt RL and the meta-POMII Appendix AA.5 we bound the difference between these problems away from their optima. In summary, the meta- POMt- allows us to represent goal-reaching tasks with uncertainty in the true goal state. Moreover, solving these goal-reaching meta- Peta-POMDPs with MaxEnt RI. is straightforward, as the reward function for MaxEnt RL a simple function of the last transition.
optimum, in
4.4 COMPUTATIONAL EXPERIMENT
To conclude this section, we present simple computational experiment verify that Max- Ent RL does solve the meta-POMDP. We instantiated the meta-POMDP using 5-armed ban- dits. Each meta-POMDP
specified by a prior belief p(i) over the target arm. We sam- ple this distribution from a Dirichlet(I). To solve this meta-POMDP, we applied MaxEnt RL using reward function r(i) = log p(t), as derived above. When the agent pulls arm it observes noisy reward r; (r(i),, 1). To implement the MaxEnt RL approach, maintained the posterior of the reward r(t). given our observations far. We initialized our beliefss with zero-mean, unit-variance Gaussian prior. To obtain policy with MaxEnt RL, chose actions with probability proportional to the exponentiated expected reward. Through- out training, we tracked the regret (Eq. 1. Since the minimum regret possible for each meta-POMMP is different, normalized the regret for each meta-POMDP by dividing by the minimum possible regret. Thus, the nor- malized regret lies in the interval [1, oo). with lower being better. Figure shows that MaxEnt RL converges to the regret-minimizing policy for each neMa-POMMP. Code reproduce all experiments is available online
normalized regret
MaxFat RI
1.3
pulicy
1.2
1.1
1.0
0.9
10P
10 environment steps
10a
Figure 1: MaxEnt RL solves the Mcta-POMDP. On 5-armed bandit problem, we show that solving a MaxEnt RL problem with a reward of r(i) mizes regret on the meta- POMDP defined by p(i). The thick line is the average across 10 randomly-generatte bandit problems (thin lines). Lower hetter.
3 log p(i) mini-
MAXIMUM ENTROPY RL AND ADVERSARIAL GAMES
While the meta-POMDE considered in the previous setting was defined in terms of task uncertainty, that uncertainty was fixed throughout the learning process. We now consider uncertainty introduced by an adversary who perturbs the reward function, and show how MaxEnt RL's aversion to deterministic policies provides robustness against these sorts of adversaries. In particular, we show MaxFnt RI. equivalent to solving robust-reward control, and computational experiment support claims. We generalize these results in Appendix B
5.1 MAXENT RL SOLVES ROBUST-REWARD CONTROL
Our main result on reward robustness builds on the general equivalence between entropy maximization and game theory from prior work. To start, note two results from prior work that show how entropy maxinization can be written as a robust optimization problem:
Lemma 5.1 (Grünwaldd et al. (2004)), Let & be random variable, and let P be the set of all distributions over æ. The problem of choosing maximum entropy distribution for and maximizing the worst-case log-loss are equivalent:
max H. Hgpp]] PEP
max min Epl- log q(z)). pEP PEP
'Code: /tttp::://rrive.g.oollee http://coogo......oe////////////
7

---

Under review as a conference paper at ICLR 2020
robust control
MaxEnt control
reward rroy
4.0
3.5
robust set,
3.5
3.5
3.0
original reward,
3.0
3.0
2.5
2.5
2.5
2.0
2.0
1.5
1.0
1.0
0.5
1.0
0.0
0.0
2.0
2.5
3.0
3.5
4.0
4.5
5.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
r'(c
1)
TTa = 1)
π (a
= 1)
Figure 2: MaxEnt RL Robust-Rewarts Control: The policy obtained by running MaxEnt RL on reward function r the optimal robust policy for a collection of rewards, Ry. (Left) We plot the original reward function, red dot, and the collection of reward functions, R, as blue line. (Center) For each policy, parameterized solely by its probability of choosing action I, we plot the expected reward for each reward function in R.. The robust-reward control problem to choose the policy whose worst-case reward (dark blue line) is largest. (Righr) For cach policy, we plot the MaxEnt RL objective (i.c., the sum of expected reward and entropy).
An immediately corollary is that maximizing the entropy of any conditional distribution is equivalent to robust optimization problem:
Corollary 5.1.1 (Grünwald et al. (2004); Ziebart al. (2011)) Let æ and y be random variables, and let Paly be the set of all conditional distributions p( y). The problem of choosing maximum
entropy distribution for the conditional distribution p(æ: y) and maximizing the worst-case log-loss of given y are equivalent:
max By [Hp[ vl] PEP=ly
max min By [Ep log q(ar [y]]
pEP qEP=/o
In short, prior work shows that the principle of maximum entropy results minimizes worst-case performance on prediction problems that use log-loss. Our contribution extends this result to show that MaxEnt RL minimizes worst-case performance on reinforcement learning problems for certain classes of reward functions.
Theorem 5.2. The MaxEnt RL objective for a reward function r is equivalent to the robust-reward control objective for certain class of reward functions:
E
rss a4) + Hrraa|
min E, rER,
Σ r()
where
R, = fr' r(s, - loog a(a 8) 1 II).
For completeness, we provide proof in Appendix B. We will call the set R, of reward functions robust set. While the adversary in Theorem 5.2 may seem peculiar, this result can also be viewed as providing a lower bound on worst-case performance against unknown reward function. As an aside, we note that the log g(a s) term in the definition of the robust set arises from the fact that we consider MaxEnt RL algorithms using Shannon entropy. MaxEnt RL algorithms using other notions of entropy (Lee et al.) [019a] Chow et al. 2018) would result in different robust sets (see Grünwald let al. 2004)). We leave this generalization for future work.
5.2
A SIMPLE EXAMPLE
In Figure
2
we consider simple, 2-armed bandit, with the following reward function:
2 a=1
r(a)
1 a=2
The robust set then defined as
R
((())
2 log ((a)
= a 2
g (0,
11 log(1 (()))
Figure 2 (left) traces the original reward function and this robust set. Plotting the robust-reward control objective (center) and the MaxEnt RI. objective (right), we observe that they equivalent.
8

---

Under review as a conference paper at ICLR 2020
5.3 A COMPUTATIONAL EXPERIMENT
We ran an experiment to support our claim that MaxEnt RL is equivalent to solving the robust- reward problem. The mean for arm i, 14, is drawn from a zero-mean, unit-variance Gaus- sian distribution, 14; ~ (0, 1). When the agent pulled arm i, it observes a noisy reward Nu, 1). We implement the MaxEnt RL approaches as in Section 4.4 As a baseline, we compare fictitious play (Brown 195I), an al- gorithm for solving two-player, zero-sum games, Fictitious play alternates between choosing the best policy w.r.t. the historical average of ob- serves rewards, and choosing the worst reward function for the historical average of policies. We choose the worst reward function from the robust set (Eq. D) For fair comparison, the pol- icy only observes the (noisy) reward associated with the selected arm. We also compared to oracle version of fictitious play that observes the (noisy) rewards associated with all arms, including arms not selected. We ran each method on the same set of 10 bandit problems, and evaluated the worst-case reward for each method (i.c., the expected reward of the policy, if the reward function were adversarially chosen from the robust set). Because each problem had different minimax reward, normalized the worst-case reward by the worst-case reward of the optimal policy. The normalized rewards are therefore in the interval [0, 1]. with being optimal. Figure plots the normalized reward throughout training. The main result is that MaxEnt RL converges to a policy that achieves optimal minimax reward, supporting our claim that MaxEnt RL is equivalent to a robust-reward control problem. The failure of fictitious play to solve this problem illustrates that the robust-reward control problem is not trivial to solve. Only the oracle version of fictitious play, which makes assumptions not made by MaxEnt RI,, is competitive with MaxEnt RI. In Appendix C we run similar experiment on four robotic control tasks and find that MaxEnt RL optimizes the minimax reward better than standard RL and fictitious play.
normalized minimax reward
1.0
0.9
0.8-
MadEn;
0.7
RicltousPayy
0.6
Drocl Fictoosstay
optimal policy
0.5
10'
10
10'
10*
environment steps
Figure 3: MaxEnt RL solves a robust-reward con- trol problem. On a 5 5-armed bandit problem, MaxEnt RL converges to the optimal minimax policy. Fictitious play, prior method for solving adversarial problems, fails to solve this task, but an oracle variant achieves re- ward similar to MaxEnt RL. The thick line is the average over 10 random seeds (thin lines). Higher is better.
DISCUSSION
In summary, this paper studies connections between MaxEnt RL and control problems with variability in the reward function. While MaxEnt RL is relatively simple algorithm, the problems that it solves, such as robust-reward control and regret minimization in the meta- Pota- are typically viewed as quite complex. This result hints that MaxEnt RL might also be used solve even broader classes of control problems. The principle of maximum entropy has also been applied to inverse RI., and we encourage future work consider whether MaxEnt IRL. (Ziebart et al., 2008) is implicitly robust to some sort of variability. Finally, we speculate that our results may help understand behavior in the natural world. The abundance of evidence for probability matching in nature suggests that, in the course of evolution, creatures that better handled uncertainty and avoided adversaries were more likely to survive. We encourage RL researchers likewise focus their research on problem settings likely to occur in the real world.
REFERENCES
Abbas Abdolmaleki, Jost Tobias Springenberg. Yuval Tassa, Remi Munos, Nicolas Heess, and Martin Riedmiller. Maximum a posteriori policy optimisation. arXiv preprint arXiv:/806.06990 2018
Zafarali Ahmed, Nicolas Le Roux, Mohammad Norouzi, and Dale Schuurmans. Understanding the impact of entropy in policy learning. arXiv preprint 181 2018.
Marcin Andrychowicz. Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tohin, OpenAl Pieter Abbeel, and Wojeiech Zaremha. Hindsight experience replay. In Advances in Neural Information Processing Systems, pp. 5048-5058, 2017.

---

Under review as a conference paper at ICLR 2020
ME Bitterman, Jerome Wodinsky. and Douglas K Candland. Some comparative psychology. The American Journal of Psychology, 71(1):94-110, 1958.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech 7aremba. Openai gym. arXiv preprint arXiv:/606.01 540, 2016.
George W Brown. Iterative solution of games by fictitious play. Activity analysis of production and allocation, 13(():374-376, 1951.
Donald H Bullock and ME Bitterman. Probability-matchingg in the pigeon. The American Journal of Psychology, 75(4):634-639, 1962.
Yinlam Chow, Ofir Nachum, and Mohammad Ghavamzadeh. Path consistency learning in tsallis entropy regularized mdps. In International Conference on Machine Learning, pp. 978 987,9087 2018.
Peter Dayan and Geoffrey E Hinton. Using expectation-maximizaiii for reinforcement learning. Neural Computation, 9(2)2711-27,, 1997.
Roy Fox. Ari Pakman, and Naftali Tishby. Taming the noise in reinforcement learning via soft updates. arXiv preprint 1r1iv::512.08888 2015.
Wolfgang Gaissmaier and Lael J Schooler. The smart potential behind probability matching, Cognition, 109(3): 416 422, 2008.
Charles R Gallistel. The organization of learning. The MIT Press, 1990.
Virgil Graf, DH Bullock, and ME. Bitterman. Further experiments on prohabilit--matching the pigeon 1. Journal of the Experimental analysis of Behavior, 7(2):151-157, 1964.
Uwe Greggers and Randolf Menzel. Memory dynamics and foraging strategies honeybees. Behavioral Ecology and Sociobiology, 32(1):17-29, 1993.
Peter D Grünwald, A Philip Dawid, et al. Game theory, maximum entropy, minimum discrepancy and robust bayesian decision theory. the Anmals of Statistics, 3374)133,,,,,,,, 2004.
Sergio Guadarrama, Anoop Korattikara, Oscar Ramirez, Pablo Castro, Ethan Holly, Sam Fishman, Ke Wang, Ekaterina Gonina, Chris Harris, Vincent Vanhoucke, et al. Ti-agents: A library for reinforcement learning in tensorflow, 2018. URL https:: gi huub...bb....... com wwt.///ttt.....ecc wtt.s//ensoooooo Low wwwp://ggtttsso
Allan Gut. Probability: a graduate course, volume 75. Springer Science & Business Media, 2013.
Tuomas Haarnoja, Vitchyr Pong, Aurick Zhou, Murtaza Dalal, Pieter Abbeel, and Sergey Levine. Composable deep reinforcement learning for robotic manipulation. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 6244-6251. IEEE, 2018a.
Tuomas Haarnoja, Aurick Zhou, Pieter Abheel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. arXiv preprint arXiv: 1801.01200, 2018b.
Tuomas Haarnoja, Aurick Zhou, Sehoon Ha, Tan, George Tucker, and Sergey Levine. Learning to walk via deep reinforcement learning. arXiv preprint arXiv: 1812.1100. 2018c.
DGC Harper.
Competitive foraging mallards: "ideal free" ducks. Animal Behaviour, 30(2):575-584, 1982.
Nicolas Heess, Gregory Wayne, David Silver, Timothy Lillicrap, Tom Erez, and Yuval Tassa. Learning continuous control policies by stochastic value gradients. In Advances Neural Information Processing Systems, pp. 2p..9444-222 2944-2952, 2015.
Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry. Adversarial examples are not bugs, they are features. arXiv preprint
2019.
Leslie Pack Kaelbling. Learning to achieve goals. IJCAI, pp. 1094-1099. Citeseer, 1993.
Hilbert Kappen. Path integrals and symmetry breaking for optimal control theory. Journal of statistical mechanics: theory and experiment, 2005(11):P11011 2005.
AE Lamb and IG Ollason. Foraging wood-ants formica aquilonia yarrow (hymenoptera: Formicidae) tend to adopt the ideal free distribution. Behavioural processes, 28(3):189-198, 1993.
Kyungjae Lee, Sungyub Kim, Sunghin Lim, Sungjoon Choi, and Songhwai Oh. Tsallis reinforcement learning: A unified framework for maximum entropy reinforcement learning. arXiv preprint arXiv: wwXiv:9902..00 990.000137 2019a.
10

---

Under review as a conference paper at ICLR 2020
Lisa Lee. Benjamin Eysenbach, Emilio Parisotto, Eric Xing, Sergey Levine, and Ruslan Salakhutdinov. Efficient exploration via marginal matching. arXiv preprint 1xXiv:9006.5522 2019b.
Sergey Levine. Reinforcement learning and control as probabilistic inference: Tutorial and review. arXiv preprint arXiv:/805.00009 2018.
Timothy P Lillicrap. Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint (eXi::5599009771 2015.
Dan Liu and Emanuel Todorov. Evidence for the flexible sensorimotor strategies predicted by optimal feedback control. Journal Neuroscience, 27(35):9354 9368, 2007.
Oliver Mihatsch and Ralph Neuncier. Risk-sensitive reinforcement learning, Machine learning, 49(2-3):267-290, 2002.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015.
Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans. Bridging the gap between value and policy based reinforeement learning In Advances in Neural Information Processing Systems, 2775 2785, 2017.
John F Nash et al. Equilibrium points in n-person games. Proceedings of the national academy of sciences, 36 (1):48-49, 1950.
Gerhard Neumann et al. Variational inference for policy search in changing situations. In Proceedings of the 28th International Conference on Machine Learning, ICML. 2011, pp. 817-824, 2011.
Mohammad Norouzi, Samy Bengio, Navdeep Jaitly, Mike Schuster. Yonghui Wu, Dale Schuurmans, et Reward augmented maximum likelihood for neural structured prediction. In Advances In Neural Information Processing Systems, pp. 1723-1731, 2016.
Brendan O'Donoguue. Variational bayesian reinforcement learning with regret bounds. arXiv preprint arXiv: arXiv:1807.000 (0.7 09647, 2018.
Lerrel Pinto. James Davidson, Rahul Sukthankar, and Abhinay Gupta. Robust adversarial reinforcement learning. In Proceedings the 34th International Conference on Machine Learning- Volume 70, pp. 2817-2826. JMLR. org, 2017.
Vitchyr H Pong. Murtaza Dalal, Steven Lin, Ashvin Nair, Shikhar Bahl, Sergey Levine. Skew-fit: State- covering self supervieed reinforcement learning. arXiv preprint arXiv:1903.03692 2019.
Martin L Puterman. Markov Decision Processes.: Discrete Stochastic Dynamic Programming. John Wiley Sons, 2014.
Konrad Rawlik, Mare Toussaint, and Sethu Vijayakumar. On stochastic optimal control and reinforcement learning by approximate inference. In Twenty- Third International Joint Conference Artificial Intelligence, 2013.
Stuart J Russell and Peter Norvig. Artificial intelligence: modern approach. Malaysia: Pearson Education Limited,, 2016.
Yutaka Sakai and Tomoki Fukai. The actor-critic learning hehind the matching law: Matching versus optimal behaviors. Neural Computation, 2011):227-,51, 2008.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. In International Conference on Machine Learning, pp. 1312-1320, 2015.
Stephen H Scott. Optimal feedback control and the neural basis of volitional motor control. Nature Reviews Neuroscience, 5(7):532, 2004.
Slavko Simie. On an upper bound for jensen's incquality. Journal of Inequalities in Pure and Applied Mathematics, 10(2):5, 2009.
Avi Singh, Larry Yang, Kristian Hartikainen, Chelsea Finn, and Sergey Levine. End-to-end robotic reinforcement learning without reward engineering. arXiv preprint arXiv: 1904.07854, 2019.
11

---

Under review as a conference paper at ICLR 2020
David W Stephens and John R Krebs. Foraging theory. Princetoon University Press, 1986.
Harold W Stevenson and Richard D Odom. Children's behavior in a probabilistic situation. Journal of experimental psychology, 68(3):260. 1964.
Evangelos Theodorou, Jonas Buchli, and Stefan Schaal. generalized path integral control approach to reinforcement learning. journal of machine learning research, 11(Nov):3137-3188 2010.
William Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285 294, 1933.
Sebastian Thrun and Lorien Pratt. Leurning to learn. Springer Science & Business Media, 2012.
Emanuel Todorov. Linearly-solvable markov decision problems. Advances in neural information procesiing systems, pp. 1369-1376, 2007.
Emanuel Todorov and Michael I Jordan. Optimal feedback control theory of motor coordination. Nature neuroscience, 5(1 (11):11 1226, 2002.
Marc Toussaint. Robot trajectory optimization using approximate inference. In Proceedings of the 26th annual international conference on machine learning, pp. 1049-1056. ACM, 2009.
Nir Vulkan. An cconomist's perspective on probability matching. Journal of economic surveys, 14(1):101-118, 2000.
David Warde-Farley, Tom Van Wiele, Tejas Kulkarni, Catalin lonescu, Steven Hansen, and Volodymyr Mnih. Unsupervised control through non-parametric discriminative rewards. arXiv preprint arXiv: 1311,119, 2018.
Morton W Weir. Developmental changes prohlem-solving strategies. Psychological review, 71(6):473, 1964.
Ronald J Williams and Jing Peng. Function optimization using connectionist reinforcement learning algorithms. Connection Science, 3(3)2411-268, 1991.
David R Wozny, Ulrik R Beierholm, and Ladan Shams. Probability matching as computational stratogy used in perception. PLoS computational biology, 1000871, 2010.
Kemin Zhou and John Comstock Doyle. Essentials of robust control, volume 104, Prentice Upper Saddle River, NJ, 1998.
Brian Ziehart. Modeling purposeful adaptive behavior with the principle of maximum causal entropy. 2010.
Brian D Ziebart, Andrew Maas, J Andrew Bagnell, and Anind K Dey. Maximum entropy inverse reinforcement
learning. 2008.
Brian Ziebart, J Andrew Bagnell, and Anind K Dey. Maximum causal entropy correlated equilibria for markov games. In The 10th International Conference on Autonomous Agents and Multiagent Systems- Volume 1, pp. 207-214, International Foundation for Autonomous Agents and Multiagent Systems, 201 1.
A META-POMDP
A. 1 SOLVING FOR THE OPTIMAL TRAJECTORY DISTRIBUTION
We will solve the optimization problem introduced in Section 4.2 using the constrained Euler- Lagrangian method. The Lagrangian is
L(T, A) / p(()) dr +
(f ((T))r-1)
(T())
The first and second derivatives of the Lagrangian are:
dC
p(T)
dC d=
- P(T) T(7)3
> 0.
(m(
Note that the second derivative positive so setting the first derivative equal to zero will provide minimum of the objective:
dL
= = T(T) -xp(T).
dπ(T)
12

---

Under review as a conference paper at ICLR 2020
We then solve for À using the constraint that x(() integrate to one, yielding the solution to the optimization problem:
x(r) = VP(T)
J (VD(T)d
A.2 THE META-POMDP AS (MEMORYLESS) META-LEARNING
The neta-POMDP can be viewed as a meta-learning problem (Thrun Pratt 2012). solved with memoryless meta-learner. Formally, meta-learning algorithm is distribution over policies given the observed data, D: p( D). We will consider memoryless meta-learning algorithms:: the distribution of policies proposed at each step is the same, the meta-learner cannot update its beliefs based on observed evidence: p(ι 'D) = p(T). We define a meta-learning problem MDPs, p(M). unknown MDP M will be sampled, and the job of the
by distribution meta-learning algorithm is to solve M as quickly as possible. Solving an MDP can mean a number of different things: reaching goal state, achieving certain level of reward, avoiding episode termination. For simplicity, we assume that each MDP has a single successful policy, and each policy successful for single MDP, though this analysis can likely be extended more general notions of success. We will define т; as the unique policy that solves MDP MM, Note that, in this setting, the regret of the meta-POMDI the (unknown) MDP. Lemma tells us that the optimal (memoryless) meta-learning algorithm is defined as ((T)) Vp(M:).
exactly the number of episodes required find the optimal policy for
While the assumption that the meta-learning algorithm is independent observed data is admittedly strong, it is realistic in settings where failing one task provides no information about that the true task might be. Broadly, we believe that the meta-POMDP is a first step towards understanding if and how MaxEnt RL might be used to solve problems typically approached meta-learning problems.
A.3 WHEN CAN TRAJECTORY-LEVHI REWARDS DECOMPOSED?
Lemma A.1. Let trajectory-level reward function v (T( be given, and define the corresponding target distribution as
T p(8441 |8,,
Pr. (T) x (((
II
If there exists a Markovian policy æ such that (()) = Pr. (T) for all trajectories т, then there exists a state-action level reward function r(s.a) satisfying
r+(T) Σ a()
Vr,
Proof. To start, we recall the definitions of TTT) and pr, (T):
T
((7) x (s1)
II p(s I st, a1)a st)
(3)
Pr. (7) x pp
p(st41 I at)
(4)
13

---

Under review as a conference paper at ICLR 2020
By assumption that (T)) Pr, (T), we know that Equations 3 and equal, up to some proportionality constant d':
T
pi(s))e*+(r)
plac+1 8t, (z) - ddp II plac+1 I 88, (() sc)
T
(i((s)) o'
(g +r log (ocl())))) II
p(sc+1 18,, az)
t=1
(1()) ((s
p(s st, sc,
where r(8,a) - logm(a Taa 8) + loge'.
A.4 WHEN DOES SOLUTION EXIST?
When considering goal-reaching meta meta-POMDDS we made an assumption that there exists policy that exactly matches some distribution (vp (((sr,ar) aT)). Here, we provide sufficient (but not necessary) condition for the existence of such policy
Lemma A.2. Let P(T) = p(ST. ar) ) be some distribution over trajectories that depends only on the last state and action in each trajectory (as in Lemma If. for every state sT and action aT where Pl ST. aT) > 0, there exists policy Exy.ay that deterministically reaches state and action on the final time step, then there exists a Markovian policy satisfying (()) p(T).
The main idea behind the proof is that, if there exists policies that reach each of the possible target state-action pairs, then there exists way of "mixing" these policies to obtain policy with the desired marginal distribution.
Proof. First, we construct mixture policy मे by sampling ST, or g(sT.ar) at the start of each episode, and using policy Tzz.er for every step in that episode. By construction, we have P= (8T, aT) = q(8T: ar). However, this policy is non-Markovian. Nonetheless, [Ziebart (2010) Theorem 2.8) guarantees that there exists Markovian policy ă with the same marginal state distribution: #(ST,ar) = a(sT,aT). Thus, there exists a Markovian policy, satisfying 7 (sr,ar) q(sr,ar).
A.5 BOUNDING THE DIFFERENCE BETWEEN MAXENT RI. AND THE META-POMDP
While the result in Section 4 shows that MaxEnt RL has the same solution as the Pcta-POMDP, does not tells how the two control problems differ away from their optima. The following theorem provides an answer.
Theorem A.3. Assume that the ratio p(T)/m(T) is bounded in (a, b) for all trajectories' and b > 0. Further, assume that there exists a policy ny that can solve the MaxEnt RL problem exactly (i.e., upper bound the log regret of the POMD- plus an additional term that vanishes as π - Pr:
(T) (. Then the MaxEnt RL objective minimizes
[ pr) log Regret,3 C(T,T).
Before proving this theorem, note that the assumption that the MaxEnt RL problem can be solved exactly is always satisfied for linearly-solveabll MDPs (Todorov] 2007). Moreover, given a MDP that cannot be solved exactly, such that the optimal policy remains the same, but such that the optimal policy now exactly matches the target distribution. The proof of the theorem will consist of two steps. First, we will bound the difference between the log regret of the meta-POMDP and a forward KL. The second step is to bound the difference between that forward KL and the reverse KL (which is optimized by MaxEnt RL).
always modify the reward function (i.e., the target distribution p(r))
Proof. To start, we apply "backwards" version of Jensen's 's inequality from Simic 2009 Theorem 1.1), which states that the following inequality holds for any convex function f(x):
I |DTT)(E.))r f p(T)) dr - (6- (b)
14

---

Under review as a conference paper at ICLR 2020
We use log(x)) as our convex function, whose derivative is =1 and further define I, ((F)/
- -f p(() log
x(T) dr log /
p((T)
(T(T)
1 (b a)(1/a- 1/b)-
dr -
x(T) 4
Rearranging terms, we get
log / (T) (())
dr / p()))og log
p(T) x(T)
dr 7 a)(a/a)))aa) 1/b).
(5)
The LHS is not quite log regret (Eq. 4.1 because it contains p²²(r) term in the numerator, which not a proper probability distribution. Defining Z = (T) as the normalizing constant (which does not depend on T), we write the log regret using proper distribution:
r²(T) dr = log / (²(T)
log Regret 4.2 (T) log
dr log Z
ZT((T)
T(T)
We now rewrite Equation 5 as bound log regret:
((T)
log Regret y (T) - p(T) log
dr + 7 (00aa)(1a--1//// + log Z.
(6)
((T)
Notice that the integral the RHS is the forward KL between p and πT, whereas MaxEnt RL minimizes the reverse KL. Our next step is to show that the forward KL is not too much larger than the reverse KL, so optimizing the reverse KL (as done by MaxEnt RL) will still minimize an upper bound on the log regret of the meta-POMDP. We will do this using result Norouzi et al. (2016). First, we need to define the logits corresponding to distributions π and p. We start by defining the logits for just the dynamics:
T
(a(T) A log (1 + log p(ger( 8t, az)-
Now, the policy distribution क (T) and the target distribution, p(T), can both be written in terms of dynamics and policy:
T
(rg)(r)= +
log ग. (aa (t))
logp(T) = la(T) +
Σ
log क. (ax |x);
1=1
where xp is the optimal MaxEnt RL policy for the reward r(r) = log p(T). By our assumption that
there exists some x such that T(T) = p(T), we know that (T) = p(T). With this notation in place, we can employ Proposition 2 of Norouzi et al. (2016):
(pL(p(T) (()) & (x) P(T)) + ((p(T))(e -
2 Σ log (a; st)
(=a(((T) lI Σ
Σ log 7H (at se)
(7)
Note that the dynamics logits la cancelled with one another. Now, we combine Equations 6 and 7 to obtain:
log Regret, (T) (TT) < (T(() p[)) +C(T,r)
(8)
Z
where
T
T
2
C(T,T)
Σ log Tp (ar (
Σ
log π (a, si)
1 + (b-aa)(//-11)) 1/b).
As - Th difference of log probabilities (term 1) vanishes. Additionally, the ratio (TT)/T(T) -+ 1, so we can take and b (the limits on the probability ratio) towards 1. As - and b + 1, the second term in C(T, r) vanishes as well.
In summary, the difference between the MaxEnt RL objective and the log regret of the POMD- controlled by a term C(T, r). At the solution to the MaxEnt RL problem. this term is zero, implying that solving the MaxEnt RI. problem will minimize regret the meta-POMDP.
15

---

Under review as a conference paper at ICLR 2020
B
MAXIMUM ENTROPY RL AND ADVERSARIAL GAMES
B.1
PROOF AND EXTENSIONS OF THEOREM
Our proof Theorem 5.2
consists of first applying Corollary 5.1.1 and then rearranging terms.
Proof.
T
T
T
max ET TEll
Σ r(s,, at) + +H=la
max , Tell
Σ
r r(sts az)
+ min E gell
Σ
log a(a | (
max min Em welf gelf
(r(se, - -log q(ai st))
(st, an)
max min En welt r'ER,
corollary of this result is that the solution to the MaxEnt RL objective is robust. More precisely, the MaxEnt objective obtained by some policy is lower bound that policy's 's reward for any reward function in some set.
Let policy x and reward function r be given, and let be the MaxEnt objective policy π. reward function r:
Corollary B.0.1.
T r(s an) + Ho s).
J(T.)) En
Σ
Then the expected return of policy n on any reward function Ry least J:
E
Σ (s))
2 {(T,T) Vr R.
B.2 INTUITION FOR ROBUST SETS
We gain intuition for the robust set by explicitly writing out the definition of II:
II A a(s,a) E 10 Vs,a and /, g(a s)da As
log (oga(s,0) a) E [-00, 0] Vs, and / clanoials) 8A
Now, we can rewrite our definition of R, follows:
R, a(s, + (a) (a) 2 0 Vs, and / e e-ms(a) = Vs
(9)
r'(s, a) (s, 2 0 Vs, a and
(((saa) = 1 Vs
Intuitively, we are robust to all reward functions obtained by adding (positive) additional reward to the original reward, with the only constraints being that (1) the reward function is increased enough, and (2) significantly increasing the reward for one state-action pair limits the amount can be increased for another state-action pair. One important caveat of the results this section is that, individually, the reward functions in in the robust set R, are "easier" than the original reward function, in that they assign larger values the reward at given state and action:
reward
r(s, a) & (s) Vs S, a E A,r' E R Appendix B.4 discusses the role of temperatures the robustness of MaxEnt RI..
16

---

Under review as a conference paper at ICLR 2020
HUNNWWS 4.0
raa= 2)
1000 10000
original reward,
robust set, R,
expanded robust set, R,*
2.0
2.5
3.0
3.5
4.0
4.5
5.0
r' (a
= (a=1)
Figure 4: Expanded Robust Set: MaxEnt RL is robust to the reward functions along the blue line, which implies that it is also robust to the reward functions in the shaded region.
B.3 EQUIVALENCE CLASSES OF ROBUST REWARD CONTROL PROBLEMS
In this section, we aim understand whether the policy obtained by running MaxEnt RL on reward function is robust to reward functions besides those in Rg. As first step, we show that the policy also robust to reward functions that are "easier" than those in R,. We then show that the set R, not unique and introduce family of equivalent robust-reward control problems, all of which are equivalent to the original MaxEnt RL problem.
B.3.1 ROBUSTNESS TO DOMINATED REWARD FUNCTIONS
In Theorem 5.2 we showed that the optimal MaxEnt RL policy is also the minimax policy for the reward functions in Rg A somewhat trivial corollary is that also robust to any reward function that is pointwise weakly better than reward function in our robust set:
Lemma B.1. The MaxEni RL objective for reward function is equivalent to the robust-reward control objective for a class of reward functions, R² 2 R
T
E
r r(s 0z)
+ Hzlaa
min E rER.
Σ r() 1=1
1=1
where
R7 2 (r(a))
R,J.
Proof. To prove this, we simply note that these additional reward functions, r+ E R \ R,, will never be chosen as the arg min of the RHS. Thus, expanding the constraint set from R2 to R does not change the value of the RHS.
This constrained says that we are robust to reward functioned that are bounded away from the original reward function. We plot the expanded robust set, R in Figure 4 Note that the expanded robust set corresponds to all reward functions "above" and to the "right" of our original robust set. We can use this result write a new definition for the robust set. Since now know that u can be made arbitrarily small, we can allow e (m) to take very small values. More precisely, whereas before we were constrained to add a term that integrated to one, we now are allows add any term whose integral is at at most one:
ux(a) Rt (rlo.a) {r(s,a)+us(o) (a(a) +
Vs, a and / e e-ul(a) da 5 VA
B.3.2 GLOBAL AFFINE TRANSFORMATIONS
In optimal control, modifying a reward function by adding global constant or scaling all reward by positive constant does not change the optimal policy. Thus, the robust-rewant control problem for set of rewards R, has the same solution as the robust-reward control problem for a scaled and shifted set of rewards:
17

---

Under review as a conference paper at ICLR 2020
b r 5 a
r(s, a
+c
8
0
c= 2.0
0.5
=1.
6
2
I1
b 1.0
== 0.0
4
1.5
4
1.0
b 2.0
2.0
0
0
8
0
2
4
6
r' (a==1)
r' ra=11)
Figure 5: Global Affine Transformations: In simple, 2-armed bandit, we draw reward function (turquoise dot) an its robust set (turquoise, thick line). The policy that is minimax for the reward functions in the robust set. The policy also minimax for other robust sets, obtained by (Left) scaling and (Right) shifting the original robust set. Importantly, the policy is not simultaneously robust against the union of these robust sets.
Lemma B.2. Let a set of reward functions Ry be given, and let b, c. E R, 0 be arbitrary constants. Then the following optimization problems are equivalent:
Σ r' (s an)
Σ r (sts ax)
arg max min ET E'R
arg max
min r'Ebit+
E
Proof. The proof follows simply by linearity of expectation, and the invariance of the argmax positive affine transformations:
T
T
arg max r'Ebit,
min
r (st, at)
= arg max min E x e't,
br (br ar) +c)
(10)
to
arg max min Ex r',
r' (sc.
(11)
T
arg max min Em ER
Σ
r' as),
(12)
Note, however, that the robust-reward control problem for rewards R, is not the same being simultaneously robust to the union of all affine transformations of robust sets. Said another way, there exists a family of equivalent robust-reward control problems, each defined by fixed affine transformation of R,-
To gain some intuition for these transformations of reward functions, we apply variety of transfor- mations to the reward function from Figure 2 In Figure we show the effect of multiplying the reward by a positive constant. Figure 5 (right) shows the effect of adding constant the reward for every state and action.. For the robust sets in the right plot, there exists another reward function (rl + c) such that the shifted robust set equal to the robust set of the shifted reward (i.e.. R = R2 + c):
Lemma B.3. Let reward function and constant E R be given. Define reward function Te(s.a) & rrss a) + Let W, be the set of robust optimization problems which equivalent the MaxEnt RL problem on reward function r. The MaxEnt RL problem with the shifted reward function, To, is equivalent to the same set of robust optimization problems: W. Wr.
18

---

Under review as a conference paper at ICLR 2020
Q = 0.
a ==
Q a=
3.0
2.5
2.0
1.5
1.0
0.5
1
0.5
1.0
1.5
2.0
2.5
3.0
0.5
1.0
1.5
2.0
2.5
3.0
1)
r(a - 1)
Figure 6: Effect of Temperature: (Left) For given reward function (blue dot), we plot the robust sets for various values of the temperature. Somewhat surprisingly, it appears that increasing the temperature decreases the set of reward functions that MaxEnt is robust against. (Right) We examine the opposite: for given reward function, which other robust sets might contain this reward function. We observe that robust sets corresponding larger temperatures (i.e., the red curve) be simultaneously robust against more reward functions than robust sets at lower temperatures.
Proof. In addition to the argument given above, we can simply note that the two MaxEnt RI. problems the same:
I
Σ rolor, at)
Σ (())
const.
arg max E
Hz(aa
arg max Ex
Hzlaa + P.rot
Lemma B.3 true for the robust in the left plot. While the policy that is minimax for R2 is also minimax for blt,, there does not exist another reward function rl such that RG = bR, The reason that scaling the robust violates the constraint f eu (a) 1.
B.4 TEMPERATURES
Many algorithms for MaxEnt RL (Haarnoja et al., 2018b; Fox et al., 2015 Nachum et al. 2017) include temperature a to balance the reward and entropy terms:
J(T, E,
Σ r(ss + a7 s].
We can gain some intuition into effect this temperature on the set of reward functions to which are robust. In partieular, including temperature results in the following robust set:
r(s, a) + (a) (a) Z Vs, a and R.
(a) da S Vs
(13)
r(s a) + ua(a) (a) Vs, a and
(a)0 da S V
(14)
In the second line, we simply moved the temperature from the objective to the constraint by redefining (a(a) a (a).
We visualize the effect of the temperature in Figure 6 First, we fix a reward function and plot the robust set R for varying values of a. Figure o (left) shows the somewhat surprising result that increasing the temperature (i.e., putting more weight on the entropy term) makes the policy less robust. In fact, the robust set for higher temperatures is a strict subset the robust set for lower temperatures:
a1
< 02
- R R
This statement can be proven by simply noting that the function is increasing function of in Equation| 14] is important to recognize that being robust against more reward functions is not always desirable. In many cases, be robust everything, optimal policy must do nothing.
19

---

Under review as a conference paper at ICLR 2020
We now analyze the temperature in terms of the converse question: if a reward function r' is included in a robust set, what other reward functions are included in that robust set? To do this, we take a reward function r', and find robust sets R. that include r', for varying values of a. As shown in Figure O (right), if we must be robust to r' and use a high temperature, the only other reward functions which we robust those that similar, or pointwise weakly better, than r'. In contrast, when using a small temperature, we are robust against wide range of reward functions, including those that are highly dissimilar from our original reward function (i.e., have higher reward for some actions, lower reward for other actions). Intuitively, increasing the temperature allows us to simultaneously be robust larger set of reward functions.
B.5 MAXENT SOLVES ROBUST CONTROL FOR REWARDS
In Section 5 we showed that MaxEnt RL equivalent to some robust-reward problem. The aim of this section is to backwards: given set of reward functions, can we formulate MaxEnt RL problem such that the robust-reward problem and the MaxEnt RL problem have the same solution?
Theorem B.4. For any collection of reward functions R, there exists another reward function r such that the MaxEnt RL policy w.r.l. r is optimal robust-reward policy for R:
arg max E,T
Σ r()
+ Hrla
arg max min E, S
Σ (st at)
r'Elt
We containment, rather than equality, because there may be multiple solutions to the robust- reward control problem.
Proof. Let rr" be solution to the robust-reward control problem:
n E arg max min E, nER
Σ
re(Se, ut)
Define the MaxEnt RL reward function as follows:
r(s, a) = log ा (a |))
Substituting this reward function Equation 2 we see that the unique solution is π = T²"
Intuitively, this theorem states that we can use MaxEnt RL to solve any robust-reward control problem that requires robustness with respect any arbitrary set of rewards, if we can find the right corresponding reward function for MaxEnt RL. One way of viewing this theorem is as providing an avenue to sidestep the challenges of robust-reward optimization. Unfortunately, we will still have to perform robust optimization to learn this magical reward function, but at least the cost of robust optimization might be amortized. In some sense, this result similar to Ilyas et al. (2019).
B.6 FINDING THE ROBUST REWARD FUNCTION
In the previous section, we showed that policy robust against any set reward functions R can be obtained by solving MaxEnt RL. problem. However, this requires calculating reward function y* for Max Ent RI,, which not in general an element in R. In this section, we aim to find the MaxEnt reward function that results in the optimal policy for the robust-reward control problem. Our main idea is to find reward function r* such that its robust set, Ry., contains the set of reward functions want be robust against, R. That is, for each r E R, we want
/ e da < Vs.
(s(8, a) r" (8, ))+ (a) for some u, (a) satisfying
Replacing u with p' r", we see that the MaxEnt reward function must satisfy the following constraints:
[ e" (a.a)) da $1 S1 R.
20

---

Under review as a conference paper at ICLR 2020
We define R² (R) as the set of reward functions satisfying this constraint w.r. reward functions in R:
1 (R)
r" e" (s0))-)))))) da S V
Note that we can satisfy the constraint by making r" arbitrarily negative, so the set R (R) is non- empty. We now use 1ooollaryS...I]] to argue that all any applying MaxEnt RL to any reward function in r" E R (R) lower bounds the robust-reward control objective.
Corollary B.4.1. Let set of reward functions R be given, and let r* E (R) be an arbitrary reward function belonging the feasible set of MaxEnt reward functions. Then
Σ Csts ar)
JTT,r") S
min E MER
VT E II.
Note that this bound holds for all feasible reward functions and all policies, so it also holds for the maximum r":
max J(T, min E (R)
Σ r' (s., a.)
VT E II.
(15)
FE
Defining x² = arg max, [ r"), we get the following inequality:
(TT,T') 2 min E r'l
Σ
r'((s a+)
max min E, r'Elt
Σ
r'(
(16)
r' r'Elt (R)
Thus, we can find the tightest lower bound by finding the policy and feasibly reward r" that maximize Equation [6
max 15
BN
Σ r(( an)
+ Hx
(17)
(())))) SIASE R.
It is useful to note that the constraints are simply LOGSUMEXP functions, which are convex. For continuous action spaces, we might approximate the constraint via sampling. Given a particular policy, the optimization problem w.r.t. has a linear objective and convex constraint, so it can be solved extremely quickly using a convex optimization toolbox. Moreover, note that the problem can be solved independently for every state. The optimization problem is not necessarily convex in
B.7 ANOTHER COMPUTATIONAL EXPERIMENT
This section presents an experiment to study the approach outlined above. Of particular interest is whether the lower bound (Eq (6) comes close the the optimal minimax policy.
We will solve robust-reward control problems on 5-armed bandits, where the robust set is collection of 5 reward functions, each drawn from zero-mean, unit-variance Gaussian. For each reward function, we add a constant to all of the rewards to make them all positive. Doing so guarantees that the optimal minimax reward positive. Since different bandit problems have different optimal minimax rewards, we will normalize the minimax reward so the maximum possible value is 1.
Our approach, which we refer as "LowerBound MaxEnt", solves the optimization problem in Equation by alternating between (1) solving convex optimization problem to find the optimal reward function, and (2) computing the optimal MaxEnt RL policy for this reward function. Step is done using CVXPY, while step is done by exponentiated the reward function, and normalizing to sum to one. Note that this approach is actually solving a harder problem: robust-reward control problem for much larger set of reward functions that contains the original set of reward functions. Because this approach is solving a more challenging problem, we do not expect that it will achieve the optimal minimax reward. However, be easier to implement than fictitious play, which we compare against. Different from experiments in Sections 4.4
solving the
emphasize that this approach may
and and 5.3 the "LowerBound MaxEnt" approach assumes access to the full reward
21

---

Under review as a conference paper at ICLR 2020
normalized minimax reward
0.8
0.6
LowerBound + MaxEnt
optimal policy uniform policy
FictitiousPlay
0.2
pointwise minimum policy
10
10a
10a
10a
optimization steps
Figure 7: Approximately solving an arbitrary robust-reward control problem. In this experi- ment, aim solve the robust-reward control problem for arbitrary set of reward functions. While we know that MaxEnt RI. can be used to solve arbitrary robust-reward control problems exactly, doing so requires that we already know the optimal policy ($ B.5). Instead, we use the approach outlined in Section B.6) which allows us to approximately solve an arbitrary robust-reward control problem without knowing the solution apriori. This approach ("LowerBound + MaxEnt") achieves near-optimal minimax reward.
function, not just the rewards for the actions taken. For fair comparison, fictitious play will also use policy player that has access to the reward function. Fictitious play is guaranteed to converge to the optimal minimax policy, so we assume that the minimax reward converges to optimal. We compare baselines. The "pointwise minimum policy" finds the optimal policy for function formed by taking the pointwise minimum of all reward functions: F(a) = min r(a). This strategy quite simple and intuitive. The other baseline is "uniform policy" that chooses actions uniformly at random.
reward
We each method the same of 10 robust-reward control bandit problems. In Figure 7 plot the (normalized) minimax reward obtained by each method on each problem, as well as the average performance across all 10 problems. The "LowerBound + MaxEnt" approach converges to normalized minimax reward of 0.91, close to the optimal value of 1. In contrast, the "pointwise minimum policy" and the "uniform policy" perform poorly, obtaining normalized minimax rewards of 0.56 and 0.60, respectively. In summary, while the method proposed for converting robust- reward control problems to MaxEnt RL problems does not converge to optimal minimax policy, empirically it performs well.
B.8 ALL ADVERSARIAL GAMES ARE MAXENT PROBLEMS
In this section, generalize the previous result to show that MaxEnt RL can be used to solve to arbitrary control games, including robust control and regret minimization on POMDPs.
We can view the robust-reward control problem zero-sum game. The policy player chooses a policy at every round (or, more precisely, a mixture of policies). The second player, the MDP player, chooses the MDP with which we interact (or, more precisely, mixture over MDPs). Formally, we define the set of policies and MDPs M, both of which correspond to pure strategies for our players. To represent mixed strategies, we use Qii C pll and Q-M C P.M to denote distributions over policies and models, respectively. Our goal is to find Nash equilibrium for the following game:
special case of more general, two player,
max min F(PT.PM) Pr Qu PMEQM
T Σ
where
A gopp M.DM a>>((a)s) rppals (s,a)
Tm as)
(18)
The objective FF says that, at the start of each episode, we independently sample a policy and a MDP. We evaluate the policy w.r.t this MDP, where both the dynamics and reward function governed
22

---

Under review as a conference paper at ICLR 2020
by the sampled MDP. We recall that the Nash Existence Theorem Nash al. 1950) proves that Nash Equilibrium will always exist. With this intuition in place, we state our main result:
Theorem B.5, For every solution adversarial control problem (Eq. 18 there exists Markovian policy that is optimal:
3x" s.f.
min F(Lx", = max min F(Pa:PM). P-E PM Q.
PMEQM
In the statement of the theorem above, have used f to indicate that the policy player uses pure strategy, deterministically using policy π.. While one might expect that mixtures of policies might be more robust, this theorem says this is not the case.
Proof. To begin, we note that F depends solely on the marginal distribution over states and actions visited by the policy. We will use Pr a) to denote this marginal distribution. Given the mixture over policies Px (T), each with its own marginal distribution, we can form the aggregate marginal distribution, p(s,a).
((s. 0.) S1{ P- (x) a)dr.
We can now employ Ziebart 2010 Theorem 2.8) to argue that there exists a single policy n² with the same marginal distribution:
3 s.t. (s. = p(s, a) Vs
Thus, conclude that
min PMEQM
F(.m.PPM)
min PMEQM
F(pt.PM)
One curious aspect of this proof is that is does not require that use MaxEnt policies. In Ap- pendix B.9 we discuss how alternative forms of regularized control might be used to solve this same problem. We now examine four special types adversarial games. For each problem, MaxEnt RL can be used to find the optimal Markovian policy.
Kobust-Reward Control The robust-reward control problem (Definition 3.1 is special case where the MDPs that the adversary can choose among, .M, have identical states, actions and dynamics, differing only in their reward functions. The adversary's 's choice of distribution over MDPs is equivalent to choosing a distribution over reward functions.
POMDPs- MaxEnt RL can be used to find the optimal Markovian policy for POMDP. Recall that all POMDPs can be defined as distributions over MDPs. Let a POMDP be given, and let PIM be its corresponding distribution over MDPs. We now define the set of MDPs the adversary can among as QM {PM} J. That is, the adversary's 's only choice is pM Note that the singleton set is closed under convex combinations (i.c., it contains all the required mixed strategies). Thus, we can invoke Theorem B.5 to claim that MaxEnt RL can solve this problem.
Robust Control - Next, we consider the general robust control problem, where an adversary chooses both the dynamics and the reward function. To invoke Theorem B.5 we simply define a set of MDPs with the same state and actions spaces, but which differ in their transition probabilities and reward functions. Note that this result is much stronger than the robust-reward control problem discussed in Section B.5 as it includes robustness to dynamics.
Robust Adversarial Reinforcement Learning - The robust adversarial RL problem (Pinto) et al.) 2017) is defined in terms of MDP and collection of "perturbation policies", among which the adversary chooses the worst. Note that the original MDP combined with perturbations from one of the perturbation policies defines new MDP with the same states, actions, and rewards, but modified transition dynamics. Thus, we can convert the original MDP and collection of perturbation policies into collection of MDPs, each of which differs only in its transition function.
While MaxEnt RL can find the optimal Markovian policy for each problem, restricting ourselves to Markovian policies may limit performance. For example, the optimal policy for a robust control problem might perform system ID internally, but this cannot be done by Markovian policy.
23

---

Under review as a conference paper at ICLR 2020
HalfCheetah-v2
Hopper-v2
Walker2d-v2
Ant-v2
cumulative reward
2000
2000
5000
1000
1000
0
minimax reward
0
-20000
-4000
-200
500000 1000000
500000 1000000
0
500000 1000000
500000 1000000 train steps
train steps
train steps
train steps
MaxEnt RL
RL
Fictitious Play
Figure 8: MaxEnt RL solves robust-reward control problems robotic control tasks. In the top row, we plot the average cumulative reward, with each column showing different environment. In the bottom row, we plot the average worst-case reward. While both MaxEnt RL and standard RL succeed at maximizing the cumulative reward. only MaxEnt RL succeeds at maximizing worst-case reward. The thick line the average over five random seeds (thin lines).
B.9 ALTERNATIVE FORMS OF REGULARIZED CONTROL
In this section, examine why used MaxEnt RL in Section If write the KKT stationarity conditions for the robust-reward control problem, we find that the solution to the robust- reward control problem æ, is also the solution standard RL problem with reward function that is a convex combination of the reward functions in the original set.
B.5
T
T Σ
Ex
Σ F(s.a) a)
=
ι E arg max E,
F(ss, ai)
where
F(8, a) A Σ Ar)
Above, we have used A; as the dual parameters for reward function r,, However, we have no guarantee that is the unique solution to the RL problem with reward function Using MaxEnt RL guarantees More broadly, we needed a regularized control problem. is
that the optimal policy is unique? ] interesting to consider what other sorts of regularizers induce unique solutions, thereby allowing us to reduce robust-reward control to these other problems as well. We leave this to future work.
C ADDITIONAL EXPERIMENTS
In Section 5 we argued that MaxEnt RL was equivalent to solving a robust-reward control problem. The proof of Theorem 5.2 holds for arbitrary MDPs, not just bandits. In this section, evaluate MaxEnt RL and two baselines on four robotic control tasks, and find that MaxEnt RL optimizes worst-case reward better than the baselines.
We consider continuous control tasks taken from the standard OpenAl Gym (Brockman et al. 2016 benchmark: Ha l @1ffheeehh-ya Hopper-v2. Wa 1 kerkd-v2 and Ant-v2. Each task has maximum horizon of 1,000 steps. We used SAC (Haarnoja et al., (0188) as our MaxEnt RL algorithm and SVG (Heess et al.) 2015)) our standard RL algorithm. We also compared with a version fictitious play that modified SVG to choose the worst-case reward function at each time step. For computational reasons, we do not include historical averaging for the fictitious play baseline this experiment. Following Haarnoja et al. (2018b), we use temperature of 1/5 (see Appendix B.4).
However, the parameters of the optimal policy may not be unique if there is surjective mapping from policy parameters to policies.
24

---

Under review as a conference paper at ICLR 2020
We used the same hyperparameters for each algorithm, taking the hyperparameterss directly from the TF-Agents (Guadarrama et al.) 2018) implementation of SAC. To evaluate each algorithm, we computed both the average cumulative reward, well the average worst-case reward. The worst- case reward was defined as in Equation 2 As shown in Figure & both MaxEnt RI. and standard RL maximize the cumulative reward, but only MaxEnt RL succeeds maximizing the worst-case reward. In summary, this experiment supports our proof that MaxEnt RL is solving a robust-reward control problem in arbitrary MDPs.
D AN EXAMPLE META- HOMA-P
Consider simple MDP shown to the right. There two
actions (Up and Down), five states (1, 2, 3, 4, 5) and episodes last two steps (i.e., two actions). We will assume that there is only one action that can be taken in the final state, and will therefore ignore the last action. The agent always starts in state 1. Now, we define meta-POMDP for this MDP. We define the trajectory distribution
2
4
UP
DOWN
p(r*)
1 5( 2- 5(("" = (1 2 2-++5) 2
5
Meta-episodes and meta-steps: Below, we go through an example meta-episode.
Meta-Episode At the start of meta-episode, a trajectory r" p(r*) is sampled. We will say that we sampled -" (1 + 2 4).
Meta-step 1: One meta-step corresponds to one episode in the MDP (i.e., two actions). For example, meta-step might consider of the policy choosing actions Up and Down, resulting in trajectory 7 (1 + 2 - 5). Since the trajectory did not equal the target trajectory * T"), the agent receives a reward of -1 (for the meta-step) and the epitaee does not terminate. Note that the reward and termination are based on the (unknown) target trajectory r", not on the trajectory distribution p(r").
Meta-step 2:
In the second meta-step, we will say the policy chooses actions Up and Up. resulting in trajectory
(1 + 2 + 4). Since the trajectory does equal the target trajectory (r = r"), the agent receives a reward of 0 (for the meta-step) and the meta-episode terminates. The cumulative return for the agent in this meta-episode is: -1 (for meta-step 1) + (for meta-step 2) -1. The optimal policy would have immediately chosen -² and received reward of 0, our policy has regret of O (-1) 1.
Meta-episode 2: At the start of the next meta-episode, another trajectory T" p(r*) is sampled. We continue as in meta-episode
For this task, the optimal policy म chooses uniformly between trajectory (1 - 2 + 4) and trajectory (1 + 2 + 5). The regret of this policy
Regret:
Regret, (T = p(r" = (1 + - 4))
( = (1 +2 2 + + = =(1 - + + 5))
T = (1-2-1
1 1 1 2
2 1/2 1/2
As another example, consider a policy that chooses uniformly between three trajectories:
(1 + 4). (1 + 2 - 5), and (1 3 + 4). The regret of this (suboptimal) policy IT2
is:
1
(ngret,(Tz)) p(T' = (1 + 2 4))
4)) + p(7" (1 11-2--2 2-++5) 5))
Tz(T"
x2(
5))
2 1/3 21/3 3.
Solving the meta- In Section 4.2
we said that the optimal policy should satisfy T(T) x
Vo(r"). In this example, this identity means that the optimal policy should be .(r) _5(7"
25

---

Under review as a conference paper at ICLR 2020
(1 2 -)) 4))+ 20T"" +
- 2 -))) Note that the optimal policy, satisfies this identity,
while the suboptimal policy, N2, does not.
Lemma 4.1 Lemma 4.1 says that there should exist reward function such that that MaxEnt RL problem with this reward function and meta-POMDP have the same solution. this simple example, such reward function is
r(s, a) = {-00 =
otherwise
Since the dynamics in this simple example are deterministic, the optimal MaxEnt RL policy chooses trajectory with probability
{
if E {(1 - 2 + 4), - - +5]
pi (T) xx r(re()))))))
otherwise
Thus, MaxEnt RL on this reward function yields the optimal policy for the meta-POMDP
Goal-reaching Peta-P Finally, we consider goal-reaching task. For example, will say that the task is to reach goal ST = 4. We define the trajectory distribution as uniform over all trajectories that reach this goal at the final time step:
p(r') 2 8(T (1 - 4)) + 50(T
+ 4)).
2
This trajectory distribution satisfies the assumption of Lemma be written function of the last state in the trajectory:
4.2 which states that the density can
1
p(r") ((sT((),
2 ( 4).
Following Lemma 4.2 the corresponding MaxEnt RL reward function is
r(s,, 0x) 5(1 log (og)))))))) f-2
if T and ST(T) # 4)
0
otherwise
Since the dynamics in this simple example are deterministic, the optimal MaxEnt RL policy chooses trajectory with probability
n" (T) E (().)))
[ if ((1 2 4), otherwise
4)}
The "magic" Lemma that we can obtain the optimal policy for this meta-POMDP by applying MaxEnt RI. to reward function that does provide reward whenever the agent reaches goal state sr. regardless the trajectory taken.
26


Reviews:
[{"review_id": "rylwfsfRFH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary :\nThe paper discusses the use of maximum entropy in Reinforcement Learning. Specifically, it relates the solution of the maximum entropy RL problem to the solutions of two different settings, 1) a ‘meta-POMDP’ regret minimization problem and 2) a ‘robust reward control’ problem. Both cases follow with simple experiments. \n\nI feel the paper could have been written more clearly. There seem to be too many definitions and descriptive examples that diverge the attention of the reader from the main problem setting. There are quite a bit of grammatical errors in the paper, making it even harder to follow. With these many definitions in the text, it is hard to make out the actual contributions of the work. Moreover, the experiments are restricted to the bandit setting and do not provide any empirical evidence on the MDP centered theory. Overall, although the paper does well in motivating the problem, the lack of rigorous experiments and poorly structured writing advocate for a weak rejection.\n\n\nComments/questions:\n- Can the authors comment on why it makes intuitive sense to study the meta-POMDP and robust reward control problem settings together? I see the commonality being the reward variability, but is there something else?\n- If one wants to solve the meta-POMDP through max entropy RL, how general/strong is the assumption that we are given access to the target trajectory belief?\n- In the goal reaching meta-POMDP, it makes sense to only have the final state distribution in the definition. What does the action taken in the final state signify?\n- It would be more intuitive to note the optimal solution as pi* and not pi (Lemma 4.1).\n- In the meta-POMDP, does the task change after every meta-episode?\n- I think it would be better to have separate, consistently named subsections devoted to defining the two problem settings and then move on to proving equivalence with the max entropy case.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "r1lPYRyHFS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper investigates the reason behind the success of MaxEntropy in reinforcement learning theoretically, connecting it to  robust control.\n\nI  think the paper should be accepted, as it investigates an important approach and offers useful insight. I think that the robust reward is an interesting perspective and the paper is also well written.\n\nI need to remark that I am not familiar enough with RL theory literature to know of novel this work is,.\n\nDetailed remarks:\n- There is an error in the proof in A.1. You are optimizing a functional not a function, so the cannot simply use Lagrange multipliers (also the derivation ignores the integral). The problem is solved easily with (constrained) Euler-Lagrange and must be corrected.\n- I disagree with the exploration paragraph in sec. 2. While the final applied agent might be deterministic, using a stochastic agent for exploration during learning is helpful. Exploration might not be only (or main) motivation behind MaxEntRL but it still a good motivation.\n-  I was happy to see the limitation of lemma 4.1 stated clearly, as some paper are less honest with their limitations.\n- You write \"Only the oracle version of fictitious play, which makes assumptions not made by MaxEnt\", maybe I missed it but I didn't see what assumptions the oracle made.\n- MaxEnt has been very successful in inverse RL where we try to find the reward, which seems connected to the conclusions here about robustness to reward perturbations. While adding analysis on IRL might be outside the scope of this paper, something at least should be said about maxEnt and IRL and the connection to the current results. \n\nTypo:\n\"inference problem be defining\" -> \"inference problem by defining\"", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "B1eC9jq0FH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper aims to theoretically understand the reason that MaxEnt RL (RL with an entropy bonus) works so well. It suggests that MaxEnt RL works well in the setting where there is uncertainty about the reward function. It proves two main theorems to support this. First, for any instance of a class of “meta-POMDPs” where the agent only has a *belief* over the goal trajectory, there exists a reward function for which MaxEnt RL on that reward function is the optimal solution to the meta-POMDP. Second, for any reward and MDP, there exists a set of reward functions such that MaxEnt RL maximizes the worst-case return for a reward chosen from that set.\n\nThe paper tackles an important question, since entropy bonuses are commonly used in RL, but are primarily a “hack” added to incentivize exploration without any principled justification. However, I question the applicability of the theorems to the success of MaxEnt RL.\n\nI’m recommending a weak reject, for the following reasons, in order of importance (explained in more detail later):\n- Section 4.2 assumes that you must deploy a single policy across all timesteps of the meta-POMDP, but it should be possible to update your policy across timesteps.\n- Section 4.3 claims to reduce goal-reaching problems to single-goal-trajectory problems, but this doesn’t work because goal-reaching problems can have multiple optimal trajectories.\n- The adversary of Theorem 5.2 is quite unusual, and it is unclear why robustness to such an adversary should be useful.\n- Since the theorems are about cases where the agent is uncertain about the reward, they don’t explain why MaxEnt RL is useful even in the case where we have no adversaries and care only about performance on a single reward function.\n- The paper is not very clear. The quality of exposition could be improved significantly.\n\nIt seems quite likely that some of my critiques are misguided (especially the one about Section 4.2), and I encourage the authors to point this out in the rebuttal.\n\n----\n\nMy primary complaint is that these theorems don’t apply to the case they are meant to explain: the authors say they want to explain why MaxEnt RL works in practice, but their explanations and theorems center on cases in which the reward is unknown. But currently MaxEnt RL works well on tasks where the reward is known! It’s not that MaxEnt RL finds different solutions that don’t do well on the original reward but do better by some other criterion: the solutions found by MaxEnt RL are the best solutions when evaluated by the known reward.\n\nNonetheless, it is still an interesting question to study the benefits of MaxEnt RL in the context of reward uncertainty. I’d recommend that the authors change the motivation and introduction to focus on that setting, without claiming to explain why MaxEnt RL works with current systems. For the rest of the review, I’ll evaluate the paper from that perspective.\n\n----\n\nI found the section on meta-POMDPs very confusing. First, one minor confusion: I believe you are assuming that the underlying MDP is deterministic? (Perhaps not, but the assumption that there is a policy with probability proportional to sqrt(p(tau)) is much less likely to hold in stochastic environments.)\n\nSection 4.2 is confusing to me. First, let me quote the description of the meta-POMDP: “Each meta-step of the meta-POMDP corresponds to one episode of the original MDP. A meta-episode is a sequence of meta-steps, which ends when the agent solves the task in the original MDP. Intuitively, each meta-episode in the meta-POMDP corresponds to multiple trials in the original MDP, where the task remains the same across trials. The agent keeps interacting with the MDP until it solves the task.”\n\nBy my understanding, this means that in the meta-POMDP the agent is able to learn across episodes. In particular, in the setting where the agent has a distribution over a single goal trajectory, and the underlying MDP is deterministic, the optimal policy is obvious: try the most probable goal trajectory, then try the second most probable goal trajectory, and so on until you find the true goal trajectory, and then repeatedly execute that goal trajectory. Why is this not the result of Section 4.2?\n\n(My guess is that you assumed that the agent is not able to learn across episodes (why?), or that the agent receives literally zero information about whether or not it has completed the goal (highly unrealistic, and certainly doesn’t apply to the physician example). Perhaps there is a different unstated assumption instead.)\n\nI’d encourage the authors to more clearly formalize the meta-POMDP as well as the relevant assumptions that lead to the results of Section 4.2. As currently defined, I don’t agree with Section 4.1, though I do think there is a formalization which makes everything work (though that formalization does not seem realistic to me).\n\n----\n\nI’m also confused about Section 4.3. In Section 4 (before subsections) and Section 4.1, it seems that the model is that there is a *single* goal trajectory which the agent must replicate, but the agent is uncertain about that trajectory. However, Section 4.3 considers goal-reaching problems, in which there can be *multiple* goal trajectories. I don’t understand how the goal-reaching problem is reduced to the single-goal-trajectory problem: I believe the current reduction is *not* solving a goal-reaching problem.\n\nFor simplicity, let’s consider a goal-reaching problem where the goal is known: a 3x3 grid where the agent starts at the bottom left and the goal is to get to the top right. Assume a horizon of 4 for simplicity. Then any trajectory involving two Ups and two Rights solves the problem, i.e. there are six optimal trajectories: {UURR, URUR, URRU, RUUR, RURU, RRUU}. However, the meta-POMDP defined in the reduction assigns 1/6 probability to each such trajectory, which by the semantics of the meta-POMDP means that the agent “actually” wants to choose one of those trajectories in particular, but doesn’t know which one is appropriate. This is not an accurate representation of the goal-reaching problem: the goal-reaching problem is solved as long as *any* of these trajectories are selected.\n\n(Lemma 4.2 is technically accurate, because it only talks about the meta-POMDP and the corresponding reward function, and doesn’t claim anything about the relation to the goal-reaching problem, but all the prose around Lemma 4.2 is misleading.)\n\nThis general problem persists even if you have a belief over the goal state, rather than being certain about the goal state. You could try fixing this by changing the meta-POMDP to put probability over *sets* of goal trajectories, and Section 4.1 would still go through (the regret would be a geometric random variable of the probability the trajectory lies within the true goal trajectory set), but Section 4.2 would no longer work.\n\n----\n\nTheorem 5.2 shows that there exists a set of reward functions such that MaxEnt RL maximizes the worst-case return for a reward chosen from that set. Taken literally, this is not particularly interesting, as it is also true of regular RL: the optimal regular RL policy pi optimizes the worst-case return for the set { r’(s, a) = r(s, a) + f(s, a) with f in F }, for any class of non-negative functions F that contains the zero function, simply because every other reward in the set is at least as large as the true reward r(s, a). (Another set that works is { r’(s, a) = K r(s, a) with K > 0 }.)\n\nSo really the interesting content of the second theorem is the particular set of reward functions that MaxEnt RL is robust to: the set {r’(s, a) = r(s, a) - log q(a | s) for all q in Pi}. This is an interesting adversary model: essentially, at every state, the adversary is required to provide a non-negative bonus b_a for each action a. To prevent the adversary from providing zero bonus everywhere, the bonuses must satisfy \\sum_a exp(b_a) = 1.\n\nThis essentially means that at each state, the adversary wants to find actions that the policy doesn’t take, and allocate more of the bonus to that action. Given this particular adversary, it makes sense to inject a little noise into the policy so that the adversary can’t “hide” the bonus in actions that are rarely taken, and so it makes sense the MaxEnt RL could be the best response to such an adversary. However, this is quite a strange adversary -- we wouldn’t usually expect that the things we need to be robust to are going to be dividing up some bonus across actions. So I’m not very confident that this theorem will actually matter in practice.\n\n----\n\nTypos:\n\nAbstract: “Probability, as this strategy is called,”: “Probability matching”\nIntroduction: “model for decision decision making”: repeated “decision”\nIntroduction: “empirical benefits of MaxEnt RL arise implicitly solving”: “arise by implicitly solving”\nPreliminaries: “These approaches cast optimal control as an inference problem be defining”: “be” --> “by”\nPreliminaries: In the derivation of Eq. 1, p(s_1) was dropped\nPreliminaries: The last equality in the derivation of Eq. 1 would only hold if you had a log on the LHS, so you probably wanted to maximize log p(O_t) in the entirety of the derivation.\nLemma 4.2: “p˜(sT(τ), aT(τ)) = p(τ)”: Reverse the order to write “p(τ) = p˜(sT(τ), aT(τ))” to follow the convention that the thing being defined is on the LHS", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies maximum entropy reinforcement learning in more detail. Maximum entropy is a popular strategy in modern RL methods and also seems used in human and animal decision making. However, it does not lead to optimize expected utility. The authors propose a setting in which maximum entropy RL is an optimal solution. 

The authors were quite split on the paper, and there has been an animated discussion between the reviewers among each other and with the authors. 

The technical quality is good, although one reviewer commented on the restricted setting of the experiments (bandit problems). The authors have addressed this by adding an additional experiment. Futhermore, two reviewers commented that the clarity of the paper could be improved. 

A larger part of the discussion (also the private discussion) revolved around relevance and significance, especially of the meta-pomdp setting that takes up a large part of the manuscript. 
- A reviewer mentioned that after reading the paper, it does not become more clear why maximum entropy RL works well in practice. The discussion even turned to why MaxEntropyRL might be *unreasonable* from the point of view of needing a meta-POMDP with Markov assumptions, which doesn't help shed light on its empirical success. The meta-POMDP setting does not seem to reflect the use cases where maximum entropy RL has done well in emperical studies. 
- Another reviewer mentioned that earlier papers have investigated maximum entropy RL, and that the paper tries to offer a new perspective with the Meta-POMDP setting. The discussion of this discussion was not deemed complete in current state and needs more attention (splitting the paper into two along these lines is a possibility mooted by two of the reviewers). A particular example was the doctor-patient example, where in the meta-POMDP setting the doctor would repeatedly attempt to cure a fixed sampled illness, rather than e.g. solving for a new illness each time. 

Based on the discussion, I would conclude that the topic broached by the paper is very relevant and timely, however, that the paper would benefit from a round of major revision and resubmission rather than being accepted to ICLR in current form. 
Decision: Reject