Uniform Last-Iterate Guarantee for Bandits and Reinforcement Learning

Authors: junyan  liu
yunfan  li
ruosong  wang
lin f yang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 09:54:21

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.

Main paper: 
 introduction: 
 In online decision-making problems with bandit feedback, a 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 to achieve good cumulative performance, commonly measured by regret or probably approximately correct (PAC) bound. For instance, in 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 et al., 2019] . To this end, a PAC bound 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 et al. [2017] propose a new performance measure called uniform-PAC, ensuring that for all ϵ > 0, the total number of ϵ-suboptimal policies played by the algorithm is bounded by a function polynomial in 1/ϵ. The uniform-PAC bound can simultaneously imply a high-probability sublinear regret bound and a polynomial sample complexity for any desired accuracy.Although uniform-PAC provides a powerful framework to unify regret2 and PAC bound, it still fails to capture the instantaneous performance of the learning algorithm. In particular, a uniform-PAC algorithm could play a bad policy in some late but finite round t, even if it enjoys a 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, is it optimally achievable by some algorithm?In this paper, we answer both questions affirmatively. Our main contributions are summarized as follows.• We introduce a new metric called uniform last-iterate (ULI), which simultaneously 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 a (near-optimal) ULI guarantee is also (near-optimally) uniform-PAC, 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-based algorithms indeed enjoy a near-optimal ULI guarantee. Then, we propose a metaalgorithm that enables any high-probability adversarial bandit algorithms, with a mild condition, to achieve a 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., lil'UCB [Jamieson et al., 2014] ) cannot achieve near-optimal ULI guarantee.As lil'UCB is near-optimally uniform-PAC, our hardness result also implies that ULI is strictly stronger than uniform-PAC. • For linear bandits with infinitely-many arms, we propose an oracle-efficient3 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) well-behaved arms. This technique generalizes the one in [Awerbuch and Kleinberg, 2008] for elimination-based 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-constrained optimization oracle for only a polynomial number of times. • Finally, we propose a new algorithm for tabular episodic Markov decision processes (MDPs), which achieves a near-optimal ULI guarantee. In particular, our algorithm adapts uncertaintydriven 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.In online decision-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, Abbasi-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 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 (δ, ϵ)-PAC which suggests that with probability at least 1 -δ, the algorithm can output a near-optimal policy at most ϵ away from the optimal one by using a sample complexity polynomial in 1/ϵ. Later, Dann et al. [2017] introduce a new framework called uniform-PAC to unify both metrics and develop a uniform-PAC algorithm for episodic Markov decision processes (MDPs). Subsequent works design uniform-PAC algorithms for MDPs with linear function approximation [He et al., 2021] and bounded Eluder dimension [Wu et al., 2023] . Though uniform-PAC strengthens regret and (δ, ϵ)-PAC bound, it still fails to characterize the instantaneous performance of online algorithms, i.e., a uniform-PAC algorithm, even with a good cumulative performance, can play bad policies for some late rounds.A 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 gametheoretic 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. 
framework: 
 We consider a general online sequential decision-making framework where a learner interacts with an environment with a fixed decision set. At each round t ∈ N, the learner makes a 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] ≜ {1, . . . , K}. Each arm a ∈ [K] is associated with a fixed and unknown [0, 1]-bounded distribution4 such that ∀t, reward X t,a is an i.i.d. sample from this distribution with mean µ a = E[X t,a ]. Let A t be the arm played at round t and ∆ a = µ ⋆ -µ a be the suboptimality gap where µ ⋆ = max a∈[K] µ a .Linear bandits. In the stochastic linear bandits setup, we assume that the arm set A ⊆ R d is compact. The reward of played arm A t at round t follows that X t,At = ⟨θ, A t ⟩ + η t where θ ∈ R d is a fixed but unknown parameter, and η t is conditionally 1-subgaussian. Let ∆ a = sup b∈A ⟨θ, b -a⟩. We follow standard assumptions that ∥θ∥ 2 ≤ 1, ∥a∥ 2 ≤ 1 for all a ∈ A, and ∆ a ≤ 1 for all a ∈ A.Tabular episodic MDPs. A tabular episodic MDP is formalized as M = (S, A, H, r, P, µ) where S, A are finite state and action spaces with |S| = S, |A| = A, H is the horizon length, r = {r h } H h=1 where r h : S × A → [0, 1] is a known reward function, {P h } h∈ [H] where P h : S × A → ∆(S) is a transition function, and µ is the initial state distribution. At the beginning of each episode t, the learner executes a policy π t = {π t,h : S → ∆(A)} H h=1 . Then, starting from the initial state s t,1 ∼ µ, for each stage h ∈ [H], the learner repeatedly takes an action a t,h ∼ π t,h (s t,h ), observes reward r h (s t,h , a t,h ), and transits to the next state s t+1,h ∼ P h (•|s t,h , a t,h ).For any policy π and stage h, we define action value function Q π h (s, a) and value function V π h (s) asQ π h (s, a) = E H h ′ =h r h ′ (s h ′ , a h ′ ) | s h = s, a h = a, π , V π h (s) = E H h ′ =h r h ′ (s h ′ , a h ′ ) | s h = s, π .The optimal action value function and value function at each stage h are denoted by V ⋆ h (s) = max π V π h (s), andQ ⋆ h (s, a) = max π Q π h (s, a) respectively. Let ∆ π = E s1∼µ [V ⋆ 1 (s 1 ) -V π 1 (s 1 )]. Suboptimality notations. For MAB and linear bandits settings, the instantaneous suboptimality is ∆ t = ∆ At , and for episodic MDP, ∆ t = ∆ πt . We use ∆ = inf a∈Π:∆a>0 ∆ a to denote the minimum suboptimality gap. Notice that it is possible that ∆ = 0 when, for example, arm set A is a ball.Regret and (δ, ϵ)-PAC are widely adopted to measure the performance. The regret is defined as: Definition 2.1 (Regret). For each fixed T ∈ N, the regret R T is defined as R T = T t=1 ∆ t .Let N ϵ = ∞ t=1 I{∆ t > ϵ} be the number of plays of policies whose suboptimality gap is greater than ϵ. The definition of (δ, ϵ)-PAC is given as: Definition 2.2 ((δ, ϵ)-PAC). For any fixed δ, ϵ ∈ (0, 1), an algorithm is (δ, ϵ)-PAC (w.r.t. function F PAC ) if there exists a function F PAC (δ, ϵ) polynomial in log(δ -1 ) and ϵ -1 such thatP (N ϵ ≤ F PAC (δ, ϵ)) ≥ 1 -δ.As shown by Dann et al. [2017] , both regret and (δ, ϵ)-PAC have limitations. Specifically, an algorithm with sublinear regret bound may play suboptimal policies infinitely often. For the algorithm with (δ, ϵ)-PAC guarantee, it may not converge to the optimal policy when feeding the algorithm with more samples. Therefore, such an algorithm would play those policies with suboptimality gap, e.g., ϵ/2 infinitely often. Motivated by these limitations, Dann et al. [2017] introduce uniform-PAC as follows. Definition 2.3 (Uniform-PAC). An algorithm is uniform-PAC for some fixed δ ∈ (0, 1) if there exists a function F UPAC (δ, ϵ) polynomial in log(1/δ) and ϵ -1 , such thatP (∀ϵ > 0 : N ϵ ≤ F UPAC (δ, ϵ)) ≥ 1 -δ.We also call F UPAC (δ, ϵ) the sample complexity function. Uniform-PAC is a stronger metric than regret and (δ, ϵ)-PAC since it leads to the following implications. Theorem 2.4 (Theorem 3 in [Dann et al., 2017] ). If an algorithm is uniform-PAC for some δ with functionF UPAC (δ, ϵ) = O α 1 /ϵ + α 2 /ϵ 2 5, where α 1 , α 2 > 0 are constant in ϵ and depend on log(1/δ) and K for MAB, d for linear bandits, and S, A, H for MDPs then, the algorithm guarantees:• P (lim t→+∞ ∆ t = 0) ≥ 1 -δ; • (δ, ϵ)-PAC with F PAC (δ, ϵ) = F UPAC (δ, ϵ) for all ϵ > 0; • With probability at least 1 -δ, for all T ∈ N, R T = O √ α 2 T + α 1 + α 2 .Limitations of Uniform-PAC. According to Theorem 2.4, uniform-PAC can imply a long-term convergence (the first bullet) and good cumulative performance (the second and the third bullets), but it does not capture the convergence rate of ∆ t for each round t. In other words, even if an algorithm enjoys uniform-PAC, it could still play a significantly bad policy for some very large but finite t. This would lead to catastrophic consequences in safety-critical applications.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 δ ∈ (0, 1) if there exists a positive-valued function F ULI (•, •), such thatP (∀t ∈ N : ∆ t ≤ F ULI (δ, t)) ≥ 1 -δ, where F ULI (δ, t) is polynomial in log(1/δ) and proportional to the product of power functions of log t and 1/t (e.g.,F ULI (δ, t) = polylog(1/δ)(log t) κ1 t -κ2 for some κ 1 , κ 2 ≥ 0).According to Definition 2.5, the instantaneous suboptimality of any algorithm with the ULI guarantee can be bounded by a function F ULI (δ, t). Moreover, F ULI (δ, t) decreases monotonically for large t if its power on 1/t is strictly positive, which captures the convergence rate of ∆ t .Note that the convergence rate of ∆ t is mainly determined by the power on 1/t in F ULI . 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 F ULI . Theorem 2.6. For any bandit algorithm that achieves ULI guarantee for some δ with function F ULI (δ, t), there exists a MAB instance such that F ULI (δ, t) = Ω t -1/2 . 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 withF ULI (δ, t) = O(1/ √ t).Then, we present the following theorem to show that ULI directly leads to 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 function F ULI (δ, t) = polylog(t/δ) • t -κ where κ ∈ (0, 1). Then, we have,• the algorithm is uniform-PAC with functionF UPAC (δ, ϵ) = O ϵ -1 κ • polylog(δ -1 ϵ -1 ) . • with probability at least 1 -δ, ∀T ∈ N, the regret R T is bounded by O min polylog(T /δ) • T 1-κ , ∆ 1-1/κ polylog 2 (δ∆) -1 ,when the minimum suboptimality gap of the input instance ∆ satisfies ∆ > 0.According to Theorem 2.7, if an algorithm is with near-optimal ULI guarantee (i.e., κ = 1 2 ), then it implies the near-optimality for uniform-PAC bound (the first bullet point) and anytime sublinear high-probability regret bound (the second bullet point). On the other hand, an algorithm with nearoptimal uniform-PAC bound does not necessarily enjoy a 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 near-optimal ULI guarantee implies an anytime sublinear high-probability regret bound, it cannot give an 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-SpaceIn 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-based algorithms, optimistic algorithms, and high-probability adversarial algorithms, in the finite arm setting, i.e., |A| = K. 
