Non-Stationary Bandits with Habituation and Recovery Dynamics
Yonatan Mintz Anil Aswani Philip Kaminsky Elena Flowers Yoshimi Fukuoka
math.OC cs.LG





























































Mintz et al.




ROGUE Bandits




Non-Stationary Bandits with Habituation and Recovery Dynamics






Yonatan Mintz
School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, ymintz@gatech.edu

Anil Aswani, Philip Kaminsky
Department of Industrial Engineering and Operations Research, University of California, Berkeley, CA 94720, {aaswani,kaminsky,}@berkeley.edu

Elena Flowers
Department of Physiological Nursing, School of Nursing, University of California, San Francisco, CA 94143, 	elena.flowers@ucsf.edu

Yoshimi Fukuoka
Department of Physiological Nursing & Institute for Health & Aging, School of Nursing, University of California, San Francisco, CA 94143, 	yoshimi.fukuoka@ucsf.edu


Many settings involve sequential decision-making where a set of actions can be chosen at each time step, each action provides a stochastic reward, and the  distribution for the reward provided by each action is initially unknown. However, frequent selection of a specific action may reduce the expected reward for that action, while abstaining from choosing an action may cause its expected reward to increase. Such non-stationary phenomena are observed in many real world settings such as personalized healthcare-adherence improving interventions and targeted online advertising. Though finding an optimal policy for general models with non-stationarity is PSPACE-complete, we propose and analyze a new class of models called ROGUE (Reducing or Gaining Unknown Efficacy) bandits, which we show in this paper can capture these phenomena and are amenable to the design of policies with provable properties. We first present a consistent maximum likelihood approach to estimate the parameters of these models, and conduct a statistical analysis to construct finite sample concentration bounds. Using this analysis, we develop and analyze two different algorithms for optimizing ROGUE models: an upper confidence bound algorithm (ROGUE-UCB) and an ϵ-greedy algorithm (ϵ-ROGUE). Our theoretical analysis shows that under proper conditions the ROGUE-UCB and ϵ-ROGUE algorithms can achieve logarithmic in time regret, unlike existing algorithms which result in linear regret. We conclude with a numerical experiment using real world data from a personalized healthcare-adherence improving intervention to increase physical activity. In this intervention, the goal is to optimize the selection of messages (e.g., confidence increasing vs. knowledge increasing) to send to each individual each day to increase adherence and physical activity. Our results show that ROGUE-UCB and ϵ-ROGUE perform better in terms of aggregated regret and average reward when compared to state of the art algorithms, and in the context of this intervention the use of ROGUE-UCB increases daily step counts by roughly 1,000 steps a day (about a half-mile more of walking) as compared to other algorithms in a simulation experiment. 








multi-armed bandits, personalized healthcare, adherence


Kinetic cascade in solar-wind turbulence: 3D3V hybrid-kinetic simulations with electron inertia
    Francesco Califano^1
    December 30, 2023
===============================================================================================


















§ INTRODUCTION


Multi-armed bandits are commonly used to model sequential decision-making in settings where there is a set of actions that can be chosen at each time step, each action provides a stochastic reward, and the distribution for the reward provided by each action is initially unknown.  The problem of constructing a policy for sequentially choosing actions in multi-armed bandits requires balancing exploration versus exploitation, the tradeoff between selecting what is believed to be the action that provides the best reward and choosing other actions to better learn about their underlying distributions.  Bandit models have been applied in a variety of healthcare settings <cit.>.  For instance, <cit.> considered the problem of selecting drugs to give to a patient from a set (where each drug is an action) in order to treat a specific disease (the reward is the improvement in patient health in response to the drug); the bandit policy asymptotically identifies the optimal drug for that particular patient.   Other common applications involve online advertising <cit.>, where selecting an ad to show is an action and the reward is the total number (from a large population) of viewers who click on the ad, as well as in various supply chain settings <cit.>.

However, most bandit models assume that the distribution for the reward provided by each action is constant over time.  This is a reasonable assumption in a large number of applications, such as the ones described above.  However, many applications involve actions that are applied to a single individual, where the rewards depend upon behavioral responses of the individual to the applied actions.  In these behavioral settings, the response to a particular action is not generally stationary.  Frequent selection of a particular action will lead to habituation to that action by the individual, and the reward for that action will decrease each time it is selected.  For example, repeatedly showing the same ad to a single individual may cause the ad to become less effective in soliciting a response from that individual.  Furthermore, another complimentary phenomenon can also occur; refraining for a period of time from showing a particular ad to a single individual may cause the ad to become more effective when reintroduced.

Most techniques for designing policies for decision-making for multi-armed bandits apply to the setting where the rewards for each action are stationary.  However, designing a policy without considering the non-stationarity of a system (when the system is in fact non-stationary) often leads to poor results in terms of maximizing rewards <cit.> because policies eventually converge to a stationary policy. The problem of designing policies for bandit models with non-stationarity has been studied in specific settings, but approaches in the literature are either computationally intractable, or the settings analyzed are not flexible enough to capture the habituation and recovery phenomenon described above.  The aim of this paper is to propose a flexible bandit model that is able to effectively model habituation and recovery, and to present an approach for designing an effective policy for this bandit model.














 §.§ Literature Review


Data-driven decision-making can be categorized into batch formulations and online formulations.  Batch formulations <cit.> use a large amount of data to estimate a predictive model and then use this model for optimization.  Adaptation to new data occurs by reestimating the predictive model, which is done periodically after a specified amount of additional data is collected.  

On the other hand, online formulations involve constructing a policy that is updated every time a new data point is collected.  Bandit models are a particularly important example of online formulations, and there has been much work on constructing policies for stationary bandits.  Approaches for designing policies for stationary bandits include those using upper confidence bounds <cit.>, Thompson sampling <cit.>, Bayesian optimization <cit.>, knowledge gradients <cit.>, robust optimization <cit.>, and adversarial optimization <cit.>.





Restless bandits are a notable class of bandit models that capture non-stationarity, because choosing any single action causes the rewards of potentially all the actions to change.  Though dynamic programming  <cit.>, approximation algorithms <cit.>, and mathematical programming <cit.> have been proposed as tools for constructing policies in this setting, the problem of computing an optimal policy for restless bandits is  PSPACE-complete <cit.>, meaning that designing policies that are approximately optimal is difficult. These models more broadly fall under the class of Partially Observable Markov Decision Processes (POMDPs), a class of problems where the decision maker is interested in solving a Markov Decision Process (MDP) with limited information about the system. The canonical methods for finding optimal policies for POMDPs involve the conversion of the POMDP into an equivalent belief MDP <cit.> in which the states correspond to a probability distribution reflecting the decision maker's belief that they are in a specific state. While for small POMDPs it is possible to solve the belief MDP using dynamic programming approaches <cit.>, in general, since POMDPs are PSPACE-complete, the resulting MDP is often too large to optimize effectively and requires using approximate dynamic programming <cit.>. Therefore, in recent literature, several solutions approaches have been proposed for solving POMDPs, which often involve exploiting the specific structure of the model in question. The framework of ROGUE multiarmed bandits we propose in this paper can be seen as a particular type of POMDP or restless bandit model, with a known deterministic transition model and partially observed rewards. To achieve efficient theoretical bounds and practical performance, the methods we propose are specific to this particular POMDP structure.







Another related research stream designs policies for non-stationary multi-armed bandits with specific structures.  For instance, model-free approaches have been proposed <cit.> for settings with bounded variations, so that  rewards of each action are assumed to change abruptly but infrequently.  These policies have been shown to achieve 𝒪(√(Tlog T)) suboptimality in worst case scenarios but can achieve 𝒪(log T) under proper model assumptions. Recently, there has been interest in studying more structured non-stationary bandits. Two relevant examples are Adjusted Upper Confidence Bounds (A-UCB) and rotting bandits <cit.>, where each action has a set of unknown but stationary parameters and a set of known non-stationary parameters that characterize its reward distribution.  Policies designed for these settings achieve 𝒪(log T) suboptimality, but these settings are unable to capture the habituation and recovery phenomenon that is of interest to us.





 §.§ ROGUE Bandits


In this paper, we define the ROGUE (reducing or gaining unknown efficacy) bandit model, which can capture habituation and recovery phenomenon, and then we design a nearly-optimal policy for this model.  ROGUE bandits are appropriate for application domains where habituation and recovery are important factors for system design; we present two such examples, in online advertising and personalized healthcare, below.












  §.§.§ Personalized Healthcare-Adherence Improving Interventions

One hundred fifty minutes of moderate-intensity aerobic physical activity each week has been shown to reduce the risk of cardiovascular disease, other metabolic disorders, and certain types of cancers <cit.>.  However, maintaining this level of moderate intensity activity is challenging for most adults. As such, proper motivation through providing daily exercise goals and encouragement has been found to be effective in helping patients succeed in being active <cit.>.


In recent years, there has been an increased rate of adoption of fitness applications and wearable activity trackers, making it easier and less costly to implement physical activity programs <cit.>. These trackers and mobile applications record daily activity, communicate activity goals, and send motivational messages. Despite these digital devices having collected a large amount of personal physical activity data, many of the most popular activity trackers provide static and non-personalized activity goals and messages to their users <cit.>. Furthermore, the choice of motivational messages sent to users may have significant impact on physical activity, because if users receive similar messages too frequently they may become habituated and not respond with increased activity, while seldom sent messages may better increase activity due to their novelty and diversity.  Because the ROGUE bandits can model habituation and recovery of rewards for different actions, we believe they present a useful framework for the design of policies that choose which messages to send to users based on data consisting of what messages they received each day and the corresponding amounts of physical activity on those days.

Personalized healthcare has been extensively studied in the operations literature. <cit.> explore the use of behavioral analytics to personalize diet and exercise goals for clinically supervised weight loss interventions in an offline setting. Markov decision processes have also been used for decision-making in personalized healthcare <cit.>. In contrast to bandit models where only the reward for the prescribed action can be observed, these methods broadly assume that the full state of the system can be observed, and thus do not require statistical estimation. Additionally, various multi-armed bandit approaches <cit.> have also been proposed for healthcare problems where habituation and recovery are not significant factors. 



  §.§.§ Online Content Creation and Advertising

Online advertising is one of the fastest-growing industries in the US. In fact, as of 2016, US Internet advertising spending has increased to over $72.5 billion, surpassing the amount spent on TV ads <cit.>. However, as this form of advertising becomes more prevalent, advertisers have been struggling to ensure that ads retain there effectiveness.
This has been attributed to Internet users being habituated by impersonal and standardized ads <cit.> which are rarely varied. For these reasons, there has been significant interest in the operations literature in creating automated systems that can utilize user-level data to better target and customize ads <cit.>. In particular, since the effect of a no-longer-effective advertisement may recover after a user has not seen it for some period of time, incorporating recovery and habituation dynamics into advertising models could yield more effective advertising campaigns.

In general, multi-armed bandit models have been proposed to model online advertising, where each action corresponds to a different type of advertisement, and the reward is equivalent to either a conversion or a click from a prospective consumer. Several approaches have been used to design such an ad targeting system, including adversarial and stochastic multi-armed bandit models <cit.>, and online statistical testing <cit.>. However, while some of these approaches use contextual data to better serve ads to individuals, they are still designed under assumptions of stationarity.  As a result, these approaches will lead to policies that show duplicated ads to individuals, which can potentially causing habituation, whereas other ads that might have recovered efficacy may not be served at all. In contrast, ROGUE Bandit models can explicitly consider the time-varying efficacy each type of ad, and thus directly capture user habituation to a specific ad, and track the recovery of efficacy of a particular ad for a specific individual.












 §.§ Outline

In Section <ref>, we formally introduce the ROGUE bandit model. To the best of our knowledge, this is the first work where a non-stationary bandit model has been defined that is able to capture habituation and recovery phenomenon, and is at the same time amenable to the design of nearly-optimal policies.  Because the ROGUE bandit is a general model, we describe two specific instantiations: the ROGUE generalized linear model and the ROGUE agent. 
 
Next, in Section <ref> we analyze the problem of estimating the parameters of a single action.  We present a statistical analysis of maximum likelihood estimation (MLE) for a single action, and use empirical process theory to derive finite sample bounds for the convergence of parameters estimates.  Specifically, we show that the MLE estimates converge to the true parameters at a 1/√(T) rate.

Section <ref> describes an upper-confidence bound policy for ROGUE bandits, and we call this policy the ROGUE-UCB algorithm.  The main result of this section is a rigorous 𝒪(log T) bound on the suboptimality of the policy in terms of regret, the difference between the reward achieved by the policy and the reward achieved by an optimal policy.  Our 𝒪(log T) bound is significant because this is the optimal rate achievable for approximate policies in the stationary case <cit.>.  We prove our bound using methods from the theory of concentration of measure.

