Sparse Policy Regularization via Tsallis Entropy

87 concepts42 papers1 proposal

In reinforcement learning (RL), agents traditionally navigate the exploration-exploitation trade-off using maximum entropy frameworks. By adding a Shannon entropy penalty to the reward objective, algorithms like Soft Actor-Critic (SAC) encourage broad exploration.

However, Shannon entropy forces a mathematical compromise: the resulting optimal policy is a softmax distribution. Because the exponential function never reaches zero, a softmax policy must allocate a non-zero probability to every single action available in the environment.

In small action spaces, this "long tail" of low probability is harmless. But in complex, real-world environments, this mathematical artifact becomes a liability. Sparse policy regularization addresses this flaw by replacing Shannon entropy with alternative regularizers—most notably Tsallis entropy—to produce policies that can assign a probability of exactly zero to suboptimal or dangerous actions.


The Tyranny of the Long Tail

To understand why standard exploration fails, consider an environment with a massive or finely discretized action space. Under a softmax policy, even if an action is known to be catastrophic, it still receives a tiny fraction of probability mass.

This creates two fundamental failure modes:

  1. The Curse of Action-Space Size: As the number of available actions grows, the cumulative probability leaked into the long tail of suboptimal actions increases. The performance gap between the regularized policy and the true optimal policy degrades logarithmically with the size of the action space.
  2. The Offline RL Vulnerability: In offline reinforcement learning, an agent learns from a fixed dataset without environment interaction. If an out-of-distribution (OOD) action is erroneously assigned a high value due to function approximation errors, a softmax policy will sample it. Without the ability to test the action and correct its mistake, the agent falls into a loop of catastrophic over-optimism.

As the authors of Sparse Markov Decision Processes With Causal Sparse Tsallis Entropy Regularization for Reinforcement Learning observe, adjusting temperature parameters can make a softmax policy sharper, but it can never achieve true sparsity. The agent remains perpetually distracted by the noise of low-value actions.


The Geometry of Sparsity

How do we modify the objective to allow for true zero probabilities? The answer lies in changing the mathematical curvature of the regularizer.

Shannon entropy is defined as: $$\mathcal{H}(\pi) = -\sum_{a} \pi(a|s) \log \pi(a|s)$$

The $\log \pi(a|s)$ term acts as a barrier function. As $\pi(a|s)$ approaches zero, $\log \pi(a|s)$ approaches negative infinity, making it infinitely expensive for the optimization objective to ever set a probability to absolute zero.

Sparse policy regularization replaces this with generalized entropy measures, most frequently Tsallis entropy (specifically where the entropic index $q=2$, which corresponds to a quadratic penalty): $$\mathcal{H}_2(\pi) = \frac{1}{2} \left(1 - \sum_{a} \pi(a|s)^2\right)$$

   Shannon Entropy (Softmax)            Tsallis Entropy (Sparsemax)

         Value Simplex                        Value Simplex
              /\                                   /\
             /  \                                 /  \
            /    \                               /    \
           /  •   \                             / •    \
          /________\                           /________\
     Asymptotically avoids                Explicitly hits the
     the boundaries.                      boundaries (Zero probability).

Geometrically, maximizing an objective with a quadratic Tsallis penalty acts as a projection of action values onto the probability simplex. Instead of asymptotically approaching the edges, the optimization trajectory can directly intersect the boundaries of the simplex. This transformation, often implemented via the sparsemax operator, effectively truncates the distribution. Actions whose estimated values fall below a dynamically computed threshold are clipped to exactly zero.


Why It Works: Error Bounding and OOD Immunity

Shifting from Shannon to Tsallis entropy fundamentally alters how an agent scales and protects itself from noise.

1. Independence from Action Space Size

In Path Consistency Learning in Tsallis Entropy Regularized MDPs, Yinlam Chow et al. proved that satisfying a consistency relationship under Tsallis regularization guarantees a policy whose sub-optimality error bound remains constant, regardless of how many actions are added to the environment. By assigning zero probability to the expanding universe of irrelevant actions, the agent prunes the search space and focuses its exploration budget entirely on a promising subset.

2. Eliminating Out-of-Distribution Actions

In offline settings, this pruning acts as an implicit safety shield. Haoran Xu et al. introduced Sparse Q-Learning (SQL), demonstrating that incorporating sparsity into value updates allows agents to ignore low-quality transitions or OOD actions entirely.

By applying a chi-squared divergence regularizer, Haoran Xu et al. derived an in-sample learning update rule where actions below a value threshold receive zero weight. This prevents function approximation errors from propagating through the Bellman equation, isolating the value function from dataset noise.

Similarly, Lingwei Zhu et al. showed that Tsallis divergence filters out over-optimistic value estimates during offline training. To make these sparse policies stable in continuous control, Lingwei Zhu developed a two-stage "Fat-to-Thin" optimization framework, transferring knowledge from a heavy-tailed proposal policy to a sparse actor, concentrating probability mass strictly on a narrow band of optimal actions.


Applications Across the RL Landscape

The benefits of sparse regularization extend far beyond standard discrete action spaces, offering structural advantages across several domains:

  • Monte-Carlo Tree Search (MCTS): In high-branching environments, standard tree search algorithms waste computational budget evaluating highly suboptimal branches. Tuan Quang Dam et al. demonstrated that Tsallis entropy regularization (TENTS) naturally induces sparse action distributions during tree search, effectively pruning suboptimal branches and achieving an exponential convergence rate compared to the polynomial rate of standard dense methods.
  • Imitation Learning: When learning from expert demonstrations, matching the full continuous distribution of an expert can lead to compounding errors. Kyungjae Lee et al. introduced Maximum Causal Tsallis Entropy Imitation Learning, showing that sparse multi-modal policies can cleanly capture complex, multi-path expert behaviors while ignoring the long tail of low-probability noise.
  • Discrete Prompt Tuning: Finding human-readable "hard prompts" to control large language models can be framed as an RL problem over a massive vocabulary action space. Yunseon Choi et al. utilized Tsallis entropy regularization to force the RL agent to concentrate on a small subset of high-value tokens, filtering out the noisy long tail of the vocabulary and discovering prompts that are both highly performant and human-interpretable.
  • Policy Mirror Descent: Rather than relying on fixed regularizers, Carlo Alfano et al. used evolutionary strategies to discover optimized mirror maps, confirming that sample efficiency increases dramatically when the learned maps induce sparsity and prune suboptimal actions early in the training process.

By fundamentally altering the geometry of the policy distribution, sparse policy regularization replaces the soft, cautious exploration of softmax with a decisive framework that knows exactly when to say "never."

Key Foundational Work

Least Absolute Policy Iteration-A Robust Approach to Value Function Approximation (2010) — contributed 1 concept elements to this direction.
Sparse Stochastic Finite-State Controllers for POMDPs (2008) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_sparse_policy_regularization_a7216f38,
  title = {sparse policy regularization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sparse-policy-regularization/rdr_a7216f38ee884ab1b8d7f057e659fba7},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_sparse_policy_regularization_a7216f38_v1,
  title = {sparse policy regularization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sparse-policy-regularization/rdr_a7216f38ee884ab1b8d7f057e659fba7/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake