Tsallis Entropy and Hybrid Regularization for Online Bandits

107 concepts72 papers1 proposal

In online learning frameworks like Follow-the-Regularized-Leader (FTRL) and Online Mirror Descent (OMD), the choice of regularizer dictates how an agent balances exploration and exploitation. For decades, negative Shannon entropy was the default choice, giving rise to the ubiquitous Exponential Weights algorithm. While Shannon entropy works exceptionally well in full-information settings, it can struggle in partial-information (bandit) environments. It often requires delicate manual tuning and fails to adapt seamlessly when the environment shifts between predictable (stochastic) and unpredictable (adversarial) regimes.

To overcome these limitations, a powerful paradigm has emerged: replacing or augmenting Shannon entropy with generalized entropy functions—most notably Tsallis entropy—and hybrid regularizers. By altering the mathematical curvature of the action space, these regularizers provide the precise variance control and stability needed to handle complex feedback structures and achieve "Best-of-Both-Worlds" performance.

The Geometry of Curvature: Why Shannon Entropy Falls Short

To understand why generalized regularizers work, we must look at the geometry they impose on the probability simplex. A regularizer acts as a penalty function that keeps the agent's policy from shifting too radically in response to noisy, immediate feedback.

Shannon entropy ($\sum p_i \log p_i$) has a gradient that blows up to infinity near the boundaries of the simplex (where the probability of choosing an arm $p_i \to 0$). This aggressive boundary gradient forces the agent to always maintain a baseline level of exploration across all actions.

However, in bandit settings, the variance of importance-weighted reward estimators scales inversely with $p_i$. Shannon entropy's curvature is not always aggressive enough to counteract this variance near the boundaries. As noted by Masahiro Kato and Shinji Ito in Best-of-Both-Worlds Linear Contextual Bandits, this mismatch often introduces higher-order logarithmic overheads in stable environments, preventing algorithms from achieving truly optimal regret.

The Power of Tsallis Entropy

Tsallis entropy introduces a parameter $\alpha$ (typically $\alpha \in [0, 1]$) that alters the scaling of the regularizer. Instead of the $\log p_i$ term found in Shannon entropy, $\alpha$-Tsallis entropy relies on power-law scaling:

$$\frac{1}{1-\alpha} \sum_{i} (p_i - p_i^\alpha)$$

When $\alpha = 1/2$, this function yields a particularly powerful regularizer known as $1/2$-Tsallis entropy. Jacob Abernethy et al. demonstrated in Fighting Bandits with a New Kind of Smoothness that utilizing Tsallis entropy within a generalized algorithmic template achieves state-of-the-art minimax regret bounds for adversarial multi-armed bandits.

The core reason for this success lies in variance control. As Shinji Ito explains in On the Minimax Regret for Contextual Linear Bandits and Multi-Armed Bandits with Expert Advice, $\alpha$-Tsallis entropy provides superior variance control for reward estimators compared to traditional Shannon entropy. The heavier regularization near the boundaries stabilizes the learning process against noisy or sparse feedback by precisely flattening the optimization objective's curvature where information is poorest.

Achieving the Best of Both Worlds

One of the most celebrated properties of Tsallis entropy is its ability to achieve "Best-of-Both-Worlds" (BoBW) guarantees. An ideal online learner should achieve fast, logarithmic regret ($\mathcal{O}(\log T)$) if the environment happens to be stable and stochastic, but remain robust with square-root regret ($\mathcal{O}(\sqrt{T})$) if the environment is adversarial or corrupted.

Christoph Dann et al. in Best of Both Worlds Policy Optimization showed that Tsallis entropy regularizers facilitate a natural, automatic transition between exploration-heavy adversarial strategies and exploitation-focused stochastic strategies. Because the curvature adapts dynamically to performance gaps without manual tuning, the agent can exploit stable reward structures while maintaining a safety net against adversarial manipulation.