We conclude with Section <ref>, where we introduce a “tuned” version of ROGUE-UCB and then conduct numerical experiments to compare the efficacy of our ROGUE-UCB algorithm to other policies that have been developed for bandit models.  Our experiments involve two instantiations of ROGUE bandit models.  First, we compare different bandit policies using a ROGUE generalized linear bandit to generate data.  Second, we compare different bandit policies using a ROGUE agent to generate data, where the parameters of this bandit model are generated using data from a physical activity and weight loss clinical trial <cit.>.  This second experiment specifically addresses the question of how to choose an optimal sequence of messages to send to a particular user in order to optimally encourage the user to increase physical activity, and it can be interpreted as a healthcare-adherence improving intervention.  Our experiments show that ROGUE-UCB outperforms all other considered bandit policies, and that it achieves logarithmic regret, in contrast to other bandit algorithms that achieve linear regret.



§ DEFINING REDUCING OR GAINING UNKNOWN EFFICACY (ROGUE) BANDITS



This section first describes the stationary multi-armed bandit (MAB) model, in order to emphasize modeling differences in comparison to our ROGUE bandit model that is introduced in this section.  Our goal in defining ROGUE bandits is to have a model that can capture specific non-stationary phenomena found in behavioral applications, and so we next formally introduce the model elements of ROGUE bandits.  To provide better intuition about ROGUE bandits, we also present two specific instantiations of a ROGUE bandit that incorporate different behavioral effects.




 §.§ Stationary MAB Model


The stationary MAB is a setting where there is a finite set of actions 𝒜 that can be chosen at each time step t, each action a ∈𝒜 provides a stochastic reward r_a with distribution ℙ_θ_a, and the parameters θ_a∈Θ for a ∈𝒜 are constants that are initially unknown but lie in a known compact set Θ.  The problem is to construct a policy for sequentially choosing actions in order to maximize the expected reward.  More specifically, let π_t∈𝒜 be the action chosen at time t = 1,…,T.  Then the policy consists of functions π_t(r_π_1,…,r_π_t-1,π_1,…,π_t-1)∈𝒜 that depend on past rewards and actions.  For notational convenience, we will use Π = {π_t(·)}_t=1^T to refer to the policy.  In this notation, the problem of constructing an optimal policy to maximize expected reward can be written as max_Π∈𝒜^T∑_t=1^T 𝔼r_π_t.  Note that certain regularity is needed from the distributions to ensure this maximization problem is well-posed.  One common set of assumptions is that the distributions ℙ_θ_a for a∈𝒜 are sub-Gaussian, and that the reward distributions are all independent.  

For the stationary MAB, we can define an optimal action a^* ∈𝒜, which is any action such that 𝔼r_a^*≥𝔼r_a for all a∈𝒜.  The benefit of this definition is it allows us to reframe the policy design problem in terms of minimizing the cumulative expected regret 𝔼R_Π(T) = 𝔼[  Tr_a^* - ∑_i=1^Tr_π_t], where the quantity r_a^* - r_π_t is known as the regret at time t.  Observe that minimizing 𝔼R_Π(T) is equivalent to maximizing ∑_t=1^T 𝔼r_π_t.  It has been shown by <cit.> that an index policy is optimal for the stationary MAB. Since these indexing policies are difficult to compute, other approximate policies have been proposed <cit.>. Some of the most common policies use upper confidence bounds <cit.>, which take actions optimistically based on estimates of the parameters θ_a. Unfortunately, it has been shown that these index policies and upper confidence bound policies can have arbitrarily bad performance in a non-stationary setting <cit.>.








 §.§ Reducing or Gaining Unknown Efficacy (ROGUE) Bandits
 

A disadvantage of the stationary MAB is that it does not allow rewards to change over time in response to previous actions, and this prevents the stationary MAB model from being able to capture habituation or recovery phenomena.  Here, we define ROGUE bandits that can describe such behavior.  The ROGUE bandit is a setting where there is a finite set of actions 𝒜 that can be chosen at each time step t, each action a ∈𝒜 at time t provides a stochastic reward r_a,t that has a sub-Gaussian distribution ℙ_θ_a,x_a,t with expectation 𝔼r_a,t = g(θ_a,x_a,t) for a bounded function g, the parameters θ_a∈Θ for a ∈𝒜 are constants that are initially unknown but lie in a known compact, convex 
set Θ, and each action a∈𝒜 has a state x_a,t with nonlinear dynamics x_a,t+1 = h_a(x_a,t,π_a,t)



where π_a,t = 1[π_t = a],  h:𝒳×𝔹 →𝒳 is a known dynamics function, and 𝒳 is a compact convex set such that x_a,t∈𝒳 ∀ a,t, and x_a,0 is initially unknown for a∈𝒜.  This particular model formulation is useful for various real world scenarios in which effective system models exist but states are not directly observed due to system or measurement noise. This can be achieved by training models on previously collected controlled data, or by using models based on information from qualified domain experts. In the case of personalized healthcare-adherence interventions and on-line marketing, often times effective models can be generated from previous experimental data (e.g., from RCTs or focus group testing) though state observation in non-laboratory (i.e., not completely controlled) situations is challenging. This data can be used in conjunction with MLE techniques to obtain useful estimates of the system dynamics. In cases where limited data and expertise are available, alternative models ought to be used, the discussion of which is out of the scope of this paper.

The problem is to construct a policy for sequentially choosing actions in order to maximize the expected reward.  Observe that the ROGUE bandit model is non-stationary since the reward distributions depend upon previous actions. This makes the problem of designing policies more difficult than that of designing policies for the stationary MAB.  More specifically, let π_t∈𝒜 be the action chosen at time t = 1,…,T.  Then the policy consists of functions π_t(r_π_1,…,r_π_t-1,π_1,…,π_t-1)∈𝒜 that depend on past rewards and actions.  For notational convenience, we will use Π = {π_t(·)}_t=1^T to refer to the policy.  In this notation, the problem of constructing an optimal policy to maximize expected reward can be written as

    max_Π∈𝒜^T{∑_t=1^T g(θ_π_t,x_π_t,t) : x_a,t+1 = h_a(x_a,t,π_a,t)  for  a ∈𝒜, t ∈{0,...,T-1}}.

This can be reframed as minimizing expected cumulative regret <cit.>: Unlike the stationary MAB, we cannot define an optimal action, but rather must define an optimal policy Π^* = {π^*_t(·)}_t=0^T, which can be thought of as an oracle that chooses the optimal action at each time step.  Then the problem of designing an optimal policy is equivalent to minimizing R_Π(T) = ∑_t=1^T r_π^*_t,t - r_π_t,t or in expectation 𝔼R_Π(T) = ∑_t=1^T g(θ_π^*_t,x_π^*_t,t) - g(θ_π_t,x_π_t,t) subject to the state dynamics defined above, a notion known as either dynamic or tracking regret. Note that since the optimal policy may be quite different from the policy actually implemented, the resulting states and rewards observed at each time period may not necessarily be the same. There have been stronger definitions of dynamic regret proposed in the literature including strongly adaptive regret <cit.>. These definitions have been shown to not hold generally in the bandit feedback case even for models with optimal tracking regret rates <cit.>, and are applied in the context of full information convex on-line optimization with limited total variation. In this paper, we center our analysis on tracking regret as our setting includes both bandit feedback and is model-based without necessarily bounded total variation.



 §.§ Technical Assumptions on ROGUE Bandits


In this paper, we will design a policy for ROGUE bandits that follow the assumptions described below:

 
The rewards r_a,t are conditionally independent given x_a,0,θ_a (or equivalently the complete sequence of x_a,t, π_t and θ_a). 

This assumption states that for any two time points t,t' such that t ≠ t' we have that r_a,t|{x_a,t,θ} is independent of r_a,t'|{x_a,t',θ}, and it is a mild assumption because it is the closest analogue to the assumption of independence of rewards in the stationary MAB.

 
The reward distribution ℙ_θ,x has a log-concave probability density function (p.d.f.) p(r|θ,x) for all x∈𝒳 and θ∈Θ.

This assumption provides regularity for the reward distributions, and is met by many common distributions (e.g., Gaussian and Bernoulli).

Now define f(·) to be L-Lipschitz continuous if |f(x_1) - f(x_2)| ≤ Lx_1-x_2_2 for all x_1,x_2 in the domain of f. We define f to be locally L-Lipschitz on a compact set 𝒮 if it has the Lipschitz property for all points of its domain on set 𝒮. Our next assumption is on the stability of the above distributions with respect to various parameters.

The log-likelihood ratio ℓ(r;θ',x',θ,x) = logp(r|θ',x')/p(r|θ,x) associated with the distribution family ℙ_θ,x is locally L_f-Lipschitz continuous with respect to x,θ  on the compact set 𝒳×Θ for all values of θ',x'∈𝒳×Θ, and g is locally L_g-Lipschitz continuous with respect to x,θ on the compact set 𝒳×Θ.
 

This assumption ensures that if two sets of parameters are close to each other in value then the resulting distributions will also be similar. We make the following additional assumption about the functional structure of the reward distribution family:

 
The reward distribution ℙ_θ,x for all θ∈Θ and x∈𝒳 is sub-Gaussian with parameter σ, and either p(r|θ,x) has a finite support or ℓ(r;θ',x',θ,x) is locally L_p-Lipschitz with respect to r. 
 

This assumption (or a similar type of regularity) is needed to ensure that sample averages are close to their means, and it is satisfied by many distributions (e.g., a Gaussian location family with known variance). 

Last, we impose conditions on the dynamics for the state of each action:




 
The dynamic transition function h is L_h Lipschitz continuous such that L_h ≤ 1.


This assumption is needed to ensure the states of each action do not change too quickly, and it implies that the dynamics are stable. 




 §.§ Instantiations of ROGUE Bandits


The above assumptions are general and apply to many instantiations of ROGUE bandit models. To demonstrate the generality of these assumptions, we present two particular instances of ROGUE bandit models.



  §.§.§ ROGUE Agent
 

Our first instantiation of a ROGUE bandit model consists of a dynamic version of a principal-agent model <cit.>, which is a model where a principal designs incentives to offer to an agent who is maximizing an (initally unknown to the principal) utility function that depends on the incentives.  In particular, consider a setting with a single (myopic) agent to whom we would like to assign a sequence of behavioral incentives π_t ∈𝒜, and the states x_a,t and parameters θ_a are scalars.  Given a particular incentive π_t at time t, the agent responds by maximizing the (random) utility function

    r_t = _r ∈ [0,1] -1/2r^2 - (c_a,t+ ∑_a ∈𝒜x_a,tπ_t,a)r,

where for fixed a∈𝒜 we have that c_a,t are i.i.d. random variables with a distribution ℙ_θ_a such that Var(c_a,t) = σ^2(θ_a) < ∞ and σ^2: ℝ→ℝ_+ is invertible. Moreover, the state dynamics are

    x_a,t+1 = proj_𝒳(α_a x_a,t + b_a (1- π_a,t) -k_a),

  Note the distribution of r_t is fully determined by x_a,t,θ_a,{π_k}_k=0^t, which means the rewards satisfy Assumption <ref>.

We can further analyze the above ROGUE agent model.  Solving the agent's optimization problem (<ref>) gives
 
    r_t|{x_a,t,θ_a} =  0    if   c_a,t≤ - x_a,t, 
    
     1    if   c_a,t≥ 1- x_a,t, 
    
      c_a,t + x_a,t   otherwise

 We can express the distribution of r_t|{x_a,t,θ_a} in terms of the cumulative distribution function (c.d.f.) F(·) and p.d.f. f(·) of c_a,t:

    p(r_t|{x_a,t,θ_a}) = F(-x_a,t)δ(r_t) +(1-F(1-x_a,t)) δ(1-r_t) + f(r_t -x_a,t) 1[r_t ∈ (0,1)].

Though p(r_t|{x_a,t,θ_a}) is not an absolutely continuous function, it satisfies Assumptions <ref> and <ref>, whenever c_t has a log-concave p.d.f. that is Lipschitz continuous, if we interpret the above probability measure p(r_t|{x_a,t,θ_a}) as a p.d.f.

 
 














  §.§.§ ROGUE Generalized Linear Model (GLM)


Dynamic logistic models and other dynamic generalized linear models <cit.> can be interpreted as non-stationary generalizations of the classical (Bernoulli reward) stationary MAB <cit.>. Here, we further generalize these models: Consider a setting where r_a,t|{θ_a,x_a,t} is an exponential family with mean parameter

    μ_a,t = 𝔼r_t = g(α_a^Tθ_a + β_a^Tx_a,t),

