Abstract
We study a new type of K-armed bandit problem where the expected return of one arm may depend on the returns of other arms. We present a new algorithm for this general class of problems and show that under certain circumstances it is possible to achieve finite expected cumulative regret. We also give problem-dependent lower bounds on the cumulative regret showing that at least in special cases the new algorithm is nearly optimal.
Introduction
In the classic Multi-Armed Bandit (MAB) framework, an agent must balance exploration (trying new arms) with exploitation (pulling the best-known arm). Standard theory assumes arms are independent, leading to the well-known result by Lai and Robbins (1985): any consistent strategy must suffer at least logarithmic cumulative regret, $O(\log n)$, as the number of trials $n$ grows.
However, many real-world problems exhibit structure. For instance, in online advertising, the click-through rates of different ad variants are often mathematically related. This paper explores whether such structures can be exploited to break the logarithmic barrier and achieve finite regret—a state where the agent eventually identifies the optimal arm with such high confidence that it stops making sub-optimal choices entirely.
The UCB-S Algorithm
The authors propose UCB-S (Structured Upper Confidence Bound), an algorithm designed to leverage known functional relationships between arms.
The Model
The reward of each arm $i$ is assumed to be a known function $\mu_i(\theta)$ of an underlying, unknown parameter $\theta^*$. Instead of estimating each arm's mean independently, UCB-S maintains a confidence set $\tilde{\Theta}_t$ of possible parameters consistent with all observed data across all arms.
Optimism under Structure
At each step, the algorithm selects the arm $i$ that maximizes the potential reward for any parameter in the current confidence set. This approach allows the agent to "learn for free." Pulling the optimal arm provides information about $\theta^*$, which in turn shrinks the confidence intervals for all other arms, even those not recently pulled.
Achieving Finite Regret
The core theoretical contribution is identifying the conditions under which UCB-S achieves finite regret. Theorem 3 establishes that if the problem structure is "identifiable"—meaning the optimal arm's mean reward uniquely distinguishes it as the best across the parameter space—the algorithm's expected cumulative regret remains bounded by a constant. In these cases, the information gained from the optimal arm is sufficient to eventually "disprove" all sub-optimal arms forever.
The Challenge of Ambiguity
Finite regret is not guaranteed for all structures. The authors identify "Ambiguous Cases" where two different parameters $\theta_1$ and $\theta_2$ might yield the same mean reward for the optimal arm but point to different arms as being optimal. In such scenarios, the agent is forced to continue pulling sub-optimal arms to distinguish between the parameters, reverting to the classic $O(\log n)$ regret.
Conclusion
This work demonstrates that logarithmic regret is not an inescapable law for all bandit problems. By exploiting problem structure, UCB-S can achieve significantly better performance, reaching a steady state of zero additional regret in many practical scenarios. Future work involves addressing the computational complexity of optimizing over high-dimensional parameter spaces and extending these guarantees to continuous action sets.
Summary updated