Kiefer Wolfowitz Algorithm is Asymptotically Optimal for a Class of Non-Stationary Bandit Problems
Rahul Singh Taposh Banerjee



Kiefer-Wolfowitz Algorithm is Asymptotically Efficient for a Class of Non-Stationary Bandit Problems

     Rahul Singh and Taposh Banerjee
Rahul Singh is with the Laboratory of Information and Decision Systems (LIDS), Massachusetts Institute of Technology, Cambridge, MA 02139, USA; Taposh Banerjee is with SEAS, Harvard University, Cambridge, MA. 
rsingh12@mit.edu, tbanerjee@seas.harvard.edu.
  
 
    December 30, 2023
=========================================================================================================================================================================================================================================================================================================


We consider the problem of designing an allocation rule or an “online learning algorithm" for a class of bandit problems in which the set of control actions available at each time s is a convex, compact subset of ℝ^d. Upon choosing an action x at time s, the algorithm obtains a noisy value of the unknown and time-varying function f_s evaluated at x. The “regret" of an algorithm is the gap between its expected reward, and the reward earned by a strategy which has the knowledge of the function f_s at each time s and hence chooses the action x_s that maximizes f_s.

For this non-stationary bandit problem set-up, we consider two variants of the Kiefer Wolfowitz (KW) algorithm i) KW with fixed step-size β, and ii) KW with sliding window of length L. We show that if the number of times that the function f_s varies during time T is o(T), and if the learning rates of the proposed algorithms are chosen “optimally", then the regret of the proposed algorithms is o(T), and hence the algorithms are asymptotically efficient. 



§ INTRODUCTION

The Multi-Armed Bandit problem (MABP) requires a player to play an arm at each time s=1,2,… from a set of arms. If X_s denotes the arm played at time s, then the player receives a random reward at time s, the distribution of which depends on X_s. The objective of the player is to maximize the expected value of the cumulative reward collected over a period of time T. The player does not know the mean value of the random reward as a function of the choice x, and hence the control action corresponding to the choice of arm to be played needs to balance an exploration-exploitation trade-off.

This paper is concerned with a particular class of bandit problems in which the control action available to the player can be mapped to a convex compact subset of ℝ^d, i.e., the continnum bandit problem <cit.>, in which the mean reward of the arms is non-stationary. The addition of non-stationarity into the MABP adds to the complexity involved in the exploration-exploitation dilemma, since now the player's belief about the mean reward of an arm cannot depend upon past data that is “too old" because the reward distribution of arms might have changed since the time that information was collected. Thus, the learning rate of the player has to be suitably adapted to the rate-of-change of the mean reward function.














§ KIEFER WOLFOWITZ ALGORITHM

Let 𝒟 be a compact and convex subset of ℝ^d. The original KW algorithm was designed in the context of maximizing a fixed function by obtaining noisy samples of the function values. We begin by describing the KW algorithm for the case when the function f:𝒟→ℝ to be optimized is fixed. The maximizer of f is denoted θ(f)∈𝒟. The vanilla version of the KW algorithm maintains, at each time-step s an estimate of the function maximizer, denoted as X_s=(X_s(1),X_s(2),…,X_s(d)). It then makes an estimate of the derivatives (∇ f)_X_s(i) of the unknown function f by sampling the function values at points X_s+ c_s e(i),i=1,2,…,d and X_s-c_se(i),i=1,2,…,d, where e(i) is the unit vector with 1 in the i-th place. 
 Let F^+_s(i),F^-_s(i) be the noisy values of the function at X_s+c_se(i) and X_s-c_se(i) respectively.  Denote by Y_s the estimated value of the derivative of function f at X_s. If Y_s=(Y_s(1),Y_s(2),…,Y_s(d)) is an estimate of ∇ f at X_s, we then have that,

    Y_s(i) = F^+_s(i)-F^-_s(i)/2c_s, i=1,2,…,d,
 
where Y_s(i) is an estimate of (∇ f)(i), i.e., the i-th component of the gradient  at X_s.
Once an estimate of the derivative of f at X_s has been made, the KW algorithm then updates the estimate of maximizer as follows,

    X_s+1 = X_s + β_s Y_s,

where β_s is called the learning rate. Typically the step sizes are chosen as β_s = s^-1/2, c_s = s^-1/4. A detailed description of the KW algorithm can be found in <cit.>.