for known vectors α_a,β_a, where the action states x_a,t have appropriate dynamics.  In this situation, we can interpret g(·) as a link function of a generalized linear model (GLM). For example, if g is a logit function, then this model implies the rewards have a Bernoulli distribution with parameter

    μ_a,t = 1/1+exp(-(α_a^Tθ_a + β_a^Tx_a,t)).

For the logistic case, the r_a,t is bounded and satisfies Assumptions <ref>-<ref>. These assumptions are also satisfied if r_a,t can be linked to a truncated exponential family distribution restricted to [0,1], meaning if the p.d.f. of r_a,t|{x_a,t,θ_a } is 

    h(r)/F(1)-F(0)exp(T(r)g(α_a^Tθ_a + β_a^Tx_a,t) - A(α_a^Tθ_a + β_a^Tx_a,t)),

where T(r) is a sufficient statistic h is the base measure (not to be confused with dynamics h_a), A is the log-partition function, and F is the full cdf of the un-truncated distribution.  If instead we consider sub-Gaussian exponential families with infinite support, Assumption <ref> is satisfied if the sufficient statistic of the GLM is Lipschitz or bounded with respect to r. While we will mainly consider one-dimensional rewards (i.e., r_a,t∈ℝ), we note that this framework can also be extended to vector and array dynamic GLM's.



§ PARAMETER ESTIMATION FOR ROGUE BANDITS


Our approach to designing a policy for ROGUE bandits will involve generalizing the upper confidence bound policies <cit.> that have been developed for variants of stationary MAB's.  As per the name of these policies, the key step involves constructing a confidence bound for the parameters θ_a, x_a,0 characterizing the distribution of each action a∈𝒜.  This construction is simpler in the stationary case because the i.i.d. structure of the rewards allows use of standard Chernoff-Hoeffding bounds <cit.>, but we can no longer rely upon such i.i.d. structure for ROGUE bandits which are fundamentally non-stationary. This is because in ROGUE bandits the reward distributions depend upon states x_a,t, and so the structure of ROGUE bandits necessitates new theoretical results on concentration of measure in order to construct upper confidence bounds for the relevant parameters.

For this analysis, let the variables {r_a,t}_t=1^T be the observed rewards for action a∈𝒜. It is important to note that the r_a,t here are no longer random variables, but are rather the actual observed values.  Since the reward distributions for each action are mutually independent by the dynamics h_a, we can study the estimation problem for only a single action. Specifically, consider the likelihood p( {r_a,t}_t∈𝒯_a| θ_a,x_a,0 ), where 𝒯_a ⊂{1,...,T} is the set of times when action a was chosen (i.e., π_t = a for t∈𝒯_a).  Let n(𝒯_a) denote the cardinality of the set 𝒯_a.  Using Assumption <ref>, the likelihood can be expressed as

    p({r_a,t}_t∈𝒯_a|θ_a,x_a,0) = ∏_t∈𝒯_ap(r_a,t|θ_a,x_a,t) ∏_t∈𝒯_ap(x_t|θ_a,x_a,t_-).

where t_- = max{s∈𝒯_a : s < t} is the latest observation before time t. Note the MLE of θ_a,x_a,0 is (θ̂_a,x̂_a,0) ∈∏_t∈𝒯_ap(r_a,t|θ_a,x_a,t) ∏_t∈𝒯_ap(x_t|θ_a,x_a,t_-). Observe that since the dynamics h_a are known the one step likelihood p(x_t|θ_a,x_a,t-1) is a degenerate distribution with all probability mass at x_a,t, by perpetuation of the dynamics h with initial conditions x_a,t-1. Thus we can express the MLE as the solution to the constrained optimization problem

    (θ̂_a,x̂_a,0) = min{-∑_t∈𝒯_alog p(r_a,t|θ_a,x_a,t) : x_a,t+1 = h_a(x_a,t,π_a,t)  for  t ∈{0,…,T}},

where we have also taken the negative logarithm of the likelihood (<ref>). In this section, we will consider concentration properties of the solution to the above optimization problem. In particular, since our results concern the joint distributions of a trajectory of values, we require the definition of the following quantity which we call the trajectory Kullback–Leibler (KL) Divergence:

	
	For some input action sequence π_1^T and arm a ∈𝒜 with dynamics h_a, given starting parameter values (θ_a,x_a,0), (θ'_a,x'_a,0) ∈𝒳×Θ, define the trajectory KL–Divergence between these two trajectories with the same input sequence and different starting conditions as:
	
    D_a,π_1^T(θ_a,x_a,0||θ'_a,x'_a,0) = ∑_t∈𝒯_aD_KL(ℙ_θ_a,x_a,t||  ℙ_θ'_a,x'_a,t) =∑_t∈𝒯_aD_KL(ℙ_θ_a,h_a^t(x_a,0)|| ℙ_θ'_a,h_a^t(x'_a,0))

	where h^k_a represents the functional composition of h_a with itself k times subject to the given input sequence, ℙ_θ,x is the probability law of the system under parameters θ,x, and D_KL is the standard KL-Divergence.
	

 If θ^*_a,x^*_0,a for a∈𝒜 are the true parameter values of a ROGUE Bandit model, then we show that 
 
For any constant ξ >0 we have

    P(1/n(𝒯_a)D_a,π_1^T(θ^*_a,x^*_a,0||θ̂_a,x̂_a,0) ≤ξ +  c_f(d_x,d_θ)/√(n(𝒯_a))) ≥ 1 - exp(-ξ^2 n(𝒯_a)/2 L_p^2 σ^2)

where

    c_f(d_x,d_θ) = 8L_f(𝒳)√(π) + 48√(2)(2)^1/d_x+d_θL_f(𝒳×Θ)√(π(d_x+d_θ))

is a constant that depends upon d_x (the dimensionality of 𝒳) and d_θ (the dimensionality of Θ), and D_a,π_1^T(θ_a,x_a,0||θ'_a,x'_a,0) is the trajectory Kullback–Leibler (KL) divergence between two different initial conditions.




 §.§ Conceptual Reformulation of MLE

Our analysis begins with a reformulation of the MLE that removes the constraints corresponding to the dynamics through repeated composition of the function h_a.

Let θ^*_a∈Θ and x^*_a,0∈𝒳 for a∈𝒜 be the true underlying parameters of the system, then the MLE is given by 

    (θ̂_a,x̂_a,0) = _θ_a,x_a,0∈Θ×𝒳1/n(𝒯_a)∑_t∈𝒯_alog p(r_a,t|θ^*_a,h_a^t(x^*_a,0,θ^*_a,π_1^t))/p(r_a,t|θ_a,h_a^t(x_a,0,θ_a,π_1^t))

where the notation h_a^k represents the repeated functional composition of h_a with itself k times, and π_1^t is the sequence of input decisions from time 1 to time t.




The complete proof for this proposition is found in Appendix <ref>, and here we provide a sketch of the proof. Observe that this formulation is obtained by first adding constant terms equal to the likelihood of the true parameter values to the objective function and dividing by the total number of observations (which does not change the optimal solution), and then composing our system dynamics and writing them as explicit functions of the initial conditions. In practice, this reformulation is not practical to solve since clearly θ^*_a,x^*_a,0 are not known a priori and the composite function h_a^t may have a complex form. However, for theoretical analysis this reformulation is quite useful, since for fixed θ_a,x_a,0 taking the expected value of the objective under ℙ_θ^*_a,x^*_a,0 yields

    𝔼_θ^*_a,x^*_a,01/n(𝒯_a)∑_t∈𝒯_alog p(r_a,t|θ^*_a,h_a^t(x^*_a,0,θ^*_a,π_1^t))/p(r_a,t|θ_a,h_a^t(x_a,0,θ_a,π_1^t)) = 1/n(𝒯_a)∑_t∈𝒯_aD_KL(ℙ_θ^*_a,x^*_a,t|| ℙ_θ_a,x_a,t)
     =1/n(𝒯_a)D_a,π_1^T(θ^*_a,x^*_a,0||θ_a,x_a,0).
 
Essentially, we have reformulated the MLE problem in terms of minimizing the KL divergence between the trajectory distribution of potential sets of parameters to the trajectory distribution of the true parameter set. Since we have clear interpretation for the expectation of our objective function we can now proceed to compute concentration inequalities.





































 §.§ Uniform Law of Large Numbers for ROGUE Bandits


Since our estimates are computed by solving an optimization problem, a pointwise law of large numbers is insufficient for our purposes since such a result would not be strong enough to imply convergence of the optimal solutions.  To obtain proper concentration inequalities we must consider a uniform law of large numbers for the MLE problem.
 
For any constant ξ > 0 we have

    P(sup_θ_a,x_a,0∈Θ×𝒳|1/n(𝒯_a)∑_t∈𝒯_alog p(r_a,t|θ^*_a,h_a^t(x^*_a,0,θ^*_a,π_1^t))/p(r_a,t|θ_a,h_a^t(x_a,0,θ_a,π_1^t))
     - 1/n(𝒯_a)D_a,π_1^T(θ^*_a,x^*_a,0||θ_a,x_a,0) | > ξ +   c_f(d_x,d_θ)/√(n(𝒯_a))) ≤exp(-ξ^2 n(𝒯_a)/2L_p^2σ^2)

where

    c_f(d_x,d_θ) = 8L_f(𝒳)√(π) + 48√(2)(2)^1/d_x+d_θL_f(𝒳×Θ)√(π(d_x+d_θ))

is a constant.


We will prove this result in several steps, the first of which uses the following lemma:

 
Consider the mapping

    φ({r_t}_t=1^n(𝒯_a))=sup_θ_a,x_a,0∈Θ×𝒳|1/n(𝒯_a)∑_t∈𝒯_alog p(r_a,t|θ^*_a,h_a^t(x^*_a,0,θ^*_a,π_1^t))/p(r_a,t|θ_a,h_a^t(x_a,0,θ_a,π_1^t)) - 1/n(𝒯_a)D_a,π_1^T(θ^*_a,x^*_a,0||θ_a,x_a,0) |.

The mapping φ is L_p-Lipschitz with respect to {r_t}_t=1^n(𝒯_a).

A detailed proof is provided in Appendix <ref>, and the main argument of the proof relies on the preservation of Lipschitz continuity through functional composition and pointwise maximization. This result is necessary since showing that objective value variations are bounded is a prerequisite for the formalization of concentration bounds. Next we consider the Lipschitz constant of the log-likelihood with respect to the parameters.

 
For any r∈ℝ, θ̅∈Θ, x̅∈𝒳, define the function ℓ: Θ×𝒳×{1,...,T}→ℝ such that ℓ(θ,x,t) = logp(r|θ̅,h_a^t(x̅,θ̅,π_1^t))/p(r|θ,h_a^t(x,θ,π_1^t)).  Then for fixed t, the function ℓ is Lipshitz with constant L_f. Moreover, for all (x,θ) ∈𝒳×Θ and for all t,t' ∈{1,...,T} we have that |ℓ(θ,x,t) -ℓ(θ,x,t')| ≤ L_f(𝒳), where (𝒳) = max_x∈𝒳x_2.

The result of this lemma can be derived using a similar argument to that of Lemma <ref>, by noting that the dynamics are bounded and Lipschitz, and then applying Assumption <ref>. The full proof of this lemma is in Appendix <ref>. Next we show the expected behavior of π is bounded.

 
Let φ be defined as in Lemma <ref>. Then 𝔼φ({r_t}_t=1^n(𝒯_a)) ≤c_f(d_x,d_θ)/√(n(𝒯_a)), where 

    c_f(d_x,d_θ) = 8L_f(𝒳)√(π) + 48√(2)(2)^1/d_x+d_θL_f(𝒳×Θ)√(π(d_x+d_θ)).








































The result of this lemma is derived by first using a symmetrization argument to bound the expectation by a Rademacher average and then using metric entropy bounds to derive the final result, and a complete proof is found in Appendix <ref>. Additional insight into these results is provided by the following remarks:

The result of Lemma <ref> implies that 𝔼φ({r_a,t}_t=1^n(𝒯_a)) = 𝒪(√(d_x+d_θ/n(𝒯_a)))


An improved constant can be achieved by using weaker metric entropy bounds (namely the union bound) however this would yield a bound of order 𝒪(√((d_x+d_θ)log n(𝒯_a)/n(𝒯_a)))








































