The EL-F Algorithm: A Reliable Scale-Free Bandit Approach

Background: When Bandit Algorithms No Longer Depend on Reward Scale

In multi-armed bandit problems, a long-standing engineering pain point is the reliance on prior knowledge of reward scale and tail parameters. In practice, the magnitude of reward distributions is often unknown and may even change over time, making many theoretically elegant algorithms unstable when deployed. The g-Forcing strategy proposed by Cowan and Katehakis provided almost-sure regret guarantees, but such guarantees only describe "what will eventually be learned"—they cannot answer questions about expected performance and extreme risk within a finite number of rounds.

A recent research paper proposes the EL-F algorithm, which extends g-Forcing through Empirical Likelihood, attempting to provide finite-time expected regret upper bounds and tail risk characterization while maintaining asymptotic optimality.

Multi-Armed Bandits and Regret: The multi-armed bandit (MAB) is a classic model for sequential decision-making. In each round, the algorithm selects one of K arms to pull and receives a random reward; the goal is to maximize cumulative reward over T rounds, which is equivalent to minimizing regret—the difference between the expected reward actually obtained and the expected reward that would have been obtained by always pulling the optimal arm. Regret captures the cost paid for exploration. Pseudo-regret is a common surrogate for regret, typically defined as the sum of the suboptimality gap of each arm multiplied by its number of pulls, which facilitates theoretical analysis.

Per-arm Suboptimality Gap: The suboptimality gap of arm i is defined as the difference between the expected reward of the optimal arm and that of arm i, i.e., Δ_i=μ*-μ_i. When Δ_i is small, more samples are needed to distinguish that arm from the optimal one, so instances with small gaps are typically harder. Cumulative regret can be written as ∑Δ_i·N_i(T), where N_i(T) is the number of times arm i is pulled over T rounds—this is precisely the quantification of "wasting rounds on suboptimal arms."

g-Forcing Strategy: g-Forcing was proposed by Cowan and Katehakis. Its core idea is to set a non-decreasing, divergent exploration schedule g(t) with increments tending to zero, forcing each arm's number of samples before round t to be no less than some lower bound determined by g, while greedily pulling the arm with the highest current empirical mean in the remaining rounds. Since the sampling lower bound depends only on the round t and not on the magnitude or tail parameters of rewards, this strategy is naturally scale-free. Its theoretical guarantee is that pseudo-regret satisfies R(T)=O(g(T)) and R(T)/g(T) converges almost surely to ∑Δ_i, but this is an asymptotic statement and does not address expected performance and extreme risk under finite T.

Three-Layer Performance Guarantees: From Asymptotic to Finite-Time

The core contribution of EL-F lies in decomposing the performance characterization into three layers.

Asymptotic Optimality Is Preserved

For integrable reward distributions and a non-decreasing, divergent exploration schedule g with increments tending to zero, EL-F preserves the asymptotic pseudo-regret property of g-Forcing: as T tends to infinity, R(T)/g(T) converges almost surely to the sum of suboptimality gaps of all suboptimal arms. This means that introducing empirical likelihood does not sacrifice long-term asymptotic efficiency.

Finite-Time Expected Regret Upper Bound

On every sub-exponential instance, for g(t)=ω(log t) satisfying mild feasibility conditions, the expected pseudo-regret is bounded by g(T)∑Δ_i + C_P, where C_P is an instance-dependent constant independent of time T. The value of this result is that it turns "will eventually converge" into "there is a clear ceiling on expected regret within any finite number of rounds," which is more instructive for practical deployment.

Tail Risk and Matching Lower Bound

The paper further provides a super-polynomial decay tail bound for regret beyond the forced exploration budget. For slowly varying g, the authors precisely characterize the exponent of the linear regret deviation on two-armed Gaussian instances and establish a matching lower bound for the strategy class under the same per-instance expected regret budget constraint. This matching of upper and lower bounds means that this characterization cannot be significantly improved in theory.