§ PAST WORKS AND CONTRIBUTIONS

A survey of the results on MABP literature can be found in <cit.>. <cit.> is the first work to consider the continum bandit problem.

KW algorithm was introduced in <cit.>, and since then its convergence rate, and the asymptotic distribution of the estimates have been established <cit.>. However, we note that in general the asymptotic convergence rate of an algorithm does not imply regret bounds. 

 <cit.> performs a regret analysis for the KW algorithm when the function is kept constant. In contrast with the work in <cit.> we consider the non-stationary set-up in which the distribution of the reward sequence, or the unknown function to be maximized, changes over time. A regret analysis in this case amounts to controlling the performance of the algorithm over all possible sequences of functions {f_s}_s=1^T,f_s∈𝒞.

We analyze two popular variants of the KW algorithm for the context of non-stationary function maximization i) KW with constant step-size β, where β is the “learning rate" and ii) KW with sliding window of length L, also denoted “memory length". We impose restrictions on the class 𝒞 of allowable functions, and obtain bounds on the regret of KW_β, KW_L algorithms in terms of the degree of non-stationarity, i.e. the quantity Δ_T/T, where Δ_T is the number of times that the function f_s being sampled changes until time T. 

We obtain the optimal learning rate β^⋆, and window length L^⋆ in terms of Δ_T/T. We then show that if these KW variants use optimal β^⋆ (resp. L^⋆), then they are asymptotically efficient, i.e., their cumulative regret is asymptotically 0 if lim_T→∞Δ_T/T=0.


§ NON-STATIONARY FUNCTION MAXIMIZATION AND REGRET

At each time s=1,2,…, an allocation rule 𝒜 chooses the control action X_s∈𝒟⊂ℝ^d. We assume that 𝒟 is convex and compact. The (random) reward earned at time s is then equal to F_s.
 If 𝒜 chooses the action x, then the distribution of the reward at time s, i.e., F_s, is given by G(·,x,f_s(x)), and the mean value of the reward earned is f_s(x), i.e., 𝔼{F_s | X_s = x} = f_s(x). We assume that the functions f_1,f_2,… belong to a function class 𝒞, for each f∈𝒞, f(x) is bounded for all x∈𝒟. Equivalently, the algorithm 𝒜 obtains a “noisy version" of the true function f_s(·) evaluated at x. At time s, Algorithm 𝒜 observes its control action X_s and the reward F_s, however it does not observe the function f_s. The control algorithm/allocation rule 𝒜, for each time s, maps the history {X_n,F^+/-_n}_n=1^s-1 to an action x∈𝒟.

Denote by f_[1:s] the sequence of functions f_1,f_2,…,f_s, and for a function f, denote by θ(f) the value of x that maximizes f. The total regret accumulated by an algorithm 𝒜 until time step T is then defined to be,
 
    ℛ(T,𝒜,f_[1:T]) = 𝔼{∑_s=1^T f_s(θ(f_s)) - f_s(X_s)   },
 
where expectation is taken with respect to the probability measure induced by the control algorithm 𝒜 which makes the choice of the sampling sequence {X_s}_s=1^T and the observations {F^+/-_s}_s=1^T. 

We will be interested in worst-case regret of the algorithm 𝒜, i.e., the quantity,
 
    ℛ(T,𝒜) = sup_f_1:T: f_s ∈𝒞 ∀ s∈[1,T]ℛ(T,𝒜,f_[1:T]).
 
The control algorithm 𝒜 is asymptotically efficient <cit.> if  
 
    lim sup_T→∞ℛ(T,𝒜)/T = 0.
 

 
 
 
Next, we impose some restrictions on the allowable function class 𝒞 that will enable us to obtain meaningful bounds on the regret. 


§ ASSUMPTIONS ON THE FUNCTION CLASS 𝒞
 
We now make certain assumptions on the function class 𝒞 from which the functions f_s,s=1,2,… are chosen. This allows us to obtain non-trivial bounds on the regret (<ref>). The conditions mentioned below are mostly taken from <cit.>. 

 Let f∈𝒞. Then f is three times continuously differentiable for all x∈𝒟, and there exist positive constants K_1,K_2 such that the following hold for all x∈𝒟:

    -K_1 x-θ(f)^2    ≥ (x-θ(f))^⊺∇ f(x)
    ∇ f(x)   ≤ K_2 x-θ(f).