Using the results of Lemmas <ref>–<ref>, we can complete the sketch of the proof for Theorem <ref>. Lemma <ref> says the mapping φ is L_p-Lipschitz, and combining this with Assumption <ref> implies that by Theorem 1 in <cit.> we have with probability at most exp(-ξ^2 n(𝒯_a)/2ϵ^2L_P^2σ^2) that the maximum difference between the empirical KL divergence and the true trajectory divergence is sufficiently far from its mean. Then using Lemma <ref> we obtain an upper bound on this expected value with the appropriate constants. For a complete proof of the theorem please refer to Appendix <ref>. This theorem is useful because it indicates the empirical KL divergence derived from the MLE objective converges uniformly in probability to the true trajectory KL divergence.



 §.§ Concentration of Trajectory Divergence

We can complete the proof of Theorem <ref> using the results of Theorem <ref> and the definition of the MLE. First, Theorem <ref> implies that with high probability the trajectory divergence between the MLE parameters θ̂_a,x̂_a,0 and true parameters θ^*_a,x_a,0^* is within 𝒪(√(d_x+d_θ/n(𝒯_a))) of the empirical divergence between these two sets of parameters. Then, since θ̂_a,x̂_a,0 minimize the empirical divergence and the empirical divergence of θ^*_a,x^*_a,0 is zero, this means that the empirical divergence term is non-positive. Combining these two facts yields the concentration bound of Theorem <ref>, and the complete proof is given in Appendix <ref>.











 
We conclude this section with an alternative statement of Theorem <ref>.








 
For α∈ (0,1), with probability at least 1-α we have

    1/n(𝒯_a)D_a,π_1^T(θ^*_a,x^*_a,0||θ̂_a,x̂_a,0) ≤ B(α)√(log(1/α)/n(𝒯_a)).

Where B(α) = c_f(d_x,d_θ)/√(log(1/α))+L_pσ√(2).

This result can be obtained by making the substitution ξ = L_pσ√(log(1/α)/n(T_a)) into the expression in Theorem <ref>. This corollary is significant because it allows us to derive confidence bounds for our parameter estimates with regards to their trajectory divergence. Note that the term B(α) differs from the term that would be derived by Chernoff-Hoeffding bounds applied to i.i.d. random variables by the addition of c_f(d_x,d_θ)/√(log(1/α)) to the standard variance term. The reason for this addition is that since we are using MLE for our parameter estimation our estimates will be biased, and this bias must be accounted for in the confidence bounds. Though there may exist specific models where MLE can provide unbiased estimates, we will only present analysis for the more general case.



§ POLICIES FOR OPTIMIZING ROGUE MODELS


This section develops two different policies which could be used to achieve effective regret bounds for ROGUE bandit models. These are a ROGUE Upper Confidence Bounds (ROGURE-UCB) policy, and an ϵ-greedy policy (ϵ-ROGUE). While both policies exhibit good theoretical performance, each policy has different advantages during implementation, because of how they trade off exploration-exploitation and computation. ϵ-ROGUE is computationally efficient to implement, but during our experiments it tended to over-explore in the short term for many instances of ROGUE models. This may be because ϵ-greedy policies explore uniformly, and even in the stationary case ϵ-greedy policies are sensitive to their tuned parameters and do not perform well with multiple sub-optimal choices <cit.>.  On the other hand, ROGUE-UCB is a more computationally intensive policy; however, in our experiments it was capable of finding optimal arms with fewer samples then ϵ-ROGUE. This makes ROGUE-UCB  more suitable for settings that require faster parameter identification such as those encountered in healthcare, while ϵ-ROGUE is better suited for low risk but high volume settings such as online advertising.

Alhough several upper confidence bounds (UCB) policies have been proposed in the non-stationary setting <cit.>, these existing policies provide regret of order 𝒪(√(Tlog T)) in the general adversarial case, but can achieve 𝒪(log T) regret under certain model-based assumptions.  In contrast, both the ROGUE-UCB and ϵ-ROGUE policies we construct achieve regret of order 𝒪(logT) under more general assumptions, which is optimal in the sense that it matches the lowest achievable rate for approximate policies in the stationary stochastic setting. We theoretically analyze the cumulative regret of both of these algorithms in the stochastic setting, and also develop a parameter free bound on regret for ROGUE-UCB. The algorithms we propose in this paper are designed for the stochastic ROGUE bandit setting.  We leave the discussion of the adversarial ROGUE bandit setting for future research.



 §.§ ROGUE Upper Confidence Bounds (ROGUE-UCB) Policy




 Pseudocode for ROGUE-UCB is given in Algorithm <ref>, and the algorithm is written for the situation where the policy chooses actions over the course of T time periods labeled {1,...,T}.  The upper confidence bounds used in this algorithm are computed using the concentration inequality from Theorem <ref>. Much like other UCB policies, for the first |𝒜| time steps of the algorithm each action a will be tried once. Then after this initialization, at each time step, we will first compute the MLE estimates of the parameters for each action (i.e., (θ_a,x̂_0,a) ∀ a∈𝒜) and then use Theorem <ref> to form the upper confidence bound on the value of g(θ_a,x_t,a), which we call g^UCB_a,t. Our approach for forming these bounds is similar to the method first proposed by <cit.> for the KL-UCB algorithm used for stationary bandits. Here, since we know that with high probability the true parameters belong to 𝒳 and Θ, we find the largest possible value of g(θ_a,x_t,a) within these sets. Finally, we choose the action that has the largest upper confidence bound, observe the result, and repeat the algorithm in the next time step. Methods for solving the component optimization problems effectively are highly dependent upon the underlying model and dynamics. In general when h_a is nonlinear these problems will be non-convex; however, the MLE problem can be computed using dynamic programming or filtering approaches while the UCB problem can be computed directly or through a convex relaxation as a relaxation solution will still be a valid UCB. In implementation, if d_x,d_θ are small, then enumeration and fine grid search methods can be employed. We leave the discussion of more efficient algorithms for specific ROGUE models for future research.



The key theoretical result about the ROGUE-UCB algorithm concerns the regret R_Π(T) of the policy computed by the ROGUE-UCB algorithm.
 
The expected regret 𝔼R_Π(T) for a policy Π computed by the ROGUE-UCB algorithm is

    𝔼R_Π(T) ≤ L_g(𝒳×Θ)∑_a∈𝒜(A(|𝒜|)^2 4log T/δ_a^2 + π^2/3).