To scale this benefit to more complex action spaces, Masahiro Kato and Shinji Ito developed LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits. They proved that Tsallis entropy provides the exact mathematical curvature necessary to secure optimal regret in linear contextual settings, bypassing the massive computational overhead typically associated with traditional "black-box" reduction techniques.

Hybrid Regularizers: Combining Potentials for Complex Feedback

Real-world online learning frequently introduces structural complications, such as delayed feedback, partial monitoring, or graph-structured observation spaces. In these scenarios, a single regularizer is rarely sufficient to address every constraint simultaneously. Instead, researchers construct hybrid regularizers that combine multiple potential functions to handle distinct mathematical challenges.

Tsallis + Shannon for Delayed Feedback

When feedback is delayed, an agent must avoid making massive, erratic updates based on stale or missing information. Julian Zimmert and Yevgeny Seldin tackled this in An Optimal Algorithm for Adversarial Bandits with Arbitrary Delays by introducing a hybrid regularizer that combines $1/2$-Tsallis entropy with negative Shannon entropy.

This hybrid approach treats the exploration-exploitation tradeoff and delay-induced uncertainty as separate mathematical challenges. The Tsallis component ensures minimax optimal exploration, while the Shannon component stabilizes the policy against temporal delays. Saeed Masoudian et al. expanded this concept in A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays, demonstrating that this dual-entropy structure allows an algorithm to adaptively switch between stochastic and adversarial regimes even when feedback arrives with severe, unpredictable delays.

Shannon + Log-Barrier for Heterogeneous Information

In graph feedback or partial monitoring settings, different actions yield vastly different amounts of information (e.g., revealing the losses of neighboring actions). To maintain stability across heterogeneous feedback structures, Chung-Wei Lee et al. in A Closer Look at Small-loss Bounds for Bandits with Graph Feedback augmented Shannon entropy with log-barrier regularizers ($-\sum \log p_i$).

The log-barrier acts as a strict numerical buffer that prevents the learner from approaching the boundaries of the action set too closely, effectively canceling out large importance-weighted variance terms. As shown by Shinji Ito et al. in Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoring, combining log-barrier and complement Shannon entropy regularizers offers a superior self-bounding property, enabling optimal logarithmic regret in stable environments without sacrificing worst-case robustness.

Beyond Bandits: Games and Reinforcement Learning

The structural benefits of generalized entropy extend naturally into multi-agent systems and continuous control.

In game theory, Shinji Ito et al. demonstrated in Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback that a $1/2$-Tsallis entropy regularizer enables agents to achieve optimal instance-dependent performance in zero-sum games, smoothing the transition between exploration and exploitation as the opponent's strategy evolves.

In Inverse Reinforcement Learning (IRL), where an agent attempts to recover an underlying reward function from expert demonstrations, standard Shannon entropy regularizers can be overly permissive. Wonseok Jeon et al. showed in Regularized Inverse Reinforcement Learning that utilizing Tsallis entropy regularizers allows practitioners to strictly adjust the sensitivity of the imitation process. By tuning the regularizer, the agent can be forced to match higher-order characteristics of the expert's distribution (such as variance) far more strictly than Shannon entropy allows, leading to more robust and transferable reward recovery.

Key Foundational Work

Fighting Bandits with a New Kind of Smoothness (2015) — contributed 2 concept elements to this direction.
Fighting Bandits with a New Kind of Smoothness (2015) — contributed 2 concept elements to this direction.
Fighting Bandits with a New Kind of Smoothness (2015) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 79 papers
  2. Version 1 · 2026-10-04 · 49 papers
Cite this direction

Latest version (a living page):

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

This exact version (version 2, frozen text):

@misc{lacuna_tsallis_entropy_regularization_79687c7a_v2,
  title = {Tsallis entropy regularization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tsallis-entropy-regularization/rdr_79687c7aeaed49ff89bf42573e3ac185/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake