Year: 2019

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.

heading: 1 INTRODUCTION
text: 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 RL) 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 (1) are stochastic, and (2) have non-zero probability of sampling every action. MaxEnt RL can equivalently be viewed as probability matching between trajectories visited by the policy and a distribution defined by exponentiating the reward (See Section 2). MaxEnt RL has appealing connections to probabilistic inference (Dayan & Hinton, 1997; Neumann et al., 2011; Todorov, 2007; Kappen, 2005; Toussaint, 2009; Rawlik et al., 2013; Theodorou et al., 2010; Ziebart, 2010), prompting a renewed interest in recent years (Haarnoja et al., 2018b; Abdolmaleki et al., 2018; Levine, 2018). MaxEnt RL can also be viewed as 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 on a number of simulated (Haarnoja et al., 2018b) 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 & Bitterman, 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 (1986)), where it is often described as obtaining the ideal free distribution. Probability matching is not merely a reflection of youth or 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
matching, while rats almost always chose the maximizing strategy. Similarly, older children and adults engage in probability matching more frequently than young children (Stevenson & Odom, 1964; Weir, 1964). While prior work has offered a number of explanations of probability matching (Vulkan, 2000; Gaissmaier & Schooler, 2008; Wozny et al., 2010; Sakai & Fukai, 2008), its root cause remains an open problem.
The empirical success of MaxEnt RL algorithms on RL problems is surprising, as MaxEnt RL optimizes a different objective than standard RL. The solution to 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, 2016), 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 a 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, we show that MaxEnt RL is equivalent to two more challenging problems: (1) regret minimization in a meta-POMDP, 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 a 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-POMDP 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 5. Even if the agent will eventually be deployed in a setting without adversaries, the adversarial objective bounds the worst-case performance of that agent. Our result in this setting can be viewed as an 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 a 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, we show that MaxEnt RL provides 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.

