summaries: The paper addresses limitation in max-entropy RL frameworks. These frameworks usually add a regularization term to the reward function to increase policy entropy to encourage exploration, but the effect can be limited in states where the Q-function dominates the expression. The authors propose a new objective that better encourages RL agents to visit rare states with low entropy, and show empirically that their method is able to outperform the baselines used for comparison. This paper proposes a conjecture that the agent should visit the state with low entropy and then do the exploration of this low entropy state with the maximum-entropy principle. To prove this conjecture, the author does a simple experiment on the 4-room maze and illustrates the empirical entropy of the action at different states. There is an interesting observation that the rarely visited states have low entropy maybe due to the function approximation error or off-policy learning explained by the author. Given this observation, the author proposes an algorithm which penalizes the reward with negative entropy （eq7) . Based on this modified Q function, the agent does the policy improvement as the original soft-actor-critic algorithm. The empirical result shows that the proposed algorithm outperforms the baselines such as SAC and many others. The authors describe a positive feedback loop, that arises in SAC-based implementation of the maximum entropy reinforcement learning and hinders efficient exploration. Q values of frequently visited states are updated more, because these states are stored more into the replay buffer. The policy update increases the entropy of the visited states, i.e. if a high entropy is rewarded in the policy the frequently visited states will be selected even more. In the paper, Max-Min Entropy Rl is proposed that is supposed to break the unwanted feedback loop. It considerably improved the empirical performance in common Maze tasks and Mujoco tasks. This paper investigates the undesired behavior of soft actor-critic (SAC) algorithm that implementing maximum entropy reinforcement learning (RL).   One of the main contributions of this paper is the empirical investigation of the undesired behavior of SAC. By running SAC with function approximation on no-reward environment, the authors illustrate that the policy obtained by SAC failed to maximize the entropy, while maximizing the entropy is the optimal situation in no-reward environment and the theoretical study of SAC in finite MDP setups guarantees its optimal convergence. The authors pointed out a possible defect in SAC with function approximation: Q value of already visited states tend to be greater than the other states because the policy update increases the entropy of the visited states.   The second contribution is the proposal of a solution to the above mentioned defect. The authors propose Max-Min Entropy RL (MME). To improve the exploration, the soft Q-function has been revised. Instead of adding the entropy term to the Q-function, the revised soft Q-function subtracts the entropy, if I borrow the authors statement, to enhance the chance to visit rare states with low entropy. This is, however, counter intuitive to me as I will describe in the main review part.  The proposed approach has been tested on sparse mujoco tasks and delayed mujoco tasks, where the environments have sparse-reward shapes, as well as on some standard mujoco environments with dense rewards. The algorithm has been compared to different SOTA approaches. Promising performance has been observed.  
abstractText: In this paper, we propose a max-min entropy framework for reinforcement learning (RL) to overcome the limitation of the soft actor-critic (SAC) algorithm implementing the maximum entropy RL in model-free sample-based learning. Whereas the maximum entropy RL guides learning for policies to reach states with high entropy in the future, the proposed max-min entropy framework aims to learn to visit states with low entropy and maximize the entropy of these low-entropy states to promote better exploration. For general Markov decision processes (MDPs), an efficient algorithm is constructed under the proposed max-min entropy framework based on disentanglement of exploration and exploitation. Numerical results show that the proposed algorithm yields drastic performance improvement over the current state-of-the-art RL algorithms.
authors.name: Seungyul Han
authors.name: Youngchul Sung
references.authors: Joshua Achiam Shankar Sastry
references.title: Surprise-based intrinsic motivation for deep reinforcement learning
references.venue: arXiv preprint arXiv:1703.01732,
references.authors: Martin Arjovsky Soumith Chintala Léon Bottou
references.title: Wasserstein generative adversarial networks
references.venue: In International conference on machine learning,
references.authors: Adrià Puigdomènech Badia Pablo Sprechmann Alex Vitvitskyi Daniel Guo Bilal Piot Steven Kapturowski Olivier Tieleman Martín Arjovsky Alexander Pritzel Andew Bolt
references.title: Never give up: Learning directed exploration strategies
references.venue: arXiv preprint arXiv:2002.06038,
references.authors: Sina Baharlouei Maher Nouiehed Ahmad Beirami Meisam Razaviyayn
references.title: R\’enyi fair inference
references.venue: arXiv preprint arXiv:1906.12005,
references.authors: Gianluca Baldassarre Marco Mirolli
references.title: Intrinsically motivated learning in natural and artificial systems
references.authors: Babak Barazandeh Meisam Razaviyayn
references.title: Solving non-convex non-differentiable min-max games using proximal gradient method
references.venue: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP),
references.authors: Lucas Beyer Damien Vincent Olivier Teboul Sylvain Gelly Matthieu Geist Olivier Pietquin
references.title: Mulex: Disentangling exploitation from exploration in deep rl
references.authors: Yuri Burda Harrison Edwards Amos Storkey Oleg Klimov
references.title: Exploration by random network distillation
references.venue: arXiv preprint arXiv:1810.12894,
references.authors: Nuttapong Chentanez Andrew G Barto Satinder P Singh
references.title: Intrinsically motivated reinforcement learning
references.venue: In Advances in neural information processing systems,
references.authors: Jongwook Choi Yijie Guo Marcin Moczulski Junhyuk Oh Neal Wu Mohammad Norouzi Honglak Lee
references.title: Contingency-aware exploration in reinforcement learning
references.venue: arXiv preprint arXiv:1811.01483,
references.authors: Thomas M Cover
references.title: Elements of information theory
references.authors: Benjamin Eysenbach Sergey Levine
references.title: Maximum entropy rl (provably) solves some robust rl problems
references.venue: arXiv preprint arXiv:2103.06257,
references.authors: Scott Fujimoto Herke van Hoof Dave Meger
references.title: Addressing function approximation error in actor-critic methods
references.venue: arXiv preprint arXiv:1802.09477,
references.authors: Gauthier Gidel Tony Jebara Simon Lacoste-Julien
references.title: Frank-wolfe algorithms for saddle point problems
references.venue: In Artificial Intelligence and Statistics,
references.authors: Ian Goodfellow Jean Pouget-Abadie Mehdi Mirza Bing Xu David Warde-Farley Sherjil Ozair Aaron Courville Yoshua Bengio
references.title: Generative adversarial nets
references.venue: In Advances in neural information processing systems,
references.authors: Yijie Guo Junhyuk Oh Satinder Singh Honglak Lee
references.title: Generative adversarial self-imitation learning
references.venue: arXiv preprint arXiv:1812.00950,
references.authors: Tuomas Haarnoja Sehoon Ha Aurick Zhou Jie Tan George Tucker Sergey Levine
references.title: Learning to walk via deep reinforcement learning
references.venue: arXiv preprint arXiv:1812.11103,
references.authors: Tuomas Haarnoja Haoran Tang Pieter Abbeel Sergey Levine
references.title: Reinforcement learning with deep energy-based policies
references.venue: arXiv preprint arXiv:1702.08165,
references.authors: Tuomas Haarnoja Aurick Zhou Pieter Abbeel Sergey Levine
references.title: Soft actor-critic: Offpolicy maximum entropy deep reinforcement learning with a stochastic actor
references.venue: arXiv preprint arXiv:1801.01290,
references.authors: Tuomas Haarnoja Aurick Zhou Kristian Hartikainen George Tucker Sehoon Ha Jie Tan Vikash Kumar Henry Zhu Abhishek Gupta Pieter Abbeel
references.title: Soft actor-critic algorithms and applications
references.venue: arXiv preprint arXiv:1812.05905,
references.authors: E Yazdandoost Hamedani A Jalilzadeh NS Aybat UV Shanbhag
references.title: Iteration complexity of randomized primal-dual methods for convex-concave saddle point problems
references.venue: arXiv preprint arXiv:1806.04118,
references.authors: Seungyul Han Youngchul Sung
references.title: Diversity actor-critic: Sample-aware entropy regularization for sample-efficient exploration
references.venue: arXiv preprint arXiv:2006.01419,
references.authors: Elad Hazan Sham Kakade Karan Singh Abby Van Soest
references.title: Provably efficient maximum entropy exploration
references.venue: In International Conference on Machine Learning,
references.authors: Zhang-Wei Hong Tzu-Yun Shann Shih-Yang Su Yi-Hsiang Chang Tsu-Jui Fu Chun-Yi Lee
references.title: Diversity-driven exploration strategy for deep reinforcement learning
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Rein Houthooft Xi Chen Yan Duan John Schulman Filip De Turck Pieter Abbeel
references.title: Vime: Variational information maximizing exploration
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Shiyu Huang Hang Su Jun Zhu Ting Chen
references.title: Svqn: Sequential variational soft q-learning networks
references.venue: In International Conference on Learning Representations,
references.authors: Sergey Levine Vladlen Koltun
references.title: Guided policy search
references.venue: In International Conference on Machine Learning,
references.authors: Ya-Feng Liu Yu-Hong Dai Zhi-Quan Luo
references.title: Max-min fairness linear transceiver design for a multi-user mimo interference channel
references.venue: IEEE Transactions on Signal Processing,
references.authors: Manuel Lopes Tobias Lang Marc Toussaint Pierre-Yves Oudeyer
references.title: Exploration in modelbased reinforcement learning by empirically estimating learning progress
references.venue: In Advances in neural information processing systems,
references.authors: Aleksander Madry Aleksandar Makelov Ludwig Schmidt Dimitris Tsipras Adrian Vladu
references.title: Towards deep learning models resistant to adversarial attacks
references.venue: arXiv preprint arXiv:1706.06083,
references.authors: Jarryd Martin Suraj Narayanan Sasikumar Tom Everitt Marcus Hutter
references.title: Count-based exploration in feature space for reinforcement learning
references.venue: arXiv preprint arXiv:1706.08090,
references.authors: Bogdan Mazoure Thang Doan Audrey Durand R Devon Hjelm Joelle Pineau
references.title: Leveraging exploration in off-policy algorithms via normalizing flows
references.authors: Volodymyr Mnih Koray Kavukcuoglu David Silver Andrei A Rusu Joel Veness Marc G Bellemare Alex Graves Martin Riedmiller Andreas K Fidjeland Georg Ostrovski
references.title: Human-level control through deep reinforcement learning
references.venue: Nature, 518(7540):529–533,
references.authors: Katta G Murty Santosh N Kabadi
references.title: Some np-complete problems in quadratic and nonlinear programming
references.venue: Technical report,
references.authors: Ofir Nachum Mohammad Norouzi Kelvin Xu Dale Schuurmans
references.title: Bridging the gap between value and policy based reinforcement learning
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Ofir Nachum Mohammad Norouzi Kelvin Xu Dale Schuurmans
references.title: Trust-pcl: An off-policy trust region method for continuous control
references.venue: arXiv preprint arXiv:1707.01891,
references.authors: Gerhard Neumann
references.title: Variational inference for policy search in changing situations
references.venue: In Proceedings of the 28th International Conference on Machine Learning,
references.authors: Maher Nouiehed Maziar Sanjabi Tianjian Huang Jason D Lee Meisam Razaviyayn
references.title: Solving a class of non-convex min-max games using iterative first order methods
references.authors: Brendan O’Donoghue Remi Munos Koray Kavukcuoglu Volodymyr Mnih
references.title: Combining policy gradient and q-learning
references.venue: arXiv preprint arXiv:1611.01626,
references.authors: Hassan Rafique Mingrui Liu Qihang Lin Tianbao Yang
references.title: Non-convex min-max optimization: Provable algorithms and applications in machine learning
references.authors: Alexander Rakhlin Karthik Sridharan
references.title: Optimization, learning, and games with predictable sequences
references.venue: arXiv preprint arXiv:1311.1869,
references.authors: Konrad Rawlik Marc Toussaint Sethu Vijayakumar
references.title: On stochastic optimal control and reinforcement learning by approximate inference
references.venue: In Twenty-Third International Joint Conference on Artificial Intelligence,
references.authors: John Schulman Xi Chen Pieter Abbeel
references.title: Equivalence between policy gradients and soft q-learning
references.venue: arXiv preprint arXiv:1704.06440,
references.authors: John Schulman Sergey Levine Pieter Abbeel Michael Jordan Philipp Moritz
references.title: Trust region policy optimization
references.venue: In Proceedings of the 32nd International Conference on Machine Learning
references.authors: John Schulman Filip Wolski Prafulla Dhariwal Alec Radford Oleg Klimov
references.title: Proximal policy optimization algorithms
references.venue: arXiv preprint arXiv:1707.06347,
references.authors: Riley Simmons-Edler Ben Eisner Daniel Yang Anthony Bisulco Eric Mitchell Sebastian Seung Daniel Lee
references.title: Qxplore: Q-learning exploration by maximizing temporal difference
references.authors: Avi Singh Larry Yang Kristian Hartikainen Chelsea Finn Sergey Levine
references.title: End-to-end robotic reinforcement learning without reward engineering
references.authors: Emanuel Todorov
references.title: General duality between optimal control and estimation
references.venue: IEEE Conference on Decision and Control,
references.authors: Emanuel Todorov Tom Erez Yuval Tassa
references.title: Mujoco: A physics engine for model-based control
references.venue: In Intelligent Robots and Systems (IROS),
references.authors: Marc Toussaint
references.title: Robot trajectory optimization using approximate inference
references.venue: In Proceedings of the 26th annual international conference on machine learning,
references.authors: Hoi-To Wai Mingyi Hong Zhuoran Yang Zhaoran Wang Kexin Tang
references.title: Variance reduced policy evaluation with smooth function approximation
references.venue: Advances in Neural Information Processing Systems,
references.authors: Brian Hu Zhang Blake Lemoine Margaret Mitchell
references.title: Mitigating unwanted biases with adversarial learning
references.venue: In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society,
references.authors: Zeyu Zheng Junhyuk Oh Satinder Singh
references.title: On learning intrinsic rewards for policy gradient methods
references.venue: In Advances in Neural Information Processing Systems,
sections.text: In this paper, we propose a max-min entropy framework for reinforcement learning (RL) to overcome the limitation of the soft actor-critic (SAC) algorithm implementing the maximum entropy RL in model-free sample-based learning. Whereas the maximum entropy RL guides learning for policies to reach states with high entropy in the future, the proposed max-min entropy framework aims to learn to visit states with low entropy and maximize the entropy of these low-entropy states to promote better exploration. For general Markov decision processes (MDPs), an efficient algorithm is constructed under the proposed max-min entropy framework based on disentanglement of exploration and exploitation. Numerical results show that the proposed algorithm yields drastic performance improvement over the current state-of-the-art RL algorithms.
sections.heading: 1 Introduction
sections.text: The maximum entropy framework has been considered in various RL domains [22, 23, 30, 45, 51, 53, 58]. Maximum entropy RL adds the expected policy entropy to the return objective of standard RL in order to maximize both the return and the entropy of policy distribution. Maximum entropy RL encourages the policy to choose multiple actions probabilistically and yields a significant improvement in exploration and robustness and good final performance in various control tasks [15, 20, 21, 25, 26, 29, 50]. In particular, soft actor-critic (SAC) implements maximum entropy RL in an efficient iterative manner based on soft policy iteration and guarantees convergence to the optimal policy for finite MDPs, yielding significant performance improvement over various on-policy and off-policy recent RL algorithms in many continuous control tasks. However, we observe that such an iterative implementation of the maximum entropy strategy of optimizing for policies that aim to reach states with high entropy in the future does not necessarily result in the desired exploration behavior but may yield positive feedback hindering exploration in model-free sample-based learning with function approximation. In order to overcome such limitations associated with implementation of the maximum entropy RL, we propose a max-min entropy framework for RL, which aims to learn policies reaching states with low entropy and maximizing the entropy of these low-entropy states, whereas the conventional maximum entropy RL optimizes for policies that aim to visit states with high entropy and maximize the entropy of those high-entropy states for high entropy of the entire trajectory. We implemented the proposed max-min entropy framework into a practical iterative actor-critic algorithm based on policy iteration with disentangled exploration and exploitation. It is demonstrated that the proposed algorithm significantly enhances exploration capability due to the fairness across states induced by the max-min framework and yields drastic performance improvement over existing RL algorithms including maximum-entropy SAC on difficult control tasks.
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
sections.heading: 2 Related Works
sections.text: Maximum Entropy RL: The maximum entropy framework has been considered in various RL domains: inverse reinforcement learning [58], stochastic optimal control [45, 51, 53], guided policy search [30], and off-policy learning [22, 23]. There is a connection between value-based and policy-based RL under the policy entropy regularization [38], [42] combines them, and finally [46] proves that they are equivalent. Maximum entropy RL is also related to probabilistic inference [40, 45]. Recently, maximizing the entropy of state distribution instead of the policy distribution [26] and maximizing the entropy considering the previous sample action distribution [25] have been investigated for better exploration.
  Max-Min Optimization: Max-min optimization aims to maximize the minimum of the objective function [11]. Under the convex-concave assumption, there exist many algorithms to find the solution to a max-min problem by using optimistic mirror descent [44], Frank-Wolfe algorithm [17], and Primal-Dual method [24]. However, non-convex max-min problems are more challenging [37] and there are several recent studies to find (approximate) solutions to non-convex max-min optimization problems [6, 41, 43]. This framework has been used in various optimization/control domains: fair resource allocation [31], inference [4, 56], generative adversarial network (GAN) [2, 18], robust training [33], and reinforcement learning [54].
  Exploration in RL: Exploration is one of the most important issues in model-free RL, as there is the key assumption that all state-action pairs must be visited infinitely often to guarantee the convergence ofQ-function [55]. In order to explore diverse state-action pairs in the joint state-action space, various methods have been considered in prior works: intrinsically-motivated reward based on curiosity [5, 10], model prediction error [1, 9], information gain [25, 27, 28], and counting states [32, 34]. These exploration techniques improve exploration and performance in challenging sparse-reward environments [3, 9, 12].
