Abstract
The multi-armed bandit (MAB) problem is a widely studied model in the field of operations research for sequential decision making and reinforcement learning. This paper mainly considers the classical MAB model with heavy-tailed reward distributions. We introduce the extended robust UCB policy, which is an extension of the pioneering UCB policies proposed by Bubeck et al. [5] and Lattimore [21]. The previous UCB policies require the knowledge of an upper bound on specific moments of reward distributions or a particular moment to exist, which can be hard to acquire or guarantee in practical scenarios. Our extended robust UCB generalizes Lattimore's seminary work (for moments of orders $p=4$ and $q=2$) to arbitrarily chosen $p$ and $q$ as long as the two moments have a known controlled relationship, while still achieving the optimal regret growth order $O(\log T)$, thus providing a broadened application area of the UCB policies for the heavy-tailed reward distributions.
Introduction
In the classic Multi-Armed Bandit (MAB) problem, an agent must choose between $K$ different actions ("arms"), each providing a random reward. The goal is to maximize the total reward over time, necessitating a balance between exploration (trying new arms) and exploitation (sticking with the best-known arm).
Most standard algorithms, such as UCB1, assume "light-tailed" rewards (e.g., Gaussian or Bernoulli), where the probability of extreme outliers is negligible. However, in practical fields like finance, web traffic, or insurance, rewards are often heavy-tailed. In these scenarios, a single extreme value can wildly distort the sample mean, causing standard UCB policies to fail. Previous "Robust UCB" methods existed but were limited by strict requirements, such as knowing an exact upper bound on the reward's moments or being restricted to specific cases like the 4th moment. This research addresses these gaps by providing a generalized solution for any distribution where at least some $p$-th moment exists for $p > 1$.
Methods
The authors propose two primary policies to address different reward distribution characteristics:
1. Extended Robust UCB (for Heavy-Tailed Rewards)
- Median-of-Means Estimator: To mitigate the impact of outliers, the algorithm employs a median-of-means estimator. It divides observations into bins, calculates the mean of each bin, and then takes the median of those means, providing a more stable estimate of the true reward than a simple empirical mean.
- Moment Control Relationship: The policy assumes a relationship between two moments ($p$ and $q$, where $p > q > 1$), generalizing the concept of "kurtosis" used in previous literature.
- Dynamic Confidence Bounds: A new Upper Confidence Bound (UCB) formula is derived that incorporates this moment relationship, ensuring balanced exploration and exploitation.
2. UCB1-LT (for Light-Tailed Rewards)
Designed for cases where the moment-generating function exists, this simplified version uses a Bernstein-type bound to create tighter confidence intervals than the original UCB1.
Results and Comparison
The Extended Robust UCB achieves an optimal regret growth of $O(\log T)$, matching the theoretical best possible rate for this class of problems. In head-to-head comparisons with Lattimore’s scale-free algorithm, the proposed policy provides a tighter regret upper bound, leading to faster convergence to the optimal strategy.
The table above illustrates how the proposed method ("Ours") generalizes the assumptions of previous works. While earlier methods like Bubeck et al. [5] or Lattimore [22] required specific moment knowledge or fixed moment orders, the Extended Robust UCB allows for a broader range of $p$ and $q$ values, provided a controlled relationship exists.
Monte Carlo simulations across Laplace, Student-t, and Pareto distributions confirmed that as the time horizon $T$ grows, the cumulative regret follows the predicted logarithmic curve. Notably, the algorithm is particularly effective in "low-discrimination" cases where the difference between the best and second-best arm is minimal.
Conclusion
This work advances the robustness of UCB policies by generalizing the moment requirements for heavy-tailed reward distributions. While the algorithm currently requires specifying the existence of a $p$-th moment and exhibits gap-dependency in its regret bounds, it provides a more flexible framework for real-world decision-making. Future work aims to remove gap dependency to create "gap-free" bounds and optimize the computational complexity associated with the median-of-means estimator.
Summary updated