Best of both worlds: Stochastic & adversarial best-arm identification

The gist The learner designs an algorithm that performs optimally in both stochastic and adversarial best-arm identification problems without knowing the nature of the rewards, though this is shown to be impossible in general.

Motivation

The study investigates best-arm identification under arbitrary and potentially adversarial rewards, where a simple random uniform learner obtains the optimal rate of error in the adversarial scenario but is suboptimal when rewards are sampled stochastically. The core question addressed is whether a learner can perform optimally in both settings without awareness of the reward nature. Learning in the presence of adversarial data implies robustness, as real-world scenarios may involve correlations or adversaries trying to obscure results. An efficient learner needs to employ internal randomization and pull each arm with a positive probability pk,t.

Problem Formulation

The general game protocol involves the learner choosing an arm It and the adversary picking a gain vector gt simultaneously at each round t, while the learner only observes gIt,t. In the adversarial case, the performance is measured by eADV(g)(n), the probability of not identifying the best arm given a fixed adversarial reward design g. In the stochastic case, where rewards are sampled i.i.d. from distributions νk, the error is eSTO(n), defined as P(Jn!= k⋆STO). The gaps in hindsight are defined to characterize the difficulty of discriminating between arms, such as ∆g k = 1/n Σ t (g k,t - g j,t).

Lower Bounds and Complexity

The paper establishes lower bounds that characterize the optimal rates of error in both settings. For the adversarial problem, Theorem 2 provides a lower bound showing that for any class problem ∆3 with associated complexity HUNIF, there exist g 1 and g 2 such that max e g(n) ≥ min 1/128 exp-32n HUNIF. Similarly, the lower bound for the best of both worlds challenge is given by Theorem 4, which shows that for any class problem ∆4 with complexity HBOB, there exists a stochastic problem STO such that if eSTO(n) ≤ 1/64 exp-2048n HBOB then there exists an adversarial problem g such that eADV(g)(n) ≥ 1/16. The complexity measures HSR, HUNIF, and HBOB are introduced to group problems with similar gap structures and complexities.

The ProbabilityONE Algorithm

A new simple parameter-free learner called ProbabilityONE (P1) is designed to bridge the gap between the two worlds. P1 selects arm It with probability pk,t ≜ 1/⟨fk⟩ t logK for all k ∈ [K], where ⟨fk⟩ t is the rank of arm k after sorting by cumulative gain Gek,t-1. This approach is inspired by Successive Rejects (SR) but differs by not dividing the game into fixed sampling phases. The complexity associated with P1 is defined as HP1, which matches the complexity HBOB up to log factors, i.e., HP1 = O(HBOB log2 K).

Performance Guarantees

Theorem 6 provides upper bounds for P1 in both environments simultaneously. For the stochastic case, eSTO(n) ≤ 2K 3n exp-n 128HP1 and for the adversarial case, eADV(g)(n) ≤ K exp-3n 40log(K)HUNIF(g). Corollary 7 demonstrates that P1 achieves the best that can be wished for in both worlds, up to log factors, by showing HP1 = O(HBOB log2 K).

Conclusion

The paper concludes that while a learner unaware of the reward process cannot guarantee optimal error rates simultaneously in both settings, the P1 algorithm achieves the best possible performance, matching the lower bounds up to log factors. The simplicity and adaptability of P1 make it a versatile tool for stochastic and adversarial best-arm identification.

How it works

The ProbabilityONE (P1) algorithm operates by sorting arms based on their estimated cumulative gains Gek,t-1 to determine the probability pk,t for selecting arm k at round t. This selection probability is inversely proportional to the rank of the arm, specifically pk,t ≜ 1/⟨fk⟩ t logK. The algorithm then recommends Jn as the arm with the highest estimated cumulative gain Gek,n.

Key Findings and Results

1. The learner can guarantee that its probability of error eSTO(n) ≤ 2K 3n exp-n 128HP1 in the stochastic setting.

2. The learner can guarantee that its probability of error eADV(g)(n) ≤ K exp-3n 40log(K)HUNIF(g) in the adversarial setting.

3. The complexity of P1, HP1, matches the complexity HBOB from the lower bound of Theorem 4 up to log factors, i.e., HP1 = O(HBOB log2 K).

4. The algorithm's performance is shown to be robust and adaptive, allowing it to handle different gap regimes in stochastic problems.

Implications for the Field

The existence of P1 suggests that a learner can achieve the best that can be wished for in both worlds, up to log factors. The analysis shows that by carefully choosing comparison rounds, the learner can minimize the final probability of error. This provides a practical, parameter-free algorithm for complex identification tasks.

Future Directions

The research suggests extensions such as using Freedman Races based on P1 to design fixed-confidence learners or adapting P1 for active anomaly detection in adversarial settings. This indicates potential applications in areas like online hyperparameter optimization and robust anomaly detection.

Summary of Key Concepts

The paper introduces three complexity measures: HSR, HUNIF, and HBOB, which relate to the stochastic (HSR), adversarial/stochastic (HUNIF), and best-of-both-worlds (HBOB) settings. The ProbabilityONE learner is shown to achieve a complexity HP1 that is bounded by HBOB log2 K. This demonstrates that P1 achieves the best that can be wished for in the two worlds, up to log factors. The analysis covers various gap regimes, including flat and square-root gaps.

Relation between Complexities

The paper proves that in general, HP1 = O(HBOB log2 K). This demonstrates that P1 achieves the best that can be wished for in the two worlds, up to log factors. The extra log K from the log2 K is not always present and is discussed in Remark 5. The relationship between HP1, HSR, and HBOB for different gap regimes is detailed in Appendix G.

1. Improved learner for both stochastic and adversarial rewards: The ProbabilityONE (P1) algorithm can be implemented to select an arm with probability proportional to its estimated rank, specifically selecting arm 1 with probability 1/logK, which does not prevent from pulling all the arms almost uniformly and more precisely with probability at least 1/(KlogK).

2. Robust performance guarantee: The P1 learner can achieve simultaneous upper bounds on misidentification error for both environments: eSTO(n) ≤ 2K3n exp − n 128HP1 and eADV(g)(n) ≤ K exp − 3n 40log(K)HUNIF(g).

3. Adaptive complexity measure: The learner can utilize the new complexity measure HP1, defined as min a∈A HP1(a), which is designed to minimize the worst-case error across different comparison round proportions, effectively characterizing the best that can be wished for in the two worlds, up to log factors.

4. Fixed-confidence stopping rule: A Freedman Race based on P1 can be designed where the learner stops when confidence intervals separate: it would stop when the confidence interval for the empirically best arm is separated from the confidence intervals for all the other arms. This allows for a guarantee of stopping with complexity of Oe (HBOB log(1/δ)), up to log factors in stochastic settings.

5. Anomaly detection capability: P1 can be adapted into a robust anomaly detector that monitors streams of rewards and can potentially detect an anomaly if one of the streams outputs a reward signal that is on average larger than a given threshold during a time window period W.