Stochastic Multi-armed Bandits in Constant Space
David Liau Eric Price Zhao Song Ger Yang
cs.DS cs.LG stat.ML


Liau, Price, Song, Yang

[

Stochastic Multi-armed Bandits in Constant Space




  David Liau

  

 
  
  Eric Price 

  

  
  
  Zhao Song 

  

 
 
  Ger Yang 

  

  
  



The University of Texas at Austin

]


  
  
We consider the stochastic bandit problem in the sublinear space
setting, where one cannot record the win-loss record for all K arms.
We give an algorithm using O(1) words of space with regret

    ∑_i=1^K1/Δ_ilogΔ_i/Δlog T
 where Δ_i is the gap between the best arm and arm i and
Δ is the gap between the best and the second-best arms.  If the
rewards are bounded away from 0 and 1, this is within an O(log
1/Δ) factor of the optimum regret possible without space
constraints.









  
  











§ INTRODUCTION

In this paper, we study the multi-arm bandit problem in a sublinear
space setting.  In an instance of the bandit problem, there are K
arms and a finite time horizon 1,…,T, where T could be unknown
to us.  At each time step, we pull one of the K arms, and receive a
reward that depends on our choice.  The goal is to find a strategy
that would achieve a sublinear (with respect to time) regret,
which is defined as the difference between the cumulative reward we
received from our strategy and the reward we could have received if we
always pulled the best arm in the hindsight.

There are many formulations of the bandit problem.  In this paper we
consider the stochastic setting specifically.  In
the stochastic setting, one assumes the rewards from the i-th arm
are i.i.d. random variables, with mean μ_i and support [0,1].  A
well-known algorithm for the stochastic bandit is the UCB algorithm
<cit.>, and it is known that UCB achieves regret O(K log T).


The UCB algorithm requires Ω(K) space since it records the estimated rewards from all of the K arms. However, in settings with limited space such as streaming algorithms, or settings with infinitely many arms <cit.>, the requirement is problematic.  There is a significant literature addressing this problem, but existing approaches assume structural properties on the set of arms,
e.g. combinatorial structure <cit.> or continuum arm with local Lipschitz condition <cit.>.  A natural question is, what can we do without these structural assumptions given limited space?


A particular example is in a streaming algorithm setting, where space is much more limited than time, such as a router <cit.>. If the space constraint is o(K) but the time constraint is Ω(K), one cannot run traditional UCB. In this case, O(K) regret is still acceptable, and by accepting O(K) total regret, we can avoid requiring structural assumptions.  In a router, complicated strategy would corresponds to a larger set K of possible strategies, which grants us the tradeoff: larger K will result in a higher regret with a better optimum. 
Since routers have strict space constraints, running UCB would result in an extremely small regret on average over time (K/T=space/time, which is acceptable for routers). Our algorithm provides more flexibility in this bias/variance tradeoff.




  
Our techniques.
Our algorithm is based on fairly simple ideas.  First, suppose we know
the time horizon T and the expected value of the optimal arm μ^*.  We
could then make a single pass through the arms; for each arm i, flip
it until we have high (1 - 1/T^3) confidence that
Δ_i = μ^* - μ_i > 0, where μ_i is the expected value of arm i.  Once this happens, move to the next
arm.  This will flip each arm O(log T/Δ_i^2) times,
inducing regret O(log T/Δ_i^2·Δ_i) from
this arm.  The total regret will then be
O(∑_i ≠ i^*log T/Δ_i), which is ideal, with
only constant space required.  The problem is that we don't know T
or μ^*.  Not knowing T isn't a big deal – we can partition the
time horizon into loglog T scales, and the last log T term
will dominate <cit.> – but not knowing μ^* is a serious
problem.


We solve this problem by iteratively refining upper and lower bounds
μ_LB and μ_UB on μ^*.  In each pass through the data,
we get new estimates that are half as far from each other.  After
O(log(1/Δ)) passes, where Δ=min_i:Δ_i>0Δ_i is the minimal gap between the optimal and the suboptimal arms, only the best arm i^* will remain
in the interval.  This gives an algorithm that loses at most an
O(log(1/Δ)) factor in the regret.  In some cases, the                                                     
loss is significantly smaller. Therefore, we can obtain the following result that improves the O(log(1/Δ)) factor into a O(log(Δ_i/Δ)) factor,

	
Given a stochastic bandit instance with K arms and their expected values μ_1, ⋯μ_k ∈ [0,1]. Let μ_* = max_i∈ [K]μ_i, Δ_i = μ_* - μ_i, and Δ = min_i : Δ_i > 0Δ_i. For any T>0, there exists an algorithm that uses O(1) words of space and achieves regret

    O( ∑_i : Δ_i>01/Δ_ilogΔ_i/Δlog T ).


