Entropy-Regularized Dynamic Programming

Infinite-horizon dynamic programming selects actions with a hard maximum. That operator is nondifferentiable at ties and produces a deterministic greedy choice. Can a modified control objective produce both a smooth Bellman operator and a stochastic optimal policy? Convex regularization supplies the link.

While the standard Bellman optimality equations use the max operator to determine the best action, an alternative formulation known as the smooth or soft Bellman optimality equations replaces it with a smooth approximation of the maximum. The history of these equations runs across two communities that rarely read each other. They appear in the work of the structural econometrician John Rust on the replacement of bus engines Rust (1987), together with an inverse problem and an algorithm to solve it. Ng & Russell (2000), who are usually credited with introducing inverse reinforcement learning, cite Rust, but the connection was then largely lost. Ziebart et al. (2008) rediscovered the same equations as maximum entropy inverse reinforcement learning, named after the maximum entropy principle. Haarnoja et al. (2017) built on Ziebart to obtain soft Q-learning, and soft actor-critic Haarnoja et al. (2018), one of the most widely used deep RL algorithms for continuous control, followed a year later.

In the infinite-horizon setting, the smooth Bellman optimality equations take the form:

Adopting an operator-theoretic perspective, we can define a nonlinear operator $\mathrm{L}_\beta$ such that the smooth value function of an MDP is then the solution to the following fixed-point equation:

As $\beta \to \infty$, $\mathrm{L}_\beta$ converges to the standard Bellman operator $\Bellman$. Furthermore, it can be shown that the smooth Bellman operator is a contraction mapping in the supremum norm, and therefore has a unique fixed point. However, as opposed to the usual “hard” setting, the fixed point of $\mathrm{L}_\beta$ is associated with the value function of an optimal stochastic policy defined by the softmax distribution:

Despite the confusing terminology, the above “softmax” policy is the smooth counterpart of the argmax in the original optimality equation, not of the max: it is a soft-argmax. The smooth counterpart of the max is the log-sum-exp. The same policy is also called a Boltzmann or Gibbs policy. As the temperature $1/\beta$ goes to zero, the softmax concentrates on the maximizing actions and we recover the greedy policy and the hard Bellman equation.

Stochastic Policies: Exploration and the Partition Function¶

Moving from the argmax to the softmax turns deterministic policies into stochastic ones, which is both useful and costly. It is useful because noise in the actions is a way to explore. In RL the agent usually gathers its own data, and if it always took the action it currently believes best it would never learn about the others. The problem is not specific to RL. An engineer identifying a model of a plant must also choose inputs that reveal the dynamics, and in system identification this is called exciting the system: a persistently exciting input is one rich enough for the parameters to be identifiable from the data.

It is costly when the action set is continuous. The softmax policy is then a density $\pi(a \mid s) \propto \exp(\beta q(s,a))$ whose normalizing constant, the partition function $\int \exp(\beta q(s,a))\, da$, is an integral with no closed form in general. The log-sum-exp value has the same problem, since it is the logarithm of that integral. This is the intractable partition function familiar from energy-based models and probabilistic graphical models. Numerical quadrature is an option in low dimension but is rarely used. Haarnoja et al. (2017) sampled from the softmax policy over continuous actions with amortized Stein variational gradient descent, which proved expensive; soft actor-critic Haarnoja et al. (2018) instead fits a tractable parametric policy to the softmax, an idea we return to in the chapters on fitted value methods and policy learning.

This formulation is interesting for several reasons. First, smoothness is a desirable property from an optimization standpoint. Unlike $\gamma$, we view $\beta$ as a hyperparameter of our algorithm, which we can control to achieve the desired level of accuracy.

Second, we presented the equations pragmatically, by replacing the max with the log-sum-exp (a smooth maximum) and the argmax with the softmax (a smooth argmax). The same equations come out of two other starting points, and this chapter follows all three routes:

1. Smoothing the operator. Replace every max by a log-sum-exp, as above. This is the route of the next subsection, and the justification is computational: a smooth operator has gradients everywhere.

2. Noise on the rewards. Keep the hard Bellman equation, but suppose that each action’s reward is perturbed by independent Gumbel noise that the decision maker sees and the modeler does not. Integrating the noise out gives the log-sum-exp (Gumbel Noise on the Rewards). This is how Rust (1987) motivated the equations, following the discrete choice models of econometrics.