elimination framework achieving near-optimal uli guarantee: 
 To examine whether the elimination-type algorithms can achieve the ULI guarantee, we first provide an elimination framework in Algorithm 1 that ensures the ULI guarantee, and we then show that most elimination-based algorithms fall into this framework. The following result shows that with a proper function f and a positive constant β, such an elimination framework ensures the ULI guarantee. Theorem 3.1. For any given δ ∈ (0, 1), if there exists function f (δ, t) = t -κ polylog(t/δ) for some κ ∈ (0, 1) and ∃β > 0, such that with probability 1 -δ, Eq. (1) holds for all t, then algorithm is ULI withF ULI (δ, t) = O (f (δ, t)).Algorithm 1 Elimination framework for ULI Input: δ ∈ (0, 1), set A, function f (•, •), and constant β. Initialize: active arm set A 0 = A. for t = 1, 2, . . . do Select an active set A t based on available observations as (a * is one of optimal arms)EQUATIONPlay an arm A t ∈ A t and observe reward X t,At .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 a 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 [Lattimore and Szepesvári, 2020] ) and the linear bandit setting (called PE-L, e.g., Algorithm 12 of Chapter 22 in [Lattimore and Szepesvári, 2020] ). Since those algorithms are standard, we defer their pseudocodes 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 1 can be instantiated by• SE-MAB for MAB to achieve the ULI withF ULI (δ, t) = O t -1 2 K log(δ -1 Kt) .• PE-MAB for MAB to achieve the ULI withF ULI (δ, t) = O t -1 2 K log(δ -1 K log(t + 1)) .• PE-L for linear bandits to achieve ULI withF ULI (δ, t) = O t -1 2 d log(δ -1 K log(t + 1) log d) .Achieving ULI by adversarial bandit algorithms. Traditional elimination-based algorithms, including the ones mentioned above, typically require a carefully designed exploration strategy which is non-trivial even for linear bandits. Here, we provide an alternative way to 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 elimination-based algorithms.In this section, we present a lower bound to show that optimistic algorithms cannot achieve nearoptimal 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 t that satisfiesEQUATIONwhere N a (t) is the number of plays of arm a before round t, µ a (Na (t)) = t-1 s=1 X s,As I{As=a} Na(t)is the empirical mean of arm a after N a (t) times play, and U δ (N a (t)) is a 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 log(2t 2 /δ)/N a (t)6 . However, the log t 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, Degenne and Perchet, 2016] with log t term in bonus function, also cannot achieve the ULI guarantee.We then consider another optimistic-type algorithm, lil'UCB [Jamieson et al., 2014] which obtains the order-optimal instance-dependent sample complexity and avoids log(t) term in U δ (N a (t)). The bonus function of lil'UCB is as log δ -1 log + (N a (t)) /N a (t) where log + (x) = log (max {x, e}). Our main result for lil'UCB is presented as follows. The full analysis of lil'UCB is deferred to Appendix E. Theorem 3.3. There exists a constant α ∈ (0, 1) that for all ∆ ∈ (0, α), running lil'UCB on the two-armed bandit instance with deterministic rewards and arm gap ∆ gives ∃t = Ω ∆ -2 such that∆ t = Ω t -1 4 log log (∆ -2 log(δ -1 )) + log(δ -1 ) .Theorem 3.3 shows that lil'UCB is not near-optimal ULI, but it is unclear whether it can achieve the ULI guarantee. Recall from Theorem 3.2 that the elimination-based algorithms ensure that with high probability, ∀t, ∆ t = O t -1 /2 . Theorem 3.3 suggests that the convergence rate of lil'UCB is strictly worse than that of elimination-based algorithms, even if it enjoys a near-optimal cumulative performance [Jamieson et al., 2014] . In fact, this lower bound holds for all optimistic algorithms as long as the bonus function is in a similar form. Remark 3.4 (ULI is strictly stronger than uniform-PAC). For lil'UCB, the number of times playing suboptimal arms is finite with an order-optimal instance-dependent sample complexity, which implies that lil'UCB is near-optimal uniform-PAC. Therefore, Theorem 3.3 also shows that an algorithm with near-optimal uniform-PAC does not necessarily enjoy near-optimal ULI guarantee. Compute V m = I + a∈Bm n m (a)aa ⊤ and θ m+1 = V -1 m t∈Tm A t X t,At where T m is a set that contains all rounds in phase m.4 Achieving Near-Optimal ULI for Linear Bandits in Large Arm-SpaceIn this section, we propose a linear bandit algorithm that can handle the infinite number of arms. The compact arm set A is assumed to span R d and d is known. 
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 carefully-designed 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 is a ball. A natural idea is to discretize A, e.g., constructing a ϵ-net, but the computational complexity has an 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 oracleefficient linear bandit algorithm in Algorithm 2 which can eliminate bad arms by efficiently querying an optimization oracle. Our algorithm equips PE with a 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 an optimization oracle in polynomial times.The definition of barycentric spanner [Awerbuch and Kleinberg, 2008] is presented as follows. Why adaptive barycentric spanner? The primary reason that the non-adaptive barycentric spanner technique [Awerbuch and Kleinberg, 2008] fails to work for PE is 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 of R d , 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 a barycentric spanner for active arm set adaptively for each phase, even if they do not span R d .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 a C-approximate barycentric spanner B m which can linearly represent all arms in active arm set A m where A 1 = A and ∀m ≥ 2EQUATIONAlgorithm 3 Tabular Episodic MDPs with ULI guarantee Input: δ ∈ (0, 1), set Π all containing all deterministic policies, absolute constant c 1 , c 2 > 0.Initialize:Π 1 = Π all . for m = 1, 2, . . . do Set δ m = δ/(2m 2 ) and duration T m = c 1 2 2m S 2 AH 4 log 2 c 2 2 2m S 2 AH 4 |Π all |/δ m . Run Algorithm 4 with input (δ m , Π m , T m ) to obtain { V π m } π∈Πm . Update active policy set Π m+1 = π ∈ Π m : max π ′ ∈Πm V π ′ m -V π m ≤ 2 -m .where a ⋆ m is the empirical best arm and θ m is the estimation of unknown parameter θ. Then, the algorithm assigns π m (a) = EQUATIONwhere V m = I + a∈Bm n m (a)aa ⊤ is the least squares matrix, used to estimate θ.According to the standard analysis of linear bandit algorithms, the estimation error of ⟨a, θ⟩ is proportional to ∥a∥ V -1 m . Hence, the estimation errors of {⟨a, θ⟩} a∈Am can be uniformly bounded by O Cd/ T m-1 , which is known to the learner. Finally, after playing each arm a ∈ B m for n m (a) times, the algorithm updates the empirical estimates V m and θ m+1 , and then steps into the next phase.The main results of Algorithm 2 for achieving the ULI guarantee and computational complexity are given as follows. The full proof can be found in Appendix G.Theorem 4.2. For any fixed δ ∈ (0, 1), Algorithm 2 achieves the ULI guarantee with function F ULI (δ, t) = O t -1 2 d 3 log(δ -1 dt) . Moreover, in each phase, the number of calls to the optimization oracle given in Definition G.2 is O d 3 log C d .Theorem 4.2 and Theorem 2.7 jointly suggest O(d 3 /2 √ T ) worst-case regret bound for the infinitearmed setting, which matches those of [Dani et al., 2008 , Agrawal and Goyal, 2013 , Hanna et al., 2023] . Compared with the lower bound Ω(d √ T ) given by Dani et al. [2008] , our regret bound suffers an extra √ d 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 Ω(dT ) 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 MDPsIn this section, we propose a novel algorithm that achieves a near-optimal ULI guarantee in tabular episodic MDPs setup. The algorithm is formally presented in Algorithm 3.High-level idea. Algorithm 3 conducts policy elimination over a policy set Π all which enumerates all deterministic policies. The key challenge here is to acquire accurate estimations of value functions uniformly for all deterministic policies. Note that naïvely playing all deterministic policies will incur linear dependence on |Π all | = A SH in F ULI , which is exponentially large. Hence, the algorithm invokes subroutine Algorithm 4 to exhaustively explore the environment, which ensures accurate estimations of the transition model and only suffers logarithmic dependence on |Π all |. 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.Algorithm 4 Uniform estimation for value functions Input: confidence δ ∈ (0, 1), policy set Π ⊆ Π all , duration T . Initialize: randomly pick a policy π 1 ∈ Π, N 1,h (s, a) = N 1,h (s, a, s ′ ) = 0 for all (h, s, a, s ′ ). Output: { V π } π∈Π where V π = 1 T T t=1 V πT,1 (s t,1 ).Input: policy set Π ⊆ Π all , reward function r, transition P, bonus function b, initial state s 1 .for π ∈ Π do Q π H+1 (•, •) = 0 and V π H+1 (•) = 0. for h = H, H -1, . . . , 1 do Q π h (•, •) = min P h V π h+1 (•, •) + r h (•, •) + b h (•, •), H and V π h (•) = Q π h (•, π(•)). Output: { V π 1 (s 1 )} π∈Π .More concretely, Algorithm 3 first accepts a set of all deterministic policies and then it proceeds in phases m = 1, 2, . . .. In each phase m, subroutine Algorithm 4 is invoked to learn the transition model. Specifically, the subroutine inherits the structure of UCB-VI [Azar et al., 2017] , but more importantly the algorithm pretends to be agnostic to the reward function and uses uncertainty-driven reward functions {b t,h (s, a)/H} t,h whereEQUATIONwhere N t,h (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 a state-action pair, i.e., more visitations of (s, a), larger N t,h (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 to play a policy that maximizes the uncertainty.The following theorem shows that our algorithm achieves the ULI guarantee. Theorem 5.1. For any fixed δ ∈ (0, 1), Algorithm 3 achieves the ULI guarantee with functionF ULI (δ, t) = O t -1 2 √ S 3 AH 5 log (tSAH/δ) .Theorem 5.1 shows near-optimality of Algorithm 3 w.r.t. episode t. Unfortunately, the regret bound implied by our ULI result incurs suboptimal dependence on S, H, and the logarithmic term, and our algorithm is not computational efficient. We leave these improvements for future work. 
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 finitearm setting. Specifically, we provide stronger analysis to show that elimination-based algorithms naturally achieve near-optimal ULI guarantees. We also provide a reduction-based approach to enable any high-probability adversarial algorithms, with a mild condition, to achieve near-optimal ULI guarantees. We further provide a 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 a ULI guarantee in tabular episodic MDPs.Some natural directions are to improve our current results, including proposing a ULI algorithm for linear bandits with infinite 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 H (a.k.a. horizon-free). In our attempts, we use the doubling trick on ϵ in existing (δ, ϵ)-PAC horizon-free RL algorithms. In this case, we run the algorithm in phases with ϵ, ϵ/2, ϵ/4, . . .. 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. Thus, we conjecture that there might exist fundamental barriers to simultaneously achieve ULI guarantee and a 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 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. We prove this claim by contradiction. Suppose that there exists an algorithm that can achieve the ULI guarantee with function 
 
 Appendix: F ULI (δ, t) ≤ c 0 1 t 1 2+α for some α ∈ (0, 1 2 ) and constant c 0 > 0 which may depend on log(1/δ) and K for MAB or d for linear bandits. We consider a K-armed bandit instance (K ≥ 2) with Gaussian rewards and all suboptimality gaps are bounded by one.By the definition of ULI, we have that with probability at least 1 -δ, for all T ∈ N with T 1 2 -α > t 0 , we haveR T = T t=1 ∆ t = t0 t=1 ∆ t + T t=t0+1 ∆ t ≤ t 0 + T t=t0+1 F ULI (δ, t) ≤ t 0 + c 0 T t=t0+1 t -α-1 2 ≤ T 1 2 -α + 2c 0 1 -2α T 1 2 -α ,where the first inequality holds as we assume all suboptimal gaps are bounded by one, and∆ t ≤ F ULI (δ, t) for all t ≥ t 0 .Since 1 2 -α ∈ (0, 1 2 ), there will be a contradiction to the regret lower bound [Lattimore and Szepesvári, 2020, Corollary 17.3] for the Gaussian MAB setup.Theorem B.1 (Restatement of Theorem 2.7). Suppose an algorithm achieves the ULI guarantee for some δ with function F ULI (δ, t) = polylog(t/δ) • t -κ where κ ∈ (0, 1). Then, we have,• the algorithm is also uniform-PAC withF UPAC (δ, ϵ) = O polylog(δ -1 ϵ -1 ) ϵ 1/κ .• with probability at least 1 -δ, ∀T ∈ N, the regret R T is bounded byO min polylog(T /δ) • T 1-κ , polylog 2 1 δ∆ ∆ 1/κ-1 ,when the minimum suboptimality gap of the input instance ∆ satisfies ∆ > 0.In this subsection, we show the first bullet of Theorem 2.7. We define the following events forEQUATIONwhich indicates the occurrence the ULI, and denote the event B as:B = ∀ϵ > 0 : ∞ t=1 I{∆ t > ϵ} ≤ F UPAC (δ, ϵ) .For some δ ∈ (0, 1), if event A holds for an algorithm with probability at least 1 -δ, then the algorithm is with ULI guarantee. Therefore, to prove the claimed result, it suffices to show that conditioning on event A that for any algorithm enjoys ULI guarantee with a function F ULI (δ, t), one can find a function F UPAC (δ, ϵ) such that event B also holds.As for any fixed δ ∈ (0, 1), F ULI (δ, t) = polylog(t/δ) • t -κ is monotonically decreasing for large t, ∃U ∈ R >0 such that F ULI (δ, t) ≤ U for all t ∈ N and F ULI (δ, t) = U is attainable by some t. Then, we consider any given ϵ > 0 with two cases as follows.Case 1: ϵ < U . Again, by the fact that F ULI (δ, t) = polylog(t/δ) • t -κ is monotonically decreasing for large t, there should exist a round t ∈ N such that F ULI (δ, s) ≤ ϵ for all s ≥ t. Let t 0 be the round with the maximal index such that F ULI (δ, t 0 ) > ϵ, which givest 0 ≤ polylog 1 κ (t 0 /δ) ϵ 1 κ .As a result, the number of times that ∆ t > ϵ occurs is at most∞ t=1 I{∆ t > ϵ} ≤ ∞ t=1 I{F ULI (δ, t) > ϵ} ≤ t 0 ≤ polylog 1 κ (t 0 /δ) ϵ 1 κ . Then, one can find constants c 0 > 0 and z ∈ (0, κ) such that polylog(t/δ) ≤ c 0 • polylog(1/δ)t z for all t ∈ R ≥1 , thereby polylog(t 0 /δ) ≤ c 0 • polylog(1/δ)t z 0 . Combining polylog(t 0 /δ) ≤ c 0 • polylog(1/δ)t z 0 and F ULI (δ, t 0 ) > ϵ gives ϵ ≤ polylog(t 0 /δ) t κ 0 ≤ c 0 • polylog(1/δ)t z 0 t κ 0 = c 0 • polylog(1/δ)t z-κ 0 ,which immediately leads toEQUATIONThen, we can further show that∞ t=1 I{∆ t > ϵ} ≤ t 0 ≤ polylog 1 κ (t 0 /δ) ϵ 1 κ ≤ polylog δ -1 c0•polylog(1/δ) ϵ 1 κ-z ϵ 1 κ ≜ F UPAC (δ, ϵ), (8)where the third inequality follows that polylog(t/δ) is monotonically increasing for all t > 0 and Eq. ( 7).Case 2: ϵ ≥ U . Conditioning on event A and by the definition of U , we have∆ t ≤ F ULI (δ, t) ≤ U ≤ ϵ for all t ∈ N, which implies ∞ t=1I{∆ t > ϵ} = 0. Therefore, any positive function works there and we still choose F UPAC (δ, ϵ) the same as above.This argument holds for all ϵ > 0. Therefore, if an algorithm satisfies the ULI guarantee, then P(A) ≥ 1 -δ, and with the above statement, we can find a function F UPAC such that P(B) ≥ 1 -δ, which concludes the proof.For some fixed δ ∈ (0, 1), let us consider an algorithm enjoys the ULI guarantee with function F ULI (•, •). The following analysis will condition on event A given in Eq. ( 6).Gap-dependent bound. Recall that ∆ > 0 is the minimum gap. We replace ϵ with ∆/2 in the proof of in Appendix B.1, case 1, and similarly define t 0 ∈ N as the maximal round such thatF ULI (δ, t 0 ) = polylog(t 0 /δ) • t -κ 0 > ∆/2.Then, we apply a similar argument (in Appendix B.1, case 1), which gives that that for some constants z ∈ (0, κ) and c 0 > 0:∞ s=1 I{∆ As > ∆/2} ≤ t 0 ≤ min        2c 0 • polylog(1/δ) ∆ 1 κ-z , polylog δ -1 2c0•polylog(1/δ) ∆ 1 κ-z (∆/2) 1 κ        , (9)where the last inequality holds by taking the minimum of Eq. ( 7) and Eq. ( 8). Therefore, the algorithm will incur no regret, i.e., ∆ t = 0 for all t ≥ t 0 For every T ∈ N, the regret R T is bounded byEQUATIONwhere the first inequality holds since we condition on the event A, the second inequality holds due to the definition of t 0 , the third inequality uses the fact that polylog(t/δ) is monotonically increasing for all t > 0.Then, one can further showR T ≤ t 1-κ 0 • polylog(δ -1 t 0 ) 1 -κ ≤ polylog δ -1 2c0•polylog(1/δ) ∆ 1 κ-z • polylog(δ -1 t 0 ) (∆/2) 1/κ-1 ≤ polylog δ -1 2c0•polylog(1/δ) ∆ 1 κ-z • polylog δ -1 2c0•polylog(1/δ) ∆ 1 κ-z (∆/2) 1/κ-1 ,where the second inequality applies the second term of Eq. ( 9) and the last inequality uses the first term of Eq. ( 9).Notice that these bounds in all three cases hold for all T ∈ N, and thus the proof of gap-dependent bound is complete.Gap-independent bound. We haveR T = T t=1 ∆ t ≤ T t=1 polylog(t/δ) • t -κ ≤ polylog(T /δ) T t=1 t -κ ≤ T 1-κ • polylog(δ -1 T ) 1 -κ .C Proof of Theorem 3.1For shorthand, we use E to denote the event that Eq. ( 1) holds for all t ∈ N. From the assumption, E holds with probability at least 1 -δ. The following proof is straightforward by the definition of E. We conditions on E and consider an arbitrary round t. If A t = a ⋆ , the claim trivially holds as ∆ At = 0. We then consider A t ̸ = a ⋆ . Since Algorithm 1 pulls an arm A t ∈ A t at each t. From the definition of E, we have ∆ At ≤ β • f (δ, t). Therefore, Algorithm 1 achieves the ULI guarantee with . We present SE-MAB algorithm in Algorithm 6 and define some notations. Let N a (t) be the number of times that arm a has been pulled before round t and let µ a (s) be the empirical mean of arm a after s ∈ N number of plays. We define the confidence width for each s ∈ N asF ULI (δ, t) = O (f (δ, t)).EQUATION)The SE-MAB algorithm always chooses the arm (from the current active arm set) with the minimum number of pulls. If there exist two arms a, j ∈ [K] such that N a (t) = N j (t), then, the algorithm chooses the arm with the smallest index.Algorithm 6 Successive elimination for multi-armed bandit (SE-MAB) Input: confidence δ ∈ (0, 1). Initialize: active arm set A 1 = [K] and sample every arm once to update N a (K + 1), µ a (N a (K + 1)), wd(N a (K + 1)) for all a ∈ [K]. for t = K + 1, K + 2, . . . do Play an arm A t = argmin a∈At N a (t) and observe reward X t,At . Update counter N a (t+1) = N a (t)+1 for A t = a and N a (t+1) = N a (t) for all a ∈ A t -{A t }.Update empirical means µ At (N At (t + 1)) =µ A t (N A t (t))•N A t (t)+X t,A t N A t (t)+1and µ a (N a (t + 1)) = µ a (N a (t)) for all a ∈ A t -{A t }. Update confidence width wd(N a (t + 1)) based on Eq. ( 11) for all a ∈ A t . Update bad arm set B t asB t = {a ∈ A t : ∃j ∈ A t such that µ j (N j (t + 1)) -wd(N j (t + 1)) -µ a (N a (t + 1)) -wd(N a (t + 1)) > 0} .A t+1 = A t -B t . Definition D.1. Let E be the event that | µ a (N a (t)) -µ a | ≤ wd(N a (t)) holds for all t ∈ N and all a ∈ A t . Lemma D.2. P (E) ≥ 1 -δ.Proof. Following the standard trick (e.g., [Audibert et al., 2010] ), we rewrite the empirical mean for every a, n as µ a (n) = 1 n n i=1 R i,a where R i,a is the reward of i-th pull of arm a. Let us fix both s ∈ N and a ∈ [K]. By Hoeffding's inequality, with probability at least1 -δ ′ | µ a (s) -µ a | ≤ log 2 δ ′ 2s .Choosing δ ′ = δ 2Ks 2 and applying a union bound over a ∈ A t (|A t | ≤ K, ∀t), we have with probability at least 1 -δ/(2s 2 ),| µ a (s) -µ a | ≤ log 4Ks 2 δ 2s = wd(s), ∀a ∈ [K].We apply a union bound over all s ∈ N and use the fact that ∞ s=1 δ 2s 2 ≤ δ to finish the proof. Lemma D.3. Suppose that E occurs where E is given in Definition D.1. For all t ∈ N, a ⋆ ∈ A t holds.Proof. We prove this by induction. For t = 1, a ⋆ ∈ A 1 trivially holds. Suppose that a ⋆ ∈ A t . To show a ⋆ ∈ A t , it suffices to show that at the end of round t, arm a ⋆ is deemed as a good arm. One can use the definition of E to show that for every a ∈ A t , the following holds.0 ≤ µ ⋆ -µ a ≤ µ a ⋆ (N a ⋆ (t + 1)) + wd(N a ⋆ (t + 1)) -µ a (N a (t + 1)) + wd(N a (t + 1)).Note that the second inequality above can hold since the inductive hypothesis gives that a ⋆ ∈ A t . The above inequality shows that a ⋆ will not be eliminated at the end of round t thereby still being active at round t + 1. Once the induction is done, the proof is complete.Lemma D.4. Suppose that E occurs where E is given in Definition D.1. For all t ∈ N and all arms a ∈ A if a ∈ A t , then∆ a ≤ 14K log (4Kt 2 /δ) t .Proof. Consider any round t ∈ N and any active arm a ∈ A t . For simplicity, we assume that the first arm is the unique optimal arm7 . If a is an optimal arm, then ∆ a = 0 and we hold the claim trivially. Then, it suffices to consider an arm a ∈ A t with ∆ a > 0. Notice that wd(x) is monotonically decreasing for all x ≥ 1 as long as K ≥ 2. Thus, we find a minimum natural number T a ∈ N such thatEQUATIONWith this definition, we have∆ a < 5wd(s) ∀1 ≤ s < T a , and ∆ a ≥ 5wd(s) ∀s ≥ T a .Recall that N a (t) is the number of plays of arm a before round t. We first show N a (t) ≤ T a . As Algorithm 6 pulls arms in a round-robin fashion, if arm a is pulled for T a times, then, the optimal arm a ⋆ is also pulled for T a times, thereby T a = T a ⋆ . From Lemma D.3, optimal arm a ⋆ is active for all t ∈ N and thus we can use it as a comparator.µ a ⋆ (T a ⋆ ) -wd(T a ⋆ ) -µ a (T a ) -wd(T a ) ≥ µ ⋆ -2wd(T a ⋆ ) -µ a -2wd(T a ) (by E) = µ ⋆ -2wd(T a ) -µ a -2wd(T a ) (by T a = T a ⋆ ) ≥ ∆ a -2 × ∆ a 5 -2 × ∆ a 5 = ∆ a 5 > 0.According to elimination rule, this inequality shows that arm a will be eliminated after T a pulling times, which suggests that N a (t) ≤ T a . Since the T a is the minimum natural number which holds Eq. ( 12), we use N a (t) ≤ T a to show∆ a < 5 log (4K(N a (t) -1) 2 /δ) 2(N a (t) -1) ≤ 5 log (4Kt 2 /δ) 2(N a (t) -1) ,where the last inequality follows from the fact that N a (t) ≤ t. Rearranging the above, we haveN a (t) ≤ 1 + 25 log 4Kt 2 /δ 2∆ 2 a ≤ 13 log 4Kt 2 /δ ∆ 2 a .Again, as Algorithm 6 pulls arms in a round-robin fashion, we have t ≤ K(N a (t) + 1) and showt ≤ K(N a (t) + 1) ≤ 14K log 4Kt 2 /δ ∆ 2 a , which gives ∆ a ≤ 14K log(4Kt 2 /δ) t. Conditioning on event E the argument holds for all t ∈ N, which thus completes the proof.Proof of Theorem 3.2 for SE-MAB. Once Lemma D.3 and Lemma D.4 hold, Theorem 3.1 gives that for any fixed δ ∈ (0, 1), SE-MAB achieves the ULI guarantee with a functionF ULI (δ, t) = O K log (Kt/δ) t .Therefore, the proof of Theorem 3.2 for SE-MAB is complete.In MAB setting with A = [K], we further consider phased elimination algorithm (e.g., Exercise 6.8 of [Lattimore and Szepesvári, 2020] ) shown in Algorithm 7 (called PE-MAB). The algorithm proceeds with phases ℓ = 1, 2, . . ., and each phase ℓ includes consecutive rounds, with an exponential increase. In phase ℓ, the algorithm sequentially pulls every arm a ∈ [K] for m ℓ times wherem ℓ = 2 2ℓ+1 log 4Kℓ 2 /δ .Once all arms are pulled m ℓ times, the algorithm steps into the next phase ℓ + 1. The counter N a (ℓ) records the number of times that arm a is pulled in phase ℓ and µ a (m ℓ ) is the empirical mean by using m ℓ samples only from phase ℓ.Algorithm 7 Phased elimination for multi-armed bandit (PE-MAB) Input: confidence δ ∈ (0, 1). Initialize: active arm setA 1 = [K].for ℓ = 1, 2, . . . do Play every arm a ∈ A ℓ for m ℓ times and observe corresponding rewards.Update empirical means { µ a (m ℓ )} a∈A ℓ only using samples from phase ℓ. Update active arm set A ℓ+1 asA ℓ+1 = A ℓ -a ∈ A ℓ : max j∈A ℓ µ j (m ℓ ) -µ a (m ℓ ) > 2 -ℓ . Definition D.5. Let E be the event that | µ a (m ℓ ) -µ a | ≤ 2 -ℓ-1 holds for all ℓ ∈ N and all a ∈ A ℓ .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) ≥ 1 -δ.Proof. We first fix both ℓ ∈ N and a ∈ [K]. By Hoeffding's inequality, with probability at most δ ′ , we have| µ a (m ℓ ) -µ a | ≥ log 2 δ ′ 2m ℓ .Choosing δ ′ = δ 2Kℓ 2 and applying union bounds over a ∈ A ℓ (A ℓ is at most K), with probability at most δ/2ℓ 2 , we have| µ a (m ℓ ) -µ a | ≥ log (4Kℓ 2 /δ) 2m ℓ = 2 -ℓ-1 .We apply union bounds over all ℓ ∈ N and use the fact that ∞ ℓ=1 δ 2ℓ 2 ≤ δ to finish the proof.Lemma D.7. Suppose that E occurs where E is given in Definition D.5. For all ℓ ∈ N, a ⋆ ∈ A ℓ .Proof. We prove this by induction. For the base case ℓ = 1, the claim trivially holds. Suppose the claim holds for ℓ, and then we will show that a ∈ A ℓ+1 . For all ℓ ∈ N and all a ∈ A ℓ , we have0 ≤ µ ⋆ -µ a ≤ µ a ⋆ (m ℓ ) -µ a (m ℓ ) + 2 -ℓ ,where the second inequality holds because the induction hypothesis ensures a ⋆ ∈ A ℓ and thus we can use the definition of E. Based on the elimination rule, a ⋆ ∈ A ℓ+1 . Once the induction is done, the proof is complete.Lemma D.8. Suppose that E occurs where E is given in Definition D.5. For each arm a with ∆ a > 0, it will not be in A ℓ for all phases ℓ ≥ ℓ a + 1 where ℓ a is the smallest phase such that ∆a 2 > 2 -ℓa .Proof. Consider any arm a with ∆ a > 0. We only need to consider a ∈ A ℓa and otherwise, the claimed result holds trivially. Recall that ℓ a is the smallest phase such that ∆a 2 > 2 -ℓa and one can showmax j∈A ℓa µ j (m ℓa ) -µ a (m ℓa ) -2 -ℓa ≥ µ a ⋆ (m ℓa ) -µ a (m ℓa ) -2 -ℓa ≥ µ ⋆ -2 -ℓa -µ a -2 -ℓa > ∆ a -2 × ∆ a 2 = 0,where the first inequality follows from Lemma D.7 that a ⋆ ∈ A ℓa and the second inequality holds due to E.According to the elimination rule, arm a will not be in phases ℓ for all ℓ ≥ ℓ a + 1. Lemma D.9. Let ℓ(t) be the phase in which round t lies. Then, ℓ(t) ≤ log 2 (t + 1) for all t ∈ N.Proof. We prove this by contradiction. Suppose that ∃t ∈ N that ℓ(t) > log 2 (t + 1). Note that we can further assume ℓ(t) ≥ 2 since one can easily verify that for all t such that ℓ(t) = 1, ℓ(t) ≤ log 2 (t + 1) must hold. We havet ≥ m ℓ(t)-1 ≥ 2 2ℓ(t)-1 log 4K(ℓ(t) -1) 2 /δ > 1 2 (t + 1) 2 log (4K/δ) > t,where the third inequality bounds ℓ(t) in the logarithmic term by ℓ(t) ≥ 2 and bound the other ℓ(t) > log 2 (t + 1) by assumption. Therefore, once a contradiction occurs, the proof is complete.Lemma D.10. Let ℓ(t) be the phase in which round t lies. Suppose that E occurs where E is given in Definition D.5. For all t ∈ N and all a ∈[K], if a ∈ A ℓ(t) , then ∆ a ≤ 256K log 4K (log 2 (t + 1)) 2 /δ 3t .Proof. If a ∈ A ℓ(t) is optimal, then, ∆ a = 0 and the claim trivially holds. In what follows, we only consider arm a ∈ A ℓ(t) with ∆ a > 0. From Lemma D.8, if an arm a ∈ A ℓ(t) is with ∆ a > 0, then, ℓ(t) ≤ ℓ a where ℓ a is defined in Lemma D.8. Thus, the total number of rounds that such an arm a is active is at mostK ℓ(t) s=1 m s = K ℓ(t) s=1 2 2s+1 log 4Ks 2 /δ ≤ 4K log 4Kℓ(t) 2 /δ ℓ(t) s=1 2 2s ≤ 4K log 4Kℓ(t) 2 /δ ℓa s=1 2 2s ≤ 16K log 4Kℓ(t) 2 /δ 3 • 4 ℓa ≤ 256K log 4Kℓ(t) 2 /δ 3∆ 2 a ≤ 256K log 4K (log 2 (t + 1)) 2 /δ 3∆ 2 a ,where the first inequality follows from ⌈x⌉ ≤ 2x for all x ≥ 1, the second inequality bounds ℓ(t) ≤ ℓ a , the fourth inequality follows from the definition of ℓ a , i.e., ∆a 2 ≤ 2 -(ℓa-1) , and the last inequality follows from Lemma D.9 that ℓ(t) ≤ log 2 (t + 1).Since this argument holds for each round t and each arm a ∈ A ℓ(t) conditioning on E, the proof is complete.Proof of Theorem 3.2 for PE-MAB. Once Lemma D.7 and Lemma D.10 hold, Theorem 3.1 gives that for any fixed δ ∈ (0, 1), PE-MAB achieves the ULI guarantee with a functionF ULI (δ, t) = O t -1 2 K log (K log(t + 1)/δ) .Therefore, the proof of Theorem 3.2 for PE-MAB is complete. where G ℓ = a∈A ℓ π ℓ (a)aa T . Play every arm a ∈ A ℓ for m ℓ (a) = ⌈π ℓ (a)m ℓ ⌉ times and observe corresponding rewards. Update the empirical estimate asEQUATION)Update active arm setA ℓ+1 = A ℓ -a ∈ A ℓ : max b∈A ℓ θ ℓ , b -a > 2 -ℓ+1 .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 ℓ = 1, 2, . . ., and in each phase ℓ, the algorithm first computes a design π ℓ ∈ ∆(A ℓ ) over all active arms where ∆(A ℓ ) is the set of all Radon probability measures over set A ℓ . 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 a ∈ A ℓ for m ℓ (a) times and updates the active arm set by using the estimates in this phase.Let us define T ℓ be a set that contains all rounds in phase ℓ andEQUATION)Lemma D.11. For all ℓ ∈ N and all a ∈ A ℓ , ∥a∥2 V -1 ℓ ≤ 2d m ℓ holds.Proof. For each ℓ ∈ N and a ∈ A ℓ , one can show∥a∥ 2 V -1 ℓ = a T V -1 ℓ a ≤ a T m ℓ a∈A ℓ π ℓ (a)aa ⊤ -1 a ≤ 2d m ℓ ,where the first inequality follows from Eq. ( 15) and the fact that if we let A = m ℓ a∈A ℓ π ℓ (a)aa ⊤ and B = V ℓ then, ∥a∥ A -1 ≥ ∥a∥ B -1 holds since A -1 ⪰ B -1 and the second inequality uses Eq. ( 13).Definition D.12. Let E be the event that θ ℓ -θ, a ≤ 2 -ℓ holds for all ℓ ∈ N and all a ∈ A ℓ .Lemma D.13. P(E) ≥ 1 -δ.Proof. Consider a fixed phase ℓ and a fixed arm a ∈ A ℓ . We start from the following decomposition.θ ℓ -θ, a = V -1 ℓ t∈T ℓ A t X t,At -θ, a = V -1 ℓ t∈T ℓ A t A T t θ + η t -θ, a = V -1 ℓ t∈T ℓ A t η t , a = t∈T ℓ V -1 ℓ A t , a η t .By Eq. (20.2) of [Lattimore and Szepesvári, 2020] , we have with probability at least 1 -δ/(2ℓ 2 K),θ ℓ -θ, a = t∈T ℓ V -1 ℓ A t , a η t ≤ 2 ∥a∥ 2 V -1 ℓ log(4ℓ 2 K/δ) ≤ 2 d log(4ℓ 2 K/δ) m ℓ ≤ 2 -ℓ ,where the last inequality applies Lemma D.11. Finally, applying union bounds over all a, ℓ completes the proof.Lemma D.14. Suppose that E occurs where E is given in Definition D.12. We have a ⋆ ∈ A ℓ for all ℓ ∈ N.Proof. This can be proved by using induction on ℓ via the same reasoning of Lemma D.3.Lemma D.15. Suppose that E occurs where E is given in Definition D.12. For each arm a with ∆ a > 0, it will not be in A ℓ for all phases ℓ ≥ ℓ a + 1 where ℓ a is the smallest phase such that ∆a 4 > 2 -ℓa .Proof. Consider any arm a with ∆ a > 0. Let ℓ a be the smallest phase such that ∆a 4 > 2 -ℓa and we havemax b∈A ℓa θ ℓa , b -a -2 -ℓa+1 ≥ θ ℓa , a ⋆ -a -2 -ℓa+1 ≥ ⟨θ, a ⋆ -a⟩ -2 -ℓa+2 > ∆ a -4 × ∆ a 4 = 0,where the first inequality follows from Lemma D.14 that a ⋆ ∈ A ℓ for all ℓ.According to the elimination rule, arm a will not be in A ℓ for all phases ℓ ≥ ℓ a +1. Since conditioning on E, this argument holds for every arm a, the proof is complete.Lemma D.16. Let ℓ(t) be the phase in which round t lies. Then, ℓ(t) ≤ log 2 (t + 1) for all t ∈ N.Proof. We prove this by contradiction. Suppose that ∃t ∈ N that ℓ(t) > log 2 (t + 1). Note that we can further assume ℓ(t) ≥ 2 since one can easily verify that for all t such that ℓ(t) = 1, ℓ(t) ≤ log 2 (t + 1) must hold. We havet ≥ a∈A ℓ(t)-1 π ℓ(t)-1 m ℓ(t)-1 ≥ m ℓ(t)-1 ≥ 4d 2 -2(ℓ(t)-1) log 4K(ℓ(t) -1) 2 /δ > d(t + 1) 2 log (4K/δ) > t,where the fourth inequality bounds ℓ(t) in the logarithmic term by ℓ(t) ≥ 2 and bound the other ℓ(t) > log 2 (t + 1) by assumption. Therefore, once a contradiction occurs, the proof is complete.Lemma D.17. Let ℓ(t) be the phase in which round t lies. Suppose that E occurs where E is given in Definition D.12. For all t ∈ N and all a ∈[K], if a ∈ A ℓ(t) , then ∆ a ≤ 512d log 4 log(d)K (log 2 (t + 1)) 2 /δ + 4 3t .Proof. If a ∈ A ℓ(t) is optimal, then, ∆ a = 0 and the claim trivially holds. In what follows, we only consider arm a ∈ A ℓ(t) with ∆ a > 0. From Lemma D.15, if an arm a ∈ A ℓ(t) is with ∆ a > 0, then, ℓ(t) ≤ ℓ a where ℓ a is defined in Lemma D.15. Then, the total number of rounds that such an arm a is active is at mostℓ(t) s=1 a∈As,πs(a)̸ =0 ⌈π s (a)m s ⌉ ≤ ℓ(t) s=1   4d log log(d) + 16 + a∈As,πs(a)̸ =0 π s (a)m s   ≤ 2 ℓ(t) s=1 m s ≤ 8d max log 4Kℓ(t) 2 /δ , log log d + 4 ℓ(t) s=1 1 2 -2s ≤ 8d max log 4K (log 2 (t + 1)) 2 /δ , log log d + 4 ℓa s=1 1 2 -2s ≤ 512d 3∆ 2 a log 4 log(d)K (log 2 (t + 1)) 2 /δ + 4 ,where the first inequality applies ⌈π s (a)m s ⌉ ≤ π s (a)m s + 1 and Eq. ( 13), the second inequality uses the definition of m s (see Eq. ( 15)), the fourth inequality follows from ℓ(t) ≤ ℓ a and Lemma D.16 gives ℓ(t) ≤ log 2 (t + 1), and the last inequality uses ∆a 4 ≤ 2 -(ℓa-1) to apply ℓ a ≤ log 2 ( 8 /∆a). Since this argument holds for each round t and each arm a ∈ A ℓ(t) conditioning on E, the proof is complete.Proof of Theorem 3.2 for PE-linear. Once Lemma D.14 and Lemma D.17 hold, Theorem 3.1 gives that for any fixed δ ∈ (0, 1), PE-linear achieves the ULI guarantee with a functionF ULI (δ, t) = O t -1 2 d log (log(d)K (log(t + 1)) /δ) .Therefore, the proof of Theorem 3.2 for PE-linear is complete.The bonus function that we here consider for lil'UCB is as:EQUATION)The choice of U δ (x) in Eq. ( 16) is slightly different from that of [Jamieson et al., 2014] because we consider for any δ ∈ (0, 1) and they constrain the choice of δ in a more restricted range. The choice of U δ (x) is motivated from another lemma of law of iterated logarithm, given in [Dann et al., 2017, Lemma F.1] with σ 2 = 1/4 as we here consider [0, 1]-bounded rewards. Note that the concentration bounds in [Dann et 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 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 U δ (x) if one adjust constant or change log log(•) to log(•).Algorithm 9 lil'UCB Input: confidence δ ∈ (0, 1) and arm set A.Initialize: play each arm a ∈ A once to update N a (|A| + 1) and µ a (N a (|A| + 1)) for all a ∈ A.for t = |A| + 1, |A| + 2, . . . do Play an arm A t = argmax a∈A { µ a (N a (t)) + U δ (N a (t))} ,where U δ (N a (t)) is given in Eq. ( 16). Update counters N a (t + 1) = N a (t) + 1 for A t = a and N a (t + 1) = N a (t) for all a ̸ = A t . Update empirical means µ At (N At (t + 1)) =µ A t (N A t (t))•N A t (t)+X t,A t N A t (t)+1and µ a (N a (t + 1)) = µ a (N a (t)) for all a ∈ A -{A t }.In the following proof, we consider the following instance. Definition E.1 (Two-armed bandit instance). Consider a two-armed setting with µ 1 > µ 2 . In each round, each arm generates deterministic rewards µ 1 and µ 2 , respectively. The arm gap is ∆ = µ 1 -µ 2 and ∆ ∈ (0, 0.6).According to Lemma E.2, the total number of plays of arm 2 is finite. Therefore, one can find a round t 0 ∈ N that the last play of arm 2 occurs. At the beginning of this round, the algorithm compares µ 1 + U δ (N 1 (t 0 )) and µ 2 + U δ (N 2 (t 0 )). Since arm 2 gets the last play at this round, we haveµ 1 + U δ (N 1 (t 0 )) ≤ µ 2 + U δ (N 2 (t 0 )) ≤ µ 2 + (1 + f (∆))∆,where the last inequality holds due to Lemma E.4 and f (∆) is defined asEQUATION)Rearranging the above, we haveU δ (N 1 (t 0 )) ≤ f (∆)∆, which immediately leads to N 1 (t 0 ) ≥ log log log(6/δ) f 2 (∆)∆ 2 + log(6/δ) f 2 (∆)∆ 2 .Moreover, since arm 2 is played at round t 0 , ∆ = ∆ At 0 , which further implies thatt 0 = N 1 (t 0 ) + N 2 (t 0 ) > N 1 (t 0 ) > log log log(6/δ) f 2 (∆)∆ 2 + log(6/δ) f 2 (∆)∆ 2 ≥ log log log(6/δ) ∆ 2 + log(6/δ) 2 3∆ 4 = log log log(6/δ) ∆ 2 + log(6/δ) 2 3∆ 4 At 0 ,where the third inequality uses f (∆) ≤ 1 for all ∆ ∈ (0, 0.6), and the last equality holds due to ∆ = ∆ At 0 (recall that in round t 0 , arm 2 gets the last play).Rearranging the above, we have∆ At 0 > log log log(6/δ) ∆ 2 + log(6/δ) (3t 0 ) 1 4 = (3t 0 ) 1 2 log log log(6/δ) ∆ 2 + log(6/δ) 3t 0 .Finally, by Lemma E.3, we have t 0 = Ω(∆ -2 ), which completes the proof.Lemma E.2. Suppose that we run Algorithm 9 for the two-armed bandit instance given in Definition E.1. For any δ ∈ (0, 1), suboptimal arm 2 will be played at most    2 log log 16 log(6/δ) ∆ 2 + log(6/δ) ∆ 2     .Proof. Note that for any fixed δ ∈ (0, 1), function U δ (x) is monotonically-decreasing for x ≥ 6. To show the claimed result, it suffices to find an integer x ≥ 6 such thatU δ (x) < ∆.Now, we consider the following choice.N = ⌈n⌉ , where n = 2 log log 16 log(6/δ)∆ 2 + log(6/δ) ∆ 2Notice that N ≥ n ≥ 6 for all ∆ ∈ (0, 1]. Then, one can showU δ (N ) ≤ U δ (n) = ∆ • log log 2(log log( 16 log(6/δ) ∆ 2)+log(6/δ)) where the first inequality uses the fact that for any fixed δ ∈ (0, 1), U δ (x) is monotonically-decreasing for x ≥ 6, the second inequality uses x + y ≤ 2xy for all x, y > 1 (here x = log(6/δ) and y = log log 16 log(6/δ) ∆ 2∆ 2 + log (6/), the last inequality first bounds 1 4 log log 16 log(6/δ) ∆ 2≤ 16 log(6/δ) ∆ 2 and then uses 2x ≤ x 2 for all x ≥ 2 with x = log 16 log(6/δ) ∆ 2 ≥ 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 the following lemmas. Lemma E.3. Suppose that we run Algorithm 9 for the two-armed bandit instance given in Definition E.1. Let n + 1 be the total number of plays of arm 2. Then,n ≥     log log log(6/δ) ∆ 2 + log(6/δ) ∆ 2     ≥ 6.Proof. For shorthand, we defineEQUATION)With this definition and ∆ ∈ (0, 0.6), we have m ≥ 6 and ⌊m⌋ ≥ 6. Now, we show that n ≥ ⌊m⌋. To this end, it suffices to show U δ (⌊m⌋) > ∆. As U δ (x) is monotonically-decreasing for all x ≥ 6 and m ≥ ⌊m⌋ ≥ 6, we haveU δ (⌊m⌋) ≥ U δ (m) = ∆ • log log log log( log(6/δ) ∆ 2)+log(6/δ)∆ 2 + log(6/δ) log log log(6/δ) ∆ 2 + log(6/δ) > ∆,where the last inequality holds as log(6/δ) ∆ 2> log(6) ∆ 2 > e. Once U δ (⌊m⌋) > ∆ 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 we run Algorithm 9 for the two-armed bandit instance given in Definition E.1. Let n + 1 be the total number of plays of arm 2. The following holds.U δ (n) ≤ ∆   1 + ∆ 3 log log log(6/δ) ∆ 2 + log(6/δ)    .Proof. From Lemma E.3, we have n ≥ 6, and thus U δ (n) ≥ U δ (n + 1) as U δ (x) is monotonically decreasing for all x ≥ 6. Using the fact that for all a ≥ b ≥ 0, a -b ≤ √ a 2 -b 2 (here a = U δ (n) and b = U δ (n + 1)), one can show that U δ (n) -U δ (n + 1) = logSince for any fixed δ ∈ (0, 1), U δ (x) is monotonically-decreasing for all x ≥ 6, and thus by using the definition of m (see Eq. ( 18)), one can show thatU δ (n) -U δ (n + 1) ≤ log log (⌊m⌋) + log (6/δ) ⌊m⌋ (⌊m⌋ + 1) ≤ log log (m) + log (6/δ) m 2 = ∆ 2 log log log(6/δ) ∆ 2 + log(6/δ) • log log   log log log(6/δ) ∆ 2 + log(6/δ) ∆ 2   + log (6/δ) ≤ ∆ 2 log log log(6/δ) ∆ 2 + log(6/δ) • log 2 log log(6/δ) ∆ 2 + log (6/δ) ≤ ∆ 2 log log log(6/δ) ∆ 2 + log(6/δ) • 3 log log log(6/δ) ∆ 2 + log (6/δ) ≤ √ 3∆ 2 log log log(6/δ) ∆ 2 + log(6/δ), where the first inequality uses Eq. ( 19) with n ≥ ⌊m⌋ ≥ e and U δ (x) is monotonically decreasing for all x ≥ 6, the second inequality upper-bounds ⌊m⌋ ≤ m in numerator and lower-bounds ⌊m⌋ (⌊m⌋ + 1) ≥ m 2 , the third inequality follows fromlog log log(6/δ) ∆ 2 + log(6/δ) ∆ 2 ≤ log(6/δ) ∆ 2 + log(6/δ) ∆ 2 ≤ log(6/δ) ∆ 2 2 ,and the fourth inequality follows 2x ≤ x 3 for all x ≥ √ 2 with x = log log(6/δ)∆ 2 ≥ √ 2 (∆ ∈ (0, 0.6)).After arm 2 gets n + 1 times play, it will not be played anymore, which implies that U δ (n + 1) < ∆.Using this bound givesU δ (n) ≤ ∆ + ∆ 2 3 log log log(6/δ) ∆ 2 + log(6/δ).Therefore, we complete the proof.We will show that the traditional optimistic algorithms fail to achieve the ULI guarantee due to the log t term in the bonus. At a high level, log t is increasing with time and forces the algorithm to play a bad arm indefinitely when t evolves. We provide the formal proof in the following:We prove the claim by contradiction. Consider a K-armed bandit instance with at least one suboptimal arm, and let ∆ > 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 δ ∈ (0, 1), with probability ≥ 1 -δ, for all t ∈ N, ∆ t ≤ F U LI (δ, t). Based on Definition 2.5, we have lim t→∞ F U LI (δ, t) = 0 and F U LI (δ, t) is monotonically decreasing w.r.t. t after a threshold. Thus, ∃t 0 ∈ N such that F U LI (δ, t) < ∆ for all t ≥ t 0 . In other words, the algorithm cannot play any suboptimal arm after t 0 -th round. Recall that the bonus term is 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.Algorithm 10 Meta-algorithm towards ULI Input: δ ∈ (0, 1), finite arm set A, and base-algorithm Alg with function g(δ) that satisfies Condition. F.1.Initialize: A 1 = [K]. for m = 1, 2, . . . do Set duration T m = ⌈576g m 2 m ⌉ where g m = g δ 2m 2 .Run Alg with active arm set A m for T m rounds and construct ℓ t,a = ℓt,a•I{At=a} pt,a for all t, a in this phase.Update active arm set A m+1 = A m -B m where:EQUATIONand T m is a set that contains all rounds in phase m and k is the empirical best arm:k ∈ argmin a∈Am s∈Tm ℓ s,aF Achieving ULI by Adversarial Bandit Algorithms F.1 Meta-algorithm Enabling Adversarial Algorithms to Achieve ULIIn this subsection, we propose a meta-algorithm shown in Algorithm 10 which enables any highprobability adversarial algorithm, with a mild condition, to achieve the ULI guarantee. Then, we show that existing high-probability 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 ℓ t,a = 1 -X t,a . Note that all algorithms in this subsection require [0, 1]-boundedness assumption on loss.At a high-level, our meta-algorithm keeps running a base-algorithm Alg to play arms and collects rewards. The meta-algorithm uses collected rewards to construct the importance-weighted (IW) estimator ℓ t,a = ℓt,a•I{At=a} pt,afor each t, a, which helps to eliminate bad arms, and then runs Alg on a reduced arm space. To achieve the ULI guarantee, our meta-algorithm requires the input base-algorithm to satisfy the following: Condition F.1. An algorithm Alg runs for given consecutive T rounds with a finite arm set A and a fixed δ ∈ (0, 1). At each round t ∈ [T ], Alg maintains a distribution p t over A and samples an arm A t ∼ p t . With probability at least 1 -3 5 δ, Alg ensures for all a ∈ A,EQUATIONwhere g(δ) is a positive-valued function, monotonically decreasing for all δ ∈ (0, 1), polynomial in log(1/δ), and g(δ) ≥ log (10|A|/δ) , ∀δ ∈ (0, 1).In fact, many high-probability 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(δ) = O |A| log(|A|/δ) (omitted proof can be found in Appendix F) and Lee et al. [2021] show that GEOMETRICHEDGE.P [Bartlett et al., 2008] with John's exploration meets the condition for linear bandits with g(δ) = O d log(|A|/δ) . Hence, feeding those algorithms to Algorithm 10 yields the following:Theorem F.2. For any fixed δ ∈ (0, 1), if Algorithm 10 uses • EXP3.P as a base-algorithm, then, for K-armed bandit, ULI guarantee is achieved withF ULI (δ, t) = O t -1 2 K log (δ -1 K log(t + 1)) .• GEOMETRICHEDGE.P as a base-algorithm then for linear bandits with K arms, ULI guarantee is achieved withF ULI (δ, t) = O t -1 2 d log (δ -1 K log(t + 1)) .Theorem F.2 suggests that Algorithm 10 enables EXP3.P and GEOMETRICHEDGE.P to achieve nearoptimal 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 δ ∈ (0, 1), if Algorithm 10 uses • EXP3.P as a base-algorithm, then, for K-armed bandit, ULI guarantee is achieved withF ULI (δ, t) = O t -1 2 K log (δ -1 K log(t + 1)) .• GEOMETRICHEDGE.P as a base-algorithm then for linear bandits with K arms, ULI guarantee is achieved withF ULI (δ, t) = O t -1 2 d log (δ -1 K log(t + 1))We decompose the proof of Theorem F.2 into two parts. In the first part, we first show that any algorithm with Condition. F.1 for some δ ∈ (0, 1) can achieve the ULI guarantee. Then, we only need to show that EXP3.P and GEOMETRICHEDGE.P satisfy Condition. F.1, 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.1. Theorem F.4. For any fixed δ ∈ (0, 1), if Algorithm 10 uses a base-algorithm that satisfies Condition. F.1, then, it achieves the ULI guarantee thatP   ∀t ∈ N : ∆ At = O   g δ -1 log 2 (t + 1) t     ≥ 1 -δ.We 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 1 to achieve the ULI. We first show that the optimal arm will not be eliminated, i.e., a ⋆ ∈ A m for all phases m ∈ N. To show this, we only need showEQUATIONwhich does not meet the elimination rule in Eq. ( 20).For analysis purpose, we decompose Eq. ( 22) asEQUATION)The first and the third term in Eq. ( 23) can be handled thanks to the bound on t ( ℓ t,a -ℓ t,a ) 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 a round t, then, for all active arms a ∈ A t , ∆ a is bounded by a function, monotonically decreasing for large t. This can be proved again via a similar decomposition of Eq. ( 23) to gets∈Tm ℓ s,a -ℓ s,k ≥ 0.5T m ∆ a -5 g m T m .Therefore, for some large T m such that 0.5T m ∆ a -5 √ g m T m > 7 √ g m T m , bad arms will be eliminated. Putting two pieces together, we complete the proof.With Theorem F.4 in hand, our next objective is to show that EXP3.P and GEOMETRICHEDGE.P 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 it. The full proof can be found in Appendix F.3. Proposition F.5. In MAB setting, for any δ ∈ (0, 1), EXP3.P with given arm set A, satisfies Condition. F.1 with g(δ) = O (|A| log (|A|/δ)).The key that EXP3.P as well as GEOMETRICHEDGE.P can fulfill Condition. F.1 is because it adds a small amount of probability for uniform exploration to each arm. Therefore, the importance-weighted (IW) estimator can be lower-bounded and the term t ( ℓ t,a -ℓ t,a ) will not be too large.Apart from EXP3.P for MAB and GEOMETRICHEDGE.P for linear bandits, Lee et al. [2021] show that refined version of SCRIBLE [Lee et al., 2020] can be used as a base-algorithm for Algorithm 10 to achieve the ULI guarantee for linear bandits, but the ULI guarantee is inferior to that of GEOMETRICHEDGE.P (i.e., inferior F ULI w.r.t. d).F.2 Proof of Theorem F.4Lemma F.6. If Algorithm 10 accepts a base-algorithm which satisfies Condition. F.1 as an input, then, with probability at least 1 -3 5 δ, for all m ∈ N and a ∈ A m , s∈TmEQUATIONProof. 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 set A m ⊆ A, then, with probability at least1 -3 5 δ ′ , for all a ∈ A m s∈Tm (ℓ s,As -ℓ s,a ) ≤ g(δ ′ )T m -2 s∈Tm ℓ s,a -ℓ s,a .By setting δ ′ = δ/(2m 2 ) for phase m and applying a union bound over all m ∈ N, we complete the proof.Recall from the second bullet of Condition. F.1 that g(δ ′ ) ≥ log (10|A|/δ ′ ) , ∀δ ′ ∈ (0, 1).As the above holds for all δ ′ ∈ (0, 1), according to the definition g m = g(δ/(2m 2 )), we also have thatEQUATION)Lemma F.7. With probability at least 1 -δ/5, for all m ∈ N and a ∈ A m , we haveEQUATION)Proof. Consider any fixed m and a ∈ A m . By applying Hoeffding's inequality with probability at least1 -δ ′ , s∈Tm ℓ s,a - s∈Tm (1 -µ a ) ≤ T m log(2/δ ′ ) 2 .Choosing δ ′ = δ/(10|A|m 2 ), applying union bounds over all m ∈ N and a ∈ A m , and using Eq. ( 25), we complete the proof.Lemma F.8. With probability at least 1 -δ/5, for all m ∈ N, we have s∈Tm ℓ s,As -EQUATION)Proof. Consider a fixed m. For each round s in this phase, let us defineM s = ℓ s,As -E s [ℓ s,As ] = a∈Am (ℓ s,a B s,a -p s,a (1 -µ a )) .By applying Azuma-inequality with the fact that |M s -M s-1 | ≤ 2 for all s and also using a union bound over all m ∈ N, with probability at least 1 -δ/5, for all m ∈ N s∈Tm ℓ s,As -s∈Tm a∈Am p s,a (1 -µ a ) ≤ 8T m log(20m 2 /δ) ≤ 8g m T m ,where the last inequality uses Eq. ( 25), which thus completes the proof.Definition F.9. Let E be the event in which the concentration inequalities in Lemma F.6, Lemma F.7, and Lemma F.8 hold simultaneously.By a union bound, we have the following fact.Fact. With the definition of E in Definition F.9, E occurs with probability at least 1 -δ. Lemma F.10. Suppose that E occurs where E is defined Definition F.9, and then for all m ∈ N and a ∈ A m ,2 s∈Tm ℓ s,a -ℓ s,a ≤ 5 g m T m + T m ∆ a .Proof. Conditioning on E, for each m ∈ N and a ∈ A m , one can show2 s∈Tm ℓ s,a -ℓ s,a ≤ g m T m + s∈Tm (ℓ s,a -ℓ s,As ) ≤ g m T m - s∈Tm j∈Am p s,j (1 -µ j ) + 8g m T m + s∈Tm (1 -µ a ) + g m T m 2 ≤ 5 g m T m + s∈Tm j∈Am p s,j (µ j -µ a ) ≤ 5 g m T m + T m ∆ a ,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 µ j ≤ µ ⋆ for all j.Corollary F.11. Suppose that E occurs where E is defined Definition F.9, and then for all m ∈ N and a ∈ A, we haveEQUATIONEQUATION)Proof. The proof is immediate by applying Lemma F.7.Lemma F.12. Suppose that E occurs where E is defined Definition F.9, and then a ⋆ ∈ A m for all m ∈ N.Proof. We prove the claimed result by induction. For the base case, the claim holds for the first phase m = 1 as A 1 = A. Suppose that a ⋆ ∈ A m . Then, we show that a ⋆ will not be eliminated at the end of phase m, thereby active for phase m + 1. Then, we haves∈Tm ℓ s,a ⋆ -ℓ s,k = s∈Tm ℓ s,a ⋆ -ℓ s,a ⋆ + s∈Tm (ℓ s,a ⋆ -ℓ s,k ) + s∈Tm ℓ s,k -ℓ s,k ≤ 5 2 g m T m + -T m ∆ k + 2g m T m + 1 2 5 g m T m + T m ∆ k = 13 2 g m T m -0.5T m ∆ k < 7 g m T m ,where the first inequality uses Lemma F.10 together with ∆ a ⋆ = 0 and Corollary F.11.Once the induction is done, we complete the proof (recall the elimination rule in Algorithm 10).Lemma F.13. Suppose that E occurs where E is defined Definition F.9. For each arm a ∈ A with ∆ a > 0, it will not be in A m for all m ≥ m a + 1, where m a is the smallest phase such that2 ma > 1 ∆ 2 a .Proof. Consider fixed phase m and arm a ∈ A with ∆ a > 0. Suppose that arm a is still active in an phase m. One can showEQUATIONwhere the first inequality holds since Lemma F.12 implies that a ⋆ ∈ A m for all m ∈ N, and the second inequality uses Lemma F.10 together with ∆ a ⋆ = 0 and Corollary F.11.Let m a be the minimum phase such that2 ma > 1 ∆ 2 a (i.e., 2 ma-1 ≤ 1 ∆ 2 a), which further gives thatT ma = ⌈576g ma 2 ma ⌉ ≥ 576g ma 2 ma > 576g ma ∆ 2 a .Hence, by the definition of m a , we haveT m > 576gm ∆ 2 a for all m ≥ m a , which gives that T m ∆ a > 24 √ g m T m for all m ≥ m a .Plugging this into Eq. ( 30), we arrive ats∈Tm ℓ s,a -ℓ s,k ≥ 0.5T m ∆ a -5 g m T m > 7 g m T m ,which implies that arm a will not be active in all phases m ≥ m a + 1 according to the elimination rule.Finally, one can repeat this argument for each a ∈ A with ∆ a > 0 conditioning on E.Lemma F.14. Let m(t) be the phase in which round t lies. Then, m(t) ≤ log 2 (t + 1) for all t ∈ N.Proof. We prove this by contradiction. Suppose that ∃t ∈ N that m(t) > log 2 (t + 1). Note that we can further assume m(t) ≥ 2 since one can easily verify that for all t such that m(t) = 1, m(t) ≤ log 2 (t + 1) must hold. Recall that in phase m(t), each active arm will be played for m ℓ(t) times, we havet ≥ T m(t)-1 ≥ 576g m(t)-1 2 m(t)-1 > 288(t + 1)g m(t)-1 > t,where the third inequality bounds ℓ(t) > log 2 (t + 1) by assumption. Therefore, once a contradiction occurs, the proof is complete.Lemma F.15. Let m(t) be the phase in which round t lies. Suppose that E occurs. For all t ∈ N and all a ∈ A, if a ∈ A m(t) , then,∆ a ≤ 4608g(δ/(2 log 2 2 (t + 1))) t .Proof. If a ∈ A m(t) is optimal, then, ∆ a = 0 and the claim trivially holds. In what follows, we only consider arm a ∈ A m(t) with ∆ a > 0. Then, t can be bounded byt ≤ m(t) n=1 ⌈576g n 2 n ⌉ ≤ 1152 m(t) n=1 g n 2 n ≤ 1152g m(t) m(t) n=1 2 n ≤ 1152g m(t) ma n=1 2 n ≤ 4608g m(t) ∆ 2 a ,where the second inequality simply bounds ⌈576g n 2 n ⌉ ≤ 2 × 576g n 2 n for all phases n, the fourth inequality holds because Lemma F.13 implies that if a ∈ A m(t) , then, m(t) ≤ m a holds, and the last inequality uses 1∆ 2 a ≥ 2 ma-1 .Since for any fixed δ ∈ (0, 1), g(δ/x 2 ) is monotonically increasing for x ≥ 1 (recall Condition. F.1) and Lemma F.14 gives m(t) ≤ log 2 (t + 1), we haveg m(t) = g(δ/(2m(t) 2 )) ≤ g(δ/(2 log 2 2 (t + 1))), which gives t ≤ 4608g(δ/(2 log 2 2 (t+1))) ∆ 2 a .Conditioning on E, this argument holds for each t, a, which completes the proof.Proof of Theorem F.4. Once Lemma F.12 and Lemma F.15 hold, and g(x) is polynomial in log(1/x), Theorem 3.1 gives that for any fixed δ ∈ (0, 1), Algorithm 10 achieves the ULI guarantee with a functionF ULI (δ, t) = O   g(δ/(2 log 2 2 (t + 1))) t   .According to the first bullet of Condition. F.1, the proof is complete.In this section, we prove that EXP3.P [Auer et al., 2002b] meets Condition. F.1. In our setting, arm set is A = [K], and the loss ℓ t,a generated by each arm a at each round t is assumed to be [0, 1]-bounded.Algorithm 11 EXP3.P Input: Time horizon T , arm set [K], confidence δ ∈ (0, 1). Initialize: ∀a ∈ [K], w 1,a = 1 and parameters η = η δ (T ), γ = γ δ (T ), β = β δ (T ) according to Eq. ( 33). for t = 1, 2, . . . , T do Play an arm A t ∈ [K] from distribution p t = [p t,1 , . . . , p t,K ] and observe loss ℓ t,At whereEQUATIONUpdate w t+1,a = w t,a exp(-η ℓ t,a ) for all a ∈ [K] withℓ t,a = ℓ t,a - 2β p t,a, where ℓ t,a = ℓ t,a B t,a p t,a , andEQUATIONThe pseudocode of EXP3.P is given in Algorithm 11 and we briefly review its procedure. Ahead of time, EXP3.P accepts a fixed time horizon T ∈ N arm set [K], and confidence δ ∈ (0, 1) as inputs.At each round t ∈ [T ], EXP3.P pulls an arm A t ∼ p t from a distribution p t = [p t,1 , . . . , p t,K ], and then observes the loss ℓ t,At . The probability of playing an arm a at round t is (1 -γ)wt,a Wt + γ Kwhere γ > 0 is a fixed parameter, which encourages the exploration, w t,a is the weight of arm a, and W t = a∈[K] w t,a . After pulling the arm, the algorithm uses the observed reward to construct the shifted IW-estimators ℓ t,a according to Eq. ( 32), and finally uses the shifted IW-estimators to update the weight w t,a for each arm.The parameters of γ δ (T ), η δ (T ), β δ (T ) are as a function T , given asEQUATIONLet E t [•] 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 t } T t=1 be a sequence of random variables adapted to filtration {F t } T t=1 and let β > 0 such that βX t ≤ 1 almost surely for all t ∈ [T ]. With probability at least 1 -δ,T t=1 (X t -E t [X t ]) ≤ β T t=1 E t [X 2 t ] + log(1/δ) β .Corollary F.17. With probability at least 1 -δ/5, for all a ∈ [K],T t=1 ℓ t,a -ℓ t,a ≤ log(5K/δ) β .Proof. Consider a fixed arm a. For all t, a, we have ℓ t,a ∈ [0, 1], and thusEQUATIONThen, we check β ℓ t,a ≤ 1 almost surely for all t ∈ [T ]. Specifically, we use p t,a ≥ γ/K to showβ ℓ t,a = β B t,a ℓ t,a p t,a ≤ β 1 p t,a ≤ βK γ = 1,where the last equality holds due to β = γ/K according to Eq. ( 33).For the fixed a, applying Lemma F.16 with X t = ℓ t,a , we have that with probability at least1 -δ ′ T t=1 ℓ t,a -ℓ t,a = T t=1 ℓ t,a -ℓ t,a - T t=1 2β p t,a ≤ β T t=1 1 p t,a + log(1/δ ′ ) β - T t=1 2β p t,a ≤ log(1/δ ′ ) β .Choosing δ ′ = δ/(5K) and applying a union bound over all a ∈ [K] yield the claimed bound.Lemma F.18. With probability at least 1 -δ/5, for all a ∈ [K], we haveEQUATION)Proof. Consider any fixed arm a. By applying Hoeffding's inequality with probability at least1 -δ ′ , T t=1 ℓ s,a - T t=1 (1 -µ a ) ≤ T log(2/δ ′ ) 2 .Choosing δ ′ = δ/(5K) and applying a union bound over all arms, we complete the proof.Lemma F.19 (Freedman's inequality). Let {X t } T t=1 be a martingale difference sequence with respect to filtration {F t } T t=1 and |X t | ≤ M almost surely for all t. Then, for any δ ∈ (0, 1), with probability at least 1 -δ,T t=1 X t ≤ 2M 3 log(2/δ) + 2 log(2/δ) T t=1 E t [X 2 t ].Corollary F.20. With probability at least 1 -δ/5, the following holds for all a,T t=1 ℓ t,a -(1 -µ a ) ≤ 2 log(10K/δ) 3 K γ + 2 log(10K/δ) T t=1 1 p t,a .Proof. Consider a fixed arm a. Let M t,a = ℓ t,a -(1 -µ a ) and {M t,a } T t=1 is a martingale difference sequence. We have E t [M t,a ] = 0, |M t,a | ≤ K γ and alsoT t=1 E t M 2 t,a ≤ T t=1 E t ℓ 2 t,a ≤ T t=1 1 p t,a ,where the last step holds due to Eq. (34).By Lemma F.19 and a union bound over all a, with probability at least 1 -δ ′ for all aT t=1 ℓ t,a -(1 -µ a ) ≤ 2 log(2K/δ ′ ) 3 K γ + 2 log(2K/δ ′ ) T t=1 1 p t,a.Choosing δ ′ = δ/5 completes the proof.Definition F.21. Let E 0 be the event in which all inequalities of Corollary F.17, Lemma F.18, and Corollary F.20 hold simultaneously. With this definition, E 0 occurs with probability at least 1 -3δ 5 . Lemma F.22. Let θ 0 be an arbitrary constant such that θ 0 ≥ 1. Suppose that E 0 occurs where E 0 is defined in Definition F.21, and then for all a ∈ [K], we haveEQUATIONProof. Let θ 0 > 0 be an arbitrary constant. By Corollary F.20, for all a ∈EQUATIONwhere the second inequality uses√ 2ab ≤ a + b for all a, b ≥ 0.Moreover, by the triangle inequality, we haveEQUATIONwhere the last inequality applies Lemma F.18 and uses Eq. ( 38).Rearranging the above gives- T t=1 β p t,a ≤ -θ 0 T t=1 ℓ t,a -ℓ t,a + 2θ 0 log(10K/δ) 3 K γ + θ 2 0 log(10K/δ) β + θ 0 T log (10K/δ) 2 .Finally, if we constrain θ 0 ≥ 1, thenT t=1 ℓ t,a -ℓ t,a = T t=1 ℓ t,a -ℓ t,a - T t=1 2β p t,a ≤ 2 log(10K/δ) 3 K γ + θ 0 log(10K/δ) β + T log (10K/δ) 2 + 1 θ 0 T t=1 βℓ t,a p t,a - T t=1 2β p t,a ≤ 2 log(10K/δ) 3 K γ + θ 0 log(10K/δ) β + T log (10K/δ) 2 - T t=1 β p t,a ,where the first inequality uses Eq. ( 39) and the last one bounds θ 0 ≥ 1.Since this argument holds for all a ∈ [K] conditioning on E 0 , we complete the proof.Lemma F.23. The following holds for all t ∈ [T ].K a=1 p t,a ℓ 2 t,a ≤ K a=1 ℓ t,a + 4K 2 β 2 γ .Proof. For any fixed t, we can showK a=1 p t,a ℓ 2 t,a = K a=1 p t,a ℓ t,a - 2β p t,a = K a=1 p t,a ℓ 2 t,a - 4β p t,a ℓ t,a + 4β 2 p 2 t,a = K a=1 p t,a ℓ t,a ℓ t,a - 4β p t,a + K a=1 4β 2 p t,a ≤ K a=1 p t,a ℓ t,a ℓ t,a + 4K 2 β 2 γ ≤ K a=1 ℓ t,a + 4K 2 β 2 γ ,where the first inequality uses ℓ t,a -4β pt,a ≤ ℓ t,a -2β pt,a = ℓ t,a and p t,a ≥ γ K , and the last inequality bounds p t,a ℓ t,a ≤ 1 for each a ∈ [K]. Since the claim deterministically holds for all t, the proof is complete.Lemma F.24. The following holds for all arms k ∈[K]. T t=1 K a=1 p t,a ℓ t,a - T t=1 ℓ t,k ≤ log(K) η + 2η K a=1 T t=1 ℓ t,a + 4T Kβ 2 .Proof. Let us defineΦ 0 = 0, Φ t = 1 -γ η log 1 K K a=1 exp -η t s=1 ℓ s,a , ∀t ≥ 1.With this definition, one can show for t ≥ 2Φ t -Φ t-1 = 1 -γ η log   K a=1 exp -η t s=1 ℓ s,a K a=1 exp -η t-1 s=1 ℓ s,a   = 1 -γ η log   K a=1 exp -η t-1 s=1 ℓ s,a K a=1 exp -η t-1 s=1 ℓ s,a exp -η ℓ t,a   = 1 -γ η log K a=1 w t,a W t exp -η ℓ t,a ≤ 1 -γ η log K a=1 w t,a W t 1 -η ℓ t,a + η 2 ℓ 2 t,a = 1 -γ η log 1 + η K a=1 w t,a W t η ℓ 2 t,a -ℓ t,a = 1 -γ η log 1 + η 1 -γ K a=1 p t,a - γ K η ℓ 2 t,a -ℓ t,a ≤ - K a=1 p t,a - γ K ℓ t,a + η K a=1 p t,a - γ K ℓ 2 t,a ≤ - K a=1 p t,a ℓ t,a + γ K K a=1 ℓ t,a + η K a=1 p t,a ℓ 2 t,a ,where the first inequality uses e -x ≤ 1 -x + x 2 whenever x ≥ -1 (here we repeat x = η ℓ t,a for every a), and the second inequality follows from log(1 + x) ≤ x for all x > -1.By summing over all t and using Lemma F.23 with η = γ K , the above result yieldsT t=1 K a=1 p t,a ℓ t,a ≤ T t=1 (Φ t-1 -Φ t ) + η T t=1 K a=1 ℓ t,a + η T t=1 K a=1 p t,a ℓ 2 t,a ≤ T t=1 (Φ t-1 -Φ t ) + 2η T t=1 K a=1 ℓ t,a + 4T Kβ 2 .As Φ 0 = 0 and 1 -γ ≤ 1, we have for an arbitrary arm k ∈ [K],T t=1(Φ t-1 -Φ t ) = -Φ T ≤ (1 -γ) log(K) η - 1 -γ η log K a=1 exp -η T t=1 ℓ t,a ≤ (1 -γ) log(K) η - 1 -γ η log exp -η T t=1 ℓ t,k ≤ log(K) η + T t=1 ℓ t,k .As this argument deterministically holds for all k ∈ [K], we complete the proof.Proof of Proposition F.5. The following analysis will condition on event E 0 which is defined in Definition F.21. As mentioned in Definition F.21, this event occurs with probability at least 1 -3 5 δ. We first note that for all t, a Recall that we choose parameters asEQUATIONIn what follows, we consider T > 4K log(10K/δ)8 . In this case, we have η, γ, β ∈ (0, 1 2 ]. Then, for an arbitrary arm k ∈ [K], we pick θ 0 = 2 and show T t=1(ℓ t,At -ℓ t,k ) = T t=1 K a=1 p t,a ℓ t,a -ℓ t,k + 2βKT ≤ T t=1 K a=1 p t,a ℓ t,a -ℓ t,k TERM 1 + 2βKT + 2 log(10K/δ) 3 K γ + 2 log(10K/δ) β + T log (10K/δ) 2 TERM 2 + (-β) T t=1 ℓ t,k p t,k TERM 3, where the equality uses Eq. ( 40) and the inequality applies Lemma F.22.We first apply Lemma F.24 to bound TERM 1 asTERM 1 ≤ log(K) η + 2η K a=1 T t=1 ℓ t,a + 4T Kβ 2 ≤ log(K) η + 2η K a=1 T t=1 ℓ t,a + log(10K/δ) β + 4T Kβ 2 ≤ log(K) η + 2ηKT + 2ηK log(10K/δ) β + 4T Kβ 2 ≤ 3 KT log(10K/δ) + 2K log(10K/δ) + 4 log(10K/δ) ≤ 6 KT log(10K/δ),where the second inequality uses Corollary F.17, the third inequality uses i ℓ t,a ≤ K, and the last inequality uses T ≥ 4K log(10K/δ) (i.e., K ≤ KT 4 log(10K/δ) ).Then, we use K/γ = 1/η to bound TERM 2:TERM 2 = 2βKT + 2 log(10K/δ) 3η + 2 log(10K/δ) β + T log (10K/δ) 2 = 2 KT log(10K/δ) + 2 3 KT log(10K/δ) + 2 KT log(10K/δ) + T log(10K/δ) 2 ≤ 14 3 KT log(10K/δ) + T log(10K/δ) 2 .Finally, we apply Eq. ( 36) with θ 0 = 2 to bound TERM 3.TERM 3 ≤ -2 T t=1 ℓ t,k -ℓ t,k + 4 log(10K/δ) 3η + 4 log(10K/δ) β + 2T log (10K/δ) = -2 T t=1 ℓ t,k -ℓ t,k + 16 3 KT log(10K/δ) + 2T log(10K/δ).Putting bounds of TERM 1, TERM 2, and TERM 3 together givesT t=1 (ℓ t,At -ℓ t,k ) ≤ -2 T t=1 ℓ t,k -ℓ t,k + 16 KT log(10K/δ) + 3 √ 2 2 T log(10K/δ) ≤ -2 T t=1 ℓ t,k -ℓ t,k + 19 KT log(10K/δ).As this argument holds for all k ∈ [K] conditioning on E 0 , the proof is thus complete.F.4 Proof of Theorem F.2For EXP3.P, we apply g(δ) = O (K log (K/δ)) 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(K/δ). Note that this is slightly different from d log(K log 2 T /δ) presented in [Lee et al., 2021] . The extra log 2 T term is caused by Lemma 2 of [Bartlett et al., 2008] , a 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. EQUATIONif s i ̸ = NULL then Update a i = s i and I m = I m -{i}.for i = 1, . . . , d do Set s i = LI-Argmax(A, A, θ m , B m-1 , m, C, a ⋆ m ). if s i ̸ = NULL then if |det (s i , A -i )| ≥ C |det(A)| or i ∈ I m then 15Update I m = I m -{i} and a i = s i .Restart this for-loop with current parameters.Return:{a i } d i=1 -∪ i∈Im ei √ Tm .G Omitted Details of Section 4We use e i ∈ R d to denote a vector whose i-th coordinate is one and all others are zero. For any two vectors x, y ∈ R d , x ≤ y indicates that x i ≤ y i holds for each coordinate i. For a positive definite matrix A ∈ R d×d , the weighted 2-norm of vector x ∈ R d is given by ∥x∥ A = √ x ⊤ Ax. For matrix A = [a 1 , • • • , a d ] ∈ R d×d with each a i ∈ R d , we use A -i to denote the (d -1)-tuple of vectors [a 1 , • • • , a i-1 , a i+1 , •, a d ].EQUATIONM m a = ⃗ 0, -⃗ C ≤ B ⊤ m-1 B m-1 -1 B ⊤ m-1 a ≤ ⃗ C.Query oracle to get a -from ( 43) by replacing u with -u. if ⟨u, a + ⟩ = 0 and ⟨u, a -⟩ = 0 then Return: NULL. else Return: argmax b∈{a + ,a -} |⟨u, b⟩|.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 i / √ T m in the i-th column of A. Otherwise, a i will be updated to s i ∈ argmax a∈Am | det(a, A -i )|. We use set I m to record the indices of columns where the replacement fails. According to the conditions in line 14, the second for-loop will be repeatedly restarted to ensure that the linear combination of elements in B m can represent all active arms in A m 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 3 times.Formally, we have the following result. Lemma G.1. Suppose C > 1 and B m is the output of Algorithm 12 in phase m. Then, for all m ∈ N, B m is a C-approximate barycentric spanner of A m .Recall from the previous subsection that Algorithm 12 and LI-Argmax needs to find the empirical best arm a ⋆ m and argmax a∈Am | det(a, A -i )|, both of which rely on the access to the following optimization oracle. Definition G.2 (Optimization oracle). Given a compact set A ⊆ R d , the oracle can solve problems of the form argmaxa∈A ⟨θ, a⟩ , s.t. U a = ⃗ β 1 , V a ≤ ⃗ β 2 , for any β 1 , β 2 ∈ R, θ ∈ R d , U ∈ R τ1×d , V ∈ R τ2×d , where τ 1 , τ 2 are at most O(d).If the optimal solution is not unique, the oracle returns any one of them.We note that the constrained optimization oracles are commonly-used and also crucial for eliminationtype 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 et al., 2008 , Agarwal et al., 2014] , linear constrained oracle, in fact, can be implemented efficiently in many cases (e.g., a common assumption that A is a ball [Plevrakis and Hazan, 2020] ) via the ellipsoid method. We refer readers to [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 to solve the optimization problem argmax a∈Am | det(a, A -i )|, which can be rewritten as follows based on Eq. (3).EQUATIONProblem ( 44) also needs to find the empirical best arm a ⋆ m . A natural idea to compute the empirical best arm a ⋆ m is to solve argmax a∈Am-1 ⟨ θ m , a⟩. Notice that both finding a ⋆ m and solving Eq. ( 44) require to deal with constraint a ∈ A m-1 . However, this constrain prevents us from querying the optimization oracle due to the following reason.Issue: a ∈ A m-1 may cause a large (even infinite) number of constraints. One can rewrite a ∈ A m-1 as:EQUATIONHowever, the evolution of phases blows up the number of constraints in (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 O(d). To address this issue, one needs to remove the dependence on m.Solution: enlarging active arm set A m-1 . Our solution is to slightly enlarge the active arm set A m-1 in Eq. ( 45) so that the enlarged set can be expressed by finitely-many linear constraints, independent of m. Before showing the way to enlarging A m-1 , we first give the following definition. Definition G.3 (C-bounded spanner). For any given set S ⊆ R d and constant C > 0, Span [-C,C] (S), defined as follows, is a set that contains all possible linear combinations from S with coefficients within [-C, C].EQUATIONwhere c s is the coefficient associated with element s.We enlarge A m-1 to A ∩ Span [-C,C] (B m-1 ), and one can easily verify that this is true since ) can be equivalently written asA m-1 ∩ A = A m-1 and Lemma G.1 implies that A m-1 ⊆ Span [-C,C] (B m-1 ).a ∈ R d : M m a = ⃗ 0, -⃗ C ≤ B ⊤ m-1 B m-1 -1 B ⊤ m-1 a ≤ ⃗ C .Hence, LI-Argmax can invoke the optimization oracle in Definition G.2 to solve problems of argmax a∈Am-1 ⟨ θ m , a⟩ and (44) approximately by solving (42) and (43), respectively.Computational efficiency. We mainly focus on two costly steps in Algorithm 12. The first step is to use Gaussian elimination to obtain the matrix M m ∈ R n×d for some n ≤ d. This step can be done with at most O(d 3 ) 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 on the number of times that Algorithm 12 invokes LI-Argmax subroutine. The LI-Argmax will be invoked for d times in the first for-loop. EQUATIONProof. For this proof, we show that a ∈ Span[-C,C] (B m-1 ) if and only if a ∈ H m . We first show that if a ∈ Span [-C,C] (B m-1 ), then a ∈ H m . As matrix M m ∈ R (d-|Bm-1|)×d is defined by Span(B m-1 ) = {x ∈ R d : M m x = ⃗ 0}, a ∈ Span [-C,C] (B m-1 ) ⊆ Span(B m-1 ) gives that M m a = ⃗ 0. Recall that B m-1 ∈ R d×|Bm-1| is a matrix whose the i-th column is the i-th element of set B m-1 and rank(B m-1 ) = |B m-1 | because B m-1 is linearly independent. Therefore, for each a ∈ Span [-C,C] (B m-1), there exists a unique vector10 x a ∈ R |Bm-1| such that B m-1 x a = a and the value of each coordinate of x a is no larger than C. As B m-1 is linearly independent, B m-1 is a full-column rank matrix, which gives thatx a = B ⊤ m-1 B m-1 -1 B ⊤ m-1 a. As a result, if a ∈ Span [-C,C] (B m-1 ), then, -⃗ C ≤ B ⊤ m-1 B m-1 -1 B ⊤ m-1 a ≤ ⃗ C, which concludes the proof of this argument. Then, we show that if a ∈ H m , then, a ∈ Span [-C,C] (B m-1 ). If M m a = ⃗ 0, then, we have a ∈ Span(B m-1 ) due to the definition of M m . As rank(B m-1 ) = |B m-1 |, for each a ∈ Span(B m-1 ), there exists a unique vector x a ∈ R |Bm-1| such that B m-1 x a = a, which gives that x a = B ⊤ m-1 B m-1 -1 B ⊤ m-1 a. Thus, -⃗ C ≤ B ⊤ m-1 B m-1 -1 B ⊤ m-1 a ≤ ⃗ C requires each coordinate of x a no larger than C. As a consequence, if a ∈ H m , then, a ∈ Span [-C,C] (B m-1 ).Combining the above analysis, we complete the proof.In this section, we aim to show that B m is a C-approximate barycentric spanner of A m . To this end, we first show that B m is a C-approximate barycentric spanner of S m which is defined below and A m ⊆ S m results in the desired claim. In fact, throughout our analysis, we stick with S m rather than A m .S 1 = A, S m = a ∈ A : θ m , a ⋆ m -a ≤ 2 -m+1 , a ∈ Span [-C,C] (B m-1 ) , ∀m ≥ 2. (48)Moreover, according to Lemma G.4, for all m ≥ 2, S m can also be equivalently rewritten as: Step 1: each solution of (43) is in S m . According to the optimization problem (43), for each phase m, the solution is drawn from (see Eq. ( 47) for definition of H m )S m = a ∈ A : θ m , a ⋆ m -a ≤ 2 -m+1 , M m a = ⃗ 0, -⃗ C ≤ B ⊤ m-1 B m-1 -1 B ⊤ m-1 a ≤ ⃗ C Lemma G.6. Let C >H m ∩ a ∈ A : θ m , a ⋆ m -a ≤ 2 -m+1 = Span [-C,C] (B m-1 ) ∩ a ∈ A : θ m , a ⋆ m -a ≤ 2 -m+1 = S m ,where the first equality holds due to Lemma G.4 and the last equality holds due to Eq. (48).Step 2: B ′ m is a C-approximate barycentric spanner of S ′ m . The proof idea of this step follows a similar arguments of Proposition 2.2 and Proposition 2.5 in [Awerbuch and Kleinberg, 2008] ) -i )| = det d i=1 w i b i , (B ′ m ) -i = d i=1 w i det (b i , (B ′ m ) -i ) = |w i | |det(B ′ m )| .Step 1 shows that each solution of ( 43) is in S m , and thus B m ⊆ S m , which further implies B ′ m ⊆ S ′ m . Recall that before the termination, the algorithm will scan each column vector of matrix A to ensure that no more replacement can be made. Hence, once Algorithm 12 terminates, we have that ∀i ∈[d], sup a∈S ′ m |det(a, (B ′ m ) -i )| ≤ C |det(B ′ m )|, and then ∀i ∈ [d], |w i | ≤ C, which implies that B ′ m is a C-approximate barycentric spanner of S ′ m .Step 3: B m is a C-approximate barycentric spanner of S m . Here, we show that every a ∈ S m can be written as a linear combination of elements only in B m with coefficients in [-C, C]. Notice that we only need to consider a ∈ S m -B m since if a ∈ B m , then, one can find a trivial linear combination by itself (recall that we assume C > 1). Then, we prove the desired claim for all a ∈ S m -B m by contradiction. Suppose that there exists an arm a ∈ S m -B m such that it cannot be linearly represented only by elements in B m with coefficients in [-C, C]. As S m ⊆ S ′ m and B ′ m is a C-approximate barycentric spanner of S ′ m (shown in step 2), there must exist coefficients {d i } d i=1 to linearly represent a as:EQUATIONAs for Eq. ( 49), we assume without loss of generality that the coefficient index j ∈ I m satisfies d j ̸ = 0. Since a / ∈ B m , the second for-loop in Algorithm 12 ensures that a can be represented as a linear combination of {b i } i∈[d]:i̸ =j , and it would be put in B m 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 coefficientsEQUATIONBridging Eq. ( 49) and Eq. ( 50), we haved j b j = i̸ =j (c i -d i ) b i -→ b j = 1 d j i̸ =j (c i -d i ) b i ,which implies that the j-th element of B ′ m , i.e., b j can be expressed as a linear combination of other elements of B ′ m , i.e., {b i } i̸ =j . This leads to a contradiction because Algorithm 12 ensures B ′ m to be linearly independent. As a consequence, every element of a ∈ S m can be written as a linear combination of elements only in B m with coefficients in [-C, C], which completes the proof.Proof of Lemma G.1. Recall from Eq. (3) that A m is defined asA 1 = A, A m = a ∈ A m-1 : θ m , a ⋆ m -a ≤ 2 -m+1 , ∀m ≥ 2.Since Lemma G.6 gives that B m is a C-approximate barycentric spanner of S m , it suffices to show that A m ⊆ S m to prove the claimed result. We prove this by induction. For the base case m = 1, A 1 ⊆ S 1 trivially holds based on definitions. Suppose that A m ⊆ S m holds for m ≥ 2. For m + 1, A m+1 is defined as:A m+1 = a ∈ A m : θ m+1 , a ⋆ m+1 -a ≤ 2 -m .Since Lemma G.6, gives that B m is a C-approximate barycentric spanner of S m , and the inductive hypothesis gives A m ⊆ S m , we haveA m ⊆ Span [-C,C] (B m ), which implies that A m+1 = a ∈ A m : θ m+1 , a ⋆ m+1 -a ≤ 2 -m = a ∈ A : θ m+1 , a ⋆ m+1 -a ≤ 2 -m , a ∈ A m ⊆ a ∈ A : θ m+1 , a ⋆ m+1 -a ≤ 2 -m , a ∈ Span [-C,C] (B m ) = S m+1 .Once the induction is done, the proof is complete.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 to 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 d is a finite and compact set. A distribution π ∈ ∆(A) is called a C-approximate optimal design with an approximation factorC ≥ 1, if sup a∈A ∥a∥ 2 V (π;A) -1 ≤ C • d, where V (π; A) = a∈A π(a)aa ⊤ .Then, the following lemma shows that if one computes a uniform design for set B, a 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 We then present the following lemma which provides a stronger result than that of Eq. ( 4). More specifically, we are supposed to show that ∥a∥ V -1 m ≤ C•d / √ Tm holds for all a ∈ A m in Eq. ( 4), but we will show that this holds for all a ∈ S m . This is stronger since A m ⊆ S m for all m ∈ N. Lemma G.9. For S m defined in Eq. The following analysis will condition on the nice event E, defined as:A ⊆ R d is a compact set that spans R d . If B = [b 1 , • • • , b d ] is a C-approximateEQUATIONwhere S m is defined in Eq. ( 48). Lemma G.10. We have P(E) ≥ 1 -δ.Proof. One can show that ∀a ∈ S m , a, θ m+1 -θ ≤ ∥a∥EQUATIONwhere the first inequality uses Cauchy-Schwartz inequality and the second inequality uses Lemma G.9.Notice that the above inequality holds for all m ∈ N. Finally, Theorem 20.5 of [Lattimore and Szepesvári, 2020] shows that with probability at least 1 -δ, for all m ∈ N θ m+1 -θ Hence, the proof is complete.Lemma G.11. Suppose E occurs where E is in Eq. ( 53). For all m ∈ N, a ⋆ ∈ S m holds where S m is defined in Eq. (48).Proof. We prove this by induction. For the base case m = 1, the claim holds trivially. Suppose that it holds for phase m (i.e., a ⋆ ∈ S m ) and then we aim to show a ⋆ ∈ S m+1 . For all a ∈ S m , one can show 0 ≤ ⟨θ, a ⋆ ⟩ -⟨θ, a⟩ ≤ θ m+1 , a ⋆ -θ m+1 , a + 2 × 2 -m-1 = θ m+1 , a ⋆ -a + 2 -m , where the second inequality follows from the definition of E (see Eq. ( 53)) and a ⋆ ∈ S m by inductive hypothesis. Then, we have θ m+1 , a ⋆ -a ⋆ m+1 + 2 -m ≥ 0.The inductive hypothesis gives a ⋆ ∈ S m , and thusEQUATIONsince Lemma G.6 gives that B m is a C-approximate barycentric spanner of S m . Combining θ m+1 , a ⋆ -a ⋆ m+1 + 2 -m ≥ 0 and Eq. ( 56), we have a ⋆ ∈ S m+1 according to definition of S m in Eq. ( 48). Once the induction is done, the proof is complete.Lemma G.12. Suppose that E occurs where E is in Eq. (53). For each arm a ∈ A with ∆ a > 0, it will not be in S m for all phases m ≥ m a + 1, where m a is the smallest phase such that ∆a 2 > 2 -ma .Proof. Consider an arbitrary arm a ∈ A with ∆ a > 0. Let m a be the smallest phase such that ∆a 2 > 2 -ma (i.e., ∆a 2 ≤ 2 -(ma-1) ). Then, we will show that arm a will be not in S τ for all τ ≥ m a . Suppose that a ∈ S ma (if not, it does not impact the claim). One can show thatθ ma+1 , a ⋆ ma+1 -a -2 -ma = sup b∈Sm a θ ma+1 , b -a -2 -ma ≥ θ ma+1 , a ⋆ -a -2 -ma ≥ ⟨θ, a ⋆ -a⟩ -2 -ma+1 > ∆ a -2 × ∆ a 2 = 0,where the first inequality uses Lemma G.11 that a ⋆ ∈ S m for all m ∈ N, the second inequality follows from the definition of E (see Eq. ( 53)), and the last inequality holds due to the choice of m a .According to the definition of S m in Eq. ( 48), arm a will not be in S m for all m ≥ m a + 1 as long as E occurs.Lemma G.13. Let m(t) be the phase in which round t lies. Then, m(t) ≤ log 2 (t + 1) for all t ∈ N.Proof. We prove this by contradiction. Suppose that ∃t ∈ N that m(t) > log 2 (t + 1). Note that we can further assume m(t) ≥ 2 since one can easily verify that for all t such that m(t) = 1, m(t) ≤ log 2 (t + 1) must hold. Recall that in phase m(t), each active arm will be played for m ℓ(t) times, we havet ≥ a∈B m(t)-1 π m(t)-1 (a)T m(t)-1 ≥ T m(t)-1 d = 256C 4 • d 2 4 -(m(t)-1) log δ -1 d 3 4 m(t)-1 ≥ 64C 4 • d 2 (t + 1) 2 log 4δ -1 d 3 > t,where the third inequality bounds ℓ(t) in the logarithmic term by ℓ(t) ≥ 2 and bound the other ℓ(t) > log 2 (t + 1) by assumption. Therefore, once a contradiction occurs, the proof is complete.Lemma G.14. Let m(t) be the phase in which round t lies. Suppose that E occurs where E is in Eq. (53) and Algorithm 2 computes a C-approximate barycentric spanner with C > 1. For all t ∈ N and all a ∈ A, if a ∈ S m(t) , then, ∆ a ≤ 64 × 512C 4 d 3 log d 3 4(t+1) 2 δ 3t .Proof where the first inequality holds due to Lemma H.7.Then, we 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 (δ ′ , Π, T ) where Π ⊆ Π all . For all h ∈ [H], the followings hold. With the above lemma in hand, one can show: We first consider a single execution of Algorithm 4 with input (δ, Π, T ) where Π ⊆ Π all . With the above supporting results, we are now ready to prove the claimed result. The following proof will condition on event E. First, one can show that for all π ∈ Π:V π -E s1∼µ [V π 1 (s 1 )] ≤ V π -E s1∼µ V π T,1 (s 1 ) + E s1∼µ V π T,1 (s 1 ) -E s1∼µ [V π 1 (s 1 )]≤ H 8T log(10|Π all |/δ) + E s1∼µ V π T,1 (s 1 ) -E s1∼µ [V π 1 (s 1 )] .(By Eq. ( 61))Then, we turn to bound the second term. Recall the reward dependent value function defined in Eq. ( 57), and we haveE s1∼µ V π T,1 (s 1 ) -V π 1 (s 1 ) ≤ E s1∼µ [V π 1 (s 1 , b T )](By Lemma H.11)= HE s1∼µ [V π 1 (s 1 , b T /H)] ≤ H T E s1∼µ T t=1 V π 1 (s 1 , b t /H) . (b T ≤ b t , ∀t)From Eq. ( 58), we haveE s1∼µ T t=1 V π 1 (s 1 , b t /H) ≤ T t=1 V π 1 (s t,1 , b t /H) + c 1 H T log ι ≤ T t=1V π t,1 (s t,1 ) + c 1 H T log ι (By Lemma H.10)≤ T t=1V πt t,1 (s t,1 ) + c 1 H T log ι.(π t ∈ argmax π∈Π V π t,1 (s t,1 ))Combining the above with Eq. ( 64), we arrive atE s1∼µ T t=1 V π 1 (s 1 , b t /H) = O SH 2 A log ι T + HS 2 A log 2 ι T .Now, we consider a fixed phase m where the input of Algorithm 4 is (δ m , Π m , T m ). There always exist two absolute constants c 1 , c 2 > 0 for T m = c 1 2 -2m S 2 AH 4 log 2 c 2 2 -2m S 2 AH 4 |Π all |δ -1 such thatV π m -E s1∼µ [V π 1 (s 1 )] ≤ 2 -m 2 .As conditioning on event E, the above holds for all m ∈ N. Thus, the proof is complete.One limitation is that the regret bound implied by the ULI guarantee for linear bandits with infinitelymany arms is suboptimal, i.e., O(d 1.5 √ T ) compared with lower bound Θ(d √ T ) but note that this problem is long-standing open. This is discussed below Theorem 4.2. We also mention the limitation of Algorithm 3 (below Theorem 5.1) that it is computational inefficient and the regret bound implied by ULI guarantee is also suboptimal.This paper proposes a new metric for online RL, called uniform last-iterate, which could be helpful for high-stacks applications, since a near-optimal result under our metric ensures both good cumulative and instantaneous results.Throughout the paper, we focus on high-probability regret, and therefore, when we mention regret, it always refer to high-probability regret. We refer readers to Remark 2.8 for a 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.Note that all MAB and linear stochastic bandit algorithms in this paper also work for R-subgaussian noise with minor adjustments. Only adversarial bandits algorithms in Section 3.1 require the boundedness assumption.We use O(•) to hide polylog factors.We slightly adjust the bonus function to ensure that with probability at least 1 -δ, the confidence bound holds for all t ∈ N.This assumption is made only for simplicity, but our proof can be easily extended to multiple optimal arms by changing the constant.With the choice of g(δ) in Proposition F.5, this requirement always holds if EXP3.P is a base-algorithm in Algorithm 10.It is equivalent to maxa∈A m | ⟨u, a⟩ | where u can be found by rank-one update. See[Zhu et al., 2022] for more details.We have the uniqueness because one can treat Bm-1xa = a as an overdetermined linear system in terms of xa ∈ R |B m-1 | and we have rank(Bm-1) = |Bm-1|. 


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