Recall that the well-known UCB algorithm gives regret O(∑_i:Δ_i>0log T/Δ_i).

Our algorithm is always within a log (Δ_i/Δ) factor of its space-unlimited version.  In certain situations, we can do slightly better by refining our estimate of μ^* by more than a constant factor in each iteration.  This gives us the following result

Under the same setting as Theorem <ref>, for any  γ>0, there exists an algorithm that uses O(1) words of space and achieves regret 

    O ( ∑_i:Δ_i>01/Δ_i(log^γ1/Δ_i + log (Δ_i/Δ)/γloglog (Δ_i/Δ))log(T) ).


In particular, if we set γ = 1/2, we can find that this algorithm is always within an O(log(1/Δ)/loglog(1/Δ)) factor of the space-unlimited UCB algorithm.  


Also, we show that we are able to further improve the O(log(1/Δ)) factor to a log (Δ_i/Δ)/loglog (Δ_i/Δ) factor,

	Given a stochastic bandit instance with K arms and their expected values μ_1, ⋯μ_k ∈ [0,1]. Let μ_* = max_i∈ [K]μ_i, Δ_i = μ_* - μ_i, and Δ = min_i:Δ_i>0Δ_i. For any arbitrarily small constant γ>0 and for any T>0, there exists an algorithm that uses O(1) words of space and achieves regret
	
    O ( ∑_i:Δ_i>01/Δ_i(log^γ1/Δ_i + log (Δ_i/Δ)/γloglog (Δ_i/Δ))log(T) ).


























The paper is presented in the following manner. Section <ref>
reviews the related work.
 Section <ref> provides
detailed preliminaries of problem formulation and the background
needed for our result. Section <ref> and <ref> contains the algorithm that gives the result (1) and (2) of Theorem <ref> with known time horizon T, respectively.  Section <ref> demonstrates how to extend the algorithms to the case with unknown time horizon. The full version is available at <https://arxiv.org/pdf/1712.09007>.



§ RELATED WORKS





For stochastic bandits, the seminal work by <cit.> demonstrated the idea of using the confidence intervals to solve the problem, and it showed that the lower bound of the regret is Ω(∑Δ_i log T/KL(μ_i,μ_*)). The UCB algorithm, which is a simple solution to stochastic bandits, was analyzed in <cit.>. The UCB algorithm is based on Hoeffding's inequality, which is optimal when KL(μ_i,μ_*)≈Δ_i^2.  In certain situations this can be improved using different types of concentration inequalities; for example, <cit.> used Bernstein's inequality to derive an algorithm with regret depending on the second moments.  Later, <cit.> and <cit.> independently proposed the KL-UCB algorithm that matches the lower bound. We refer to the reader the comprehensive survey by <cit.> for general bandit problems.


In addition to regret analysis for online decision making, there is a set of papers that discuss the sample complexity for the pure exploration problem, i.e. how to identify the best arm  <cit.>.  
Similar algorithms has been used in the regime of online decision making <cit.>.  With the idea of the best arm identification, the explore-then-commit (ETC) policy is designed to first performs some tests to identify the best arm, and then commit to it in the remaining time horizon.  The ETC policy is shown to be suboptimal <cit.> but simplifies the analysis.   In particular, our algorithm is based on the framework by <cit.>, but our algorithm takes only O(1) space while the method by <cit.> takes O(K) space.



Moreover, there is a small set of papers that integrates the sketching techniques from streaming and online learning <cit.>.   <cit.> considered the problem of minimizing α-exp-concave losses, and the regret is required to be O(log T) uniformly over time.  They used the idea from streaming to keep a small active set of experts.  <cit.> considered the online convex optimization problem, and they used the ideas of sketching to reduce the efficiency for computing online Newton steps, however, the complexity is still Ω(K). 


§ PRELIMINARY



  
Notations
For any positive integer n, we use [n] to denote the set {1,2,⋯,n}. 
For random variable X, let 𝔼[X] denote its expectation of X (If this quantity exists). 
In addition to O(·) notation, for two functions f,g, we use the shorthand f≲ g (resp. ≳) to indicate that f≤ C g (resp. ≥) for an absolute constant C. We use f g to mean cf≤ g≤ Cf for constants c,C.

We measure space in words using the word RAM model, so that the input values (such as K, T, and rewards) and variables can each be expressed in O(1) word of space in O(log(KT)) bits. For more details of word RAM model, we refer the readers to <cit.>.





 §.§ Problem Formulations
 