Sub-exponential Distributions and Super-polynomial Decay: A sub-exponential distribution is a family broader than sub-Gaussian, with tail decay slower than Gaussian but faster than heavy-tailed power laws. Typical examples include the exponential distribution, the chi-squared distribution, and some bounded but asymmetric distributions. A random variable X is said to have sub-exponential tails if there exists a parameter such that its moment generating function is finite near the origin. In bandit analysis, the MGF method is often used to derive concentration inequalities for regret. Super-polynomial decay means that the tail probability decays faster than any polynomial—that is, for any constant k, the tail probability multiplied by T^k still tends to zero. This is stronger than the common polynomial decay and implies that extremely bad regret events are almost impossible, which is especially critical for risk-sensitive practical deployments.

Greedy Variant and Local Optimism

EL-F degenerates to a greedy variant when the empirical likelihood radius is zero, and the paper's quantitative guarantees also cover this special case. When the radius takes a fixed positive value, the algorithm introduces local optimism, which, while preserving the dominant asymptotic regret, brings two provable advantages:

• In two-armed bandits with a deterministically suboptimal arm, a coupled pathwise dominance relationship with the greedy variant is established;
• Experiments show that on hard instances, compared with the original g-Forcing, EL-F significantly reduces the duration of long-term suboptimal allocation.

The latter point is especially important from an engineering perspective—many failed bandit deployments do not fail to converge to the optimal arm, but rather waste too many rounds on clearly inferior arms before convergence.

Local Optimism: Optimism is a classic principle in bandit algorithms—when facing uncertainty, choose the arm with the highest confidence upper bound, allowing the algorithm to automatically balance exploration and exploitation. The UCB family is the representative of global optimism. Local optimism means that optimistic judgments take effect only within a local range defined by the forced exploration schedule; for example, in EL-F, a bounded upward adjustment of the empirical mean is made only when the empirical likelihood radius is positive. Compared with global optimism, local optimism does not require constructing confidence sets over the entire reward space, thereby avoiding explicit estimation of reward scale, variance, or tail parameters while retaining the effect of reducing sampling time on suboptimal arms. The size of the empirical likelihood radius directly controls the strength of optimism: a radius of zero degenerates to pure greediness.

Comparative Analysis with Existing Methods

The strategic logic of g-Forcing is to use a non-decreasing exploration schedule g(t) to force a lower bound on the number of times each arm is sampled, thereby bypassing the need to estimate reward scale. EL-F adds the degree of freedom of the empirical likelihood radius on this basis, which is equivalent to embedding data-driven confidence judgments within the framework of forced exploration.

Methodologically, this path differs from the UCB family. UCB requires constructing confidence upper bounds, and the width of these bounds typically depends on the variance or tail parameters of the reward distribution; EL-F avoids explicit dependence on these parameters through empirical likelihood while retaining the scale-free property through the scheduling structure of g-Forcing. The paper's theoretical results show that this combination incurs no additional cost asymptotically.

In the experimental section, the authors demonstrate the reduction of EL-F relative to g-Forcing in long-term suboptimal allocation on challenging instances, validating the practical value of the local optimism brought by a fixed positive radius.

Applicable Scenarios and Open Problems

The applicable scenarios for EL-F mainly fall in real systems where the reward scale is unknown, the distribution may have sub-exponential tails, and the number of operating rounds is finite, such as online advertising bidding, cold-start exploration in recommendation systems, and traffic allocation in A/B testing. A common feature of these scenarios is that they are more sensitive to "how much traffic will be wasted in the worst case" than to "whether the optimal solution will eventually be found."

Open directions left by the paper include: precise characterization of the linear regret deviation exponent under a larger number of arms, matching lower bounds under non-Gaussian distributions, and adaptive selection of the g schedule under practical constraints such as delayed feedback. From an engineering perspective, guidance on the optimal choice of the fixed positive radius is still lacking, and this may be the most worthwhile gap for follow-up work to fill.