3. Entropy regularization. Keep the rewards, but add a bonus proportional to the entropy of the policy in every state. The regularized Bellman equation is again the log-sum-exp equation (Regularized Markov Decision Processes). This is the reading behind maximum entropy RL and soft actor-critic.

Each route brings its own tools: smoothness gives differentiability, the noise model gives a likelihood for observed behavior, and the regularization view gives convex duality. A fourth reading, close to the third, starts from the energy-based models of supervised learning, where a softmax turns unnormalized scores into a distribution; this is essentially what Ziebart et al. (2008) did. It connects to probabilistic graphical models, where finding an optimal smooth policy becomes an inference problem. This is the idea of control as inference, whose converse, inference as control, is now used to derive samplers and amortized inference methods with RL Levine et al. (2018).

Smooth Value Iteration Algorithm¶

Before iterating $\mathrm{L}_\beta$, we should check that iterating it is the right thing to do, that is, that it is a contraction. It is, in the sup-norm and with the same factor $\gamma$ as the hard Bellman operator. The proof uses the same three facts as for $\Bellman$. The log-sum-exp is monotone, it commutes with adding a constant to all of its arguments, and $\mathrm{L}_\beta$ maps a uniform shift $c\mathbf{1}$ of $v$ into a shift $\gamma c\mathbf{1}$ of $\mathrm{L}_\beta v$. From $v \le u + \|v-u\|_\infty\mathbf{1}$ we get $\mathrm{L}_\beta v \le \mathrm{L}_\beta u + \gamma\|v-u\|_\infty\mathbf{1}$, and exchanging $u$ and $v$ gives the contraction. A word of caution about the converse: failing to show that an operator is a contraction does not mean that its fixed point fails to exist or that no algorithm finds it. Contraction is a convenient sufficient condition, and other fixed-point theorems cover other cases.

Successive approximation applied to $\mathrm{L}_\beta$ is smooth value iteration. It has the structure of value iteration, with a log-sum-exp wherever value iteration had a max and a softmax policy at the end where value iteration returned a greedy one.

Differences from standard value iteration:

• Line 6 uses $\frac{1}{\beta} \log \sum_a \exp(\beta \cdot q(s,a))$ instead of $\max_a q(s,a)$

• Line 10 extracts a stochastic policy using softmax instead of a deterministic argmax policy

• As $\beta \to \infty$, the algorithm converges to standard value iteration

• Lower $\beta$ values produce more stochastic policies with higher entropy

What the stopping rule guarantees. Because $\mathrm{L}_\beta$ is a $\gamma$-contraction, the a posteriori bound of the Banach fixed-point theorem applies unchanged, and the stopping test of line 9 guarantees $\|v - v^\star_\beta\|_\infty \le \varepsilon/2$. The proof that value iteration returns an $\varepsilon$-optimal policy also carries over, with one change of meaning. The softmax policy satisfies $\mathrm{L}_{\pi,\Omega} v = \mathrm{L}_\beta v$ for the entropy-regularized evaluation operator of Regularized Bellman Operators, with regularizer $\Omega(\pi(\cdot|s)) = \frac{1}{\beta}\sum_a \pi(a|s)\log\pi(a|s)$,, just as a greedy policy satisfies $\mathrm{L}_\pi v = \Bellman v$. Repeating the proof of Proposition 2 with these operators shows that the returned policy is $\varepsilon$-optimal for the entropy-regularized objective. How far is that from optimal for the original rewards? Since $\max_a x_a \le \frac{1}{\beta}\log\sum_a e^{\beta x_a} \le \max_a x_a + \frac{\log|\mathcal{A}|}{\beta}$, where $|\mathcal{A}|$ is the largest number of actions in any state, the two fixed points satisfy

and the softmax policy returned by the algorithm loses at most $\varepsilon + \frac{\log|\mathcal{A}|}{\beta(1-\gamma)}$ against the optimal value of the unregularized MDP. The temperature therefore adds a bias that does not shrink with more iterations; it is the price of smoothness and of exploration.

Gumbel Noise on the Rewards¶