We refer to these conditions as Concavity-Like Condition (CL) and Linearly Bounded Growth Rate (LBG) respectively.



There exists K_3>0 such that for all f∈𝒞 and x∈𝒟,

    f(θ)-f(x)≤ K_3x-θ(f)^2.

We refer to this condition as Quadratically Bounded (QB) function.
 
Other than the various “smoothness" criteria that we assumed on the function f, we also need to ensure that the sampling noise is sufficiently well-behaved. We impose a uniform bound on the noise variance at each sample point, i.e., 


    ∫ (y-f(x))^2 g(y;x,f(x))dμ(y)<σ^2, ∀ f∈𝒞, x∈𝒟,

where μ is a σ finite measure on ℬ(ℝ), i.e., Borel sets of ℝ, and g(·;x,u) is the density of the random reward earned when the control action is x, and the mean value of reward is f(x) = u. 

Examples of function classes 𝒞 which satisfy the above stated conditions can be found in <cit.>. We now state the KW algorithm with fixed step-sizes, i.e., β_s≡β and c_s≡ c.
The following assumption on the function class 𝒞 is in the spirit of the Mean Value Theorem.

Let M_s(X_s): =𝔼(F^+_s-F_s^-/2c|X_s=x,f_s=f ). If the parameter c is chosen to be sufficiently small, 

    M_s(X_s) = ∇ f (X_s+ ϵ_X_s),

where ϵ_X_s < ϵ, and moreover ϵ<c^2.





§ VARIANTS OF KIEFER-WOLFOWITZ ALGORITHM FOR NON-STATIONARY BANDIT OPTIMIZATION

We describe two variants of the basic KW algorithm, that are used when the function f of interest is time-varying. Throughout, for two functions a(t),b(t) we denote  a(t)=o(b(t)) if lim sup_t→∞a(t)/b(t)=0. 


 §.§ KW with fixed step-size β (KW_β)

The KW algorithm with fixed step size has been discussed in <cit.>. It keeps the step-sizes β_s,c_s to be a constant instead of slowly decaying them to 0. Since the parameter β_s corresponds to the “learning" rate, the proposed algorithm places lesser weights to past samples, and hence “eventually forgets the past estimates".  The KW with fixed step-size is stated as follows : Let β and c be “small" positive constants. The estimate of the optimal point at time s evolves as,

    X^i_s+1 = X^i_s  +β{(F^+_s-F^-_s/2c)},

where F^+_s,F^-_s are the measurement values at X_s +/- ce, and the vector e=(1,1,…,1). Henceforth, we will assume that the parameter c has been chosen to be sufficiently small so that the Condition <ref> is satisfied.


 §.§ KW with Sliding Window of length L (KW_L)

In the second variant of the KW algorithm, we fix an integer L>0, which is called “window length" or “memory size". At each time s, the algorithm uses only the latest L function measurements in order to choose the action X_s. This is called KW with sliding window of length L, denoted KW_L. In the below, X_0∈𝒟 has been chosen at time s=0. At each time s=1,2,…, the KW_L algorithm utilizes the estimates of derivatives at past L sample values {X_n}_n=s-L^s-1, and chooses the action X_s according to,

    X_s = X_0 + ∑_n=1^min{L,s}β_n Y_n+ s-L/c_n,
 
where β_n = n^1/2, c_n = n^1/4, and Y_n the estimate of the derivative at X_n and is given by (<ref>). Thus, the algorithm behaves as if at each time s, the original KW algorithm (<ref>)-(<ref>) restarts with an initial value of X_0, and the estimate of the maximizer gets updated L times. 
Since the sample values F^+/-_s that have been obtained at time s will not be utilized for generating actions X_s̃, s̃>s+L, the algorithm “forgets" samples that are “older" than L time units. This finite memory property enables it to adapt to non-stationary function. 


 §.§ Trade-off in choosing learning rates β,L

The step-size β corresponds to the learning rate of KW_β algorithm, while the window length L corresponds to the “memory" of KW_L algorithm.
Due to the non-stationary of the function f_s, there is a fundamental trade-off involved in choosing these parameters. If we have f_s≡ f, then choosing a large vale of L leads to a better convergence of the iterates to θ(f). However, when the f_s is time-varying, a large value of L will introduce the dependence of the current estimate X_s on the past values of f_t,t<s. Since f_t may not be equal to f_s, L must be chosen appropriately in order to achieve a trade-off between the twin objectives of achieving a low-regret, while simultaneoulsy adapting to the changing function f_s. 