sections.heading: 3 Background
sections.heading: 3.1 Basic RL Setup
sections.text: We consider an infinite-horizon MDP (S,A, P, γ, r), where S is the state space, A is the action space, P is the transition probability, γ is the discount factor, and r is the bounded reward function. We assume that each action dimension is bounded. The RL agent has a policy π : S ×A → R+ ∈ Π, which chooses an action at for given state st according to at ∼ π(·|st) at each time step t, where Π is the policy space. For action at, the environment yields the reward rt := r(st, at) and the next state st+1 ∼ P (st+1|st, at). Standard RL learns policy π to maximize the discounted return Es0∼p0, τ0∼π[ ∑∞ t=0 γ trt], where τt = (st, at, st+1, at+1, · · · ) is an episode trajectory.
sections.heading: 3.2 Maximum Entropy RL and Soft Actor-Critic
sections.text: Maximum entropy RL maximizes both the expected return and the expected policy entropy simultaneously to achieve an improvement in exploration and robustness. The entropy-augmented objective function of maximum entropy RL is given by
  JMaxEnt(π) = Es0∼p0, τ0∼π [ ∞∑ t=0 γt(rt + αH(π(·|st))) ] , (1)
  whereH(π(·|s)) = Ea∼π(·|s)[− log π(a|s)] is the entropy function and α > 0 is the entropy coefficient. A key point here is that the policy entropy is included in the reward not used as an external regularizer at each time step. Thus, this maximum entropy RL framework optimizes for policies that aim to reach states on which policies have high entropy in the future [21].
  Soft actor-critic (SAC) is an efficient off-policy actor-critic algorithm to solve the maximum entropy RL problem [22]. SAC maximizes (1) based on soft policy iteration, which consists of soft policy evaluation and soft policy improvement. For this, the soft Q-value of given (st, at) is defined as
  Qπ(st, at) := rt + Eτt+1∼π [ ∞∑ l=t+1 γl−t(rl + αH(π(·|sl))) ] , (2)
  which does not include the policy entropy of the current time step but includes the sum of all future policy entropy and the sum of all current and future rewards. For given π, soft policy evaluation guarantees the convergence of soft Q-function estimation, which estimates Qπ by iteratively applying a modified Bellman operator T π to a real-valued estimate function Q : S ×A → R, given by
  T πQ(st, at) = rt + γEst+1∼P (·|st,at)[V (st+1)], where (3) V (st) = Eat∼π(·|st)[Q(st, at)− α log π(at|st)]
  and V (st) is the soft state value function. Then, at each iteration, SAC updates the policy as
  πnew = arg min π∈Π DKL
  ( π(·|st)|| exp(Qπold(st, at)/α)
  Zπold(st)
  ) (4)
  = arg max π∈Π
  Eat∼π(·|st)[Q πold(st, at)− α log π(at|st)] (5)
  where Zπold(st) is the log partition function which is a function of st only. Soft policy improvement guarantees Qπnew(st, at) ≥ Qπold(st, at) for all (st, at) ∈ S × A. Finally, soft policy evaluation and soft policy improvement are repeated. Then, any initial policy π ∈ Π converges to the optimal policy π∗, i.e., Qπ ∗ (st, at) ≥ Qπ ′ (st, at) for all π′ ∈ Π and all (st, at) ∈ S ×A, and π∗ maximizes JMaxEnt [22]. Proof of soft policy iteration assumes finite MDPs. SAC approximates the soft policy iteration by sample-based learning with function approximation in continuous-space cases.
