Title: REPRESENTING ENTROPY : A SHORT PROOF OF THE EQUIVALENCE BETWEEN SOFT Q-LEARNING AND POLICY GRADIENTS

Abstract: Two main families of reinforcement learning algorithms, Q-learning and policy gradients, have recently been proven to be equivalent when using a softmax relaxation on one part, and an entropic regularization on the other. We relate this result to the well-known convex duality of Shannon entropy and the softmax function. Such a result is also known as the Donsker-Varadhan formula. This provides a short proof of the equivalence. We then interpret this duality further, and use ideas of convex analysis to prove a new policy inequality relative to soft Q-learning.

1. INTRODUCTION AND SETTING:

Deep reinforcement learning as a research field is currently undergoing tremendous growth, largely due to empirical successes brought about by scaling the technique to real-world examples such as Atari games and Go. Historically, two main families of algorithms have existed:

• Q-learning (V. Mnih (2015) ) proposes to iteratively refine estimates of a family of scalar action-value functions. These represent the reward expected after undertaking a given action, so as to be able to act greedily (or -greedily) with respect to those numbers;

• Policy gradients (V. Mnih & Kavukcuoglu. (2016) ), looks to maximize the expected reward by improving policies to favor high-reward actions. In general, the target loss function is regularized by the addition of an entropic functional for the policy. This makes policies more diffuse and less likely to yield degenerate results.

A critical step in the theoretical understanding of the field has been a smooth relaxation of the greedy max operation involved in selecting actions, turned into a Boltzmann softmax O. Nachum & Schuurmans. (2017b.) . This new context has lead to a breakthrough this year J. Schulman & Abbeel.

(2017) with the proof of the equivalence of both methods of Q-learning and policy gradients. While that result is extremely impressive in its unification, we argue that it is critical to look additionally at the fundamental reasons as to why it occurs. We believe that the convexity of the entropy functional used for policy regularization is at the root of the phenomenon, and that (Lagrangian) duality can be exploited as well, either yielding faster proofs, or further understanding. The contributions of our paper are as follows:

1. We show how convex duality expedites the proof of the equivalence between soft Qlearning and softmax entropic policy gradients -heuristically in the general case, rigorously in the bandit case.

2. We introduce a transportation inequality that relates the expected optimality gap of any policy with its Kullback-Leibler divergence to the optimal policy.

We describe our notations here. Abusing notation heavily by identifying measures with their densities as in dπ(a|s) = π(a|s)da, if we note as either r(s, a) or r(a, s) the reward obtained by taking action a in state s, the expected reward expands as:

EQUATION

K r is a linear functional of π. Adding Shannon entropic regularization1 improves numerical stability of the algorithm, and prevents early convergence to degenerate solutions. Noting regularization strength β, the objective becomes a free energy functional, named by analogy with a similar quantity in statistical mechanics:

EQUATION

Crucially, viewed as a functional of π, J is convex and is the sum of two parts

EQUATION

2 THE GIBBS VARIATIONAL PRINCIPLE FOR POLICY EVALUATION

2.1. LEGENDRE TRANSFORM AND POLICY ENTROPY:

Here we are interested in the optimal value of the policy functional J, achieved for an optimal policy π * . We hence look for J * = J(π * ) = sup π∈P J(π). In the one step-one state bandit setting we are in, this is in fact almost the same as deriving the state-value function. (2017) yield a useful representation. Non-regularized empirical rewards in equation 1 can be seen as the standard inner product in Hilbert space L 2 . We therefore equate inner product, expectation and integral over A. Writing J * as

EQUATION

with H the entropy functional defined above, we recover exactly the definition of the Legendre-Fenchel transformation, or convex conjugate, of β • H. The word convex applies to the entropy functional, and doesn't make any assumptions on the rewards r(s, a), other that they be well-behaved enough to be integrable in a.

