Year: 2021

Abstract:
For traffic routing platforms, the choice of which route to recommend to a user depends on the congestion on these routes – indeed, an individual’s utility depends on the number of people using the recommended route at that instance. Motivated by this, we introduce the problem of Congested Bandits where each arm’s reward is allowed to depend on the number of times it was played in the past ∆ timesteps. This dependence on past history of actions leads to a dynamical system where an algorithm’s present choices also affect its future pay-offs, and requires an algorithm to plan for this. We study the congestion aware formulation in the multi-armed bandit (MAB) setup and in the contextual bandit setup with linear rewards. For the multi-armed setup, we propose a UCB style algorithm and show that its policy regret scales as Õ( √ K∆T ). For the linear contextual bandit setup, our algorithm, based on an iterative least squares planner, achieves policy regret Õ( √ dT + ∆). From an experimental standpoint, we corroborate the no-regret properties of our algorithms via a simulation study.

text: For traffic routing platforms, the choice of which route to recommend to a user depends on the congestion on these routes – indeed, an individual’s utility depends on the number of people using the recommended route at that instance. Motivated by this, we introduce the problem of Congested Bandits where each arm’s reward is allowed to depend on the number of times it was played in the past ∆ timesteps. This dependence on past history of actions leads to a dynamical system where an algorithm’s present choices also affect its future pay-offs, and requires an algorithm to plan for this. We study the congestion aware formulation in the multi-armed bandit (MAB) setup and in the contextual bandit setup with linear rewards. For the multi-armed setup, we propose a UCB style algorithm and show that its policy regret scales as Õ( √ K∆T ). For the linear contextual bandit setup, our algorithm, based on an iterative least squares planner, achieves policy regret Õ( √ dT + ∆). From an experimental standpoint, we corroborate the no-regret properties of our algorithms via a simulation study.

