Uniform Last-Iterate Guarantee for Bandits and Reinforcement Learning
Authors: Junyan Liu
Yunfan Li
Ruosong Wang
Lin Yang
Venue: NeurIPS 2024 poster (2024)
Keywords: uniform last-iterate
bandits
reinforcement learning
Primary area: reinforcement_learning
TL;DR: We propose a new metric, called uniform last-iterate and show it is achievable for multi-armed bandits and linear bandits, and tabular Markov decision processes

Abstract: Existing metrics for reinforcement learning (RL) such as regret, PAC bounds, or uniform-PAC (Dann et al., 2017), typically evaluate the cumulative performance, while allowing the play of an arbitrarily bad policy at any finite time t. Such a behavior can be highly detrimental in high-stakes applications. This paper introduces a stronger metric, uniform last-iterate (ULI) guarantee, capturing both cumulative and instantaneous performance of RL algorithms. Specifically, ULI characterizes the instantaneous performance since it ensures that the per-round suboptimality of the played policy is bounded by a function, monotonically decreasing w.r.t. (large) round t, preventing revisits to bad policies when sufficient samples are available. We demonstrate that a near-optimal ULI guarantee directly implies near-optimal cumulative performance across aforementioned metrics, but not the other way around. 
To examine the achievability of ULI, we first provide two positive results for bandit problems with finite arms, showing that some elimination-based algorithms and high-probability adversarial algorithms with stronger analysis or additional designs, can attain near-optimal ULI guarantees. We also provide a negative result, indicating that optimistic algorithms cannot achieve a near-optimal ULI guarantee. Furthermore, we propose an efficient algorithm for linear bandits with infinitely many arms, which achieves the ULI guarantee, given access to an optimization oracle. Finally, we propose an algorithm that achieves a near-optimal ULI guarantee for the online reinforcement learning setting.

Uniform Last-Iterate Guarantee for Bandits and Reinforcement Learning
Junyan Liu
Yunfan Li
University of Washington
University of California, Los Angeles yunf ang ucla. edu
j junyanl 10cs. washington. edu
Ruosong Wang" CFCS and School of Computer Science Peking University
Lin E. Yang* University of California, Los Angeles linyang@ee ucla. edu
ruosongwang@pku.co edu.
Abstract
Existing metrics for reinforcement learning (RI.) such regret, PAC bounds, uniform-PAC [Dann et al., 2017], typically evaluate the cumulative performance, while allowing the agent play an arbitrarily bad policy at any finite time Such a behavior can be highly detrimental in high-stakes applications. This paper in- troduces a stronger metric, uniform last-iterate (ULI) guarantee, capturing both cumulative and instantaneous performance of RL algorithms. Specifically, ULI characterizes the instantaneous performance by ensuring that the per-round subopti- mality of the played policy is bounded by function, monotonically decreasing w.r.t. round preventing revisiting bad policies when sufficient samples are available. We demonstrate that near-optimal ULI guarantee directly implies near-optimal cumulative performance across aforementioned metries, but not the other way around. To examine the achievability of ULI, we first provide two positive results for bandit problems with finite arms, showing that elimination- based algorithms and high-probability adversarial algorithms with stronger analysis additional designs, can attain near-optimal ULI guarantees. We also provide negative result, indicating that optimistic algorithms cannot achieve near-optimal ULI guarantee. Furthermore, we propose an efficient algorithm for linear bandits with infinitely many arms, which achieves the ULII guarantee, given access to optimization oracle. Finally, we propose an algorithm that achieves near-optimal UL.I guarantee for the online reinforcement learning setting.
Introduction
In online decision-making problems with bandit feedback, learner sequentially interacts with an unknown environment: in each round, the learner plays an policy and then observes the corresponding rewards of the played policy. Typically, the goal of the learner is achieve good cumulative performance, commonly measured by regret or probably approximately correct (PAC) bound. For instance, the online advertisement scenario, the goal of the website (learner) could be maximizing the cumulative click numbers [Li et al., 2010]. Hence, the website aims to minimize the regret that measures the cumulative clicks of the recommended advertisement compared to that of the unknown optimal advertisement. In addition to regret minimization, the goal could also be quickly identifying popular advertisements [Chen et al., 2014, Jin al., 2019]. To this end, PAC bound
"Corresponding authors
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

is suitable here to measure the sample complexity (i.e.. cumulative time steps) that the algorithm needs to identify those popular advertisements. To reap the benefits of both measures, Dann al. [2017] propose new performance measure called uniform-PAC, ensuring that for all e >> 0. the total number of e-suboptimal policies played by the algorithm is bounded by function polynomial 1/c. The uniform-PAC bound can simultaneously imply a high-probability sublinear regret bound and polynomial sample complexity for any desired accuracy.
Although uniform-PAC provides a powerful framework to unify regret and PAC bound, it still fails to capture the instantaneous performance of the learning algorithm. In particular, a uniform- PAC algorithm could play bad policy in some late but fimite round t, even if it enjoys good cumulative performance. This drawback impedes the application of uniform-PAC algorithms into high-stakes fields. Clinical trials, for example, place high demands on instantaneous performance for every treatment test, since patients need to be assigned with increasingly better treatments when more experimental data are available [Villar et al., 2015]. Hence, two natural questions arise:
1. Can we find a new metric that characterizes not only the cumulative performance but also the instantaneous performance?
2. If such a metric exists, optimally achievable by some algorithm?
In this paper, answer both questions affirmatively. Our main contributions are summarized as follows.
We introduce a new metric called uniform last-iterate (ULI), which simultancously characterizes cumulative and instantaneous performance of sequential decision-making algorithms. On one hand, ULI can characterize the instantaneous performance: the per-round suboptimality of any algorithm with ULI guarantee is upper bounded by a function, monotonically decreasing for late time t. On the other hand, we show that any algorithm with (near-optimal) ULI guarantee is also (near- ontaallptimally) uniform-PAS PACC, demonstrating that ULI can imply cumulative performance.
To answer the question whether ULI is achievable, we examine three common types of bandit algorithms in the finite arm setting. First, we provide a stronger analysis to show that many existing elimination--an -based algorithms indeed enjoy near-optimal ULI guarantee. Then, we propose meta- algorithm that enables any nigh-probabilitg adversarial bandit algorithms, with mild condition, to achieve near-optimal ULI guarantee, and we show that such condition naturally holds for many adversarial bandit algorithms. Finally, we provide a hardness result showing that optimistic algorithms (e.g., liIUCB [Jamieson et al., 2014]) cannot achieve near-optimal ULI guarantee. As UCC is near-optimally uniform-PAL -PAC, our hardness result also implics that ULI is strictly stronger than uniform-PAC.
For linear bandits with infinitely-many arms, we propose oracle-efficient linear bandit algorithm with the ULI guarantee (with access to an optimization oracle). In particular, we propose an adaptive barycentric spanner technique, selecting finitely many base arms that can linearly represent all (possibly infinitely many)
arms. This technique generalizes the one in [Awerbuch and Kleinberg, 2008] for climination-bass algorithms by adaptively identifying spaces that active arms span. Leveraging the phased elimination algorithm [Lattimore et al., 2020], our algorithm can conduct the elimination over all arms by only playing a finite subset of arms and querying a linearly-constraimg optimization oracle for only polynomial number of times.
Finally, we propose new algorithm for tabular episodic Markov decision processes (MDPs), which achieves a near-optimal ULI guarantee. In particular, our algorithm adapts uncertainty- driven reward functions to encourage exploration of the transition model, which ensures accurate estimations of value functions across all policies. The final ULI guarantee is achieved by conducting policy elimination.
Related work. In online decision decision-making making problems, regret and PAC bounds are widely adopted to evaluate the cumulative performance of algorithms. More concretely, one line of research [Auer et al., 2002a,b, Abbusi- Yadkori et al., 2011, Li et al., 2010, Jin et al., 2018] aims to minimize the regret which measures the difference between the cumulative rewards of the selected policies and that of the
Throughout the paper, focus high probability regret, and therefore, when we mention regret, it always refer to high-proo probbbbrbbbbbtttttoo regret. refer readers Remark 2.8 for discussion on expected regret. A linear bandit algorithm is oracle-efficient if it calls an optimization oracle per- round for at most polynomial number of times.

---