The Legendre transform inverts derivatives. A simple calculation shows that the formal convex conjugate of f : t → t log t is f * : p → e (p-1) -this because their respective derivatives log and exp are reciprocal. We can apply this to f (π(a|s)) = π(a|s) log π(a|s), and then this relationship can also be integrated in a. Hence the dual Legendre representation of the entropy functional H is known. The Gibbs variational principle states that, taking β = 1/λ as the inverse temperature parameter, and for each Borelian (measurable

EQUATION

or in shorter notation, for each real random variable X with exponential moments,

EQUATION

We can prove a stronger result. If µ is a reference measure (or policy), and we now consider the relative entropy (or Kullback-Leibler divergence) with respect to µ, H µ (•), instead of the entropy H(•), then the Gibbs variational principle still holds (Villani. (2008), chapter 22) . This result regarding dual representation formulas for entropy is important and in fact found in several areas of science:

• as above, in thermodynamics, where it is named the Gibbs variational principle;

• in large deviations, this also known as the Donsker-Varadhan variational formula Dembo & Zeitouni. (2010);

• in statistics, it is the well-known duality between maximum entropy and maximum likelihood estimation Altun & Smola. (2006) ; • finally, the theory of information geometry Amari. ( 2016) groups all three views and posits that there exists a general, dually flat Riemannian information manifold.

The general form of the result is as follows. For each Φ representing a rewards function r(s, a) or an estimator of it:

EQUATION

and the supremum is reached for the measure π * ∈ P defined by its Radon-Nikodym derivative equal to the Gibbs-Boltzmann measure yielding an energy policy:

EQUATION

In the special case where µ is the Lebesgue measure on a bounded domain (that is, the uniform policy), we find back the result 5 above, up to a constant irrelevant for maximization. In the general case, the mathematically inclined reader will also see this as a rephrasing of the fact the Bregman divergence associated with Shannon entropy is the Kullback-Leibler divergence. For completeness' sake, we provide here its full proof : Proposition 1. Donsker-Varadhan variational formula. Let G be a bounded measurable function on A and π, π be probability measures on A, with π absolutely continuous w.r.t. π.

EQUATION

where π * is a probability measure defined by the Radon-Nikodym derivative:

dπ * dπ = e G/τ

A e G/τ dπ (10)

Proof. A Gdπ -τ D KL [π π] = A Gdπ -τ A ln dπ dπ dπ = A Gdπ -τ A ln dπ dπ * dπ -τ A ln dπ * dπ dπ = A Å G -τ ln dπ * dπ ã dπ -τ D KL [π π * ] = A Å G -τ ln e G/τ A e G/τ dπ ã dπ -τ D KL [π π * ] = A ln A e G/τ dπ dπ -τ D KL [π π * ] = ln A e G/τ dπ -τ D KL [π π * ]

Proposition 2. Corollary :

max π ï A Gdπ -τ D KL [π π] ò = ln A e G/τ dπ (11)

and the maximum is attained uniquely by π * .

Proof. D KL [π π * ] ≥ 0, and D KL [π π * ] = 0 if and only if π = π * .

The link with reinforcement learning is made by picking Φ = r(s, a), π = π(a|s), λ = 1/β, and by recalling the implicit dependency of the right member on s but not on π at optimality, so that we can write 2017). Note that here V * (s) depends on the reference measure µ which is used to pick actions frequency -we can be off-policy, in which case V * is only a pseudo state-value function.