Reviews: review: paper_summary: paper_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$).

* They show that ULI is strictly stronger than uniform PAC (and hence also unifies regret and PAC).
* They show that successive elimination (SE) and phased elimination (PE) algorithms achieve ULI for finite-arm and linear bandits (in the case of PE).
* 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.
* They show that a phased-meta algorithm used with well-known adversarial bandit algorithms such as EXP3.P can achieve ULI (Appendix F).
* They show that phased-policy-elimination with a modified version of UCB-VI can achieve ULI for tabular episodic MDPs.
* 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})$,
strength_weakness: strength_weakness: * 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).
* 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).
* There is no experimental evaluation for the modified algorithms compared to the baseline algorithms.
questions: 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: limitations: The limitations have been addressed adequately by the authors. No negative social impact.
paper_summary: paper_summary: This paper introduces a stronger metric, uniform last-iterate (ULI) guarantee. 

The 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. 

The authors first provide two results for bandit problems with finite arms, showing that some algorithms can attain near-optimal ULI guarantees. 

They also provide a negative result, indicating that optimistic algorithms cannot achieve a near-optimal ULI guarantee. 

Finally, 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.
strength_weakness: strength_weakness: - 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?
    - 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. 

- 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. 

- They cannot achieve anytime sublinear expected regret, since their result is stricter than uniform-PAC.
questions: 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
    - Result of instance-dependent regret, such as the counterpart of Thm 2.6
    - 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. 

- I want to ask for additional theorems about the impossibility of optimism-based algorithms, see the weakness section above. 

- Necessity of the ULI: check the weakness section above. I somewhat feel ULI as 'unnecessarily strict' criterion.
limitations: limitations: The authors state their limitation in their paper. 

No negative societal impact
paper_summary: paper_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.
strength_weakness: strength_weakness: - The reinforcement learning algorithm presented in the paper have to examine every policy, which is generally not computationally efficient.
questions: 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?

He, 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: limitations: - The authors have thoroughly discussed the limitations of their work.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
3. 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?
questions: questions: see weaknesses
limitations: limitations: yes

Comments: comment: Thank you for the response, I will keep my positive score.
Thanks for your detailed rebuttal. I will change my score from 4 to 5.