sections.heading: 4 Motivation: Limitation of Maximum Entropy SAC in Pure Exploration
sections.text: In this section, we will consider only the maximum entropy SAC in a pure exploration setup without the reward function (the reward function r = 0 in MDPs). As seen in Sec. 3, SAC efficiently solves the maximum entropy RL problem to maximize (1) in an iterative manner based on judiciously-defined state and action value functions and the step-wise optimization cost (5). The well-defined value functions and the local cost function as such enable proof of soft policy improvement for finite MDPs in a similar way to the proof of the classical policy improvement theorem. Note that at each time step, SAC updates the policy to maximize the cost (5), composed of two terms: Eat∼π(·|st)[Qπold(st, at)] and αEat∼π(·|st)[− log π(at|st)] = αH(π(at|st)). As aforementioned, the soft Q-function contains the sum of current and future rewards and the sum of only future policy entropy. Since we consider only the entropy terms without rewards here, the first term Eat∼π(·|st)[Qπold(st, at)] is the current estimate of the sum of future entropy when action at is taken from policy π at state st, whereas the second term αH(π(at|st)) is the entropy of the policy π itself. Hence, at each time step, SAC tries to update the policy π to yield the maximum sum of the estimated future entropy and the policy entropy itself. Here, the term Eat∼π(·|st)[Qπold(st, at)] plays the role of guiding the policy towards the direction of high future entropy.
  Saturation: In sample-based update with function approximation, however, the SAC iteration does not yield the desired result, contrary to the intention behind maximum entropy. To see this, let us consider a pure exploration task in which there is no reward. The considered task is a 100 × 100 continuous 4-room maze proposed in [25], modified from the continuous grid map available at https://github.com/huyaoyu/GridMap. Fig. 1(a) shows the maze environment, where state is the (x, y)-position of the agent in the map, action is (dx, dy) bounded by [−1, 1]× [−1, 1], and the next state of the agent is (x + dx, y + dy). Starting from the left-lower corner (0.5, 0.5), the agent explores the maze without any external reward. First, note that for this pure exploration task, the optimal policy maximizing JMaxEnt(π) is given by the uniform policy that selects all actions in A = [−1, 1]× [−1, 1] uniformly regardless of the value of st. This is because the uniform distribution has maximum entropy for a bounded space [13]. Then, we compare the exploration behaviour of SAC and the uniform policy in the maze task. Fig. 1(b) shows the mean accumulated number of different visited states averaged over 30 random seeds as time goes, where the shaded region in the curve represents standard deviation (1σ) from the mean and a different state is meant as a nonoverlapping quantized 1× 1 square. As seen in Fig. 1(b), SAC explores more states than the uniform policy at the early stage of learning. As learning progresses, however, SAC fails to visit new states after 300k time steps, whereas the uniform policy continues visiting new states. As a result, SAC eventually visits fewer states than the uniform policy on average. The result shows that SAC fails to converge to the optimal uniform policy and its performance become saturated.
  Narrow Exploration Radius: To examine the saturation behavior of SAC in the above pure exploration task, we investigate the policy update of SAC in (5). Since the current Q-function estimate (implemented by a neural network) replaces Qπold in (5) in implementation with function approximation, the policy update is rewritten as
  arg max π∈Π {Eat∼π(·|st)[Q(st, at)] + αH(π(·|st))}. (6)
  As mentioned already, the first term Eat∼π(·|st)[Q(st, at)] is the current estimate of the sum of future entropy in this pure exploration case when action at is taken from policy π at state st, whereas the second term αH(π(at|st)) is the entropy of the policy π itself. The first term Eat∼π(·|st)[Q(st, at)] intends to direct the policy towards the direction of high future entropy. Note that maximizing the second term already yields the uniform policy, but the Q-function term affects the policy update. In order to see how the Q-function term actually affects the policy update, we differentiate the entropy coefficient α in the policy update part (5) or (6) as the policy entropy coefficient απ and that in the soft value function part (2) and (3) as the value entropy coefficient αQ. We fix απ as απ = 1 and change αQ as 0, 0.1, and 1 (note that the case of αQ = 1 is original SAC). With this change of αQ, we conducted the same pure exploration maze task. Fig. 1(c) shows the average norm of the gradient of Q-function with respect to action, i.e., Est∼D[||∇aQ(st, a)|a=at ||] over time with at ∼ π(·|st) and st from a mini-batch drawn from the replay buffer D of SAC update, where the Q neural network weights were initialized randomly. Fig. 1(d) shows the histogram of states that the policy visits over 50k time steps starting from 300k, 350k, 400k, and 450k time steps. When αQ = 0 with no reward, the Q-function update by the Bellman operator T π in (3) is trivial as Q(s, a)← Es′∼P (·|s,a),a′∼π(·|s′)[Q(s′, a′)], i.e., replacement. When the initial Q(s, a) is (nearly) flat over S × A by initial random weight assignment for the Q-neural network, the flat Q is maintained by this trivial update. Indeed, it is seen in Fig. 1(c) that Est∼D[||∇aQ(st, a)|a=at ||] with at ∼ π(·|st) is nearly zero across all time for αQ = 0. With a flat function Q(st, ·) ≈ c over the action space A, the first term Eat∼π(·|st)[Q(st, at)] in (6) does not affect the policy update, only the second termH(π(·|st)) works, and thus the policy update yields π to converge to the uniform policy for every state maximizing the total entropy. Hence, the exploration radius in the case of αQ = 0 is almost the same as that of the uniform policy, as seen in Fig. 1(d). When αQ > 0, on the other hand, the Q-function starts to be updated nontrivially by the Bellman operator T π in (3) due to the − log π(at+1|st+1) term in V (st+1) in (3), with π given by the current policy. It is now seen in Fig. 1(c) that Est∼D[||∇aQ(st, a)|a=at ||] is not zero anymore and the gradient norm becomes larger as αQ increases from 0.1 to 1.0. Non-zero Est∼D[||∇aQ(st, a)|a=at ||] means that Q(st, ·) as a function of action at for given st is not flat anymore and the first term in (6) affects the policy update so that the policy is updated for the direction of high Q-value (with intention for high future entropy) as well
  as high policy entropy H(π). As seen in Fig. 1(d), however, the exploration radius reduces as αQ increases from 0 to 1. The iteration process does not evolves for wider exploration as intended.