§ KW_Β PRELIMINARY RESULTS FOR STATIONARY CASE, F_T≡ F


In this section we present some results that will be used in later sections in order to perform a regret analysis of the two variants of KW algorithm that have been introduced. Throughout this section we will assume that the function f that is being sampled is kept fixed, i.e., f_s≡ f, and θ is the maximizer. We begin by imposing a couple of conditions that are specifically utilized for analyzing the KW_β algorithm. 
 
[Uniform locally Lipschitz]
For x,y∈𝒟 satisfying x-y≤ϵ, we have

    ∇ f(x) -∇ f(y)≤ K_4 x-y, ∀ f∈𝒞.


[Condition on step-size β]
The step size β is chosen as β=c^2/1-α where α∈(0,1).

Let us now write the update equation (<ref>) in more detail. We note that 𝔼(F_s|X_s=x) = f(x),
and moreover the distribution of F_s conditioned on the action X_s=x is denoted G(·;x,f_s(x)) and thus the noise distribution depends both on value of sampled point x, and the value of function f_s(x).
We denote the following,

    Y_s    = F^+_s-F^-_s/2c,
    
    M_s(X_s):    =𝔼(Y_s|ℱ_s) = 1/2c d(X_s,c),
    
    Z_s     = Y_s - 𝔼(Y_s|ℱ_s-1)

where d(x,c) denotes the vector of differences evaluated at x with a step-size of c. Z_s is the noise in observation of derivative.
The recursion (<ref>) can thus equivalently be re-written as,

    X_s+1 = X_s + β(M_s(X_s)+ Z_s).


  




 
 












From the recursion (<ref>), i.e., X_s+1 = (X_s + β M_s(X_s))+β  Z_s we have that,

    X_s+1-θ^2 = X_s-θ^2 + β^2 M_s(X_s)^2
       +2β(X_s-θ) M_s(X_s)^⊺ +β^2 Z_s^2 
       +2β Z_s (X_s -θ+ β M_s(X_s))^⊺.

Next, we use the conditions imposed on 𝒞 and obtain a simple-to-analyze recursion for analyzing the quantity 𝔼X_s-θ^2.

If the Conditions 1,3 and 4 hold true, then for the recursions (<ref>), we have that,

    𝔼{X_s+1-θ^2|ℱ_s }≤γX_s-θ^2+ H(β),

where

    γ   : = 1-2β K_1+2β^2 K^2_2<1,
    
     H(β)    :=β^2σ^2/c^2+2KK_4 βϵ+ 2β^2K_2^2ϵ^2,
 
where K is the diameter of the set 𝒟, step-size β is chosen to be sufficiently small in order that γ<1, and σ̃^2:=4dσ^2



The term β^2M_s(X_s)^2 can be bounded as follows

    β^2 M_s(X_s)^2    = β^2 ∇ f(X_s+ϵ_X_s)^2
       ≤β^2K_2^2 X_s+ϵ_X_s-θ^2
       ≤β^2K_2^2 (X_s-θ+ϵ)^2
       ≤ 2β^2 K_2^2 (X_s-θ^2 + ϵ^2),

where the first equality follows from Condition <ref>, while the first inequality follows from the inequality (<ref>) of Condition <ref>, while second inequality follows from the triangle inequality, and the last inequality follows since for x,y∈ℝ, we have (x+y)^2≤ 2(x^2+y^2).

Next, we have  


    (X_s-θ)M_s(X_s)^⊺ = (X_s-θ)∇ f(X_s+ϵ_X_s)^⊺
        = (X_s-θ)(∇ f(X_s)+∇ f(X_s+ϵ_X_s)-∇ f(X_s))^⊺
        = (X_s-θ)∇ f(X_s)^⊺
        + (X_s-θ)(∇ f(X_s+ϵ_X_s)-∇ f(X_s))^⊺
       ≤ -K_1 X_s-θ^2 + K K_4ϵ,

where the first equality follows from Condition <ref>. For the last inequality, the bound on the first term follows from (<ref>), while that on the second term follows from Cauchy-Schwartz inequality used in conjunction with Condition <ref>. 
 










