summaries: The paper studies multinomial logistic (MNL) regression bandits, a generalization of binary logistic bandits. It differs from previous works on MNL bandits by considering a different decision-making process. That is, the authors do not address the combinatorial action selection of previous MNL bandits, but rather study the problem setting where the agent offers a single item, but with K different outcomes.   The paper introduces a UCB-based algorithm for this problem, for which the authors establish a sub-linear regret bound. By building on recent advances in logistic bandits, they improve the prohibitive impact of the constant \kappa from both the design of their algorithm and its theoretical guarantees.

summaries: This paper presents MNL-UCB Algorithm for contextual MNL bandits problem. At every step, the algorithm estimates a K-tuple of parameter vectors in the confidence region. Specifically, they prove that the regret of MNL-UCB scales as \tilde{O}(dK\sqrt{\kappa}\sqrt{T}) where $\kappa$ is a parameter that captures the degree of (non)-smoothness of the MNL model. It improves the constant from linear in \kappa to \sqrt{\kappa}. They further improved algorithm that achieves a regret bound with problem-dependent constant \kappa being pushed into a second order term.  Compared to the most existing work, a major difference is that each choice is associated with a different parameter so a matrix of parameters needs to be learned.

summaries: This paper considers a version of stochastic contextual bandits where the rewards are drawn from a discrete distribution governed by a multionimal logit model. This setting is motivated by applications in online advertising where the user may give various feedbacks in the face of a recommendation beyond a binary ‘clicked’ or ‘did not click’ – e.g. ‘show me again later’, ‘never show me again’. The authors propose and analyse a UCB algorithm for this problem with the confidence sets being based on the work of Faury et al. (2020, ICML) and the regret analysis being based on that of Abbasi-Yadkori et al. (2011, NeurIPS). The particular advantage of utilising the concentration results of Faury et al is that the regret of the resulting algorithm scales favourably (square root order) with respect to a parameter $\kappa$ characterising the smoothness of the logit function around the true parameter. A further algorithm whose dependence on $\kappa$ is relegated to lower order terms w.r.t. the horizon is also developed – however this approach is computationally intractable. In the related (binary) logistic bandit setting, some popular algorithms have been shown to have exponential order dependence on this parameter and the design of algorithms which are robust to its value is useful. It may be useful to note that this version of a multinomial bandit is different from the combinatorial problem in the dynamic assortment selection literature (e.g. Agrawal et al (2017, 2019)) where the different outcomes represent different items.

summaries: The paper studies multinomial logistic regression bandit problem, where the number of outcomes can be greater than two. This is an extension of the well-studied generalized linear bandit problem with two outcomes (e.g., clicks and no-clicks). The authors first propose the problem setup with real-life motivated scenarios and then propose a UCB based algorithm to minimize cumulative regret. The authors analyze its performance and derive an upper bound of \tilde{O}(dK\sqrt{\kappa T}), where d is the dimension of the action space, (K + 1) is the number of outcomes, T is the number of interactions, and \kappa is the degree of non-smoothness, which is inherent to the multi-nomial problem. At the end, the authors provide a simulation based study which supports their theoretical insights.

abstractText: Out of the rich family of generalized linear bandits, perhaps the most well studied ones are logistic bandits that are used in problems with binary rewards: for instance, when the learner aims to maximize the profit over a user that can select one of two possible outcomes (e.g., ‘click’ vs ‘no-click’). Despite remarkable recent progress and improved algorithms for logistic bandits, existing works do not address practical situations where the number of outcomes that can be selected by the user is larger than two (e.g., ‘click’, ‘show me later’, ‘never show again’, ‘no click’). In this paper, we study such an extension. We use multinomial logit (MNL) to model the probability of each one of K+1 2 possible outcomes (+1 stands for the ‘not click’ outcome): we assume that for a learner’s action xt, the user selects one of K + 1 2 outcomes, say outcome i, with a MNL probabilistic model with corresponding unknown parameter ✓̄⇤i. Each outcome i is also associated with a revenue parameter ⇢i and the goal is to maximize the expected revenue. For this problem, we present MNL-UCB, an upper confidence bound (UCB)-based algorithm, that achieves regret Õ(dK p T ) with small dependency on problemdependent constants that can otherwise be arbitrarily large and lead to loose regret bounds. We present numerical simulations that corroborate our theoretical results.

authors:
Y. Abbasi-Yadkori
D. Pál
C. Szepesvári

title: Improved algorithms for linear stochastic bandits

venue: Advances in Neural Information Processing Systems, pages 2312–2320.

authors:
M. Abeille
L. Faury
C. Calauzènes

title: Instance-wise minimax-optimal algorithms for logistic bandits

venue: In International Conference on Artificial Intelligence and Statistics,

authors:
M. Abeille
A Lazaric

title: Linear thompson sampling revisited

venue: Electronic Journal of Statistics,

authors:
P. Agrawal
V. Avadhanula
T. Tulabandhula

title: A tractable online learning algorithm for the multinomial logit contextual bandit

venue: arXiv preprint arXiv:2011.14033.

authors:
S. Agrawal
V. Avadhanula
V. Goyal
A. Zeevi

title: Thompson sampling for the mnl-bandit

venue: Conference on Learning Theory, pages 76–78.

title: Mnl-bandit: A dynamic learning approach to assortment selection

venue: Operations Research, 67(5):1453–1485.

authors:
O. Avner
S. Mannor

title: Multi-user communication networks: A coordinated multi-armed bandit approach

venue: IEEE/ACM Transactions on Networking, 27(6):2192–2207.

authors:
F. Berkenkamp
A. Krause
A.P. Schoellig

title: Bayesian optimization with safety constraints: safe and automatic parameter tuning in robotics

venue: arXiv preprint arXiv:1602.04450.

authors:
A. Berman
R.J. Plemmons

title: Nonnegative matrices in the mathematical sciences

venue: SIAM.

authors:
X. Chen
Y. Wang
Y. Zhou

title: Dynamic assortment optimization with changing contextual information

venue: arXiv preprint arXiv:1810.13069.

authors:
W.C. Cheung
D. Simchi-Levi

title: Thompson sampling for online personalized assortment optimization problems with multinomial logit choice models

venue: Available at SSRN 3075658.

authors:
V. Dani
T.P. Hayes
S.M. Kakade

title: Stochastic linear optimization under bandit feedback

venue: Conference on Learning Theory.

authors:
K. Dong
Y. Li
Q. Zhang
Y. Zhou

title: Multinomial logit bandit with low switching cost

venue: arXiv preprint arXiv:2007.04876.

authors:
S. Dong
B. Van Roy

title: An information-theoretic analysis for thompson sampling with many actions

venue: Advances in Neural Information Processing Systems, pages 4157–4165.

authors:
L. Faury
M. Abeille
C. Calauzènes
O. Fercoq

title: Improved optimistic algorithms for logistic bandits

venue: arXiv preprint arXiv:2002.07530.

authors:
S. Filippi
O. Cappe
A. Garivier
C. Szepesvári

title: Parametric bandits: The generalized linear case

venue: Advances in Neural Information Processing Systems, pages 586–594.

authors:
D. Gamarnik
J. Gaudio