sections.heading: 5 Methodology
sections.heading: 5.1 A Deeper Look at Pure Exploration
sections.text: In order to propose our new approach overcoming the limitation of SAC implementation of the maximum entropy framework, we first take a deeper look at how the Q-function term in (6) hinders exploration, as SAC (with απ = αQ = 1) learns the maze task. For this, we consider four 2 × 2 squares centered at (5, 5), (10, 10), (20, 20), and (30, 30) in the 100×100 maze, where every episode starts from (0.5,0.5). Fig. 2(a) shows the number of accumulated visits to each square as time elapses. Figs. 2(b) and 2(c) show the estimated Q value and the average empirical entropy of each square, respectively, as time goes. For Fig. 2(b), every 1000 time steps, we sampled 1000 states uniformly from each square and an action from the current policy for each sampled state, and computed the Q-value average over the 1000 state-action samples for each square. Then, we computed the mean value of the four average values of the four squares. Fig. 2(b) shows the average Q value of each square relative to the four-square mean value as time goes. For Fig 2(c), every 1000 time steps, we sampled 1000 states uniformly from each square and computed the average empirical entropy Est [Eat∼π(·|st)[− log π(at|st)]] of the current policy π at time t averaged over the 1000 sampled states {st} from each square. The upper row of Fig. 2(d) shows the cross-section of the estimate Q-function Q(s, a) along the diagonal action line from (−1,−1) to (1, 1) at the center state s of each square, as time goes, where each curve is shifted in y-axis so that the mean value averaged over samples along the action line is matched to zero in y-axis. The lower row of Fig. 2(d) shows the value of log π(a|s) of the current policy π at time step t along the diagonal action line from (−1,−1) to (1, 1) at the center state s for each square as time goes, where the curve is shifted in y-axis to match the mean value to zero in y-axis.
  First, note from Fig. 2(a) that the farther a state is from the starting point (0.5, 0.5), the less the agent visits the state, and the visitation difference is large. At the early stage of learning starting with random Q-network weight initialization and random policy-network weight initialization, there is little Q-value difference with respect to either state or action, as seen in Figs. 2(b) and 2(d), so the entropy term is dominant in the policy update (6) and the policy entropy increases with the policy distribution approaching the uniform distribution, as seen in Fig. 2(c). As time goes, learning of
  the Q-function with the Bellman backup (3) progresses. Basically, the Bellman backup (3) with no reward adds ∆Qt = γ{Eat+1∼π(·|st+1)[Q(st+1, at+1)] + αH(π(·|st+1))} −Q(st, at) to Q(st, at) for every (st, at) ∈ S×A. However, this is approximated in practical RL. In sample-based off-policy learning with function approximation, RL typically stores visited state-action pairs in the replay buffer D and the above Bellman backup is approximated as updating the Q-function by minimizing the loss E(st,at)∼D[(Q(st, at)−Qtarget(st, at))2] based on a mini-batch uniformly drawn from the buffer. Under this off-policy learning with experience replay, when the initial Q-function is roughly flat and small, ∆Qt soon becomes positive (the policy update increases the entropy of the visited states and ∆Qt soon becomes positive for the visited states), and hence the Q-values of frequently-visited states are updated more and thus have higher Q-values as seen in Fig.2(b). This is because these states are stored more into D and sampled more from D at mini-batch generation. Then, the initial Q-value difference biases the policy to visit the states with high Q-values more frequently than the states with low Q-values because the policy is updated to choose actions that maximizes the expectation of Q-value Eat∼π(·|st)[Q(st, at)] in the policy update (6). This is evident in the Fig. 2(d), which shows the estimate of Q-function and the value of log π along the diagonal line. At the early stage of learning (10k time step in the figure), Q-function is roughly flat and the policy is almost close to the uniform distribution for the action line. As the time steps go on, the Q-values of actions close to (−1,−1) becomes higher than the Q-value of actions near (1, 1) due to the off-policy learning with experience replay, as explained above. Then, the policy is updated to choose actions with high Q-values more frequently to maximize the Q-value expectation, so the probability of choosing action (−1,−1) towards the left-lower corner becomes higher than that of action (1, 1) for the opposite direction. As the policy distribution leans toward a certain action and becomes asymmetric away from uniformity, the policy entropy decreases further. As seen in Fig. 2(c), the speed of the policy entropy decrease varies depending on the Q-value difference along the action line in Fig. 2(d), and the policy entropy difference deepens the Q-value difference between states in Fig. 2(b) because the Q-value estimates the policy entropy sum of future states. This positive feedback continues until saturation, as seen in Fig. 2(b), and it results in the narrow exploration radius in Fig. 1(d) because the policy will be forced to visit states with high Q-values only. Note that this positive feedback reduces the policy entropy due to the Q-value difference, contrary to the intention behind maximum entropy.