Next, it follows from (<ref>) that expectation of 2β Z_s (X_s-θ + β M_s(X_s))^⊺ conditioned on ℱ_s-1 is 0.
Also, from Condition <ref> we have that β^2/c^2𝔼( Z_s^2|ℱ_s-1)= β^2𝔼( ∑_i=1^d(F^+_s(i)-F^-_s(i))^2|ℱ_s-1)≤β^24dσ^2/c^2, since the random variable Z_s conditioned on the filtration ℱ_s-1 is the value of noise in the current estimate of the function gradient, and we imposed a uniform bound on the variance of this noise. This yields us 

    𝔼(β^2 Z_s^2 +2β Z_s (X_s-θ + β M_s(X_s))^⊺ |ℱ_s)≤β^2σ̃^2/c^2.

The proof is now completed by substituting the inequalities (<ref>), (<ref>) and (<ref>) in the expression (<ref>) and letting
γ = 1-2β K_1+2β^2K_2^2 and H(β) as in (<ref>).



 §.§ Regret Analysis with fixed f

Taking unconditional expectation in the expression (<ref>), and solving for the ensuing recursions we obtain,

    𝔼X_s-θ^2 ≤ H(β) (1-γ^s)/(1-γ) + x_0-θ^2 γ^s.

It follows from Condition <ref> that the regret at time s, i.e., the quantity  f(θ)-f(X_s) can be bounded in terms of the distance X_s-θ^2, 

    𝔼f(θ)-f(X_s)≤ K_3(H(β) (1-γ^s)/(1-γ) + x_0-θ^2 γ^s).


Thus, we see that the instantaneous regret at time s or equivalently the “distance" of the current estimate X_s from the optimal point θ can be decomposed into the following two components:


  * Regret due to incomplete learning: i.e., the quantity K_3x_0-θ^2 γ^s which is the error between the current estimate X_s and the true maximizer θ. Note that for a fixed value of γ, this component decreases with increasing s, so that the KW_β algorithm improves upon the estimate of θ as it obtains more information about the function f with time.
 

  * Regret due to Noisy Estimate of ∇ f:  K_3H(β) (1-γ^s)/(1-γ) resulting from noisy measurements of the gradients ∇ f(x). Note that if the step-size β was allowed to decay as in (<ref>), then the noise would “average-out" and its limiting contribution will be 0 almost surely.

The regret decompositon (<ref>) throws light on the fundamental trade-off presented in the non-stationary setting. The contribution of 2) is increasing in the learning-rate β.
Indeed, if the function were stationary, i.e., f_t ≡ f, one could asymptotically “stop-learning" by letting β_t → 0 asymptotically, so that 2) would vanish. Due to non-stationarity, β has to be kept constant at a “small value". However, for small values of β, from (<ref>) we have γ≈ 1-2K_1β, so that a small β implies a larger learning regret, i.e., the algorithm takes a long time to learn the function maxima. Thus, the “optimal" choice of β amounts to obtaining an optimal trade-off between the components 1) and 2) of the instantaneous regret. 

 We will now evaluate the expressions for each of these regret terms.
 
Consider the allocation rule (<ref>), i.e, KW with constant step-size β, applied to find the maximizer of an unknown function f∈𝒞. Let the time-horizon be fixed at T, and the function class 𝒞 and step-size β satisfy Conditions 1-6. The cumulative regret incurred during the period {1,2,…,T} can be upper-bounded as

    𝔼(∑_s=1^Tf(X_s)-f(θ)) ≤K_3H(β)T/1-γ + X_0-θ^2 K_3/1-γ.

Consider the learning rate



    β^⋆ =Λ/T^1/(2+α),

where Λ = (K^2/σ̃^2)^1/(2+α) is a constant that depends upon the function class 𝒞, and σ̃^2=4dσ^2. The regret incurred by KW_β^⋆ is then upper-bounded as

    ℛ(T,KW_β^⋆)/T≤K_3/2K_1( Λ^α T^-1/(2+α) +2KK_4Λ^α T^-1/(2+α).
       .+2Λ^3T^-3/(2+α) +K^2/ΛT^-(1+α)/(2+α)),

and hence we have that

    lim sup_T→∞ℛ(T,KW_β^⋆)/T =0.
 
 
 
 
We note that since from Condition <ref> we have that for each f∈𝒞 the regret f(θ)-f(X_s) can be bounded within a factor of K_3 from X_s-θ^2, rest of the discussion will be focused on bounding the latter term, and we will occasionally call it “regret", or “estimation error".