heading: 1 INTRODUCTION
text: The online multi-armed bandit (MAB) problem and its extensions have been widely studied and used to model many real world scenarios (Robbins, 1952; Auer et al., 2002; 2001). In the basic MAB setup there are K arms with either stochastic or adversarially chosen reward profiles. The goal is to design an algorithm that achieves a cumulative reward that is as good as that of the best arm in hindsight. This is quantified in terms of the regret achieved by the algorithm over T time steps (see Section 2 for formal definitions). In many real world scenarios the MAB setup as described above is not suitable as the reward obtained by playing an arm/action at a given time step may depend on the algorithm’s choices in the previous time steps. In particular, we are motivated by online routing problems where the reward of suggesting a particular edge to traverse along a path from source to destination often depends on the congestion on that edge. This congestion is a function of the number of times the particular edge has been recommended earlier (potentially in a time window). In such scenarios, one would desire algorithms that can compete with the best policy, i.e., the best sequence of actions, in hindsight as compared to a fixed best action.
Classical multi-armed bandit formulation and associated no-regret algorithms (Slivkins, 2019), or their extensions to routing problems (Kalai & Vempala, 2005; Awerbuch & Kleinberg, 2008) do not suffice for the above scenario as they only guarantee competitiveness with respect to the best fixed arm in hindsight. To overcome these limitations, we propose a new model, viz., congested bandits which captures the above scenario. In our proposed model the reward of a given arm at each time step depends on how many times the arm has been played within a given time window of size ∆. Hence over time, an arm’s expected reward may decay and reset dynamically. While our model is motivated by online routing problems, our proposed formulation is very general. As another example, consider a digital music platform that recommends artists to its end users. In order to maximize profit the recommendation algorithm may prefer to recommend popular artists, and at the same time the platform may want to promote equity and diversity by highlighting new and emerging artists as well. This scenario can be model via congested bandits where each artist is an arm and the reward for suggesting an artist is a function of how many times the artist has been recommended in the past time window of length ∆. In both the scenarios above, the ability to reset the congestion cost (by simply not playing an arm for ∆ time steps) is a crucial part of the problem formulation.
Our contributions. We propose and study the congested bandits model with short term resets under a variety of settings and design no-regret algorithms. In the most basic setup we consider aK-armed stochastic bandit problem where each arm a has a mean reward µa, and the mean reward obtained by playing arm a at time t equals fcong(a, ht)µa. Here ht denotes the history of the algorithm’s choices within the last ∆ time steps and fcong is a non-increasing congestion function. Recall that the algorithm’s goal in this setup is to compete with the best policy in hindsight. While the above setting can be formulated as a Markov Decision Process (MDP), existing no regret algorithms for MDPs will incur a regret bound that scales exponential in the parameters (scaling as K∆) (Auer et al., 2009; Jaksch et al., 2010). Instead, we carefully exploit the problem structure to design an algorithm with near-optimal regret scaling as Õ( √ K∆T ). Next, we extend our model to the case of online routing with congested edge rewards, again presenting near optimal no-regret algorithms that avoid exponential dependence on the size of the graph in the regret bounds.
We then extend the multi-armed and the congested online routing formulations to a contextual setting where the mean reward for each arm/edge at a given time step equals fcong(a, ht)〈θ∗, φ(xt, a))〉, where xt ∈ Rd is a context vector and θ∗ is an unknown parameter. This extension is inspired from classical work in contextual bandits (Li et al., 2010; Chu et al., 2011) and captures scenarios where users may have different preferences over actions/arms (e.g., a user who wants to avoid routes with tolls). Solving the contextual case poses significant hurdles as a priori it is not even clear whether the setting can be captured via an MDP. By exploiting the structure of the problem, we present a novel epoch based algorithm that, at each time step, plays a near optimal policy by planning for the next epoch. Showing that such planning can be done when only given access to the distribution of the contexts is a key technical step in establishing the correctness of the algorithm. As a result, we obtain algorithms that achieve Õ( √ dT + ∆) regret in the contextual MAB setting. Finally, using simulations, we perform an empirical evaluation of the effectiveness of our proposed algorithms.
Related work. Closest to our work are studies on multi-armed bandits with decaying and/or improving costs. The work of (Levine et al., 2017) proposes the rotting bandits model that has been further studied in (Seznec et al., 2019). In this model the mean reward of each arm decays in a monotonic way as a function of the number of times the arm has been played in the past. There is no notion of a short-term reset as in our setting. As a result it can be shown that a simply greedy policy is optimal in hindsight. In contrast, in our setting greedy approaches can fail miserably as highlighted in Figure 1. The work of Heidari et al. (2016) considers a setting where the mean reward of an arm can either improve or decay as a function of the number of times it has been played. However, similar to the rotting bandits setup there is no notion of a reset. Pike-Burke & Grünewälder (2019) considers a notion of reset/improvement by allowing the mean reward to depend on the number of time steps since an arm was last played. Their work considers a Bayesian setup where the mean reward function is modelled by a draw from a Gaussian process. On the other hand, in our work, the reward is a function of the number of times an arm was played in the past ∆ time steps. However their regret bounds are either with respect to the instantaneous regret, or with respect to a weaker policy class of d-step look ahead policies. The notion of instantaneous regret only compares with the class of greedy policies at each timestep as compared to the globally optimal policy.
There also exist works studying the design of online learning algorithms againstm-bounded memory adversaries. The assumption here is that the reward of an action at each time step depends only on the previous m actions. While this is also true for our setting, in general the regret bounds provided for bounded-memory adversaries are either with respect to a fixed action or a policy class containing policies that do no switch often (Arora et al., 2012; Anava et al., 2015). Our problem formulation for the contextual setup is reminiscent of the recent line of works on contextual MDPs (Azizzadenesheli et al., 2016; Krishnamurthy et al., 2016; Hallak et al., 2015; Modi & Tewari, 2020). However these works either assume that the context vector is fixed for a given episode (allowing for easier planning), or make strong realizability assumptions on the optimal Q-function. Finally, our congested bandits formulation of the routing problem is a natural extension of classical work on the online shortest path problem Kalai & Vempala (2005); Awerbuch & Kleinberg (2008); Dani et al. (2007).