sections.heading: 5.2 Max-Min Entropy RL
sections.text: In order to break the unwanted positive feedback loop occurring when implementing the maximum entropy framework (i.e., max-max entropy framework) in the previous subsection, we must reduce the policy entropy difference between states to reduce the Q-value difference between states in the feedback loop. For this, we aim to learn the Q-function so that the policy visits states with low entropy, and the policy update increases the policy entropy of these low-entropy states. Under this principle, we propose a new max-min entropy (MME) framework that aims to learn the Q-function to estimate the negative sum of policy entropy, while maintaining the policy entropy maximization term H(π(·|st)) in the policy update to increase the policy entropy of the visited states. Thus, we define the reversed soft Q-function QπR(st, at) for MME as
  QπR(st, at) := rt + Eτt+1∼π [ ∞∑ l=t+1 γl−t(rl − αQH(π(·|sl))) ] , (7)
  whereas the original soft Q-function of SAC in (2) is given by
  Qπ(st, at) := rt + Eτt+1∼π [ ∞∑ l=t+1 γl−t(rl + απH(π(·|sl))) ] .
  Note that the original soft Q-function Qπ adds the policy entropy to the reward and drives the policy to visit states with high entropy. On the other hand, our reversed soft Q-function subtracts the policy entropy from the reward and drives the policy to visit states with low entropy. In this sense, we call QR as the “reversed” soft Q-function because it desires the reverse behavior of soft Q-function.
  Then, QπR is estimated by a real-valued function QR : S ×A → R based on a Bellman operator T πR : T πRQR(st, at) = rt + γEst+1∼P (·|st,at)[VR(st+1)], (8) where VR(st) = Eat∼π(·|st)[QR(st, at) + αQ log π(at|st)] is the reversed soft state value function. At each iteration, the policy of MME is updated as
  πnew = arg max π∈Π
  Eat∼π(·|st)[Q πold R (st, at)− απ log π(at|st)], (9)
  where QπoldR is substituted by the estimate function QR at the iteration. Then, in pure exploration with no reward rt = 0,∀t, the policy of MME will visit the states with low entropy due to the first term Eat∼π(·|st)[Q πold R (st, at)], and the policy entropy of those states will increase by the second term Eat∼π(·|st)[− log π(at|st)] = H(π(·|st)), as we intended. Note that the behaviour of the proposed method follows the max-min principle [11], so we expect that our MME fairly increase the policy entropy of all states based on the fairness perspective of max-min optimization, whereas SAC increases the policy entropy of states with high entropy only. The MME is expected to reduce the entropy difference and the Q-value difference between states to reduce the unwanted feedback loop and solve the saturation problem. Furthermore, SAC considers the same entropy coefficient απ for its policy update and the soft Q-function Qπ , but our MME distinguishes the policy entropy coefficient απ in the policy update (9) and the value-entropy coefficient αQ in the reversed soft Q-function QπR in (7), as we experimented in Section 4. Changing αQ and απ allows for us to control the amount of the reversed Q-function in the policy update, and it will determine the ratio between the exploration due to the policy entropy and the exploration due to the reversed soft Q-function.
  In actual implementation, the negative entropy in (7) is plus-offsetted to make the Q-update increase the Q-value. The detailed implementation and algorithm of MME are provided in Appendix A.
