Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: 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.

The 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.

I’m recommending a weak reject, for the following reasons, in order of importance (explained in more detail later):
- 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.
- 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.
- The adversary of Theorem 5.2 is quite unusual, and it is unclear why robustness to such an adversary should be useful.
- 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.
- The paper is not very clear. The quality of exposition could be improved significantly.

It 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.

----

My 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.

Nonetheless, 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.

----

I 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.)

Section 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.”

By 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?

(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.)

I’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).

----

I’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.

For 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.

(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.)

This 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.

----

Theorem 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 }.)

So 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.

This 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.

----

Typos:

Abstract: “Probability, as this strategy is called,”: “Probability matching”
Introduction: “model for decision decision making”: repeated “decision”
Introduction: “empirical benefits of MaxEnt RL arise implicitly solving”: “arise by implicitly solving”
Preliminaries: “These approaches cast optimal control as an inference problem be defining”: “be” --> “by”
Preliminaries: In the derivation of Eq. 1, p(s_1) was dropped
Preliminaries: 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.
Lemma 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
review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: Summary :
The 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. 

I 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.


Comments/questions:
- 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?
- 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?
- 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?
- It would be more intuitive to note the optimal solution as pi* and not pi (Lemma 4.1).
- In the meta-POMDP, does the task change after every meta-episode?
- 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.

review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: The paper investigates the reason behind the success of MaxEntropy in reinforcement learning theoretically, connecting it to  robust control.

I  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.

I need to remark that I am not familiar enough with RL theory literature to know of novel this work is,.

Detailed remarks:
- 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.
- 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.
-  I was happy to see the limitation of lemma 4.1 stated clearly, as some paper are less honest with their limitations.
- 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.
- 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. 

Typo:
"inference problem be defining" -> "inference problem by defining"
review_title: Official Blind Review #2

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