best policy in hindsight. The PAC guarantees are more common than the regret when studying the pure-exploration/best policy identification problems (Even-Dar et al., 2006, Kalyanakrishnan et al., 2012, Wagenmaker et al., 2022]. One of the popular PAC measures is (6, c)PAC which suggests that with probability least 6, the algorithm can output near-optimal policy most 6 away from the optimal one by using sample complexity polynomial in 1/c.. Later, Dann et al. [2017] 7] introduce a new framework called uniform-PAC to unify both metrics and develop a uniform-PAA algorithm for episodic Markov decision processes (MDPs). Subsequent works design uniform-PAC. algorithms for MDPs with linear function approximation [He et al., 2021] I] and bounded Eluder dimension [Wu et al., 2023]. Though uniform- -AC strengthens regret and (6, c)-PAC bound, it still fails to characterize the instantaneous performance of online algorithms,, i.e., a uniform-PAr PAC algorithm, even with a good cumulative performance, can play bad policies for some late rounds.
seemingly related performance measure is last-iterate convergence (LIC) which has been studied for optimizing MDPs [Moskovitz et al., 2023, Ding et al., 2023] and they use the primal-dual approach to formulate the problem of identifying an optimal policy in the constrained MDPs from a game- theoretic perspective. These works often require additional knowledge of the value functions and the LIC does not characterize the unknown dynamics of the environment. However, in our problem, the dynamics need to be learned as the algorithm sequentially interacts with the environment.
2 Preliminaries
2.1 Framework
We consider a general online sequential decision-making framework where learner interacts with an environment with fixed decision set. At each round E N, the learner makes decision from the set and observes the corresponding reward(s). In what follows, we instantiate this framework to multi-armed bandits, linear bandits, and tabular episodic Markov decision processes (MDPs).
Multi-armed bandits. In the stochastic MAB setting, the arm (decision) set follows that A= = [K] A (1...., K). Each arm a E [K] associated with a fixed and unknown [0, 1] 1J-bounded distribution such that Vt, reward Xt,a is i..dd sample from this distribution with mean μ4a = [[X,, Let A, be the arm played at round t and A. = μ² no be the suboptimality gap where μ²" = max Ma-
Linear bandits. In the stochastic linear bandits setup, we assume that the arm set C RRd is compact. The reward of played arm A, round follows that Xt.A, = (0, Ad) + 1)t where 0 E IR is fixed but unknown parameter, and 7/: is conditionally I-subgaussian. Let A. = supbe (0, - a). We follow standard assumptions that ||0]|2 I 1, ||a|]| S 1 for all a E A. and A. < 1 for all
A.
Tabular episodic MDPs. A tabular episodic MDP formalized as M = (S, H, r, P. (1) where S. A are finite state and action spaces with S = S, |A|| = A, H is the horizon length, r = {rx } where TĄ : S A [0, 1] is a known reward function, {Px (Prhne) where PA S A ((S) is transition function, and μ is the initial state distribution. At the beginning of each episode the learner executes a policy π. (TEA. S + ((A)) H - Then, starting from the initial state st,1 ~ p. for each stage h E [H]. the learner repeatedly takes an action at (t,,((1..)) observes reward rn (8t,n (,,)), and transits to the next state 8,11 ~ Pa(-Ist,n: (r,))-
For any policy and stage h, we define action value function Q7 (s, a) and value function V77 as
H Th aNd =, = a, (T) = E
H Th (sw aw) | sh s,
Q7 a) = E
Lh=h
The optimal action value function and value function at each stage h are denoted by Vi( max, V7. (8), and Q (s, a) max, Q7 (s, a) respectively. Let A, = (V Vi
Suboptimality notations. For MAB and linear bandits settings, the instantaneous suboptimality is
A = A,,, and for episodic MDP, A, = As,- We use A = inf Ar to denote the minimum suboptimality gap. Notice that is possible that A 0 when, for example, arm set a ball.
'Note that all MAB and linear stochastic bandit algorithms in this paper also work for H- Husubaaussian noise with minor adjustments. Only adversarial bandits algorithms in Section 3.1 require the boundedness assumption.
3

---

2.2 Limitations of Existing Metrics
Regret and (6, c)PACC are widely adopted to measure the performance. The regret defined as:
Definition 2.1 (Regret), For each fixed T E N, the regret Rr is defined as Ro = -i= A..
Let N₂ = Σi= T(A, > e) be the number of plays policies whose suboptimality gap greater than e. The definition of (ò, PAC is given as:
Definition 2.2 ((ō, e)-PAC), For any fixed ò, E (0, 1), an algorithm is e)-P) (w.r.t. function FFA) if there exists a function FPAC (ő, e) polynomial in log(6 and e such that
P (N I FPAC (6,e)) e)) 2
As shown by Dann et al. [2017], both regret and (ó, c)-PAC have limitations. Specifically, an algorithm with sublinear regret bound may play suboptimal policies infinitely often. For the algorithm with e guarantee, it may not converge to the optimal policy when feeding the algorithm with more samples. Therefore, such algorithm would play those policies with suboptimality gap, e.g.. e/2 infinitely often, Motivated by these limitations, Dann et al. [2017] introduce uniform miforr--PAC&a as follows.
Definition 2.3 (Uniform-PACE An algorithm is uniform-PAC PAC for some fixed å E (0, 1) if there exists function FUPAC (6, e) polynomial in log(1/5) and e e-,, such that
P (Ve 0: N. S FUPAC (8, <)) 2
We also call (U <) the sample complexity function. Uniform-Pal -PC a stronger metric than regret and (6, PPPPAC since it leads to the following implications.
Theorem 2.4 (Theorem in [Dann et al., 2017]). If an algorithm is uniform-PAC. for some with function FUPAc(ó, e) Ô (a1/E+ a2)=2s,, where 0n, 0r > 0 are constant in and depend on (og(1 and for MAB, d for linear bandits, and S, A, H for MDPs then, the algorithm guarantees:
P (lime A, 0) 2 1 6;
(6. c) with ( c) Furac(5, c) for all 0: With probability at least 8, for all T N, Ri Ô (VarT + az)
Limitations of Uniform-PAC. According to Theorem 2.4, uniform-PAC PAC can imply a long-term convergence (the first bullet) and good cumulative performance (the second and the third bullets), but does not capture the convergence rate of A, for each round t. In other words, even an algorithm enjoys uniform-PAS it could still play significantly bad policy for some very large but finite t. This would lead to catastrophic consequences in safety- critical applications.
2.3 New Metric: Uniform Last-Iterate Guarantee
To address the aforementioned issue, we introduce a new metric, formally defined below.
Definition 2.5 (Uniform last-iterate (ULI)). An algorithm is ULI for some E (0, if there exists a positive-valued function Fou(.;)) :), such that
(Vt E A, S Fuu t)) 2 1-5,
where (o t) is polynomial in (1/) and proportional to the product of power functions of R2 logt and 1/t (e.g.. Fo)( = polylog(1 (logt) = for some K1, K2 2 0).
According to Definition 2.5, the instantaneous suboptimality of any algorithm with the ULI guarantee be bounded by a function (6 (). Moreover, FuLI(ō, 1) decreases monotonically for large / its power on 1/t is strictly positive, which captures the convergence rate of A..
Note that the convergence rate of A is mainly determined by the power 1/t in FULI- Moreover, as we will show shortly, an algorithm with the ULI guarantee automatically has a small regret bound. We therefore have the following lower bound on FULI-
Theorem 2.6. For any bandit algorithm that achieves ULI guarantee for some 8 with function Fo t), there exists MAB instance such that Fvu(ő, t) Ω 1/2).
'ee use Ö(:) to hide polylog factors.

---

We provide the proof in Appendix A. In the rest of the paper, we say an algorithm is near-optimal ULI if it achieves the ULI guarantee with FU = (L/vVt).
Then, we present the following theorem show that ULI directly leads uniform-PAC, implying that ULI also characterizes the cumulative performance of bandit algorithms.
Theorem 2.7. Suppose an algorithm achieves the ULI guarantee for some with F Fou(,, t) =
polylog(t/0) t- where (0, 1). Then, we have,
the algorithm is uniform-PACC with function FUrAc(õ, O polylog(o-1e
with probability least 6, VT N, the regret Rr is bounded by
min { (o1)log(T/0) - - A - polloo polylog' ((64)
when the minimum suboptimality gap of the input instance satisfies A
According to Theorem 2.7, if an algorithm is with near-optimal ULI guarantee (i.e., = $) then implies the near-optimality for uniform-PAC bound (the first bullet point) and anytime sublinear high-probabiliin regret bound (the second bullet point). On the other hand, an algorithm with near- optimal uniform-PAC bound does not necessarily enjoy near-optimal ULI guarantee as shown in Section 3.2. The proof of Theorem 2.7 can be found in Appendix B.
Remark 2.8. Although a hear-optimet ULI guarantee implies an anytime sublinear high-probabilityy regret bound, it cannot give anytime sublinear expected regret bound. This is because any algorithm with ULI guarantee is also uniform- PAC, but [Dann et al., 2017, Theorem 1] implies that no algorithm can be uniform- PAC and achieve anytime sublinear expected regret bound simultaneously.
3 Achieving Near-Optimal ULI in Bandits with Finite Arm-Space
In this section, we answer the question whether ULI is achievable for bandit problems. To this end, we examine three common types of bandit algorithms, including elimination- algorithms, optimistic algorithms, and high-probability adversarial algorithms, the finite arm setting, i.e., |.A| = K.
3.1 Elimination Framework Achieving Near-Optimal ULI Guarantee
To examine whether the climination-type algorithms can achieve the ULI guarantee, first provide an elimination framework in Algorithm that ensures the ULI guarantee, and we then show that most elimination- based algorithms fall into this framework. The following result shows that with proper function f and a positive constant B, such an elimination framework ensures the ULI guarantee.
Theorem 3.1. For any given (0,1). if there exists function f = t """olylog(/// () for some E (0, 1) and 33 >> 0, such that with probability 1 - 8, Eq. (1) holds for all t, then algorithm is ULI with Fu 6, t) O (f(6.t)).
Algorithm 1 Elimination framework for ULI
Input: 5 (0, 1). set A. function f(::)) and constant S. Initialize: active arm set Au A.
for 1= 1, 1,2.... do
Select an active set A, based on available observations as (a" is one of optimal arms)
(6,t)) A {a Am A, 3. u u
Play an arm A, E A, and observe reward Xt,A,-
Theorem 3.1 suggests that Eq. (1) is a sufficient condition for elimination- based algorithms to achieve the ULI guarantee. Now, we show that existing elimination algorithms indeed fall into such framework. We here consider successive elimination (SE) and phased elimination (PE). Notice that we consider SE only for the MAB setting (called SE-MAB, e.g., Algorithm 3 in [Even-Dar et al., 2006)) but PE for both the MAB setting (called PE-MAB, e.g., exercise 6.8 in [attimoree and Szepesvári, 2020]) and the linear bandit setting (called PE-L., e.g., Algorithm of Chapter 22 in [Lattimore and Szepesvári, 2020]). Since those algorithms are standard, we defer their pseudocodes
5

---

to Appendix D. Given Theorem 3.1, the following results show that the elimination framework can be instantiated by these algorithms with proper functions and therefore they achieve the ULI.
Theorem 3.2. For any fixed å (0, 1), elimination framework in Algorithm I can be instantiated by
SE-MAB for MAB achieve the ULI with Fuu(ō, t) (t- log log Kt))
PE-MAB for MAB to achieve the ULI with Fuu(ó. (6, t) = O / K lo K log(t 1])). for linear bandits to achieve ULI with Fuu(6, t) = O 1 / log(t + 1) log d)).
Achieving ULI by adversarial bandit algorithms. Traditional elimination- algorithms, including the ones mentioned above, typically require carefully designed exploration strategy which non-trivial even for linear bandits. Here, we provide an alternative way achieve ULI by employing adversarial bandit algorithms to explore and then conduct the elimination. As shown in Appendix F, all adversarial bandit algorithms for both MAB and linear bandits that meet a certain condition can naturally be used to achieve the ULI guarantees similar to those of traditional climination- bassdd algorithms.
3.2 Lower Bound for Optimistic Algorithms
In this section, we present a lower bound to show that optimistic algorithms cannot achieve near- optimal ULI guarantee. The procedure of optimistic algorithms is summarized as follows. After playing each arm once, at each round t, the algorithm plays an arm A, that satisfies
A E argmax (Pa (Na(()))) + (s(N)((t))
(2)
aEA
where (t) is the number of plays of arm before round t, Taa (Na(())) Ele X,,A,I(A,=a)) is the Na empirical mean of arm a after Na (t) times play, and (t)) is positive bonus function which encourages the exploration.
We first consider optimistic algorithms e-g., upper confidence bound (UCB) [Lattimore and Szepesvári, 2020, Algorithm 3, Chapter 7], which enjoy (near)-optimal regret bounds. This type of algorithms typically uses the bonus function in the form of //og(2(2//))) (212/))///// /8).N(()) However, the log I term forces the algorithm to play suboptimal arms infinitely often, and thus they cannot achieve the ULI guarantee (refer to Appendix E.3 for a detailed proof). Similarly, other variants [Audibert and Bubeck, 2010, O Degenne and Perchet, 2016] with log f term in bonus function, also cannot achieve the ULI guarantee.
We then consider another optimistic- type algorithm, lil Ui' [Jamieson et al., 2014] which obtains the order-optimal instanc--dependet sample complexity and avoids log(t) term in U& (t)). The bonus function of liI is as Vlog (8- (8-1 (N)) (t) where log,, (a) ) = log (max {a, e)). Our main result for lil' UCB is presented as follows. The full analysis of UiI'UCB is deferred to Appendix E. Theorem 3.3. There exists a constant a E (0, 1) that for all E (0, at), running lil' UCB on the two-armed bandit instance with deterministic rewards and arm gap gives = 2 (A-2) such that
A. St -0((1 V/og log (A A-2
(A~2 log(5-1))
log(0-1))
Theorem 3.3 shows that lil'UCB not near-optimal ULI, but is unclear whether it can achieve the ULI guarantee. Recall from Theorem 3.2 that the dimination-basee algorithms ensure that with high probability, Vt, A. Ô (t (z2). Theorem 3.3 suggests that the convergence rate of lil'UCB is strictly worse than that of climination-bast performance [Jamieson et al., 2014]. In fact, this lower bound holds for all optimistic algorithms as long as the bonus function is in similar form.
algorithms, even if it enjoys near cpttmmptmmal cumulative
Remark 3.4 (ULI is strictly stronger than uniform- PACC) For lil UCB, the number of times playing suboptimal arms finite with an order-optimal irstance-dependent sample complexity. which implies that lil' UCB is near-optimal uniform-PAe PAC. Therefore, Theorem 3.3 also shows that an algorithm with near-optimal uniform- PAC does not necessarily enjoy near-optimal ULI guarantee.
'We slightly adjust the bonus function to ensure that with probability at least 1 ô, the confidence bound holds for all t E N.

---

Algorithm 2 PE with adaptive barycentric spanner
Input: Compact arm set A, confidence E (0, 1). and constant C 1. Initialize: 0 = {o....,.0 .0 E IR, To = 1 and Bo = fei...., Ed).
for 2, do
Set T. = 256C d0 I-m log (5-1
Invoke Algorithm 12 with (A, m. B, Tms C. to find C- C-approximate barycentric spanner Bm for active arm set Am where Am is in Eq. (3).
Set (a) d for each E Bm-
Play each arm E Bm for nm (a) [T Tm (a)] times.
Compute V. = I ++ EeeB Am aa)aaaa T and 0mt1 = Vm ELET A,Xi,A, where Tm is a set that contains all rounds phase
Achieving Near-Optimal ULI for Linear Bandits in Large Arm-Space
In this section, we propose a linear bandit algorithm that can handle the infinite number of arms. The compact arm set is assumed to span Rdd and is known.
4.1 Main Algorithm and Main Results
The starting point of our algorithm design is the phased elimination (PE) algorithm [Lattimore et al., 2020, Algorithm 12, Chapter 22]. However, PE in general is not feasible when the arm space is large (e.g., a continuous space). In this section, we present a serefully-designnn algorithm to address the new challenges from large arm-spaces.
Issues of PE for large arm-space. PE needs to (i) compute (approximately) G-optimal design whose complexity scales linearly with |.A] and (ii) compare the empirical mean of each arm, both of which are impossible when the arm set is infinite, e.g.. A a ball. A natural idea is discretize A, e-g.. constructing e-net, but the computational complexity has exponential dependence on d, and the optimal arm does not necessarily lie in the net, which prevents the convergence to the optimal arm.
High-level idea behind our solution. To address the aforementioned issues, we propose an oracle- efficient linear bandit algorithm Algorithm which can eliminate bad arms by efficiently querying an optimization oracle. Our algorithm equips PE with newly-developed adaptive barycentric spanner technique. The proposed technique selects a finite representative arm set to represent (possibly infinite) active arm set and adaptively adjusts the selection of arms across phases. By conducting the (approximate) G-optimal design [Kiefer and Wolfowitz, 1960] on the representative arm set and playing each arm in the set according to the design, the algorithm can acquire accurate estimations uniformly over all active arms. Moreover, the adaptive barycentric spanner approach can be implemented by efficiently querying optimization oracle in polynomial times.
The definition of barycentric spanner [Awerbuch and Kleinberg, 2008] is presented follows.
Definition 4.1 (C-approximate barycentric spanner). Let A C. Rd be a compact set. The set B = [bi..... ba] S A is C-approximate barycentric spanner for A each a A can be expressed as a linear combination of points in B with coefficients in the range of []C
Why adaptive barycentric spanner? The primary reason that the pon-adaptive barycentric spanner technique [Awerbuch and Kleinberg, 2008] fails to work for PE that it requires the knowledge of the space that the active arm set spans. However, acquiring such knowledge is often difficult because the active arm set, which may span a proper linear subspace Rd varies for different phases and the number of active arms could be infinite. Our algorithm shown in Algorithm 12 (whose pseudocode is deferred to Appendix G.2 due to space limit) can identify barycentric spanner for active arm set adaptively for each phase, even if they do not span Rd.
Algorithm procedure. Our algorithm proceeds in phases m 1, 2...... and each phase consists of consecutive rounds. At the beginning of phase m, the algorithm invokes subroutine Algorithm 12 to identify C-approximate barycentric spanner B,,, which can linearly represent all arms in active arm
set A., where A A and Vm 2 2
{o aa Am-1 (Tmo - -a) 5 2-m++1 m++1
Am
7

---

Algorithm 3 Tabular Episodic MDPs with ULI guarantee
Input: å (0, 1), set Han containing all deterministic policies, absolute constant c12 c2 O.
Initialize: 111 I11.1-
for m 1, ........ do
Set 6n (2m²² and duration Tm se 5² *H log² (c222m SHHHHHHHaaaa
Run Algorithm 4 with input (6m, Hm Tm) to obtain {V m Ielll.
Update active policy set m1 TT E Il max V V < 2-m
where am, is the empirical best arm and 0m is the estimation of unknown parameter 0.
Then, the algorithm assigns Tin (a) à for each a Bm- In fact, if add Usezm fi.. (refer Appendix G for and Im) back to Bm, and denote the new set by B then Tm B optimal design. It noteworthy that our algorithm only plays arms in Bm as these added elements do not necessarily exist in the arm set Am. As each added element e; is close to zero, even if we only vIn still acquire accurate estimations uniformly over Am (refer Appendix G.6
forms an
play arms in Bm, for details):
Ya E Am |ally = VaTVm S CCC Cdd//Tm
where Vn I EEEB.... Tm (a)aa" is the least squares matrix, used to estimate 0.
According to the standard analysis of linear bandit algorithms, the estimation error of (a. 0) is proportional to ||a|ly., 1. Hence, the estimation errors of {a, 0) )aEA.. can be uniformly bounded by Ö(Cd/ VIm-1). which is known to the learner. Finally, after playing each arm B, for n.n (a) times, the algorithm updates the empirical estimates Vm and 0m and then steps into the next phase.
The main results of Algorithm 2 for achieving the ULI guarantec and computational complexity given as follows. The full proof can be found in Appendix G.
Theorem 4.2. For any fixed E (0, 1), Algorithm 2 achieves the ULI guarantee with function Fou( () = O log(o -dd)) Moreover, in each phase, the number of calls to the optimiza- tion oracle given in Definition G.2 is O (d3 logo d).
Theorem 4.2 and Theorem 2.7 jointly suggest ((d"/2/T) worst-case regret bound for the infinite- armed setting, which matches those of [Dani al., 2008, Agrawal and Goyal, 2013, Hanna et al., 2023]. Compared with the lower bound (dvVT) given by Dani al. [2008], our regret bound suffers an extra vd factor, caused by the spanner technique. Yet, it remains open to find a computationally efficient linear bandit algorithm that can handle the infinite arm setting with general compact A and matches the ((d/T) lower bound.
Theorem 4.2 also shows that, for each phase, the spanner can be constructed by calling the oracle for only polynomial times. Compared to the computational efficiency of the algorithm in [Awerbuch and Kleinberg, 2008), the efficiency of our algorithm is only d times worse than theirs.
5 Achieving Near-Optimal ULI in Tabular Episodic MDPs
In this section, we propose a novel algorithm that achieves a near-optimal ULI guarantce in tabular episodic MDPs setup. The algorithm is formally presented in Algorithm 3.
High-level idea. Algorithm 3 conducts policy elimination over policy set 1l.11 which enumerates all deterministic policies. The key challenge here is to acquire accurate estimations of value functions uniformly for all deterministic policies. Note that naively playing all deterministie policies will incur linear dependence on |Пس = ASH in FULI. which is exponentially large. Hence, the algorithm invokes subroutine Algorithm to exhaustively explore the environment, which ensures accurate estimations of the transition model and only suffers logarithmic dependence on [Tau| Once the transition model can be well-approximated, the algorithm constructs an accurate estimation of the value function for every policy and then decides which policies should be eliminated.
8

---

Algorithm 4 Uniform estimation for value functions
Input: confidence (0, 1), policy C Man. duration T. Initialize: randomly pick a policy E 11, (1) NLN(s,a,s)) = 0 for all s, s'). for ( .,..., do
Observe initial state St,1 ~ p.
for h I...., H do
Take action det = Te, (81,)) and observe 8t,4+1 ~ Pn((
Increase counters Nt,1 (St,h att at,h, $1,1+11 $ 1 and Nen (r.h) $ 1.
Nenls,,,s") Update estimates (s,, a) max [ for all (x, a,s") E x A x S.
Update bonus function (be, where b,,(+,)) is updated according to Eq. (5).
Get (V.z (s1)) by invoking Algorithm 5 with input (II, b H, (Prr by $1,1).
Update policy k++1 argmax,en Vi,((s))
for 1 I...., do
Get (511(()))) by invoking Algorithm with input (I,,,, (Pra)ne(H) O, 8..1).
Output: (V*) weE where v- + Σ V7 (s,,))
Algorithm 5 Construct estimated value function
Input: policy set C ILm reward function r, transition P, bonus function b, initial state $1.
for E 11 do
@7 17+1(: and V (-) O. #++10)
for h = H, H ..... 1 do
(,)))) min P. P h+1 (..) + +b..),, and (.)() (+).(()).
Output: (VI(s))
More concretely, Algorithm 3 first accepts set of all deterministic policies and then it proceeds in phases m = 1, ..... In each phase m, subroutine Algorithm is invoked to learn the transition model. Specifically, the subroutine inherits the structure of UCB-V [Azar et al., 2017], but more importantly the algorithm pretends to agnostic to the reward function and uses uncertainty-driver reward functions (b, a) Hi, where
25 log
2HSlog
where 105 10SAH Ta (5)
(8, = HV m1 + 3 Nc,(s,))
=H
5
where (s, a) is the number of times of visiting (s, a) at stage h up to episode t. Note that Eq. (5) captures the uncertainty of visitation state-action pair, i.e., more visitations of (s, a). larger Ne, (s, a), and less uncertainty. This modification, inspired by [Wang et al., 2020] forces the algorithm to aggressively explore the environment, in the sense that the algorithm prefers play policy that maximizes the uncertainty.
The following theorem shows that our algorithm achieves the ULI guarantee.
Theorem 5.1. For any fixed E 1), Algorithm 3 achieves the ULI guarantee with finction log (L))H/))).
Fo ()
Theorem 5.1 shows oetinoptymality of Algorithm w.r.t. episode t. Unfortunately. the regret bound implied our ULII result incurs suboptimal dependence on S, H. and the logarithmic term, and algorithm is not computational efficient. We leave these improvements for future work.
6 Conclusions and Future Work
In this paper, we propose a new metric, the uniform last-iterate (ULI) guarantee, which captures both instantaneous and cumulative performance of sequential decision-making algorithms. To answer

---

whether ULI is (optimally) achievable, we first examine three types of bandit algorithms in the finite- arm setting. Specifically, we provide stronger analysis to show that elimination- based algorithms naturally achieve near-optimal ULI guarantees. We also provide reduction-basee approach to enable any high-probability adversarial algorithms, with mild condition, to achieve near-optimal ULI guarantees. We further provide negative result for optimistic bandit algorithms showing that they cannot achieve near-optimal ULI guarantee. Furthermore, in the large arm space setting, we propose an oracle-efficient linear bandit algorithm, equipped with the novel adaptive barycentric spanner technique. Finally, we propose a new algorithm, which adapts uncertainty-driven reward functions into policy elimination to achieve ULI guarantee in tabular episodic MDPs.
Some natural directions are to improve our current results, including proposing ULI algorithm for linear bandits with infimite arms and proposing a computationally efficient algorithm, possibly based on the action-elimination approach, for tabular MDPs. We also summarize other interesting directions as follows.
Design (computationally efficient) algorithms for MDPs with linear function approximation. The main challenge is to bypass any dependence on the number of states which is possibly infinite. Thus, generalizing our RL algorithm, which enumerates all deterministic policies, to linear MDPs does not work.
Design (computationally efficient) algorithms for Episodic MDPs with only logarithmic dependence on И (a.k.a. horizon-free), In our attempts, we use the doubling trick on e in existing (6, e--PAC horizon-free RL algorithms. In this case, we run the algorithm in phases with c, e/2, e/4..... The main difficulty is to leverage the information learned from the previous phase to guide the algorithm to play improved policy at the next phase as required by ULI. Thus, we conjecture that there might exist fundamental barriers to simultaneously achieve ULI guarantee and logarithmic dependence on H.
It could be also interesting to investigate some empirical issues when deploying ULI algorithms in high-stakes fields. Typically, optimistic algorithms initially incur a lower regret than ULI algorithms, but their regret will exceed those of ULI algorithms certain juncture. At this juncture, ULI algorithms have eliminated all suboptimal arms, whereas optimistic algorithms continue exploring time evolves. Hence, identifying this turning point could be beneficial for deploying ULI algorithms in high-stakes domains.
References
Y. Abbasi-Yadkori D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, 2011.
A. Agarwal, D. Hsu, S. Kale, Langford, L. Li, and R. Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, 2014.
S. Agrawal and N. Goyal. Thompson sampling for contextual bandits with linear payoffs.. In International conference on machine learning, 2013.
J. Y. Audibert and S. Bubeck. Regret bounds and minimax policies under partial monitoring, Journal of Machine Learning Research, 1(94):2755-2366. 2010.
J. Y. Audibert, S. Bubeck, and R. Munos. Best arm identification in multi-armed bandits. In Conference Learning Theory, 2010.
Auer, N. Cesa-Bianchi: and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 2002a.
P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77, 2002b.
B. Awerbuch and R. Kleinberg. Online linear optimization and adaptive routing. Journal of Computer and System Sciences, 74(1)997-114, 2008
M. G. Azar, I. Osband, and R. Munos. Minimax regret bounds for reinforcement learning. In Proceedings of the International Conference on Machine Learning, 2017.
10

---

P. L. Bartlett, V. Dani, T. P. Hayes, S. M. Kakade, A. Rakhlin, and A. Tewari. High-probability regret bounds for bandit online linear optimization. In Conference on Learning Theory, 2008.
A. Bibaut, A. Chambaz, and M. Laan. Generalized policy elimination: an efficient algorithm for nonparametric contextual bandits. In Conference on Uncertainty in Artificial Intelligence, 2020.
S. Chen, T. Lin, I. King, M. R. Lyu, and W. Chen. Combinatorial pure exploration of multi-armed bandits. In Advances in Neural Information Processing Systems, 2014.
V. Dani, P. Hayes, and S. M. Kakade. Stochastic linear optimization under bandit feedback. In Conference Learning Theory, 2008.
C. Dann, T. Lattimore, and E. Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems, 2017.
R. Degenne and Perchet. Anytime optimal algorithms stochastic multi-armed bandits. In International Conference Machine Learning, 2016.
D. Ding, C.-Y. Wei, Zhang, and A. Ribeiro. Last-iterate convergent policy gradient primal-dual methods for constrained mdps. arXiv preprint arXiv:2306.11700 2023.
E. Even-Dar, S. Mannor, Y. Mansour, and S. Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.
O. Hanna, L. Yang, and C. Fragouli. Efficient batched algorithm for contextual linear bandits with large action space via soft elimination. In Advances in Neural Information Processing Systems, 2023.
He, D. Zhou, and Q. Gu. Uniform-pac bounds for reinforcement learning with linear function approximation. In Advances in Neural Information Processing Systems, 2021.
K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck. uil: An optimal exploration algorithm for multi-armed bandits. In Conference on Learning Theory, 2014.
C. Jin, Z. Allen-Zhu, S. Bubeck, and M. I. Jordan. Is q-larning provably efficient? In Proceedings of the International Conference on Neural Information Processing Systems, 2018.
C. Jin, T. Jin, H. Luo, S. Sra, and T. Yu. Learning adversarial markov decision processes with bandit feedback and unknown transition. In Proceedings of the International Conference on Machine Learning (ICML), 2020.
Jin, J. Shi, X. Xiao, and E. Chen. Efficient pure exploration in adaptive round model. In Advances in Neural Information Processing Systems, 2019.
Kalyanakrishnan, Tewari, P. Auer, and Stone. Pac subset selection in stochastic multi-armed bandits. In International Conference on Machine Learning, 2012.
Kiefer and J. Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363-366, 1960.
T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Lattimore, C. Szepesvari, and G. Weisz. Learning with good feature representations in bandits and in rl with a generative model. In International Conference on Machine Learning. 2020.
C.WW. Lee, Luo, C.-Y. Wei, and M. Zhang. Bias no more: high-probabilltty data-dependent regret bounds for adversarial bandits and mdps. In Advances in neural information processing systems, 2020.
C.WW. Lee, Luo, C.-Y. Wei, M. Zhang, and X. Zhang. Achieving near instance-optimality and minimax-optimality in stochastic and adversarial linear bandits simultaneously. In International Conference Machine Learning, 2021.

---

L. Li, W. Chu, J. Langford, and R. E. Schapire. A contextual bandit approach to personalized news article recommendation. International Conference on World Wide Web, 2010.
Z. Li, Ratliff, K. G. Jamieson, Jain, et al. Instance-optimal pac algorithms for contextual bandits. In Advances in Neural Information Processing Systems, 2022.
T. Moskovitz, B. O'Donoghue, V. Veeriah, S. Flennerhag, S. Singh, and T. Zahavy. Reload: Rein- forcement learning with optimistic ascent-descent for last-iterate convergence in constrained mdps. In International Conference on Machine Learning, 2023.
O. Plevrakis and Hazan. Geometric exploration for online control. In Advances in Neural Information Processing Systems, 2020.
S. S. Villar, J. Bowden, and J. Wason. Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical science: a review journal of the Institute of Mathematical Statistics, 30(2):199, 2015.
A. J. Wagenmaker, M. Simchowitz, and K. Jamieson. Beyond no regret: Instance-dependee pac reinforcement learning. In Conference on Learning Theory, pages 358 418. PMLR, 2022.
R. Wang. S. S. Du, L. Yang, and R. R. Salakhutdinov. On reward free reinforcement learning with linear function approximation. Advances neural information processing systems, 2020.
Y. Wu, J. He, and Q Gu. Uniform-pac guarantees for model-based with bounded eluder dimension. In Conference on Uncertainty in Artificial Intelligence, 2023.
Y. Zhu, J. Foster, J. Langford, and P. Mineiro. Contextual bandits with large action spaces: Made practical, In International Conference on Machine Learning, 2022.
12

---

Appendix
Proof of Theorem 2.6
14
Proof of Theorem 2.7
14
B.1 Proof of the first bullet: ULI guarantee implies uniform-PAC bound
14
B.2 Proof of the second bullet: ULI implies regret bounds
15
Proof of Theorem 3.1
17
Proof of Theorem 3.2
17
D.I ULI guarantce for SE-MAB algorithm
17
D.2 ULI guarantee for PE-MAB
19
D.3 ULI guarantee for PE-linear
21
Omitted Details of Section 3.2
24
E.1 Proof of Theorem 3.3
24
E.2 Proof of Supporting Lemmas
................................
25
E.3
Traditional Optimistic Algorithms Fail to Achieve ULI Guarantee
................................
F
Achieving ULI by Adversarial Bandit Algorithms
29
E.I
Meta-algorithm Enabling Adversarial Algorithms to Achieve ULI
29
F2 Proof of Theorem F.4
F3 Proof of Proposition F.5
34
Proof of Theorem F.2
40
Omitted Details of Section
G.1 Notations
41
G.2 Key Technique: Adaptive Barycentric Spanner
G.3 Computational Analysis
42
G.4 Proof of Lemma G.4
43
G.5 Proof of Lemma G.I
44
G.6 Proof of Theorem 4.2: Regret Analysis
46
G.7 Proof of Theorem 4.2: Computational Analysis
H Omitted Details of Section
50
III Proof of Theorem 5.1
50
H.2 Construction of Nice Fvent
51
H.3 Supporting Lemmas
52
H.4 Proof of Proposition H.1
53
1 Limitations
55
J Broader Impacts
55
13

---

A Proof of Theorem 2.6
We prove this claim by contradiction. Suppose that there exists an algorithm that can achieve the ULI guarantee with function FULI(O, t) S co 22#
for some (0, 2) and constant oo > 0 which may depend on (/) and K for MAB or d for linear bandits. We consider a K K-armed bandit instance (K 2) with Gaussian rewards and all suboptimality gaps are bounded by one.
By the definition of ULI, have that with probability least 1 8, for all T N with Ti-a > lo. we have
Ry
A
tg
A
A
t=
< 105 +
Fin1(8,1)
1=
T
< to + Co
t a--
(=lo+1
20D
<T
T a0
2a
where the first inequality holds assume all suboptimal gaps bounded by one, and A, s Fo t) for all f 2 lo-
Since 1 E (0, )) there will be a contradiction to the regret lower bound [Lattimore and Szepesvári, 2020, Corollary 17.3] for the Gaussian MAB setup.
B Proof of Theorem 2.7
Theorem B.1 (Restatement of Theorem 2.7). Suppose an algorithm achieves the ULI guarantee for some 8 with function Fuurlō, l) polylog(1/8)- 1 where (0, 1). Then, we have,
the algorithm is also uniform-PAC with
Fuesc(Ó,e) (polylog(6-1c-1) cl/Rc
with probability at least 8, VT E N, the regret Ry is bounded by
min polylog(T/O) - polylog"
8A })
A/K-1
when the minimum suboptimality gap of the input instance satisfies A >
B.1 Proof of the first bullet: ULI guarantee implies uniform- PAC bound
In this subsection, we show the first bullet of Theorem 2.7. We define the following events for Fou = polylog(t/o) t
A = (AL E N: A, S ())
(6)
which indicates the occurrence the ULI, and denote the event B as:
Ve 0: Σ K4 > Pipaa((6.))
14

---

For some 8 E (0, 1), if event A holds for an algorithm with probability at least 1 - 8, then the algorithm is with ULI guarantee. Therefore, to prove the claimed result, it suffices show that conditioning on event A that for any algorithm enjoys ULI guarantee with function Fu (), one can find function FURAC(Ó, 6) such that event B also holds.
As for any fixed E (0, 1), (6) polylog(t/0) t- is monotonically decreasing for large t, 3U Ry such that F t) U for all & and Fiur(d, t) U is attainable by some Then, we consider any given >> O with two cases as follows.
-t
Case 1: U. Again, by the fact that (6), polylog(t/6) t-* is monotonically decreasing for large t, there should exist a round E N such that Fu s) S e for all s 2 t. Let to be the round with the maximal index such that Fu tu) > e, which gives
to polylog (to/o)
As result, the number of times that A, > occurs is at most
polylog (lo/0)
Σ HA $ Σ (FFu((,tt) > e) to S
6
Then, one can find constants co > and E (0, k) such that polylog(t/0) S co polylog(1/O)) (18)) for all t E Ry1, thereby polylog(ta/8) /8) I co polylog( (6) Combining polylog(fo/0)
polylog(1/8)t and Fuli to) gives
x polylog(to/))
co polylog(11 (1/)) = po1)1og(1/8)6
18
which immediately leads to
co polylog(1/8)) -
to
S
Then, we can further show that
polylog 8-1 0-1(5po22yog(11 corpoyyogg(1/8 k-2
polylog* (to/8)
Σ (AA))665
FUPAC (6, e),
6
where the third inequality follows that polylog(t/0) is monotonically increasing for all > 0 and Eq. (7).
Case 2: 2 U. Conditioning on event A and by the definition of U, we have A, S ( xc
U for all E N, which implies Σ I(A c) 0. Therefore, any positive function works there
and we still choose FL,Ac e) the same above.
This argument holds for all e > 0. Therefore, if an algorithm satisfies the ULI guarantee, then P(A) 2 - 8, and with the above statement, we can find function FUPAC such that IPB) 2 1 8, which concludes the proof.
B.2 Proof of the second bullet: ULI implies regret bounds
For some fixed (0, let us consider algorithm enjoys the ULI guarantee with function Fo The following analysis will condition on event A given in Eq. (6).
Gap-dependent bound. Recall that A > 0 is the minimum gap. We replace with A/2 in the proof of in Appendix B. case 1, and similarly define lo E N as the maximal round such that Fou( to) polylog(to/O) to 2/2. Then, apply similar argument (in Appendix B.I.
15

---

case 1), which gives that that for some constants E (0, x) and Co > 0:
Σ 11 > A/2]
S to
(9)
(200-plyylog polylog(1/6) - polylog 8-1 (20 x-2
A
I min
A
(A/2) :
where the last inequality holds by taking the minimum Eq. (7) and Eq. (8). Therefore, the algorithm will incur regret, i.e., A, 0 for all t to For every T N, the regret Ry is bounded by
Rr
A
polylog(1/0) 1
polylog(t/0) t
< polylog(to/O) /0)
1/ polylog(
(0)
(10)
1-R
where the first inequality holds since condition the event A, the second inequality holds due to the definition of to, the third inequality uses the fact that polylog(t/O) is monotonically increasing for all >
Then, one can further show
to --- polylog(6 to)
RT
1-A K
2cp pc0-polylog(1/] *
polylog
8-1
polylog(6 tto
A
(A/2)1/K-1
polylog
8-1
pooololly
w-a
polylog
8-1
po0yoooly (18)
A
(A (A/2)1/X-1
where the second inequality applies the second term of Eq. (9) and the last inequality uses the first term Eq. (9).
Notice that these bounds in all three cases hold for all T' e N, and thus the proof of gap-dependent bound is complete.
Gap-independent bound. We have
T
T
T1-x polylog (TT
Rt
polylog(t/6)- t- spoolylog(T//) Σ x-
1-k KK
t=1
t=
t=1
16

---

C Proof of Theorem 3.1
For shorthand, & holds with probability at least 1 - 8. The following proof is straightforward by the definition of E. We conditions on and consider an arbitrary round If A, a", the claim trivially holds as AA, = O. We then consider A, * a". Since Algorithm pulls an arm A, E A, at each t. From the definition of & we have A.. S 3 f6, t). Therefore, Algorithm achieves the ULI guarantee with (6, = O (f(),t)).
& denote the event that Eq. (1) holds for all E N. From the assumption,
D Proof of Theorem 3.2
D.I ULI guarantee for SE-MAB algorithm
Consider the successive elimination (SE-MAB) algorithm (e.g., Algorithm in [Even-Dar et al., 2006]) in the MAB setting where A [K]. We present SE-MAB algorithm in Algorithm 6 and define some notations, Let (t) be the number of times that arm a has been pulled before round and let Paa be the empirical mean of arm after E N number of plays. We define the confidence width for each E N as
(s) log (4Ks²/6)
(1I)
28
The SE-MAB algorithm always chooses the (from the current active set) with the minimum number of pulls. If there exist two arms a. E [K] such that N. (t) (t),), then, the algorithm chooses the arm with the smallest index.
Algorithm Successive elimination for aamti- bandit (SE-MAB)
Input: confidence E (0, 1). Initialize: active arm set A1 [K] and sample every arm once update Na(K 1), (Na(( 1)), Vvd(NN(L (K K + 1)) for all [
for f K + 1, K 2.... do
Play an arm A, arrgmn (t) and observe reward Xt.A,-
Update counter (t+++)) = N₂ (t) (f)+11 for A, and N₂ (t+1) Na forall A. (A,). Update empirical means A., (NV,, ( (t + 1)) BA, (O) and ea (Na (t 1)) for all E AA - {A,}.
NA, 0041
Update confidence width wd Na (t + 1)) based on Eq. (11) for all At. Update bad arm set B, as
B, = {a E A 3j E A such that eo (N, 1)) (V - PNa - + 1)) > 0}.
Update active
A+t1 A Bi-
Definition D.1. Let E be the event that I (N)(t)) Hal S wd((N(t)) holds for all e N and all
a E A,.
Lemma D.2. P (8) 2 1 5.
Proof. Following the standard trick (e.g.. [Audibert et al., 2010). we rewrite the empirical mean for every a. Pa (n) > Ri,a where Ri,a is the reward of i-th pull of amm Let us fix both E N and E [K] By Hoeffding's inequality, with probability at least - 8'
log
[P, (5) Mal S
2s
Choosing 8' probability least 1 5/(22²)
.ズ. and applying union bound over E A. (AA:) S K, Vt), have with
log 4Ks2
Pa (s) - Maa S
wd(s), Va E (K].
2s
17

---

We apply a union bound over all & E N and use the fact that E 6 S 5 to finish the proof. 22
Lemma D.3. Suppose that & occurs where & is given in Definition D.I. For all t E N, a" E A holds.
Proof. We prove this by induction. For = a' E Ai trivially holds. Suppose that a" E A,, To show a" Ar. suffices to show that at the end of round I, arm a" is deemed good arm. One can use the definition of & to show that for every a E Ac, the following holds.
S pz Me Po. (No (t + 1)) ( (t 1)) P. (t 1)) wd(NN 1))-
Note that the second inequality above can hold since the inductive hypothesis gives that a" E A The above inequality shows that a* will not be eliminated the end of round thereby still being active at round I. + 1. Once the induction is done, the proof complete.
Lemma D.4. Suppose that occurs where & is given in Definition D.I. For all E N and all arms E Afa E Ao, then
14K log (4K+²/8)
Aa S
t
Proof. Consider any round E N and any active arm E A.. For simplicity, we assume that the first arm is the unique optimal arm? If a is an optimal arm, then A, 0 and we hold the claim trivially. Then, it suffices to consider an arm a A, with A, > 0. Notice that wd(x) monotonically decreasing for all 2 1 as long as K 2 2. Thus, we find minimum natural number Ta E N such that
log (4KT3/0) 5Td.
A 2 5
(12)
21a
With this definition, we have
A. < 5wd(s) V1 8 < To: and A, 5wd(s) Vs 2 Ta.
Recall that (t) is the number of plays of arm a before round t. We first show (a(t) S To. As Algorithm pulls arms in round-robin fashion, if arm pulled for Ta times, then, the optimal arm a" is also pulled for Ta times, thereby To Te. From Lemma D.3, optimal arm a" is active for all N and thus we can use it as a comparator.
pa (Ta+) wd(TT.) (Ta) wd(Ta) 2 4¹ 2wd( Paa 2wd(Ir)
(by E) (by Ta = T
4³ - 2wd(Ta) Ha -T.)(T.)
Ag A
2 A. - -2 x
x
5
5
A
5
According to elimination rule, this inequality shows that arm a will be eliminated after T, pulling times, which suggests that (1) < T.. Since the T, is the minimum natural number which holds Eq. (12), we use (1)
()) < Ta to show
log
- 1)2//)
log (4K12/8)
A < 5p.
5
2(Na(1) 1)
2(N. -))
where the last inequality follows from the fact that Nt) < t. Rearranging the above, we have
25 log (4Kt//)
13 log (4Kt/6)
No < 1+
24
A
"This assumption is made only for simplicity, but our proof can be easily extended to multiple optimal arms by changing the constant.
18

---

Again, as Algorithm 6 pulls arms in a round- fashion, we have t S (t) + 1) and show
14K log (4Kt²/4 /6)
S (KNN(++))))
A
which gives A which thus completes the proof.
14K 10g(1)12/0)
Conditioning on event & the argument holds for all N.
1
Proof of Theorem 3.2 SE-MAB. Once Lemma D.3 and Lemma D,4 hold, Theorem 3.1 gives that for any fixed E (0, 1). SE-MAB achieves the ULI guarantee with a function
=0(v
(V (K1/5)
K
Therefore, the proof of Theorem 3.2 for SE-MAB complete.
D.2 ULI guarantee for PE-MAB
In MAB setting with A = [K]. we further consider phased elimination algorithm (c.g., Exereise 6.8 of [Lattimore and Szepesvári, 2020]) shown in Algorithm 7 (called PE-MAB). The algorithm proceeds with phases ......., and each phase includes consecutive rounds, with an exponential increase. In phase the algorithm sequentially pulls every arm [K] for my times where
my 22 log (4K&2/8))
Once arms are pulled my times, the algorithm steps into the next phase + The counter N (c) records the number of times that arm is pulled in phase i and (m²) is the empirical mean by using my samples only from phase l.
Algorithm 7 Phased elimination for multi-armes bandit (PE-MAB)
Input: confidence E (0, 1). Initialize: active arm A [K].
for e= 2, do Play every arm Ar for my times and observe corresponding rewards. Update empirical means (ma)) aeA, only using samples from phase L.
Update active arm Aet1
Ae+1 Ai a Ae max (ax()) (a 2-
jEA:
Definition D.5. Let & be the event that [Pa pal < 2-8-1 holds for all & e N and all E Ar. We first give the following lemmas, whose proof is similar to those of Lemma D.2 and Lemma D.3. Lemma D.6. P(E) 2 -
Proof. We first fix both E N and [K]. By Hoeffding's inequality, with probability most 8', we have
Pia (me) - Hal 2 log (
2m
Choosing 8' 2R'2 and applying union bounds most /22 have
Ae (Ac is at most K), with probability
log (4K2118
(mme)) - Hal
2 2-6-1
2114
We apply union bounds over all l N and use the fact that Σ
Et=1 2
S to finish the proof.
19

---

Lemma D.7. Suppose that & occurs where & is given in Definition D.5. For all E N, a' E As.
Proof. We prove this by induction. For the base case & = 1, the claim trivially holds. Suppose the claim holds for l, and then will show that a A For all E N and all Ar, have
S 4² Ma S Pa- (me) - Pa (me)) + 2
where the second inequality holds because the induction hypothesis ensures a' E A and thus we can use the definition of E. Based on the elimination rule, a" E A Once the induction is done, the proof is complete.
Lemma D.S. Suppose that & occurs where is given in Definition D.5. For each arm a with 4. > 0, it will not be in Ae for all phases 2 la + where la is the smallest phase such that 2 > 2 fu.
Proof. Consider any arm with A, > O. We only need to consider E Ar.. and otherwise, the claimed result holds trivially. Recall that la is the smallest phase such that A > 2-fa and one can show
max (y(mee.) (aa(me))))) 2 2a jEAr
2 pa (me,) - Ma 222 P.
2 k¹ 2 t/ Ha - hh
Aa
> A. 2 x
2
0,
where the first inequality follows from Lemma D.7 that a" E At, and the second inequality holds due to E
According to the elimination rule, will not be in phases e for all l ta 1.
Lemma D.9. Let E(L) be the phase in which round lies. Then, E(I) S logg + for all & N.
Proof. We prove this by contradiction. Suppose that 3t N that ((t) log +). Note that further assume E(t) 2 2 since one can easily verify that for all such that {(t) = 1, E(t) S log, (t (1) must hold. We have
t m 2 220(1)-1og log (4K(E(t)- - 1))/0))))(())))))))))))))))))))) J 1)a log (4K/8) >
where the third inequality bounds E(t) in the logarithmic term by E(t) 2 and bound the other E(t) loga (t + 1) by assumption. Therefore, once contradiction occurs, the proof is complete. O
Lemma D.10. Let E(t) be the phase in which round lies. Suppose that & occurs where E is given in Definition D.5. For all e N and all a E [K], if Aetey, then
256K log 4K (log, (t + 1))2/1))
A. S
31
Proof. If a E Ant is optimal, then, A, = 0 and the claim trivially holds. In what follows, we only consider arm a E Aeto) with A, > 0. From Lemma D.8, if an arm Aete is with A, > 0, then, E(t) Ea where la is defined in Lemma D.8. Thus, the total number of rounds that such an arm is active is at most
8(1) K
{(()
K
2 21+1 log (4Ks2/00 s
#
#=1
f(t)
< 4K log (4KE(1)//8)
Σ
2
20

---

4K log /6)))))))))))))))))))))))))))(
Σ
220
16K log
(4K2(()))00)
.44
256K log (4Ke(t)2/0)
34
256K log [KK (log2(1 (t + 1))² /6)
3
where the first inequality follows from [x] I 2x for all x 2 1, the second inequality bounds
((t) I far the fourth inequality follows from the definition of las i.., Au
2 I (fa 1) and the last
inequality follows from Lemma D.9 that {(t) logg(t
Since this argument holds for each round and each arm a E Ae(o) conditioning on &, the proof is complete.
L
Proof of Theorem for PE-MAB. Once Lemma D.7 and Lemma D.10 hold, Theorem 3.1 gives that for any fixed å E (0, 1), PE-MAB achieves the ULI guarantee with function
FoL((,, t) = 0 (t
K log (K log(t + 1)/6))
Therefore, the proof of Theorem 3.2 for PE-MAB is complete.
D.3 ULI guarantee for PE-linear
Algorithm 8 Phased elimination for linear bandit (PE-linear)
Input: confidence (0, 1). Initialize: active arm set A1 = A. for f. 1,2.... do Find design me E A(As) with
max rEAt
|alll S 2d, and |supp( [T) S lo log(d) + 16,
(13)
where G5 EnEA Te(a)aaT.
Play every arm E A for me(a) [e((amme] times and observe corresponding rewards. Update the empirical estimate as
Q = V
Σ 1ET
A.X
where
=e= Σ
mela)aaT.
(14)
ac
Update active arm set
- - > 2-(41)
A = Ac-
a a
A:: max beAi
We consider a phased elimination algorithm (e.g., algorithm in Chapter 22 of [Lattimore and Szepesvári, 2020]) for linear bandits setting with a finite arm set A = [K]. The algorithm proceeds with phases f = 1, 2, and in each phase f, the algorithm first computes design E A (AAe) over all active arms where ((Ar) is the of all Radon probability measures over set Ar. Rather than computing an exact design in [Lattimore and Szepesvári, 2020], we follow Lattimore et al. [2020] to compute a nearly-optimal design (13), which can be efficiently implemented. Then, PE-linear plays each arm Ar for my(a) times and updates the active arm set by using the estimates in this phase.
Let define Te be that contains all rounds in phase & and
4d
m²(a) (a)m/l, where
m,
20 max {log (4KE2/8) log log + 4) (15)
21

---

Lemma D.11. For all & E N and all a e As. lalli S
2d
holds.
me
Proof. For each & E and a E Ar, one can show
| V a
me Σ re(a)aa acAAe
2d mig
where the first inequality follows from Eq. (15) and the fact that if we let A me EneA, Te(a)aa and B Ve then, ||al|a=1 2 |||| holds since A-1 B-1 and the second inequality uses Eq. (13).
Definition D.12. Let be the event that Kθe (oc-6.a) $2 holds for all E E and all E As.
Lemma D.13. () 2 1 d.
Proof. Consider a fixed phase and a fixed arm a E Ag. We start from the following decomposition.
(o.- - 0,
V
Σ
A,X,, - 0,a
LE
Σ
A (A + m2) - -8,a
NE
Amn a
TE
Σ (V; Ae, a) M1
ET
By Eq. (20.2) of [Lattimore and Szepesvári, 2020], have with probability at least 1 6/(2P2K).
dlog(462
Σ (VE A,,a) m S 22 log(482 S VV
2
m
where the last inequality applies Lemma D.11. Finally, applying union bounds over all a, E completes the proof.
Lemma D.14. Suppose that & occurs where & is given in Definition D. We have a* E As for all e N.
Proof. This can be proved by using induction on via the same reasoning of Lemma D.3.
Lemma D.15. Suppose that & occurs where is given in Definition D. 121 For each arm a with
A 0, it will not be in Ae for all phases la + where ta is the smallest phase such that
2
Proof. Consider any arm with AS > O. Let la be the smallest phase such that Aa > 2 f. and have
ba) -2-hut 1ltt1 (0t,,
Eut2 -2) 2 10,0a a) -2 2 tu+2 A. 4x
A
max beAr,
0,
where the first inequality follows from Lemma D.14 that a* E Ar for all C.
According the climination rule, arm will not be in A for all phases é la + Since conditioning
on ε, this argument holds for every arm the proof is complete.
Lemma D.16. Let ((t) be the phase in which round t lies. Then, E(t) < log, (t + 1) for all t N.
22

---

Proof. We prove this by contradiction. Suppose that 3t E N that f(t) > logg(t++) Note that we can further assume {t) 2 2 since one can easily verify that for all such that {(t) (()) s log, (t + 1)
must hold, We have
Σ -
4d
ma(t))12 2 2- 1((()-1) (log (4K(((t)-1)//8) d(t 1) log (4K/6) t.
where the fourth inequality bounds E(t) in the logarithmic term by ((t) 2 2 and bound the other E(t) log2 (t 1) by assumption. Therefore, once contradiction occurs, the proof is complete. L
Lemma D.17. Let E(l) be the phase in which round & lies. Suppose that & occurs where & is given in Definition 1. For all E N and all [K], if E Accez, then
512dlog (log(d) (log2 + 1))² 18) +4
A
3
Proof. If a E Arto is optimal, then, A, = 0 and the claim trivially holds, In what follows, we only consider arm E Aea with A₂ > O. From Lemma D.15, if an arm a E Aeca is with A, >> 0, then, E(t) < la where la is defined in Lemma D.15. Then, the total number of rounds that such an arm active is at most
Σ
Σ
[=)(m)m
(a))
{(L)
4d log log(d) 16
Σ
aEA., (a)
((t)
mg
s=1
{(t)
1
Sd max {log (4KE(t)//6) log log d + 4]
Σ
2-28
la
s 8d max log [4K (toga(t + 1))² /8) log log +
+4
Σ
1
2-25
am1
512d
(log (ogg()) (log2(1 + 1))² /8) + +4)
3
where the first inequality applies [a)mm) S n2 (a)am,, + and Eq. (13), the second inequality uses the definition of m. (see Eq. (15)), the fourth inequality follows from E(t) < t, and Lemma 1.16 gives (() < log,(t (L+ + 1), and the last inequality uses As < (fa--1 to apply f,, < log, ($/a.)-
Since this argument holds for each round and each arm E Aeto conditioning &, the proof is complete.
Proof of Theorem 3.2 for PE-linear Once Lemma 1.14 and Lemma D.17 hold, Theorem 3.1 gives that for any fixed 8 E (0, 1), PE-lincar achieves the ULI guarantee with function
F5 (8 t) O (1 / (log(d) K (log(t + 1)) 15)
Therefore, the proof Theorem 3.2 for PE-linear complete.
23

---

E Omitted Details of Section 3.2
The bonus function that here consider for UiI is as: Ug(2)= log log (max e)) + log (6/0)
(16)
The choice of (z) in Eq. (16) is slightly different from that of [Jamieson et al., 2014] because consider for any 8 E (0. 1) and they constrain the choice of ó in more restricted range. The choice of (z( is motivated from another lemma of law of iterated logarithm, given in [Dann et al., 2017, Lemma F.1] with x² = 1/4 as we here consider [0, --bounded rewards. Note that the concentration bounds in [Dann al., 2017] apply for the conditionally subgaussian random variables, and one can get the same result for i.i.d. subgaussian random variables, by simply replacing the Doob's 's maximal inequality by Hoeffding's maximal inequality (see [Jamieson et al., 2014, Lemma 3)).
One caveat here is that our analysis still works for other choices of U3 (2) if one adjust constant or change log log(-) to log(-).
Algorithm 9 lil
Input: confidence (0, 1) and arm set Initialize: play each arm É A once to update (aA + 1) and (l. + 1)) for all E A. for t |A| + 1, |A| + 2.... do
Play an arm
A argmax (Na( Us (N))
aEA
where (!)) is given Eq. (16).
Update counters No (1 1) Na(1) + 1 for A. and (1 + +1) Na No for all a + A..
Update empirical means PA (Na, (t + 1)) (NA, (B))-NA, Na, (t)+ and (Na + 1)) = Pa (Na(N))) for all E A {A.)
(1)(+)+
E.1 Proof of Theorem 3.3
In the following proof, consider the following instance. Definition E.1 (Two-armed bandit instance). Consider two-armed setting with μn > P2. In each round, each arm generates deterministic rewards μil and μ2, respectively. The arm gap is A = A11 u2 and A E (.,).
According Lemma E.2, the total number of plays of arm 2 is finite. Therefore, one can find round to E N that the last play of arm 2 occurs. At the beginning of this round, the algorithm compares #1 + Ug (to)) and μ2 (s(NN(to)) Since arm 2 gets the last play at this round, we have
in + (NV (to)) S μ22 + (&(N2((o)) S p2 (1 + f()))
where the last incquality holds due to Lemma E.4 and f(A) defined as
3
f(A)
(17)
log log
log(6/8) 1
+ log(6/5)
Rearranging the above, we have which immediately leads to
Us (t)
log log
log (6/8) P(AJA?
+ log(6/8)
N (to) Z
f²(A)A2
Moreover, since arm is played round tu. A which further implies that
(1oo + Ne(to)
24

---

(too
log log
log(6/8)
+ log(6/0)
(A)))
(2(A)
log log
[og[6/6]
1og(6/6))
A*
34
log log [oog6//)
1og(6/6))
3A 1
Ato
where the third inequality uses f(A) < 1 for all A E (0.0.6), and the last equality holds due to A AAo (recall that in round to. arm 2 gets the last play).
Rearranging the above, we have
log log
log(G/8) A
+ log((/8)
(3to)
log log
log(6/6)
+ log(6/6)
A
A A1o
(3to)
34o
Finally, by Lemma E.3, we have In = 12A2212) which completes the proof.
E.2 Proof of Supporting Lemmas
Lemma E.2. Suppose that we run Algorithm 9 for the two-armed bandit instance given in Defini- tion E.I. For any å E (0, 1), suboptimal arm 2 will be played at most
2 log log
16 log(6/))
+ log(6/5)
A
Proof. Note that for any fixed 5 E (0, 1). function Us(x) is monotonically-ddcreaiing for 2 6. To show the claimed result, suffices to find an integer xr 2 6 such that
Us(x) A.
Now, consider the following choice.
log log
( 16 log(6//)) A
+ (6g())))
= [[n], where n
A
Notice that N 2 2 6 for all A (0,1). 1]. Then, one can show
Us(N)= - (n(n)
2 2(log log( 161ox(6/5) +lox((/8))
log log
+ log (6/8)
A
A.
2 log log
log(6/8)
2 (og(6/8)
A
4 log log
16log(1/6))
llg(6/8)
log log
+ log (6/0)
A
A
log log
16
2lo((6/6)
A=
log
log
1 log log
16log(6/6) A
+ log
16 16 A2
+ log (6/8)
A.
2 log log
16 (G/g)(//))
(6/8)
A=
25

---

2 log log
10 (og((//8)
log (6/6)
log log
[6
+ 2 log(6/0)
AA.
where the first inequality uses the fact that for any fixed 6 E (0. 1). (2( is munotonicalyy-decrrassii
for 2 6, the second inequality uses x + y I 2xy for all z, (here
log(6/8) and
y log log
(1 A
(og(6
). the last inequality first bounds log log 16log(6/0)
16 (6/(6) and A
then uses 2x S x² for all with log
(66log(6/)) A²
2.
Thus, the proof is complete.
From Lemma E.2, the total number of plays of suboptimal arm is finite. Based on this fact, we present following lemmas.
Lemma E.3. Suppose that Algorithm for the two-armed bandit instance given in Defini- tion E.I. Let n + 1 be the total number of plays of arm 2. Then,
log log
log(6/)) A²
+ 1og(6/5)
ni 2
2 6.
2
Proof. For shorthand, define
log log
log(6/6) A
+ (og(6/o)
m
(18)
With this definition and A E (0, 0.6), we have m 2 6 and [m] 2 6.
Now, we show that n 2 [m]. To this end, it suffices to show Us([m]) A. As Us(z) is monotonically-decreaa for all x 2 6 and m 2 [m] 2 6, we have
Um([m.]) 2 (m(m)
log log( Lox(e/5)
(ox((/8)
log log
32
+ log(6/6)
log log
(og(6/5) A
log(6/8)
where the last inequality holds as
log (6/()/)) A
(og(6) A
> e.
Once Us((m)) > A holds, [m] cannot be the last play of arm 2 (i.e., at least the one before the last), which completes the proof.
Lemma E.4. Suppose that
Algorithm for the two-armed bandit instance given in Defini- tion E.I. Let n + 1 be the total number of plays of arm 2. The following holds.
3
Ug(n) SA
1+A
log log
log(6/6) A
+ log(6/0)
Proof. From Lemma E.3, have 6, and thus (n(n)
> Us(n + 1) Us(w) is monotonically
decreasing for all x > 6. Using the fact that for all b 0, b Va 82 (here Us(n) and Us(n + 1)), one can show that
Un(n) Us(n 11)
log log (max (n, e)) log (6/8)
log log (max (n 1, + log (6/8)
+ 1
26

---

log log (max(n, e}) log (6/8)
log log (max + 1,e}) + log (6/0)
n +
nn + 1) log (max(n.e)) - n log log (max(n 1, (.e)) + log (6/6)
nin +
log log [n,x(n,e)) e}) + log (6/8)
(19)
n(n 1
Since for any fixed d (0, 1). (z( is monotonieally-derraaee for all x 2 6, and thus by using the definition of m (see Eq. (18)), one can show that
Us(n)- Us(n + 1)
log log [m]] + log (6/5)
m (Im 1)
log log (m) + log (6/0)
m
A
log log
log(6/6) A7
+ log (6g(6/))
log log
log (6/8)
log log
log(6/6)
+ log(6/6)
A
A
2
log (gg(6/))
))
log
2 log
+ log (6/6)
log log
log(6/8)
log(6/5)
A
A²
2
log(6/0) 2
3 log log
+ log (6/8)
log log
log(6/8)
log(6/0)
V3A²
log log
log(0/8) A²
log(6/0)
where the first inequality uses Eq. (19) with [m] > and (s(x) is monotonically decreasing
for all x 2 6, the second inequality upper-bounds |m] I m in numerator and (ower-bounds
[m] ([ml +1) m the third inequality follows from
log log (on(6/5)
+ log(6/8))
log(6/8)
log(6/0)
(lo(66/8) 2
2
2
and the fourth inequality follows 2x < 3 for all x 2 v with x = log (0, 0.6)).
(og(66/)) A
2
V2 (A E
After arm 2 gets n + times play, will not be played anymore, which implies that Us(n + < A. Using this bound gives
3
Un(n) < A +
log log
log(5/8) A
+ 1og(6/5)
Therefore, we complete the proof.
F.3 Traditional Optimistic Algorithms Fail Achieve ULII Guarantee
We will show that the traditional optimistic algorithms fail to achieve the ULI guarantee due to the log term in the bonus. high level, log is increasing with time and forces the algorithm to play bad arm indefinitely when & evolves. We provide the formal proof in the following:
27

---

We prove the claim by contradiction. Consider a K -armed bandit instance with at least one suboptimal arm, and let A > 0 be the minimum arm gap. Suppose there exists an optimism- algorithm with log in bonus term that can achieve the ULI guarantee in this setting. Then, for some fixed 6, for all N, A S FELr t). Based on Definition 2.5, we have lim Fo = 0 and Fū t) is monotonically decreasing w.r.t. t after threshold. Thus, 36g E N such that FULr(ô, t) < for all f 2 to. In other words, the algorithm cannot play any suboptimal arm after to round. Recall that the bonus term Vlog t/Na(U (t) where No (t) is the number of plays of arm before round For any suboptimal arm a, (1) should not increase after 1o-th round, but log / keeps increasing. This leads the bonus of arm a goes to infinity, which will incur play of arm at round after to- This makes contradiction.
5 E (0, 1), with probability 2
28

---

Algorithm 10 Meta-algorithm towards ULI
Input: 8 (0, 1), finite arm A, and base-algorithm Alg with function g(ö) that satisfies Condi- tion. F.I.
Initialize: A1 [
for m = 1...... do
Set duration mm Run Alg with active arm set Am for T' rounds and construct É, (Aema)) for all t, a in this phase.
m576gm2 2 where =
2m
Update active arm Am+1 Am B, where:
Bm = a Am
Σ SETm..
(Baa--esh)
Eeekk
> 7 9m I'm
(20)
and Tm is set that contains all rounds in phase m and k is the empirical best arm:
k argmin Σ taa
eEAm
SET
F
Achieving ULI by Adversarial Bandit Algorithms
F1
Meta-algorithm Enabling Adversarial Algorithms to Achieve ULI
In this subsection, we propose a meta-algorithm shown in Algorithm 10 which enables any high- probability adversarial algorithm, with mild condition, to achieve the ULI guarantee. Then, show that existing high-pro ceeh-prbbabiltty adversarial bandit algorithms naturally meet this condition in both MAB and linear bandit settings. For notational simplicity, we follow the convention of adversarial analysis to use loss l,a = 1 - Xt.a- Note that all algorithms in this subsection require [o, 1] |-boundedness assumption loss.
At a high-level, our meta-algorithm keeps running a base-algorithm Alg to play arms and collects rewards. The meta-algorithm estimator Lr, (A,,a)) for each t, a. which helps eliminate bad arms, and then runs Alg on reduced arm space. To achieve the ULI guarantee, our aeta-algorithm requires the input case-algorithn satisfy the following:
collected rewards to construct the importance-weighted (IW)
Pt.a
Condition F.1. An algorithu Alg runs for given consecutive T rounds with a finite arm set A and fixed 6 E (0, 1). At each round E [T], Alg maintains a distribution pt over A and samples an arm A, ~ Pr. With probability at least 66, Alg ensures for all A.
T Σ 1=1
Σ (l..A. 4.,) Vo(6)T -
(21)
where g(ō) a positive-valued function, monotonically decreasing for all d E (0, 1), polynomial in log(1/8), and g(6) > log (10] v6
1).
In fact, many high-probabbiity adversarial bandit algorithms naturally meet Condition. F.1, but require stronger analysis. In particular, we show that EXP3.P [Auer et al., 2002b] for MAB holds this condition with g( = ((AA) (lg(()))/)) (omitted proof can be found in Appendix F) and Lee al. [2021] show that GEOMETRICHEDGE.. [Bartlett et al., 2008] with John't ion's exploration meets the condition for linear bandits with g( Od Al/)).. Hence, feeding those algorithms to Algorithm 10 yields the following:
Theorem F.2. For any fixed E (0, 1), if Algorithm 10 uses
ExP33.P P base-algorithm, then, for K-armed bandit, ULI guarantee is achieved with
Fvu(ô,t) Ott - KK log (6-1 1 log(t 1))).
29

---

GEOMETRICHEDGE.T as a base-algorithm then for linear bandits with K arms, ULI guarantee is achieved with
F Ot V (8-1K log(t + 1)))
Theorem F.2 suggests that Algorithm 10 enables ExP3.P and GEOMETRICHEDGEL, to achieve near- optimal ULI guarantees for MAB and linear bandits, respectively. Moreover, their ULI guarantees are as good as those of conventional elimination- based algorithms (refer to Theorem 3.2).
Our main objective in this section is to prove the following results.
Theorem F.3 (Restatement of Theorem F.2). For any fixed å E (0, 1), if Algorithm 10 uses
ExP3.P as a base-algorithm, then,for K-armed bandit, ULI guarantee is achieved with Fu) =((( log (ō 1 log(t + 1)))-
GEOMETRICHEDGE. as a base-algorithm then for linear bandits with K arms, ULI guarantee is achieved with
Fu t) = O / (8- log(t + 1)))
decompose the proof of Theorem F.2 into two parts. the first part, we first show that any algorithm with Condition, F.I for some å E (0, 1) can achieve the ULI guarantee. Then, we only need to show that EXP3.P and GEOMETRICHEDGE.. satisfy Condition. F.I, which completes the proof of Theorem F.2.
The following result suggests that showing an algorithm enjoys the ULI guarantee is reduced to show that this algorithm meets Condition. F.l.
Theorem F4. For any fixed 8 (0,1), Algorithm 10 uses base-algorithm that satisfies Condi- tion. F.I, then, it achieves the ULI guarantee that
01 log 2 + 1)) 2 21-6. -
( )1))
P M
-
t
sketch the proof of Theorem F.4 as follows. The full proof can be found in Appendix F.2.
Proof Sketch. The high-level objectives are to show the sufficient condition of Eq. (1) given in Algorithm I to achieve the ULL. We first show that the optimal arm will not eliminated, i.c. a" E Am for all phases E N. To show this, we only need show
(La..o- -Tan) S TV Im where le E argmin Σ Es.a
Vm N
(22)
oEAm SET...
SET.
which does not meet the elimination rule in Eq. (20).
For analysis purpose, we decompose Eq. (22) as
Σ
(Taan- - (s, = Σ
(La,a- - Es + Σ (Ls,a-
La,k) +
Σ 8E Tm
(la,k - Pau) (aa)) (23)
TETm
BETm
8ETm
The first and the third term in Eq. (23) can be handled thanks the bound on E. le,) in Eq. (21), and the second term in Eq. (23) can be handled by invoking the standard concentration inequality as losses are drawn from fixed distributions.
Then, we show that if an arm is still active at round f, then, for all active arms E A,, A, is bounded by a function, monotonically decreasing for large This can be proved again via a similar decomposition of Eq. (23) to get
Σ TET
(2.a-2a. 0.5TT - -ōv 9m Tm-
Therefore, for some large Ti such that 0.57 5y climinated. Putting two pieces together, complete the proof.
7 7mmmmt T bad arms will be
D
30

---

With Theorem F.4 in hand, our next objective is to show that EXP3.P P and GEOMETRICHEDGE,I are able to satisfy Condition. F.1. For GEOMETRICHEDGE.P with John's exploration (which improves the original bound [Bartlett et al., 2008)), Lee et al. [2021] have already shown that it achieves the condition, and the rest result will show that ExP3.P also holds The full proof can be found in Appendix F.3.
Proposition F.5. In MAB setting, for any ò E (0,1), EXP3.P with given arm set A, satisfies Condition. F.1 with g( O (IA) log (IA)/8)).
The key that ExP3. P well as GFOMETRICHEDGE.J can fulfill Condition, F.1 is because it adds small amount probability for uniform exploration to each arm. Therefore, the importance-weighted (IW) estimator be lower-bounded and the term Ee te,a) will not be too large.
Apart from EXP3.P for MAB and GEOMETRICHEDGEL. for linear bandits, Lee et al. [2021] show that refined version of SCRIBLE [Lee et al., 2020] can be used as base-algorithm for Algo- rithm 10 to achieve the ULI guarantee for linear bandits, but the ULI guarantee is inferior to that of GEOMETRICHEDGGE.P (i.e., inferior FULI w.r.t. d).
F22 Proof of Theorem F.4
Lemma F.6. Algorithm 10 accepts a base- aase-algoritmm which satisfies Condition. F.l as an input, then, with probability at least 1 65 for all m N and a E Am.
Σ BET
(la,A, - llao) S Im -
Σ
(laa- (aa--
(24)
BET
Proof. We first consider a fixed phase m. Since the base-algorithm satisfies Condition. F.1, if the base-algorithm runs for consecutive T'm and active arm Am S A. then, with probability least 1 3 8', for all E Am
Σ (Ca,A, - ls,a) V0(6'TT -2
Σ (lea (saa
T
By setting = 62m2²² for phase m and applying a union bound over all m E N, we complete the proof.
Recall from the second bullet of Condition. F.1 that
g(0') 2 log (10)A1/8") 4g E (0,
As the above holds for 8' (0, 1), according to the definition Im = (2m))) we also have
that
220m² (amm||Al)) 1-11). Vm e N.
9m 2 log
(25)
Lemma E7. With probability at least - 8, all m E and a E Ams we have
Im
Σ lea (1- Ha) S Sv
(26)
2
SE
SETm
Proof. Consider any fixed m and Am. By applying Hoeffding's inequality with probability at least 1 1-88. 8',
Tm log (2/8')
Σ lea (1- Ha)
2
TE
TET
Choosing 8' {/(10) applying union bounds over all m E and E Ams and using Eq. (25), complete the proof.
L
31

---

Lemma F.8. With probability at least 1 - 8/5, for all m E N, we have
Σ
Σ
Σ
Ps.a (1 (aa
v 88m Tmm
(27)
BE
=ETm aEAm
Proof. Consider a fixed m. For each round in this phase, let us define
M₂ la - Es [c.AA=== =
E aeAA..
(la,aBea - Pe.a(1 - -Ha)).
By applying ixuma-inequalityy with the fact that |Mg -M-11 I 2 for all s and also using union bound over all m N, with probability at least 5/5, for all m E N
LOaA Σ E Ps.a(1 ua))
S v m7 log(20m² S V 88m T ms
BE
SETm aEA.
where the last inequality
Eq. (25), which thus completes the proof.
Definition F.9. Let & be the event in which the concentration inequalities in Lemma F.6, Lemma F.7, and Lemma hold simultaneously.
By union bound, we have the following fact.
Fact. With the definition of & in Definition F.9, & occurs with probability at least - 6. Lemma F.1.. Suppose that & occurs where & is defined Definition F.9, and then for all m E N and E Am
Σ
-laa)) s Immmm + Tm Ag.
Proof. Conditioning on E, for each m and a E Am. one can show
2
Σ mETm
l0.0 - Eea)
V Im Tim + E
(La,a (r,An)
mETm
9m T m
v Immmm
Σ
Σ
Pap p4) + / /8gmIm +
(1 Σ Ma) +
2
SET JEAm
SETm
< 9m Σ
Σ
Peslit - Ma)
SETm jEAA
< 55 Tm.
where the first inequality holds due to Lemma F.6, the second inequality uses Lemma F.7 and Lemma F.8, and the last inequality bounds b4 S 4² for all j.
Corollary F.11. Suppose that & occurs where & is defined Definition F.9, and then for all E N and a E A, we have
Σ leaa
Σ la.a S -Tm + V 22m Tm,
(28)
SET
SETm
Σ
le Σ lea < Am + v 22mmm
(29)
T
SETm
Proof. The proof is immediate by applying Lemma F.7. Lemma F.12. Suppose that & occurs where & is defined Definition F.,, and then Am for all
E N.
32

---

Proof. We prove the claimed result by induction. For the base case, the claim holds for the first phase m == as Ai = A. Suppose that a" Am. Then, we show that a* will not be eliminated at the end of phase m, thereby active for phase + 1. Then, we have
Σ
Ps.a- - Pa.kk
SETm
(Cear- losar) +x (le,a* la,k) + Σ (las Pask)
Σ
SEm..
SETm
SETm
9m + (-Tm Ax + 1/2gmm Iim
+ (5 Im ImIm + I'
13
V Im- 0.5Tm
< 7 VV Um.mi
where the first inequality uses Lemma F.10 together with A. = 0 and Corollary F.1.
Once the induction is done, we complete the proof (recall the climination rule in Algorithm 10).
Lemma F.1.. Suppose that & occurs where & is defined Definition F.9. For each arm E A with
Ao 0, it will not be in Am for all m 2 ma 1, where ma is the smallest phase such that
2ma
A
Proof. Consider fixed phase m and arm E A with A., > 0. Suppose that arm is still active in an phase m. One can show
Σ
(2n, tsck)
mEmm
Ploja - -Re,ar)
SEmm
Σ
(Crja - lsaa)
Σ
(laaa (Isa--a,a'') la,a+)+ Σ (Esar Elaa--pah -En,or)
mETm
BETm
8ETm
-1
(5v Dm Tm Tmda)= + (Tm v '29mmm
-5
V Im
2
0. - 5v ImIm.
(30)
where the first inequality holds since Lemma F.12 implies that a" E Am for all m E N, and the second inequality uses Lemma F.10 together with A.. and Corollary F.11.
Let m, be the minimum phase such that nn
x² (i.c., 2 1 S )
) which further gives that
576gm=
T m.
5766m. n 576gm, 2
A
Hence, by the definition of ma. we have Tm 576gm for all m 2 ma. which gives that T,, A. > 24 9m 24 Tm for all 2 ma. Plugging this into Eq. (30), we arrive at
A
Σ E(
0.5TT Von 7 VmnTm
which implies that arm a will not be active in all phases m 2 my according the elimination
rule.
Finally, repeat this argument for each A with 4. 0 conditioning on E.
Lemma F.14. Let m(t) be the phase in which round t lies. Then, m(t) - logz(t + for all t e N.
Proof. We prove this by contradiction. Suppose that 31 E that m(t) > log, (1 + 1). Note that can further assume m(t) 2 since one easily verify that for all such that m(t) 1.
33

---

m(t) S (t 1) must hold. Recall that in phase m(t), each active arm will be played for ma(e) times, we have
m1)-)1 2 -
288(t 1)9m(())1 t
where the third inequality bounds {(t) > log + 1) by assumption. Therefore, once a contradiction occurs, the proof is complete.
Lemma F.15. Let m(t) be the phase which round lies. Suppose that & occurs. all & N and all E A, if a E Amit)- then,
D. 4608g(6/(21og2(t 1)))
Proof. If a E Amer) is optimal, then, A, = 0 and the claim trivially holds. In what follows, we only consider arm Amtt) with A. 0. Then, can be bounded by
(()
1566g 2"
m(tt)
1152
In 2
Pm
m(t)
1152gm
2
YLm
1152gm(()
2n
4608gmm(1)
A
where the second inequality simply bounds [576g, 2n1 2 57 for all phases n. the fourth inequality holds because Lemma F.13 implies that if E Am(t)- then, m(t) S m, holds, and the last inequality uses AZ 2
Since for any fixed E (0, 1), g(6/2²) is monotonically increasing for æ 2 (recall Condition. F.I) and Lemma F.14 gives m(t) - log,(t + 1), we have
9m(t) g(f/(mm()))) S g2 1))),
which gives < completes the proof.
Conditioning on E, this argument holds for each a, which
A
Proof of Theorem F.4. Once Lemma F.12 and Lemma F.15 hold, and g(x) is polynomial in log l/x). Theorem 3.1 gives that for any fixed E (0, 1), Algorithm 10 achieves the ULI guarantee with function
to) = (1
(2 1)))
According to the first bullet of Condition. F.1, the proof is complete.
F.3 Proof Proposition F.5
In this section, we prove that ExP3.P [Auer et al., 2002b] meets Condition. F.1. In our setting, arm set [K]. and the loss l,a generated by each arm a each round assumed to be [0, bouudeed..
34

---

Algorithm 11 E
Input: Time horizon T. set [K]. confidence 8 E (0, 1).
Initialize: Va E [K], 11,a = and parameters 1/ = ( -T( (T) according to Eq. (33).
for f = 1....... do
Play an arm Ar E [K] from distribution Pt Pt.1..... Pt.k and observe loss Er,,, where
Pt.e (1 11-71
We,a 7 W₁
where
Wi
Σ
(31)
aE[K]
Update 11+1,a aia exp(-n/e for all E [K] with
28
where lea- Br.a and Bi,a = 1I (A, a).
lea le,a
(32)
Pt.a
Pt.a
The pseudocode of ExP3.P is given in Algorithm 11 and briefly review its procedure. Ahead of time, ExP3. accepts a fixed time horizon T E N arm set [K], and confidence 5 E (0, 1) as inputs. At each round E [T]. ExP3.P P pulls then observes the loss 4,A. The probability of playing an arm a at round is (1 - 7) W. + R where y >>> 0 a fixed parameter, which encourages the exploration, Wt,a is the weight of arm a, and W. = = Wr,a- After pulling the arm, the algorithm the observed reward construct the shifted IW-estimators Ee,0 according Eq. (32), and finally uses the shifted IW-estimators update the weight Wt,a for each arm.
A, Pt. from distribution pt 1 PP. k). and We.
The parameters of 76 (T), (T))))) 15(3)) are as a function T, give as
K log(10K/5)
3x(T) (T) (2') K
76 (T) min
(33)
2'
T
Let [:] []] be the conditional expectation given the history prior to round t. Lemma F.16 (Exercise 5.15 of [Lattimore and Szepesvári, 2020]), Let (X,) {x be sequence of random variables adapted to filtration {Fe)T= and let B > O such that 3X, S almost surely for all t E [T]. With probability least 6,
log(1/8)
Ex.--BIX Ex( SB)
Σ
E. [x?]
B
Corollary F.17. With probability at least - 6/5, for all a E [K],
log(5K/6)
Σ (Fr. - (1a) S B
Proof. Consider a fixed arm a. For all i, a, we have le,a E [0, 1], and thus
LG B,
c Bra
B
Eg
E,
E,
E,
(34)
1.a
pi
Piaa
Pi.a
Pt.a
Then, check Bi I 1 almost surely for all t [T]. Specifically, we Pt,a 2 4/K to show
BPr. BBaala < <B <B_ 3K
=1
Pt.a
Pt.a
7
where the last equality holds due to 3 7/K according to Eq. (33).
For the fixed a, applying Lemma F.16 with X, = -Eras have that with probability least 1 8'
T
T
laa
(+a)= =
Σ
(Pia (r,a)
29
Pr.a
1=1
35

---

T
(1/81
T
23 Pr.a
S 3
+
Pt.a
B
log L/86)
8
Choosing 8' 6/(5K) and applying union bound over all [K] yield the claimed bound.
Lemma F.18. With probability al least - 5/5, for all E [K] we have
E Ha) = Tlog (10K/8)
lia
(35)
2
Proof. Consider any fixed arm By applying Hoeffding's 's inequality with probability least 1 8',
S.a En- (a- S Tlog(2/0")
2
Choosing 8' 6/(5K) and applying union bound over all arms, we complete the proof.
Lemma F.19 (Freedman's inequality). Let {Xe)tz1 be martingale difference sequence with respect to filtration {F.)==1 and [Xel S M almost surely for all Then, for any ó (0, 1), with probubility
at least 5.
2M
Σ
X,
(2/() +
2 llog(2/8)
Σ [x
1=1
t=1
Corollary F220. With probability at least - 8/5, the following holds for all
Σ
T
Ee (1 (1-l)a))
2 2log(10K/0) K
2 2log(10K/H
Σ
T
3
Pt.a
Proof. Consider a fixed arm a. Let Mt, = -4 (1 - Ma) and {Me 1T a martingale difference
sequence. We have E. [Ma,a] = O, |Maal S K
and also
1
E2 [M3a]]
E
taa
Pr,a
(=1
where the last step holds due to Eq. (34).
By Lemma F.19 and a union bound over all with probability at least 1 - 8' for all a
(L-pa)) (n))
2 2log(2K/80) K
r
Σ (1. (1-
2 2log(2K/8))
3
Pt.a
Choosing 8' = 8/5 completes the proof.
Definition F.21. Let En be the event in which all inequalities of Corollary F.17, Lemma F.18, and
Corollary E.20 hold simultaneously. With this definition, En occurs with probability least 1 35
Lemma F.22, Let Og be an arbitrary constant such that 0g 2 1. Suppose that Eg occurs where Eo is defined in Definition F.21, and then for all E [K], we have
T
8 Pr.a
80
Σ
(Ira lea)
2K0, log(10K/8))
0 loogo(11 log(10/00) + 6
T log (10K/8)
By
3
2
(36)
2K log(10K/8)
6g log 10K/8)
Tlog (10K/8)
Σ
(r, - ((,a)
5
(37)
37
2
Pr.a
36

---

Proof. Let Bu > 0 be an arbitrary constant. By Corollary F.20, for all a E [K]
r
l - (1 - (1-no))
2 2log(10K/0)
r
Σ
+
2 2log(10K/b (0)
3
Pt.a
2log (10K/)))))) K
8o log(10K/6)
T
+
3
B
00
Pt,a
1=1
210g(10K/0) K
8o log(10K/0))
8
+
(38)
3
3
00
Pt.o
where the second inequality uses 2ab S a + for all a, Moreover, by the triangle inequality, we have
T
T
T
lea - t4,0)
Σ (e. - (1 (1- (ai-aa))
Σ (le, - (1 (1-1a))
+
210g(10K/0)
K +
(0lg(110K/0)
1
T log (10K/5)
+
3
7
8
00 1=1 Pt.e
(39)
where the last inequality applies Lemma F.18 and uses Eq. (38).
Rearranging the above gives
Σ S 0o
T
T Σ
(Bra ((uaa-
leaa)
20 log
0g log(10//0)
80
T log (10K/0)
Pr.a
3
B
[=1
Finally, if we constrain 0o 2 1, then
T1a - tea)
Σ leaa -((,)
Σ
2,3
1=1
Pi.a
2log(10K/8) K
0 log(10K/5))
T Tlog (10K/8)
T
Ble
2,
Σ
3
B
6u
Pt.a
Pi,a
i=1
200g(10 K 0 looolo0//
T log (10K/8)
T
3
B
Pt.a
where the first inequality uses Eq. (39) and the last one bounds 0g 2 1. Since this argument holds for all a E [K] conditioning on Eg, we complete the proof.
Lemma F223. The following holds for E [T].
K
K
4K2 7
72 Pt.a 1,a
Pea +
a=1
Proof. For any fixed I, show
K
K Σ
233 2
Σ
Pr.a pr.al
72
Pr.a Pra
1,a
Pr.a.
a=1
37

---

K
43
4,3
P
le +
Pr.
Pr,a
Piaa
0=1
Σ Pr.aleaa (Bra
K
48
K
4,8
+
Pc,a
Pt.a
a=1
a=1
4K2
Pr.alt,at,,a
7
4K2
Σ l1a +
7
where the first inequality uses l,, bounds Pr.act,a for each a E [K]. Since the claim deterministically holds for all t, the proof is complete.
48
<
l1,a
28
21 and Pt.a से. and the last inequality
Pt.a
Pt..
Lemma F224 The following holds for all arms k E [K].
T
K
T Eee
K T
ΣΣ
log K)
+
2n
L + 4TKB²
17
t=
1=1
a=1
1=1
Proof. Let us define
K Σ
-17 Σ laa )) 12
t
2: = 1-2
Lo = 0,
log
exp
K
a=1
8=1
With this definition, one can show for / 2 2
-17 Σイ s=1 E0,
1-
a== exp
4 0 -1
log
17
2a=1 cxp
K
17 Σ Essa
K
-1) E Ema
Y y
log
a=1 exp
exp (-nk,a)
7
>a=1 exp
K
-1) E (aaa
1 1-2 Y log
Whe W.
(-nera)
cxp
17
K
7 log
Wi. (1 - nPe, (1-1 + 17 1p
<
17
We
a=1
K
1 7 log
Wh.a
11 tt.0))
1
W
a=1
1 1-7 log
1+
71
Σ
Pria x)
(112,
Tar))
"
Pt.a
γ K
Er,a + 11
Σ
(ttaa 2) 72
K
a=1
a=1
K Pra
7 K
K
+
F, + 1)
Pt.
7h 1,07
K
==1
a=1
where the first inequality uses em < 11-2 x every a), and the second inequality follows from log(1 + 2) S x for all x > -1.
x whenever x. 2 -1 (here we repeat x = n/eea for
38

---

By summing over all t and using Lemma F.23 with 17
the above result yields
K
T
K
Peabia
p f-1
bx)
+
l,a + 1)
Σ
Σ
pr, P2
T
T
K
( 41)
21j
l, + -4TK3
As Py = and - S 1, we have for an arbitrary arm k E [K],
T
Σ
Φ1-1 ②1) -r
t=1
(1 - 7) log( K)
1 - 7 log
exp
1
1
a=1
1=1
7) log(K)
? log
exp
-17
7
log(K) (K)
T
Pek
As this argument deterministically holds for & [K], we complete the proof.
Proof of Proposition E3. The following analysis will condition on event &g which is defined in Definition F21. mentioned in Definition F.21, this event occurs with prohability at least 88. We first note that for all a
23 Pr.a
Σ Pr.ahe Σpro Pt.a
Σ
(L.a -23) le,.e -28K.
(40)
Pi.a
Recall that we choose parameters as
{ 1
K log logglo00)) (10K/0)
== == 7
min
(41)
2
T
K
In what follows, we consider T >> 4K log(10K/6)*. In this case, we have 7, E (0, 1
Then, for arbitrary arm [K], pick 0g and show
Σ (Ci.A. -(,))
T
K
Σ Piaali,a - le.k
+ 23KT
T
K
Ptaaiaa
+ +,3KT +
2 log (10g(///))
llog(10K) (10K/0)
+
Tlog (10K/8)
+ +
Σ
le,k
3
y
2
Pe,
1=1
TERM
TERM
TERM
where the equality uses Eq. (40) and the inequality applies Lemma F.22.
first apply Lemma F.24 to bound TERM as
TERM 1 < log(K) K)
K T
2m
ΣV L.a
4T
'With the choice of g(8) in Proposition F.5, this requirement always holds if EXP3. is base-algorithm in Algorithm 10.
39

---

log(K)
K + +21
(0g(10K//)
Σ
Σ
l,a +
+ 4TK33
3
a=1
log(K)
+ 127TT''+ + 2 log( 10K/6)
+ 4TK
B
3 3v KT (o0llog0(00)))) + 2K log(10K/0) + (lx(110/0))
2 6v KT L00K//)))))
where the second inequality uses Corollary F.17, the third inequality uses Σ, 4,a S K, and the last inequality uses T 2 4K 1og(10K/5) (i.e., K V
41og(10K//)) )-
KT
Then, we use K/ 1/n to bound TERM 2:
(00K/0) TERM 2 23KT +
2 log 10K/6)
log (10K/5)
31
B
2
2
T
=2 KT -2VKTlog/e (Tooog100/0)) +
KT log(10K/0) + 2 KT logglog((000) (10K/0)
3
14 $ log (10K))
T (1og(10K/0)
2
Finally, we apply Eq. (36) with 0g bound TERM
T
4 1log(10K/8)
4log(10K/5)
TERM -2
Σ
le,
+ /2TTog (10K/8)
31
B
1=1
T
2
Σ
(le,
lr,x
+
16
KT (TTlog100/0)) + 22 logllog((///
3
Putting bounds of TERM TERM 2, and TERM 3 together gives
T
3v2 2
Σ (l.A. - l,,0)) -2 -2
Σ
Z lxx)
+ (og/Kllo(100// +
V (00((1/00))
T
-2 -
Σ
(Be, (4.x)
+ +19 (TlKo(00)/)))
As this argument holds for all l E [K] conditioning on Eg, the proof is thus complete.
F4 Proof of Theorem F.2
For ExP3.P, we apply g(0) = O ( log (K/5)) given in Proposition F.5 into Theorem F.4 to get the claimed result.
As for GEOMETRICHEDGE.P we consider an improved version in [Lee et al., 2021] which uses John's exploration and shows that g(ō) d log (//).. Note that this slightly different from d logg K log, T presented in [Lee et al., 2021]. The extra log, T term is caused by Lemma 2 of [Bartlett et al., 2008], concentration inequality for martingales, but one can invoke Lemma F.19 to avoid it. By applying such a function g into Theorem F.4, we obtain the claimed result.
40

---

Algorithm 12 Adaptive barycentric spanner
Input: compact arm set A, phase m, spanner mm parameters Tm. C, and estimation 0m- Initialize: matrix A = [01,.... Od] by setting a, = ei_ R for all E [d]. and Im = [d]. vTm
Let Bm-1 R mm be a matrix whose the i-th column vector is the i-th element of set mm--- if mmm-1 < d then
Use Gaussian elimination to get Mm E (d il)xd such that Span(Bm-i) = {xr IR
Mm = 0}.
else
Remove constraints in (42), (43) related to Bm- Mm-
Query oracle to get empirical best arm o the solution of
argmax (Pm:.a) aeA
(42)
s.t. Mma = =Ū, - (B Bm- B C.
7 for i = 1,....d. do
Set = I.I-Argmax (A, A, Pm, Bm Bm-1, C, am))
8; F NULL then
10
Update a; and Im = Im (i).
for i 1.....d do
Set 8; = LI-Argmaar LI-Arrmax A, 6m, Bm 1: m. C, am))
13
s; + NULL then
14
if |det (si, A-:) 2 C (A)) or i Im then Update I'm = Imm - {i} and 0; = 8i.
15
Restart this for-loop with current parameters.
17
Return: {a.)d UiEZ vim
G
Omitted Details of Section 4
G.1
Notations
We use E Rd to denote a vector whose i-th coordinate is one and all others are zero. For any two vectors v, y E Rdd x S y indicates that x; S ys holds for each coordinate For a positive definite matrix A E pdxd the weighted 2-norm of vector x E Rd is given by ||ж|| = Vx Ar. For matrix A = [a1, ................................ aul E ddd with each a, Rd. we use A_ to denote the (d - 1)-tuple of vectors [01, a,-1, a++1, aa). For matrices A, B, use A > B to indicate that A B is positive definite. For two sets A, B, we use B to indicate the exclusion. For any scalar C R, we use Ö to denote a vector, with all coordinates equal to C.
G.2 Key Technique: Adaptive Barycentric Spanner
Algorithm description. Algorithm 12 aims identify finite set Bn, to linearly represent the (possibly infinite) active arm set Am, so that playing arms in B,, allows us to obtain an accurate estimation of (a, 0) for each E Am-
Algorithm 12 initializes a matrix A = [aj..... aa] whose column vectors are linearly independent, and 04 = es/vTm- At the beginning, the algorithm solves (42) to find an empirical best arm a (line 1-6). Then, in two for-loops (line 7-10 and line 11 11-6)), the algorithm tries to replace each column vector of with an active arm a E An by invoking the subroutine LI-Argmax in Algorithm 13, while keeping column vectors of A linearly independent. For each column i, LI-Argmax attempts to find max, det((,, 1) by solving (43) with a If max, det A_;) = 0, then,
II is equivalent to max.c.A.. (u, a) where can be found by rank- one update. See [Zhu et al., 2022] for more details.
41

---

Algorithm 13 Linear-independent argmax (LI-Argmax)
Input: compact arm set A, matrix A, estimation 0 spanner Bm-1, and phase m, parameter C, and arm C
Find a e Rd s.t. (u, 2) = det (a, A-;). Va R
Query oracle to obtain at,, the solution of
argmax (u, a) aEA
( on - a) S 22mm+1
(43)
Mma 0, Ō S 1mm11
B Bm- S C.
3 Query oracle to get a from (43) by replacing u with u.
(u,a+) = 0 and (u, (,) then
L Return: NULL.
<else
Return:
argmaxne a-) ((,
the algorithm returns NULL, since there does not exist an active arm that can maintain the linear independence. In this case, the algorithm keeps e e T/vTim in the i-th column of A. Otherwise, a; will be updated to E argmax det(a, A-:)l We use set In to record the indices of columns where the replacement fails. According the conditions in line 14, the second for-loop will be repeatedly restarted to ensure that the linear combination of elements in Bm, can represent all active arms in A. with coefficients in the range of [|C,C]. Also note that, as shown in Theorem 4.2, LI-Argmax will be oracle-efficient as it only queries the oracle O (d times.
Formally, we have the following result.
Lemma G.1. Suppose C and B,, is the output of Algorithm 12 in phase m. Then, for all m E N, Bn is C-approximate barycentric spanner of Amn
G.3 Computational Analysis
Recall from the previous subsection that Algorithm 12 and LI-Argmax needs to find the empirical best arm a,, and argmax det(o, both of which rely the access to the following optimization oracle.
Definition G.2 (Optimization oracle). Given a compact set A Rd the oracle can solve problems of the form
argmax (0,a), s.t. Ua $ Va B2
aEA
for any 31, 32 ER U U V Rexd where Tı, T2 are at most Od). If the optimal solution is not unique, the oracle returns any one of them.
We note that the constrained optimization oracles are commonly and also crucial for elimination- type approaches e.g., [Bibaut et al., 2020, Li et al., 2022]. Although this oracle is slightly powerful than that used for non-elimination based approaches [Dani al., 2008, Agarwal al., 2014], linear constrained oracle. in fact, can be implemented efficiently in many cases (e.g., common assumption that ball [Plevrakis and Hazan, 2020]) via the ellipsoid method. We refer readers (Bibaut et al., 2020, Plevrakis and Hazan, 2020] for more discussions.
With the optimization oracle in hand, our goal here is to query the oracle solve the optimization problem argmax, det A-)), which can be rewritten as follows based on Eq. (3).
argmax det(a, A s.t. (8m. on - -0) < m+
(44)
aEAm-1
Problem (44) also needs to find the empirical best arm a A natural idea to compute the empirical best arm af is to solve arg (m,, a). Notice that both finding at and solving Eq. (44)
42

---

require to deal with constraint E Am-1- However, this constrain prevents us from querying the optimization oracle due to the following reason.
Issue: a E Am-1 may cause a large (even infinite) number of constraints. One can rewrite E Am-1 as:
( -a S2 ( m 1m1
A: (r,
(45)
However, the evolution of phases blows up the number constraints (45) (e.g., when m ((exp(d))) which prevents LI-Argmax from directly querying the optimization oracle defined in Definition G.2, since it requires the number of constraints at most (dd) To address this issue, one needs to remove the dependence
Solution: enlarging active arm set Am-1. Our solution is to slightly enlarge the active arm set Am-1 in Eq. (45) so that the enlarged set can be expressed by finitel-mmany linear constraints, independent of m. Before showing the way to enlarging Am-1, we first give the following definition.
Definition G.3 (C-bounded spanner). For any given set S T& and constant C > O, - (S), defined as follows, is set that contains all possible linear combinations from S with coefficients within CC C).
Span -S. Ic. Vc, e1-c.a...
(46)
LSES
where is the coefficient associated with element 8.
We enlarge Am-1 A -pan (Bm-1), and can easily verify that this is true since Am-1 Am-1 and Lemma G.I implies that Am-1 S (B.c((BmBBm1)))
Now, it remains to show that -p.nn-c.cy(Bm. (Bm-1) constraints. The following lemma gives the desired result.
be expressed by O (d) number of linear
Lemma G.4. Suppose that [Bm-1] < d. For Mm and Bm-1 given in Algorithm 12, can be equivalently written as
{aEmR Mm Ō (B D
Hence, LI-Argmax invoke the optimization oracle in Definition G.2 solve problems of argmax (0m a) and (44) approximately by solving (42) and (43), respectively.
Computational efficiency. We mainly focus two costly steps in Algorithm 12. The first step to use Gaussian climination to obtain the matrix Mm x for some n S d. This step can be done with at most ((d)) complexity and is implemented at most once for each phase m. The other expensive step is to query the optimization oracle to construct a C-approximate barycentric spanner. The number of calls to the oracle depends
the number of times that Algorithm 12 invokes LI-Argmax subroutine. The LI-Argmax will be invoked for times the first for-loop. For the
second for-loop, LI-Argmax will be invoked for Ö (d3) times. Compared with (df) in [Awerbuch and Kleinberg, 2008], the extra d in our complexity comes from the additional restart-condition i E Im in line 14 of Algorithm 12. As |Tm| < d and In is non-increasing when update, this condition will be met for most times.
G.4 Proof of Lemma G.4
Lemma G.5 (Restatement Lemma G.4). Suppose that [mm-1l < For Mn and Bm given in Algorithm 12, the set |p (Bm-1) Hm where
B Hm. {a TRd Mn = 0, - c 1B B
c
(47)
Proof. For this proof, we show that E Span (Bm-)) (Bm-1) ) if and only if a E Hm.
We first show that if E Sp,n (Bm-1), then a E Hm. As matrix Mm defined by Span(Bm-1) far E Rd Mmx 0}. E c.an Span(Bm--) gives
is
43

---

that Mm 0. Recall that Bm-1 Rd il is a matrix whose the i-th column is the i-th element of set -1 1 and rank (m = 1 because mm is linearly independent. Therefore, for each E - 11, there exists a unique vector Ia E RRlBm-al such that Bm-1 = a and the value of each coordinate of za is no larger than C. As Bm-1 linearly independent, Bm-1 1
1 Bm-1)) Bm- As a result, if is full-column rank matrix, which gives that Ta -1 B BT- a S C, which concludes the proof of a E Span (Bm-1)) (Bm-1), then, - (B m- Bm-1) this argument.
Then, we show that if a E Hm. then, a E Span (.cn--).)(BBm-i) If Mma Õ. then, we have a E Span(Bm-1) due to the definition of Mm. As fank(Bm-i) = 1Bm-tle for each a E Span(Bm- 1), there exists a unique vector za E RB such that Bm-1Wa = a, which gives that za = (m-1)mm-1) -1 B B Thus, - < (B (m each coordinate of ra no larger than C. As consequence, if a E Hm, then, a E Span (Bm-1).
B a S C requires
Combining the above analysis, we complete the proof.
G.5 Proof of Lemma G.1
In this section, we aim to show that Bm, is C-approximate barycentric spanner of Am To this end, we first show that Bm is a C-approximate barycentric spanner of Sm which is defined below and Am S Sm results in the desired claim. In fact, throughout our analysis, we stick with Sm rather than Am.
Sm = {a {aE E A: (8m. am - -a) 2--m+ a [p.c (Bm-1)). Vm 2 2. (48)
S A,
Moreover, according Lemma G.4, for all m 2 2, S. can also be equivalently rewritten as:
Sm = aa A: (Dm: am - -a) S 2 m+1 Mm = 0, -C S (BTT11 Bm-1) B c}
Lemma G.6. Let > 1 and Bm is in Algorithm For all m E N. Bm is a C-approximate barycentric spanner Sm-
Proof. For all m E N. we define B', Bm U (ViEIm (ine We further define set S',, Sm U (UIEZ.. ) and matrix B', = [b1, ,b,....,bul. bul where b, is the i-th element of B By these definitions, b, = for all i E Im. The proof consists of three steps, and we first proceed step 1.
Step 1: each solution of (43) is in S.. According the optimization problem (43), for each phase m, the solution is drawn from (see Eq. (47) for definition of Hm)
Hm n {aE A: (0m, oi - S $2-m+1}
-a)
( ( (0m. am - a) 52 2-
Smn
where the first equality holds due to Lemma G.4 and the last equality holds due to Eq. (48).
Step 2: B',, is C-approximate barycentric spanner of S The proof idea of this step follows a similar arguments of Proposition 2.2 and Proposition 2.5 in [Awerbuch and Kleinberg, 2008]. In Algorithm 12, each update for matrix A E Rdd always maintains det (A)) > and thus B spans Rdd As S', C Rdd every element a E S, can be linearly represented by = Ed= wib, for some coefficients {wi J and then we have
|det (a, (B,,) det Σ w.bi, (B'm)
Σ we det (b;, (Bi)) |ws| (B't(((,)))
10 have the uniqueness because one can treat Bm- 180 a an overdetermined linear system in terms of Lo I (8m-il and we have rank Bm)) Bm-1]. 1|.
44

---

Step shows that each solution of (43) is in Sm, and thus Bn S Sm, which further implies By S S. Recall that before the termination, the algorithm will sean each column vector of matrix A to ensure that no more replacement can be made. Hence, once Algorithm 12 terminates, we have that Vi E [d], SUP&ES, (a, (Bm))=) & C' (det(B',,)) B,,,), and then Vi E [d], | S C, which implies that B is C-approximate barycentric spanner S...
Step 3: B,, is C-approximate barycentric spanner of Sm. Here, we show that every a E Sm. can be written as a linear combination of elements only in B,, with coefficients in [-C, CJ. Notice that we only need to consider E S.. Bm, since if a E Bm, then, one can find trivial linear combination by itself (recall that we assume > 1). Then, we prove the desired claim for all Sm Bm such that it cannot be
E S. - Bm by contradiction. Suppose that there exists an arm linearly represented only by elements in Bn with coefficients in [-C, Cj. As Sm C S,, and B is C-approximate barycentric spanner of St, (shown in step 2), there must exist coefficients {d.). to linearly represent as:
a
Σ debs, Vi di E--C, and Bi E Im such that dj o 1=1
(49)
As for Eq. (49), we assume without loss of generality that the coefficient index j E Im satisfies d * O. Since & Bm the second for-loop in Algorithm 12 ensures that be represented as linear combination of (b: and it would be put in B,, otherwise (recall that Algorithm 12 terminates the second for-loop, when it scans every column vector of A and makes no replacement). Hence, there exist coefficients (c hE(dies such that
Σ
cabi, W
(50)
iEld
Bridging Eq. (49) and Eq. (50), we have
d,br = Σ - -c) - bj
Σ (c: - (F
(c-dd)bb bi)
dj
which implies that the j-th element of B',.. i.e., by can be expressed as a linear combination of other elements of B'n. i.e., {b: Jo4j This leads contradiction because Algorithm 12 ensures B to be linearly independent. As consequence, every element of a E Sm can be written as linear combination of elements only in Bn with coefficients [-C, CJ. which completes the proof.
Proof of Lemma G.I. Recall from Eq. (3) that Am is defined as
A1 A. Am = {o Am-1 (Pme on - -a) s 2 m-2m--1)
Vm 2
Since Lemma G.6 gives that Bm a C-approximate barycentric spanner of Sm- it suffices show that Am C Sm to prove the claimed result. We prove this by induction. For the base case m 1, A C Sj trivially holds based on definitions. Suppose that Am Sm holds for m 2 2. For m + 1, Am+1 is defined as:
{a faE Am (0m+1.0mn-1- - 52)s22 $2-m
Am+1 =
Since Lemma G.6, gives that Bm is a C-approximate barycentric spanner of Sn, and the inductive hypothesis gives Am C Sm, we have An C -p,an which implies that
Am+1+
{ a E Am : (0m-1.0
-a) 2 m
A:
(Bmtz,
a < 2- a E Am
C { Aa A: (Bm+1,
2 m E Span (Bm))
Smm+1
Once the induction is done, the proof is complete.
45

---

G.6 Proof of Theorem 4.2: Regret Analysis
Before proving Theorem 4.2, we first present technical concept and lemmas. We first formally introduce the concept of C-approximate optimal design, both of which help us to prove a stronger result of Eq. (4), paving the way prove the main theorem. Let ((A) be the set of all Radon probability measures over set A.
Definition G.7 (C-approximate optimal design), Suppose that A R a finite and compact set. A distribution π E A(A) is called a C-approximate optimal design with an approximation factor
C C21,
sup |lal (m:A)) C.dd, where ((T;A) = Σ x(a)aa" aEA
aEA
Then, the following lemma shows that if one computes uniform design for set B, barycentric spanner for another set A, then, playing arms in B can guarantee accurate estimations over A. Lemma G.8 (Lemma 2 of [Zhu et al., 2022]). Suppose that A C IR is compact set that spans Rd. If B = [b,, .bal is a C-approximate barycentric spanner for A, then, π : B + 1 (C² d) appprxximeeeee optimal design, which guarantees
sup ||al -². where V(T: =
aEA
We then present the following lemma which provides stronger result than that of Eq. (4). More specifically, we are supposed to show that ||a|ly.. S C'//TTm. holds for all Am in Eq. (4), but we will show that this holds for all E Sm. This is stronger since Am S Sm for all m E N.
Lemma G.9. For Sm defined in Eq. (48) and Bm returned by Algorithm 12, setting T (a) 3 for each a E Bm and playing each arm a E Bm for nom (a) [T Tm
Tm [a)] times ensure that
C.
Va E Smi
||all== S VTm
(51)
Proof. For all m E N, we define B', = Bm U (UiET.m vim
c
and
(TTi B'n)
Σ (a)aaa Σ
Tmaa)aa
Tm (m)aa
W. 23
aEBn
aEB Bm
With this definition and also the definition Fu (a)
[a)]
have
Vm = I+ Σ Rem
(a)(a)a"
BEBm..
I + Ti
Tm (a)aa
B
Tm (Tmi B'm):
(52)
where the last step follows from the fact that
I Tm
C e
Tm Σ Tm
Ci VTm
e;
c
Tm
Σ
Ten (a)aaa
T
VT
VT
VTm
VEIm
BEB'
Bmn
Since By spans Rdd and By, C Span (B',). set Span (Bm) also spans Rdd. Lemma G.8 gives that
Ya E -p (Bm.), (v( -1.)) C..
Thus, one can use Eq. (52) to show that for all
(amm C-d
Va E Span (B,)). |ally
Vim
Vim
As B,, is C-approximate barycentric spanner of Sm, we have Sm C Span (Bm) Span:-.cc (B,m), the proof is thus complete.
S
0
46

---

The following analysis will condition on the nice event &, defined as:
= = Vm E N:
( (a 9m+1
0) s 2 2- for all a E Sm
(53)
where Sm is defined in Eq. (48). Lemma G.10. We have P(E) 2
Proof. One can show that
(a,8m+111 -0) - |ally... | 0m-1 - V.n
C.
0m++ 8
Va E Sm:
(54)
vTm
where the first inequality uses
inequality and the second inequality uses Lemma G.9. Notice that the above inequality holds for all m E N. Finally, Theorem 20.5 of [Lattimore and Szepesvári, 2020] shows that with probability least 1 5, for all m E
0m+1 - 8 ll Vin
s 2 log (og((1)) + d (Tl)
(55)
Combining Eq. (55) and Eq. (54), we have that Va E Sm.
<a 0m+1mm+-- 666
1og(118) + d m
s /
Tm
$
1
2-
log(1/8) log (256C4
T-m
d3
log
494
8C
log 444m
1
4 4log(4C) + log
4
log
4m
2-m
8C
log
1 mm
1
8C 2og 4m gm 2
80
log 4m
16C log [d
2
8C
log
43
2 -2-m-1 m-
where the third inequality uses 4 (or( < 8r for all x E Ry0, the fourth inequality follows from + b 2ab whenever a, > 1 (here 8C and b 4m and the last inequality holds due to > 1.
Hence, the proof is complete.
Lemma G.11. Suppose occurs where & is in Eq. (53). For all m E M, a" E Sm holds where Sm is defined in Eq. (48).
Proof. We prove this by induction. For the base case m = 1, the claim holds trivially. Suppose that holds for phase m (i.e., S.)) and then we aim show at E Sm+1. For all a E Sm. one can show
s (0,a") - (0, < (8m+1.a*) (8m+11 + +2x 2 1 (0m+z, a" -a) + +--
where the second inequality follows from the definition of & (see Eq. (53)) and a* E Sm by inductive hypothesis. Then, we have
(0m++1a' aai+1) + 0.
The inductive hypothesis gives a* E Sm, and thus
a" Span c., n.A
(56)
47

---

since Lemma G.6 gives that Bm is C-approximate barycentric spanner of Sm. Combining (0m+1,a a* am+1/ + 2 2 0 and Eq. (56), we have a" E Sm+1 according to definition of Sn in Eq. (48). Once the induction is done, the proof is complete.
Lemma G.12. Suppose that & occurs where is in Eq. (53). For each arm a E A with A > 0, it will not be in Sm. for all phases m Z ma where ma is the smallest phase such that A 2- ma
Proof. Consider an arbitrary arm a E A with A. > O. Let my be the smallest phase such that An < 2- (m_ ().. Then, we will show that arm will be not in S, for all ma-
Ae > >2- (i.e.. 2 Suppose that Sm, (if not, it does not impact the claim). One can show that
(0 +1, ama+1 a)) -2 -2mm..
(0ma+1,b b-
--a) aa) 2
sup DESma
0 mg 1, -a) -2 -2-ma
(0, a" a) -2 2
Aa
A 2 x
2
0,
where the first inequality uses Lemma G.11 that a" E Sm for all m E N. the second inequality follows from the definition of & (see Eq. (53)), and the last inequality holds due to the choice of ma-
According to the definition of Sm. in Eq. (48), arm a will not be in Sn for all m 2 m. + as long as E occurs.
Lemma G.13. Let ml(1) be the phase in which round I lies. Then, m(l) S logg + 1) for all i E N.
Proof. We prove this by contradiction. Suppose that 31 E N that ml() > logz (1 + 1). Note that we can further assume m(l) 2 since one can easily verify that for all such that m(() = 1, m(t) < logz(t + 1) must hold. Recall that in phase mtt), each active arm will be played for ma() times, we have
Σ aEBm(()1
(a)
m1)))11
Tm(()- 256C
(m log (o-1d2gm(t))11) > 640 10044.((1+ 1) (48-1 t
d²
d
where the third inequality bounds E(t) in the logarithmic term by E(t) 2 2 and bound the other
((t) ltgz(t + 1) by assumption. Therefore, once contradiction occurs, the proof complete. O
Lemma G.14. Let m() be the phase in which round lies. Suppose that E occurs where E is in Eq. (53) and Algorithum computes a O-approximate barycentric spanner with C > For all e N
and all a E A, if E Smit). then,
64 x 512(' log d'a(t+112
A S
34
Proof. If a E Sm(t) is optimal, then, A_ = 0 and the claim trivially holds. In what follows, we
only consider arm Sm(t) with A, 0. Consider an arbitrary round e N and an arbitrary arm E Smit)- Then, i can be bounded by
mft
[T)
s=1
48

---

ml(t)
2
(a)TT
s=
a
m(())
d
4
5120
log
(())
& $5120 log
(0)
dd
ma
5 512C 1lo log
64 x 5120 log
(4m(())
34
64 x 512C* d log
d"1tnoa(t++1)
8
3
64 x 512C' d log
d2((++1)
3
where the second inequality holds because (a)
for all N and all Bg thereby T, (a)T, 2 1, which gives [T, (a)T,] S 2n, (a) the inequality (a) bounds m(t) I m, where m. is defined in Lemma G.12, the inequality (b) uses As < 2- to bound ma I loga (4/a.), and
the inequality (c) follows from Lemma G.13 that m(t) (1 11.
Conditioning on E, this argument holds for each t, a, which completes the proof.
Proof of Theorem 4.2. Once Lemma G.11 and Lemma G.14 hold, Theorem 3.1 gives that for any fixed E (0, Algorithm 10 achieves the ULI guarantee with a function (omitting C' as it is constant)
(V (dt/8)
F6) 0
Therefore, the proof complete.
G.7 Proof of Theorem 4.2: Computational Analysis
As the second for-loop restarts repeatedly, and first present the following lemma to bound the number of times that it restarts.
Lemma G.15, Under the same setting of Lemma G.I, Algorithum 12 outputs C-barycentric spanner by restarting the second for-loop for O (d2
times.
Proof. According to [Awerbuch and Kleinberg, 2008, Lemma 2.6), if I,,, never changes after entering the second for-loop, then, the second for-loop restarts for at most (Ol (oge)d) times, and then the algorithm terminates. In Algorithm 12, if I,,. changes, the second for-loop restarts. As set Im is always non-increasing, it suffices to consider the worst case (Im changes at most (dd) times). Hence, the second for-loop restarts most ( (og times.
Now, we are ready to show the computational complexity.
From Lemma G.15, Algorithm 12 restarts the second for-loop at most (d log)-()) times. For each run of second for-loop, the optimization oracle invoked at most d times. Thus, the number of calls to the oracle is at most (dd (d).. Apart from the second for-loop, the first for- invokes the oracle times and computing the empirical best arm at requires once call the oracle. Combining all together, obtain the claimed bound.
49

---

H
Omitted Details of Section
H.1 Proof of Theorem 5.1
The proof of main theorem conditions on nice event & in which some high-probability bounds hold simultaneously. We defer the formal definition of to Appendix H.2.
The key to conducting policy climination is to ensure that the estimated value functions will be closer the true value functions as phases evolve. The following proposition gives us the desired result.
Proposition H.1. Suppose that & occurs. For all m E N and क E [m we have
V m
Ea (s))) S 2
With the above result hand, treat each policy Appendix D.2 (counterparts are Lemma D.7, Lemma D.8, and Lemma D.9) to get the following three lemmas.
and repeat the same arguments in
Lemma H.2. Suppose that occurs. For each m E N, T E 1mm holds.
Lemma H.3. Suppose that & occurs. For each policy π with A > 0. it will not be in IIm for all
phases m 2 m, + where my is the smallest phase such that Ar
mn. 2-m
2
Lemma H.4. Let m(l) be the phase that round & lies in. Then, ml() S (1 1) all / E N.
The next lemma shows that a policy is not eliminated, then, the policy gap is order (2))
Lemma H.5. Let m(t) be the phase in which episode/round t lies. Suppose that & occurs. For all t N and all II, if a E Im then
S3AH' log² (tSAH/0)
A
t
Proof. If π E Llm(e) is optimal, then, As = 0 and the claim trivially holds. In what follows, we only consider policy lm with A > From Lemma H.3, if policy æ E Um(()) is with > then, ml() my where my defined in Lemma H.3. Thus, the total number of episodes/rounds that such policy x is active is at most
T
m(t)
< 2c, 52 AH
2s log (2025222s 5² AH |an
| 1/8)
m(t)
$ 20, 22 log? (2cz log t(t + 5) A AH //0)
Σ
225
s=1
52 (LSAH Tar1
0
A
AHH log 2 (tS (HSAH/5)
A2
where the second inequality holds due to s S mt) S loga + 1), and the last step uses the fact that aan SH Rearranging the above, complete the proof.
Now, Theorem 5.1 is immediate if we treat each policy an arm and invokes Theorem 3.
50

---

H.2 Construction of Nice Event
We extend the definitions of value function and action value functions seward-dependen ones.
H
a,) E
The (swr, ane) 88 8, UN
(57)
(s, E Th (sh,, ax)) S/ 8,
Next, we start to construct high-probability event. first construct an event that high-probabilityy bounds occur for single phase (i.e., single execution of Algorithm 4), and then extend it to the case in which those bounds simultaneously hold for all phases.
Lemma H.6. Suppose that Algorithm 4 is executed with input (6, II, T) where II S aan. With probability at least - 8/5, for all (1, h, n, 8, a) E (T) x [H] x x S x A:
log 10H SA au (T/8) 2 max (s, a),
( - P.NN (s, a)
S H
Proof. For (s, a) has been visited, apply Hoeffding's ss inequality and union bounds to complete the proof. For those (s, a) that has not been visited yet, the claim trivially holds true.
Lemma H.7. Suppose that Algorithm 4 is executed with input (6, II, T) where S Nan With probability at least - 8/5. for all (h, s,a, π., E [H] x S A x II x [T].
[PP.P Ph) (s, a) (s,
Proof. For those (s,a) that has not been visited yet, the claim trivially holds true. For (s,a) has been visited, by Bernstein's 's inequality, with probability at least - -5,
(Pan Pw PW) Gh+1 (s. =
Σ s'ES
2P(s"|s, a) log(2/8))
2log(2/8))
Vi
(s,
(N,,,.(s,))
2s(8' a) log(2/8")
2HSlog(220)
Σ H
Ne,(8,a)
(s,
S'SS
25 1ogo((2/8))
(HSlog(2/8))
where the last inequality uses the (s,a)
3N,
inequality. By taking a union bound, choosing a proper 8', and using the definition of br, (s, a), complete the proof.
In the following high-probability bounds, we again assume that Algorithm 4 is executed with input (6, II, T) where IT Tan- By Azuma-Hooffdinng" inequality and union bounds, with probability least 1 - 8/5, for all e II.
T
Exj mep
Σ (VT(sibeeHH))
(s b.HH) + 11 8T (og(5)]lan//5)
(58)
For shorthand, we denote
C. Pr. VT. (Se,h, ar,n))
Vm tihti (st,))
(59)
By Azuma-Hoeffding' inequality and union bounds, with probability at least 1 - 8/5, for all (t, E [T] x [H).
Σ Σ Euu s /8Toogg55T
(60)
51

---

where > 0 is some absolute constant.
Again, by the fact that |ma 2 [T] and Aruma-Hoefiding's inequality and union bounds, with probability at least 1 6m 15, for all x E II,
-M--Brrw [VFa(s)]] I H /HHSSTTo (10[[[a1l/6m))
(61)
Definition H.8 (definition of E, single phase). Suppose that Algorithm 4 is executed with input (6', 11, T) where 11 Matt. Let & be the event that all high probability bounds in Eq. (58), Eg. (60), and Eq. (61) hold simultaneously.
Taking union bound over those gigh--robbbiltty bounds, have
( (8)21-8'
(62)
Definition H.9 (definition of E). Let & be the event that when running Algorithm 3, all high probability bounds in Eq. (58), Eq. (60), and Eq. (61) hold for all phases
N simultaneously.
Recall that Algorithm 3 runs Algorithm 4 in phases with input (8m- Im Tm) where 6m. 6/(2m²) and Vm E N. Imm & aaa holds. By a union bound over all m E N. IP (E) 2 1 - 8.
H.3 Supporting Lemmas
Recall the reward-dependent value function given in Eq. (57), and we give the following lemmas. Lemma H.10. Suppose that Algorithum is executed with input (8', II, T) where C Ian.. and suppose & occurs. For all (x,t, h, s) II x [T] x Н S, VE (s. b H) s Vi,(s) holds.
Proof. Conditioning on ε, one can use Lemma H.6 and follow the same idea of Lemma 18 in [Azar et al., 2017] to complete the proof.
Lemma H.11. Suppose that Algorithm 4 is executed with input (8, II, where II S aan. and suppose E occurs. For all policy π II, the following holds.
Vπ II,
E Esiop
(51 VI V[ Enio [VT
Proof. One can show the following:
V [7, (81) (71
EsrnH
(81, (s1, (f(rm,)())))
< Esro
(rr. -P15((0,
Exro
(r.1(91,11s)) + [P, (()))
(s1)) [PP Va]s,,,
E P (), (s))) + (r,2))2) V3(22)
< Enjoy (T),
where the second inequality follows from Lemma H.7.
Since those concentration bounds are also two-sided, the other side of desired claim can be similarly proved. Note that for the other side, one only need consider (7,1 a) < for all (s, a), and otherwise, the difference is negative, which implies that the claim trivially holds.
Lemma H.12. Suppose that Algorithm is executed with inpul (8', II, where C Mais and suppose & occurs. For &x defined in Eq. (59), we have
1 H
Σ (s.1))
ELA +
2
br.1 (s111,
(63)
52

---

Proof. Conditioning on E, we have
T
(81,1)
[P
2.2 (8t,1, a111) + (51( + (st,1 (x1))
M++ MM
(1 [1) b,, (411)
1 1)
[F a.1+
2
b (111).1.)1))
H
1
L.11 + (8.2)) +
2
b (1,,1
H
T #-1
T
H
Σ
Sth +
2
Σ
by (St, ac.));
H
where the first inequality holds due to Lemma H.7.
Then, turn to bound two terms in Eq. (63). Note that Eq. (60) already gives the bound of the first term, and thus we only need to bound the second term. Before that, we first present an auxiliary lemma. The proof of this lemma can be found in [Jin et al., 2020, Lemma 10]
Lemma H.13. Suppose that Algorithm 4 is executed with input (8', II,T) where II C al... For all [H). the followings hold.
T
an a max Ne,(,, = OSA
Σ
(s.a) t=1
T I( ar (s, = = (VSAT). Vmx (1,,),)
Σ
(x.4)
With the above lemma in hand, one can show:
den (Se,n, ac,1))
2S log max (1, ( (s,,),) + Nr ar,))
2HS log
I((8),,) (n,n) -s, ())
SH (t,1) (8, a)) log
H HV2Slog
/max Ne, (Anas,,,
3 max/11 (80,,
(S.A)
o SHH Aog + H Alog(T) logı).
where the last step holds due to Lemma H.13. Therefore, have
(()()))) 0 ( 1=1
V VARP/ATlo log + HS² Algg(T)) log.))
(64)
H.4 Proof of Proposition H.1
We first consider single execution of Algorithm 4 with input (6. II, T) where IT C Tan- With the above supporting results, we are ready to prove the claimed result. The following proof will
53

---

condition on event &. First, one can show that for all π E II:
8 Es mu (s1)]
VT Eg mu
(81())) + Eay (s1)
Esya [V*
s H / 8T (100l1))la11)//// 10)) + Barr [2 (81)
Berc [V
(By Eq. (61))
Then, we turn bound the second term. Recall the reward dependent value function defined in Eq. (57), and we have
Eei mp (o), (s1(s))
- Es mu
(V1 br)l
(By Lemma H.11)
= HBB
T
H
E rap
Σ
(s1,
(br S be, vt)
T
[=1
From Eq. (58), we have
T
Esy
Σ
beHH)
<
(8,,, 1041,,,//1 b/HH) + ci H / Tlg
1=1
Ta 6,1 (86.)) + V
(By Lemma H.10)
(s..)) + 01 T
(Te E argmax VI (s..))
Combining the above with Eq. (64), we arrive at
T
=o -
Alog
A &
Egg ExycH mo
Σ VT
T
T
Now, we consider fixed phase m where the input of Algorithm 4 is (6m, Im, Tm)) There always exist two absolute constants C12 >> 0 for I'm 2 2m S2 AH log" (c22 2m AH 881) such that
- 2 m
Eg my (VT((s))
m
2
As conditioning on event E, the above holds for all m N. Thus, the proof is complete.
54

---

I Limitations
One limitation that the regret bound implied by the ULI guarantee for linear bandits with infinitely- many arms is suboptimal, i.e., Odd--5 /T) compared with lower bound (dv/T) but note that this problem is long-standing open. This is discussed below Theorem 4.2. We also mention the limitation of Algorithm (below Theorem 5.1) that is computational inefficient and the regret bound implied by ULI guarantee is also suboptimal.
Broader Impacts
This paper proposes a new metric for online RI,, called uniform last-iterate, which could be helpful for high-stacks applications, since near-optimal result under our metric ensures both good cumulative and instantancous results.
55

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We itemize two main questions in introduction section and also itemize contributions on how to approach and resolve those issues in our paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Please refer Appendix I.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
56

---

All assumptions can be found in Section 2 and all proofs can be found in appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
This paper is theoretically oriented and does not conduct any experiment.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
57

---

Answer:
[NA]
Justification:
This paper is theoretically oriented and does not conduct any experiment.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/ Belliiicguidess/Cdeeee
weriiisssonpoiiiii oolicylyyy)) cc) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //iips.co.. wttpccccpppcccceee.cc..cccccclct /ttpi///ggiiiee/eeeeuuubiiiiii /Codeeeooiissseeeeeee wwwssssoiiyyyyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper is theoretically oriented and does not conduct any experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper is theoretically oriented and does not conduct any experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
58

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper is theoretically oriented and does not conduct any experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https : http///eerrpp.eeeee cc
Answer: [Yes]
Justification:
We have reviewed NeurlPS Code of Ethics and commit it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Please refer Appendix J.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
59

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi sepprssiithood thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
60

---

Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This the paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
61


Reviews:
[{"review_id": "5dcLJMxozn", "reviewer": "Reviewer_HueZ", "summary": "This paper introduces a new form of guarantee for MAB and RL algorithms named \"Uniform Last Iterate (ULI)\". Just like the uniform PAC guarantee introduced in Dann Lattimore and Brunskill (2017), it unifies the traditional sublinear-regret (with optimal rates) and PAC guarantees for such algorithms. However, unlike uniform-PAC, ULI guarantees are also shown to encapsulate the instantaneous perfromance of MAB/RL algorithms, ensuring that, with high probability, a very suboptimal arm/action is _never_ taken after large enough $t$ (with probability $\\geq 1 - \\delta$, the maximum suboptimality after round $t$ is bounded by a decreasing function of $t$).\n\n* They show that ULI is strictly stronger than uniform PAC (and hence also unifies regret and PAC).\n* They show that successive elimination (SE) and phased elimination (PE) algorithms achieve ULI for finite-arm and linear bandits (in the case of PE).\n* They show that well-known optimistic algorithms for stochastic bandits do not achieve ULI, and that even some modifications (lil'UCB) do not achieve near-optimal-rate ULI.\n* They show that a phased-meta algorithm used with well-known adversarial bandit algorithms such as EXP3.P can achieve ULI (Appendix F).\n* They show that phased-policy-elimination with a modified version of UCB-VI can achieve ULI for tabular episodic MDPs.\n* All the ULI guarantees are near-optimal (the ULI bound decays as $t^{-1/2}$) which leads to near optimal regret bounds $\\tilde{O}(\\sqrt{T})$,", "questions": "* Can you comment on where the UBEV algorithm of (Dann et al 2017) with the uniform PAC guarantee fails w.r.t the ULI guarantee (ULI even if not with near optimal rates)?", "limitations": "The limitations have been addressed adequately by the authors. No negative social impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The ULI guarantee is a novel and interesting extension of existing work which unifies a number of known-guarantees applied to online bandit/RL algorithms (regret, PAC, uniform PAC).\n* ULI encapsulates instantaneous performance in a way that existing guarantees do not, which is of interest in safety-critical applications.\n* The ULI guarantee is very _applicable_ in the sense that existing well-known algorithms achieve it with mild conditions/modifications, and the authors successfully demonstrate this in the paper.", "weaknesses": "* The regret bounds obtained by ULI have the optimal dependency on $T$ (i.e. $\\sqrt{T}$) but suboptimal dependence on other parameters (such as $d$ for linear bandits).\n* The algorithm for episodic tabular RL is computationally inefficient (both limitations are acknowledged and drawn attention to by the authors in the paper, and are fairly minor considering the contribution).\n* There is no experimental evaluation for the modified algorithms compared to the baseline algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. Below we address your concern. \n\n---\n**Q:** Can you comment on where the UBEV algorithm of (Dann et al 2017) with the uniform PAC guarantee fails w.r.t the ULI guarantee (ULI even if not with near optimal rates)?\n\n**A:** In fact, the UBEV algorithm is the RL version of lil’UCB, as both utilize the law of the iterated logarithm (LIL) to avoid the $\\log t$ term in the bonus. When reducing UBEV to the MAB setting, it operates in a similar manner to lil’UCB. From Theorem 3.3, we know that lil’UCB (and thus UBEV) cannot be near-optimal ULI. However, it remains unclear whether lil’UCB (and UBEV) is ULI, as discussed in the text below Theorem 3.3.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yCRWFyjJlf", "reviewer": "Reviewer_vbbn", "summary": "This paper introduces a stronger metric, uniform last-iterate (ULI) guarantee. \n\nThe authors demonstrate that a near-optimal ULI guarantee directly implies near-optimal cumulative performance across traditional metrics such as regret and PAC-bounds, but not the other way around. \n\nThe authors first provide two results for bandit problems with finite arms, showing that some algorithms can attain near-optimal ULI guarantees. \n\nThey also provide a negative result, indicating that optimistic algorithms cannot achieve a near-optimal ULI guarantee. \n\nFinally, they propose other interesting algorithms that achieve a near-optimal ULI guarantee for linear bandits with infinitely many arms (given access to an optimization oracle) and the online reinforcement learning setting.", "questions": "- What about the instance-dependent bound? UCB is strong since it also guarantees good instance-dependent bound. I guess most of the results in this paper are written in a minimax manner. It would be great if authors could provide the followings\n    - Result of instance-dependent regret, such as the counterpart of Thm 2.6\n    - Example of algorithms with optimal instance-dependent regret and satisfying ULI condition. If this is difficult, it would be great if authors could make an instance-dependent analysis for the algorithms in section 3.1. \n\n- I want to ask for additional theorems about the impossibility of optimism-based algorithms, see the weakness section above. \n\n- Necessity of the ULI: check the weakness section above. I somewhat feel ULI as 'unnecessarily strict' criterion.", "limitations": "The authors state their limitation in their paper. \n\nNo negative societal impact", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Interesting new metric: Uniform last-iterate, which is a stricter version of uniform-PAC. \n\n- Interesting inclusion result: \n    - ULI includes uniform-PAC but the converse is not true. \n    - Also, any optimism-based algorithms cannot satisfy the ULI standard. \n    - ULI algorithms can still achieve tight minimax regret for many bandit instances (Section 3.1)", "weaknesses": "- Necessity of the ULI itself: basically this notation forces the learner to choose less explorative options. However, in my intuition, the only way to do less exploration later is to choose more sub-optimal arms often at the early stage where ULI is less restrictive. In your patient example in the Introduction section, does it make any major ethical difference?\n    - As somewhat expected, an algorithm with ULI standard was not able to achieve the minimax optimal regret on the general linear bandit (with infinitely many arms) since the criterion prevents the algorithm from exploring, while in linear bandit it is important to explore each direction enough. Still, admitting the weakness shows honesty in their report. \n\n- Clarity: As a first reader, it is not easy for me to understand why the $\\log (t)$ term in the optimism-based algorithms guarantees that they fail the ULI standard. They said the log term makes the algorithm choose sub-optimal arms infinitely often, but does that directly induce that it does not satisfy the ULI condition? It would be great if authors could add a theorem for it, besides the lil'UCB result. \n\n- They cannot achieve anytime sublinear expected regret, since their result is stricter than uniform-PAC.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. Below we address your concerns. \n\n---\n**Q1:** Necessity of the ULI itself. In your patient example in the Introduction section, does it make any major ethical difference?\n\n**A1:** Indeed, the ULI forces the algorithm to explore more in the beginning. Hence, it implies the necessity in safety-critical examples. Regarding the ethical difference: early-phase clinical trials could be conducted on animals, where ethical concerns are less stringent compared to later phases involving humans. Therefore, ULI is a desirable metric for safety-critical applications where playing a bad arm/policy at a late stage could lead to catastrophic consequences.\n\n---\n**Q2:** Why the $\\log t$ term in the optimism-based algorithms guarantees that they fail the ULI standard? Add additional theorems about the impossibility of optimism-based algorithms.\n\n**A2:** At a high-level, $\\log t$ is increasing with time and forces the algorithm to play a bad arm indefinitely when $t$ evolves.\nWe provide the formal proof in the following and will include it in our final version:\n\n\n*Proof.* We prove the claim by contradiction. Consider a $K$-armed bandit instance with at least one suboptimal arm, and let $\\Delta>0$ be the minimum arm gap. Suppose there exists an optimism-based algorithm with $\\log t$ in bonus term that can achieve the ULI guarantee in this setting. Then, for some fixed $\\delta \\in (0,1)$, with probability $\\geq 1-\\delta$, for all $t \\in \\mathbb{N}$, $\\Delta_t \\leq F_{ULI}(\\delta,t)$. Based on Definition 2.5, we have $\\lim_{t\\to \\infty}F_{ULI}(\\delta,t)=0$ and $F_{ULI}(\\delta,t)$ is monotonically decreasing w.r.t. $t$ after a threshold. Thus, $\\exists t_0 \\in \\mathbb{N}$ such that $F_{ULI}(\\delta,t) <\\Delta$ for all $t \\geq t_0$. In other words, the algorithm cannot play any suboptimal arm after $t_0$-th round. Recall that the bonus term is $\\sqrt{\\log t/N_a(t)}$ where $N_a(t)$ is the number of plays of arm $a$ before round $t$. For any suboptimal arm $a$, $N_a(t)$ should not increase after $t_0$-th round, but $\\log t$ keeps increasing. This leads the bonus of arm $a$ goes to infinity, which will incur a play of arm $a$ at a round after $t_0$. This makes a contradiction.\n\n---\n**Q3:** Result of instance-dependent regret, such as the counterpart of Thm 2.6.\n\n**A3:** All ULI results can be directly translated into instance-dependent regret bounds by invoking Theorem 2.7. We take the ULI result of SE-MAB in Theorem 3.2 as an example. According to ULI result of SE-MAB in Theorem 3.2, we have $F_{ULI}(\\delta,t)=\\text{polylog}(t/\\delta)t^{-\\kappa}=t^{-\\frac{1}{2}}\\sqrt{K\\log(\\delta^{-1}Kt)}$ with $\\kappa=1/2$ in Theorem 2.7 and for all $T \\in \\mathbb{N}$, $R_T = O(\\Delta^{-1}K \\log(K\\delta^{-1} \\Delta^{-1}))$. Other ULI results in our paper can be similarly translated.\n\n---\n**Q4:** Example of algorithms with optimal instance-dependent regret and satisfying ULI condition. If this is difficult, could authors \n make an instance-dependent analysis for the algorithms in section 3.1?\n\n**A4:** It is unclear if an algorithm can simultaneously achieve optimal instance-dependent regret and ULI guarantee, but we note that the regret bounds of algorithms in Section 3.1 are near-optimal via a instance-dependent analysis provided below. The main difficulty is that the algorithm (e.g., optimism-based) with the optimal regret bound should mix exploration and exploitation, whereas ULI requires the algorithm (elimination-based) to explore more in the beginning, and [1] show that elimination-based algorithms cannot be optimal. \nIt is interesting to study if there exists a separation between optimal regret and optimal ULI for future work.\n\n[1] On explore-then-commit strategies, NIPS, 2016.\n\nBelow, we provide the formal instance dependent analysis for the algorithms. One can directly invoke Theorem 2.7 to get an instance-dependent regret bound in the form of $\\widetilde{O}(K\\Delta^{-1})$ (where $\\Delta$ is the minimum gap) or making an instance-dependent analysis for specific algorithms to get a tighter bound as $\\widetilde{O}(\\sum_{a:\\Delta_a>0} \\Delta_a^{-1})$. The analysis is given in the following.\n\n**SE-MAB.** Recall that $N_a(t)$ is the number of plays of arm $a$ before $t$. With probability $\\geq 1-\\delta$, for all $t \\in \\mathbb{N}$, $R_t =\\sum_{a:\\Delta_a>0} \\Delta_a N_a(t+1) = O(\\sum_{a:\\Delta_a>0}  \\frac{\\log(Kt/\\delta)}{\\Delta_a} )$ where the bound of $N_a(t)$ is given in Lemma D.4. Recall that $T_a$ is an upper bound for the number of plays of suboptimal arm $a$ until getting eliminated. By solving Eq. (12) in Lemma D.4, one can also derive a high-probability anytime bounded regret $R_t =\\sum_{a:\\Delta_a>0} \\Delta_a T_a = O(\\sum_{a:\\Delta_a>0}  \\frac{\\log(K\\Delta_a^{-1}\\delta^{-1})}{\\Delta_a} )$. Combining both bounds, we have\n$$\\mathbb{P} \\left( \\forall t:R_t=O(\\sum_{a:\\Delta_a>0} \\frac{\\log(K\\min\\{\\Delta_a^{-1},t\\}\\delta^{-1})}{\\Delta_a} \n)\\right) \\geq 1-\\delta.$$\n\n**PE-MAB.** \nRecall from Algorithm 7 (see Appendix D.2) that PE-MAB runs in phases $s=1,2,\\ldots$ and in each phase $s$, it plays every arm $a$ in active arm set for $m_{s}=\\lceil  2^{2s+1}\\log(4Ks^2 \\delta^{-1})  \\rceil$ times. Let $s(t)$ be the phase that round $t$ lies in and we denote $s_a$ be the last phase that suboptimal arm $a$ survive. Thus, with probability $\\geq 1-\\delta$, for all $t \\in \\mathbb{N}$ ($\\lesssim$ hides constant),\n\n$$R_t  = \\sum_{a:\\Delta_a>0} \\Delta_a \\sum_{s=1}^{  \\min\\\\{s(t),s_a\\\\}  } m_{s} \\lesssim \\sum_{a:\\Delta_a>0} \\Delta_a \\cdot \\log(K\\delta^{-1} (\\min\\\\{s(t),s_a\\\\})^2 ) \\sum_{s=1}^{  s_a  } 2^{2s+1} \\lesssim \\sum_{a:\\Delta_a>0} \\frac{\\log(K\\delta^{-1} \\min\\\\{\\log(t),\\log(\\Delta_a^{-1})\\\\} ) }{\\Delta_a}$$\n\nwhere the last inequality uses $s(t) \\leq \\log_2(t+1)$ (Lemma D.9) and $\\frac{\\Delta_a}{2} \\leq 2^{-(s_a-1)}$ (Lemma D.8).\n\n**PE-L.** As this algorithm is also phased-based, the instance-dependent regret bound can be derived by using a similar argument of PE-MAB, as shown above.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EAzgIE2KG5", "reviewer": "Reviewer_upT1", "summary": "In this paper, the authors study algorithms with better performance metrics for both bandits and reinforcement learning. They propose a new metric, namely the uniform last-iterate guarantee, generalizing uniform-PAC, which can further ensure the last-iterate performance of the algorithm. The authors present algorithms achieving this guarantee in different scenarios. In the multi-armed bandits setting, the authors propose an elimination-based meta algorithm that can achieve a near-optimal uniform last-iterate guarantee. Together with the adaptive barycentric spanner technique, they then show that the algorithm can be extended to linear bandits with possibly infinite arms. Finally, the authors generalize their algorithm to the tabular Markov decision process, achieving a uniform last-iterate guarantee with near-optimal factors.", "questions": "- Could the authors discuss potential barriers that might prevent the phase-based algorithm (He et al., 2021) from achieving a uniform last-iterate guarantee in linear bandits?\n\nHe, Jiafan, Dongruo Zhou, and Quanquan Gu. \"Uniform-pac bounds for reinforcement learning with linear function approximation.\" Advances in Neural Information Processing Systems 34 (2021): 14188-14199.", "limitations": "- The authors have thoroughly discussed the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is generally well-written and easy to follow.\n\n- The paper discusses a new metric for online learning algorithms. It is shown that the new uniform last-iterate guarantee is strictly stronger than the uniform-PAC guarantee, which I think is an interesting concept for study.\n\n- The paper presents a meta-algorithm that translates the uniform last-iterate guarantee into adversarial bandits. This adaptation highlights significant implications for the new metric, which are compelling and merit further exploration.", "weaknesses": "- The reinforcement learning algorithm presented in the paper have to examine every policy, which is generally not computationally efficient.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. Below we address your concern. \n\n---\n**Q:** Could the authors discuss potential barriers that might prevent the phase-based algorithm (He et al., 2021) from achieving a uniform last-iterate guarantee in linear bandits?\n\n**A:** \nThe main barriers for UPAC-OFUL (He et al., 2021) to achieve ULI is the optimistic arm selection rule. Specifically, UPAC-OFUL runs OFUL, an optimistic-based algorithm, in a multi-layer fashion.\nHowever, the arm selection rule established upon optimism, explores the bad arms unevenly across time steps. Consequently, it might play a significantly bad arm for some very large but finite $t$. The ULI guarantee, on the contrary, requires the algorithm to intensively conduct the exploration at the early stage.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4Z4Rm5Skx1", "reviewer": "Reviewer_rjuw", "summary": "The paper proposes a new metric for sample efficiency in online learning called Uniform Last Iterate (ULI), show that it is stronger than existing metrics, and gives algorithms that achieve near-optimal ULI.", "questions": "see weaknesses", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper proposes a new metric for online learning that characterizes not only the cumulative performance but also the instantaneous performance of the learner, which might be important in high-risk fields. The authors show that the proposed metric, called ULI, captures instantaneous performance and is strictly stronger than existing metrics: regret and uniform-PAC. This shows that their new metric is indeed valuable.\n2. The authors then present algorithms that achieve near-optimal ULI in multi-armed bandit, linear bandits and tabular MDPs. The main insight is that algorithms based on action elimination achieve near-optimal ULI, while optimistic algorithms are proved to not achieve near-optimal ULI. This separation between optimism and action elimination is an interesting side effect.\n3. The paper is very clearly written. Presenting a new concept is not easy, and the authors do a good job in explaining it, its motivation and its differences from existing metrics. The algorithms and proofs in the appendix are also easy to follow.", "weaknesses": "1. Although I quite like the definition of this new metric, the potential impact of this paper seems low. The insight about action elimination algorithms being better than optimistic algorithms is nice, but we have seen other cases where this is true and optimistic algorithms are not used in practice anyways. Unfortunately, I believe that the paper cannot get a higher score because of this reason. I would be happy to hear what the authors believe could be the future works that build on this paper.\n2. While the paper and the appendix are well-written, I think that the structure of the paper could greatly improve so that the important things appear in the main text. There are many theorems but not one proof sketch. This is a shame because many of the claims are nice and simple to explain even in just two sentences. I think this would give much better intuition to the readers regarding the logic behind this new metric. In contrast, using a full page to describe an RL algorithm which is mostly standard seems like a huge waste of space. I do not feel like I gained any insight from the RL section (section 5), after reading the previous sections on bandits.\n3. The RL algorithm is disappointing because it is not computationally efficient. For me, this means that the authors did not prove that near-optimal ULI can be achieved in MDPs. The result is over claiming of the contributions in the introduction, especially since near-optimal computationally efficient algorithms based on action elimination already exist in tabular MDPs. Is there a reason they do not achieve near-optimal ULI?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. Below we address your concerns. \n\n---\n**Q1:** What the authors believe could be the future works that build on this paper?\n\n**A1:** We provide three future directions below and will include the discussion in our final version.\n\n- It could be interesting to investigate some empirical issues when deploying ULI algorithms in high-stakes fields.\nTypically, optimistic algorithms initially incur a lower regret than ULI algorithms, but their regret will exceed those of ULI algorithms at a certain juncture. At this juncture, ULI algorithms have eliminated all suboptimal arms, whereas optimistic algorithms continue exploring as time evolves. Hence, identifying this turning point could be beneficial for deploying ULI algorithms in high-stakes domains.\n    \n- Design (computationally efficient) algorithms for MDPs with linear function approximation. The main challenging is to bypass any dependence on the number of states which is possibly infinite. Thus, generalizing our RL algorithm, which enumerates all deterministic policies, to the linear settings does not work.\n\n\n- Design (computationally efficient) algorithms for Episodic MDPs with only logarithmic dependence on $H$ (a.k.a. horizon-free). In our attempts, we use doubling trick on $\\epsilon$ in existing $(\\delta,\\epsilon)$-PAC horizon-free RL algorithms. In this case, we run the algorithm in phases with $\\epsilon,\\epsilon/2,\\epsilon/4,\\ldots$. The main difficulty is to leverage the information learned from the previous phase to guide the algorithm to play an improved policy at the next phase as required by ULI.\nThus, we conjecture that there might exist fundamental barriers to simultaneously achieve ULI guarantee and a logarithmic dependence on $H$.\n\n---\n\n\n**Q2:** The structure and organization issues of the paper in the main text.\n\n**A2:** Thanks for this suggestion. \nWe will use the extra page granted in the final version to improve the main text presentation.\n\n\n\n---\n**Q3:** The RL algorithm is disappointing because it is not computationally efficient. For me, this means that the authors did not prove that near-optimal ULI can be achieved in MDPs. The result is over claiming of the contributions in the introduction, especially since near-optimal computationally efficient algorithms based on action elimination already exist in tabular MDPs. Is there a reason they do not achieve near-optimal ULI?\n\n**A3:** Great question. \nULI condition requires algorithms to play increasingly better policies as time evolves.\nFor action-elimination based algorithms, they typically focus on the cumulative performance such as regret, but does not control the single-round error that ULI requires.\nAs a result, it is entirely possible for the algorithm to take a policy considerably worse after an action is eliminated. \nTherefore, we propose a more direct approach based on policy-elimination to achieve ULI.\nWe left the design of an efficient RL algorithm with ULI guarantee as our future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Overall a good paper with a stronger notion (than standard regret) proposed and characterized. Reviewers overall appreciated the work.
Decision: Accept (poster)