where A(x) = B(x^-4), and 

    δ_a    = min{1/n(𝒯_a)D_a,π_1^T(θ_a,x_a,0||θ_a',x_a',0): |g(h_a^t(x_a,0),θ_a) - g(h_a^t(x_a',0),θ_a')| ≥ϵ_a/2}
    ϵ_a    = min_a'∈𝒜∖ a,t {|g(θ_a,h_a^t(x_a,0)) -g(θ_a',h_a^t(x_a',0))|: g(θ_a,h_a^t(x_a,0)) ≠ g(θ_a',h_a^t(x_a',0))}

are finite and strictly positive constants.


This corresponds to a rate of order 𝒪(log T) when lim inf_Tδ_a > 0.  In fact, lim inf_Tδ_a > 0 for many settings such as (with appropriate choice of model parameter values) the ROGUE GLM and ROGUE agent defined in Section <ref>.
























To prove Theorem <ref>, we first present two propositions. The first proposition bounds the expected regret R_Π(T) by the number of times an action is taken while it is suboptimal.

 
For a policy Π calculated using the ROGUE-UCB algorithm, if T̃_a = ∑_t=1^T 1{π_t = a, a ≠π^*_t}, then 𝔼R_Π(T) ≤ L_g(𝒳×Θ)∑_a∈𝒜𝔼T̃_a.










For this proposition, we first use Assumption <ref> to upper bound the value of the regret with respect to the L_g and the diameter of the parameter set. Then since we are left with a finite sum of positive numbers, we can rearrange the summation term to obtain the expected number of suboptimal actions. For the detailed proof, please see Appendix <ref>. Next we proceed to prove a bound on the expected number of times a suboptimal action will be chosen.
 
For a policy Π calculated using the ROGUE-UCB algorithm, we have that 𝔼T̃_a ≤ A(|𝒜|)^2 4log T/δ_a^2 + π^2/3, where A(t) = B(t^-4), δ_a = min{1/n(𝒯_a)D_a,π_1^T(θ_a,x_a,0||θ_a',x_a',0): |g(h_a^t(x_a,0),θ_a) - g(h_a^t(x_a',0),θ_a')| ≥ϵ_a/2}, and ϵ_a = min_a'∈𝒜∖ a,t {|g(θ_a,h_a^t(x_a,0)) -g(θ_a,h_a^t(x_a,0))|: g(θ_a,h_a^t(x_a,0)) ≠ g(θ_a,h_a^t(x_a,0))}.



































To prove this proposition, we proceed in a manner similar to the structure first proposed by <cit.>. We must show that if an action is chosen at a time when it is suboptimal, then this implies that either we have not properly estimated its parameters (i.e., have not explored enough) or the true values of the parameters x_a,0,θ_a or x_π^*_t,0,θ_π^*_t are not contained inside their confidence bounds. Using these facts, we use Theorem <ref> to show that the probability that all of these events occurring simultaneously is bounded, and then upper bound the expected number of times these events can occur.  Combining the results of Propositions <ref> and <ref>, we thus prove the desired result of Theorem <ref>.  The full proofs of Proposition <ref> and Theorem <ref> are provided in Appendix <ref>.

Developing a regret bound in the ROGUE setting that is free of problem-dependent parameters is quite challenging. This is because in contrast to the stationary setting, if ϵ_a,δ_a are dependent on T and can arbitrarily approach zero in the long run, the bound presented in Theorem <ref> might not hold. This behavior, however, depends greatly on the rate at which  ϵ_a,δ_a approach zero. For instance,  it is clear that if ϵ_a = o(1/T), ∀ a ∈𝒜 then the bound from Theorem <ref> might in fact be loose, so to achieve the worst case rate ϵ_a,δ_a must approach zero quite slowly. In Section <ref> we provide additional discussion of how these rates may impact regret and can be computed in certain settings.  In this section, we provide the following problem-dependent parameter free bound for the case when ϵ_a,δ_a are bounded from below away from zero:

 
If there exists ϵ such that ∀ a ∈𝒜 and ∀ T ϵ_a ≥ϵ, then in the worst case ROGUE-UCB achieves  𝔼R_Π(T) = 𝒪(T^4/5(|𝒜|A(|𝒜|)^2σ^2log T)^1/5).


The proof of this corollary can be found in Appendix <ref>, but here we present a sketch. Essentially, if the ϵ_a are bounded from below by ϵ, then for small ϵ we would expect the regret to behave in the worst case linearly, namely at ϵ T, and not according to the 𝒪(log T) bound presented in Theorem <ref>. Thus, the result follows from finding an ϵ that minimizes both of these regret bounds and substituting into the given expressions. Unlike the stationary case, for which UCB1 has a worst case rate of 𝒪(√(Tlog T)), we note that this is a 𝒪((T^4log T)^1/5) worst case rate, and so is slightly worse but still sub-linear. This is not surprising, and can be attributed to the high variability of the problem parameters. In fact, this agrees with the bounds computed by <cit.>, who show that if total variation is proportional to T, we expect worst case regret of the form 𝒪(T^2 +β/3) for some β∈ (0,1], a rate our result meets up to a log factor. 




 §.§ ϵ-Greedy Policy for ROGUE Bandits


In this section we develop an ϵ-greedy policy that can be used to optimize ROGUE bandits. The pseudo code of this method can be found in Algorithm <ref>. At each time step t, the algorithm samples a standard uniform random variable u_t. If u_t is above some threshold ϵ_t the algorithm performs a pure exploration step (i.e. chooses an arm from 𝒜 uniformly randomly). Otherwise, the algorithm performs a greedy optimization step by computing the MLE values  for the expected rewards of each of the arms, and then playing the arm with the highest MLE expected reward. Note that ϵ_t decreases as the bandit is played – this is critical to ensure that as the MLE estimates improve the algorithm makes fewer unnecessary explorations. Additionally, if ϵ_t is held at some constant value ϵ, it is easy to see that this results in linear time regret, specifically a lower bound regret of Ω(ϵ T).  


We next show the following theoretical results for the cumulative regret performance of ϵ-ROGUE:



	 
		For any time T> c|𝒜|/δ^2_min, the probability a sub-optimal arm is pulled for a policy Π computed by the ϵ-ROGUE algorithm is at most:
		
    8L_p^2σ^2/δ^2_minexp(c_f(d_x,d_θ)^2/2L_p^2σ^2)(eTδ_min^2/|𝒜|c)^-c/8L_p^2σ^2 + c/δ_min^2(logeTδ_min^2/|𝒜|c)(eTδ_min^2/|𝒜|c)^-3c/28δ_min^2 + c/δ_min^2T

		Where δ_min≤min_a ∈𝒜δ_a.
	

	
		This instantaneous regret bound implies asymptotic cumulative regret of order 𝒪(log(T)) since the first several terms are o(1/T) for a sufficiently large choice of constant c, namely c ≥max{8L_p^2σ^2, 28δ_min^2/3}. 
	
	
	A complete proof for Theorem <ref> can be found in Appendix <ref>, but here we provide a sketch of the proof. Essentially, to bound the probability of a sub optimal arm being pulled, we first use the union bound to bound it from above by the probability it was pulled randomly in an exploration step or during an exploitation step.  We then bound the probability of subotimality in the exploration step by using the concentration bounds from Theorem <ref>.




 §.§ Discussion of the Behavior of ϵ_a and δ_a


The constants ϵ_a and δ_a are critical for the results presented in the previous two sections. However, these quantities have a non-trivial dependence on the underlying model of the ROGUE bandit as well as the algorithm utilized, and are thus difficult to analyze in the most general case. Below we present two different examples meant to illustrate how ϵ_a and δ_a may behave for certain models and how this may impact performance.



  §.§.§ Exponentially Small ϵ_a,δ_a
 For this section, consider a two-armed ROGUE bandit model with arms 𝒜:= {0,1} such that θ_1=θ_0=0 and r_a,t∼𝒩(x_a,t,1) ∀ a ∈𝒜, 𝒳:=[0,1], hence g(θ_a,x_a,t) = x_a,t. Define the dynamics for each arm as follows:

    h_0(x_0,t,π_0,t) = proj_[0,1]( 0 · x_0,t + 0 ·π_0,t) 
       h_1(x_1,t,π_1,t) = proj_[0,1]( 0.5 · x_1,t + 0 ·π_1,t)


Observe that here arm 0 stays at state x_0,t = 0 for all time periods t, while the state of arm one can be described by x_1,t = (1/2)^t x_1,0. So if x_1,0 > 0.  As time progresses, the expected reward of each arm get exponentially close, and hence ϵ_a decreases exponentially. Moreover, using the KL divergence of normal distributions, it is clear that  δ_a = Ω((1/2)^2T x_1,0^2). This means that asymptotically the regret bounds provided in Sections <ref> and <ref> would no longer be of order 𝒪(log T). 









  §.§.§ Constant Bounded ϵ_a,δ_a

As before, consider a two armed ROGUE bandit model with arms 𝒜 := {0,1} such that θ_1 = θ_0 = 0 and r_a,t∼𝒩(x_a,t,1) ∀ a ∈𝒜, 𝒳 := [0,1], and g(θ_a,t,x_a,t) =x_a,t. Furthermore define the dynamics of each arm as follows:

    h_0(x_0,t,π_0,t) = proj_[0,1](x_0,t + 2 ·π_0,t - 1) 
        h_1(x_1,t,π_1,t) = proj_[0,1](x_1,t - 2 ·π_0,t + 1)


Here, the dynamics are only with respect to the action taken on arm 0 since in a two armed bandit setting, by definition π_0,t = 1 - π_1,t.  From these dynamics it is clear that regardless of which arm is played, whenever an action is taken the reward of of the played arm will decrease to 0 while the reward of the unplayed arm will increase to 1. Hence, for any horizon T, in this case ϵ_0 = ϵ_1 = min{1, |x_0,0 - x_1,0|} if x_0,0≠ x_1,0 and ϵ_0 = ϵ_1 = 1 otherwise. Using the KL divergence between normal distributions with different means and equal variances, this implies that δ_0 = δ_1 ≥1/8min{1, (x_0,0 - x_1,0)^2 } when x_0,0≠ x_1,0 and δ_0 = δ_1 = 1/8 otherwise. for any horizon T. This holds asymptotically, and so since δ_a,ϵ_a are bounded asymptotically, this indicates that the regret results from Sections <ref> and <ref> will hold and regret will be of order 𝒪(log T).





















§ NUMERICAL EXPERIMENTS


In this section, we perform two numerical experiments where the policies computed by the ROGUE-UCB and ϵ-ROGUE algorithms are compared against the policies computed by other non-stationary bandit algorithms. The first experiment considers the ROGUE GLM described in Section <ref>, and  specifically looks at the logistic regression instantiation of ROGUE GLM. We use synthetically generated data for this first experiment. Next, we perform an experiment in the context of healthcare-adherence improving interventions to increase physical activity, which can be modeled using the ROGUE agent from Section <ref>. Using real world data from the mDPP trial <cit.>, we show how ROGUE-UCB and ϵ-ROGUE can be implemented to personalize messages for participants in this intervention. All experiments in this section were run using Python 3.5.2 and Anaconda on a laptop computer with a 2.4GHz processor and 16GB RAM.

Our goal with these experiments is to show how each of the bandit algorithms performs in terms of long run reward and how quickly the algorithms can learn the underlying system state. While these problems are equivalent in the stationary bandit setting, in the non-stationary setting incorrect actions taken due to improper system identification may still have rewards that are quite close to optimal. As such, we consider two different performance measures for each algorithm, the tracking regret which measures how quickly the unknown model parameters are identified, and the long run reward. Our results show that both the Tuned ROGUE-UCB and ϵ-ROGUE algorithms outperform the other candidate algorithms both in terms of long run average reward and average regret. However, while both ROGUE algorithms have similar performance in the long run, ROGUE-UCB tends to identify model parameters faster then ϵ-ROGUE as it performs less exploration but at a slightly greater computational cost at each time step. This suggests that ROGUE-UCB is most useful for settings that require fast identification, such as settings that require higher consideration for risk and fairness (e.g., healthcare settings), while ϵ-ROGUE is ideal for low risk settings where computational resources are the main implementation constraint (e.g., targeted advertising). 



 §.§ Tuned ROGUE-UCB

As has been noted for other UCB policies <cit.>, the high probability bounds derived theoretically for these methods are often too conservative. While the 𝒪(√(logt/n(𝒯_a))) is a tight rate, the term A(t) is too conservative. Drawing inspiration from <cit.> who used asymptotic bounds for Tuned UCB, we similarly construct a variant of our algorithm: This variant is described in Algorithm <ref> and called Tuned ROGUE-UCB. Using the results of <cit.>, we note that if the MLE θ̂_a,x̂_a,0 are in the interior of the feasible region and are consistent, then they are asymptotically normally distributed with a variance equal to their Fisher information. Using these results and the delta method <cit.>, we can derive the quantity 𝒮_a,π_1^T(θ_a,x_a,0||θ̂_a,x̂_a,0) = 1/n(𝒯_a)^2∇_θ',x'D_a,π_1^T(θ_a,x_a,0||θ',x')^T ℐ_{r_t}_t∈𝒯_a(θ',x')^-1∇_θ',x'D_a,π_1^T(θ_a,x_a,0||θ',x')|_θ',x'=θ̂_a,x̂_a,0, which is the asymptotic variance of the average trajectory KL-Divergence.  Here, η is a constant that corresponds to the maximum value of the KL-divergence; ℐ_{r_t}_t∈𝒯_a(θ',x') represents the observed trajectory Fisher information, which can be calculated as ℐ_{r_t}_t∈𝒯_a(θ',x') = ∑_t∈𝒯_aℐ_r_t(θ',x'), due to Assumption <ref>. As an implementation note, if the empirical information matrix is singular, then the Moore-Penrose pseudoinverse should be used to achieve similar asymptotic results <cit.>. Note that although these asymptotic bounds work well in practice, they are not high probability bounds and do not provide the same theoretical guarantees as the ROGUE-UCB algorithm. A full analysis of regret for Tuned ROGUE-UCB is beyond the scope of this work. Instead, we only consider empirical analysis of this algorithm to show its strong performance. 








 §.§ Experimental Design

We examined two settings for our experiments, which correspond to the instantiations of ROGUE bandits presented in Sections <ref> and <ref>. For each of the scenarios, we compared the Tuned ROGUE-UCB algorithm and ϵ-ROGUE algorithms with ϵ_t = 1/t to policies determined by six alternative methods. For each scenario, we present two result metrics: cumulative regret of each algorithm in that scenario and the average reward to date of the algorithm. While these two measures are related, a key difference is that in the non-stationary setting sub-optimal actions may not have a significantly lower expected reward than the optimal action at all time periods. Hence, while an algorithm may incur a significant amount of regret it could still achieve a high amount of reward. The five alternative algorithms we used for comparison are as follows: 



  * Pure Exploration: First, we considered a completely random, or “pure exploration” algorithm, which chooses an action uniformly at random from the set of available actions. 



  * Stationary Upper Confidence Bound (UCB1): Next, we considered the UCB1 algorithm <cit.>, which is designed for stationary bandits. This approach uses the sample average as an estimate of the expected reward of each action and utilizes a padding upper confidence bound term derived from Hoeffding's bound. In our experiments, we implemented Tuned UCB1 <cit.>, which replaces the theoretical constants by the asymptotic variance of the sample average and a small constant that corresponds to the maximum variance of a Bernoulli random variable (since the rewards are bounded between 0 and 1).



  * Discounted Upper Confidence Bounds (D-UCB): D-UCB is an upper confidence bound approach designed for non-stationary systems. It utilizes an exponentially weighted average of the reward observations to estimate the expected reward at the current time period and a square root padding function to provide upper confidence bounds <cit.>. The weighted average is constructed with a positive discount factor that decreases the influence of older observations on the reward estimate to zero as time goes on. We implemented this algorithm with its optimal theoretical parameters, as described in <cit.>.
 


  * Sliding Window Upper Confidence Bounds (SW-UCB): The next approach we considered is the SW-UCB approach. This algorithm considers a fixed window size of how many action choices to “keep in memory”, and computes the estimate of the expected action rewards as the average of these choices <cit.>. We implemented this algorithm with its optimal theoretical parameters as proposed by <cit.>.



  * Exploration and Exploitation with Exponential Weights (EXP3): The next bandit algorithm we considered in our experiments is the EXP3 algorithm. Essentially, EXP3 is a modification of the exponential weights algorithm used in online optimization to the bandit setting where not all action rewards are observed <cit.>. Though EXP3 is designed for stationary bandits, unlike UCB approaches that assume a stochastic setting, it is meant for  adversarial bandits, which makes it potentially robust to non-stationarity. The particular variant of EXP3 we utilized is EXP3.S proposed by <cit.>, which is designed for arbitrary reward sequences, using the theoretically optimal parameters as proposed by the authors. Specifically, the learning rate γ was set to min{1,√(|𝒜|/Tlog(|𝒜|T))} and prior weighting α was set to 1/T. Essentially, this parameter tuning assumes the full horizon the bandit is to be run for is known. 


  * Restarting EXP3 (REXP3): The last bandit algorithm we considered in our experiments is the REXP3 algorithm proposed by <cit.>. This algorithm is a modification of the EXP3 algorithm for a non-stationary setting, where the none-stationarity has bounded total variation. This approach  performs EXP3 update steps for a preset number of arm pulls, and once this number is reached, the algorithm resets as if it is restarting. The length of the period before the reset depends on the total time horizon of the bandit, as well as the total variation of the underlying reward. In our experiments, we tuned this algorithm using various values for the total variation and found that the best results overall were achieved by setting this value to be proportional to the total horizon T, so we only present these results.





 §.§ ROGUE Logistic Regression

For this experiment, we consider the logistic regression instantiation of the ROGUE GLM presented in Section <ref>.  Our setup includes two actions whose rewards r_t,a are Bernoulli with a logistic link function of the form g(x,θ) = 1/1+ exp(-aθ - b x). The initial parameters and dynamics matrices for each of the actions are presented in Table <ref>. Here, the sets 𝒳 and Θ were set to [0,1]. Action 0 has a significant portion of its reward dependent on the time varying state x_t, and recovers its reward slowly but also decreases slowly. On the other hand, Action 1 has more of its expectation dependent on the stationary component θ, but it expectation decreases faster than that of Action 0. 
  


The experiments were run for 20,000 action choices and replicated 30 times for each of the candidate algorithms. Figure <ref> shows the cumulative regret accrued by each of the algorithms averaged across the replicates, and Figure <ref> shows the average reward per action for each algorithm averaged across the replicates. As expected in these experiments, the UCB1 algorithm achieves linear regret since it assumes a stationary model and thus converges to a single action, which causes a large gap between the expectations of the two actions. Interestingly, SW-UCB and D-UCB also perform worse than random choices. A key note here is that D-UCB and SW-UCB assume that action rewards do not change frequently and are independent of the choices. However, D-UCB outperforms SW-UCB since the weighted average contains more information about the trajectory of the expected reward of each action while data from earlier choices are removed from the estimates in the sliding window. EXP3, REXP3, and random action selection perform approximately the same in terms of both regret and expected reward. This is unsurprising because the weighting scheme in EXP3 emphasizes the rewards of the past action states as opposed to current action states, and high total variation essentially reduces the restart horizon of REXP3 which means it retains less information about the overall reward trajectory. In terms of both regret and reward, Tuned ROGUE-UCB and ϵ-Rogue substantially outperform the other approaches.

In Figures <ref> and <ref> we compare the two model-based approaches in terms of their cumulative regret and average reward, respectively. While the other approaches seem to obtain linear regret, both ROGUE-UCB and ϵ-ROGUE do in fact have regret on the order of 𝒪(log T) in this experiment. Moreover, in this particular non-stationary setting we observe that these two algorithms have very similar long run average rewards while ROGUE-UCB obtains slightly better cumulative regret. This can be attributed to ROGUE-UCB performing less exploration then ϵ-ROGUE.



 



 




 §.§ Healthcare-Adherence Improving Intervention for Increasing Physical Activity

Next, we consider an experiment using real world data from the mobile diabetes prevention program (mDPP) <cit.>. This was a randomized control trial (RCT) that was conducted to evaluate the efficacy of a 5 month mobile phone based weight loss program among overweight and obese adults at risk for developing type 2 diabetes and was adapted from the Diabetes Prevention Program (DPP) <cit.>. Sixty one overweight/obese adults were randomized into an active control group that only received an accelerometer (n=31) or a treatment group that received the mDPP mobile app plus the accelerometer and clinical office visits (n=30). Changes in primary and secondary outcomes for the trial were clinically and statistically significant. The treatment group lost an average of 6.2 ± 5.9 kg (-6.8% ± 5.7%) between baseline and the 5 month follow up while the control group gained 0.3 ± 3.0 kg (0.3% ± 5.7 %) (p < 0.001). The treatment group's steps per day increased by 2551 ± 4712 compared to the control group's decrease of 734 ± 3308 steps per day (p < 0.001). Additional details on demographics and other treatment parameters are available in <cit.>.

One key feature of the mDPP application was the ability for the clinicians to send daily messages to the participants to encourage that they adhere to the intervention and maintain a sufficiently increased activity level. Broadly speaking, there were 5 different message categories that the clinicians could choose to send to the patients. These categories are self-efficacy/confidence, motivation/belief/attitude, knowledge, behavior reinforcement, and social support. Each day the experimental group would receive a preprogrammed message from one of these categories, and all participants received the same messages each day. For our simulations, we used the data of what messages were sent to what participants, as well as their daily step counts.



  §.§.§ Patient Model

For our experiment, we used a behavioral analytics model of patient behavior first proposed by <cit.>. Here, each patient is assumed to be a utility maximizing agent who chooses how many steps to take each day based on previous behavior and the intervention implemented. We defined each of the different message categories be one of the actions of the bandit, which forms a ROGUE agent model as described in Section <ref>. Using the notation of Section <ref>, let c_t be a sequence of i.i.d. Laplace random variables with mean zero and shape parameter θ. This means σ^2(θ) = 2θ^2. After normalizing the step counts to be in [0,1] (where 1 is equal 14,000 steps), we can then write the reward distribution of a particular message type a as p(r_t|{x_a,t,θ_a}) = 1/2exp(-x_a,t/θ_a) δ(r_t) + 1/2exp(x_a,t-1/θ_a) δ(1-r_t) + 1/2θ_aexp(-|r_t-x_t|/θ_a)1[r_t ∈ (0,1)], where the state x_a,t∈ [0,1] and θ_a ∈ [ϵ,1] for a small ϵ >0. This results in a reward function g(x,θ) = x + θ/2(exp(-x/θ)- exp(x-1/θ)). Using Laplace noise has the advantage of allowing commercial mixed integer programming solvers to be used for offline parameter estimation by solving inverse optimization problems <cit.>. Using this MILP reformulation and behavioral models, we estimated the respective trajectory parameters for each message group and each patient of the treatment group for which we had data. These initial parameters were found using the Gurobi Solver in Python <cit.>.



  §.§.§ Simulation Results

This simulation was conducted using the mDPP data described above. Each experiment consisted of 1,000 action choices, which would correspond to about two years of a message based physical activity intervention, and 10 replicates of the simulation were conducted per patient and algorithm. The results in Figures <ref> and <ref> represent averages across all patients and replicates. Since we are using real data, the interpretation of the y-axis of each of the plots corresponds to number of steps in units of 1,000 steps, and the x-axis corresponds to the day of the intervention.

ROGUE-UCB and ϵ-ROGUE outperform all other algorithms both in terms of regret and average reward. In terms of regret, both ROGUE-UCB and ϵ-ROGUE obtain logarithmic-in-time regret; however, as before, ROGUE-UCB achieves lower cumulative regret than ϵ-ROGUE. While D-UCB is the only other algorithm that can outperform pure exploration, it only obtains linear regret. In terms of average reward, ROGUE-UCB, ϵ-ROGUE, and D-UCB are the only algorithms that outperform pure exploration. Interpreting these results in the healthcare context of this intervention, we find that the improved predictive model and use of MLE estimates within our specialized ROGUE Bandit algorithms results in an increase of 1,000 steps a day (approximately a half-mile more of walking per day) relative to the next best algorithm, which is a significant increase in activity. We note that in terms of average reward, both ROGUE-UCB and ϵ-ROGUE have similar performance; however, ROGUE-UCB has higher initial rewards due to fewer exploration steps. This property is of particular interest in this healthcare setting, as it insures that each participating individual receives the most appropriate recommendations at a faster rate.







§ CONCLUSION

In this paper, we defined a new class of non-stationary bandit models where the specific actions chosen influence the reward distributions of each action in subsequent time periods through a specific model. We conducted a finite sample analysis of the MLE estimates in this setting, and derived finite time concentration bounds. Using this analysis, we developed both the ROGUE-UCB  and ϵ-ROGUE algorithms that provide policies for these bandit models. Our theoretical results show that in expectation ROGUE-UCB and ϵ-ROGUE achieve logarithmic  in time regret. This is a substantial improvement over model-free algorithms, which can only achieve a square-root regret in the worst case scenario. We then showed through simulations using real and artificial data, that with minor modification, the ROGUE-UCB and ϵ-ROGUE algorithms significantly outperform state of the art bandit algorithms both in terms of cumulative regret and average reward. These results suggest that ROGUE bandits have strong potential for personalizing health care interventions, and in particular for healthcare-adherence improving interventions.


The authors gratefully acknowledge the support of NSF Award CMMI-1450963, UCSF Diabetes Family Fund for Innovative Patient Care-Education and Scientific Discovery Award, K23 Award (NR011454), and the UCSF Clinical and Translational Science Institute (CTSI) as part of the Clinical and Translational Science Award program funded by NIH UL1 TR000004.

informs2014 





Yonatan Mintz: Yonatan is a Postdoctoral Research Fellow at the H. Milton Stewart School of Industrial and Systems Engineering at the Georgia Institute of Technology, previously he completed his PhD at the department of Industrial Engineering and Operations research at the University of California, Berkeley. His research interests focus on the application of machine learning and optimization methodology for personalized healthcare and fair and accountable decision making.

Anil Aswani: Anil is an assistant professor in the Department of Industrial Engineering and Operations Research at the University of California, Berkeley. His research interests include data-driven decision making, with particular emphasis on addressing inefﬁciencies and inequities in health systems and physical infrastructure.

Philip Kaminsky Philip is the Earl J. Isaac Professor in the Science and Analysis of Decision Making in the Department of Industrial Engineering and Operations Research at UC Berkeley, where he previously served as Executive Associate Dean of the College of Engineering, faculty director of the Sutardja Center for Entrepreneurship and Technology, and department chair of Industrial Engineering and Operations Research.  His research focuses primarily on the analysis and development of robust and efficient tools and techniques for design, operation, and risk management in logistics systems and supply chains. He consults in the areas of production planning, logistics, and supply chain management., and prior to his graduate education, he worked in production engineering and control at Merck & Co.

Elena Flowers Elena is an Associate Professor in the Department of Physiological Nursing and Institute for Human Genetics at the University of California, San Francisco. Her program of research is focused on the relationships between risk factors, risk-reduction interventions, and molecular biomarkers for chronic diseases, namely type-2 diabetes and preterm birth, in high risk racial groups.

Yoshimi Fukuoka Yoshimi, PhD, RN, FAAN is a professor in the Department of Physiological Nursing at the University of California, San Francisco. Her research focuses on the primary prevention of cardiovascular disease and type 2 diabetes using digital technologies and artificial intelligence.














§ PROOFS OF PROPOSITIONS IN TEXT


Proof of Proposition <ref>: 
To obtain this formulation first we can augment the objective function of the log-likelihood problem by adding the constant term log∑_t∈𝒯_ap(r_a,t|θ^*_a,x^*_a,t) and multiplying by the positive constant 1/n(𝒯_a) which does not change the value of the optimal solution. Next we use functional compositions to contract the dynamics and obtain an objective function which is explicitly a function of θ_a,x_0,a. 

Proof of Lemma <ref>:  We can see that this is the case by noting that by Assumption <ref> we have that each of the log-likelihood ratios are Lipschitz with constant L_p. Since Lipschitz continuity is preserved by addition and averaging we note that the average of all of these log-likelihood ratios is also L_p-Lipschitz. Next we use the property that functional compositions of Lipschitz functions are Lipschitz with a constant equal to the product of their respective constants and the Lipschitz continuity is preserved through point wise maxima <cit.>. Since the absolute value function is 1-Lipschitz and we are performing maximization we have that ϕ is indeed L_p-Lipschitz with respect to the input sequence. 

Proof of Lemma <ref>:
To show the first result we use a similar argument to that of the proof of Lemma <ref> by showing that the likelihood is Lipschitz and then using the preservation of Lipschitz continuity across functional compositions. First consider h_a^t(x), since by Assumption <ref> h_a is locally L_h Lipschitz such that L_h ≤ 1, hence  

 we have that with respect to x,x' ∈𝒳 h_a^t(x) - h_a^t(x')_2 < x - x'_2.  Hence h_a^t(x) is locally 1-Lipschitz continuous with respect to x,t. Next, applying Assumption <ref> shows that since the likelihood ratio is L_f-Lipschitz with respect to its two inputs we simply have a composition of Lipschitz functions and the result follows. 

To show the second result note that ℓ depends on t only through the composite dynamics mapping h_a^t. By definition h^t(x) ∈𝒳 which is a bounded set, we have that for any t,t' ∈{1,...,T} h_a^t(x) - h_a^t'(x)_2 ≤(𝒳), thus using Assumption <ref> we obtain the desired result.

Proof of Lemma <ref>
To prove this result we first bound the expectation by a Rademacher average <cit.> and then apply Dudley's Integral bound <cit.>. First let us consider the explicit form of 𝔼φ({r_a,t}_t=1^n(𝒯_a)). Using an identically distributed sequence of rewards {r'_a,t}_t=1^n(𝒯_a) which is independent of the observed sequence we see that

    𝔼sup_θ_a,x_a,0∈Θ×𝒳|1/n(𝒯_a)∑_t∈𝒯_alog p(r_a,t|θ^*_a,h_a^t(x^*_a,0,θ^*_a,π_1^t))/p(r_a,t|θ_a,h_a^t(x_a,0,θ_a,π_1^t)) - 1/n(𝒯_a)D_a,π_1^T(θ^*_a,x^*_a,0||θ_a,x_a,0) |
       =𝔼sup_θ_a,x_a,0∈Θ×𝒳|1/n(𝒯_a)𝔼[∑_t∈𝒯_alog p(r_a,t|θ^*_a,h_a^t(x^*_a,0,θ^*_a,π_1^t))/p(r_a,t|θ_a,h_a^t(x_a,0,θ_a,π_1^t)) - ∑_t∈𝒯_alog p(r'_a,t|θ^*_a,h_a^t(x^*_a,0,θ^*_a,π_1^t))/p(r'_a,t|θ_a,h_a^t(x_a,0,θ_a,π_1^t))|{r_a,t}_t=1^n(𝒯_a)] |
       ≤𝔼sup_θ_a,x_a,0∈Θ×𝒳|1/n(𝒯_a)(∑_t∈𝒯_alog p(r_a,t|θ^*_a,h_a^t(x^*_a,0,θ^*_a,π_1^t))/p(r_a,t|θ_a,h_a^t(x_a,0,θ_a,π_1^t)) - ∑_t∈𝒯_alog p(r'_a,t|θ^*_a,h_a^t(x^*_a,0,θ^*_a,π_1^t))/p(r'_a,t|θ_a,h_a^t(x_a,0,θ_a,π_1^t))) |.

Here the inequality follows from Jensen's Inequality <cit.>. Let {ϵ_t}_t=1^n(𝒯_a) be a sequence of i.i.d. Rademacher random variables, which are independent of the observations r_a,t,r'_a,t, then through a symmetrization argument its clear that

    𝔼φ({r_a,t}_t=1^n(𝒯_a)) ≤ 2𝔼sup_θ_a,x_a,0∈Θ×𝒳|1/n(𝒯_a)∑_t∈𝒯_aϵ_tlog p(r_a,t|θ^*_a,h_a^t(x^*_a,0,θ^*_a,π_1^t))/p(r_a,t|θ_a,h_a^t(x_a,0,θ_a,π_1^t))|.

Since x^*_a,0,θ^*_a are constants we can use simplify the above expression using the notation introduced in Lemma <ref> to 2𝔼sup_θ_a,x_a ∈Θ×𝒳|1/n(𝒯_a)∑_t∈𝒯_aϵ_tℓ(θ_a,x_0,a,t)|.  We can bound this expression as follows

    2𝔼sup_θ_a,x_a ∈Θ×𝒳|1/n(𝒯_a)∑_t∈𝒯_aϵ_tℓ(θ_a,x_0,a,t)|, 
       = 2𝔼sup_θ_a,x_a ∈Θ×𝒳|1/n(𝒯_a)∑_t∈𝒯_aϵ_t(ℓ(θ_a,x_0,a,t)-ℓ(θ_a,x_0,a,0)+ℓ(θ_a,x_0,a,0))|, 
       ≤ 2𝔼sup_θ_a,x_a ∈Θ×𝒳|1/n(𝒯_a)∑_t∈𝒯_aϵ_t(ℓ(θ_a,x_0,a,t)-ℓ(θ_a,x_0,a,0))|+ 2𝔼sup_θ_a,x_a ∈Θ×𝒳|1/n(𝒯_a)∑_t∈𝒯_aϵ_tℓ(θ_a,x_0,a,0)|.


For our analysis we can consider each of these terms separately and bound them using Dudley's Integral Bound <cit.> and Lemmas <ref>,<ref>. Consider the first term, note that by Lemma <ref> we have that |ℓ(θ_a,x_0,a,t)-ℓ(θ_a,x_0,a,0)| ≤ L_f(𝒳) and is contained in an ℓ_2 ball of this radius, hence by Lemma <ref>

    2𝔼sup_θ_a,x_a ∈Θ×𝒳|1/n(𝒯_a)∑_t∈𝒯_aϵ_t(ℓ(θ_a,x_0,a,t)-ℓ(θ_a,x_0,a,0))|, 
    ≤ 8 ∫_0^L_f(𝒳)√(log𝒩(L_f(𝒳)B_2,α,_2)/n(𝒯_a))dα≤ 8L_f(𝒳)√(π/n(𝒯_a)).

The last inequality follows from using  a volume bound on the covering number and using integration by parts. Next consider the second term in (<ref>), we can bound this term using a direct application of Dudley's entropy integral as follows

    2𝔼sup_θ_a,x_a ∈Θ×𝒳|1/n(𝒯_a)∑_t∈𝒯_aϵ_tℓ(θ_a,x_0,a,0)| ≤ 16√(2)∫_0^∞√(log2𝒩(α,ℓ(Θ×𝒳),_2)/n(𝒯_a))dα, 
    ≤
     16√(2)∫_0^∞√(log2𝒩(α/L_f,Θ×𝒳,_2)/n(𝒯_a))dα.

Let v_ℓ B_2 be the ℓ_2 ball on ℝ^d_x+d_θ with radius v_ℓ = (𝒳×Θ), then

    (<ref>)≤ 16√(2)∫_0^∞√(log2𝒩(α/L_f,B_ℓ,_2)/n(𝒯_a))dα≤ 16√(2)∫_0^∞√(log2(3v_ℓ L_f/α)^d_x+d_θ/n(𝒯_a))dα

Solving the integral shows that (<ref>) ≤ 48√(2)(2)^1/d_x+d_θL_fv_ℓ√(π(d_x+d_θ)/n(𝒯_a)). Hence the result follows. 

Proof of Theorem <ref>: 
Lemma <ref> guarantees that the mapping φ is Lispschitz continuous with respect to the observed rewards with parameter L_p, furthermore we have by Assumption <ref> that the reward distributions are sub-Gaussian with parameter σ^2. By applying Theorem 1 from <cit.> we obtain for ξ >0:

    ℙ(φ({r_t}_t=1^n(𝒯_a)) - 𝔼φ({r_t}_t=1^n(𝒯_a)) > ξ) ≤exp(-ξ^2n(𝒯_a)/2L_p^2σ^2).


Hence, using the upper bound obtained from Lemma <ref>, we can substitute the result into the above equation giving the desired result. 

Proof of Theorem <ref>:  Using Theorem <ref> we know that with probability at least 1-exp(-ξ^2n(𝒯_a)/2L^2_pσ^2) we have:

    1/n(𝒯_a)D_a,π_1^T(θ^*_a,x^*_a,0||θ̂_a,x̂_a,0) - 1/n(𝒯_a)∑_t∈ n(𝒯_a)logp(r_a,t|θ_a^*,h_a^t(x^*_a,0,θ^*_a,π_1^t))/p(r_a,t|θ̂_a,h_a^t(x̂_a,0,θ̂_a,π_1^t))≤c_f(d_x,d_θ)/√(n(𝒯_a)) +ξ.

Also since θ̂_a,x̂_a are minimizers of the empirical trajectory divergence implies that

    1/n(𝒯_a)∑_t∈ n(𝒯_a)logp(r_a,t|θ_a^*,h_a^t(x^*_a,0,θ^*_a,π_1^t))/p(r_a,t|θ̂_a,h_a^t(x̂_a,0,θ̂_a,π_1^t))≤1/n(𝒯_a)∑_t∈ n(𝒯_a)logp(r_a,t|θ_a^*,h_a^t(x^*_a,0,θ^*_a,π_1^t))/p(r_a,t|θ^*_a,h_a^t(x^*_a,0,θ^*_a,π_1^t)) = 0.

Hence the desired result follows. 

Proof of Proposition <ref>:  Recall that by definition 𝔼R_Π(T) = ∑_t=1^Tg(θ_pi^*_t,x_pi^*_t) - g(θ_pi_t,x_pi_t). Since by Assumption <ref> we have that g is L_g-Lipschitz then we have ∀ t that g(θ_pi^*_t,x_pi^*_t) - g(θ_pi_t,x_pi_t) ≤ L_g(θ_pi^*_t,x_pi^*_t) - (θ_pi_t,x_pi_t)≤ L_g(𝒳×Θ)ℙ(π_t ≠π^*t). Hence  

    𝔼R_Π(T)    ≤ L_g (𝒳×Θ) ∑_t=0^T ℙ(π_t ≠π_t^*) = L_g (𝒳×Θ) ∑_t=0^T ∑_a∈𝒜ℙ(π_t = a, a ≠π_t^*) 
       = L_g (𝒳×Θ)  ∑_a∈𝒜∑_t=0^T ℙ(π_t = a, a ≠π_t^*) = L_g (𝒳×Θ) ∑_a∈𝒜𝔼T̃_a



Proof of Proposition <ref>:  We proceed to prove this proposition in a similar method to that presented in <cit.>. Suppose that at time t, the ROGUE-UCB policy chooses a ≠π^*_t. If the upper confidence bounds hold then we observe that g_a,t^UCB≥ g_π^*_t,t^UCB≥ g_π^*_t,t. Also define the mapping ψ_a(γ) = max{|g(θ,h_a^t(x_0)) - g(θ̂_a,h_a^t(x̂_a,0))|: 1/n(𝒯_a) D_a,π_1^T(θ,x_0||θ̂_a,x̂_a,0) ≤γ}. Then clearly g_a,t^UCB - g(θ̂_a,h_a^t(x̂_a,0)) ≤ψ_a(A(t)√(4log(t)/n(𝒯_a))) and g(θ̂_a,h_a^t(x̂_a,0)) - g_a,t≤ψ_a(A(t)√(4log(t)/n(𝒯_a))). Hence we have that g_a,t^UCB≤ 2ψ(A(t)√(4log(t)/n(𝒯_a))) + g_a,t. Therefore ψ(A(t)√(4log(t)/n(𝒯_a))) ≥1/2(g_π^*_t,t - g_a,t). By definition of ϵ_a we thus have that ψ(A(t)√(4log(t)/n(𝒯_a))) ≥ϵ_a/2. Therefore, by definition of δ_a we observe that A(t)√(4log t/n(𝒯_a))≥δ_a and hence n(𝒯_a) ≤4A(t)^2log t/δ_a^2.

Now, consider T̃_a:

    T̃_a = ∑_t=1^T 1{π_t = a, a ≠π^*_t}
        = ∑_t=1^T1{π_t = a, a ≠π^*_t, n(𝒯_a) ≤4A(t)^2log t/δ_a^2} + ∑_t=1^T1{π_t = a, a ≠π^*_t, n(𝒯_a) > 4A(t)^2log t/δ_a^2}
       ≤∑_t=1^T1{π_t = a, a ≠π^*_t, n(𝒯_a) ≤4A(|𝒜|)^2log T/δ_a^2} +∑_t=1^T1{π_t = a, a ≠π^*_t, n(𝒯_a) > 4A(t)^2log t/δ_a^2}
       ≤4log(T)/δ_a^2 A(|𝒜|)^2 + ∑_t=1^T1{π_t = a, a ≠π^*_t, n(𝒯_a) > 4A(t)^2log t/δ_a^2}

Observe that if we play sub optimal action a at time t this means we either severely over estimate the value of g_a,t, severely under estimate the value of g_π_t^*,t, or the two values are very close to each other. Hence
 
    {π_t=a, a≠π^*_t, n(𝒯_a)  > 4A(t)^2log t/δ_a^2}⊆{g_a,t^UCB - g_a,t > 2 ψ_a(A(t)√(4log(t)/n(𝒯_a))), n(𝒯_a) >4A(t)^2log t/δ_a^2}_(a)
    ∪{g_π^*_t,t >g^π_t^*,t_UCB, n(𝒯_a) >4A(t)^2log t/δ_a^2}_(b)∪{g_π^*_t,t - g_a,t≤ 2ψ_a(A(t)√(4log(t)/n(𝒯_a))), n(𝒯_a) >4A(t)^2log t/δ_a^2}_(c).
 
 However, as we established in the beginning of the proof the event (c) = ∅. Also note that for events (a),(b) to occur this would imply that θ_a,x_a,0 and θ_π_t^*,x_π_t^*,0 are not feasible points of their respective UCB deriving problems, hence
 
    {π_t=a, a≠π^*_t, n(𝒯_a)  > 4A(t)^2log t/δ_a^2}⊆{∃ s<t : 1/sD_π^*_t,π_1^s(θ̂_π^*_t,x̂_π^*_t,0||θ_π^*_t,x_π^*_t,0) > A(t)√(4log(t)/s)}
       ∪{∃ s'<t:  1/s'D_a,π_1^s'(θ̂_a,x̂_a,0||θ_a,x_a,0) > A(t)√(4log(t)/s')}
       ⊆⋃_1≤ s < t{1/sD_π^*_t,π_1^s(θ̂_π^*_t,x̂_π^*_t,0||θ_π^*_t,x_π^*_t,0) > A(t)√(4log(t)/s)}⋃_1≤ s' < t{1/s'D_a,π_1^s'(θ̂_a,x̂_a,0||θ_a,x_a,0) > A(t)√(4log(t)/s')}.
 
 Taking the expected value of T̃_a we obtain
 
    𝔼T̃_a ≤4log(T)/δ_a^2 A(|𝒜|)^2 + 𝔼∑_t=1^T1{π_t = a, a ≠π^*_t, n(𝒯_a) > 4A(t)^2log t/δ_a^2}
       ≤4log(T)/δ_a^2 A(|𝒜|)^2 + ∑_t=1^T∑_s=1^t∑_s'=1^tℙ(1/sD_π^*_t,π_1^s(θ̂_π^*_t,x̂_π^*_t,0||θ_π^*_t,x_π^*_t,0) > A(t)√(4log(t)/s))
       + ∑_t=1^T∑_s=1^t∑_s'=1^tℙ(1/s'D_a,π_1^s'(θ̂_a,x̂_a,0||θ_a,x_a,0) > A(t)√(4log(t)/s'))  
       ≤4log(T)/δ_a^2 A(|𝒜|)^2 +  2∑_t=1^T∑_s=1^t∑_s'=1^t t^-4≤4log(T)/δ_a^2 A(|𝒜|)^2 + π^2/3.

 Here the third inequality is derived by Theorem <ref> and the final inequality by utilizing the solution to the Basel Problem <cit.>. Hence we obtain the desired result. 