For a multi-armed bandit problem, there are K arms in total, and a finite time horizon 1,2,…,T.  At each time step t ∈ [T], the player has to choose an arm I_t ∈ [K] to play, and receives a reward X_i,t associate to that arm.  Without loss of generality, assume that for each arm i ∈ [K] and each time step t ∈ [T], X_i,t∈ [0,1].  We denote the arm that player chooses at time t as I_t. The goal of the player is to maximize the total reward he is getting.  We will measure the performance of an algorithm via its regret, which is defined as the difference between the best reward in the hindsight and the reward received with the algorithm:

    Ψ_T = max_i ∈ [K]( ∑_t=1^T X_i,t - ∑_t=1^T X_I_t,t).




In this paper, we consider the stochastic setting, where we assume the rewards are coming from some stochastic processes.

In a stochastic bandit, we assume each arm i ∈ [K] is associated with a distribution D_i over [0,1], with mean μ_i.  The reward X_i,t at time t ∈ [T] is drawn from D_i independently.


For stochastic bandits, instead of using the regret defined above, we will consider the pseudo regret:

    Ψ_T = max_i ∈ [K]( [ ∑_t=1^T X_i,t] - [ ∑_t=1^T X_I_t,t] ) .




We can rewrite the pseudo regret using  Wald's identity:

    Ψ_T = max_i ∈ [K]( ∑_j=1^K[ N_j,TΔ_ij] ),

where N_j,T is the number of times arm j is chosen up to time T,









and we define Δ_ij = μ_i - μ_j to be the gap between the means of arm i and arm j.  
We use μ_* to denote the mean reward for the arm with the highest mean, i.e., μ_* = max_i∈ [K]  μ_i.









 §.§ Concentration Inequalities

In this paper, for simplicity, we will use Chernoff-Hoeffding inequality to analyze the concentration behavior for random variables with bounded support.
[Chernoff-Hoeffding Bound]
	Let x_1, x_2, …, x_n be i.i.d. random variables in [0,1].  Let X = 1/n∑_i=1^n x_i.  Then for any ϵ > 0,
	
    [ | X -  [X] | > ϵ] ≤ 2e^-2nϵ^2.

	
	
	
	




































 



§ UCBCONSTSPACE WITH KNOWN T

The original UCB-1 algorithm <cit.> needs O(K) space to achieve O(∑_i:Δ_i>01/Δ_ilog T ) regret. In this section, we propose a new algorithm which requires only O(1) space in exchange for a slightly worse regret. 


First, we consider the setting where T is known.  The main result is presented in the following theorem.



Given a stochastic bandit instance with known T, let Δ_i = μ_* - μ_i, and let Δ = min_i:Δ_i>0Δ_i. Then for any T>0, there exists an algorithm that uses O(1) words of space and achieves regret

    O ( ∑_i:Δ_i>01/Δ_ilog (Δ_i/Δ ) log T ).



[t]UCB algorithm with constant space and known T (Theorem <ref>)
	
	


We present the method in Algorithm <ref>, where we iteratively improve our estimation of Δ.  More precisely, we scan through the data multiple rounds.  In the r-th round, we sample each arm up to some precision g_r.  The desired precision g_r is halved after each round.  In this sampling process, we only keep the information of the best arm and the second best arm seen in the current and the previous round, instead of saving those from all arms.  With the information of the best arm and the current precision g_r, we can refine the upper and lower bound μ_UB and μ_LB on μ_*.  If an arm whose upper confidence value is less than μ_LB, we can rule it out without continuing to g_r precision.  This process is terminated if we are able to determine the best arm with the rest arms.


We define a^(r) and b^(r) as the best arm and the second best arm stored at the end of the r-th round.  Also, we let μ̅_i^(r) to be the recorded empirical mean at the end of the r-th round for arm i.  Denote n_i^(r) as the total number of pulls of arm i at the r-th round. Then, we define μ̅_i,n^(r) as the empirical mean μ̅_i stored for arm i after pulling it for n times in round r.  Further, we define r_max as the value of r-1 at the moment the algorithm exits the loop in Line <ref>. 