Why does adding independent Gumbel perturbations to action rewards produce a log-sum-exp value before the perturbation is observed?

We can obtain the smooth Bellman equation by considering a setting in which we have Gumbel noise added to the reward function. This derivation provides theoretical insight and also connects to practical modeling scenarios where rewards have random perturbations.

Step 1: Define the Augmented MDP with Gumbel Noise¶

At each time period and state $s$, we draw an action-indexed shock vector:

These shocks are independent across time periods, states, and actions, and are independent of the MDP transition dynamics $p(\cdot | s, a)$.

The Gumbel distribution with location parameter $\mu$ and scale parameter $1/\beta$ has probability density function:

To generate a Gumbel-distributed random variable, we can use inverse transform sampling: $X = \mu - \frac{1}{\beta} \ln(-\ln(U))$ where $U$ is uniform on $(0,1)$.

We now define an augmented MDP with:

• Augmented state: $\tilde{s} = (s, \boldsymbol{\epsilon})$ where $s \in \mathcal{S}$ and $\boldsymbol{\epsilon} \in \mathbb{R}^{|\mathcal{A}_s|}$

• Augmented reward: $\tilde{r}(\tilde{s}, a) = r(s,a) + \epsilon(a)$

• Augmented transition: $\tilde{p}(\tilde{s}' | \tilde{s}, a) = p(s' | s, a) \cdot p(\boldsymbol{\epsilon}')$

The transition factorizes because the next shock vector $\boldsymbol{\epsilon}'$ is drawn independently of the current state and action (conditional independence).

Step 2: The Hard Bellman Equation on the Augmented State Space¶

The Bellman optimality equation for the augmented MDP is:

Here the expectation is over the next augmented state $(s', \boldsymbol{\epsilon}')$, which includes both the next state $s' \sim p(\cdot | s, a)$ and the next shock vector $\boldsymbol{\epsilon}' \sim p(\cdot)$.

This is a perfectly well-defined Bellman equation, and an optimal stationary policy exists:

However, this equation is computationally intractable because:

• The state space is continuous and infinite-dimensional

• The shocks are fresh each period

• We would need to solve for $\tilde{v}$ over an uncountable domain

We never solve this equation directly. Instead, we use it as a mathematical device to derive the smooth Bellman equation.

Step 3: Define the Ex-Ante (Inclusive) Value Function¶

The idea here is to consider the expected value before observing the current shocks. We define what some authors in econometrics call the inclusive value or ex-ante value:

This is the value of being in state $s$ before we observe the current-period shock vector $\boldsymbol{\epsilon}$.

Step 4: Separate the Deterministic and Random Components¶

Now we take the expectation of the augmented Bellman equation with respect to the current shocks only (everything that does not depend on the current $\boldsymbol{\epsilon}$ can be pulled out).

First, note that by the law of iterated expectations and independence of shocks across time:

This follows from our definition of $v$ and the fact that the next shock is independent of everything else.

Now define the deterministic part of the right-hand side:

This is the expected return from taking action $a$ in state $s$ without the shock. Using this notation, the augmented Bellman equation becomes:

Taking the expectation over $\boldsymbol{\epsilon}$ on both sides:

Step 5: Apply the Gumbel Random Utility Identity¶

We now invoke a result from extreme value theory:

Applying this identity to our problem (with mean-zero shocks):

Substituting the definition of $x_a(s)$:

We have arrived at the smooth Bellman equation.

Step 6: Summary of the Derivation¶

To recap the logical flow:

1. We constructed an augmented MDP with state $(s, \boldsymbol{\epsilon})$ where shocks perturb rewards

2. We wrote the standard Bellman equation for this augmented MDP (hard max, but over an infinite-dimensional state space)

3. We defined the ex-ante value $v(s) = \mathbb{E}_{\boldsymbol{\epsilon}}[\tilde{v}(s, \boldsymbol{\epsilon})]$ to eliminate the continuous shock component

4. We separated deterministic and random terms: $\tilde{v}(s, \boldsymbol{\epsilon}) = \max_a \{x_a(s) + \epsilon(a)\}$

5. We applied the Gumbel identity to evaluate $\mathbb{E}_{\boldsymbol{\epsilon}}[\max_a \{\cdots\}]$ in closed form as a log-sum-exp

The augmented MDP with shocks exists only as a mathematical device. We never approximate $\tilde{v}$, never discretize $\boldsymbol{\epsilon}$, and never enumerate the augmented state space. The only computational object we work with is $v(s)$ on the original (finite) state space, which satisfies the smooth Bellman equation.

Deriving the Optimal Smooth Policy¶

Now that we have derived the smooth value function, we can also obtain the corresponding optimal policy. The question is: what policy should we follow in the original MDP (without explicitly conditioning on shocks)?

In the augmented MDP, the optimal policy is deterministic but depends on the shock realization:

However, we want a policy for the original state space $s$ (not the augmented state). We obtain this by marginalizing over the current shocks, essentially asking: “what is the probability that action $a$ is optimal when we average over all possible shock realizations?”

Define an indicator function:

where $x_a(s) = r(s,a) + \gamma \sum_{j \in \mathcal{S}} p(j|s,a) v(j)$ as before.

The ex-ante probability that action $a$ is optimal at state $s$ is:

This is the probability that action $a$ achieves the maximum when utilities are perturbed by Gumbel noise.

Applying this result to our problem:

This is the softmax policy or Gibbs/Boltzmann policy with inverse temperature $\beta$.

Properties:

• As $\beta \to \infty$: the policy becomes deterministic, concentrating on the action(s) with highest $x_a(s)$ (recovers standard greedy policy)

• As $\beta \to 0$: the policy becomes uniform over all actions (maximum entropy)

• For finite $\beta > 0$: the policy is stochastic, with probability mass proportional to exponentiated Q-values

This completes the derivation: the smooth Bellman equation yields a value function $v(s)$, and the corresponding optimal policy is the softmax over Q-values.

Regularized Markov Decision Processes¶

Which convex penalty on action distributions generates a desired smooth maximum through conjugate duality?

Regularized MDPs Geist et al. (2019) provide another perspective on how the smooth Bellman equations come to be. This framework offers a more general approach in which we seek to find optimal policies under the infinite horizon criterion while also accounting for a regularizer that influences the kind of policies we try to obtain.

Let’s set up some necessary notation. First, recall that the policy evaluation operator for a stationary policy with decision rule $\pi$ is defined as:

where $\mathbf{r}_\pi$ is the expected reward vector under policy $\pi$, $\gamma$ is the discount factor, and $\mathbf{P}_\pi$ is the state transition probability matrix under $\pi$. A complementary object to the value function is the q-function (or Q-factor) representation:

The policy evaluation operator can then be written in terms of the q-function as:

Legendre-Fenchel Transform¶

The workhorse behind the theory of regularized MDPs is the Legendre-Fenchel transform, also known as the convex conjugate. For a strongly convex function $\Omega: \Delta_{\mathcal{A}} \rightarrow \mathbb{R}$, its Legendre-Fenchel transform $\Omega^*: \mathbb{R}^{\mathcal{A}} \rightarrow \mathbb{R}$ is defined as:

An important property of this transform is that it has a unique maximizing argument, given by the gradient of $\Omega^*$. This gradient is Lipschitz and satisfies:

An important example of a regularizer is the negative entropy, which gives rise to the smooth Bellman equations as we are about to see.

Regularized Bellman Operators¶

How do the regularizer and its convex conjugate alter Bellman evaluation, policy improvement, and their contraction properties?

With these concepts in place, we can now define the regularized Bellman operators:

1. Regularized Policy Evaluation Operator $(\mathrm{L}_{\pi,\Omega})$:

   $$[\mathrm{L}_{\pi,\Omega} v](s) = \langle q(s,\cdot), \pi(\cdot | s) \rangle - \Omega(\pi(\cdot | s))$$

   (29)

2. Regularized Bellman Optimality Operator $(\mathrm{L}_\Omega)$:

   $$[\mathrm{L}_\Omega v](s) = [\max_\pi \mathrm{L}_{\pi,\Omega} v ](s) = \Omega^*(q(s, \cdot))$$

   (30)

It can be shown that the addition of a regularizer in these regularized operators still preserves the contraction properties, and therefore the existence of a solution to the optimality equations and the convergence of successive approximation.

The regularized value function of a stationary policy with decision rule $\pi$, denoted by $v_{\pi,\Omega}$, is the unique fixed point of the operator equation:

Under the usual assumptions on the discount factor and the boundedness of the reward, the value of a policy can also be found in closed form by solving for $\mathbf{v}$ in the linear system of equations:

where $[\boldsymbol{\Omega}_\pi](s) = \Omega(\pi(\cdot|s))$ is the vector of regularization terms at each state.

The associated state-action value function $q_{\pi,\Omega}$ is given by:

The regularized optimal value function $v^*_\Omega$ is then the unique fixed point of $\mathrm{L}_\Omega$ in the fixed point equation:

The associated state-action value function $q^*_\Omega$ is given by:

An important result in the theory of regularized MDPs is that there exists a unique optimal regularized policy. Specifically, if $\pi^*_\Omega$ is a conserving decision rule (i.e., $\pi^*_\Omega = \arg\max_\pi \mathrm{L}_{\pi,\Omega} v^*_\Omega$), then the randomized stationary policy $\boldsymbol{\pi} = \mathrm{const}(\pi^*_\Omega)$ is the unique optimal regularized policy.

In practice, once we have found $v^*_\Omega$, we can derive the optimal decision rule by taking the gradient of the convex conjugate evaluated at the optimal action-value function:

Recovering the Smooth Bellman Equations¶

Under this framework, we can recover the smooth Bellman equations by choosing $\Omega$ to be the negative entropy, and obtain the softmax policy as the gradient of the convex conjugate. Let’s show this explicitly:

1. Using the negative entropy regularizer:

   $$\Omega(d(\cdot|s)) = \sum_{a \in \mathcal{A}_s} d(a|s) \ln d(a|s)$$

   (37)

2. The convex conjugate:

   $$\Omega^*(q(s, \cdot)) = \ln \sum_{a \in \mathcal{A}_s} \exp q(s,a)$$

   (38)

3. Now, let’s write out the regularized Bellman optimality equation:

   $$v^*_\Omega(s) = \Omega^*(q^*_\Omega(s, \cdot))$$

   (39)

4. Substituting the expressions for $\Omega^*$ and $q^*_\Omega$:

   $$v^*_\Omega(s) = \ln \sum_{a \in \mathcal{A}_s} \exp \left(r(s, a) + \gamma \sum_{j \in \mathcal{S}} p(j|s,a) v^*_\Omega(j)\right)$$

   (40)

This matches the form of the smooth Bellman equation we derived earlier, with the log-sum-exp operation replacing the max operation of the standard Bellman equation.

Furthermore, the optimal policy is given by the gradient of $\Omega^*$:

This is the familiar softmax policy we encountered in the smooth MDP setting.

Smooth Policy Iteration Algorithm¶

Now that we’ve seen how the regularized MDP framework leads to smooth Bellman equations, we present smooth policy iteration. Unlike value iteration which directly iterates the Bellman operator, policy iteration alternates between policy evaluation and policy improvement steps.

Key properties of smooth policy iteration:

1. Entropy-regularized evaluation: The policy evaluation step (line 12 of Algorithm 2) accounts for the entropy bonus $\alpha H(\pi(\cdot|s))$ where $\alpha = 1/\beta$

2. Stochastic policy improvement: The policy improvement step (lines 12-14 of Algorithm 3) uses softmax instead of deterministic argmax, producing a stochastic policy

3. Temperature parameter:

   • Higher $\beta$ produces policies closer to deterministic (lower entropy)

   • Lower $\beta$ produces more stochastic policies (higher entropy)

   • As $\beta \to \infty$, the method recovers standard policy iteration

4. Convergence: Like standard policy iteration, this algorithm converges to the unique optimal regularized value function and policy

5. Partial improvement: As in the hard case, the improvement does not need to be applied in every state for the method to make progress. The policy-iteration loops hidden inside actor-critic methods make use of this.

Smooth Policy Iteration Is Newton’s Method¶

The link between policy iteration and the Newton-Kantorovich method (Newton-Kantorovich and Policy Iteration) is easier to see here than in the hard case, because $\mathrm{L}_\beta$ is differentiable everywhere and there are no ties to worry about. The derivative of the log-sum-exp with respect to its arguments is the softmax, so the Fréchet derivative of $\mathrm{L}_\beta$ at $v$ is

the transition matrix of the softmax policy. A Newton step on $v - \mathrm{L}_\beta v = 0$ solves

At the softmax policy the log-sum-exp equals the expected $q$ plus the entropy bonus, $\mathrm{L}_\beta v = \mathbf{r}_{\pi_v} + \gamma\mathbf{P}_{\pi_v} v + \frac{1}{\beta}\mathbf{H}_{\pi_v}$. The right-hand side is therefore $\mathbf{r}_{\pi_v} + \frac{1}{\beta}\mathbf{H}_{\pi_v}$, and the Newton step is exactly the entropy-regularized evaluation of the softmax policy. Smooth policy iteration is the Newton-Kantorovich method applied to the smooth Bellman equation, without the semismooth machinery that the hard max requires.

Rust (1987) solved his smooth Bellman equation this way. He did not call it policy iteration. He recognized an operator equation, a root-finding problem in a function space, and applied Newton-Kantorovich to it, after a few rounds of successive approximation to get close enough for Newton’s method to converge quickly.

Equivalence Between Smooth Bellman Equations and Entropy-Regularized MDPs¶

We have now seen two distinct ways to arrive at smooth Bellman equations. Earlier in this chapter, we introduced the logsumexp operator as a smooth approximation to the max operator, motivated by analytical tractability and the desire for differentiability. Just now, we derived the same equations through the lens of regularized MDPs, where we explicitly penalize the entropy of policies. These two perspectives are mathematically equivalent: solving the smooth Bellman equation with inverse temperature parameter $\beta$ yields exactly the same optimal value function and optimal policy as solving the entropy-regularized MDP with regularization strength $\alpha = 1/\beta$. The two formulations are not merely similar. They describe identical optimization problems.

To see this equivalence clearly, consider the standard MDP problem with rewards $r(s,a)$ and transition probabilities $p(j|s,a)$. The regularized MDP framework tells us to solve:

where $H(\pi(\cdot|s)) = -\sum_a \pi(a|s) \ln \pi(a|s)$ is the entropy of the policy at state $s$, and $\alpha > 0$ is the entropy regularization strength.

We can rewrite this objective by absorbing the entropy term into a modified reward function. Define the entropy-augmented reward:

However, this formulation makes the reward depend on the entire policy at each state, which is awkward. We can reformulate this more cleanly by expanding the entropy term. Recall that the entropy is:

When we take the expectation over actions drawn from $\pi$, we have:

since the entropy doesn’t depend on which action is actually sampled. But we can also write this as:

This shows that adding $\alpha H(\pi(\cdot|s))$ to the expected reward at state $s$ is equivalent to adding $-\alpha \ln \pi(a|s)$ to the reward of taking action $a$ at state $s$. More formally:

The entropy bonus at each state, when averaged over the policy, becomes a per-action penalty proportional to the negative log probability of the action taken. This reformulation is more useful because the modified reward now depends only on the state, the action taken, and the probability assigned to that specific action by the policy, not on the entire distribution over actions.

This expression shows that entropy regularization is equivalent to adding a state-action dependent penalty term $-\alpha \ln \pi(a|s)$ to the reward. Intuitively, this term amounts to paying a cost for low-entropy (deterministic) policies.

Now, when we write down the Bellman equation for this entropy-regularized problem, at each state $s$ we need to find the decision rule $d(\cdot|s) \in \Delta(\mathcal{A}_s)$ (a probability distribution over actions) that maximizes:

Here $\Delta(\mathcal{A}_s) = \{d(\cdot|s) : d(a|s) \geq 0, \sum_a d(a|s) = 1\}$ denotes the probability simplex over actions available at state $s$. The optimization is over randomized decision rules at each state, constrained to be valid probability distributions.

This is a convex optimization problem with a linear constraint. We form the Lagrangian:

where $\lambda$ is the Lagrange multiplier enforcing the normalization constraint. Taking the derivative with respect to $d(a|s)$ and setting it to zero:

Solving for $d^*(a|s)$:

Using the normalization constraint $\sum_a d^*(a|s) = 1$ to solve for $\lambda$:

Therefore:

Substituting this back into the Bellman equation and simplifying:

Setting $\beta = 1/\alpha$ (the inverse temperature), this becomes:

We recover the smooth Bellman equation we derived earlier using the logsumexp operator. The inverse temperature parameter $\beta$ controls how closely the logsumexp approximates the max: as $\beta \to \infty$, we recover the standard Bellman equation, while for finite $\beta$, we have a smooth approximation that corresponds to optimizing with entropy regularization strength $\alpha = 1/\beta$.

The optimal policy is:

which is exactly the softmax policy parametrized by inverse temperature.

The derivation establishes the complete equivalence: the value function $v^*$ that solves the smooth Bellman equation is identical to the optimal value function $v^*_\Omega$ of the entropy-regularized MDP (with $\Omega$ being negative entropy and $\alpha = 1/\beta$), and the softmax policy that is greedy with respect to this value function achieves the maximum of the entropy-regularized objective. Both approaches yield the same numerical solution: the same values at every state and the same policy prescriptions. The only difference is how we conceptualize the problem: as smoothing the Bellman operator for computational tractability, or as explicitly trading off reward maximization against policy entropy.

This equivalence has important implications. When we use smooth Bellman equations with a logsumexp operator, we are implicitly solving an entropy-regularized MDP. Conversely, when we explicitly add entropy regularization to an MDP objective, we arrive at smooth Bellman equations as the natural description of optimality. This dual perspective will prove valuable in understanding various algorithms and theoretical results. For instance, in soft actor-critic methods and other maximum entropy reinforcement learning algorithms, the connection between smooth operators and entropy regularization provides both computational benefits (differentiability) and conceptual clarity (why we want stochastic policies).

Entropy-Regularized Dynamic Programming Algorithms¶

While the smooth Bellman equations (using logsumexp) and entropy-regularized formulations are mathematically equivalent, it is instructive to present the algorithms explicitly in the entropy-regularized form, where the entropy bonus appears directly in the update equations.

Features:

• Line 11 updates the policy using the softmax of Q-values, with temperature $\alpha$

• Line 14 explicitly computes the entropy-regularized value: expected Q-value plus entropy bonus

• The algorithm maintains and updates a stochastic policy throughout

• As $\alpha \to 0$ (or equivalently $\beta \to \infty$), this recovers standard value iteration

Features:

• Policy Evaluation (lines 3-15): Computes the value of the current policy including entropy bonus

  • Option 1: Iterative method (successive approximation)

  • Option 2: Direct solution via linear system

• Policy Improvement (lines 16-29): Updates policy to softmax over Q-values

• Line 14 shows the vector form: the linear system includes the entropy vector $\mathbf{H}_\pi$

• The algorithm alternates between evaluating the current stochastic policy and improving it

• Converges to the unique optimal entropy-regularized policy

Rust’s Bus Engines and Inverse Reinforcement Learning¶

What can we learn about a decision maker’s goals from records of what they did?

Rust’s 1987 paper is worth reading for three reasons: it contains the smooth Bellman equation, it poses what is now called inverse reinforcement learning, and it solves that problem with a bilevel method that relies on implicit differentiation, a tool that became popular in machine learning three decades later for hyperparameter optimization.

The problem. Harold Zurcher was the superintendent of maintenance at the Madison Metropolitan bus company. Rust had his maintenance records: for each bus, the odometer reading each month, and the months in which Zurcher replaced the engine. Replacing an engine is expensive, while keeping an old engine running costs more and more as the mileage grows. The question was how Zurcher decided when to replace. Rust is a structural econometrician. Structural econometrics does not stop at predicting behavior; it posits a mechanism that generates it, here a decision maker solving an MDP, and fits the parameters of that mechanism to data. The fitted mechanism can then answer questions the data alone cannot, such as how behavior would change if the price of an engine changed.

The model. The state $s$ is the mileage since the last replacement, discretized into bins. Each month there are two actions, keep ($a=0$) or replace ($a=1$). Keeping costs $c(s;\theta)$, increasing in $s$; replacing costs a fixed amount $RC$ and resets the mileage. With parameters $\theta$ collecting $RC$ and those of $c$, the reward is $r_\theta(s,0) = -c(s;\theta)$ and $r_\theta(s,1) = -RC - c(0;\theta)$, and the mileage transitions are estimated directly from the odometer data. The data contradict any deterministic policy: two buses with the same mileage are sometimes treated differently. Rust’s answer was the Gumbel model of Gumbel Noise on the Rewards. Zurcher sees, in addition to $s$, a shock $\epsilon(a)$ for each action that the econometrician does not see, and acts optimally given both. Integrating out the shocks gives the smooth Bellman equation and the softmax choice probabilities

This is the second, deeper reason Rust used these equations. Besides being smooth, they follow from the random-utility models of McFadden (1974), the standard statistical basis of discrete choice in econometrics, in the same way that least squares follows from assuming Gaussian noise. In machine learning terms, McFadden’s conditional logit is multiclass logistic regression with a structural interpretation.

The estimator. Given observed pairs $(s_t, a_t)$, maximize the log-likelihood $\ell(\theta) = \sum_t \log \pi_\theta(a_t \mid s_t)$. Every evaluation of $\ell$ requires solving the smooth Bellman equation for the current $\theta$, so the problem is bilevel: an outer maximization over $\theta$ around an inner fixed-point problem. Rust called his algorithm the nested fixed point (NFXP) algorithm. The gradient of $\ell$ needs $\partial v_\theta / \partial\theta$, which the implicit function theorem provides without differentiating through the iterations of the inner solver. Differentiating $v_\theta = \mathrm{L}_{\beta,\theta} v_\theta$ and using the derivative of $\mathrm{L}_\beta$ from Smooth Policy Iteration Is Newton’s Method,

The matrix to invert is the one of policy evaluation, already factored by the Newton steps of the inner solver. For rewards linear in the parameters, $r_\theta(s,a) = \theta^\top\phi(s,a)$, this derivative is the vector of expected discounted feature counts under the softmax policy, the quantity that Ziebart et al. (2008) matches to the empirical feature counts. The score of one observation is then

What the model assumes. The setup is a strong one, and naming its assumptions explains why inverse RL is hard in general.

• Rationality. The decision maker is assumed to solve the MDP exactly. People do not; the literature on bounded rationality studies how they fall short, and Rust himself has written skeptically about whether people follow Bellman’s principle of optimality. The assumption is still a useful starting point, in the same way a linear model is.

• Observability. Rust observes the state and the action. In many applications one or both are missing. With logged prices, for instance, an unchanged price may be a decision to keep it or simply the absence of a decision, and the action itself must be inferred, which makes the problem partially observable.

• Identifiability. Many reward functions explain the same behavior equally well. With hard maxima, a constant reward makes every policy optimal, and adding a shaping term $\gamma\Phi(s') - \Phi(s)$ to any reward leaves the optimal policies unchanged Ng et al. (1999). The map from rewards to behavior is many-to-one, so the data can at best single out a set of candidate rewards. Structural econometrics restores identification by restricting the reward to a parametric family, fixing the discount factor and the scale $\beta$, and normalizing one action’s reward. Whether such restrictions are acceptable depends on the goal: predicting what Zurcher would do under new engine prices is a weaker demand than recovering what he “really” wanted.

Summary and Outlook¶

Entropy regularization replaces hard action selection with a smooth conjugate operator and produces a stochastic optimal policy. Gumbel perturbations, log-sum-exp Bellman updates, and regularized policy iteration describe the same construction from probabilistic, variational, and algorithmic viewpoints. Smooth policy iteration is Newton’s method on the smooth Bellman equation, and Rust’s nested fixed-point estimator uses the same derivative to recover reward parameters from observed behavior.

The same log-sum-exp form appears over whole trajectories in continuous time. Path-integral stochastic control examines systems driven by Gaussian disturbances whose Hamilton--Jacobi--Bellman equation becomes linear under a logarithmic transformation, so that optimal feedback can be estimated from weighted trajectories.

Smoothness changes the operator but does not remove the need to represent its unknown value function. How can an infinite-dimensional functional equation be reduced to finitely many coefficients and test conditions? Weighted-residual methods provide the general approximation machinery.

Self-checks¶