Proof of Theorem <ref>: 
Using Proposition <ref> we bound the expected regret as 𝔼R_Π(T) ≤ L_g(𝒳×Θ)∑_a∈𝒜𝔼T̃_a. Then applying the result of Proposition <ref> we obtain the desired result. 

Proof of Corollary <ref>: 
To obtain the desired rate we must first express the bound from Theorem <ref> in terms of ϵ. We can do this by noting that from Assumption <ref> we know that the reward distributions are sub-Gaussian with parameter σ, therefore using the property that exponential families achieve the maximum entropy given moment constraints <cit.>, we observe that ∀θ'_a,x'_a,0∈Θ×𝒳: 

	
    1/n(𝒯_a)D_a,π_1^T(θ_a,x_a,0||θ'_a,x'_a,0) ≥1/2σ n(𝒯_a)∑_t ∈𝒯(g(θ_a,x_a,t)- g(θ'_a,x'_a,t))^2 ≥1/2σϵ_a^2


Thus applying the definition of δ_a we observe that in fact δ_a ≥1/2σϵ_a^2. Hence substituting into the bound from Theorem <ref> we obtain the following weaker regret bound in terms of the ϵ_a: 

	
    𝔼R_Π(T) ≤ L_g(𝒳×Θ)∑_a∈𝒜(A(|𝒜|)^2 16σ^2log T/ϵ_a^4 + π^2/3).