sections.heading: 5.3 Disentangled Exploration and Exploitation for Rewarded Setup
sections.text: In the previous subsection, we considered the problem from a pure exploration perspective. However, the ultimate goal of RL is to maximize the sum of rewards in rewarded environments, and the goal of exploration is to receive higher rewards without falling into local optima. With non-zero reward in (7) - (9), the policy will not only visit states with low entropy but also states with higher return. In this case, the reward and the entropy are intertwined in the Q-function and then it is difficult to expect the intended MME exploration behavior through the intertwined Q-function. Therefore, we disentangle exploration from exploitation for rewarded setup, as considered in several previous works [7, 49], and propose disentangled MME (DE-MME) for rewarded setup. For this, we consider two policies: pure exploration policy πE that samples actions for pure exploration as described in Sec. 5.2, and target policy πT that actually interacts with the environment. We decompose the reversed soft Q-function QπR in (7) into two terms Q π R = Q π R,R +Q π R,E , where Q π R,R is the expected current and future reward sum considered in standard RL and QπR,E is the expected sum of future entropy:
  QπR,R(st, at) = rt + Eτt+1∼π
  [ ∞∑
  l=t+1
  γl−trl ] , QπR,E(st, at) =−αQEτt+1∼π [ ∞∑
  l=t+1
  γl−tH(π(·|st)) ] .
  Then, we update the policy πE for pure exploration as
  πE,new = arg max π′∈Π
  Eat∼π′(·|st) [ Q πE,old R,E (st, at)− απ log π ′(at|st) ] . (10)
  Note that increasing the expectation of QπE,oldR,E makes the policy visit states with low entropy of πE , as we intended in the pure exploration case in Sec. 5.2. Finally, we update the target policy πT by using QπE,oldR,E as
  πT,new = arg max π′∈Π
  Eat∼π′(·|st) [ Q πT,old R,R (st, at) +Q πE,old R,E (st, at)− απ log π ′(at|st) ] . (11)
  For implementation, QπT,oldR,R and Q πE,old R,E are estimated by real-valued functions QR,R and QR,E based on their own Bellman operators (see Appendix A). Note that the policy update (9) in Sec. 5.2 can be expressed as maximizing Eat∼π′(·|st)[Q πT,old R (st, at)− απ log π′(at|st)] over the target policy, where QπT,oldR = Q πT,old R,R +Q πT,old R,E . Thus, we can view that the policy update in (11) replaces Q πT,old R,E in the previous policy update (9) withQ πE,old R,E to disentangle exploration from exploitation. In this way, the policy update (11) will simultaneously increase the expectation of QπT,oldR,R to maximize the reward sum, the expectation of QπE,oldR,E to visit states with low entropy, and the policy entropy for diverse action. The detailed implementation and algorithm for DE-MME are provided in Appendix A.