The instantaneous regret at time s is bounded as in (<ref>).
The contribution of the term H(β) (1-γ^s)/(1-γ) 
is upper-bounded by H(β) 1/(1-γ), so that the cumulative regret due to the first term of (<ref>) is bounded by H(β) T/(1-γ).
Also, ∑_s=0^Tx_0-θ^2 γ^s =x_0-θ^2 1-γ^T/1-γ≤ K^21/1-γ, where K is the diameter of the set 𝒟.
This yields us the bound (<ref>). The proof of regret bound (<ref>) follows by substituting the value of β^⋆ from (<ref>), and γ,H(β) from (<ref>),(<ref>) into the bound (<ref>) and performing simple algebraic manipulations.
 
 








 











§ REGRET ANALYSIS OF KW_Β FOR NON-STATIONARY CASE 

We begin by introducing some notation. Since the function f_s changes with time, let us denote by τ_1,τ_2,… the times at which the functions change. We will denote the set {x,x+1,…,y} by [x,y]. Thus, for each of the individual “episodes" comprising of time intervals
[0,τ_1],[τ_1+1,τ_2],[τ_2+1,τ_3],…, we have that f_τ_i=f_τ_i + 1=⋯=f_τ_i+1-1. Also denote by Δ_T the number of episodes until time T.
 For a function f∈𝒞, let θ(f) be the value of x that maximizes the function f.
 Let θ_s denote the maxima of the function f_s. Thus, if s∈ [τ_i+1,τ_i+1], then θ_s=θ_τ_i=θ(f_τ_i). 

 
We will denote by θ_[1:T] the sequence θ_1,θ_2,…,θ_T, similarly for f_[1:T].

Next, we will perform a sample-path performance analysis of KW_β algorithm. Thus, fix a sequence f_[1:T] with the corresponding θ_s sequence given by θ_[1:T] =θ_1,θ_2,…,θ_T. Moreover, for each episode i=1,2,…,Δ_T denote by 
T_i: = τ_i+1-τ_i, to be the “episode-length" or horizon length of episode i. Since the cumulative regret incurred over the time horizon T can be decomposed into the sum of regrets incurred during individual episodes composed of time intervals {[τ_i,τ_i+1-1]}_i=1^Δ_T, the regret incurred by KW_β is then equal to,

    𝔼∑_s=1^T f_s(θ_s) - f(X_s) 
        = ∑_i=1^Δ_T𝔼𝔼{∑_s=τ_i^τ_i+1-1f_τ_i(θ_τ_i)-f_τ_i(X_s) |ℱ_τ_i},

where ℱ_s is the filtration generated by the random variables {(X_n,Y_n,F^+/-_n)}_n=1^s.
We now analyze the regrets incurred during the interval [τ_i,τ_i+1-1].

We will work with the distance X_s-θ_s^2 in lieu of f_s(θ_s)-f_s(X_s), with the understanding that the regret can be upperbounded within a constant factor of the former by using Condition <ref>. Since during the episode i, the function f being sampled, and its maximizer θ(f) are equal to f_τ_i,θ_τ_i respectively, and the inequality (<ref>) holds for all f∈𝒞, we can use the bound (<ref>). Thus, the regret incurred during the i-th episode can be bounded by utilizing the bound (<ref>) developed in Lemma <ref>. However, the term X_0 will be replaced by the quantity X_τ_i-θ_i to account for the difference between the estimate X_τ_i at beginning of episode i, and the true maximizer τ_τ_i during episode i. Similarly, the horizon T will be replaced by the episode length T_i. This yields us,  

    𝔼{∑_s=τ_i^τ_i+1-1X_s-θ_τ_i^2 |ℱ_τ_i}   < H(β) T_i/1-γ + X_τ_i-θ_τ_i^2/1-γ,
       ≤ H(β)T_i/1-γ + K^2/1-γ,

where the second inequality follows since we can bound the distance X_τ_i-θ_τ_i by the diameter of the set 𝒟, i.e., K. Combining the above bound with the tower property of conditional expectations (<ref>), we obtain the following result.

Consider the problem of designing optimal allocation rule for the non-stationary set-up, and for each time s=1,2,…,T, let the function f_s∈𝒞. Let the function class 𝒞 satisfy the conditions 1-5. 