Note that this bound is convex and monotonically decreasing in the ϵ_a, and in fact is minimized if ϵ_a = max_(θ_1,x_1),(θ_2,x_2) ∈Θ×𝒳 |g(θ_1,x_1) - g(θ_2,x_2)| for all a ∈𝒜. Hence all ϵ_a will be equal to each other when this bound is minimized. However, this bound will go to infinity as the ϵ_a become small. Note though that since by assumption, ϵ_a ≥ϵ and hence as ϵ_a become small we would expect our regret to be at a rate of ϵ T. Using these two notions we can thus conclude that our regret can be bounded as:

	
    𝔼R_Π(T) ≤min{ L_g(𝒳×Θ)|𝒜| (A(|𝒜|)^2 16σ^2log T/ϵ^4 + π^2/3),ϵ T}


Since one of these expressions increases in ϵ and the other decreases in ϵ we can minimize the right hand side by setting both parts of the min to be equal to each other. This shows that the minimizing epsilon can be given as a zero to the following quintic polynomial:

	
    Tϵ^5 - L_g(𝒳×Θ)|𝒜|π^2/3ϵ^4 - L_g(𝒳×Θ)|𝒜|A(|𝒜|)^216σ^2log T


Since the zeros of this polynomial are difficult to compute we can use the Fujiwara bound on polynomial zeros <cit.> to show that for sufficiently large T, ϵ = 𝒪(( |𝒜|A(|𝒜|)^2σ^2log T/T)^1/5), and hence the desired result follows from substituting this value into Equation (<ref>). 