title: Estimation of monotone multi-index models

venue: arXiv preprint arXiv:2006.02806.

authors:
R.A. Horn
C.R. Johnson

title: Matrix analysis

venue: Cambridge university press.

authors:
T. Lattimore
C. Szepesvári

title: Bandit algorithms

venue: Cambridge University Press.

authors:
L. Li
Y. Lu
D. Zhou

title: Provably optimal algorithms for generalized linear contextual bandits

venue: arXiv preprint arXiv:1703.00048.

authors:
S. Li
F. Hao
M. Li
Kim
H.-C.

title: Medicine rating prediction and recommendation in mobile social networks

venue: International conference on grid and pervasive computing, pages 216–223. Springer.

authors:
Oh
M.-h.
G. Iyengar

title: Thompson sampling for multinomial logit contextual bandits

venue: Advances in Neural Information Processing Systems, pages 3151–3161.

authors:
P. Rusmevichientong
J.N. Tsitsiklis

title: Linearly parameterized bandits

venue: Mathematics of Operations Research, 35(2):395–411.

authors:
D. Russo
B. Van Roy

title: Eluder dimension and the sample complexity of optimistic exploration

venue: In Advances in Neural Information Processing Systems,

title: Learning to optimize via posterior sampling

venue: Mathematics of Operations Research, 39(4):1221–1243.

authors:
Y. Sui
V. Zhuang
J.W. Burdick
Y. Yue

title: Stagewise safe bayesian optimization with gaussian processes

venue: arXiv preprint arXiv:1806.07555.

authors:
T. Sun
Q. Tran-Dinh

title: Generalized self-concordant functions: a recipe for newton-type methods

title: Inequalities for the minimum eigenvalue of m-matrices

venue: The Electronic Journal of Linear Algebra, 20.

authors:
Q. Tran-Dinh
Li
Y.-H.
V. Cevher

title: Composite convex minimization involving selfconcordant-like cost functions

venue: Modelling, Computation and Optimization in Information Systems and Management Sciences, pages 155–168. Springer.

authors:
Y. Wang
X. Chen
Y. Zhou

title: Near-optimal policies for dynamic multinomial logit assortment selection models

venue: Advances in Neural Information Processing Systems, pages 3101–3110.

authors:
Z. Yang
K. Balasubramanian
Z. Wang
H. Liu

title: Learning non-gaussian multi-index model via second-order stein’s method

venue: Advances in Neural Information Processing Systems, 30:6097–6106.

text:
p T ) with small dependency on problem-
dependent constants that can otherwise be arbitrarily large and lead to loose regret bounds. We present numerical simulations that corroborate our theoretical results.

heading: 1 Introduction

text:
Linear stochastic bandits provide simple, yet commonly encountered, models for a variety of sequential decision-making problems under uncertainty. Specifically, linear bandits generalize the classical multi-armed bandit (MAB) problem of K arms that each yields reward sampled independently from an underlying distribution with unknown parameters, to a setting where the expected reward of each arm is a linear function that depends on the same unknown parameter vector Dani et al. (2008); Abbasi-Yadkori et al. (2011); Rusmevichientong and Tsitsiklis (2010). Linear bandits have been successfully applied over the years in online advertising, recommendation services, resource allocation, etc. Lattimore and Szepesvári (2020). More recently, researchers have explored the potentials of such algorithms in more complex systems, such as in robotics, wireless networks, the power grid, medical trials, e.g., Li et al. (2013); Avner and Mannor (2019); Berkenkamp et al. (2016); Sui et al. (2018). However, linear bandits fail to model a host of other applications. This has called for extensions of linear bandits to a broader range of reward structures beyond linear models. One of the leading lines of work addressing these extensions relies on the Generalized Linear Model (GLM) framework of statistics. In GLMs the expected reward associated with an arm x is given by µ(✓̄Tx), where ✓̄ 2 Rd is the system unknown parameter and µ is a non-linear link function. Specifically, logistic bandits, that are appropriate for modeling binary reward structures, are a special case of generalized linear bandits (GLBs) with µ(x) = (1 + exp( x)) 1. UCB-based algorithms for GLBs were first introduced in Filippi et al. (2010); Li et al. (2017); Faury et al. (2020). The same problem, but with a Thompson Sampling- (TS) strategy was also studied in Abeille et al. (2017);
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Russo and Van Roy (2013, 2014); Dong and Van Roy (2018). Beyond GLMs, an even more general framework for modeling reward is the semi-parametric index model (see for example Yang et al. (2017); Gamarnik and Gaudio (2020) for a list of applications in statistics). A semi-parametric index model relates the reward y 2 R and the action/arm x 2 Rd as y = µ(✓̄T1 x, ✓̄ T 2 x, . . . , ✓̄ T Kx) + ✏, where µ : RK ! R and ✓̄1, . . . , ✓̄K 2 Rd are K system’s unknown parameters. GLBs are special cases of this for K = 1, also known as single-index models (SIM) in statistics. In this paper, we formulate an extension of the problem of binary logistic bandits (i.e., a special case of SIM) to multinomial logit (MNL) bandits, a special case of multi-index models (MIM) to account for settings with more than two possible outcomes on the user choices (K 1). For this model, we present an algorithm and corresponding regret bound. Our algorithmic and analytic contribution is in large inspired by recent exciting progress on binary logistic bandits by Faury et al. (2020).
To motivate MNL bandits, consider ad placement. When an ad is shown to a user, the user may have several options to react to the ad. For example, she can choose to 1) click on the ad; 2) click on “show me later”; 3) click on “never show me this ad”; 4) not click at all, etc. The user selects each of these options based on an unknown probability distribution that inherently involves linear combinations of the selected feature vector denoting the ad and unknown parameters denoting the user’s preferences about the ad. In this setting, each option is associated with a specific notion of reward. The agent’s goal is to determine ads with maximum expected rewards to increase the chance of a successful advertisement.
Outline. In Section 1.1, we formally define the problem. In Sections 2.1, 2.2 and 2.4, we elaborate on the challenges that the generalization of the Logistic-UCB-1 by Faury et al. (2020) to the settings with MIM rewards brings to our theoretical analysis. We then summarize our proposed MNL-UCB in Algorithm 1 and provide a regret bound for it in Section 2.5. In Section 3, we present a detailed discussion on the challenges and computation of necessary problem-dependent constants. Finally, we complement our theoretical results with numerical simulations in Section 4.
Notation. We use lower-case letters for scalars, lower/upper-case bold letters for vectors/matrices. kxk2 denotes the Euclidean norm and x T y inner product. ij denotes the Kronecker delta, i.e., ij = 1 if i 6= j and ij = 0 if i = j. A⌦B denotes the Kronecker product. For square matrices A and B, we use A B to denote B A is positive semi-definite. We denote the minimum and maximum eigenvalues of A by min(A) and max(A). For A ⌫ 0, the weighted 2-norm of ⌫ with respect to A is defined byk⌫k
A =
p
⌫TA⌫. For positive integers n and m  n, [n] and [m : n] denote the sets {1, 2, . . . , n} and {m, . . . , n}, respectively. For any ⌫ 2 RKd, ⌫̄i = ⌫ [(i 1)d+1:d] 2 Rd denotes the vector containing the i-th set of d entries of ⌫. We use 1 and ei to denote the vector of all 1’s and the i-th standard basis vector, respectively. Finally, we use Õ for big-Oh notation that ignores logarithmic factors.

