Congested bandits: Optimal routing via short-term resets
Authors: Pranjal Awasthi
Kush Bhatia
Sreenivas Gollapudi
Kostas Kollias
Venue: ICLR 2022 Submitted (2022)
Keywords: Multi-armed bandits
linear contextual bandits
policy regret
congestion aware routing

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 $\Delta$ 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 $\tilde{O}(\sqrt{K \Delta T})$. For the linear contextual bandit setup, our algorithm, based on an iterative least squares planner, achieves policy regret $\tilde{O}(\sqrt{dT} + \Delta)$. From an experimental standpoint, we corroborate the no-regret properties of our algorithms via a simulation study.

Under review as a conference paper at ICLR 2022
CONGESTED BANDITS: OPTIMAL ROUTING VIA SHORT-TERM RESETS
Anonymous authors Paper under double-blind review
ABSTRACT
For traffic routing platforms, the choice of which route to recommend to a user de- pends on the congestion on these routes indeed, an individual's 's utility depends on the number of people using the recommended route at that instance. Moti- vated by this, reward is allowed to depend on the number of times it was played in the past A timesteps. This dependence on past history of actions leads dynamical system where an algorithm's 's present choices also affect its future pay-offs, and requires an algorithm to plan for this. We study the congestion aware formulation the multi-armed bandit (MAB) setup and in the contextual bandit setup with linear rewards. For the multi-armer setup. we propose UCB style algorithm and show that its policy regret scales as Ö TIVKATT KA).. For the linear contextual bandit setup, our algorithm, based on an iterative least squares planner, achieves policy regret Ó(VdT + A). From an experimental standpoint, we corroborate the no-regret properties of our algorithms via simulation study.
introduce the problem of Congested Bandits where each arm's
INTRODUCTION
The online multi-armes bandit (MAB) problem and its extensions have been widely studied and used model many real world scenarios (Robbins) 1952 Auer 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 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 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 given time step may depend on the algorithm's is choices in the previous time steps. In particular, we are motivated by online routing problems where the reward of suggesting 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.c., the best sequence of actions, in hindsight compared
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 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 given time window of size A. Hence over time, an arm's 's expected reward may decay and reset dynamically. While our model 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 A. In both the scenarios above, the ability to reset the congestion cost (by simply not playing an arm for A time steps) is crucial part of the problem formulation.

---