Proof of Theorem <ref>: 
We proceed to prove this theorem using similar analysis to that provided in <cit.>. The probability that an arm a is played sub-optimally by the ϵ-ROGUE algorithm is given by:

    ℙ(π_t=a,a≠π^*_t) = ϵ_t/|𝒜| + (1-ϵ_t)ℙ(g(x̂_a,t,θ̂_a) ≥ g(x̂_π_t^*,t,θ̂_π_t^*))

Where the first term coms from the probability of performing an exploration step and the second term corresponds to an exploration step. First lets consider the exploitation term, define Δ_a,t = g(x_π_t^*,t,θ_π^*_t) - g(x_a,t,θ_a), using this value we can upper bound the exploitation term as follows:


    ℙ(g(x̂_a,t,θ̂_a) ≥ g(x̂^*_a,t,θ̂^*_a))  
       ≤ℙ( (g(x̂_a,t,θ̂_a) - g(x_a,t,θ_a)) - (g(x̂_π*_t,t,θ̂_π^*_t) - g(x_π^*_t,t,θ_π^*_t)) ≥Δ_a,t) 
       ≤ℙ(g(x̂_a,t,θ̂_a) - g(x_a,t,θ_a) ≥Δ_a,t/2) + ℙ( g(x̂_π*_t,t,θ̂_π^*_t) - g(x_π^*_t,t,θ_π^*_t) ≤-Δ_a,t/2)


Using the definitions of ϵ_a,δ_a from Theorem <ref> we obtain the following:

    ≤ℙ(g(x̂_a,t,θ̂_a) - g(x_a,t,θ_a) ≥ϵ_a/2) + ℙ( g(x̂_π*_t,t,θ̂_π^*_t) - g(x_π^*_t,t,θ_π^*_t) ≤-ϵ_a/2) 
       ≤ℙ(D̅_a,π_1^t(θ_a,x_a,0||θ̂_a,x̂_a,0) ≥δ_a ) + ℙ( D̅_π^*_t,π_1^t(θ_π^*_t,x_π^*_t,0||θ̂_π^*_t,x̂_π^*_t,0) ≥δ_a )


Both of these terms can be bounded in a similar manner, as such we will present the arguments for bounding the first term and note that a similar procedure can be used to bound the second. We begin as follows:

    ℙ(D̅_a,π_1^t(θ_a,x_a,0||θ̂_a,x̂_a,0) ≥δ_a ) ≤∑_n=1^t ℙ(n(𝒯_a)=n, D̅_a,π_1^n(θ_a,x_a,0||θ̂_a,x̂_a,0) ≥δ_a ) 
       ∑_n=1^t ℙ(n(𝒯_a)=n| D̅_a,π_1^n(θ_a,x_a,0||θ̂_a,x̂_a,0) ≥δ_a )ℙ(D̅_a,π_1^n(θ_a,x_a,0||θ̂_a,x̂_a,0) ≥δ_a)


Applying Theorem <ref> we obtain:

    ∑_n=1^t ℙ(n(𝒯_a)=n| D̅_a,π_1^n(θ_a,x_a,0||θ̂_a,x̂_a,0) ≥δ_a )exp(-(δ_a√(n)-c_f(d_x,d_θ))^2/2L_p^2σ^2) 
       ≤∑_n=1^⌊ w ⌋ℙ(n(𝒯_a)=n| D̅_a,π_1^n(θ_a,x_a,0||θ̂_a,x̂_a,0) ≥δ_a ) + ∑_n= ⌈ w ⌉^∞exp(-(δ_a√(n)-c_f(d_x,d_θ))^2/2L_p^2σ^2)


Where we define w = 1/2|𝒜|∑_n=1^t ϵ_t. We can bound the first term in the expression above by using the the total number of times arm a is chosen as part of an exploration step, we call this quantity n^R(𝒯_a). This can be done as follows:

    ∑_n=1^⌊ w ⌋ℙ(n(𝒯_a)=n| D̅_a,π_1^n(θ_a,x_a,0||θ̂_a,x̂_a,0) ≥δ_a ) 
       ≤∑_n=1^⌊ w ⌋ℙ(n^R(𝒯_a)≤ n |D̅_a,π_1^n(θ_a,x_a,0||θ̂_a,x̂_a,0) ≥δ_a) 
       ≤ wℙ(n^R(𝒯_a)≤ w)


The last two inequality follows since the amount of exploration steps is independent of how the parameter estimates are concentrating. Note that w = 1/2𝔼n^R(𝒯_a), and that (n^R(𝒯_a)) ≤𝔼n^R(𝒯_a). Hence we can employ the Bernstein bound <cit.> to obtain the following upper bound on the above expression:

    wℙ(n^R(𝒯_a)≤ w) ≤ w exp(-3w/14)


 We will bound the second term in the summation using an integral bound. To do this, first note that since -(δ_a√(n)-c_f(d_x,d_θ))^2 is concave in n, so we can upper bound it using an appropriate first order approximation. Namely, consider the first order Taylor expansion about n = (2c_f(d_θ,d_x)/δ_a)^2, then:

    -(δ_a√(n) - c_f(d_x,d_θ))^2 ≤-δ_a^2/2n + c_f(d_x,d_θ)^2 
       exp(-(δ_a√(n) - c_f(d_x,d_θ))^2/2L_p^2σ^2) ≤exp(-δ_a^2/2n + c_f(d_x,d_θ)^2/2L_p^2σ^2)
 
Then using this bound we can upper bound the second summation term as follows:

    ∑_n= ⌈ w ⌉^∞exp(-(δ_a√(n)-c_f(d_x,d_θ))^2/2L_p^2σ^2) ≤∑_n= ⌈ w ⌉^∞exp(-δ_a^2/2n + c_f(d_x,d_θ)^2/2L_p^2σ^2) 
       ≤4L_p^2σ^2/δ_a^2exp(-δ_a^2/2⌊ w ⌋ + c_f(d_x,d_θ)^2/2L_p^2σ^2)


Combining all of these equations together we obtain that:

    ℙ(π_t=a,a≠π^*_t) ≤ϵ_t/|𝒜| + 2w exp(-3w/14) + 8L_p^2σ^2/δ_a^2exp(-δ_a^2/2⌊ w ⌋ + c_f(d_x,d_θ)^2/2L_p^2σ^2)


All that remains to complete the proof is to provide a lower bound on w. Let t': = c|𝒜|/δ_min^2 then:

    w = 1/2|𝒜|∑_n=1^t ϵ_n = 1/2|𝒜|∑_n=1^t'ϵ_n + 1/2|𝒜|∑_n=t'^t ϵ_n 
        = c/2δ_min^2 + c/2δ_min^2∑_n=t'^t1/n
       ≥c/2δ_min^2 + c/2δ_min^2logtδ_min^2/c|𝒜| = c/2δ_min^2logetδ_min^2/c|𝒜|


Substituting thins bound into (<ref>) and expanding ϵ_t gives the desired result. 






§ TECHNICAL METRIC ENTROPY LEMMA

 
Let a ∈ A ⊆ℝ^n such that A is bounded and K = max_a∈ Ad(a,0)/n with respect to some metric d and ∀ a ∈ A, a_2 ≤ d(a,0) . Then for i.i.d Rademacher process {ϵ_i}_i=1^n :

    𝔼sup_a∈ A | 1/n∑_i=1^nϵ_i a_i | ≤ 4 ∫_0^K√(log2𝒩(α,A,d)/n) dα


Proof: We proceed to prove this result in a similar technique to that used by <cit.>. Let  A̅ = A ∪ A^- and {Â_i}_i=0^N be a sequence of successively finer covers of set A̅, such that Â_i is an α_i cover of set A̅ with respect to metric d and α_i = 2^-iK. Next, define a sequence of  approximating vectors of a and denote these by â_i such that for any two successive approximations â_i ∈Â_i and â_i-1∈Â_i-1 we have that d(â_i,â_i-1) ≤α_i. Then observe we can rewrite a as follows:

    a = a + â_N - â_N = â_0 + ∑_i=1^N(â_i - â_i-1) + a - â_n

Observe that we can set â_0 to the 0 vector since clearly a metric ball of radius K will form a K cover of set A. Hence we obtain:

    𝔼sup_a∈ A | 1/n∑_i=1^nϵ_i a_i |= 𝔼sup_a∈ A | 1/n⟨ϵ, a ⟩ | = 𝔼sup_a ∈A̅1/n⟨ϵ, a ⟩ = 𝔼sup_a∈A̅1/n⟨ϵ, ∑_j=1^N(â_i - â_i-1) + a - â_N ⟩
       ≤𝔼∑_j=1^Nsup_â_j ∈Â_j, â_j-1∈Â_j-1⟨ϵ, â_j - â_j-1⟩ + 𝔼sup_a∈A̅⟨ϵ, a - â_N ⟩
       ≤∑_j=1^N α_i √(2 log |Â_j||Â_j-1|/n) + α_N

Here the final inequality is obtained by applying the finite class lemma <cit.>. Observe that |Â_j-1| ≤ |Â_j-1| = 𝒩(α_i,A̅,d) and that by construction α_j = 2(α_j - α_j+1). Hence:

    𝔼sup_a∈ A | 1/n∑_i=1^nϵ_i a_i | ≤∑_j=1^N 4(α_j - α_j+1) √(log𝒩(α_i,A̅,d)/n) + α_N 
       ≤ 4 ∫_α_N+1^α_0√(log𝒩(α,A̅,d)/n) dα + α_N → 4 ∫_0^K √(log𝒩(α,A̅,d)/n) dα

Note that 𝒩(α,A̅,d) ≤ 2𝒩(α,A,d) thus completing the proof. 