heading: 1.1 Problem formulation

text:
Reward Model. The agent is given a decision set1 D ⇢ Rd. At each round t, the agent chooses an action xt 2 D and observes the user purchase decision yt 2 [K] [ {0}. Here, {0} denotes the “outside decision”, which means the user did not select any of the presented options. The agent’s decision at round t is based on the information gathered until time t, which can be formally encoded in the filtration Ft := (F0, ({xs, ys}t 1s=1)), where F0 represents any prior knowledge. Let each option i 2 [K] be associated with an unknown vector ✓̄⇤i 2 Rd and let ✓⇤ = [✓̄ T ⇤1, ✓̄ T ⇤2, . . . , ✓̄ T ⇤K ] T 2 RKd. The user’s choice of what to click on is given by a multinomial logit (MNL) choice model. Under this model, the probability distribution of the user purchase decision is given by
P(yt = i|xt,Ft) :=
8 >><
>>:
1
1+ PK j=1 exp( ¯✓ T ⇤jxt) , if i = 0,
exp( ¯✓ T
⇤ixt)
1+ PK j=1 exp( ¯✓ T ⇤jxt) , if i 2 [K].
(1)
When the user clicks on the i-th option, a corresponding reward ⇢i is revealed to the agent and we set ⇢0 = 0. Then, the expected reward observed by the agent when she plays action xt is
1Our results extend easily to time-varying decision sets.
E[Rt|xt,Ft] = PK j=1 ⇢j exp( ¯✓ T ⇤jxt)
1+ PK j=1 exp( ¯✓ T ⇤jxt) = ⇢T z(xt,✓⇤), where ⇢ = [⇢1, ⇢2, . . . , ⇢K ]T , z(xt,✓⇤) =
[z1(xt,✓⇤), z2(xt,✓⇤), . . . , zK(xt,✓⇤)]T , and
zi(xt,✓⇤) = P(yt = i|xt,Ft), 8i 2 [K]. (2)
Note that E[Rt|xt,Ft] = µ(✓̄ T ⇤1x, ✓̄ T ⇤2x, . . . , ✓̄ T ⇤Kx) is not directly a generalized linear model, i.e., a function µ(✓̄T⇤ xt), but rather it is a multi-index model, where µ : RK ! R. Goal. Let T be the total number of rounds and x⇤ be the optimal action that maximizes the reward in expectation, i.e., x⇤ 2 argmaxx2D ⇢T z(x,✓⇤). The agent’s goal is to minimize the cumulative pseudo-regret defined by RT = PT t=1 ⇢ T z(x⇤,✓⇤) ⇢T z(xt,✓⇤).

heading: 1.2 Contributions

text:
We study MNL logistic regression bandits, a generalization of binary logistic bandits, that address applications where the number of outcomes that can be selected by the user is larger than two. The probability of selecting any possible K + 1 > 2 options (+1 stands for the ‘not click’ outcome aka “outside decision”) is modeled using a multinomial logit (MNL) model. For this problem:
• We identify a critical parameter , which we interpret as the degree of (non)-smoothness (less smooth for larger values of ) of the MNL model over the agent’s decision set. We prove that  scales exponentially with the size of the agent’s decision set creating a challenge in the design of low-regret algorithms, similar to the special binary case previously studied in the literature. • We develop a UCB-type algorithm for MNL logistic regression bandits. At every step, the algorithm decides on the inclusion of a K-tuple of parameter vectors ✓̄⇤1, . . . , ✓̄⇤K in the confidence region in a way that captures the local smoothness of the MNL model around this K-tuple and past actions. We show that this is critical for the algorithm’s favorable regret performance in terms of . • Specifically, we prove that the regret of our MNL-UCB scales as Õ(dK p  p T ). Instead, we show that a confidence ellipsoid that fails to capture local dependencies described above results in regret that scales linearly with  rather than with p . Moreover, our regret bound scales optimally in terms of the number of options K. • We propose an improved algorithm that achieves a regret bound with problem-dependent constant  being pushed into a second order term that vanishes quickly. • We complement our theoretical results with numerical simulations and corresponding discussions on the performance of our algorithm.

heading: 1.3 Related works

text:
Generalized Linear Bandits. GLBs were studied in Filippi et al. (2010); Li et al. (2017); Abeille et al. (2017); Russo and Van Roy (2013, 2014); Dong and Van Roy (2018) where the stochastic reward is modeled through an appropriate strictly increasing link function µ. All these works provide regret bounds Õ( p T ), where the multiplicative factor  is a problem-dependent constant and characterizes the degree of non-linearity of the link function.
Logistic Bandits. In Faury et al. (2020), the authors focused on the logistic bandit problem as a special case of GLBs. By introducing a novel Bernstein-like self-normalized martingale tail-inequality, they reduced the dependency of the existing GLB algorithms’ regret bounds on the constant  by a factor of p  and obtained a O(d p T ) regret for the logistic bandit problem. They further discussed the crucial role of , which can be arbitrarily large as it scales exponentially with the size of the decision set, on the performance of existing algorithms. Motivated by such considerations, with careful algorithmic designs, they achieved to drop entirely the dependence on  leading to a regret of Õ(d p T ).
Multinomial Logit Bandits. In a different line of work, Agrawal et al. (2017, 2019); Wang et al. (2018); Oh and Iyengar (2019); Chen et al. (2018); Dong et al. (2020); Agrawal et al. (2020) used the multinomial logit choice model to address the dynamic assortment selection problem, which is a combinatorial variant of the bandit problem. In this problem, the agent chooses a so-called assortment which is a subset of a set S = [N ] of N items. At round t, feature vectors xit, for every item i 2 S , are revealed to the agent, and given this contextual information, the agent selects an assortment St ⇢ S
and observes the user choice yt = i, i 2 St [ {0} where {0} corresponds to the user not selecting any item in St. The user choice is given by a MNL model with an unknown parameter ✓̄⇤ 2 Rd such that the probability that the user selects item i 2 St is exp(✓̄ T ⇤ xit)/(1 + P i2St exp(✓̄ T ⇤ xit)). Furthermore, a revenue parameter denoted by rit for each item i is also revealed at round t. The goal of the agent is to offer assortments with size at most K to maximize the expected cumulative revenue or to minimize the cumulative regret PT t=1 Rt(S ⇤ t , ✓̄⇤) Rt(St, ✓̄⇤), where Rt(St, ✓̄⇤) := P i⇢St rit exp(✓̄ T ⇤ xit)/(1 + P i2St exp(✓̄ T ⇤ xit)). Finally, the closely related paper Cheung and Simchi-Levi (2017) studies a problem where at each round, the agent observes a userspecific context based on which, it recommends a set of items to the user. The probability distribution of each one of the items in that set being selected by the user is given by an MNL model. This problem can be categorized as an online assortment optimization problem. Despite similarities in the use of an MNL model, there are certain differences between Cheung and Simchi-Levi (2017) and our paper in terms of problem formulation. In our setting, the user may have multiple reactions (one of K + 1 options), to a single selected item. In contrast, in Cheung and Simchi-Levi (2017), the agent must select a set of items to each of which the user reacts by either clicking or not clicking. Also, here the probability distribution of different user reactions remains the same at all rounds, while in Cheung and Simchi-Levi (2017) the response to an item from the recommended set depends on the other items in that set. We defer to future work studying implications of our techniques to the setting of Cheung and Simchi-Levi (2017).

heading: 2 Multnomial Logit UCB Algorithms

text:
In this section, we introduce two key quantities: (i) ✓t, an estimate of ✓⇤; (ii) ✏t(x), an exploration bonus for each x 2 D at each round t 2 [T ]. Based on these, we design a UCB-type algorithm, called MNL-UCB. At each round t, the algorithm computes an estimate ✓t of ✓⇤, that we present in Section 2.4. For each x 2 D and t 2 [T ], let ✏t(x) be such that the following holds with high probability:
(x,✓t) := |⇢ T z(x,✓⇤) ⇢ T z(x,✓t)| ✏t(x). (3)
At round t, having knowledge of ✏t(x), the agent computes the following upper bound on the expected reward ⇢T z(x,✓⇤) for all x 2 D:
⇢T z(x,✓⇤)  ⇢ T z(x,✓t) + ✏t(x). (4)
Then, the learner follows a UCB decision rule to select an action xt according to the following rule:
xt := argmax x2D
⇢T z(x,✓t) + ✏t(x). (5)
To see how the UCB decision rule in (5) helps us control the cumulative regret, we show how it controls the instantaneous regret by the following standard argument Abbasi-Yadkori et al. (2011); Faury et al. (2020):
rt = ⇢ T z(x⇤,✓⇤) ⇢ T z(xt,✓⇤) (4)  ⇢T z(x⇤,✓t) + ✏t(x⇤) ⇢ T z(xt,✓⇤)
(5)  ⇢T z(xt,✓t) ⇢ T z(xt,✓⇤) + ✏t(xt) (3)  2✏t(xt) . (6)
In view of this, our goal is to design an algorithm that appropriately chooses the estimator ✓t and the exploration bonus ✏t(x) such that its regret is sub-linear.

heading: 2.1 Maximum likelihood estimate

text:
The problem of estimating ✓⇤ at round t given Ft is identical to a multi-class linear classification problem, where ✓̄⇤i is the “classifier” for class i. A natural way to compute the estimator of the unknown parameter ✓⇤ of the MNL model given Ft is to use the maximum likelihood principle. At round t, the regularized log-likelihood (aka negative cross-entropy loss) with regularizer > 0 writes
L t (✓) :=
t 1X
s=1
KX
i=0
{ys = i} log zi(xs,✓)
2 k✓k22 . (7)
Then, the maximum likelihood estimate of ✓⇤ is defined as ✓̂t := argmax✓ L t (✓). Taking the gradient of (7) with respect to ✓ we obtain
r✓L t (✓) :=
t 1X
s=1
[ms z(xs,✓)]⌦ xs ✓, (8)
where ms is the ‘one-hot encoding’ vector of the user’s selection at round s, i.e., ms :=⇥ {ys = 1}, . . . , {ys = K} ⇤T . It will also be convenient to define the Hessian of L t (✓):
Ht(✓) := IKd + t 1X
s=1
A(xs,✓)⌦ xsx T s , (9)
where A(x,✓)ij := zi(x,✓) ij zj(x,✓) for all i, j 2 [K]. Equivalently, in matrix form
A(x,✓) := diag(z(x,✓)) z(x,✓)zT(x,✓). (10)
Note here that A(x,✓) is a matrix function that depends on ✓ and x via the inner products ✓̄ T 1 x, ✓̄ T 2 x, . . . , ✓̄ T Kx. Also, the matrix A(x,✓) has nice algebraic properties (discussed more in Section 3) that turn our to be critical in the execution and analysis of our algorithm.
Now, we introduce assumptions on the problem structure, under which our theoretical results hold. Assumption 1 (Boundedness). Without loss of generality,kxk2  1 for all x 2 D. Also, ✓⇤ 2 ⇥ := {✓ 2 RKd :k✓k2  S} andk⇢k2  R. Both upper bounds S and R are known to the agent.
The assumption that S is known is standard in the literature of GLBs. Knowledge of R is also reasonable to assume because ⇢i’s represent the revenue parameters that are typically known or set by the system operator. Assumption 2 (Problem-dependent constants). There exist strictly positive constants 0 < L < 1 and 0 <  < 1 such that sup
x2D,✓2⇥ max A(x,✓) := L and infx2D,✓2⇥ min A(x,✓) := 1 .
We comment further on the knowledge of  and L in Section 3. Here, we note that  is reminiscent of the corresponding quantity in binary logistic bandits which is defined accordingly as  := sup
x2D,k✓̄k 2 S 1/µ̇(✓̄
T x), where µ̇ is the first derivative of the logistic function µ(x) = 1/(1 +
exp( x)). As Filippi et al. (2010); Li et al. (2017); Faury et al. (2020) have shown, this quantity plays a key role in characterizing the behavior of binary (K = 1) logit bandit algorithms. In this paper, we will show that the proper analogue of this quantity to multinomial (K > 1) logit bandit algorithms is the parameter  defined in Assumption 2.

heading: 2.2 Confidence set around ✓⇤

text:
We introduce a confidence set Ct( ) that will include ✓⇤ with high probability thus allowing us to upper bound (x,✓t) in the following subsection. We start by defining the key quantity
gt(✓) := ✓ + t 1X
s=1
z(xs,✓)⌦ xs. (11)
To see why this is useful, note that by the first-order optimality condition r✓L t (✓̂t) = 0 we have ✓⇤ satisfying gt(✓⇤) gt(✓̂t) = ✓⇤ + st, with st := Pt 1 s=1 z(xs,✓⇤) ms ⌦ xs. This in turn motivates us to define a confidence set Ct at the beginning of each round t 2 [T ] such that
Ct( ) := {✓ 2 ⇥ : gt(✓) gt(✓̂t)
H 1 t (✓)
 t( )}, (12)
where t( ) is chosen as in Theorem 1 below to guarantee ✓⇤ 2 Ct( ) with high probability 1 . Theorem 1 (Confidence set). Let the Assumption 1 hold and for 2 (0, 1), define t( ) := K3/2dp
log (1 + td ) +
p /K
2 + 2K3/2dp log( 2 ) +
p S. Then with probability at least 1 , for all
t 2 [T ] it holds that ✓⇤ 2 Ct( ).
Once we have properly identified the key quantities gt(✓⇤) and Ht(✓), the proof of the theorem above rather naturally extends Lemma 1 in Faury et al. (2020). Compared to the special case K = 1 studied in Faury et al. (2020), extra care is needed here to properly track the scaling of t( ) with respect to the new parameter K that is of interest for us. The details are deferred to Appendix A. To a great extent, the similarities between the binary and multinomial cases end here. It will turn out that bounding (x,✓t), for an appropriate choice of ✓t, is significantly more intricate here than in the binary case. Our main technical contribution towards this direction is given in the lemmas presented in Section 2.3 that are used to prove the following key result. Lemma 1. Let Assumptions 1 and 2 hold. For all x 2 D, t 2 [T ] and ✓ 2 Ct( ), with probability at least 1 :
(x,✓)  2RL t( ) p  (1 + 2S)kxk
V 1 t
, (13)
where Vt :=  I + Pt 1 s=1 xsx T s .
The complete proof is in Appendix B. In the following section, we give a proof sketch.

heading: 2.3 Proof sketch of Lemma 1

text:
To prove Lemma 1, we will use the high probability confidence set Ct( ) in (12) paired with the problem setting’s properties encapsulated in Assumptions 1 and 2. To see the key challenges in establishing (13), consider the following. By definition of (x,✓) in (3), Cauchy-Schwarz inequality, and Assumption 1, for any x 2 D, t 2 [T ], and ✓ 2 Ct( ):
(x,✓)  Rkz(x,✓⇤) z(x,✓)k2. (14)
Thus, our goal becomes relating kz(x,✓⇤) z(x,✓)k2 to gt(✓⇤) gt(✓̂t)
H 1 t (✓⇤) and/or gt(✓̂t) gt(✓)
H 1 t (✓)
. The reason is that the two latter quantities are both known to be bounded
by t( ) with high probability since ✓⇤ 2 Ct( ) with probability at least 1 (cf. Theorem 1). We accomplish our goal in three steps. First, in Lemma 2, we connect z(x,✓1) z(x,✓2) to ✓1 ✓2 for any x 2 Rd and ✓1,✓2 2 RKd. Lemma 2. For any x 2 Rd, ✓1,✓2 2 RKd, recall the definition of A(x,✓) in (10) and define
B(x,✓1,✓2) :=
Z 1
0 A(x, v✓1 + (1 v)✓2)dv. (15)
Then, we have z(x,✓1) z(x,✓2) = ⇥ B(x,✓1,✓2)⌦ xT ⇤ (✓1 ✓2).
The proof of the lemma above in Appendix B.1 relies on a proper application of the mean-value Theorem. Next, in Lemma 3 below, we relate ✓1 ✓2 to gt(✓1) gt(✓2). Lemma 3. Let
Gt(✓1,✓2) := IKd + t 1X
s=1
B(xs,✓1,✓2)⌦ xsx T s . (16)
Then, for any ✓1,✓2 2 RKd, we have
gt(✓1) gt(✓2) = Gt(✓1,✓2)(✓1 ✓2). (17)
The proof in Appendix B.1 uses the definition of gt(✓), Lemma 2 and a proper application of the mixed-product property of the Kronecker product. Note that Gt(✓1,✓2) ⌫ 0; thus, it is invertible.
Now, combining Lemmas 2 and 3, our new goal becomes bounding ⇥ B(x,✓⇤,✓)⌦ xT ⇤ G 1 t (✓⇤,✓) gt(✓⇤) gt(✓)
2 . Our key technical contribution is es-
tablishing good bounds for the spectral norm ⇥ B(x,✓⇤,✓)⌦ xT ⇤ G 1/2 t (✓⇤,✓)
2
and the
weighted Euclidean norm gt(✓⇤) gt(✓)
G 1 t (✓⇤,✓) . We start by briefly explaining how we bound the spectral norm above; see Appendix B.2 for details. By using the cyclic property of
the maximum eigenvalue and the mixed-product property of the Kronecker product, it suffices to bound max ✓ G 1/2 t ⇣ B T B ⌦ xx T ⌘ G 1/2 t ◆ , where we denote B = B(x,✓⇤,✓) and
Gt = Gt(✓⇤,✓) for simplicity. There are two essential ideas to do so. First, thanks to our Assumption 2, which upper bounds the eigenvalues of A(x,✓) by L, and by recalling the definition of B(x,✓1,✓2), we manage to show that (BBT )⌦ xx T L2 (IK ⌦ x) IK ⌦ xT . Our second idea is to relate the matrix Gt to the Gram matrix of actions
Vt :=  Id + t 1X
s=1
xsx T s . (18)
Specifically, using our Assumption 2 that the minimum eigenvalue of A(x,✓) is lower bounded by 1/ and standard spectral properties of the Kronecker product, we prove in Lemma 12 in the appendix that Gt ⌫ 1IK ⌦Vt or G 1 t IK ⌦V 1 t . By properly combining the above, we achieve the following convenient upper bound: [B(x,✓⇤,✓)⌦ xT ]G 1/2t (✓⇤,✓)
2  L
p kxk
V 1 t
. (19)
To see why this is useful, note that compared to Ht(✓) in (9), which is a ‘matrix-weighted’ version of the Gram matrix, the definition of Vt in (18) is the same as the definition of the Gram matrix in linear bandits. Thus, we are now able to use standard machinery in Abbasi-Yadkori et al. (2011) to bound
PT t=1kxtkV 1t .
Finally, we discuss how to control the remaining term gt(✓⇤) gt(✓)
Gt(✓⇤,✓) 1
. By adding and
subtracting gt(✓̂t) to and from the argument inside the norm, it suffices to bound gt(✓⇤) gt(✓̂t)
Gt(✓⇤,✓) 1
+ gt(✓̂t) gt(✓)
Gt(✓⇤,✓) 1
. (20)
To do this, we exploit the definition of Ct( ) in (12) by first relating the G 1t (✓⇤,✓)–norms with those in terms of H 1t (✓⇤) and H 1 t (✓). To do this, we rely on the generalized self concordance property of the strictly convex log-sum-exp (lse : RK ! R [1) function Tran-Dinh et al. (2015) lse(s) := log(1 + PK i=1 exp(si)). Notice that our z(x,✓) is the gradient of the lse function at point [✓̄T1 x, ✓̄ T 2 x, . . . , ✓̄ T Kx] T , that is z(x,✓) = rlse ⇣ [✓̄ T 1 x, ✓̄ T 2 x, . . . , ✓̄ T Kx] T ⌘ . Thanks to the
generalized self-concordance property of the lse, upper bounds on its Hessian matrix (essentially the matrix Ht(✓)) have been developed in Tran-Dinh et al. (2015); Sun and Tran-Dinh (2019). Proper use of such bounds leads to lower bounds on Gt(✓⇤,✓) as follows. Lemma 4 (Generalized self-concordance). For any ✓1,✓2 2 ⇥, we have (1 + 2S) 1Ht(✓1) Gt(✓1,✓2) and (1 + 2S) 1Ht(✓2) Gt(✓1,✓2).
The proof is given in Appendix B.1. Finally, plugging the above lower bounds on matrix Gt into (20) for ✓⇤ and ✓ gives the final bound on (x,✓) in Lemma 1.

heading: 2.4 Error bound on (x,✓t)

text:
In this section, we specify ✓t and ✏t(x) for all t 2 [T ] and x 2 D. In view of Lemma 1, the exploration bonus ✏t(x) can be set equal to the RHS of (13), only if ✓t 2 Ct( ). Recall from the definition of Ct( ) in (12) that for ✓t 2 Ct( ), it must be that ✓t 2 ⇥. Since the ML estimator ✓̂t does not necessarily satisfy ✓̂t 2 ⇥, we introduce the following “feasible estimator":
✓t := argmin ✓2⇥ gt(✓) gt(✓̂t) H 1 t (✓) , (21)
which is guaranteed to be in the confidence set Ct( ) for all t 2 [T ] since kgt(✓t) gt(✓̂t)kH 1t (✓) kgt(✓⇤) gt(✓̂t)kH 1t (✓) t( ) and ✓t 2 ⇥. Thus, we have proved the following.
Corollary 1 (Exploration bonus). For all x 2 D and t 2 [T ], with probability at least 1 , we have
(x,✓t)  ✏t(x) := 2RL t( ) p  (1 + 2S)kxk
V 1 t
. (22)
Algorithm 1: MNL-UCB 1 for t = 1, . . . , T do 2 Compute ✓t as in (21). 3 Compute xt := argmaxx2D ⇢T z(x,✓t) + ✏t(x) with ✏t(x) defined in (22). 4 Play xt and observe yt.
With these, we are now ready to summarize MNL-UCB in Algorithm 1. Remark 1. The projection step in (21) is similar to the ones used in Filippi et al. (2010); Faury et al. (2020) for binary logistic bandits. In particular, this step in Filippi et al. (2010) involves norms with respect to Vt instead of Ht(✓) (for K = 1). All of these involve non-convex optimization problems. Empirically, we observe that it occurs frequently that ✓̂t 2 ⇥. Then, ✓t = ✓̂t and these complicated projection steps do not need to be implemented.

heading: 2.5 Regret bound of MNL-UCB

text:
In the following theorem, we state the regret bound of MNL-UCB as our main result. Theorem 2 (Regret of MNL-UCB). Fix 2 (0, 1). Let Assumptions 1 and 2 hold. Then, with probability at least 1 , it holds that RT  4RL T ( ) q 2max(1, 1  ) (1 + 2S) dT log(1 + T  d ). In particular, choosing = Kd log(T ) yields RT  O ⇣ RLKd log(T ) p T ⌘ .
Now we comment on the regret order with respect to the key problem parameters T, d,K and p . With respect to these the theorem shows a scaling of the regret of Algorithm 1 as O(Kd log(T ) p T ). Specifically, for K = 1 we retrieve the exact same scaling as in Theorem 2 of Faury et al. (2020) for the binary case in terms of T, d and . In particular, the bound is optimal with respect to the action-space dimension d as O(d) is the optimal order in the simpler setting of linear bandits Dani et al. (2008). Of course, compared to Faury et al. (2020) our result applies for general K 1 and implies a linear scaling with the number K of possible outcomes that can be selected by the user. In fact, our bound suggests our algorithm on a K-multinomial problem has performance of same order as the performance of the algorithm of Faury et al. (2020) for a binary problem with dimension Kd instead of d. On the one hand, this is intuitive since the MNL reward model indeed involves Kd unknown parameters. Thus, we cannot expect regret better than O(Kd) for Kd unknown parameters. On the other hand, the MNL is a special case of multi-index models rather than a GLM. Thus, it is a-priori unclear whether it differs from a binary logistic model with Kd parameters in terms of regret performance. In fact, our proof does not treat the MNL reward model as a GLM. Despite that, it results to the linear order O(K) same as the optimal order of a binary logistic setting with Kd unknown parameters. Finally, as previously mentioned, the parameter  defined in Assumption 2 generalizes the corresponding parameter for binary bandits. As in Theorem 2 of Faury et al. (2020) our bound for the multinomial case scales with p . Next, we show how this scaling is non-trivial and improves upon standard approaches. Remark 2. Using same tools as for GLM-UCB in Filippi et al. (2010) for single-index reward models (K = 1), we can define the following alternative confidence set around the parameter ✓⇤ of the MNL model:
Et( ) := ✓ 2 ⇥ : k✓ ✓̃tkṼ 1t   t( ) , (23)
where t( ) is a slowly increasing function of t with similar order as t( ) (see Lemma 14 in appendix), Ṽt = IK ⌦Vt, and ✓̃t := argmin✓2⇥ kgt(✓) gt(✓̂t)kṼ 1t . Due to the appearance of an extra  factor above compared to (12), relying on Et( ) (23) in our analysis would lead to the following error bound (see Appendix C.2):
(x, ✓̃t)  ✏̃t(x) := 2RL t( )kxkV 1t . (24)
This bound is significantly looser compared to our bound in (22) since the parameter  can become arbitrarily large depending on the size of set D ⇥⇥.

heading: 2.6 Improved MNL-UCB

text: The regret of MNL-UCB scales as O( p ) with respect to . A more careful treatment of Ct( ) in (12) leads to Improved MNL-UCB, a modification of MNL-UCB, with a newly defined estimator and improved exploration bonus. Compared to MNL-UCB, the new algorithm is computationally intractable. Yet, it is interesting from a theory perspective as we show a regret bound where the -dependence is pushed into a quickly-vanishing second order term, trading-off a slight increase in the regret’s dependence on K. In particular, we prove improved regret of order O(K1.5d p T log(T ) + K2d log(T )). Due to space limitations, we defer a detailed description (see Algorithm 2) and analysis (see Theorem 3) of Improved MNL-UCB in Appendix D.

heading: 3 Discussion on  and L

text:
Knowledge of the problem-dependent constants  and L is required to implement MNL-UCB as they appear in the definition of ✏t(x) in (22). While specifying their true values (defined in Assumption 2) requires solving non-convex optimization problems in general, here we present computationally efficient ways to obtain simple upper bounds. Also, we show that  can indeed scale poorly with the size of D ⇥ ⇥ by deriving an appropriate lower bound for it. The upper bound on L is rather straightforward and it can be easily checked that L  maxx2D e Skxk2
1+eSkxk2+(K 1)e Skxk2 . Next, we focus on upper/lower bounding , which is more interesting.
In (26), we will show that  scales unfavorably with the size of the set D ⇥ ⇥. In our regret analysis in the previous sections, it was useful to assume in Assumption 1 that kxk2 1. This assumption was without loss of generality because of the following. Suppose a general setting with X = maxx2Dkxk2> 1. We can then define an equivalent MNL model with actions x̃ = x/X and new parameter vector ✓̃ = X✓. The new problem satisfies the unit norm constraint on the radius of D and has a new parameter norm bound S̃ = SX . For clarity with regards to the goal of this section, it is convenient to keep track of the radius of D (rather than push it in S). Thus, we let X := maxx2Dkxk2 (possibly large). We will prove that  grows at least exponentially in SX , thus it can be very large if the action decision set is large.
In order to bound , we identify and take advantage of the following key property of A(x,✓) stated as Lemma 5. Recall that a matrix A 2 RK⇥K is strictly diagonally dominant if each of its diagonal entries is greater than the sum of absolute values of all other entries in the corresponding row/column. We also need the definition of an M -matrix: A matrix A is an M -matrix if all its off-diagonal entries are non-positive and the real parts of its eigenvalues are non-negative Berman and Plemmons (1994). Lemma 5. For any x 2 Rd and ✓ 2 RKd, the matrix A(x,✓) in (10) is a strictly diagonally dominant M -matrix.
This key observation (see Appendix C for the proof) allows us to use Theorem 1.1 in Tian and Huang (2010) that provides upper and lower bounds on the minimum eigenvalue of a strictly diagonally dominant M -matrix. Specifically, we find that for all all x and ✓:
min i2[K]
KX
j=1
A(x,✓)ij  min(A(x,✓))  max i2[K]
KX
j=1
A(x,✓)ij . (25)
Starting from this and setting X := maxx2Dkxk2 we show the following bounds (Appendix C.4):
e SXp K (1 +Ke SXp K )2    eSX(1 +KeSX)2. (26)

heading: 4 Experiments

text:
We present numerical simulations to complement and confirm our theoretical findings. In all experiments, we used the upper bound on  in (26) to compute the exploration bonus ✏t(x).
We evaluate the performance of MNL-UCB on synthetic data. All the results shown depict averages over 20 realizations, for which we have chosen = 0.01, d = 2, and T = 1000. We considered time-independent decision sets D of 20 arms in R2 and the reward vector ⇢ = [1, . . . ,K]T . Moreover,
the arms and ✓̄⇤i are drawn from N (0, Id) and N (0, Id/K), respectively. The normalization of the latter by K is so that it guarantees that the problem’s signal-to-noise ratiok✓⇤k2 does not change with varying K. Figure 1a depicts the average regret of MNL-UCB for problem settings with different values of K = 1, 2, 3. The plot verifies that larger K leads to larger regret and seems to match the proved scaling of the regret bound of MNL-UCB as O(K) with respect to K. Figure 1b showcases the average regret of MNL-UCB for problem settings with fixed K = 2 and different values of  = 30, 60, 100 (upper bounds computed using (26)). Observe that larger  leads to larger regret. This is consistent with our theoretical findings on the impacts of  on the algorithm’s performance. Finally, Figure 1c emphasizes the value of using the exploration bonus ✏t(x) in (22) compared to ✏̃t(x) introduced in (24) in the UCB decision making step. In this figure, we fixed K = 2 and the average regret curves are associated with a problem setting with  = 30. A comparison between regret curves further confirms the worse regret performance of MNL-UCB when it exploits ✓̃t and ✏̃t(x) rather than ✓t and ✏t(x) in the UCB decision rule at Line 3 of the Algorithm 1.

heading: 5 Conclusion

text:
For the MNL regression bandit problem, we developed MNL-UCB and showed a regret Õ(Kd p  p T ) that scales favorably with the critical problem-dependent parameter  and optimally with respect to the number of options K. We further proposed Improved MNL-UCB that achieves a regret bound with problem-dependent constant  being pushed into a second order logarithmic term, trading-off a slight increase in the regret’s dependence on K. After this work was completed, we became aware of Abeille et al. (2021) that improves Faury et al. (2020) in the binary case. Our work shows that extension of Faury et al. (2020) to MNL model is non-trivial and requires several careful analysis adjustments. It is an exciting future direction to investigate whether the algorithmic improvements of Abeille et al. (2021) can be properly adjusted in the multiclass case of interest here. In light of our discussion after Theorem 2 in Section 2.5, another promising future direction is to determine a lower bound that formally justifies the optimal dependence is O(K) or determine an improved algorithm/analysis that lowers the dependency on K. It is also interesting to study the efficacy of Thompson sampling-based algorithms for this new problem. Also, extending our results to other multi-index models is yet another important future direction.
Acknowledgments and Disclosure of Funding
This work is supported in part by the National Science Foundation under Grant Number (1934641). Part of this work was completed while the second author was affiliated with the University of California, Santa Barbara.

title: UCB-based Algorithms for Multinomial Logistic Regression Bandits


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.

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

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

summaries: 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:
Joshua Achiam
Shankar Sastry

title: Surprise-based intrinsic motivation for deep reinforcement learning

venue: arXiv preprint arXiv:1703.01732,

authors:
Martin Arjovsky
Soumith Chintala
Léon Bottou

title: Wasserstein generative adversarial networks

venue: In International conference on machine learning,

authors:
Adrià Puigdomènech Badia
Pablo Sprechmann
Alex Vitvitskyi
Daniel Guo
Bilal Piot
Steven Kapturowski
Olivier Tieleman
Martín Arjovsky
Alexander Pritzel
Andew Bolt

title: Never give up: Learning directed exploration strategies

venue: arXiv preprint arXiv:2002.06038,

authors:
Sina Baharlouei
Maher Nouiehed
Ahmad Beirami
Meisam Razaviyayn

title: R\’enyi fair inference

venue: arXiv preprint arXiv:1906.12005,

authors:
Gianluca Baldassarre
Marco Mirolli

title: Intrinsically motivated learning in natural and artificial systems

authors:
Babak Barazandeh
Meisam Razaviyayn

title: Solving non-convex non-differentiable min-max games using proximal gradient method

venue: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP),

authors:
Lucas Beyer
Damien Vincent
Olivier Teboul
Sylvain Gelly
Matthieu Geist
Olivier Pietquin

title: Mulex: Disentangling exploitation from exploration in deep rl

authors:
Yuri Burda
Harrison Edwards
Amos Storkey
Oleg Klimov

title: Exploration by random network distillation

venue: arXiv preprint arXiv:1810.12894,

authors:
Nuttapong Chentanez
Andrew G Barto
Satinder P Singh

title: Intrinsically motivated reinforcement learning

venue: In Advances in neural information processing systems,

authors:
Jongwook Choi
Yijie Guo
Marcin Moczulski
Junhyuk Oh
Neal Wu
Mohammad Norouzi
Honglak Lee

title: Contingency-aware exploration in reinforcement learning

venue: arXiv preprint arXiv:1811.01483,

title: Elements of information theory

authors:
Benjamin Eysenbach
Sergey Levine

title: Maximum entropy rl (provably) solves some robust rl problems

venue: arXiv preprint arXiv:2103.06257,

authors:
Scott Fujimoto
Herke van Hoof
Dave Meger

title: Addressing function approximation error in actor-critic methods

venue: arXiv preprint arXiv:1802.09477,

authors:
Gauthier Gidel
Tony Jebara
Simon Lacoste-Julien

title: Frank-wolfe algorithms for saddle point problems

venue: In Artificial Intelligence and Statistics,

authors:
Ian Goodfellow
Jean Pouget-Abadie
Mehdi Mirza
Bing Xu
David Warde-Farley
Sherjil Ozair
Aaron Courville
Yoshua Bengio

title: Generative adversarial nets

authors:
Yijie Guo
Junhyuk Oh
Satinder Singh
Honglak Lee

title: Generative adversarial self-imitation learning

venue: arXiv preprint arXiv:1812.00950,

authors:
Tuomas Haarnoja
Sehoon Ha
Aurick Zhou
Jie Tan
George Tucker
Sergey Levine

title: Learning to walk via deep reinforcement learning

venue: arXiv preprint arXiv:1812.11103,

authors:
Tuomas Haarnoja
Haoran Tang
Pieter Abbeel
Sergey Levine

title: Reinforcement learning with deep energy-based policies

venue: arXiv preprint arXiv:1702.08165,

authors:
Tuomas Haarnoja
Aurick Zhou
Pieter Abbeel
Sergey Levine

title: Soft actor-critic: Offpolicy maximum entropy deep reinforcement learning with a stochastic actor

venue: arXiv preprint arXiv:1801.01290,

authors:
Tuomas Haarnoja
Aurick Zhou
Kristian Hartikainen
George Tucker
Sehoon Ha
Jie Tan
Vikash Kumar
Henry Zhu
Abhishek Gupta
Pieter Abbeel

title: Soft actor-critic algorithms and applications

venue: arXiv preprint arXiv:1812.05905,

authors:
E Yazdandoost Hamedani
A Jalilzadeh
NS Aybat
UV Shanbhag

title: Iteration complexity of randomized primal-dual methods for convex-concave saddle point problems

venue: arXiv preprint arXiv:1806.04118,

authors:
Seungyul Han
Youngchul Sung

title: Diversity actor-critic: Sample-aware entropy regularization for sample-efficient exploration

venue: arXiv preprint arXiv:2006.01419,

authors:
Elad Hazan
Sham Kakade
Karan Singh
Abby Van Soest

title: Provably efficient maximum entropy exploration

venue: In International Conference on Machine Learning,

authors:
Zhang-Wei Hong
Tzu-Yun Shann
Shih-Yang Su
Yi-Hsiang Chang
Tsu-Jui Fu
Chun-Yi Lee

title: Diversity-driven exploration strategy for deep reinforcement learning

authors:
Rein Houthooft
Xi Chen
Yan Duan
John Schulman
Filip De Turck
Pieter Abbeel

title: Vime: Variational information maximizing exploration

authors:
Shiyu Huang
Hang Su
Jun Zhu
Ting Chen

title: Svqn: Sequential variational soft q-learning networks

venue: In International Conference on Learning Representations,

authors:
Sergey Levine
Vladlen Koltun

title: Guided policy search

authors:
Ya-Feng Liu
Yu-Hong Dai
Zhi-Quan Luo

title: Max-min fairness linear transceiver design for a multi-user mimo interference channel

venue: IEEE Transactions on Signal Processing,

authors:
Manuel Lopes
Tobias Lang
Marc Toussaint
Pierre-Yves Oudeyer

title: Exploration in modelbased reinforcement learning by empirically estimating learning progress

authors:
Aleksander Madry
Aleksandar Makelov
Ludwig Schmidt
Dimitris Tsipras
Adrian Vladu

title: Towards deep learning models resistant to adversarial attacks

venue: arXiv preprint arXiv:1706.06083,

authors:
Jarryd Martin
Suraj Narayanan Sasikumar
Tom Everitt
Marcus Hutter

title: Count-based exploration in feature space for reinforcement learning

venue: arXiv preprint arXiv:1706.08090,

authors:
Bogdan Mazoure
Thang Doan
Audrey Durand
R Devon Hjelm
Joelle Pineau

title: Leveraging exploration in off-policy algorithms via normalizing flows

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Andrei A Rusu
Joel Veness
Marc G Bellemare
Alex Graves
Martin Riedmiller
Andreas K Fidjeland
Georg Ostrovski

title: Human-level control through deep reinforcement learning

authors:
Katta G Murty
Santosh N Kabadi

title: Some np-complete problems in quadratic and nonlinear programming

venue: Technical report,

authors:
Ofir Nachum
Mohammad Norouzi
Kelvin Xu
Dale Schuurmans

title: Bridging the gap between value and policy based reinforcement learning

title: Trust-pcl: An off-policy trust region method for continuous control

venue: arXiv preprint arXiv:1707.01891,

title: Variational inference for policy search in changing situations

venue: In Proceedings of the 28th International Conference on Machine Learning,

authors:
Maher Nouiehed
Maziar Sanjabi
Tianjian Huang
Jason D Lee
Meisam Razaviyayn

title: Solving a class of non-convex min-max games using iterative first order methods

authors:
Brendan O’Donoghue
Remi Munos
Koray Kavukcuoglu
Volodymyr Mnih

title: Combining policy gradient and q-learning

venue: arXiv preprint arXiv:1611.01626,

authors:
Hassan Rafique
Mingrui Liu
Qihang Lin
Tianbao Yang

title: Non-convex min-max optimization: Provable algorithms and applications in machine learning

authors:
Alexander Rakhlin
Karthik Sridharan

title: Optimization, learning, and games with predictable sequences

venue: arXiv preprint arXiv:1311.1869,

authors:
Konrad Rawlik
Marc Toussaint
Sethu Vijayakumar

title: On stochastic optimal control and reinforcement learning by approximate inference

venue: In Twenty-Third International Joint Conference on Artificial Intelligence,

authors:
John Schulman
Xi Chen
Pieter Abbeel

title: Equivalence between policy gradients and soft q-learning

venue: arXiv preprint arXiv:1704.06440,

authors:
John Schulman
Sergey Levine
Pieter Abbeel
Michael Jordan
Philipp Moritz

title: Trust region policy optimization

venue: In Proceedings of the 32nd International Conference on Machine Learning

authors:
John Schulman
Filip Wolski
Prafulla Dhariwal
Alec Radford
Oleg Klimov

title: Proximal policy optimization algorithms

venue: arXiv preprint arXiv:1707.06347,

authors:
Riley Simmons-Edler
Ben Eisner
Daniel Yang
Anthony Bisulco
Eric Mitchell
Sebastian Seung
Daniel Lee

title: Qxplore: Q-learning exploration by maximizing temporal difference

authors:
Avi Singh
Larry Yang
Kristian Hartikainen
Chelsea Finn
Sergey Levine

title: End-to-end robotic reinforcement learning without reward engineering

title: General duality between optimal control and estimation

venue: IEEE Conference on Decision and Control,

authors:
Emanuel Todorov
Tom Erez
Yuval Tassa

title: Mujoco: A physics engine for model-based control

venue: In Intelligent Robots and Systems (IROS),

title: Robot trajectory optimization using approximate inference

venue: In Proceedings of the 26th annual international conference on machine learning,

authors:
Hoi-To Wai
Mingyi Hong
Zhuoran Yang
Zhaoran Wang
Kexin Tang

title: Variance reduced policy evaluation with smooth function approximation

venue: Advances in Neural Information Processing Systems,

authors:
Brian Hu Zhang
Blake Lemoine
Margaret Mitchell

title: Mitigating unwanted biases with adversarial learning

venue: In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society,

authors:
Zeyu Zheng
Junhyuk Oh
Satinder Singh

title: On learning intrinsic rewards for policy gradient methods

heading: 1 Introduction

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

heading: 2 Related Works

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

heading: 3 Background

heading: 3.1 Basic RL Setup

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.

heading: 3.2 Maximum Entropy RL and Soft Actor-Critic

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.

heading: 4 Motivation: Limitation of Maximum Entropy SAC in Pure Exploration

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.

heading: 5 Methodology

heading: 5.1 A Deeper Look at Pure Exploration

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.

heading: 5.2 Max-Min Entropy RL

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.

heading: 5.3 Disentangled Exploration and Exploitation for Rewarded Setup

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.

heading: 6 Experiments

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.

heading: 6.2 Performance in Rewarded Environments

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.

heading: 7 Conclusion

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.

heading: 8 Acknowledgement

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