heading: 2 CONGESTED MULTI-ARMED BANDIT
text: In this section, we model the congestion problem in a multi-armed bandit (MAB) framework.Our setup for congested multi-armed bandits models the congestion phenomenon by allowing the rewards of an arm to depend on the number of times it was played in the past.
Let us consider a MAB setup with K arms, where each arm may represent a possible route. Let us denote by ∆ the size of the window which affects the reward at the current time step. For any time t, let ht ∈ H∆ : = [K]∆ denote the history of the actions taken by an algorithm1 in the past ∆ time steps, that is, ht = [at−∆, . . . , at−1] where aτ is the action chosen by the algorithm at time τ . In order to model congestion arising from repeated plays of a single arm, we consider a function fcong : [K] × [∆]+ → (0, 1]. This congestion function takes in two arguments: an arm a and the number of times this arm was played in the past ∆ time steps, and outputs a value indicating the decay in the reward of arm a arising from congestion.
Protocol for congestion in bandits. We consider the following online learning protocol for a learner in our congested MAB framework: At each round t, the learner picks an arm at ∈ [K] and observes reward
r̃(ht, at) = fcong(at,#(ht, at)) · µat + t where t ∼ N (0, 1)).
Finally, the history changes to ht+1 = [ht,2:∆, at] where we have used the notation ht,i:j to denote the vector [ht(i), . . . , ht(j)] and #(h, a) to denote the number of times the action a was played in history h.
Each arm a is associated with a mean reward vector µa and the congestion function multiplicatively decreases the reward of that arm. We assume that the learner does not know the exact form of the function fcong as well as the the mean vector µ = {µa}[K]. The objective of the learner is to select the actions at which minimizes a notion of policy regret, which we define next.
Policy regret for congested MAB. In the standard MAB setup, regret compares the cumulative reward of the algorithm to the benchmark of playing the arm with the highest mean reward at all time steps. However, as described in Section 1, this benchmark is not suitable for our setup. Indeed, the asymptotically optimal algorithm is one which maximizes the average cumulative reward ρ∗ : = maxalg limT→∞ 1 T ∑T t=1 r(ht, at), where the action at is the one chosen by the algorithm alg and history ht is the sequence of actions in the past ∆ time steps.
This asymptotically algorithm corresponds to a stationary policy π∗ whose selection at only depends on the history ht. Accordingly, we consider the following class of stationary policies as the comparator for our regret Π = {π : H∆ → [K]} , with size |Π| = KK ∆
. Denote by hπt the history at time t by running policy π up to time t, we define the policy regret for any algorithm
RT (alg; Π, fcong) : = sup π∈Π T∑ t=1 r(hπt , π(h π t ))− T∑ t=1 r̃(halgt , at) , (1)
1We usually suppress the dependence of this history on the algorithm, but make it explicit whenever it is not clear from context.
Algorithm 1: CARMAB: Congestion Aware Routing via Multi-Armed Bandits Input: Congestion window ∆, confidence parameter δ ∈ (0, 1), action set [K], time horizon T . Initialize: Set t = 1 for episodes e = 1, . . . , E do
Initialize episode Set start time of episode te = t. For all actions a and historical count j, set ne(a, j) = 0 and Ne(a, j) = ∑ s<e ns(a, j). Set empirical reward estimate for each arm and historical count
r̂e(a, j) =
∑te−1 τ=1 rτ · I[aτ = a, jτ = j]
max{1, Ne(a, j)} .
Compute optimistic policy Set the feasible rewards
Re = { r ∈ [0, 1]A×(∆+1) | for all (a, j), |r(a, j)− r̂e(a, j)| ≤ 10 √ log(A∆te/δ)
max{1, Ne(a, j)} } Find optimistic policy π̃e = arg maxπ∈Π,r∈Re ρ(π, r) Execute optimistic policy while ne(a, j) < max{1, Ne(a, j)} do
Select arm at = π̃e(st), obtain reward r̂t. Update ne(a,#(st, a)) = ne(a,#(st, a)) + 1.
where at is the action chosen by alg at time t and r(ht, at) = fcong(ht, ) · µat . This notion of regret is called policy regret (Arora et al., 2012) because the history sequence observed by the algorithm π∗ and the algorithm alg can be different from each other – this leads to a situation where choosing the same action a at time t can lead to different rewards for the algorithm and the comparator.

heading: 2.1 CARMAB: CONGESTED MAB ALGORITHM
text: We now describe our learning algorithm for the congested MAB problem. At a high level, CARMAB, detailed in Algorithm 1, is based on a reduction of this problem to a reinforcement learning problem with state space S = H∆ and action space A = [K], where the underlying dynamics are known to the learner. With this reduction, CARMAB deploys an epoch-based strategy which plays a optimistic policy π̃e computed from optimistic estimates of the reward function.
Reduction to MDP. Our congested MAB setup can be viewed as a learning problem in a Markov decision process (MDP) with finite state and action spaces. This MDPMmab comprises state space S = H∆ and action space A = [K]. The reward function for this MDP is given by r(s, a) = fcong(a,#(s, a)) · µa and the deterministic state transitions are given P (s′|s, a) = I[s′ = [s2:∆, a]].
Algorithm details. Our learning algorithm in this MDP is an upper confidence bound (UCB) style algorithm, adapted from the classical UCRL2 (Jaksch et al., 2010) for learning in finite MDPs. It splits the time horizon T into a total of E epochs, each of which can be of varying length. In each episode, for every pair (a, j) of action a and historical count j ∈ [∆]+, the algorithm computes the empirical estimate of the rewards r̂e(a, j) from observations in the past epoch and maintains a feasible set Re of rewards. This set is constructed such that with high probability, the true reward r belong to this set for each epoch. Given this set, our algorithm computes the optimistic policy
π̃e = arg max π∈Π,r∈Re ρπ(r) where ρπ : = lim T→∞
1
T T∑ t=1 r(hπt , π(h π t )) , (2)
that is, the policy which achieves the best average expected reward with respect to the optimistic set Re. The optimistic policy πe is then deployed in the congested MAB setup till one of the (a, j) pair doubles in the number of times it is played and this determines the size of any epoch.
Computing optimistic policy. In the MDP described above, each deterministic policy π follows a cyclical path since the transition dynamics are deterministic and the state space is finite. With
this insight, this problem of finding the optimal policy with highest average reward is equivalent to finding the maximum mean cycle in a weighted directed graph. In our simulations, we use Karp’s algorithm (Karp, 1978) for finding these optimistic policy. This algorithm runs in time O(K∆+1).

heading: 2.2 REGRET ANALYSIS FOR CARMAB
text: In this section, we obtain a bound on the policy regret of the proposed algorithm CARMAB. Our overall proof strategy is to first establish that the MDP Mmab has a low diameter (the time taken to move from one state to another in the MDP), then bounding the regret in each episode e of the process and finally establishing that the total number of episodes E can be at most logarithmic in the time horizon T . Combining these elements, we establish in the following theorem that the regret of CARMAB scales as Õ( √ K∆T ) with high probability.2
Theorem 1 (Regret bound for CARMAB). For any confidence δ ∈ (0, 1), congestion window ∆ > 0 and time horizon T > ∆K, the policy regret (1), of CARMAB is
RT (CARMAB; Π, fcong) ≤ c ·∆2K log ( T
∆K
) + c √ K∆T log ( ∆KT
δ
) + c √ T log ( 1
δ ) with probability at least 1− δ.
A few comments on the theorem are in order. Observe that the dominating term in the above regret bound scales as Õ( √ K∆T ) in contrast to the classical regret bounds for MAB which have a Õ( √ KT ) dependence. This additional factor of √ ∆ comes from the fact the stronger notion of policy regret as well as the non-stationary nature of the arm rewards. Additionally, a naı̈ve application of the UCRL2 regret bound to the constructed MDP scales linearly with state space and would correspond to an additional factor of O(K∆). The CARMAB algorithm is able to avoid this exponential dependence by exploiting the underlying structure in the congested MAB problem. Our regret bound are also minimax optimal – observe that for any constant value of ∆, the lower bounds from the classical MAB setup immediately imply that the regret of any learner should scale as Ω( √ KT ), which matches the upper bound in Theorem 1.
We defer the complete proof of this to Appendix A but provide a high-level sketch of the important arguments.
MDP Mmab has bounded diameter. The diameter D of an MDP M measures the number of steps it takes to reach a state s′ from a state s using an appropriately chosen policy. The diameter is a measure of the connectedness of the underlying MDP and is commonly studied in the literature on reinforcement learning (Puterman, 2014).
Definition 1 (Diameter of MDP.). Consider the stochastic process induced by the policy π on an MDPM. Let τ(s′|s,M, π) represent the first time the policy reaches state s′ starting from s. The diameter D of the MDP is D : = maxs6=s′ minπ E[τ(s′|s,M, π)].
Recall from Section 2.1 that the MDPMmab has deterministic dynamics and state space given by the set of historiesH∆. Proposition 2 in Appendix A establishes that the diameter of this MDP is at most the window size ∆. With this bound on the diameter, we then show in Lemma 4 that the total regret of the algorithm can be decomposed into a sum of regret terms, one for each episode.
RT ≤ sup π∈Π E∑ e=1 re + c
√ T log ( T
δ
) with re : = ∑ a,j ne(a, j)(ρπ − fcong(a, j)µa) , (3)
which holds with probability at least 1 − δ. We have used ne(a, j) to denote the number of times action a was played by the algorithm when it had a count j in the history and ρπ the average reward of policy π. Our analysis then proceeds to bound the per-episode regret re.
2For clarity purposes, through out the paper we denote by c an absolute constant whose value is independent of any problem parameter. We allow this value of c to change from line to line.
Regret for episode e. In episode e, the set of feasible rewards Re is chosen to ensure that with high probability, the true reward r∗(a, j) = fcong(a, j) · µj belongs to this set. Conditioning on this event, we show that the regret in each episode is upper bounded by the window size ∆ and a scaled ratio of the number of times each action-history (a, j) is played, that is,
re ≤ ∆ + c √ log ( ∆Kte δ )∑ a,j ne(a, j)√ max(1, Ne(a, j)) . (4)
where te is the time at which episode e starts and Ne(a, j) = ∑ i<e ni(a, j). Theorem 1 follows
from combining the above with a bound on the total number of episodes E ≤ c ·∆K log ( T
∆K
) .

heading: 2.3 ROUTING WITH CONGESTED BANDITS
text: We now study an extension of the congested MAB setup where the arms correspond to edges on graph G = (V,E) with a pre-defined start state sG and goal state tG. In this setup, at each round t the learner selects an sG-tG path pt on the graph G and receives reward r̃(ht, ei,t) = fcong(ei,t,#(ht, ei,t)) ·µei,t + t for each ei,t on path pt. The history changes to ht+1 = [ht,2:∆, pt]. In comparison to the multi-armed bandit protocol, the learner here selects an sG-tG path on the graph G, the history at any time t consists of the entire set of paths {pt−∆, . . . , pt−1}, and we assume that the congestion function on each edge fcong(h, e) depends on the number of times this edge has been used in the past ∆ time steps. The following theorem generalizes the result from Theorem 1 and shows that a variant of CARMAB has regret Õ( √ T ) for the above sG-tG online problem. Theorem 2 (Regret bound for CARMAB-st). For any confidence δ ∈ (0, 1), congestion window ∆ > 0 and time horizon T , the policy regret, of CARMAB-st is
RT (CARMAB-st; Π, fcong) ≤ c ·∆2V E log ( V T
∆E
) + c √ V E∆T log ( V E∆T
δ
) + c √ V T log ( 1
δ ) with probability at least 1− δ.
The proof of the above theorem is detailed in Appendix A.3.

heading: 3 LINEAR CONTEXTUAL BANDITS WITH CONGESTION
text: We now consider the contextual version of the congested bandit problem, where the reward function depends on the choice of arm a as well as an underlying context x ∈ X .While most of our notation stays the same from the multi-armed bandit setup in Section 2, we introduce the modifications required to account for the context vectors xt. We consider the linear contextual bandit problem where the reward function is parameterized as a linear function of a parameter θ∗ and context-action features φ(xt, at), that is, r(ht, at, xt; θ∗) : = 〈θ∗, φ(xt, at)〉fcong(at,#(ht, at)), where we assume that the context-action features φ(xt, at) ⊂ Rd satisfy ‖φ(xt, at)‖2 ≤ 1 and the true parameter ‖θ∗‖2 ≤ 1. In contrast to the bandit setup, we expand our policy class to be dependent on the context as well with ΠX : = {π : H∆ ×X 7→ [K]}. In each round of the linear contextual bandits with congestion game, the learner observes context vectors {φ(xt, ai)}[K] and selects action at. The learner then observes reward r̃(ht, xt, at) = r(ht, at, xt; θ∗) + t and the history changes to ht+1 = [ht,2:∆, at]. The objective of the learner in the above contextual bandit game is to output a sequence of actions which are competitive with the best policy π ∈ ΠX . Formally, the regret of an algorithm alg is defined to be
RT (alg; ΠX , fcong, θ∗) : = sup π∈ΠX T∑ t=1 r(hπt , π(h π t , xt), xt; θ∗)− T∑ t=1 r̃(halgt , at, xt; θ∗) . (5)
In order to provide some intuition about the algorithm, we start with a simple case where all the contexts are known to the learner in advance and later generalize the results to stochastic contexts.

heading: 3.1 WARM-UP: KNOWN CONTEXTS
text: In the known context setup, the learner is provided access to a set of contexts {xt} at the start of the online learning game. Algorithm 2 details our proposed algorithm, CARCB, for this setup.
Algorithm 2: CARCB: Congested linear contextual bandits with known contexts Input: Congestion window ∆, congestion function fcong, action set [K], time horizon T , contexts {xt}Tt=1 Initialize: Set t = 1, θ1 ∼ unif(Bd) for episodes e = 1, . . . , E do
Initialize episode Set start time of episode te = t. Let the steps in this epoch Ie = [te, . . . , te + 2e∆]. Set the episode policy π̃e = arg maxπ∈ΠX ∑ t∈Ie\{te,...,te+∆} r(h π t , π(h π t , xt), xt; θe) Execute estimated policy for t = te, . . . , te + 2e∆ do
Select arm at = π̃e(ht, xt) and observe reward r̂t. Update θe via OLS update θe+1 = arg minθ ∑ τ (rτ − 〈θ, φ(xτ , aτ )〉fcong(aτ ,#(hτ , aτ ))2
Algorithm details. We again divide the total time T into E episodes, where the length of each episode e = 2e∆. Unlike CARMAB, the algorithm does not maintain any optimistic estimate of the reward parameter θ∗ but simply updates it via an ordinary least squares (OLS) procedure and executes the policy π̃e which maximizes this estimated reward function. The core idea underlying this algorithm is that as we observe more samples, our estimate θe converges to θ∗ and our planner is then able to execute the optimal sequence of actions.
Regret analysis. To analyze the regret for CARCB, we study the error incurred in estimating the parameter θe from the reward samples. To do so, we begin by making the following assumption on the minimum eigenvalue of the sample covariance matrix obtained at any time te. Assumption 1. For t > cd and for any sequence of actions {a1, . . . , aT }, we have λmin ( 1 t ∑ τ≤t φ(xt, at)φ(xt, at) > ) ≥ γ , for some value γ > 0.
Our bound on the regret RT will depend on this minimum eigenvalue γ. Later when we generalize our setup to the unknown setup, we will show that this assumption holds with high probability for a large class of distributions. The following theorem shows that the regret bound for CARCB scales as Õ( √ dT + ∆) with high probability.
Proposition 1 (Regret bound; known contexts). For any confidence δ ∈ (0, 1), congestion window ∆ > 0 and time horizon T > cd, suppose that the sample covariance Σt satisfies Assumption 1. Then, the policy regret, defined in eq. (5), of CARCB with respect to the set Π is
RT (CARCB; ΠX , fcong) ≤ c γ · cmin · √ d(T + ∆) · log log(T ) δ + ∆ log(T ) + c √ T log ( K δ ) with probability at least 1− δ where cmin = mina,j fcong(a, j).
The proof of the above theorem is deferred to Appendix B. At a high level, the proof proceeds in two steps where first it upper bounds the error ‖θe − θ∗‖2 for every epoch e and then uses this to bound the deviation of the policy π̃e from the optimal choice of policy π∗. In the next section, we generalize this result to the unknown context setup.

heading: 3.2 UNKNOWN STOCHASTIC CONTEXTS
text: Our stochastic setup assumes that the context vectors {φ(xt, at)} at each time step are sampled i.i.d. from a known distribution. We formally state this assumption3 next. Assumption 2 (Stochastic contexts from known distribution.). At each time instance t, the features φ(xt, a) for every action a ∈ [K] are assumed to be sampled i.i.d. from the Gaussian distribution N (x̄a,Σa), such that αlI Σa αuI and ‖x̄a‖2 ≤ 1.
3While our results are stated in terms of the multivariate Gaussian distribution, these can be generalized to sub-Gaussian distribution.
For large-scale recommendation systems for traffic routing which interact with million of users daily, the above assumption on known distributions is not restrictive at all. Indeed these systems have a fair understanding of the demographics of the population which interact with it on a daily basis and the real uncertainty is on which person from this population will be using the system at any time.
The algorithm for this setup is similar to the known context scenario where instead of planning with the exact contexts in the optimistic policy computation step, we obtain the episode policy as
π̃e = arg max π∈Π
E[ ∑
t∈Ie\{te,...,te+∆}
r(hπt , π(h π t , xt), xt; θe)] ,
where the expectation is taken with respect to the sampling of context. Our regret bound for this modified algorithm depends on the mixing time of the policy set ΠX in an appropriately defined Markov chain. Definition 2 (Mixing-time of Markov chain). For an ergodic discrete time Markov chain M , let d represent an arbitrary starting state distribution and let d∗ denote the stationary distribution. The -mixing time τmix( ) is defined as τmix( ) = min{t : maxd ‖dM t − d∗‖TV ≤ }.
The mixing time of the policy set ΠX is given by τ∗mix : = maxπ∈ΠX maxh τmix,π(h). The following theorem establishes the regret bound for the modified CARCB algorithm, showing that not knowing the context can increase the regret by an additive factor of Õ( √ ∆τ∗mix · T ).
Theorem 3 (Regret bound; unknown contexts). For any confidence δ ∈ (0, 1), congestion window ∆ > 0 and time horizon T , suppose that the context sampling distributions satisfy Assumption 2. Then, with probability at least 1− δ, the policy regret of CARCB satisfies
RT (CARCB; ΠX , fcong) ≤ c · √ αuT log ( K
δ
) + c · √ ∆τ∗mixT log ( K log(T )
δ
)
+ cαu cminαl
· √ d(T + ∆) · log log(T )
δ + ∆ log(T ) . (6)
A detailed proof of this result is deferred to Appendix B. Observe that the above bound can be seen as a sum of two terms: RT . √ dT + √ ∆τ∗mixT . The first term is a standard regret bound in the d dimensional contextual bandit setup. The second term, particular to our setup, arises because of the interaction of the congestion window with the unknown stochastic contexts. In comparison to the bound in Theorem 1, the window size ∆ interacts only additively in the regret bound surprisingly. The reason for this additive deterioration of regret is that the shared parameter θ∗ allows us to use data across time steps in our estimation procedure – thus, in effect, the congestion only slows the estimation by a factor of cmin which shows up due to the dependence on the minimum eigenvalue.
In order to go from the regret bound in the known context case, Proposition 1, we need to address two key technical challenges: 1) bound the deviation of the reward of policy π̃e from the policy which plans with the known sampled contexts, and 2) the context vectors selected by the algorithm φ(xt, at) satisfy the minimum eigenvalue condition in Assumption 1.
Deviation from known contexts. One way to get around this difficulty is to reduce the above problem to the multi-armed bandit on from Section 2. This simple reduction would lead to a regret bound which scales with the size of the context space |X | which is exponentially large in the dimension d. Instead of this, we show that the reward obtained by the distribution maximizer π̃e are close to those obtained by the sample maximizer via a concentration argument for random walks on the induced Markov chains. The key to our analysis is the construction of this random walk using policy π̃e and then using the following concentration bound from . Lemma 1 (Theorem 3.1 in Chung et al. (2012)). Let M be an ergodic Markov chain with state space [n] and stationary distribution d∗. Let (V1, ..., Vt) denote a t-step random walk on M starting from an initial distribution d on [n]. Let µ = EV∼d∗ [f(V )] denote the expected reward over the stationary distribution and X = ∑ i f(Vi) denote the sum of function on the random walk. There exists a universal constant c > 0 such that
Pr(|X − µt| ≥ δµt) ≤ c‖d‖d∗ exp ( −δ2µt 72τmix ) for 0 ≤ δ < 1 , (7)
where the norm ‖d‖2d∗ : = ∑ i d2i d∗i .
This concentration bound is not directly applicable to our setup because of two reasons: 1) the constructed Markov chainMπ̃e might not be ergodic, and 2) the norm ‖d‖d∗ might be unbounded in our setup. By using the fact that the diameter of the MDP Mπ̃e is bounded by ∆, we use an intermediate policy in the time steps {te : te + ∆} in each episode reach a state starting from which the MDP is shown to be ergodic and have bounded norm ‖d‖d∗ . See Appendix B for details.
Minimum eigenvalue bound. In order to obtain a regret bound for the stochastic setup, we need to establish that the covariance matrix formed by these context-action features satisfies the minimum eigenvalue assumption. The challenge here is that the the features φ(xt, at) are not independent across time – they are correlated since the algorithm’s choice at time t depends on the history ht which in turn depends on the past features. In Appendix B we get around this difficulty by decoupling these dependencies and showing that even after this decoupling, the random variables still satisfy a sub-exponential moment inequality.

heading: 4 EXPERIMENTAL EVALUATION
text: In this section, we evaluate both our proposed algorithms, CARMAB and CARCB, in the congested bandit framework and exhibit their no-regret properties.
We generate K arms and assign a base reward of r̂j ∈ (0, 1) to each j ∈ [K]. We draw a noise parameter t,j for every action j and time step t. We set fcong(at,#(ht, at)) = 1/#(ht, at). We also set the parameter ∆, which controls the length of the history ht at time t. Then, the observed reward is r̃(ht, at) =
r̂at #(ht,at)
+ t,at . We set parameter δ of algorithm CARMAB to 0.1. In terms of distributions, we draw r̂j uniformly in (0, 1) and t,j from N (0, 0.1). In Figure 2, we present how the average regret of the algorithm changes as time progresses for K = 4 and different values of the window size ∆ during which congestion occurs.
For evaluating CARCB, again we generateK arms. For each arm i ∈ [K] and each time step t ∈ [T ], we draw a random context. A context xa,t is a vector of 10 numbers which are drawn uniformly in (0, 1) and then normalized so that the Euclidean norm of the vector is unit. We also draw the true parameter θ∗ in the same way. We assume each arm’s context is available to the algorithm at each time step. We use the same noise and congestion function as in the previous section. The observed reward in this setting is:
r̃(ht, at, xa,t, θ∗) = xTa,tθ∗
#(ht, at) + t,at
In Figure 2 we present how the average regret of CARCB changes over time, in a setting with similar K and ∆ (K = ∆ = 4) and a setting with a number of actions larger than the congestion window (K = 10 and ∆ = 2).
ETHICS STATEMENT
Our contributions in this work are theoretical in nature and we do not see any ethics related issue arising from this work in the foreseeable future.
REPRODUCIBILITY STATEMENT
On the theoretical side, we provide detailed proofs for all our theoretical results in the appendix. For the experimental aspect, we have attached our python code as a supplementary file. Furthermore, we have described all necessary hyper parameters and algorithmic details required to reproduce the experiments.

Review summaries:
This paper proposes a novel multi-armed bandit framework to formulate the scenario of route recommendation based on dynamic traffic situations. The formulated model fits in both stochastic bandits and linear contextual bandits.  The paper first introduces the stochastic bandit setting with time-varying expected reward for each arm, which depends on the pulling history within a fixed-sized sliding window. The authors propose an algorithm CARMAB, with regret analysis indicating that the regret upper bound scales as $ O(\sqrt{K\Delta T\log(\Delta KT)})$ with high probability.  Then the paper discusses the contextual bandit setting with known contexts. The authors updated the model and propose an algorithm CARCB with regret analysis indicating the regret upper bound scales as $\tilde O(\sqrt{dT+\Delta})$ with high probability. Then the authors further relax the assumption on contexts by allowing unknown stochastic contexts samples from a known distribution. The regret analysis indicates an additional term with respect to  $T$ comparing to the known contexts setting.

This paper studied congested bandits, a special class of multi-armed bandit problems where each arm's reward depends on the number of times it was played in the past few steps. The authors showed the reduction of the congested bandit problem to an MDP problem. A UCRL-type algorithm was then proposed and the regret bound of the algorithm was analyzed. 

This paper raises and studies a new problem named congested bandits, an extension of the standard multi-armed bandits (MAB) problems. In this setting, the reward of an arm depends on the number of times this arm has been pulled during the past $\Delta$ time. The authors also extended the congested bandits to graph-based congested bandits and congested linear contextual bandits.   The authors proposed new algorithms for the above settings and derived regret upper bounds similar to those of MAB or linear contextual bandits.   To be specific, for congested bandits, the regret upper bound is $\tilde{O}(\sqrt{K\Delta T})$, where $K$ is the number of arms and $T$ is the time horizon. For graph-based congested bandits, the regret upper bound is $\tilde{O}(\sqrt{VE\Delta T})$, where $V$ is the number of nodes and $E$ is the number of edges. For congested linear contextual bandits, the regret upper bound is $\tilde{O}(\sqrt{dT})$.  The authors also conducted numerical simulations to confirm the above theoretical results. 

This paper proposes a new structured bandit model, called congested bandits, where an arm’s reward is a decaying function of how many times it has been played during a recent time window. The proposed bandit model aims to address recommendation problems such as route recommendation, in which recommended routes tend to get congested (hence yield lower rewards). Different from prior work on bandits with changing arm reward distributions, the current paper proposes a model in which the effect of congestion resets over Delta time steps. By viewing the problem as structured MDP, the paper develops a variant of UCRL2 that learns to recommend the optimal arm for each congestion state. It is shown that the proposed algorithm achieves a policy regret of tilde{O}(sqrt{KDeltaT}), which significantly improves upon the exponential dependence on the state space of UCRL2. The authors also propose a variant of their algorithm tailored for the linear stochastic contextual bandit setup and analyze the policy regret for this case as well.