Under review as a conference paper at ICLR 2022
Cumulative Reward
Algorithm No-regret MAB
Route I
Ri R2 Ri R2
Route
0.4
Ri Ri Ri Ri
Route
0.6
0.3
Route 2
Route rewards
Time
(a)
(b)
Figure 1, Our proposed Congested Bandits framework. (a) A route recommendation scenario where an algorithm can recommend one of two routes to the incoming vehicle. (b) The reward for each route depends on whether there is congestion on the route or not. (c) Traditional multi-armed bandit algorithms learn to recommend the best route, Route I for every incoming vehicle. This is clearly suboptimal. Our algorithm, CARMAB, adapts to the congestion and achieves better performance.
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 a K-armed stochastic bandit problem where each arm a has a mean reward Na, and the mean reward obtained by playing arm at time equals Scong (a, (a, he) Here he denotes the history of the algorithm's 's choices within the last A time steps and scong is a non-increasing congestion function. Recall that the algorithm's '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 regret bound that scales exponential in the parameters (scaling as A (Auer et al. 2009 Jaksch et al. 2010). Instead, we carefully exploit the problem structure to design an algorithm with npar-optimal regret scaling as Ō(VKAT). 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 contextual setting where the mean reward for each arm/edge at a given time step equals fcong (a, he) (0., o(I, a))), where E Idd is context vector and 0, is an unknown parameter. This extension is inspired from classical work in contextual bandits (Li et al. 2010 Chu al. 2011 and captures scenarios where users may have different preferences over actions/arms (e.g., 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 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 the algorithm. As a result, we obtain algorithms that achieve Ö(v (TVTT + A) 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 im- proving 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 monotonic way as a function of the number of times the arm has been played in the past. There is no notion of short-term reset as in our setting. As 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 The work Heidari 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. How- ever, similar to the rotting bandits setup there is no notion of reset. PPik--Burk Burke Grünewälder (201)) considers notion of reset/improvement by allowing the mean reward to depend on the num- ber 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 Gaussian process. On the other hand, in our work, the reward a function of the number of times an arm was played in the past A time steps. However their regret bounds are either with respect to the instantaneous regret, or with respect to weaker policy class of d-step look ahead policies. The notion of instantancous regret only compares with the class of greedy policies at each timestep compared the globally optimal policy.
2

---

Under review as a conference paper at ICLR 2022
There also exist works studying the design of online learning algorithms against m-bounded memory adversaries. The assumption here is that the reward an action at each time step depends only on the previous actions. While this is also true for our setting, in general the regret bounds provided for hounded-memors adversaries are either with respect to fixed action or a policy class containing policies that do switch often (Arora the contextual setup is reminiscent of the recent line of works on contextual MDPs (Azizadennssheii
2012 Anava et al. 2013). Our problem formulation for
al. 2016 Krishnamurthy et al. 2016 Hallak al., 2015 Modi Tewari 2020). However these works either assume that the context vector is fixed for 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 natural extension of classical work on the online shortest
path problem Kalai Vempala 2005); Awerbuch & Kleinberg (2008); Dani et al. (0007)
2 CONGESTED MULTI-ARMER BANDIT
In this section, we model the congestion problem in multi-armed bandit (MAB) framework. Our setup for congested multi-armed bandits models the congestion phenomenon by allowing the re- wards of an arm to depend on the number of times it was played in the past.
Let us consider MAB setup with K arms, where each arm may represent 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 h2 Ha [K] denote the history of the actions taken by algorithm in the past time steps, that is, f22 = (a.-A...... 4--1] where a, is the action chosen by the algorithm at time In order model congestion arising from repeated plays of single arm, we consider a function feong [K] x | + (0, 1]. This congestion function takes in two arguments: an arm a and the number of times this arm was played in the past A time steps, and outputs a value indicating the decay in the reward of arm arising from congestion.
Protocol for congestion in bandits. We consider the following online learning protocol for learner our congested MAB framework: At each round I, the learner picks an arm de E [K] and observes reward
F(he, 0+) - Scong # (he, 0e)) Mai + Et
where e, ~ N0(0, 1)).
Finally, the history changes to he+11 = [h,,2:,, ar] where we have used the notation fug, to denote the vector [ir( h,(j)] and #(h, a) to denote the number of times the action was played in history
Each arm a is associated with a mean reward vector Na 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 well the the mean vector μ {Ma {p]. The objective of the learner is to select the actions 0₂ 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[ I this benchmark is not suitable for our setup. Indeed, the asymptotically optimal algorithm is one which maximizes the average cumulative reward p" maXaig 3 Σi= r(h,, at), where the action a, is the one chosen by the algorithm alg and history hy is the sequence of actions in the past A time steps.
This asymptotically algorithm corresponds to a stationary policy x" whose selection a only de- pends the history h4. Accordingly, consider the following class of stationary policies as the comparator for our regret IT (х HA > [K]] with size [T|| = KK* Denote by hi the history at time / by running policy up to time f,, we define the policy regret for any algorithm
T
(alg: II, fcong) sup (( (h2)))
Σ
Σ
F(h al ax)
(1)
ell t=1
t=1
We usually suppress the dependence of this history the algorithm, but make it explicit whenever is not clear from context.
3

---

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 into total of & epochs, each of which can be of varying length. In each episode, for every pair (a.j) of action a and historical count j [A]_, the algorithm computes the empirical estimate the rewards f. (a, from observations in the past epoch and maintains a Under review as a conference paper at ICLR 2022
Algorithm 1: CARMAB: Congestion Aware Routing via Multi-Armed Bandits
Input: Congestion window A, confidence parameter E (0, 1), action set [K], time horizon T. Initialize: Set
for episodes c , do
Initialize episode
Set start time of episode =t
For all actions and historical count j, set (a.a.j) 0 and N. (a Eoce ns(a,)). Set empirical reward estimate for each arm and historical count
fe(a. Ei-tn 74 Ia, a.j- =
max (e,N,,,,Ja))
Compute optimistic policy Set the feasible rewards
log(AAt./5)
R₂ r E (0, for all (a,j), fc(a,))) s 10 max (a,
Find optimistic policy म. = arg max p(T,r) Execute optimistic policy while () < max(1, No (a. do
Select arm ar = #e (8t). obtain reward ft. Update n. (a ( a)) ne(a, ((s,, a)) + 1.
where is the action chosen by alg at time f and r(h,, az) = fcong (he,) Pa., This notion of regret called policy regret (Arora al. 2012) because the history sequence observed by the algorithm T and the algorithm alg can be different from each other - this leads to situation where choosing the same action a at time t can lead to different rewards for the algorithm and the comparator.
=
2.1 CARMAB: CONGESTED MAB ALGORITHM
We now describe our learning algorithm for the congested MAB problem. At high level, CARMAB, detailed in Algorithm T is based on a reduction of this problem to reinforcement learning problem with state space S = HA and action space A [K]. where the underlying dy- namics are known to the learner. With this reduction, CARMAB deploys an epoch-based based strategy which plays optimistic policy म. computed from optimistic estimates of the reward function.
Reduction to MDP. Our congested MAB setup can be viewed learning problem in Markov decision process (MDP) with finite state and action spaces, This MDP Mmab comprises state space S Ha and action space A [K]. The reward function for this MDP is given by r(s, a) fcong( (a, #(s a)) Ha and the deterministic state transitions are given P(s'|s. s, a) = I[s' = [S2.A. a]].
feasible set R, of rewards. This set is constructed such that with high probability, the true reward belong to this set for each epoch. Given this set, our algorithm computes the optimistic policy
1 Σ T
म. arg max
(r) where
Px := lim
r(h ((h)))
TEIl,ERR,
T
that is, the policy which achieves the best average expected reward with respect to the optimistic set RR. The optimistic policy πe 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 cyclical path since the transition dynamics are deterministic and the state space is finite. With
4

---

Under review as a conference paper at ICLR 2022
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 KKrpp 1978) for finding these optimistic policy. This algorithm runs in time 0(A++)
2.2 REGRET ANALYSIS FOR CARMAB
In this section, obtain bound on the policy regret of the proposed algorithm CARMAB. Our overall proof strategy to first establish that the MDP Mmab has a low diameter (the time taken to move from state to another in the MDP), then bounding the regret in each episode of the process and finally establishing that the total number of episodes & can be at most logarithmic the time horizon T. Combining these elements, establish in the following theorem that the regret of CARMAB scales as Ö(v K AT) with high probability
Theorem 1 (Regret bound for CARMAB). For any confidence E (0, 1), congestion window A > O and time horizon T > AK, the policy regret ① of CARMAB is
T AK
AKT 8
(C; S C.K log
+ +0 KAT log
+ c T Tlog
with probability at least 1 5.
few comments on the theorem are in order. Observe that the dominating term in the above re- gret bound scales as ((VKAT) in contrast the classical regret bounds for MAB which have a Ö(vK') KT) dependence. This additional factor of VA comes from the fact the stronger notion of policy regret as well as the non-stationary nature of the arm rewards. Additionally, naïve ap- plication of the UCRL2 regret bound to the constructed MDP scales linearly with state space and would correspond to 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 A, the lower bounds from the classical MAB setup immediately imply that the regret of any learner should scale as Q KT), which matches the upper bound in Theorem 1.
We defer the complete proof of this Appendix A but provide 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 8 using an appropriately chosen policy. The diameter is measure of the connectedness of the underlying MDP and commonly studied in the literature on reinforcement learning [Puterman,22) 2014).
Definition 1 (Diameter of MDP.). Consider the stochastic process induced by the policy MDP M. Let T (5' M,, π represent the first time the policy reaches state s' starting from s. The diameter D of the MDP is D maX,4ss min, E[r(s' M,,, T))-
Recall from Section 2.1 that the MDP Mmab has deterministic dynamics and state space given by the set of histories H.s. Proposition 2 in Appendix ( esstabliss that the diameter of this MDP is at most the window size A. 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.
T (5)
Ry < TEIl
F.
q Tlog
with -==n=nnaa (a. Scoog (a,
which holds with probability at least 1 8. We have used ne (a.j) 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 bound the per-episode regret
(a
For clarity purposes, through out the paper we denote by absolute constant whose value is independent of any problem parameter. We allow this value of change from line to line.
5

---

Under review as a conference paper at ICLR 2022
Regret for episode t. In episode e, the set of feasible rewards R. is chosen to ensure that with high probability, the true reward r" (a. j) fcong(a, j) My belongs to this set. Conditioning on this event, show that the regret in each episode is upper bounded by the window size A and scaled ratio of the number of times each action-history (a,j) is played, that is,
Aktt 8
The ne(a,))
F. f A log
Σ a.j
(4)
Vmax (a.
where te is the time at which episode starts and N.(a. = Eike (;( Theorem follows from combining the above with bound on the total number of episodes & S c- AK log AR
2.3 ROUTING WITH CONGESTED BANDITS
We now study an extension of the congested MAB setup where the arms correspond 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 sc-tG path ps on the graph G and receives reward F(h,, e4,1) Scong(es e, (h+, ei,))) Meg,e + for each Gitt path pt. The history changes to h++1 = (hr,,:a,Pl] Pc]-
In comparison to the multi-armer bandit protocol, the learner here selects an sc-tG path on the graph G. the history at any time consists of the entire set of paths {Pt {Pt-A..... Pt-11. h. and we assume that the congestion function on each edge [cang(h, e) depends on the number of times this edge has been used in the past A time steps. The following theorem generalizes the result from Theorem and shows that variant of CARMAB has regret Ö(VT) for the above sc-lc online problem.
Theorem 2 (Regret bound for CARMAB-st). For any confidence ō E (0, congestion window A > O and time horizon T, the policy regret, of CARMAB-SI is
VT AE
VEAT
(
Rr (CARMABBsst 11, fcong) S c. A-VAVVEEO
E
VEAT log
+ C log
with probability at least 1
The proof of the above theorem is detailed in Appendix A.3
LINEAR CONTEXTUAL BANDITS WITH CONGESTION
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 E 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 Zt. We consider the linear contextual bandit problem where the reward function is parameterized as linear function of parameter 6, and context-action features 6(2,, a.), that is, r(hr, at, Ir; 0.) = (0., 6(Ir, 0z)) (con))c # (he, at)). where we assume that the context-action features ((x,, 0z) C Rdd satisfy [|œ(I;, 04)l|2 S and the true parameter ||0~112 S 1. In contrast to the bandit setup. we expand our policy class to be dependent on the context as well with 11x = {x : HA x X' + [K]].
In each round of the linear contextual bandits with congestion game, the learner observes con- text vectors {Ø(ø,, [x) and selects action dg. The learner then observes reward F(h,, X2, a.) = r(he, at, zy; O.) + 6, and the history changes to he+1 = [bx,2: 0r). The objective of the learner in the above contextual bandit game is to output sequence of actions which are competitive with the best policy π E 1xx Formally, the regret of an algorithm alg is defined to be
T
(alg: XIx, foong 0.) = sup Σ r(h7 x [hT (2),,))) x.),, 21;
Σ F(hels ar 01;0); (5)
rlllx
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.
3.1 WARM-UP: KNOWN CONTEXTS
In the known context setup, the learner is provided access to a set of contexts {a,} at the start of the online learning game. Algorithm details our proposed algorithm, CARCB, for this setup.

---

Under review as a conference paper at ICLR 2022
Algorithm 2: CARCB: Congested linear contextual bandits with known contexts
Input:
Congestion window A, congestion function fcong. action set [K], time horizon T, contexts [xz]i=1 Initialize: Set ( = 1, 0 unif((Ba)
for episodes c = 8, do
Initialize episode Set start time of episode le = L.
Let the steps in this epoch I. (le....,, +
Set the episode policy मe- = arg max, EtEle\(eemnte-)) rlh (h7 ,0),,,,,,, (1;
Execute estimated policy
for t te....,te
.....,,e tt 2 A do L Select d4 #e (c(,,, 22) and observe reward ft. Update 0. via OLS update de+1 arg ming E, (r= (0, 0(x,, ar) fcong Fole,#(00 #(r, aT))
Algorithm details. We again divide the total time T into episodes, where the length of each episode 2 A. Unlike CARMAB, the algorithm does not maintain any optimistic estimate of the reward parameter& 9, but simply updates it via an ordinary least squares (OLS) procedure and executes the policy म. which maximizes this estimated reward function. The core idea underlying this algorithm that as we observe more samples, our estimate 0, converges to 0, and our planner then able execute the optimal sequence of actions.
Regret analysis. To analyze the regret for CARCB, we study the error incurred in estimating the parameter 0, 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 f.-
Assumption 1. For > ed and for any sequence of actions { ..),, we have Amin Ersr o(x, (0)(())))TT) 27 for some value y > O.
Our bound on the regret Ry will depend this minimum eigenvalue 7, Later when generalize our setup to the unknown setup, we will show that this assumption holds with high probability for large class of distributions. The following theorem shows that the regret bound for CARC B scales Ó(vdT + A) with high probability.
Proposition 1 (Regret bound; known contexts). For any confidence & E (0, 1), congestion window A O and time horizon T > cd, suppose that the sample covariance E, satisfies Assumption 1 Then, the policy regret, defined in eg. (5), of CARCB with respect to the set 11 is
log(T)
+ A log(T) + a Tlog (
(CACC Ix, Scong) S 7. Cmin V d(T + A) -log
5
with probability at least 1 - 5 where Cmin = mina.j Scong(( (a, j).
The proof of the above theorem is deferred to Appendix At a high level, the proof proceeds in two steps where first it upper bounds the error 10, 0, for every epoch and then uses this to bound the deviation the policy म. from the optimal choice of policy π*. In the next section, we generalize this result to the unknown context setup.
3.2 UNKNOWN STOCHASTIC CONTEXTS
Our stochastic setup assumes that the context vectors (ō(æ,, a.)} at each time step are sampled i.i.d. from known distribution. We formally state this assumptior next.
Assumption (Stochastic contexts from known distribution.). At each time instance t, the features ((x,, a) for every action a [K] are assumed be sampled i.i.d. from the Gaussian distribution ( Ea), such that oq 3 Σ, 3 o and [ < 1.
While our results are stated in terms of the multivariate Gaussian distribution, these can he generalized to sub-Gaussian distribution.

---

Under review as a conference paper at ICLR 2022
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 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
# = arg max E HIll
Σ
r(hg x (h7 2t), z4; 0e)]
tEL
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 IIx 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 e-mixing time Tmix(e) is defined as Teix(e) = min(t: maxa [|dM |TV S e).
The mixing time of the policy set 1Ix is given by mix maxx max,, Tmix, (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 Ó(/ATri T
Theorem (Regret bound; unknown contexts). For any confidence ó E (0, 1), congestion window
A O and time horizon T, suppose that the context sampling distributions satisfy Assumption 2
Then, with probability at least 1- 8, the policy regret of CARCB satisfies
K )
K (og(T)
(CARCC IIx fcons) S c
a TaTT log
+c.
A
mix Tlog
5
log(T')
d(T + A) log
+ log(T)
(6)
Cmin
B Observe that the above bound can be seen as a sum of two terms: Ry S VdT + /Armit The first term standard regret bound in the d dimensional contextual bandit setup. The second term, particular to setup, arises because of the interaction of the congestion window with the unknown stochastic contexts. comparison to the bound in Theorem | the window size A interacts only additively in the regret bound surprisingly. The reason for this additive deterioration of regret is that the shared parameter 6. allows us to use data across time steps in our estimation procedure thus, in effect, the congestion only slows the estimation by factor of Cmin which shows up due to the dependence on the minimum eigenvalue.
detailed proof of this result deferred to Appendix
In order to go from the regret bound in the known context case, Proposition 1 need address two key technical challenges: 1) bound the deviation of the reward of policy म. from the policy which plans with the known sampled contexts, and 2) the context vectors selected by the algorithm 6(*,, ax) satisfy the minimum eigenvalue condition in Assumption] [
Deviation from known contexts. One way get around this difficulty is reduce the above problem to the multi-armed bandit on from Section 2 This simple reduction would lead to regret bound which scales with the size of the context space |XX which is exponentially large in the di- mension d. Instead of this, we show that the reward obtained by the distribution maximizer म. 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 ergodic Markov chain with state space [n] and stationary distribution d'. Let (V1,.., Vo) denote a t-step random walk on M starting from an initial distribution d on [n). Let μ Ev [S(V) denote the expected reward over the stationary distribution and X Σ. (V%) denote the sum of function on the random walk. There
exists a universal constant e > such that
(80pt
Pr([X ju| 2 8pt) cl|d]|a- exp
0
72
8

---

Under review as a conference paper at ICLR 2022
di ap" where the norm | Σ,
This concentration bound is not directly applicable to setup because of two reasons: 1) the constructed Markov chain Ma, 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 Ma, is bounded by A, we use an intermediate policy in the time steps {4e : le А} in each episode reach a state starting from which the MDP is shown be ergodic and have bounded norm || See Appendix 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- features satisfies the minimum eigenvalue assumption. The challenge here is that the the features ((Ix, (t.) are not independent across time- - they are correlated since the algorithm's is choice at time / depends on the history he which in turn depends the past features. In Appendix B we get around this difficulty by de- coupling these dependencies and showing that even after this decoupling, the random variables still satisfy sub-exponential moment inequality.
EXPERIMENTAL EVALUATION
In this section, evaluate both proposed algorithms, CARMAB and CARCB, in the congested bandit framework and exhibit their no-regret properties.
We generate K arms and assign base reward of fy E (0. to each [K]. We draw noise parameter Etj for every action j and time step t. We set Frong(ar, # #(y, a²)) = 1/# (h,, a.). We also set the parameter A, which controls the length of the history h4 time t. Then, the observed fay
reward is F(le, 0r) = #(h.,a)) + Er.a. We set parameter å of algorithm CARMAB to 0.1. In terms of distributions, we draw fnj uniformly in (0, 1) and 6t from (00 0.1). In Figure we present how the average regret of the algorithm changes as time progresses for K = 4 and different values of the window size A during which congestion occurs.
CARMAB Regret with k=
CARCB Regret
8--4
E-10anda-22 k-dandd-4
0.04
Average Regret
0.03
0.2
0.02
0.01
0.00
0.0
100000
150000
250000
2000
4000
6000
0000
Timsstup
Tir Tiieesep
Figure 2. (Left) No-regret property of CARMAB. CARMAB is able to learn optimal sequence of arms play and enjoys no-regret property. Increasing the size of history window A makes the problem more challenging and requires larger number of time steps. (Right) No-regret property CARCB.
For evaluating CARCB, again we generate K arms. For each arm E [K] and each time step f [T]] draw random context. A context Fa,t is vector of 10 numbers which drawn uniformly in (0, 1) and then normalized so that the Euclidean norm of the vector is unit. We also draw the true parameter 0, in the same way. We assume each arm's context is available to the algorithm each time step. We use the same noise and congestion function as in the previous section. The observed reward in this setting is:
F(he, Oes Na,1, 0.) = # (he, at)
Et,a,
In Figure 2 we present how the average regret of CARCB changes over time, in setting with similar K and A (K- = A = 4) and setting with number of actions larger than the congestion window (K 10 and A 2).

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
Our contributions this work are theoretical in nature and we do not see any ethics related issue arising from this work in the foresceable future.
REPRODUCIBILITY STATEMENT
On the theoretical side, provide detailed proofs for all 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 reproduce the experiments.
10

---

Under review as a conference paper at ICLR 2022
REFERENCES
Oren Anava, Elad Hazan, and Shie Mannor. Online learning for adversaries with memory: price of past mistakes. In Advances Neural Information Processing Systems, pp. 784-792. Citeseer, 2015.
Raman Arora, Ofer Dekel, and Ambuj Tewari. Online bandit learning against adaptive adversary: from regret to policy regret. arXiv preprint (edi::2206.6444 2012.
Peter Auer, Nicolo Cesa-Bianchi, and Yoav Freund Robert E. Schapire. The non-stochastic multi- armed bandit problem. 2001.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 2362-3):35--26,, 2002.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement
learning. In Advances in neural information processing systems, pp. 89 89-96, 2009.
Baruch Awerbuch and Robert Kleinberg. Online linear optimization and adaptive routing. Journal of Computer and System Sciences, 74:97-114, 2008.
Kamyar Arizzadenesheli,, Alessandro Lazaric, and Animashree Anandkumar. Reinforcement learn- ing of contextual mdps using spectral methods. arXiv preprint arXiv: 17X1:1661 2016.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff func- tions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208-214, 2011.
Kai-Min Chung, Henry Lam, Zhenming Liu, and Michael Mitzenmacher. Chernoff-hoeffdin bounds for markov chains: Generalized and simplified. arXiv preprint arXiv:/201.0559 2012.
Varsha Dani, Thomas P Hayes, and Sham Kakade. The price of bandit information for online optimization. 2007.
Assaf Hallak, Dotan Di Castro, and Shie Mannor. Contextual markov decision processes. arXiv preprint 1502.02502..22 2015.
Hoda Heidari, Michael J Kearns, and Aaron Roth. Tight policy regret bounds for improving and decaying bandits. In IJCAI, pp. 1562-1570, 2016.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4), 2010.
Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-307 2005.
Richard M Karp. A characterization of the minimum cycle mean in a digraph. Discrete mathematics, 23(3):309-311 1978.
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Contextual-mdee for pacreinforceemet learning with rich observations. arXiv preprint arXiv:
(rXiv:1602.022 ww....0022222222 020220 2016.
Nir Levine, Koby Crammer, and Shie Mannor. Rotting bandits. arXiv preprint arXiv: 1rXiv:1702.07274, 2017.
Lihong Li, Wei Chu, John Langford, and Robert Schapire. contextual-bande approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661-670, 2010.
Aditya Modi and Ambuj Tewari. No-regret exploration in contextual reinforcement learning. In Conference on Uncertainty Artificial Intelligence, pp. 829-838. PMLR, 2020.
Ciara and Steffen Grünewälder. Recovering bandits. arXiv preprint arXiv:1910.14354 2019.
11

---

Under review as a conference paper at ICLR 2022
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programmingg John Wiley & Sons, 2014.
Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):227-535, 1952.
Julien Seznec, Andrea Locatelli, Alexandra Carpentier, Alessandro Lazaric, and Michal Valko. Rot- ting bandits are no harder than stochastic ones. In International Conference on Artificial Intelli- gence and Statistics. PMLR, 2019.
Alcksandrs Slivkins. Introduction to multi-armed bandits. arXiv preprint 4XX0:1900.07222,2009
12


Reviews:
[{"review_id": "uQDOkLL4mfj", "reviewer": "Reviewer_9u2j", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**1. Motivation**. The congested bandit problem is said to be motivated by the traffic routing problem. However, the proposed model has almost no connection with the classic routing problem. The network routing problem is usually cast as a congestion game [1], in which the cost of an agent depends on the path it chooses and the number of agents choosing the same path. The evolutionary dynamics through which the agents learn to choose the \"best\" route (a.k.a. the day-to-day equilibrium) is also a well-studied topic. On a specific day, the realized cost of a path still should only depend on the number of agents selecting the path.\n\n[1] Rosenthal, R. W. (1973). A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2(1), 65-67. \n\nHowever, the congested bandit model proposed by the authors has a completely different mechanism. Here the reward for selecting a path (arm) depends on the number of times it was played in the past, instead of the total number of agents selecting it at the current iteration. Although it could be understood as another type of \"congestion\", I see no reason it could be applied to the traffic routing problem. \n\n**2. Model.** It seems that the decision-maker in this bandit is a traffic routing platform. First of all, in such a context, there should be two different types of agents: the platform that recommends the route and the travelers that may (or may not) follow the recommendations. The cost of a path is realized by the travelers rather than the platform. However, the proposed model doesn't have such a bi-level structure; the cost is realized by the platform itself. \n\nMeanwhile, I hope the authors could specify the goal of the platform more clearly. Here are some typical examples in the classic game/bandit literature:\n\n(1). The platform wants to achieve the desired system state. Following Wardrop's first and second principles [2], it could be (i) social optimal, that the total cost of agents is minimized; or (ii) user equilibrium, that no agent has the incentive to change its route. These two models have been widely studied in both operations research and machine learning literature. \n\n[2] Wardrop, J. G. (1952). Road paper. some theoretical aspects of road traffic research. Proceedings of the institution of civil engineers, 1(3), 325-362.\n\n(2). The platform only \"cares\" about the quality of its recommendation for specific agents. Then the problem may be cast as a **multi-agent bandit** and a \"coordinator\" aims to identify the best arm [3].\n\n[3] Shi, C., Xu, H., Xiong, W., & Shen, C. (2021). (Almost) Free Incentivized Exploration from Decentralized Learning Agents. arXiv preprint arXiv:2110.14628.\n\nThe route recommendation problem may be understood from different perspectives. **Yet, I don't think it can be appropriately modeled without considering these two levels of agents (platform and travelers) independently**. Besides, I also recommend the authors to think about the goal of the platform and the recommendation mechanism (recommend personalized route? would all of the travelers follow the recommendation) more carefully.  \n\n**3. Algorithm and regret bound**. It is shown that the congested bandit problem can be reduced to an MDP problem. After this reduction, the overall structure algorithm, as well as the procedure for bounding the regret, could directly follow from the results in [4].  I don't think this paper contributes to this classic problem substantially with new insights in the proof of Theorem 1. \n\n[4] Jaksch, T., Ortner, R., & Auer, P. (2010). Near-optimal Regret Bounds for Reinforcement Learning. Journal of Machine Learning Research, 11(4).\n\nTheorem 2 then provides the regret bound of the proposed algorithm in routing problems. Here the traffic network is defined as a graph $G = (V, E)$. As far as I'm concerned, the regret bound provided in Theorem 2 cannot address how the regret grows clearly. In the graph, the number of nodes, edges and paths (V, E and K) are not totally independent. Specifically, K relies on V and E with a typically expoential relationship. A formula as in Theorem 2 could provide the regret bound of any specific case, yet an overall picture is more desirable. This may be carried out on a graph with a special structure that can we can establish a the relationship between V, E and K explicitly (e.g., a grid).  \n\nMinor issue: I don't suggest to \"use the V and E to denote both the edge and vertex sets as well as their sizes\", which could be extremely confusing. If the authors still want to make this simplification, then this important statement should at least be moved to the main body of the paper.\n\nThe congested bandit model is also extended the contextual version. I didn't check the details of the proof in the Appendix for this section. My feeling in general is that it is not that easy to analyze the regret bounds, nevertheless, as contextual bandits and contextual MDP are all well-studied topics, the technical novelty is still not significant. \n", "summary_of_the_paper": "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. ", "summary_of_the_review": "The overall assumption in the proposed bandit model is that the reward of an arm relies on the number of times it was played in the past. I recommend rejecting this paper in a large part because:\n1. This setting cannot address the traffic routing problem which motivated the study.\n2. Compared with existing bandit models which take history into consideration, the major difference in this paper is that it considers a short-term reset, which is not a significant modification.\n3. The technical contribution is not substantial, as the overall structure of the algorithm and the corresponding regret analysis follows directly from other papers with limited new insights.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Y0E8yDus7r-", "reviewer": "Reviewer_kNab", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: The idea in this paper is novel and practical. I believe that the described traffic recommendation is popular in industry, also the theoretical formulation is non-trivial. The content in this paper is substantial. Two bandit settings are well-discussed including almost every possible raised problem. There are still minor places that could be improved, see below.\n\nWeaknesses: (i) there is a constant $c$ in each proposed theorem, I note that the authors claim that the value of $c$ is independent of any parameter and could change from line to line. However, I have no clue how the value of $c$ is scaled in each theorem, which makes the results less informative, and since the regrets highly depends on $c$, more discussions on what $c$ looks like or how to potentially pick $c$ for each theorem is favorable;\n(ii) in algorithm 1 CARMAB, in the equation of empirical reward estimate, should $a_t$ and $j_t$ in the numerator be $a_\\tau$ and $j_\\tau$?\n(iii) in the related work section, I would like to know more about differences between existing works and the paper. For example how the work Pike-Burke & Grunewalder (2019) differs from the paper? Current version is not clear to me, like what is instantaneous regret and how it differs from the proposed regret? Is their model formulation the same as the proposed?", "summary_of_the_paper": "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.\n\nThe 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.\n\nThen 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.", "summary_of_the_review": "I would vote for acceptance of this paper. I believe the idea is novel and practical, also theoretically non-trivial. The content in this paper is substantial. Still there could be some improvable weaknesses, see above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QmYBhBCE5hc", "reviewer": "Reviewer_otHr", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\nA new bandit model in which arm rewards depend on a past window of actions. \n\nSharper regret bounds compared to UCLR2 due to the additional structure imposed on arm rewards. \n\nTechniques used to analyze regret under unknown stochastic contexts are sufficiently novel.\n\nWeaknesses:\n\nA niche problem formulation. The current formulation does not truly capture congestion models for traffic routing platforms or other practical routing problems. \n\nThe structure of the optimal policy (when mean rewards are known) needs to be better understood. \n\nNo lower bounds on regret.\n\nProposed algorithms are somewhat trivial extensions of UCLR2 and LinUCB.\n\nContextual regret analysis is performed on multivariate Gaussian distributions only. \n\nExperiments lack adequate comparison, especially comparisons with other MDP-based RL approaches.\n", "summary_of_the_paper": "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.\n", "summary_of_the_review": "This paper proposes a new theoretical bandit model called congested bandits. While there is some novelty in problem formulation, algorithm, and regret analysis, overall, the paper does not adequately address the problem of congestion in real-world routing problems. \n\nIn online routing problems, congestion will depend on many other factors such as the exact time of recommendation, speed of the vehicle, etc. One way to relax the current assumption is to assume that the current reward depends on a weighted average of the number of times an arm is played in the past (with decaying weights). This paper proposes a niche theoretical bandit model; however, its practical significance is not clear. \n\nIt is not clear how the non-increasing nature of f_cong affects the regret analysis. Does this property have any effect on regret bounds? Is it used as a part of regret analysis to prove sharp bounds? What happens when f_cong is not non-increasing? \n\nThe form of the optimal policy when mean rewards are known deserves more discussion. Is the optimal policy an index policy? Is it a threshold-type policy? \n\nPlease compare with other methods, like UCLR2 in experiments.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "PL2xBUzuct9", "reviewer": "Reviewer_w1p9", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: This paper raises a new interesting problem, and proposed solid algorithms and derived theoretical analysis on the upper bounds. The results seem to be optimal from my point of view.\n\nHowever, this paper does not have enough novelty and theoretical depth for getting an accept.\n\n1. The problems of congested bandits in the paper seem trivial for me. For instance, in the congested bandits, there are actually $K\\Delta$ numbers or expected rewards we need to learn from the environment. In the classical UCB algorithms, we only need to replace the value $K$ in the confidence intervals to $K\\Delta$, and do simple modifications on the pulling strategy, we should be able to get regret upper bounds $\\tilde{O}(\\sqrt{K\\Delta})$ simply. Thus, I do not see enough theoretical novelty from this paper. The other cases have the similar issue. \n\n2. It is better to have results on the lower bounds, without which, it is hard to say the results of this paper are good enough. The authors should explain more why the lower bounds are missing.", "summary_of_the_paper": "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. \n\nThe authors proposed new algorithms for the above settings and derived regret upper bounds similar to those of MAB or linear contextual bandits. \n\nTo 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})$.\n\nThe authors also conducted numerical simulations to confirm the above theoretical results.\n", "summary_of_the_review": "This paper proposed an interesting question, but the algorithms and techniques used in this paper lack enough novelty for being accepted by the conference. Thus, I tend to vote a reject. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a new structured bandit problem called congested bandits, where the expected reward for an arm is a decaying function of how many times it has been played recently. This model aims to address problems such as route recommendation, in which recommended routes tend to get congested (hence yield lower rewards). Different from prior work on bandits with non-stationary reward distributions, the effect of congestion in this model resets after Delta time steps. The authors show that this problem can be formulated as a structured MDP and propose a variant of UCRL2 that learns to recommend the optimal arm for each congestion state. They show that the proposed algorithm achieves a policy regret bound that significantly improves upon UCRL2. They also propose a variant of their algorithm tailored for the linear stochastic contextual bandit setup with the associated analysis.

Unfortunately, this is a rather niche problem formulation and it fails to truly capture congestion models for traffic routing platforms (or other practical routing problems) which serve as the main motivation for the paper.  Moreover, the novelty is limited: the setting is very close to existing non-stationary bandit models and the proposed algorithms are straightforward extensions of existing strategies. A possible way for supporting the novelty of the setting could be to improve its theoretical understanding through a lower bounds analysis, which is currently lacking from the paper. Although this paper contains interesting and well-articulated ideas, contributions are not sufficient.
Decision: Reject