For each r ∈ [r_max], define the event ξ_r to be the event:
∃ r' ∈ [r], ∃ i ∈ [K], ∃ n ∈ [n_i^(r')]
such that
|μ̅_i,n^(r') - μ_i| > √(log(1/δ) /(2n)),
i.e., there exists some estimate of μ_i,n^(r') that is not within our desired confidence interval up to round r. 

 Throughout the first part of our analysis, we focus on the case when ξ_r holds when we are discussing the state of the algorithm at round r, i.e., all estimates are within our desired confidence interval.
 
	In Algorithm <ref>, at any round r ∈ [r_max], given ξ_r, the following statements are true: 

		1. n_a^(r)^(r) = ⌈ ( 2log(1/δ) ) / g_r^2  ⌉, i.e. the claimed optimal arm cannot be ruled out early. 

		2. n_*^(r) = ⌈  (2log(1/δ) )/ g_r^2 ⌉, i.e. the true optimal arm cannot be ruled out early. 

		3. |μ̅_a^(r)^(r) - μ_*| ≤ g_r/2.



	We prove this lemma by induction.  For the base case, the first and the second statement are true because all arms have to be played for ⌈2log(1/δ)/(g_1)^2⌉ times.  For the third statement, we prove by contradiction.  Assume the contrary, i.e. μ̅_a^(1)^(1) - μ_* > g_1/2 or μ_* - μ̅_a^(1)^(1) > g_1/2.  If μ̅_a^(1)^(1) - μ_* > g_1/2, then we have
	
    μ_*    <  μ̅_a^(1)^(1) - g_1/2    
       ≤ μ_a^(1) + √(log(1/δ) / (2 n_a^(1)^(1)) )  - g_1/2 
       ≤ μ_a^(1) + g_1/2 - g_1/2 
       =  μ_a^(1)

	where the second step follows by condition ξ_r and the third step follows by n_a^(1)^(1)≥   ( 2log(1/δ) ) /g_1^2.
	
	The above equation leads to a contradiction because μ_*>μ_i for any i≠*.  Similarly, if μ_* - μ̅_a^(1)^(1) > g_1/2, then we have
	
    μ̅_a^(1)^(1)   < μ_* - g_1/2    
       ≤μ̅_*^(1) + √(log(1/δ) /( 2 n_*^(1))) - g_1/2 
       ≤μ̅_*^(1) + g_1/2 - g_1/2 
       = μ̅_*^(1)

	where the second step follows by condition ξ_r, and the third step follows by n_*^(1)≥ (2log(1/δ) )/g_1^2.
	
	The above equation also results in a contradiction because for any i≠* to be assigned as a^(1), we must have μ̅_a^(1)^(1) > μ̅_*^(1).
	
	For the induction step, we assume these three statements are true for r ≤ r'-1.  Now consider r=r'.  We first prove the second statement.  Assume the contrary, i.e. the true optimal arm has been ruled out early, meaning
	
    μ̅_*^(r) + √(log(1/δ) / ( 2 n_*^(r)) ) < μ̅_a^(r-1)^(r-1) - g_r-1/2

	Then, we can see that
	
    μ_*    ≤ μ̅_*^(r) + √(log(1/δ) / (2 n_*^(r))) 
    	
    	
       <  μ̅_a^(r-1)^(r-1) - g_r-1/2
    	
    	
       ≤ μ_a^(r-1)

	where in the last inequality, we use the induction hypothesis, n_a^(r-1)^(r-1)≥2 log(1/δ)/g_r-1^2 and then
	
    μ_a^(r-1)≥μ̅_a^(r-1)^(r-1) - √(log(1/δ)/2n_a^(r-1)^(r-1))≥μ̅_a^(r-1)^(r-1) - g_r-1/2

	There is a contradiction in (<ref>) because we must have μ_* ≥μ_a^(r-1).  Hence the second statement is true.
	
	Next, we can see that the first statement is now clear because we have shown that there is at least one arm that is going to pull for ⌈2log(1/δ)/g_r^2⌉ times at the r-th round (which is arm * according to the second statement we have just shown).  This means that if arm a^(r) is not arm *, then it has to be pulled for ⌈2log(1/δ)/g_r^2⌉ times as well.
	
	
	For the third statement, the proof is similar to the base case, where we prove by contradiction.  Assume the contrary, i.e. μ̅_a^(r)^(r) - μ_* > g_r/2 or μ_* - μ̅_a^(r)^(r) > g_r/2.
	
	If μ̅_a^(r)^(r) - μ_* > g_r/2, then we have
	
    μ_*    < μ̅_a^(r)^(r) - g_r/2    
       ≤μ_a^(r) + √(log(1/δ) / ( 2 n_a^(r)^(r))) - g_r/2 
       ≤μ_a^(r) + g_r/2 - g_r/2 
       = μ_a^(r)

	where the second step follows by condition ξ_r, and the third step follows by n_a^(r)^(r)≥2log(1/δ)/g_r^2(the first statement).
	
	This results in a contradiction because μ_*≥μ_i for any i∈[K].  Similarly, if μ_* - μ̅_a^(r)^(r) > g_r/2, then we have
	
    μ̅_a^(r)^(r)   < μ_* - g_r/2    
       ≤μ̅_*^(r) + √(log(1/δ) / ( 2 n_*^(r))) - g_r/2 
       ≤μ̅_*^(r) + g_r/2 - g_r/2 
       = μ̅_*^(r)

	where the second step follows by condition ξ_r and the third step follows by n_*^(r)≥2log(1/δ)/g_r^2(the second statement). 
	
	This results in a contradiction because for any i≠* to be assigned as a^(r), we must have μ̅_a^(r)^(r) > μ̅_*^(r), otherwise we will have |μ̅_*^(r) - μ_*| ≤ g_r/2 by condition ξ_r.


 
	In Algorithm <ref>, conditioning on event ξ_r_max holds, we have r_max≤⌈log(2/Δ) ⌉.


	Assume the contrary, i.e. at the end of round r=⌈log(2/Δ) ⌉, the best arm and the second best arm are still not differentiated, meaning we still have



	
    μ̅_*^(r) - g_r/2    < μ̅_a^(r)^(r) + g_r/2

	First note that r > log(2/Δ) implies 2^-r=g_r < Δ/2.  We have
	
    μ_*    ≤μ̅_*^(r) + √(log(1/δ) / ( 2n_*^(r))) 
       ≤μ̅_*^(r) + g_r/2 < μ̅_a^(r)^(r) + 3g_r/2
       < μ̅_a^(r)^(r) + 3Δ/4

	Similarly, we have
	μ_a^(r) > μ̅_a^(r)^(r) - Δ/4.






	Then, we can show that
	
    Δ≤μ_* - μ_a ≤ (μ̅_a^(r)^(r) + 3Δ/4) - (μ̅_a^(r)^(r) - Δ/4) < Δ
 
	which results in a contradiction.  This implies that given ξ_r_max, we must have r_max≤⌈log(2/Δ) ⌉.


 
	In Algorithm <ref>, at any round r, given ξ_r, the number of plays for any arm i∈[K] is upper-bounded by
	
    n_i^(r)≤2log(1/δ)/(Δ_i- g_r-1)^2 +1.



	First, note that as long as an arm has not been ruled out, we have
	
    μ̅_i,n_i^(r)-1^r + √(log(1/δ)/2(n_i^(r)-1))≥μ̅_a^(r-1)^(r-1) - g_r-1/2

	Then, we can show
	
    Δ_i    = μ_* - μ_i  
       ≤μ̅_a^(r-1)^(r-1) + g_r-1/2 - μ_i  
       ≤μ̅_a^(r-1)^(r-1) + g_r-1/2 - ( μ̅_i,n_i^(r)-1^(r)-√(log(1/δ)/2(n_i^(r)-1))) 
       ≤  2( g_r-1/2 + √(log(1/δ)/2(n_i^(r)-1)))

	where the second step follows from Lemma <ref>, the third step follows by ξ_r, and the last step follows by (<ref>).  Reorganizing the above inequality proves the lemma.



	Consider Algorithm <ref>.  For each round r ∈ [r_max], conditioned on ξ_r, i.e. the confidence interval is correct, we first recognize two bounds on the number of plays n_i^(r) for each arm i ∈ [K].
	
	By the definition of Algorithm <ref>, we have
	
    n_i^(r)≤ 2log(1/δ) /  g_r^2 +1

	Also, from Lemma <ref>, we have
	
    n_i^(r)≤  2log(1/δ) / (Δ_i- g_r-1 )^2 +1

	By combining (<ref>) and (<ref>), together with r_max≤⌈log(2/Δ) ⌉ by Lemma <ref>, we can upper bound the regret results from pulling arm i in the algorithm. Let α=⌈log(2/Δ) ⌉ and β=⌈log(3/Δ_i)⌉. Conditioning on event ξ_r_max holds, we have,
	
    ∑_r=1^αΔ_i n_i^(r)≤    ∑_r=1^αΔ_i ( 2log(1/δ)/( max{g_r, Δ_i-2g_r })^2 +1 )    
    
    		=     ∑_r=1^αΔ_i ( 2log(1/δ)/( max{2^-r, Δ_i-2 · 2^-r})^2 +1 )

	Furthermore, we can obtain 
    ∑_r=1^αΔ_i n_i^(r)
       ≤∑_r=1^βΔ_i ·2log(1/δ)/2^-2r + ∑_r=β+1^αΔ_i ·2log(1/δ)/(Δ_i - 2 · 2^-log(3/Δ_i))^2
        + Δ_i ·⌈log(2/Δ) ⌉   
       ≤288log(1/δ)/Δ_i + 18log(2Δ_i/3Δ)log(1/δ)/Δ_i
        + Δ_i (log(2/Δ)+1)    
       ≲log(Δ_i/Δ)log(1/δ)/Δ_i

	For the next step, we find an upper bound for the probability of event ξ_r_max :={∃ r∈[r_max] ,∃ i ∈ [K], ∃ n ∈ [n_i^(r)]  s.t.  |μ̅_i,n^(r) - μ_i| > √(log(1/δ) / (2n) )}: 
    (ξ_r_max) 
    ≤    ∑_r=1^T/K∑_i=1^K∑_n=1^T( |μ̅_i,n^(r) - μ_i| > √(log(1/δ)/ (2n))) 
    ≤     2T^2 δ
	
	Finally, by choosing δ = 1/T^3, and combining (<ref>) and (<ref>), we have
	
    Ψ_T    ≲ ∑_i=1^K(log(Δ_i/Δ)log(T)/Δ_i + Δ_i T · 2T^2 δ)  
       ≲ ∑_i=1^Klog(Δ_i/Δ)log(T)/Δ_i

	which proves the theorem.





















































§ IMPROVED ALGORITHM FOR UCBCONSTSPACE


The result in Theorem <ref> gives an additional O(log(Δ_i/Δ)) factor to the original UCB-1 algorithm by <cit.>.  This means that in a bad scenario, for example, if most of the arms have gap Δ_i = K Δ, the O(log(Δ_i/Δ)) factor translates to an additional log K factor in the regret.

In this section, we show that we are able to improve the additional log(Δ_i/Δ) factor to a log(Δ_i/Δ)/loglog(Δ_i/Δ) factor by slightly changing the update rule on the precision g_r.  This means that in the bad example described above, we are improving the competitive ratio from log K to log K/loglog K.  We present our result in the following theorem.

	Given a stochastic bandit instance with known T, let Δ_i = μ_* - μ_i, and let Δ = min_i:Δ_i>0Δ_i. For any γ>0 and any T>0, there exists an algorithm that uses O(1) words of space and achieves regret
	
    O ( ∑_i:Δ_i>01/Δ_i(log^γ1/Δ_i + log (Δ_i/Δ)/γloglog (Δ_i/Δ))log(T) ).

	
	
	
	



We consider a modified version of Algorithm <ref>, where the update rule in Line <ref> is replaced by 

    g_r+1=g_r/2(log(1/g_r))^ϵ

where ϵ is some constant to be determined later.
In the following lemma, we show that with this update rule, basically given any D<1, it takes only O(1/ϵ·log(1/D)/loglog(1/D)) steps to reach accuracy D.
 
	Given any g_0, D ∈ (0,1), D<g_0, let r_0 = log (g_0/D)/loglog (g_0/D).  If for any positive integer r,
	g_r=g_r-1/2(log(1/g_r-1))^ϵ.
	Then, for any r ≥ (2/ϵ+1)r_0+2, we have g_r ≤ D.


	First, note that by definition of g_r, we have g_r ≤ g_0 2^-r for any r ≥ 1.  Therefore, for any r ≥ r_0, we have
	
    g_r ≤ g_0 2^-r≤ g_0 2^-r_0 = g_0 (D/g_0)^1/loglog (g_0/D)

	Then, we can see that for any r ≥ r_0, we have
	
    g_r+1≤g_r/2(log (g_0/D)/loglog (g_0/D))^ϵ≤g_r/2(log (g_0/D))^ϵ/2

	As a result, we have
	
    g_r+⌈2/ϵr_0⌉   ≤g_r/2^2/ϵr_0 (log (g_0/D))^r_0
       ≤ g_0 (log (g_0/D))^-r_0 = D

	This implies that for any r ≥ (r_0 + 1) + (2/ϵr_0 + 1) ≥⌈r_0⌉ + ⌈2/ϵr_0⌉, we have g_r ≤ D.

Note that we can apply Lemma <ref> and Lemma <ref> for Algorithm <ref> with update rule (<ref>) because they do not require specific update rules.  Before we proceed to the proof of Theorem <ref>, we need the following lemma for an upper bound of r_max.

	In Algorithm <ref> with update rule (<ref>), given ξ_r_max, we have r_max≤⌈(2/ϵ+1)log 2/Δ/loglog 2/Δ + 2⌉.


	Assume the contrary, i.e. at the end of round r=⌈(2/ϵ+1)log 2/Δ/loglog 2/Δ + 2⌉, the best arm and the second best arm are still not differentiated, meaning for some i ≠ *, we still have
	
    μ̅_*^(r) - g_r/2 < μ̅_i^(r) + g_r/2

	By Lemma <ref>, we have g_r ≤Δ/2.  Thus, we have
	
    μ_*    ≤μ̅_*^(r) + g_r/2 ≤μ̅_i^(r) + 3g_r/2 ≤μ̅_i^(r) + 3Δ/4

	where for the second step we use Lemma <ref>.  Similarly, we haveμ_i ≥μ̅_i^(r) - Δ/4.
	Then, we have
	
    Δ≤μ_* - μ_i ≤ (μ̅_i^(r) + 3Δ/4) - (μ̅_a^(r)^(r) - Δ/4) < Δ
 
	which results in a contradiction.



	Consider Algorithm <ref> with update rule (<ref>).  For each arm i ∈ [K], if we condition on ξ_r_max, then by Lemma <ref> and Lemma <ref>, we can upper bound the regret results from pulling arm i in the algorithm:
	
    ∑_r=1^r_maxΔ_i n_i^(r)
    ≤    ∑_r=1^r_maxΔ_i ( 2log(1/δ)/( max{g_r, Δ_i-g_r-1})^2 +1 )    
    ≤    ∑_r=1^r_iΔ_i ·2log(1/δ)/g_r^2 + ∑_r=r_i+1^r_maxΔ_i ·2log(1/δ)/(Δ_i - g_r-1)^2
         + Δ_i · r_max

	where r_i be the minimal round r such that g_r<Δ_i/2. For the first term of (<ref>), since g_r decays super-exponentially, i.e. g_r+1≤ g_r/2, we have
	
    ∑_r=1^r_i2Δ_ilog(1/δ)/g_r^2   ≤4Δ_ilog(1/δ)/g_r_i^2
       =4Δ_i(log1/g_r_i-1)^2ϵlog(1/δ)/g_r_i-1^2
       ≤16(log1/Δ_i)^2ϵ/Δ_ilog(1/δ)

	where the last step follows from the fact that g_r_i-1≥Δ_i/2 by the definition of r_i.  For the second term of (<ref>), we have
	
    ∑_r=r_i+1^r_max2Δ_ilog(1/δ)/(Δ_i - g_r-1)^2≤    ∑_r=r_i+1^r_max8Δ_ilog(1/δ)/Δ_i^2
    ≤    ∑_r=r_i+1^r_max8log(1/δ)/Δ_i

	By Lemma <ref>, we can find that it takes ⌈(2/ϵ+1)log (Δ_i/Δ)/loglog (Δ_i/Δ) + 2⌉ rounds to get from Δ_i/2 to Δ_i/2.  As a result, we can upper bound (<ref>) by
	
    ∑_r=r_i+1^r_max2Δ_ilog(1/δ)/(Δ_i - g_r-1)^2
       ≤((2/ϵ+1)log (Δ_i/Δ)/loglog (Δ_i/Δ) + 3) 8log(1/δ)/Δ_i
       ≤(2/ϵ+1)log (Δ_i/Δ)/loglog (Δ_i/Δ)16log(1/δ)/Δ_i

	
	Using the similar argument as we have done in the proof of Theorem <ref>, we can find that 
	
    (ξ_r_max) ≤ 2T^2δ

	
	Finally, by combining (<ref>), (<ref>), and (<ref>), we can get 
    Ψ_T ≤     16∑_i:Δ_i>01/Δ_i(log^2ϵ1/Δ_i + (2/ϵ+1)log (Δ_i/Δ)/loglog (Δ_i/Δ)) 
        ·log(1/δ)  + ∑_i:Δ_i>0Δ_i T · 2T^2 δ

	By choosing δ=1/T^3 and ϵ = γ/2 we can find that 
	
    Ψ_T ≲∑_i:Δ_i>01/Δ_i(log^γ1/Δ_i + log (Δ_i/Δ)/γloglog (Δ_i/Δ))log(T)

	which proves the theorem.

We conjecture below that the O(log (Δ_i/Δ)/loglog (Δ_i/Δ)) factor is not improvable given the O(1) space constraint.  The discussion for our conjectured hard instance is in the appendix.

	There exists a distribution over stochastic bandit problems such that, for any algorithm taking O(1) words of space will have regret 
	
    Ω( ∑_i:Δ_i>01/Δ_i(log (Δ_i/Δ)/loglog (Δ_i/Δ))log(T) ).





§ UNKNOWN HORIZON T
 
Now, we show that using the technique described in <cit.>, we are able to get the same regret as in Theorem <ref> if T is unknown.


	Given a stochastic bandit instance with unknown T, let Δ_i = μ_* - μ_i, and let Δ = min_i:Δ_i>0Δ_i. For any T>0, there exists an algorithm that uses O(1) words of space and achieves regret
	
    O(∑_i:Δ_i>0log (Δ_i/Δ)/Δ_ilog T)



	We present the algorithm in Algorithm <ref>.  The algorithm repeatedly calls the procedure in Algorithm <ref> with increasing time horizons T_0, T_1, …, T_L, where L ≤loglog T.  By setting T_l = T_l-1^2, we have T_l = T_0^2^l.  Then, by Theorem <ref>, we can upper bound the regret as
	
    Ψ_T    ≲ ∑_l=0^L∑_i=1^Klog(Δ_i/Δ)log T_l/Δ_i
        =  ∑_l=0^L∑_i=1^K2^l log(Δ_i/Δ)log T_0/Δ_i
       ≲ ∑_i=1^K2^L log(Δ_i/Δ)log T_0/Δ_i
       ≲ ∑_i=1^Klog(Δ_i/Δ)log T/Δ_i

	which proves the theorem.







Similarly, we are able to use this trick for the improved algorithm in Section <ref> and get the same regret as in Theorem <ref>.

	Given a stochastic bandit instance with unknown T, let Δ_i = μ_* - μ_i, and let Δ = min_i:Δ_i>0Δ_i. For any γ>0 and any T>0, there exists an algorithm that uses O(1) words of space and achieves regret
	
    O ( ∑_i:Δ_i>01/Δ_i(log^γ1/Δ_i + log (Δ_i/Δ)/γloglog (Δ_i/Δ))log(T) ).

	
	
	
	









§ CONCLUSION
  We proposed a constant space
algorithm for the stochastic multi-armed bandits problem.  Our
algorithms proceeds by iteratively refining a confidence interval
containing the best arm's value.  In the simpler version of our
algorithm, we refine the interval by a constant factor in each step,
and each iteration only uses O() regret.  This gives an
O(log1/Δ)-competitive algorithm.  We then showed how
to improve this by an O(loglog1/Δ) factor in
certain cases, by using fewer rounds that give more progress.
Finally, we showed how to adapt our algorithms—which involve
parameters that depend on the time horizon T—to situations with
unknown time horizon.







































§ ACKNOWLEDGMENTS

This work was partially supported by NSF through grants CCF-1216103, CCF-1331863, CCF-1350823 and CCF-1733832.








































































































§ DISCUSSION OF CONJECTURE ON THE LOWER BOUND FOR STOCHASTIC BANDITS

For any given round r, for some α>0, define:

    R_^(r) = ∑_i: Δ_i<α g_r1/g_r,
       R_^(r) =∑_i: Δ_i>α g_r1/Δ_i

That correspond to two terms in 

    ∑_r=1^r_iΔ_i ·2log(1/δ)/g_r^2 + ∑_r=r_i+1^r_maxΔ_i ·2log(1/δ)/(Δ_i - g_r-1)^2
         + Δ_i · r_max

which is the total regret provided within Section <ref>.  Consider the following example where there is a group of high-value arms and a group of low-value arms, and the size of the low-value arms is larger than the high-value arms.

	Assume 1>E ≫ϵ, and s>1/2. Let Δ_i=ϵ for i=1… sK, and Δ_i=E for i=sK+1 … K.

In this example, we can find that as g_r<E/2, R_^(r) = sK/g_r, and R_^(r)=(1-s)K/E.  Since g_r ≲ E and s>1/2, we can find that R_^(r)≲ R_^(r).  This means that Example <ref> will not harm us if we use Algorithm <ref> because we know that ∑_r R_^(r)≲∑_i 1/Δ_i.

Then, we consider another example where the size of the group of the high-value arms is larger than low-value arms.  Particularly, we consider

	Assume 1>E ≫ϵ, and s<1/2, where s/(1-s)<ϵ/E. Let Δ_i=ϵ for i=1… sK, and Δ_i=E for i=sK+1 … K.

We can find that in this example, as long as ϵ≲ g_r≲ E, R_^(r)≲ sK/ϵ≲ (1-s)/E = R_^(r).  This means that this is the hard case for Algorithm <ref> because R_^(r) is dominating.  However, we can deal with this example with the following update rule

    g_r+1 = g_r/2 max{1,(1-s)/s}

which is roughly g_r+1 = g_r/2 max{1,R_^(r)/R_^(r)}.
Note that if s is unknown, we can estimate it by simply counting the number of arms not ruled out.  With the new update rule, we can find that as long as g_r ≲ E, we have g_r+1≲ Es/(1-s) ≲ϵ.  This means that in the next round, we are able to identify the high-value arms.  Therefore, the number of rounds is a constant.

Finally, we consider the following case where we conjectured to be the hard case:

	Let Δ_i = i/K for i = 1,2,…, K.

First note that in this example, R_^(r) n and R_^(r) nlog 1/g_r, where we can find that R_^(r)≲ R_^(r) for any r.  If we use the trick we are dealing with Example <ref>, we can find that the corresponding update rule becomes g_r+1 = g_r/2 log 1/g_r.  Such rule is exactly (<ref>).  Therefore, we conjecture that the additional log (Δ_i/Δ)/loglog (Δ_i/Δ) factor is not improvable.














































































































































































abbrvnat