sections.heading: 6 Experiments
sections.text: We provide numerical results to show the performance of the proposed MME and DE-MME in pure exploration and various control tasks. We provide source code for the proposed method at
  http://github.com/seungyulhan/mme/ that requires Python Tensorflow. For all plots, the solid line represents the mean over random seeds and the shaded region represents 1 standard deviation from the mean.
  6.1 Pure Exploration
  To see how the proposed method behaves in pure exploration, we considered the maze task described in Sec.4 again. We compared the exploration performance of MME in Sec.5.2, SAC, and the uniform policy. For MME, we considered several αQ ∈ {0.1, 0.2, 0.5, 1, 2, 5, 10} with απ = 1. Fig. 3(a) in the next page shows the mean number of accumulated quantized visited states averaged over 30 random seeds corresponding to Fig. 1(b), and Fig. 3(b) shows the
  histogram of visited states, of which setup is the same as Fig.1(d). As seen in Fig. 3(a), the proposed MME visits much more states than SAC or the uniform policy. In addition, we observe that MME continues discovering new states throughout the learning, while SAC rarely visits new states as learning progresses. As seen in Fig. 3(b), MME explores far and rare states as compared to SAC or the uniform policy, and this leads to a large enhancement in exploration performance, as intended in Sec. 5.2. Note that the larger αQ in update (7) (9) with rt = 0, the stronger is the effect of the Q-function term to visit states with low entropy and the weaker is the effect of the policy entropy term to explore widely in the action space, as we expected in Section 5.2. Hence, there is a trade-off between the two terms and αQ = 0.5 seems best in the maze task when απ = 1.0, as seen in Fig. 3(a). Thus, the result clearly shows why we distinguish the policy entropy coefficient απ and the value entropy coefficient αQ for MME, whereas SAC uses the common entropy coefficient α = απ = αQ. We also plotted the Q-value difference and the empirical entropy of the four squares centered at (5,5), (10,10), (20,20) and (30,30) for MME, as done in Figs. 2(b) and 2(c). The result is shown in Fig. 4. It is seen that the Q-value difference and the entropy difference among the states are clearly reduced as compared to Figs. 2(b) and 2(c). It means that MME breaks the unwanted positive feedback loop and improves the policy entropy of diverse states more uniformly as compared to SAC in terms of fairness under our max-min framework. This leads to better exploration, as seen in Fig 3.
