Technical Summary: Mean-Based Algorithms: A Lower Bound and Regret

Problem Statement

The paper investigates mean-based algorithms within the context of online learning, specifically focusing on the multi-armed bandit (MAB) setting with bandit feedback and an unknown time horizon.

Mean-based algorithms are defined by the principle that an agent should select actions with low past average rewards with low probability in the future. While recent literature suggests these algorithms converge favorably to serially undominated actions (approximating Nash equilibria in economic games), empirical studies indicate they suffer from slow convergence compared to established algorithms in bandit-feedback scenarios. Furthermore, there is a tension between the "exploitability" of these algorithms in principal-agent games and their theoretical convergence guarantees.

The specific challenges addressed are:

1. Defining mean-based algorithms for the unknown-horizon setting (where the total number of rounds $T$ is not known in advance).
2. Determining the theoretical limits on the algorithm's defining rate sequence, $\gamma_t$, which controls the threshold for avoiding "dominated" actions.
3. Clarifying the relationship between mean-based algorithms and no-external-regret algorithms, particularly whether an algorithm can possess both properties simultaneously under bandit feedback.

Methodology

1. Definitions and Preliminaries

The authors formalize two definitions of mean-based algorithms:

• $\gamma_t$-mean-based: Based on current average rewards $\alpha_t(a)$. If $\alpha_t(a') - \alpha_t(a) > \gamma_t$, the probability of picking $a$ at $t+1$ is at most $\gamma_t$.
• Predictive $\gamma_t$-mean-based: Based on the next step's average rewards $\alpha_{t+1}$.

The paper establishes that these definitions are mutually convertible and focuses on the non-predictive variant for the bandit setting.

2. Proposed Algorithms

The authors propose two algorithms adapted for bandit feedback and unknown horizons:

• Generalized $\epsilon$-Greedy: A variant where actions are deemed "dominated" if their estimated cumulative reward is significantly lower than others. The algorithm assigns a small probability $\epsilon_t$ to dominated actions and distributes the remaining probability among non-dominated actions.
• Mean-Based Exp3: A variant of the Exp3 (Exponential-weight algorithm for Exploration and Exploitation) algorithm. It uses multiplicative weights based on estimated cumulative rewards, with an exploration component $\epsilon_t$ to ensure sufficient sampling.

Both algorithms utilize importance-weighted estimators to handle the lack of full feedback.

3. Theoretical Lower Bound Derivation

To determine the fundamental limit of how fast these algorithms can learn, the authors derive a lower bound on the rate sequence $\gamma_t$.

• Adversarial Construction: They construct two specific adversarial environments ($x'_t$ and $x''_t$) that exploit the exploration-exploitation dilemma. In these environments, an algorithm must distinguish between two actions that initially appear similar but diverge later.
• Indistinguishability Argument: Due to bandit feedback, if the algorithm plays a specific action too rarely (to satisfy a small $\gamma_t$), it cannot distinguish between the two environments.
• Inequality Derivation: By analyzing the probability of selecting a dominated action in these constructed environments, they derive a necessary inequality: $\sum_{t=t_1}^{t_c-1} \gamma_t + k \cdot \gamma_{t_c} \geq 1$.
• Asymptotic Analysis: They approximate this sum using integrals to show that any rate sequence decaying faster than $O(1/\sqrt{t})$ (specifically, any sequence where $\gamma_t \in o(1/\sqrt{t})$) violates the condition required for the algorithm to be mean-based in the bandit setting.

4. Regret Analysis

The authors analyze the intersection of mean-based algorithms and no-external-regret algorithms. They demonstrate that while mean-based algorithms do not automatically guarantee no-regret (and can suffer linear regret in specific adversarial setups with very small $\gamma_t$), there exist configurations (specifically certain parameterizations of Exp3) that satisfy both the mean-based property and the no-external-regret property.

Key Contributions

1. First Lower Bound on $\gamma_t$: The paper provides the first formal lower bound for the rate sequence $\gamma_t$ of mean-based algorithms in the bandit-feedback setting. It establishes that $\gamma_t$ cannot decay faster than $O(1/\sqrt{t})$. Specifically, any sequence $\gamma_t \in o(1/\sqrt{t})$ is invalid for mean-based algorithms in this setting.
2. Unknown-Horizon Algorithms: The authors propose two concrete mean-based algorithms (generalized $\epsilon$-greedy and mean-based Exp3) that operate effectively without prior knowledge of the time horizon $T$.
3. Reconciliation of Definitions: The work clarifies the relationship between predictive and non-predictive mean-based definitions, showing their convertibility.
4. Regret-Mean-Based Overlap: The paper proves that the set of mean-based algorithms and the set of no-external-regret algorithms are not disjoint. It constructs a specific Exp3 variant that is both mean-based and no-regret.
5. Empirical Validation: Through numerical experiments, the authors show that while mean-based algorithms may converge slightly slower than standard counterparts, they can achieve competitive performance in both stochastic MAB settings and economic games (Bertrand oligopoly).

Results

Theoretical Results

• Lower Bound: The sequence $\gamma_t = \frac{1}{2\sqrt{t}+1}$ is identified as a critical threshold. Any sequence decaying strictly faster than this (e.g., $\gamma_t = 1/t^{0.51}$ or $\gamma_t = 1/t$) is proven to be invalid for mean-based algorithms under bandit feedback.
• Regret: The paper confirms that mean-based algorithms are not inherently "exploitable" in a way that precludes no-regret guarantees. There exist algorithms that are both mean-based and no-regret.

Empirical Results

• Stochastic MAB: In a 10-arm bandit experiment, the proposed mean-based Exp3 (with $\alpha=1/2$) showed slightly slower convergence to the optimal action compared to a standard Exp3 configuration, but the difference was marginal. The $\epsilon$-greedy variants showed performance dependent on the exploration rate.
• Bertrand Oligopoly: In a repeated pricing game, the mean-based Exp3 algorithm converged to the Nash equilibrium significantly faster than previously observed in similar literature (e.g., Bichler et al., 2025). The mean-based $\epsilon$-greedy algorithms were slower, attributed to excessive exploration when the domination threshold was high.

Significance and Claims

The paper claims to provide a fundamental limit on the performance of mean-based algorithms. The derived lower bound on $\gamma_t$ explains why these algorithms often learn slowly: to satisfy the mean-based condition (avoiding dominated actions) without full feedback, the algorithm must maintain a certain level of exploration. If the exploration rate drops too quickly (i.e., $\gamma_t$ becomes too small), the algorithm cannot distinguish between environments and is forced to play dominated actions, violating the mean-based definition.

The authors position their work as a necessary step in reconciling the "exploitability" concerns of principal-agent games with the convergence guarantees in game theory. By showing that mean-based and no-regret properties can coexist, they suggest that mean-based algorithms are a viable alternative for economic learning scenarios, provided the rate $\gamma_t$ is chosen carefully to respect the derived lower bound.

The paper concludes that while mean-based algorithms are not universally faster than standard no-regret algorithms, they offer a distinct class of learning dynamics that can be competitive, particularly in settings where convergence to serially undominated strategies is the primary goal. The work leaves open the question of whether an algorithm can be constructed that exactly matches the theoretical lower bound $\gamma_t \approx 1/\sqrt{t}$ while maintaining optimal regret.