heading: 2 PRELIMINARIES
text: We begin by defining notation and discussing some previous motivations for MaxEnt RL. An agent observes states st, takes actions at ∼ π(at | st), and obtains rewards r(st, at). The initial state is sampled s1 ∼ p1(s1), and subsequent states are sampled s′ ∼ p(s′ | s, a). Episodes have T steps, which we summarize as a trajectory τ , (s1, a1, · · · , sT , aT ). Without loss of generality, we can assume that rewards are undiscounted, as any discount can be addressed by modifying the dynamics to transition to an absorbing state with probability 1− γ. The RL objective is:
arg max π
Eπ [ T∑ t=1 r(st, at) ] = ∫ ( T∑ t=1 r(st, at) ) p1(s1) T∏ t=1 p(st+1 | st, at)π(at | st)dτ.
In fully observed MDPs, there always exists a deterministic policy as a solution (Puterman, 2014). The MaxEnt RL problem, also known as the entropy-regularized control problem, is to maximize the sum of expected reward and conditional action entropy,Hπ[a | s]:
arg max π
Eπ [ T∑ t=1 r(st, at) ] +Hπ[a | s] = Eπ [ T∑ t=1 r(st, at)− log π(at | st) ] The MaxEnt RL objective results in policies that are stochastic, with higher-entropy action distributions in states where many different actions lead to similarly optimal rewards, and lower-entropy
distributions in states where a 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 equivalently be defined as a form of probability matching, minimizing a reverse Kullback Leibler (KL) divergence (Rawlik et al., 2013):
max π
Eπ [ T∑ t=1 r(st, at) ] +Hπ[a | s] = −min π DKL(π(τ) ‖ pr(τ)),
where the policy distribution π(τ) and the target distribution pr(τ) are defined as
pr(τ) ∝ p1(s1) T∏ t=1 p(st+1 | st, at)e ∑T t=1 r(st,at), π(τ) , p1(s1) T∏ t=1 p(st+1 | st, at)π(at | st).
Prior work on MaxEnt RL offers a 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 as performing good exploration. Unlike many other RL algorithms, such as DQN (Mnih et al., 2015) and DDPG (Lillicrap et al., 2015), MaxEnt RL performs exploration and policy improvement with the same (stochastic) policy. One problem with this motivation is 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 a stochastic policy, many MaxEnt RL papers evaluate the corresponding deterministic policy (Haarnoja et al., 2018b), 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 a second motivation for MaxEnt RL (Abdolmaleki et al., 2018; Haarnoja et al., 2018b; Todorov, 2007; Levine, 2018; Toussaint, 2009). These approaches cast optimal control as an inference problem by defining additional optimality binary random variables Ot, equal one with probability proportional to exponentiated reward. These methods then maximize the following log-likelihood:
log p(Ot) = log ∫ p1(s1) T∏ t=1 p(Ot = 1 | st, at)p(st+1 | st, at)π(at | st)dτ
= log ∫ p1(s1)e ∑T t=1 r(st,at) T∏ t=1 p(st+1 | st, at)π(at | st)dτ
= logEπ [ e ∑T t=1 r(st,at) ] ≈ Eπ [ T∑ t=1 r(st, at) ] + Varπ [ T∑ t=1 r(st, at) ] (1)
The last term is a cumulant generating function (i.e., the logarithm of a moment generating function (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-seeking behavior, not optimal control. Equation 1 can also be directly obtained by considering an agent with a risk-seeking utility function (O’Donoghue, 2018). While risk seeking behavior can be avoided by maximizing a certain lower bound on Equation 1 (Levine, 2018), artificially constraining algorithms to maximize a lower bound suggests that likelihood is not what we actually want to 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.

heading: 3 WHAT PROBLEMS DOES MAXENT RL SOLVE?
text: MaxEnt RL produces stochastic policies, so we 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.

heading: 3.1 ANSWER 1: PARTIALLY OBSERVED ENVIRONMENTS
text: The first strength of stochastic policies guarantees that they will not have to wait infinitely long to find a good outcome. Imagine that a 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 a belief over what the true reward is. For example, in a health-care setting, consider the course of treatment for a 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 to 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 4, we define a meta-level POMDP for describing these sorts of tasks and show that MaxEnt RL minimizes regret in such settings.

heading: 3.2 ANSWER 2: ROBUSTNESS TO EXPLOITATION
text: 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 to guarantee that a 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 a set of reward functions R = {ri} is
arg max π min r′∈R
Eπ [ T∑ t=1 r′(st, at) ] .
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 a saddle-point problem. Nonetheless, in Section 5, we show that MaxEnt RL is exactly equivalent to solving a robust-reward control problem.

heading: 3.3 SUMMARY
text: 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 to 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., a robot in a medical setting may not observe the true cause for a patient’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.

heading: 4 MAXIMUM ENTROPY RL AND PARTIALLY OBSERVED ENVIRONMENTS
text: 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 an unknown task as a special
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-POMDP as a MDP with many possible tasks that could be solved. 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 as simply matching some target trajectory, τ∗. Crucially, the agent does not know which task it must solve (i.e., τ∗ is not observed). Rather, the agent has access to a belief p(τ) over what the target trajectory may be. This results in a POMDP, where the agent’s ignorance of the true task makes the problem partial observed.
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. While the meta-POMDP 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 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 a 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 a meta-POMDP.
Before proceeding, we emphasize that defining the meta-POMDP 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-Farley et al., 2018; Pong et al., 2019), can be viewed as a special case of this general formulation.

heading: 4.1 REGRET IN THE META-POMDP
text: 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 = 1 for every meta-step when the agent fails to solve the task, and 1− 1 = 0 for the (final) meta-step when the agent solves the task. Thus, the cumulative 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.
Our analysis of the meta-POMDP 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 in a future meta-step within the same meta-episode. Our results will therefore be lower bounds on the performance of 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, we use π(τ∗) to denote the probability that policy π produces target trajectory τ∗. Then, the number of episodes until it matches trajectory τ∗ is a geometric random variable with parameter π(τ∗). The expected value of this random variable is 1/π(τ∗), so we can write the regret of the meta-POMDP as:
Regretp(π) = Eτ∗∼p [ 1
π(τ∗)
] .
Note that this regret is a function of a particular policy π(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.

heading: 4.2 SOLVING THE META-POMDP
text: We solve the meta-POMDP by finding an optimal distribution over trajectories:
min π
Regretp(π) s.t. ∫ π(τ)dτ = 1, π(τ) > 0.
Using Lagrange multipliers (see Appendix A.1), we find that the optimal policy is:
π(τ) = √ p(τ)∫ √ p(τ ′)dτ ′ .
This policy is stochastic and matches the unnormalized distribution √ p(τ). This result suggests that we can find the optimal policy by solving a MaxEnt RL problem, with a trajectory-level reward function rτ (τ) , 12 log p(τ). To make this statement precise, we consider the bandit setting and MDP setting separately. If the underlying MDP is a bandit, then trajectories are equivalent to actions. We can define a reward function as r(a) = 12 log p(a). Applying MaxEnt RL to this reward function yields the following policy, which is optimal for the meta-POMDP: π(a) ∝ √ p(a). For MDPs with horizon lengths greater than one, we can make a similar statement:
Lemma 4.1. Let a goal trajectory distribution p(τ) be given, and assume that there exists a policy π whose trajectory distribution is proportional to the square-root of the target distribution: π(τ) ∝√ p(τ). Then there exists a 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-POMDP, so it must satisfy π∗(τ) ∝ √ p(τ). Thus, π∗ is the solution to the MaxEnt RL problem with the trajectory-level reward r(τ) = 12 log p(τ):
π∗ ∈ arg min π
Eπ [ 1
2 log p(τ)
] +Hπ[a | s] = DKL(π(τ) ‖ 1
c
√ p(τ)) ⇐⇒ π(τ) ∝ √ p(τ) ∀τ.
The normalizing constant c, which is independent from π∗, is introduced to handle the fact that√ p(τ) 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 A.3 that a trajectory-level reward r(τ) can always be decomposed into an state-action reward r(st, at) with the same MaxEnt RL solution. Thus, there exists a reward function such that MaxEnt RL solves the meta-POMDP:
π∗ ∈ arg min π Eπ [ T∑ t=1 r(st, at) ] +Hπ[a | s] ⇐⇒ π∗(τ) ∝ √ p(τ) ∀τ.
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: even when the meta-POMDP is unknown, MaxEnt RL methods will minimize regret in some meta-POMDP, which could account for their good performance, particularly in the presence of uncertainty and perturbations.

heading: 4.3 GOAL-REACHING META-POMDPS
text: We can make the connection between MaxEnt RL and meta-POMDPs more precise by considering a special class of meta-POMDPs: meta-POMDPs where the target distribution is defined only in terms of the last state in a trajectory, corresponding to goal-reaching problems. While prior work on goal-reaching (Kaelbling, 1993; Schaul et al., 2015; Andrychowicz et al., 2017) assumes that the goal state is observed, the goal-reaching meta-POMDP only assumes that the policy has a belief about the goal state.
Lemma 4.2. Let a meta-POMDP with target distribution that depends solely on the last state and action in the trajectory be given. That is, the target distribution p(τ) satisfies
sT (τ) = sT (τ ′) and aT (τ) = aT (τ ′) =⇒ p(τ) = p(τ ′) ∀τ, τ ′
where sT (τ) and aT (τ) are functions that extract the last state and action in trajectory τ . We can thus write the density of a trajectory under the goal trajectory distribution as a function of the last state and action: p(τ) = p̃(sT (τ), aT (τ)), where p̃(sT , aT ) is an unnormalized density. Assume that there exists a policy whose marginal state density at the last time step, ρTπ (s, a), satisfies ρ T π (s, a) ∝ √ p̃(s, a) for all states s. Then the MaxEnt RL problem with reward r(st, at) , 121(t = T ) · log p̃(st, at) and the meta-POMDP have the same solutions.
Proof. We simply combine Lemma 4.1 with the definition of the reward function r:
T∑ t=1 r(st, at) = T∑ t=1 1 2 1(t = T ) · log p(st, at) = 1 2 log p̃(sT , sT ) = rτ (τ).
While our assumption that there exists a policy that exactly matches some distribution ( √ p̃(sT , aT )) may seem somewhat unnatural, we provide a sufficient condition in Appendix A.4. Further, while the analysis so far has considered the equivalence of MaxEnt RL and the meta-POMDP at optimum, in Appendix A.5 we bound the difference between these problems away from their optima. In summary, the meta-POMDP allows us to represent goal-reaching tasks with uncertainty in the true goal state. Moreover, solving these goal-reaching meta-POMDPs with MaxEnt RL is straightforward, as the reward function for MaxEnt RL is a simple function of the last transition.

heading: 4.4 A COMPUTATIONAL EXPERIMENT
text: To conclude this section, we present a simple computational experiment to verify that MaxEnt RL does solve the meta-POMDP. We instantiated the meta-POMDP using 5-armed bandits. Each meta-POMDP is specified by a prior belief p(i) over the target arm. We sample this distribution from a Dirichlet(1). To solve this meta-POMDP, we applied MaxEnt RL using a reward function r(i) = 12 log p(i), as derived above. When the agent pulls arm i, it observes a noisy reward ri ∼ N (r(i), 1). To implement the MaxEnt RL approach, we
maintained the posterior of the reward r(i), given our observations so far. We initialized our beliefs with a zero-mean, unit-variance Gaussian prior. To obtain a policy with MaxEnt RL, we chose actions with probability proportional to the exponentiated expected reward. Throughout training, we tracked the regret (Eq. 4.1). Since the minimum regret possible for each meta-POMDP is different, we normalized the regret for each meta-POMDP by dividing by the minimum possible regret. Thus, the normalized regret lies in the interval [1,∞], with lower being better. Figure 1 shows that MaxEnt RL converges to the regret-minimizing policy for each meta-POMDP. Code to reproduce all experiments is available online.1

heading: 5 MAXIMUM ENTROPY RL AND ADVERSARIAL GAMES
text: While the meta-POMDP 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 MaxEnt RL is equivalent to solving robust-reward control, and run a computational experiment to support our claims. We generalize these results in Appendix B.

heading: 5.1 MAXENT RL SOLVES ROBUST-REWARD CONTROL
text: Our main result on reward robustness builds on the general equivalence between entropy maximization and game theory from prior work. To start, we note two results from prior work that show how entropy maximization can be written as a robust optimization problem:
Lemma 5.1 (Grünwald et al. (2004)). Let x be a random variable, and let P be the set of all distributions over x. The problem of choosing a maximum entropy distribution for x and maximizing the worst-case log-loss are equivalent:
max p∈P Hp[x] = max p∈P min q∈P Ep[− log q(x)].
1Code: https://drive.google.com/file/d/1Xf3OTxWBg67L2ka1eLd32qDQmtnG8Fxc
An immediately corollary is that maximizing the entropy of any conditional distribution is equivalent to a robust optimization problem: Corollary 5.1.1 (Grünwald et al. (2004); Ziebart et al. (2011)). Let x and y be random variables, and let Px|y be the set of all conditional distributions p(x | y). The problem of choosing a maximum entropy distribution for the conditional distribution p(x | y) and maximizing the worst-case log-loss of x given y are equivalent:
max p∈Px|y Ey [Hp[x | y]] = max p∈Px|y min q∈Px|y Ey [Ep[− log q(x | y)]] .
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 a certain class of reward functions:
Eπ [ T∑ t=1 r(st, at) ] +Hπ[a | s] = min r∈Rr Eπ [ T∑ t=1 r(st, at) ] ,
where Rr = {r′(s, a) , r(s, a)− log q(a | s) | q ∈ Π}. (2)
For completeness, we provide a proof in Appendix B.1. We will call the set Rr of reward functions a 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 an unknown reward function. As an aside, we note that the log q(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., 2019a; Chow et al., 2018) would result in different robust sets (see Grünwald et al. (2004)). We leave this generalization for future work.

heading: 5.2 A SIMPLE EXAMPLE
text: In Figure 2, we consider a simple, 2-armed bandit, with the following reward function:
r(a) =
{ 2 a = 1
1 a = 2 .
The robust set is then defined as
Rr =
{ r′(a) = { 2− log q(a) a = 1 1− log(1− q(a)) a = 2 ∣∣∣∣ q ∈ [0, 1]} . Figure 2 (left) traces the original reward function and this robust set. Plotting the robust-reward control objective (center) and the MaxEnt RL objective (right), we observe that they are equivalent.

heading: 5.3 A COMPUTATIONAL EXPERIMENT
text: We ran an experiment to support our claim that MaxEnt RL is equivalent to solving the robustreward problem. The mean for arm i, µi, is drawn from a zero-mean, unit-variance Gaussian distribution, µi ∼ N (0, 1). When the agent pulled arm i, it observes a noisy reward ri ∼ N (µi, 1). We implement the MaxEnt RL approaches as in Section 4.4. As a baseline, we compare to fictitious play (Brown, 1951), an algorithm for solving two-player, zero-sum games. Fictitious play alternates between choosing the best policy w.r.t. the historical average of observes rewards, and choosing the worst reward function for the historical average of policies. We choose the worst reward function from the robust set (Eq. 2). For fair comparison, the policy only observes the (noisy) reward associated with the selected arm. We also compared to an
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.e., the expected reward of the policy, if the reward function were adversarially chosen from the robust set). Because each problem had a different minimax reward, we 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 1 being optimal. Figure 3 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 RL, is competitive with MaxEnt RL. In Appendix C, we run a similar experiment on four robotic control tasks and find that MaxEnt RL optimizes the minimax reward better than standard RL and fictitious play.

heading: 6 DISCUSSION
text: In summary, this paper studies connections between MaxEnt RL and control problems with variability in the reward function. While MaxEnt RL is a relatively simple algorithm, the problems that it solves, such as robust-reward control and regret minimization in the meta-POMDP, are typically viewed as quite complex. This result hints that MaxEnt RL might also be used to solve even broader classes of control problems. The principle of maximum entropy has also been applied to inverse RL, and we encourage future work to 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 to likewise focus their research on problem settings likely to occur in the real world.

heading: A META-POMDP

heading: A.1 SOLVING FOR THE OPTIMAL TRAJECTORY DISTRIBUTION
text: We will solve the optimization problem introduced in Section 4.2 using the constrained EulerLagrangian method. The Lagrangian is
L(π, λ) , ∫ p(τ)
π(τ) dτ + λ
(∫ π(τ)dτ − 1 ) .
The first and second derivatives of the Lagrangian are:
dL dπ(τ) = − p(τ) π(τ)2 − λ d 2L dπ2 = 2 p(τ) π(τ)3 > 0.
Note that the second derivative is positive so setting the first derivative equal to zero will provide a minimum of the objective:
dL dπ(τ)
= 0 =⇒ π(τ) = √ −λp(τ).
We then solve for λ using the constraint that π(τ) integrate to one, yielding the solution to the optimization problem:
π(τ) = √ p(τ)∫ √ p(τ ′)dτ ′ .

heading: A.2 THE META-POMDP AS (MEMORYLESS) META-LEARNING
text: The meta-POMDP can be viewed as a meta-learning problem (Thrun & Pratt, 2012), solved with a memoryless meta-learner. Formally, a meta-learning algorithm is a 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, as the meta-learner cannot update its beliefs based on observed evidence: p(π | D) = p(π). We define a meta-learning problem by a distribution over MDPs, p(M). A unknown MDP M will be sampled, and the job of the meta-learning algorithm is to solveM as quickly as possible. Solving an MDP can mean a number of different things: reaching a goal state, achieving a certain level of reward, or avoiding episode termination. For simplicity, we assume that each MDP has a single successful policy, and each policy is successful for a single MDP, though this analysis can likely be extended to more general notions of success. We will define πi as the unique policy that solves MDPMi. Note that, in this setting, the regret of the meta-POMDP is exactly the number of episodes required to find the optimal policy for the (unknown) MDP. Lemma 4.1 tells us that the optimal (memoryless) meta-learning algorithm is defined as p(πi) ∝ √ p(Mi).
While the assumption that the meta-learning algorithm is independent of observed data is admittedly strong, it is realistic in settings where failing at 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 as meta-learning problems.

heading: A.3 WHEN CAN TRAJECTORY-LEVEL REWARDS BE DECOMPOSED?
text: Lemma A.1. Let a trajectory-level reward function rτ (τ) be given, and define the corresponding target distribution as
prτ (τ) ∝ p1(s1)erτ (τ) T∏ t=1 p(st+1 | st, at).

heading: If there exists a Markovian policy π such that π(τ) = prτ (τ) for all trajectories τ , then there exists a
text: state-action level reward function r(s, a) satisfying
rτ (τ) = T∑ t=1 r(st, at) ∀τ,
Proof. To start, we recall the definitions of π(τ) and prτ (τ):
π(τ) ∝ p1(s1) T∏ t=1 p(st+1 | st, at)π(at | st) (3)
prτ (τ) ∝ p1(s1)erτ (τ) T∏ t=1 p(st+1 | st, at). (4)
By our assumption that π(τ) = prτ (τ), we know that Equations 3 and 4 are equal, up to some proportionality constant c′:
p1(s1)e rτ (τ) T∏ t=1 p(st+1 | st, at) = c′p1(s1) T∏ t=1 p(st+1 | st, at)π(at | st)
= p1(s1)e log c′+
∑T t=1 log π(at|st) T∏ t=1 p(st+1 | st, at)
= p1(s1)e ∑T t=1 r(st,at) T∏ t=1 p(st+1 | st, at),
where r(s, a) , log π(a | s) + 1T log c ′.

heading: A.4 WHEN DOES A SOLUTION EXIST?
text: When considering goal-reaching meta-POMDPs, we made an assumption that there exists a policy that exactly matches some distribution ( √ p̃(sT , aT )). Here, we provide a sufficient (but not necessary) condition for the existence of such a policy Lemma A.2. Let p(τ) = p̃(sT , aT ) be some distribution over trajectories that depends only on the last state and action in each trajectory (as in Lemma 4.2). If, for every state sT and action aT where p̃(sT , aT ) > 0, there exists a policy πsT ,aT that deterministically reaches state sT and action aT on the final time step, then there exists a Markovian policy satisfying π(τ) = p(τ).
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 a way of “mixing” these policies to obtain a policy with the desired marginal distribution.
Proof. First, we construct a mixture policy π̄ by sampling sT , aT ∼ q̃(sT , aT ) at the start of each episode, and using policy πsT ,aT for every step in that episode. By construction, we have ρπ̄(sT , aT ) = q(sT , aT ). However, this policy π̄ is non-Markovian. Nonetheless, Ziebart (2010, Theorem 2.8) guarantees that there exists a Markovian policy π̃ with the same marginal state distribution: π̃(sT , aT ) = π̄(sT , aT ). Thus, there exists a Markovian policy, π̃ satisfying π̃(sT , aT ) = q(sT , aT ).

heading: A.5 BOUNDING THE DIFFERENCE BETWEEN MAXENT RL AND THE META-POMDP
text: While the result in Section 4 shows that MaxEnt RL has the same solution as the meta-POMDP, it does not tells us how the two control problems differ away from their optima. The following theorem provides an answer. Theorem A.3. Assume that the ratio p(τ)/π(τ) is bounded in [a, b] for all trajectories τ and a, b > 0. Further, assume that there exists a policy πr that can solve the MaxEnt RL problem exactly (i.e., π(τ) = p(τ)). Then the MaxEnt RL objective minimizes an upper bound on the log regret of the meta-POMDP, plus an additional term that vanishes as π → pr:
J(π, pr) ≥ log Regretp2r (π) + C(π, r).
Before proving this theorem, we note that the assumption that the MaxEnt RL problem can be solved exactly is always satisfied for linearly-solveable MDPs (Todorov, 2007). Moreover, given a MDP that cannot be solved exactly, we can always modify the reward function (i.e., the target distribution p(τ)) 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).
Proof. To start, we apply a “backwards” version of Jensen’s inequality from Simic (2009, Theorem 1.1), which states that the following inequality holds for any convex function f(x):∫
p(τ)f(xτ )dτ − f ∫ p(τ)xτdτ ≤ 1
4 (b− a)(f ′(b)− f ′(a)).
We use − log(x) as our convex function, whose derivative is −1x , and further define xτ = p(τ)/π(τ): − ∫ p(τ) log ( p(τ)
π(τ)
) dτ + log ∫ p2(τ)
π(τ) dτ ≤ 1 4 (b− a)(1/a− 1/b).
Rearranging terms, we get
log
∫ p2(τ)
π(τ) dτ ≤
∫ p(τ) log ( p(τ)
π(τ)
) dτ + 1
4 (b− a)(1/a− 1/b). (5)
The LHS is not quite a log regret (Eq. 4.1) because it contains a p2(τ) term in the numerator, which is not a proper probability distribution. Defining Z = ∫ p2(τ) as the normalizing constant (which does not depend on π), we can write the log regret using a proper distribution:
log Regret 1 Z p 2(π) = log
∫ p2(τ)
Zπ(τ) dτ = log
∫ p2(τ)
π(τ) dτ − logZ
We can now rewrite Equation 5 as a bound on log regret:
log Regret 1 Z p
2(π) ≤ ∫ p(τ) log ( p(τ)
π(τ)
) dτ + 1
4 (b− a)(1/a− 1/b) + logZ. (6)
Notice that the integral on the RHS is the forward KL between p and π, 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 a result from 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:
`d(τ) , log p1(s1) + T∑ t=1 log p(st+1 | st, at).
Now, the policy distribution π(τ) and the target distribution, p(τ), can both be written in terms of dynamics and policy:
log π(τ) = `d(τ) + T∑ t=1 log π(at | st)
log p(τ) = `d(τ) + T∑ t=1 log π∗p(at | st),
where π∗p is the optimal MaxEnt RL policy for the reward r(τ) = log p(τ). By our assumption that there exists some π such that π(τ) = p(τ), we know that π∗p(τ) = p(τ). With this notation in place, we can employ Proposition 2 of Norouzi et al. (2016):
DKL(p(τ) ‖ π(τ)) ≤ DKL(π(τ) ‖ p(τ)) + ∑ τ (`p(τ)− `π(τ))2
= DKL(π(τ) ‖ p(τ)) + ∑ τ ( T∑ t=1 log π∗p(at | st)− T∑ t=1 log π(at | st) )2 . (7)
Note that the dynamics logits `d cancelled with one another. Now, we combine Equations 6 and 7 to obtain:
log Regretp2r (π) ≤ 1 Z DKL(π(τ) ‖ p(τ)) + C(π, r), (8)
where
C(π, r) = ( T∑ t=1 log π∗p(at | st)− T∑ t=1 log π(at | st) )2 + 1 4 (b− a)(1/a− 1/b).
As π → π∗p , difference of log probabilities (term 1) vanishes. Additionally, the ratio p(τ)/π(τ)→ 1, so we can take a and b (the limits on the probability ratio) towards 1. As a → 1 and b → 1, the second term in C(π, r) vanishes as well.
In summary, the difference between the MaxEnt RL objective and the log regret of the meta-POMDP is controlled by a term C(π, r). At the solution to the MaxEnt RL problem, this term is zero, implying that solving the MaxEnt RL problem will minimize regret on the meta-POMDP.

heading: B MAXIMUM ENTROPY RL AND ADVERSARIAL GAMES

heading: B.1 PROOF AND EXTENSIONS OF THEOREM 5.2
text: Our proof of Theorem 5.2 consists of first applying Corollary 5.1.1, and then rearranging terms.

heading: Proof.
text: max π∈Π
Eπ [ T∑ t=1 r(st, at) ] +Hπ[a | s] = max π∈Π Eπ [ T∑ t=1 r(st, at) ] + min q∈Π Eπ [ T∑ t=1 − log q(at | st) ]
= max π∈Π min q∈Π
Eπ [ T∑ t=1 (r(st, at)− log q(at | st)) ]
= max π∈Π min r′∈Rr
Eπ [ T∑ t=1 r′(st, at) ] .
A 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 a lower bound on that policy’s reward for any reward function in some set. Corollary B.0.1. Let policy π and reward function r be given, and let J be the MaxEnt objective policy π on reward function r:
J(π, r) , Eπ [ T∑ t=1 r(st, at) ] +Hπ[a | s].
Then the expected return of policy π on any reward function in Rr is at least J:
Eπ [ T∑ t=1 r′(st, at) ] ≥ J(π, r) ∀r′ ∈ Rr.
B.2 INTUITION FOR ROBUST SETS
We can gain intuition for the robust set by explicitly writing out the definition of Π:
Π , { q | q(s, a) ∈ [0, 1] ∀s, a and ∫ A q(a | s)da = 1 ∀s }
= { q | log q(s, a) ∈ [−∞, 0] ∀s, a and ∫ A elog q(a|s)da = 1 ∀s } .
Now, we can rewrite our definition of Rr as follows:
Rr = { r(s, a) + us(a) | us(a) ≥ 0 ∀s, a and ∫ A e−us(a)da = 1 ∀s } (9)
= { r′(s, a) | r′(s, a) ≥ 0 ∀s, a and ∫ A er(s,a)−r ′(s,a)da = 1 ∀s } .
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 the reward can be increased for another state-action pair. One important caveat of the results in this section is that, individually, the reward functions in in the robust set Rr are “easier” than the original reward function, in that they assign larger values to the reward at a given state and action:
r(s, a) ≤ r′(s, a) ∀s ∈ S, a ∈ A, r′ ∈ Rr.
Appendix B.4 discusses the role of temperatures on the robustness of MaxEnt RL.

heading: B.3 EQUIVALENCE CLASSES OF ROBUST REWARD CONTROL PROBLEMS
text: In this section, we aim to understand whether the policy obtained by running MaxEnt RL on reward function r is robust to reward functions besides those in Rr. As a first step, we show that the policy is also robust to reward functions that are “easier” than those in Rr. We then show that the set Rr is not unique and introduce a family of equivalent robust-reward control problems, all of which are equivalent to the original MaxEnt RL problem.

heading: B.3.1 ROBUSTNESS TO DOMINATED REWARD FUNCTIONS
text: In Theorem 5.2, we showed that the optimal MaxEnt RL policy π is also the minimax policy for the reward functions in Rr. A somewhat trivial corollary is that π is also robust to any reward function that is pointwise weakly better than a reward function in our robust set:
Lemma B.1. The MaxEnt RL objective for a reward function r is equivalent to the robust-reward control objective for a class of reward functions, R+r ⊇ Rr:
Eπ [ T∑ t=1 r(st, at) ] +Hπ[a | s] = min r∈R+r Eπ [ T∑ t=1 r(st, at) ] ,
where R+r , {r+(s, a) = r′(s, a) + c | c ≥ 0, r′ ∈ Rr}.
Proof. To prove this, we simply note that these additional reward functions, r+ ∈ R+r \ Rr, will never be chosen as the arg min of the RHS. Thus, expanding the constraint set from Rr to R+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+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 to write a new definition for the robust set. Since we now know that u can be made arbitrarily small, we can allow e−us(a) to take very small values. More precisely, whereas before we were constrained to add a term that integrated to one, we now are allows to add any term whose integral is at at most one:
R+r = { r(s, a) + us(a) | us(a) ≥ 0 ∀s, a and ∫ A e−us(a)da ≤ 1 ∀s } .

heading: B.3.2 GLOBAL AFFINE TRANSFORMATIONS
text: In optimal control, modifying a reward function by adding a global constant or scaling all reward by a positive constant does not change the optimal policy. Thus, the robust-reward control problem for a set of rewards Rr has the same solution as the robust-reward control problem for a scaled and shifted set of rewards:
Lemma B.2. Let a set of reward functionsRr be given, and let b, c ∈ R, b > 0 be arbitrary constants. Then the following two optimization problems are equivalent:
arg max π min r′∈Rr
Eπ [ T∑ t=1 r′(st, at) ] = arg max π min r′∈bRr+c Eπ [ T∑ t=1 r′(st, at) ] .
Proof. The proof follows simply by linearity of expectation, and the invariance of the argmax to positive affine transformations:
arg max π min r′∈bRr+c
Eπ [ T∑ t=1 r′(st, at) ] = arg max π min r′∈Rr Eπ [ T∑ t=1 (br′(st, at) + c) ] (10)
= arg max π b min r′∈Rr
Eπ [ T∑ t=1 r′(st, at) ] + cT (11)
= arg max π min r′∈Rr
Eπ [ T∑ t=1 r′(st, at) ] . (12)
Note, however, that the robust-reward control problem for rewards Rr is not the same as 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 a fixed affine transformation of Rr.
To gain some intuition for these transformations of reward functions, we apply a variety of transformations to the reward function from Figure 2. In Figure 5 (left) we show the effect of multiplying the reward by a positive constant. Figure 5 (right) shows the effect of adding a constant to the reward for every state and action.. For the robust sets in the right plot, there exists another reward function (r† = r + c) such that the shifted robust set is equal to the robust set of the shifted reward (i.e., Rr+c = Rr + c):
Lemma B.3. Let reward function r and constant c ∈ R be given. Define a reward function rc(s, a) , r(s, a) + c. LetWr be the set of robust optimization problems which are equivalent to the MaxEnt RL problem on reward function r. The MaxEnt RL problem with the shifted reward function, rc, is equivalent to the same set of robust optimization problems: Wr =Wrc
Proof. In addition to the argument given above, we can simply note that the two MaxEnt RL problems are the same:
arg max π
Eπ [ T∑ t=1 rc(st, at) ] +Hπ[a | s] = arg max π Eπ [ T∑ t=1 r(st, at) ] +Hπ[a | s] + : const. T · c.
Lemma B.3 is not true for the robust sets in the left plot. While the policy that is minimax for Rr is also minimax for bRr, there does not exist another reward function r† such that Rr† = bRr. The reason is that scaling the robust violates the constraint ∫ e−us(a)da = 1.

heading: B.4 TEMPERATURES
text: Many algorithms for MaxEnt RL (Haarnoja et al., 2018b; Fox et al., 2015; Nachum et al., 2017) include a temperature α > 0 to balance the reward and entropy terms:
J(π, r) = Eπ [ T∑ t=1 r(st, at) ] + αHπ[a | s].
We can gain some intuition into the effect of this temperature on the set of reward functions to which we are robust. In particular, including a temperature α results in the following robust set:
Rαr = { r(s, a) + αus(a) | us(a) ≥ 0 ∀s, a and ∫ A e−us(a)da ≤ 1 ∀s } (13)
= { r(s, a) + us(a) | us(a) ≥ 0 ∀s, a and ∫ A e−us(a)/αda ≤ 1 ∀s } . (14)
In the second line, we simply moved the temperature from the objective to the constraint by redefining us(a)→ 1αus(a). We visualize the effect of the temperature in Figure 6. First, we fix a reward function r, and plot the robust set Rαr for varying values of α. Figure 6 (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 of the robust set for lower temperatures: α1 < α2 =⇒ Rα2r ⊆ Rα2r . This statement can be proven by simply noting that the function e− x α is an increasing function of α in Equation 14. It is important to recognize that being robust against more reward functions is not always desirable. In many cases, to be robust to everything, an optimal policy must do nothing.
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αr that include r
′, for varying values of α. As shown in Figure 6 (right), if we must be robust to r′ and use a high temperature, the only other reward functions to which we are robust are those that are similar, or pointwise weakly better, than r′. In contrast, when using a small temperature, we are robust against a 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 to a larger set of reward functions.

heading: B.5 MAXENT SOLVES ROBUST CONTROL FOR REWARDS
text: In Section 5, we showed that MaxEnt RL is equivalent to some robust-reward problem. The aim of this section is to go backwards: given a set of reward functions, can we formulate a 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.t. r is an optimal robust-reward policy for R:
arg max π
Eπ [ T∑ t=1 r(st, at) ] +Hπ[a | s] ⊆ arg max π min r′∈R Eπ [ T∑ t=1 r′(st, at) ] .
We use set containment, rather than equality, because there may be multiple solutions to the robustreward control problem.
Proof. Let π∗ be a solution to the robust-reward control problem:
π∗ ∈ arg max π min ri∈R Eπ [ T∑ t=1 ri(st, at) ] .
Define the MaxEnt RL reward function as follows:
r(s, a) = log π∗(a | s).
Substituting this reward function in Equation 2, we see that the unique solution is π = π∗.
Intuitively, this theorem states that we can use MaxEnt RL to solve any robust-reward control problem that requires robustness with respect to any arbitrary set of rewards, if we can find the right corresponding reward function r 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 is similar to Ilyas et al. (2019).

heading: B.6 FINDING THE ROBUST REWARD FUNCTION
text: In the previous section, we showed that a policy robust against any set of reward functions R can be obtained by solving a MaxEnt RL problem. However, this requires calculating a reward function r∗ for MaxEnt RL, which is 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 a reward function r∗ such that its robust set, Rr∗ , contains the set of reward functions we want to be robust against, R. That is, for each ri ∈ R, we want
ri(s, a) = r ∗(s, a) + us(a) for some us(a) satisfying ∫ A e−us(a)da ≤ 1 ∀s.
Replacing u with r′ − r∗, we see that the MaxEnt reward function r must satisfy the following constraints: ∫
A er ∗(s,a)−r′(s,a)da ≤ 1 ∀s ∈ S, r′ ∈ R.
We define R∗(R) as the set of reward functions satisfying this constraint w.r.t. reward functions in R:
R∗(R) , { r∗ ∣∣∣∣ ∫ A er ∗(s,a)−r′(s,a)da ≤ 1 ∀s ∈ S, r′ ∈ R } Note that we can satisfy the constraint by making r∗ arbitrarily negative, so the set R∗(R) is nonempty. We now use Corollary 5.1.1 to argue that all any applying MaxEnt RL to any reward function in r∗ ∈ R∗(R) lower bounds the robust-reward control objective. Corollary B.4.1. Let a set of reward functions R be given, and let r∗ ∈ R∗(R) be an arbitrary reward function belonging to the feasible set of MaxEnt reward functions. Then
J(π, r∗) ≤ min r′∈R Eπ [ T∑ t=1 r′(st, at) ] ∀π ∈ Π.
Note that this bound holds for all feasible reward functions and all policies, so it also holds for the maximum r∗:
max r∗∈R∗(R) J(π, r∗) ≤ min r′∈R Eπ [ T∑ t=1 r′(st, at) ] ∀π ∈ Π. (15)
Defining π∗ = arg maxπ J(π, r ∗), we get the following inequality:
max r∗∈R∗(R),π∈Π J(π, r∗) ≤ min r′∈R Eπ∗ [ T∑ t=1 r′(st, at) ] ≤ max π∈Π min r′∈R Eπ [ T∑ t=1 r′(st, at) ] . (16)
Thus, we can find the tightest lower bound by finding the policy π and feasibly reward r∗ that maximize Equation 16:
max r,π
Eπ [ T∑ t=1 r(st, at) ] +Hπ[a | s] (17)
s.t. ∫ A er(s,a)−r ′(s,a)da ≤ 1 ∀ s ∈ S, r′ ∈ 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. r 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 π.

heading: B.7 ANOTHER COMPUTATIONAL EXPERIMENT
text: This section presents an experiment to study the approach outlined above. Of particular interest is whether the lower bound (Eq 16) comes close the the optimal minimax policy.
We will solve robust-reward control problems on 5-armed bandits, where the robust set is a collection of 5 reward functions, each is drawn from a 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 is 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 to as “LowerBound + MaxEnt”, solves the optimization problem in Equation 17 by alternating between (1) solving a convex optimization problem to find the optimal reward function, and (2) computing the optimal MaxEnt RL policy for this reward function. Step 1 is done using CVXPY, while step 2 is done by exponentiated the reward function, and normalizing it to sum to one. Note that this approach is actually solving a harder problem: it is solving the robust-reward control problem for a 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, we emphasize that this approach may be easier to implement than fictitious play, which we compare against. Different from experiments in Sections 4.4 and 5.3, the “LowerBound + MaxEnt” approach assumes access to the full reward
function, not just the rewards for the actions taken. For fair comparison, fictitious play will also use a 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 it converges to is optimal. We compare to two baselines. The “pointwise minimum policy” finds the optimal policy for a new reward function formed by taking the pointwise minimum of all reward functions: r̃(a) = minr∈R r(a). This strategy is quite simple and intuitive. The other baseline is a “uniform policy” that chooses actions uniformly at random.
We ran each method on the same set of 10 robust-reward control bandit problems. In Figure 7, we 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 a 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 robustreward control problems to MaxEnt RL problems does not converge to the optimal minimax policy, empirically it performs well.

heading: B.8 ALL ADVERSARIAL GAMES ARE MAXENT PROBLEMS
text: In this section, we 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 as a special case of a more general, two player, 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, a mixture over MDPs). Formally, we define the set of policies Π and MDPsM, both of which correspond to pure strategies for our players. To represent mixed strategies, we use QΠ ⊆ PΠ and QM ⊆ PM to denote distributions over policies and models, respectively. Our goal is to find a Nash equilibrium for the following game:
max pπ∈QΠ min pM∈QM
F(pπ, pM)
where F(pπ, pM) , E π∼pπ,M∼pM a∼π(a|s), s′∼pM(s′|s,a) [ T∑ t=1 rM(st, at) ] . (18)
The objective F 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 are governed
by the sampled MDP. We recall that the Nash Existence Theorem (Nash et al., 1950) proves that a 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 a Markovian policy π∗ that is optimal:
∃π∗ s.t. min pM∈QM F(1π∗ , pM) = max pπ∈QΠ min pM∈QM F(pπ, pM).
In the statement of the theorem above, we have used 1π∗ to indicate that the policy player uses a 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 ρπ(s, a) to denote this marginal distribution. Given the mixture over policies pπ(π), each with its own marginal distribution, we can form the aggregate marginal distribution, ρ̄(s, a):
ρ̄(s, a) = ∫ Π pπ(π)ρπ(s, a)dπ.
We can now employ Ziebart (2010, Theorem 2.8) to argue that there exists a single policy π∗ with the same marginal distribution: ∃ π∗ s.t. ρπ∗(s, a) = ρ̄(s, a) ∀s, a. Thus, we conclude that
min pM∈QM F(1π∗ , pM) = min pM∈QM F(p∗π, pM).
One curious aspect of this proof is that is does not require that we use MaxEnt policies. In Appendix B.9, we discuss how alternative forms of regularized control might be used to solve this same problem. We now examine four special types of adversarial games. For each problem, MaxEnt RL can be used to find the optimal Markovian policy.
Robust-Reward Control – The robust-reward control problem (Definition 3.1) is a 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 choice of a 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 a POMDP. Recall that all POMDPs can be defined as distributions over MDPs. Let a POMDP be given, and let p∗M be its corresponding distribution over MDPs. We now define the set of MDPs the adversary can among asQM = {p∗M}. That is, the adversary’s only choice is p∗M. Note that the singleton set is closed under convex combinations (i.e., 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 a MDP and a 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 a 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 a 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 a Markovian policy.

heading: B.9 ALTERNATIVE FORMS OF REGULARIZED CONTROL
text: In this section, we examine why we used MaxEnt RL in Section B.5. If we write out the KKT stationarity conditions for the robust-reward control problem, we find that the solution to the robustreward control problem π, is also the solution to a standard RL problem with a reward function that is a convex combination of the reward functions in the original set.
∇πEπ [ T∑ t=1 r̄(s, a) ] =⇒ π ∈ arg max π Eπ [ T∑ t=1 r̄(st, at) ] ,
where r̄(s, a) , ∑ i λiri(s, a).
Above, we have used λi as the dual parameters for reward function ri. However, we have no guarantee that π is the unique solution to the RL problem with reward function r̄. Using MaxEnt RL guarantees that the optimal policy is unique.2 More broadly, we needed a regularized control problem. It is interesting to consider what other sorts of regularizers can induce unique solutions, thereby allowing us to reduce robust-reward control to these other problems as well. We leave this to future work.

heading: C ADDITIONAL EXPERIMENTS
text: 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, we 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 OpenAI Gym (Brockman et al., 2016) benchmark: HalfCheetah-v2, Hopper-v2, Walker2d-v2, and Ant-v2. Each task has a maximum horizon of 1,000 steps. We used SAC (Haarnoja et al., 2018b) as our MaxEnt RL algorithm and SVG (Heess et al., 2015) as 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 in this experiment. Following Haarnoja et al. (2018b), we use a temperature of 1/5 (see Appendix B.4).
2However, the parameters of the optimal policy may not be unique if there is a surjective mapping from policy parameters to policies.
We used the same hyperparameters for each algorithm, taking the hyperparameters directly from the TF-Agents (Guadarrama et al., 2018) implementation of SAC. To evaluate each algorithm, we computed both the average cumulative reward, as well as the average worst-case reward. The worstcase reward was defined as in Equation 2. As shown in Figure 8, both MaxEnt RL and standard RL can maximize the cumulative reward, but only MaxEnt RL succeeds as 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.

heading: D AN EXAMPLE META-POMDP
text: Consider a simple MDP shown to the right. There are 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 a meta-POMDP for this MDP. We define the trajectory distribution as
p(τ∗) = 1 2 δ(τ∗ = (1→ 2→ 4)) + 1 2 δ(τ∗ = (1→ 2→ 5))
Meta-episodes and meta-steps: Below, we go through an example meta-episode.
Meta-Episode 1: At the start of a meta-episode, a trajectory τ∗ ∼ p(τ∗) 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, a meta-step might consider of the policy choosing actions Up and Down, resulting in trajectory τ = (1→ 2→ 5). Since the trajectory did not equal the target trajectory (τ 6= τ∗), the agent receives a reward of -1 (for the meta-step) and the meta-episode does not terminate. Note that the reward and termination are based on the (unknown) target trajectory τ∗, not on the trajectory distribution p(τ∗). 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 (τ = τ∗), 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) + 0 (for meta-step 2) = -1. The optimal policy would have immediately chosen τ∗ and received a reward of 0, so our policy has a regret of 0− (−1) = 1.
Meta-episode 2: At the start of the next meta-episode, another trajectory τ∗ ∼ p(τ∗) is sampled. We continue as in meta-episode 1.
Regret: For this task, the optimal policy π1 chooses uniformly between trajectory (1→ 2→ 4) and trajectory (1→ 2→ 5). The regret of this policy is
Regretp(π1) = p(τ ∗ = (1→ 2→ 4)) 1 π1(τ∗ = (1→ 2→ 4)) + p(τ∗ = (1→ 2→ 5)) 1 π1(τ∗ = (1→ 2→ 5))
= 1
2
1
1/2 +
1
2
1
1/2 = 2.
As another example, consider a policy that chooses uniformly between three trajectories: (1→ 2→ 4), (1 → 2 → 5), and (1 → 3 → 4). The regret of this (suboptimal) policy π2 is:
Regretp(π2) = p(τ ∗ = (1→ 2→ 4)) 1 π2(τ∗ = (1→ 2→ 4)) + p(τ∗ = (1→ 2→ 5)) 1 π2(τ∗ = (1→ 2→ 5))
= 1
2
1
1/3 +
1
2
1
1/3 = 3.
Solving the meta-POMDP: In Section 4.2, we said that the optimal policy should satisfy π(τ) ∝√ p(τ∗). In this example, this identity means that the optimal policy should be π(τ) = 12δ(τ ∗ =
(1 → 2 → 4)) + 12δ(τ ∗ = (1 → 2 → 5)). Note that the optimal policy, π1 satisfies this identity, while the suboptimal policy, π2, does not.
Lemma 4.1: Lemma 4.1 says that there should exist a reward function such that that MaxEnt RL problem with this reward function and meta-POMDP have the same solution. In this simple example, one such reward function is
r(s, a) = { −∞ if s = 3 0 otherwise .
Since the dynamics in this simple example are deterministic, the optimal MaxEnt RL policy chooses trajectory τ with probability
pi∗(τ) ∝ e ∑ t r(st,at) = { 1 if τ ∈ {(1→ 2→ 4), (1→ 2→ 5)} 0 otherwise .
Thus, MaxEnt RL on this reward function yields the optimal policy for the meta-POMDP.
Goal-reaching meta-POMDPs: Finally, we consider a goal-reaching task. For example, we 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(τ∗) = 1 2 δ(τ∗ = (1→ 2→ 4)) + 1 2 δ(τ∗ = (1→ 3→ 4)).
This trajectory distribution satisfies the assumption of Lemma 4.2, which states that the density can be written as a function of the last state in the trajectory:
p(τ∗) = p̃(sT (τ), aT (τ)) = 1
2 δ(sT (τ) = 4).
Following Lemma 4.2, the corresponding MaxEnt RL reward function is
r(st, at) = 1
2 δ(t = T ) log p̃(sT (τ), aT (τ)) = { −∞ if t = T and sT (τ) 6= 4) 0 otherwise .
Since the dynamics in this simple example are deterministic, the optimal MaxEnt RL policy chooses trajectory τ with probability
π∗(τ) ∝ e ∑ t r(st,at) = { 1 if τ ∈ {(1→ 2→ 4), (1→ 3→ 4)} 0 otherwise .
The “magic” of Lemma 4.2 is that we can obtain the optimal policy for this meta-POMDP by applying MaxEnt RL to a reward function that does provide reward whenever the agent reaches goal state sT , regardless of the trajectory taken.

Review summaries:
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.