sections.heading: 6.2 Performance in Rewarded Environments
sections.text: As mentioned in Sec.5.3, the ultimate goal of RL is to maximize the reward sum in rewarded environments and exploration is one of the means to achieve this goal. Based on the enhanced
  exploration performance of MME, we expect MME/DE-MME to show good performance in rewarded environments too. In order to verify this, we considered three types of difficult control tasks for which current state-of-the-art RL algorithms do not show satisfactory performance: Two types of sparse-reward tasks (SparseMujoco tasks and DelayedMujoco tasks) and high dimensional Humanoid tasks. SparseMujoco [27, 35] is a sparse version of Mujoco [52] in OpenAI Gym [8], and the reward is 1 if the agent crosses the x-axis threshold τ , otherwise 0. DelayedMujoco [19, 57] is a delayed version of Mujoco in which the reward is accumulated for D time steps and the agent receives the accumulated reward sum once every D time steps. During the accumulation time, the agent receives no reward. These sparse-reward environments have widely been considered as challenging environments for validating the performance of exploration in many previous works [9, 25, 27].
  First, we compared the performance of MME algorithms to that of maximum entropy SAC in the sparse-reward tasks. For MME, we considered two versions: vanilla MME proposed in Sec.5.2, and disentangled MME (DE-MME) proposed in Sec.5.3. For MME/DE-MME, we fixed απ of MME and DE-MME to be equal to α of SAC, and chose proper αQ for each task. Detailed experimental setup is provided in Appendix B. Figs. 5 and 6 show the performance averaged over 10 random seeds on SparseMujoco tasks and 5 random seeds on DelayedMujoco tasks, respectively. It is seen that the proposed MME shows much higher performance than SAC in the considered environments with rewards. It is also seen that MME itself performs well enough in most environments but DE-MME indeed yields performance gain over vanilla MME and the gain is large in SparseWalker. Thus, disentanglement of exploration from exploitation is beneficial to MME for better reward performance in rewarded environments, as discussed in Sec.5.3. We provided the corresponding max average return tables in Appendix C and ablation study for further analysis in Appendix D. There, one of ablation study empirically shows that the performance enhancement by MME is caused by improved exploration of MME as we intended.
  Finally, we compared the performance of MME/DE-MME to that of popular general RL algorithms and recent exploration methods on the considered sparse-reward environments (SparseMujoco and DelayedMujoco tasks) and dense-reward high-dimensional Mujoco tasks (Humanoid, HumanoidStandup). We considered several action-based exploration methods: SAC combined with divergence [27] (SAC-Div) and diversity actor-critic (DAC) [25], and state-based exploration methods with random network distillation (RND) [9] and MaxEnt (State) [26]. For general RL algorithms, we considered several on-policy RL algorithms: proximal policy optimization (PPO) [48] and trust-region policy optimization (TRPO) [47], and entropy-based off-policy RL algorithms: soft Q-learning (SQL) [21] and SAC [22]. We provided detailed explanation and implementation for each algorithm in Appendix C. Table 1 summarizes the max average return result. It is seen that MME/DE-MME have superior performance to other methods.
sections.heading: 7 Conclusion
sections.text: In this paper, we have proposed a MME framework for RL to resolve the unwanted exploration behavior of maximum entropy RL in off-policy learning with function approximation. In pure exploration, to implement MME, we train the Q-function to visit states with low entropy contrary to the maximum entropy strategy, while maintaining the policy entropy maximization term in the policy update. Then, we extended MME to rewarded environments. In rewarded environments we disentangle exploration from exploitation for MME to explore diverse states as in pure exploration as well as to achieve high return. Numerical results show that the proposed MME explores farther and wider in the state space than maximum entropy realization, alleviates possible positive feedback of off-policy maximum entropy learning, and yields a significant enhancement in exploration and final performance over existing RL methods in various difficult tasks. As for potential impacts, RL can be applied to sensitive areas that require control, such as drone control. However, it is only a risk that RL itself has, and it is not very relevant to the work that we are trying to address in this paper.
sections.heading: 8 Acknowledgement
sections.text: This work is supported by Center for Applied Research in Artificial Intelligence (CARAI) grant funded by Defense Acquisition Program Administration (DAPA) and Agency for Defense Development (ADD) (UD190031RD). Dr. Seungyul Han is currently with AI Graduate School of UNIST and his work is partly supported by Artificial Intelligence Graduate School support (UNIST), Institute of Information & Communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No.2020-0-01336).
title: A Max-Min Entropy Framework for Reinforcement Learning