J * = V * (s) = β • log A e r(

2.2. PROVING SOFT Q-LEARNING EQUIVALENCE:

In this simplified one-step setting, this provides a short and direct proof that in expectation, and trained to optimality, soft Q-learning and policy gradients ascent yield the same result J. Schulman & Abbeel. ( 2017). Standard Q-learning is the special case β → 0, λ → ∞ where by the Laplace principle we recover V (s) → max A r(s, a) ; that is, the zero-temperature limit, with no entropy regularization. For simplicity of exposition, we have restricted so far to the proof in the bandit setting; now we extend it to the general case.

First by inserting V * (s) = sup π V π (s) in the representation formulas above applied to r(s, a) + γV * (s ), so that

V * (s) = sup π E π [r(s, a) + γV * (s )] -βH(π) = β • log A e r(s,a)+γV * (s ) β da (13)

The proof in the general case will then be finished if we assume that we could apply the Bellman optimality principle not to the hard-max, but to the soft-max operator. This requires proving that the soft-Bellman operator admits a unique fixed point, which is the above. By the Brouwer fixed point theorem, it is enough to prove that it is a contraction, or at least non-expansive (we assume that the discount factor γ < 1 to that end). We do so below, noting that this result has been shown many times in the literature, for instance in O. Nachum & Schuurmans. (2017b.) . Refining the soft-Bellman operator just like above, but in the multi-step case, by the expression

EQUATION

we get the:

Proposition 3. Nonexpansiveness of the soft-Bellman operator for the supremum norm f ∞ .

EQUATION

Proof. Let us consider two state-value functions V (1) (s) and V (2) (s) along with the associated action-value functions Q (1) (s, a) and Q (2) (s, a). Besides, denote MDP transition probability by p(s |s, a). Then :

B * V (1) -B * V (2) ∞ = max s (B * V (1) )(s) -(B * V (2) )(s) ≤ max s max a Q (1) (s, a) -Q (2) (s, a) = γ max s max a E s |s,a V (1) (s ) -V (2) (s ) ≤ γ max s max a p(s |s, a) 1 V (1) -V (2)

∞ by Hölder's inequality

= γ V (1) -V (2) ∞ < V (1) -V (2) ∞ 2.3 INTERPRETATION

In summary, the program of the proof was as below :

1. Write down the entropy-regularised policy gradient functional, and apply the Donsker-Varadhan formula to it. 2. Write down the resulting softmax Bellman operator as a solution to the sup maximization -this obviously also proves existence. 3. Show that the softmax operator, just like the hard max, is still a contraction for the max norm, hence prove uniqueness of the solution by fixed point theorem.

The above also shows formally that, should we discretize the action space A to replace integration over actions by finite sums, any strong estimator r(s, a) of r(s, a), applied to the partition function of rewards 1 λ log a e λr (s,a) , could be used for Q-learning-like iterations. This is because strong convergence would imply weak convergence (especially convergence of the characteristic function, via Levy's continuity theorem), and hence convergence towards the log-sum-exp cumulant genera- 2016) can be seen as a control variate balancing of the two terms in 7. In theory, the rewards distribution could be also recovered simply by varying λ (or β), for instance by inverse Laplace transform.

3. POLICY OPTIMALITY GAP AND TEMPERATURE ANNEALING:

In this section, we propose an inequality that relates the optimality gap of a policy -by how much that policy is sub-optimal on average -to the Kullback-Leibler divergence between the current policy and the optimum. The proof draws on ideas of convex analysis and Legendre transormation exposed earlier in the context of soft Q-learning.

Let us assume that X is a real-valued bounded random variable. We denote sup |X| ≤ M with M constant. Furthermore we assume that X is centered, that is, E[X] = 0. This can always be achieved just by picking Y = X -E[X].

Then, by the Hoeffding inequality :

log E e βX ≤ K β 2 2 (16)

with K a positive real constant, i.e., the variable X is sub-Gaussian, so that its cumulant generating function grows less than quadratically. By taking a Legendre transformation and inverting it, we get that for any pair of measures P and Q that are mutually absolutely continuous, one has

EQUATION

which by specializing Q to be the measure associated to P * the optimal policy, P θ the current parameterized policy, and X an advantage return r :

E P * r ≤ E P θ r + √ 2K » D KL P * ||P θ (18)

By the same logic, any upper bound on log E e βX can give us information about E Q X -E P X . This enables us to relate the size of Kullback-Leibler trust regions to the amount by which our policy could be improved. In fact by combining the entropy duality formula with the Legendre transformation, one easily proves the below : Proposition 4. Let X a real-valued integrable random variable, and f a convex and differentiable function such that f (0) = f (0) = 0. Then with f * : x → f * (x) = sup(βx -f (β)) the Legendre transformation of f , f * -1 its reciprocal, and P and Q any two mutually absolutely continuous measures, one has the equivalence:

EQUATION

:

In this article we follow the convention of convex analysis, that is, entropy H is taken to be convex, rather than that of information theory with H preceded by a negative sign and concave.

Figures and Tables:

s,a)/β dµ(a) (12) which is the definition of the one-step soft Bellman operator at optimum R. Fox & Tishby. (2015); O. Nachum & Schuurmans. (2017b.); T. Haarnoja & Levine. (

tive function above. Different estimators r(s, a) lead to different algorithms. When the MDP and the rewards function r are not known, the parameterised critic choice r(s, a) ≈ Q w (s, a) recovers Nachum's Path Consistency Learning O. Nachum & Schuurmans. (2017b.;c). O'Donoghue's PGQ method B. O'Donoghue & Mnih. (

Peer review (iclr2018):
 This paper uses a well-known variational representation of the relative entropy (the so-called Donsker-Varadhan formula) to derive an expression for the Bellman error with entropy regularization in terms of a certain log-partition function. This is stated in Equation (13) in the paper. However, this precise representation of the Bellman error (with costs instead of rewards and with minimization instead of maximization) has been known in the literature on risk-sensitive control, see, e.g., P. D. Pra, L. Meneghini, and W. J. Runggaldier, “Connections between stochastic control and dynamic games,” Math. Control Signals Systems, vol. 9, pp. 303–326, 1996. The same applies to contraction results for the "softmax" Bellman operator -- these results are not novel at all, see, e.g., D. Hernandez-Hernandez and S. I. Marcus, “Risk sensitive control of Markov processes in countable state space,” Systems and Control Letters, vol. 29, pp. 147–155, 1996. Also, there are some errors in the paper: for example, the functional of in Eq. (2) is concave, not convex, since the expression for the Shannon entropy in Eq. (3) has the wrong sign.