The regret incurred by KW_β algorithm during the time horizon T is upper-bounded by,

    ℛ(T,KW_β) ≤H(β)K_3T/(1-γ) + K^2Δ_TK_3/1-γ,

so that with the learning rate β set equal to

    β^⋆ =Λ(Δ_T/T)^1/(2+α),

where Λ = (K^2/σ̃^2)^1/(2+α),
we have that 

    (ℛ(T,KW_β^⋆)/T)2K_1/K_3≤Λ^α(T/Δ_T)^-1/(2+α)
       +2KK_4Λ^α(T/Δ_T)^-1/(2+α)
       +2Λ^3(T/Δ_T)^-3/(2+α)+K^2/Λ(T/Δ_T)^-(1+α)/(2+α),

so that if Δ_T=o(T), we have

    lim sup_T→∞ℛ(T,KW_β^⋆)/T =0,
 
















 



§ REGRET ANALYSIS OF KW WITH SLIDING WINDOW

We begin with the case where the function is held fixed at f_s≡ f, and time-horizon is fixed at T. Let L denote the length of window, and θ be the maximizer of f. Next, we can apply Chung's Lemma as in Lemma III.5 of <cit.>, in order to analyze the asymptotic properties of the distance X_s-θ.

Let the function class 𝒞 satisfy the Conditions <ref>-<ref>.
For the KW with sliding window of length L applied to obtain the maxima of a stationary function f∈𝒞, the following is true. There exists an integer s_0>0 such that,

    𝔼X_s-θ^2 ≤K_5/√(L), ∀ s>max{s_0, L},

where the constants K_5 and s_0 depend on the function class 𝒞 only through the values K_1,K_2,K_3.


Throughout, we will assume that the window length L has been chosen so that it satisfies L>s_0, and hence the bound above can be written as 

    𝔼X_s-θ^2 ≤ K_5/√(L), ∀ s>L.

Next, we consider the non-stationary set-up. Fix a sequence f_[1:T], and the corresponding θ_[1:T], and as before let Δ_T be the number of episodes until time T. Let us analyze the regret incurred during the i-th episode that is of duration T_i = τ_i+1-τ_i. Since the control action X_s generated at times s∈[τ_i+1,τ_i+1] is a function of the values {Y_n}_n=s-L^s-1, the regret bound (<ref>) which was derived for stationary set-up can now be applied only when s-(τ_i+1)>L or equivalently s>L+ τ_i+1. This gives us the following,

Let KW_L algorithm be applied to the non-stationary function maximization problem. Consider the process X_s-θ during the episode i, which is comprised of time interval [τ_i+1,τ_i+1]. If the episode length τ_i+1-τ_i is greater than L, then, we have

    𝔼{X_s-θ_τ_i^2 | ℱ_τ_i}≤K_5/√(L), ∀ s∈[τ_i+L,τ_i+1].

Thus, the total regret incurred during i-th episode can be bounded as follows,

    𝔼{∑_s∈[τ_i+1,τ_i+1]f_τ_i(θ_τ_i)-f_τ_i(X_s) | ℱ_τ_i}
           ≤ K_3( K_5(T_i-L)^+/√(L) + (L∧ T_i)K)
           ≤K_3K_5T_i/√(L) + LK_3K,

where K is the diamater of the set 𝒟, and the function x^+ = max{x,0}, and for x,r∈ℝ, the function x∧ y=min(x,y).



For the non-stationary bandit problem, the regret incurred by the KW_L algorithm during time period T can be bounded as,

    ℛ(T,KW_L) ≤K_3K_5T/√(L) + LK_3KΔ_T.

The choice of L that minimizes the upper-bound is given by,

    L^⋆ = ( K_5/2KT/Δ_T)^2/3,

so that the regret under KW(L^⋆) is bounded as,

    ℛ(T,KW(L^⋆))/T≤ K_5^2/3K^1/3(Δ_T/T)^1/3[ 2^1/3+1/2^2/3],

Thus, if the number of episodes Δ_T = o(T), then we have,

    lim sup_T→∞ℛ(T,KW(L^⋆))/T = 0.



The bound (<ref>) is obtained by utilizing the upper-bound (<ref>) on the regrets incurred during individual episodes, in conjunction with the tower property (<ref>) of conditional expectations. Rest of the proof involves simple algebraic manipulations, and is omitted due to space constraints. 



 

 IEEEtran


