summaries: In this submission a routing problem is studied. In the considered model with each edge of the given graph a congestion function is associated that specifies the congestion depending on the current load of the edge. Then cars have to be routed through the network where each car has a source and a destination and one aims at choosing a path from the source to the destination with the smallest total congestion. However, the congestion functions of the edges are a priori unknown and hence one cannot trivially use a shortest path algorithm. Instead one gains information about the congestion functions only by routing the cars. When a car is routed one observes for each edge on its path the current congestion up to some random additive term. These observations can then be used for future routing decisions. This work introduces an interesting generalization of stochastic combinatorial semi-bandits for routing in a static graph. The main differences are: (1) the expected loss of an edge e is f_e(x^t_e) where the flow x^t_e is revealed at the beginning of each round (for each edge) and f_e is an unknown Lipschitz function (with known Lipschitz constant); (2) the regret is dynamic, computed against the sequence of optimal paths. When f_e is a constant function for each edge, then we recover a version of the stochastic combinatorial semi-bandit. The paper uses the bandit learning framework to study the online learning problem for routing in a city network . After each routing decision, the learning agent observes the actual delay on each edge, which is given by the congestion function on the given flow plus a random noise, and the reward is the total delay on all edges. The paper proposes a learning algorithm similar to the UCB approach, provide the regret bound result, and conduct simulations on the New York City network to verify performance of the algorithm. 
abstractText: We consider the problem of routing users through a network with unknown congestion functions over an infinite time horizon. On each time step t, the algorithm receives a routing request and must select a valid path. For each edge e in the selected path, the algorithm incurs a cost ce = fe(x t e) + η t e, where x t e is the flow on edge e at time t, fe is the congestion function, and η e is a noise sample drawn from an unknown distribution. The algorithm observes ce, and can use this observation in future routing decisions. The routing requests are supplied adversarially. We present an algorithm with cumulative regret Õ(|E|t), where the regret on each time step is defined as the difference between the total cost incurred by our chosen path and the minimum cost among all valid paths. Our algorithm has space complexity O(|E|t) and time complexity O(|E| log t). We also validate our algorithm empirically using graphs from New York City road networks.
references.authors: Baruch Awerbuch Robert D Kleinberg
references.title: Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches
references.venue: In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing,
references.authors: Baruch Awerbuch Yossi Azar Amir Epstein
references.title: The price of routing unsplittable flow
references.venue: In Proceedings of the 37th Annual ACM Symposium on Theory of Computing,
references.authors: Zahy Bnaya Ariel Felner Solomon Eyal Shimony
references.title: Canadian traveler problem with remote sensing
references.venue: IJCAI
references.authors: Anthony Chen Zhaowang Ji
references.title: Path finding under uncertainty
references.venue: Journal of Advanced Transportation,
references.authors: Caspar Chorus
references.title: Regret theory-based route choices and traffic
references.venue: equilibria. Transportmetrica,
references.authors: George Christodoulou Elias Koutsoupias
references.title: The price of anarchy of finite congestion games
references.venue: In Proceedings of the 37th Annual ACM Symposium on Theory of Computing,
references.authors: Gabriel de Oliveira Ramos Bruno Castro da Silva Ana L.C. Bazzan
references.title: Learning to minimise regret in route choice
references.venue: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems,
references.authors: Mo Dong Qingxi Li Doron Zarchy Philip Brighten Godfrey Michael Schapira
references.title: PCC: rearchitecting congestion control for consistent high performance
references.venue: In 12th USENIX Symposium on Networked Systems Design and Implementation,
references.authors: Mo Dong Tong Meng Doron Zarchy Engin Arslan Yossi Gilad Brighten Godfrey Michael Schapira
references.title: PCC vivace: Online-learning congestion control
references.venue: 15th USENIX Symposium on Networked Systems Design and Implementation,
references.authors: András György Tamás Linder Gábor Lugosi György Ottucsák
references.title: The on-line shortest path problem under partial monitoring
references.venue: J. Mach. Learn. Res.,
references.authors: Junchen Jiang Rajdeep Das Ganesh Ananthanarayanan Philip A. Chou Venkat N. Padmanabhan Vyas Sekar Esbjorn Dominique Marcin Goliszewski Dalibor Kukoleca Renat Vafin Hui Zhang
references.title: Via: Improving internet telephony call quality using predictive relay selection
references.venue: In Proceedings of the ACM SIGCOMM 2016 Conference,
references.authors: Junchen Jiang Shijie Sun Vyas Sekar Hui Zhang
references.title: Pytheas: Enabling data-driven quality of experience optimization using group-based exploration-exploitation
references.venue: 14th USENIX Symposium on Networked Systems Design and Implementation,
references.authors: Branislav Kveton Zheng Wen Azin Ashkan Hoda Eydgahi Brian Eriksson
references.title: Matroid bandits: Fast combinatorial optimization with learning
references.venue: In Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence,
references.authors: Keqin Liu Qing Zhao
references.title: Adaptive shortest-path routing under unknown and stochastically varying link states. In 10th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt)
references.authors: Evdokia Nikolova David R. Karger
references.title: Route planning under uncertainty: The canadian traveller problem
references.venue: Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence,
references.authors: Evdokia Nikolova Jonathan A. Kelner Matthew Brand Michael Mitzenmacher
references.title: Stochastic shortest paths via quasi-convex maximization
references.venue: Algorithms - ESA
references.authors: Christos H. Papadimitriou Mihalis Yannakakis
references.title: Shortest paths without a map
references.venue: Theoretical Computer Science,
references.authors: Tim Roughgarden Éva Tardos
references.title: How bad is selfish routing
references.venue: J. ACM,
references.authors: Aleksandrs Slivkins
references.title: Introduction to multi-armed bandits
references.venue: arXiv preprint arXiv:1904.07272,
references.authors: Mohammad Sadegh Talebi Zhenhua Zou Richard Combes Alexandre Proutière Mikael Johansson
references.title: Stochastic online shortest path routing: The value of feedback
references.venue: IEEE Trans. Autom. Control.,
references.authors: Jinkai Zhou Xuebo Lai Joseph Chow
references.title: Multi-armed bandit on-time arrival algorithms for sequential reliable route selection under uncertainty
references.venue: Transportation Research Record Journal of the Transportation Research Board, 2673:673–682,
references.authors: Zhenhua Zou Alexandre Proutière Mikael Johansson
references.title: Online shortest path routing: The value of information
references.venue: In American Control Conference,
sections.text: t e) + η t e, where x t e is the flow on
  edge e at time t, fe is the congestion function, and ηte is a noise sample drawn from an unknown distribution. The algorithm observes cte, and can use this observation in future routing decisions. The routing requests are supplied adversarially. We present an algorithm with cumulative regret Õ(|E|t2/3), where the regret on each time step is defined as the difference between the total cost incurred by our chosen path and the minimum cost among all valid paths. Our algorithm has space complexity O(|E|t1/3) and time complexity O(|E| log t). We also validate our algorithm empirically using graphs from New York City road networks.
sections.heading: 1 INTRODUCTION
sections.text: Modern navigation applications such as Google Maps and Apple Maps are critical tools in large scale mobility solutions that route billions of users from their source to their destination. In order to be effective, the application should be able to accurately estimate the time required to traverse each road segment (edge) along the user route in the road network (graph): we call this the cost of the edge. In general, the cost of an edge also depends on the current traffic level (the flow) on the edge. Furthermore, costs may scale differently on different edges: a highway can tolerate more traffic than a small residential street. We model this using congestion functions that map traffic flows to edge costs.
  Usually, cost information is not readily available to the routing engine and can only be inferred indirectly. For example, this can be done using location pings from vehicles, or with loop detectors that record when vehicles cross a particular marker. All realistic methods of measuring the cost of an edge (such as those above) require the presence of a vehicle that reports this information back to the routing platform. In this paper, we assume that whenever a vehicle traverses an edge, we observe the time spent on the edge. We can then use this observation in future routing decisions. This induces a natural exploration/exploitation trade-off: we may wish to send vehicles on underexplored routes, even if those routes currently seem suboptimal.
  In this paper, we propose a learning model for congestion-aware routing, and present an algorithm which seeks to minimize the total driving time across all vehicles. Our algorithm applies to arbitrary networks and arbitrary (Lipschitz-continuous) congestion functions, even when observations are noisy. The algorithm is also robust to changes in traffic conditions in a strong sense: we show that even when request endpoints are chosen adversarially and even when traffic congestion on the edges is updated adversarially between requests, our algorithm learns an optimal routing policy.
sections.heading: 1.1 MODEL
sections.text: Consider a directed graph (V,E). Each edge e has a deterministic and fixed (but unknown) congestion function fe : R≥0 → R≥0. We assume each fe is L-Lipschitz continuous and nondecreasing, with L known. For simplicity, we also assume that fe(0) = 0 for all e ∈ E (if not, we can simply translate and extend the function appropriately).
  We consider an infinite horizon of time steps, starting from t = 0. At each time t, a new car arrives. An adversary tells us the current amount of flow on each edge, and the source and destination of the new car. Let xte be the flow on edge e at time t and let Pt be the set of paths between the source and destination for the time t arrival. Let xtmax = maxe,t x t e. We must choose how to route the car, i.e., we must select a path pt ∈ Pt. Based on our choice of pt, we incur a cost based on the flow and the congestion functions on the edges in our chosen path:
  ct = ∑ e∈pt fe(x t e)
  For each e ∈ pt, we observe cte = fe(xte) + ηte, where ηte is a random variable with expectation 0. The distribution of ηte is unknown, and can vary between edges and time steps. The distributions can be correlated across edges, as long as for a given edge, all the individual samples (i.e., η1e , η 2 e , . . . ) are independent. We assume that there exists β such that ηte ∈ [−β/2, β/2] for all edges e and times t, and that β (or an upper bound on β) is known.
  The optimal cost at time t is c∗t = min
  p∈Pt ∑ e∈p fe(x t e)
  so the regret of our algorithm over the first t time steps is
  Rt = t∑ r=1 E[ct − c∗t ]
  where the expectation is over the randomness in the noise samples. Note also that we do not include the noise we observe in the objective function, since the noise has expectation 0.
  Any algorithm with sublinear regret can be said to learn an optimal routing policy: if Rt = o(t), then E[ct− c∗t ] must shrink as t goes to infinity, i.e., the difference between our algorithm’s cost and the optimal cost must go to 0 on average.1 In this paper, we give an algorithm with regret Õ(t2/3).
sections.heading: 1.2 OUR CONTRIBUTION
sections.text: Our main result is the following theorem:
  Theorem 1.1. The expected regret of Algorithm 1 after t time steps is Rt = O ( t2/3 · |E| log xtmax(β √ log t+ xtmaxL) ) The space complexity and time complexity on time step t areO(|E|t1/3 log xtmax) andO ( |E|(log t+
  log log xtmax) + SP(|E|, |V |) ) , respectively.
  Here SP(|E|, |V |) denotes the time complexity of computing the shortest path between two vertices in a graph with nonnegative weights. For example, this can be done by Dijkstra’s algorithm in time O(|E|+ V log V ). We also validate our algorithm’s performance using graphs from New York City road networks.
sections.heading: 1.3 RELATED WORK
sections.text: Comparison with multi-armed bandits. Perhaps the simplest model of exploration vs exploitation is the classical multi-armed bandit (MAB) problem (Slivkins, 2019). A MAB instance consists of n arms, each with an unknown but fixed distribution. At each time step, the algorithm selects an arm and observes a reward drawn randomly from that arm’s distribution. Several algorithms obtaining regret Õ( √ t) are known, and this is also known to be the best possible, up to logarithmic factors. 1Note that E[ct − c∗t ] may not monotonically decrease: a sublinear regret algorithm can still incur large errors sporadically, as long as the the frequency of the large errors goes to 0.
  Our routing model generalizes the MAB problem. In particular, when the graph consists of n parallel edges, the congestion functions are constant, and each edge has a single fixed noise distribution, our model reduces to the MAB problem: each edge is an arm, and the reward distribution for each edge is (the negative of) the congestion constant plus the noise distribution. Our model can be thought of as extending the MAB problem to the case where (1) each reward distribution has a parameter (in our case, the flow), and (2) the arms are edges in an arbitrary graph and their usage is constrained according to paths in the graph. We believe that routing is the most natural application of this model, but there could be other applications as well. Since our problem is strictly harder than the MAB problem, we know that regret o( √ t) is impossible. We conjecture that even regret Θ( √ t) is impossible for our problem, but leave this as an open question.
  Comparison with other routing work. Our work is also related to the body of literature on shortest paths under uncertainty, in which it is typically assumed that edge lengths follow known independent distributions. A canonical problem is to find an s–t path whose length is below a threshold L with highest probability. When the edge length distributions are Gaussian, Nikolova et al. (2006) present a quasi-polynomial time algorithm for this problem via connections to quasi-convex maximization. A related probing problem is the Canadian Traveler Problem (Nikolova & Karger, 2008; Papadimitriou & Yannakakis, 1991), where the length of an edge is revealed when we reach one of its end-points and the goal is to minimize the expected cost. There are no efficient algorithms known for this problem, except under special assumptions such as no backtracking (Bnaya et al., 2009).
  Awerbuch & Kleinberg (2004) study a conceptually similar adaptive routing problem. In their version, there is no noise in the observations, but the algorithm observes only the total cost of the path, and not the cost of each individual edge. Their model also does not have the same notion of a parametrized congestion function. Although their model is technically distinct from ours, it is noteworthy that they also obtain a regret bound of Õ(t2/3). A number of subsequent works have also sought to apply bandit algorithms to shortest path selection problems in the domain of network signal routing (Chen & Ji, 2005; György et al., 2007; Liu & Zhao, 2012; Zou et al., 2014; Talebi et al., 2018). Moreover, there is a long line of other works broadly dealing with regret minimization in Internet routing and congestion control settings (Dong et al., 2015; 2018; Jiang et al., 2016; 2017; Talebi et al., 2018).
  Similar works apply bandit algorithms to shortest path selection have also been applied to traffic route planning (Chorus, 2010; de Oliveira Ramos et al., 2017). However, these works differ from ours in that they do not consider the more general congestion functions that we consider in our model. A more recent work (Zhou et al., 2019) considers a similar routing problem, labeled the Multi-Armed Bandit On-Time Arrival Problem. In this setting, regret is quantified in terms of ontime arrival reliability, and the arms are joint route and departure times. Kveton et al. (2014) also study (among other applications) a routing setting in the context of matroid bandits, but this work also assumes static edge costs and does not factor in congestion.
  Routing in the presence of congestion functions has been studied in the context of selfish routing Roughgarden & Tardos (2002) and in the atomic congestion games setting Awerbuch et al. (2005); Christodoulou & Koutsoupias (2005). The difference from our setting is that the congestion games model and selfish routing models assume drivers have full information about the costs in the network and route themselves on an optimal path. In our setting costs are learned as time progresses and there is a centralized routing control as given by navigation applications.
sections.heading: 2 DESCRIPTION OF THE ALGORITHM
sections.text: In this section, we define and give intuition for our algorithm for learning an optimal routing policy.
sections.heading: 2.1 INTUITION BEHIND THE ALGORITHM
sections.text: On each step, the algorithm uses past observations to form an estimate for the cost of each edge at the current flow, i.e., an estimate for fe(xte). It then selects the shortest path according to these estimated costs.
  The heart of the algorithm is the cost estimation scheme. There are two sources of error in this estimation: we may not have observed this exact flow before (type 1 error), and noise (type 2 error). For type 1 error, suppose all the observations we use are based on flows y such that |y − xte| ≤ ε. Then Lipschitz continuity implies that |fe(y)− fe(xte)| ≤ εL, and so if ε is small, this aspect of our estimation should be accurate.
  However, we do not actually observe fe(y): instead, we observe fe(y) + ηy , where ηy is a random noise term with expectation 0. Even if we have observed the exact flow xte before, this noise will prevent us from having a perfect estimate. However, the more observations we use to form our estimate, the less impact the noise has: we can use Hoeffding’s Inequality to show that | ∑ y ηy| goes to 0 quickly as the number of observations grows, and thus our type 2 error shrinks. But as we increase the number of observed flows y that we use (for a fixed time step), we also (in general) increase the maximum distance maxy |y − xte|. Concretely, if k(ε, x) is the number of observations based on flows within ε of x, then k(ε, x) is weakly increasing with ε. This is diametrically opposed to our plan for the type 1 error.
  In order for the average error to approach 0 as t increases, we will have to carefully manage this tradeoff. We will need to ensure that the number of observations we use for estimation tends to infinity, but also that the maximum distance tends to 0. Intuitively, this should be possible: if observations are somewhat uniformly distributed across edges and across the flow spectrum, then we should have Θ(t) observations per edge and Θ(tε/xtmax) observations on every interval of size ε (treating |E| as a constant here). Setting ε to be something like Θ(t−1/2) would lead to Θ( √ t/xtmax) observations being used for each estimation with a maximum distance of Θ(t−1/2), which fits our requirements.
  Observations are of course not guaranteed to be uniform, and can even be adversarial. For example, suppose we have observed many flows less than 1 on some edge e, but no flows above 1. When estimating the cost of a flow less than 1, we are in good shape (if those observations are uniformly distributed, say). But suppose we are asked to estimate the cost for flow 2: we may incur a large estimation error, since we have no information about that portion of the flow spectrum.
  But our lack of information also implies that so far we have not incurred any error in that part of the flow spectrum, since we have never used it! The more we use part of the flow spectrum on a given edge (i.e., our chosen path used that edge at a flow in that range), the more error we incur, but the more we learn. Thus we will need an analysis that is decomposable across edges and across the flow spectrum: for each interval I , we need to bound our cumulative error over all estimation queries that fall within that interval as a function of the length of the interval and the number of such queries.
  There is one more complicating factor: what if we consistently overestimate the cost of a particular flow, so that we never use it? Then we may repeatedly incur a large error from that flow, without ever learning about it. For this reason, we will want to ensure that with high likelihood, all of our estimates are underestimates: this will allow us to bound the regret on a given time step in terms of the estimation error only on edges in the path that we used.
sections.heading: 2.2 OUR COST ESTIMATION SCHEME
sections.text: The cost estimation works roughly as follows. The algorithm maintains a “bucketing” system for each edge, inspired by hashtables. The interval [0, xte,max] is partitioned into a set of intervals, with each interval being a “bucket”. Whenever we observe a new flow, we identify which bucket that flow falls into, and use all the observations in that bucket to estimate the cost. (We also subtract a term proportional to √ log t in order to ensure that we get an underestimate with high probability; this is similar to the Upper Confidence Bound algorithm for multi-armed bandits.) We then observe the resulting cost for this flow (for this edge), and insert it into the bucket. If we observe a flow that falls outside of our bucketing system, we create a new depth 0 bucket so that the observed flow falls into our new bucket.
  If the number of elements in the bucket surpasses a certain threshold, we split it into two new buckets (whose associated intervals are equal length). The threshold depends on the depth (i.e., how many times one of its ancestors was split). We denote the “lifetime” of a bucket at depth m by and we denote it by h(m). Our analysis will be “decomposable” across buckets: we will bound the total error any single bucket of depth m can contribute over the course of its lifetime.
  Let bte be the bucket we used for estimating the cost of edge e at time t. The smaller the interval associated with this bte, the smaller the error of type 1: if our estimation only uses observed flows y within this interval, and the interval has length ε, then the type 1 error is at most εL, since our target flow xte is also in the interval. This incentivizes us to make h(m) small, so that we can more quickly we get to buckets with small interval lengths. If we only cared about type 1 error (i.e., if there were no noise) choosing h(m) = 1 would be optimal.
  On the other hand, the more observations stored in bte, the smaller type 2 error. This incentivizes us to make h(m) large, so that each bucket contains a large number of observations for a larger portion of its lifetime. If we only cared about type 2 error (i.e., if fe were constant), choosing h(m) = ∞ would be optimal. This is exactly the tradeoff we discussed in Section 2.1. Eventually, h(m) = 22m will give us the best regret bound.
sections.heading: 2.3 DEFINING THE ALGORITHM
sections.text: Algorithm 1 provides pseudocode for our algorithm. We use Be to denote the entire bucketing system for edge e. We treat Be as a set, whose elements are “buckets”. Each bucket b supports the following operations:
  |b| → returns the number of (flow, cost) pairs stored in b dom(b)→ returns the interval [w, z] ⊆ [0,K] associated with b
  depth(b)→ returns the depth of bucket b estimate(b)→ returns the cost estimate based on the current observations stored in b
  create(m, [w, z])→ returns a new empty bucket b with dom(b) = [w, z] and depth(b) = m INSERT(b, (y, cy))→ inserts the flow y and its associated observed cost cy into b
  The first four operations will simply be numerical fields stored in b. We also assume that the create operation takes constant time and space, and that the aforementioned four fields are initialized appropriately (estimate(b) should be 0). However, we will need to implement INSERT ourselves in order to ensure that it is done in an efficient fashion (hence the differing font). In general, we will reserve the variables w, z for dom(b), y for arbitrary elements of b, and x = xte for the proposed flow on the current time step.
  To limit space usage, we will not actually “store” each relevant observation in the bucket; instead, we will simply incorporate it into the estimate field that we store. However, in the analysis, it will be useful to use “y ∈ b” to denote that a particular observation (y, cy) has been used in that bucket. For each y ∈ b, let ηy denote the noise sample associated with this observation. Note that ηy is not known to the algorithm; we will simply use this notation in our analysis. Also, let len(dom(b)) denote the length of the domain, i.e., z − w if dom(b) = [w, z]. We can think of the bucketing system in terms of binary trees. Each bucket of depth 0 is a “root”, and whenever we split a bucket, we create two “children”. Thus Be is essentially a forest of binary trees, where each node represents a bucket. Any bucket b ∈ Be has exactly one ancestor of depth 0.
sections.heading: 3 EXPERIMENTS
sections.text: In this section, we empirically validate the algorithm’s performance on graphs from New York City road networks. We first describe the methodology, and then reflect on the results.
sections.heading: 3.1 METHODOLOGY
sections.text: We used two different graphs, corresponding to different regions within New York City. Graph 1 consisted of 303 vertices and 657 edges, and Graph 2 consisted of 429 vertices and 1204 edges.Congestion functions with domain [0, 1] were generated randomly for each run of the algorithm, with each congestion function consisting of three pieces of slope chosen uniformly from [0, 1]. Uniform noise distributions were used for all runs, with varying values of β. The algorithm was initialized with L = 1 and α = 2β2. On each time step, the following steps were performed:
  1. Independently sample a uniformly random flow xte in [0, 1] for each edge e.
  Algorithm 1 Algorithm for learning an optimal social routing policy. 1: function ROUTINGALGORITHM(E,L, α, h) 2: for each e ∈ E do 3: Be ← {create(0, [0, 1])} . Start with a single bucket of depth 0 and constant length 4: for each t ∈ N>0 do 5: xte ← proposed flow on edge e 6: for each e ∈ E do 7: ute ← ESTIMATEEDGECOST(xte, Be, L, α) 8: pt ← arg minp∈Pt ∑ e∈p u t e
  9: selectRoute(pt), observe cost cte ∀e ∈ pt 10: for each e ∈ pt do 11: UPDATEBUCKETS(xte, Be, c t e, h)
  1: function ESTIMATEEDGECOST(x,B,L, α, t) 2: if ∃b ∈ B s.t. x ∈ dom(b) and |b| > 0 then 3: return max ( 0,estimate(b)− √ |b|−1 ln tα ) 4: else 5: return 0 1: function UPDATEBUCKETS(y, cy, B, h) 2: if ∃b ∈ B s.t. y ∈ dom(b) then . Insert our observation into the corresponding bucket 3: INSERT(b, (y, cy)) 4: m← depth(b) 5: if |b| > h(m) then . Split the bucket if it is too big 6: [w, z]← dom(b) 7: b1 ← create(m+ 1, [w, w+z2 ]) 8: b2 ← create(m+ 1, [w+z2 , z]) 9: INSERT(b1, (y, cy)) . Insert the observation into new buckets so they aren’t empty. 10: INSERT(b2, (y, cy)) . Type 1 error is still proportional to the domain lengths. 11: Be ← (Be \ b) ∪ {b1} ∪ {b2} 12: else . This flow does not fall into any bucket: create a new depth 0 bucket 13: ymax ← max ( ∪b∈Be dom(b)
  ) 14: b← create ( 0, [ymax, 2x]
  ) 15: Be ← Be ∪ {b}
  1: function INSERT(b, (y, cy)) 2: [w, z]← dom(b) 3: if y < w then . y 6∈ dom(b) is possible if we created b on this time step 4: uy = cy 5: else 6: uy = cy − L(y − w) 7: estimate(b)← |b| · estimate(b) + uy
  |b|+ 1 . This is a running average of {uy : y ∈ b}
  8: |b| ← |b|+ 1
  2. Independently sample a uniformly random noise term ηte ∈ [−β/2, β/2] for each edge e.
  3. Independently sample a uniformly random source and destination from the graph.
  4. Compute the path chosen pt chosen by our algorithm. 5. Compute ct−c∗t = ∑ e∈pt fe(x t e)−minp∈Pt ∑ e∈p fe(x t e) and record the cumulative regret
  Rt.
  Each run was characterized by the following parameters:
  1. Time horizon (either 100,000 or 1,000,000)
  2. The graph used (Graph 1 or Graph 2)
  3. The noise parameter β ∈ {0, .01, .02, .05, .1, .2, .5}.2
  Figure 1 shows the results of all runs.
sections.heading: 3.2 RESULTS
sections.text: All runs of the algorithm display the general behavior we would hope to see: concavity of the cumulative regret curve. Also as expected, higher noise levels lead to both larger absolute regret, and weaker concavity: learning takes longer. Most of the runs display substantial concavity within 100,000 time steps, but some the β = .5 runs (on both graphs) require closer to 200,000 steps in order for the concavity to clearly manifest.
  With regards to absolute regret, β has a dramatic effect. On the extremes, the total regret for β = 0 after 1,000,000 time steps is less than 5,000 for Graph 1 and less than 9,000 for Graph 2. (The regret for Graph 1 tends to larger, due to the graph being larger.) However, for β = .5, the regret after 100,000 time steps is already more than 12,000 and 20,000 for Graph 1 and Graph 2, respectively. If we look at the average regret for β = 0 over 1,000,000 time steps, we get <.005 and <.009 for Graphs 1 and 2, respectively. Since the expected cost of each edge on a given time step is .25 (expected flow is .5, expected slope is .5), we view this as quite good. In contrast, for β = .5, the average regret over 1,000,000 time steps is > .48 and >.88 for Graphs 1 and 2 respectively. Relative to the average edge cost of .25, we view this as quite poor. This behavior again matches our expectations.
  Finally, we note that there are many other experimental parameters that we have not included in these plots. For example: non-i.i.d flows, non-i.i.d. sources and destinations, non-i.i.d. congestion functions, congestion functions with different numbers of pieces, congestion functions with different Lipschitz constants, other noise distributions, correlated noise, and many more. We have indeed tested many of these, but due to space constraints, there is a limit to the number of plots we can include in the paper. We assure the reader that we have yet to find a parameter combination that causes unexpected behavior from the algorithm.
sections.heading: 4 CONCLUSION
sections.text: In this paper, we presented an algorithm which learns an optimal routing policy for any graph, any (Lipschitz continuous) congestion functions, and any (bounded) noise distribution, and adversarial routing requests (i.e., source, destination, and the current flow on each edge). Our algorithm has cumulative regret Õ(|E|t2/3). There are many interesting directions for future work. The first relates to the dependence on t in the regret bound. Since our problem generalizes the multi-armed bandit problem, we immediately inherit a Ω( √ t) lower bound. However, that still leaves substantial room to improve the dependence on t. It would also be interesting to improve the dependence on |E|. We have made several worstcase assumptions in this paper that are perhaps overly pessimistic: for example, neighboring edges may have correlated congestion functions, and flows do not change arbitrarily between time steps.
  On the empirical side, we evaluated our algorithm using real-world graphs, but synthetic congestion functions. Future experiments could use real data for the congestion functions as well: either by fitting a congestion function to the data, or by randomly sampling data points to simulate a congestion function.
  2With regards to the chosen range of β values, note that the expected maximum cost on each edge is .5, since the domain of each fe is [0, 1] and the expected slope of each piece is .5. Thus in some sense, β = .5 represents “as much noise as signal”, β = .2 represents “2/5 as much noise as signal”, and so on.
sections.heading: A PROOF OF THEOREM 1.1
sections.text: In this section, we prove our main theorem:
  Theorem 1.1. The expected regret of Algorithm 1 after t time steps is Rt = O ( t2/3 · |E| log xtmax(β √ log t+ xtmaxL) ) The space complexity and time complexity on time step t areO(|E|t1/3 log xtmax) andO ( |E|(log t+
  log log xtmax) + SP(|E|, |V |) ) , respectively.
  We restate the algorithm below for the reader’s convenience.
  Our first lemma upper bounds the distance between two flows associated with the same bucket.
  Lemma A.1. Consider an arbitrary edge e and bucket b ∈ Be, let (x, cx) ∈ b, and let y ∈ dom(b) (but not necessarily y ∈ b). If m = depth(b), then |x− y| ≤ xtmax/2m−1.
  Proof. Let b′ be the unique depth 0 ancestor of b. If b has depth m, then dom(b) must have length exactly len(dom(b′))/2m, since the domain length is halved whenever the depth is incremented. Since len(dom(b′)) ≤ xtmax, we have len(dom(b)) ≤ xtmax/2m. If x ∈ dom(b), then |x − y| ≤ xtmax/2m and we are done. If not, then x must have been inserted on the time step that b was created. Let b′′ be the parent of b. In this case, x ∈ dom(b′′). By construction, dom(b) ⊂ dom(b′), so we have x, y ∈ dom(b′′). Finally, since b′ has depth m − 1, len(dom(b′′)) ≤ xtmax/2m−1, so |x− y| ≤ xtmax/2m−1.
  Lemma A.2 is a standard concentration equality due to Hoeffding. Lemma A.3 is essentially a restatement of Hoeffding’s Lemma for our setting.
  Algorithm 1 Algorithm for learning an optimal social routing policy. 1: function ROUTINGALGORITHM(E,L, α, h) 2: for each e ∈ E do 3: Be ← {create(0, [0, 1])} . Start with a single bucket of depth 0 and constant length 4: for each t ∈ N>0 do 5: xte ← proposed flow on edge e 6: for each e ∈ E do 7: ute ← ESTIMATEEDGECOST(xte, Be, L, α) 8: pt ← arg minp∈Pt ∑ e∈p u t e
  9: selectRoute(pt), observe cost cte ∀e ∈ pt 10: for each e ∈ pt do 11: UPDATEBUCKETS(xte, Be, c t e, h)
  1: function ESTIMATEEDGECOST(x,B,L, α, t) 2: if ∃b ∈ B s.t. x ∈ dom(b) and |b| > 0 then 3: return max ( 0,estimate(b)− √ |b|−1 ln tα ) 4: else 5: return 0 1: function UPDATEBUCKETS(y, cy, B, h) 2: if ∃b ∈ B s.t. y ∈ dom(b) then . Insert our observation into the corresponding bucket 3: INSERT(b, (y, cy)) 4: m← depth(b) 5: if |b| > h(m) then . Split the bucket if it is too big 6: [w, z]← dom(b) 7: b1 ← create(m+ 1, [w, w+z2 ]) 8: b2 ← create(m+ 1, [w+z2 , z]) 9: INSERT(b1, (y, cy)) . Insert the observation into new buckets so they aren’t empty. 10: INSERT(b2, (y, cy)) . Type 1 error is still proportional to the domain lengths. 11: Be ← (Be \ b) ∪ {b1} ∪ {b2} 12: else . This flow does not fall into any bucket: create a new depth 0 bucket 13: ymax ← max ( ∪b∈Be dom(b)
  ) 14: b← create ( 0, [ymax, 2x]
  ) 15: Be ← Be ∪ {b}
  1: function INSERT(b, (y, cy)) 2: [w, z]← dom(b) 3: if y < w then . y 6∈ dom(b) is possible if we created b on this time step 4: uy = cy 5: else 6: uy = cy − L(y − w) 7: estimate(b)← |b| · estimate(b) + uy
  |b|+ 1 . This is a running average of {uy : y ∈ b}
  8: |b| ← |b|+ 1
  Lemma A.2 (Hoeffding’s Inequality). Let X1, . . . , Xn be independent random variables each supported on an interval of length β > 0 and let X̄ = 1n ∑n i=1Xi. Then for any ε > 0,
  Pr[|X̄ − E[X̄]| > ε] ≤ exp (−2nε2
  β2 ) Lemma A.3. Fix an edge e and a bucket b ∈ Be. With probability at least 1− δ,
  ∣∣∣∣ 1|b|∑ y∈b ηy ∣∣∣∣ ≤ β √ ln δ−1 2|b|
  Proof. If β = 0, the claim is trivially true. Otherwise, since E[ηy] = 0, and all ηy are independent for a given edge, Hoeffding’s Inequality gives us
  Pr ∣∣∣∣ 1|b|∑ y∈b ηy ∣∣∣∣ > β √ ln δ−1 2|b|  ≤ exp(β2 ln δ−1 2|b| · −2|b| β2 ) = δ
  as required.
  We will now start the process of bounding the costs incurred by our algorithm. Moving forward, we will need to separately handle the time steps where xte does not fall into any bucket we have, and we must create a new depth 0 bucket (on line 14 of UPDATEBUCKETS). Let Te be the set of time steps t where (1) e ∈ pt, (2), ∃r < t such that e ∈ pr (i.e., this is not the first we are using this edge), and (3) we do not create a new depth 0 bucket. The reader can think of Te as the set of time steps when edge e is used in a “normal” way.
  Throughout the analysis, for each e ∈ E and time t, let bte denote the bucket that is used on line 3 of ESTIMATEEDGECOST, if such a bucket exists. For each t ∈ Te, we are guaranteed that bte exists, since Condition 3 above ensures that there exists b ∈ Be with xte ∈ dom(b), and Condition 2 ensures that |b| > 0. Throughout the proof, we will use |bte| to denote the number of observations in the bucket on that time step, before inserting the new element (if one is inserted).
  Also, for each e ∈ E and time t, let ζe(t) be the indicator variable that | 1|bte| ∑ y∈bte
  ηy| ≤√ |bte|−1 ln tα = β √ |bte|−1 ln tα/β
  2 . (If bte does not exist, let ζe(t) = 1). Note that by Lemma A.3, Pr[ζe(t) = 1] ≥ 1− t−α/β 2 .
  The next lemma states that as long as ζe(t) = 1, our algorithm’s estimate ute will always be an underestimate of the true cost fe(xte). Lemma A.4. Fix a time t and edge e. If ζe(t) = 1, then fe(xte) ≥ ute.
  Proof. If ute = 0, then trivially u t e ≤ fe(xte). Thus assume ute > 0. This implies t ∈ Te, and so bte exists. For each y ∈ bte, define uy as in the INSERT function in Algorithm 1, and let [w, z] = dom(bte). For brevity, let x = x t e. Note that x ≥ w and thus fe(x) ≥ fe(w). Also recall that cy = fe(y) + ηy by definition. We first claim that fe(x) ≥ uy − ηy for all y ∈ bte. Case 1: w > y. Then x > y, so we have uy − ηy = cy − ηy = fe(y) ≤ fe(x), as required. Case 2: y ≥ w. Then uy−ηy = cy−ηy−L(y−w) = fe(y)−L(y−w). Because fe is L-Lipschitz, we have fe(y) ≤ fe(w) + L(y − w), so
  uy − ηy = fe(y)− L(y − w) ≤ fe(w) + L(y − w)− L(y − w) ≤ fe(x)
  Therefore
  fe(x) ≥ 1 |bte| ∑ y∈bte (uy − ηy)
  = 1 |bte| ∑ y∈bte uy − 1 |bte| ∑ y∈bte ηy
  ≥ 1 |bte| ∑ y∈bte uy − 1 |bte| ∣∣∣∣ ∑ y∈bte ηy ∣∣∣∣ Since ζe(t) = 1 by assumption, we get
  fe(x t e) ≥
  1 |bte| ∑ y∈bte uy − √ |bte|−1 ln tα = estimate(bte)− √ |bte|−1 ln tα
  Since ute > 0, we have u t e = estimate(b t e)− √ |bte|−1 ln tα. Thus fe(xte) ≥ ute, as required.
  Lemma A.5 states that if t ∈ Te and ζe(t) = 1, then our estimate ute also shouldn’t be too much more than fe(xte).
  Lemma A.5. Fix a time t ∈ Te and edge e, and let m = depth(bte). If ζe(t) = 1, then
  fe(x t e) ≤ ute +
  xtmaxL 2m−1 + 2 √ |bte|−1 ln tα
  Proof. As before, for each y ∈ bte, define uy as in INSERT, let [w, z] = dom(bte), and let x = xte for brevity. We first claim that fe(x) ≤ uy − ηy + L(x − y) for all y ∈ bte. Since x ≥ w and fe is L-Lipschitz, we have fe(x) ≤ fe(w) + L(x− w). Case 1: y ≥ w. Then fe(w) ≤ fe(y) by monotonicity, so
  fe(x) ≤ fe(y) + L(x− w) = cy − ηy + L(x− y) + L(y − w) = uy − ηy + L(x− w) ≤ uy − ηy + 21−mxtmaxL
  where the last step follows from Lemma A.1.
  Case 2: w > y.3 Then fe(w) ≤ fe(y) + L(w − y), so
  fe(x) ≤ fe(y) + L(w − y) + L(x− w) = cy − ηy + L(x− y) ≤ uy − ηy + L(x− y) ≤ uy − ηy + 21−mxtmaxL
  again using Lemma A.1 on the last step. Therefore
  fe(x) ≤ 1 |bte| ∑ y∈bte (uy − ηy + 21−mxtmaxL)
  = 21−mxtmaxL+ 1 |bte| ∑ y∈bte uy − 1 |bte| ∑ y∈bte ηy
  ≤ 21−mxtmaxL+ estimate(bte) + 1
  |bte| ∣∣∣∣ ∑ y∈bte ηy ∣∣∣∣+√|bte|−1 ln tα −√|bte|−1 ln tα Since ute = max(0,estimate(b)− √ |b|−1 ln tα), we have estimate(b)− √ |b|−1 ln tα ≤ ute.
  Also, | 1|bte| ∑ y∈bte ηy| ≤ √ |bte|−1 ln tα, since ζe(t) = 1 by assumption. Therefore
  fe(x) ≤ ute + 21−mxtmaxL+ 1
  |bte| ∣∣∣∣ ∑ y∈bte ηy ∣∣∣∣+√|bte|−1 ln tα ≤ ute + 21−mxtmaxL+ 2 √ |bte|−1 ln tα
  The next lemma is a simple bound on the maximum flows on time steps when we create a new depth 0 bucket. This will be needed later to bound the error on those time steps.
  Lemma A.6. Fix an edge e ∈ E and a time step t > 0. Let t0, . . . , tk be the time steps up to and including time t on which a new depth 0 bucket is created in Be (where t0 = 0). Then k ≤ 1 + log xtmax. Furthermore, ∑k i=1 x tk e ≤ 2xtmax.
  3This means that y is actually not in dom(bte). This only happens if y was inserted into bte on the time step when bte was created.
  Proof. Assume t0 < t1, . . . , < tk. Let yrmax = max(∪b∈Bredom(b)), where B r e denotes the set of buckets for edge e at the beginning of time step r. This is the maximum flow that falls into any bucket in Be at time r Note that yr+1max = y r max for all r 6∈ {t1, . . . , tk}. Furthermore, for r ∈ {t1, . . . , tk}, we have yr+1max = 2xre > yrmax. Therefore for each i ∈ {1, . . . , k}, yti+1max = 2x ti e > 2y ti max
  Thus for all i, j ∈ {1, k} with i ≤ j, ytjmax > 2j−i. In particular,
  ytkmax > 2 k · yt0max = 2i
  where yt0max = 1 is because we initialize Be with a single bucket corresponding to the interval [0, 1]. We know that ytk+1max = 2x tk−1 e ≤ 2xtmax, so 2k ≤ 2xtmax. Therefore |Dte| = k ≤ 1 + log xtmax. Finally, k∑ i=1 xtie = 1 2 k∑ i=1 yti+1max
  ≤ y tk+1 max
  2 k∑ i=1 1 2k−i
  ≤ y tk+1 max
  2 · 2
  ≤ 2xtmax as required.
  Lemma A.7 gives our first bound on the cumulative regret of the algorithm. This bound is quite complex, and it will take substantial work later on to show that this bound is in fact Õ(t2/3). Lemma A.7. Assume α = 2β2. Then for all t, we have
  Rt ≤ |E|xtmaxL(π2 + 18)
  6 + t∑ r=1 ∑ e∈pr ( xtmaxL 2depth(b t e)−1 + 2 √ |bte|−1 ln tα ) Proof. We first prove a lower bound on E[c∗t ], the expected cost incurred by the optimal algorithm. By definition, c∗t = minp∈Pt ∑ e∈p fe(x t e), so Lemma A.4, we have fe(x t e) ≥ ute with probability at least 1− t−α/β2 . For brevity, let δ = t−α/β2 . Since c∗t ≥ 0 always, we have
  E[c∗t ] ≥ (1− δ) · min p∈Pt ∑ e∈p ute
  Next, we prove an upper bound on E[ct], the expected cost incurred by our algorithm. Note that E[ct] = ∑ e∈pt fe(x t e) = ∑ e∈pt:t∈Te fe(x t e) + ∑ e∈pt:t6∈Te fe(x t e)
  We will first handle the first term, and then the second term. Since fe is L-Lipschitz and fe(0) = 0, we have fe(x) ≤ xtmaxL for all x ≤ xtmax. Since xte ≤ xtmax, we have fe(x t e) ≤ xtmaxL as a broad upper bound for all cases. If t ∈ Te, then Lemma A.5 implies that fe(x t e) ≤ ute+ 21−depth(b t e)xtmaxL+ 2 √ |bte|−1 ln tα with probability at least 1− δ. Also recall that
  pt = arg minp∈Pt ∑ e∈p u
  t e by definition. Thus∑
  e∈pt:t∈Te
  fe(x t e) ≤ ∑ e∈pt [ δxtmaxL+ (1− δ) ( ute + xtmaxL 2depth(b t e)−1 + 2 √ |bte|−1 ln tα )]
  ≤ δ|E|xtmaxL+ (1− δ) · min p∈Pt ∑ e∈p ute + (1− δ) ∑ e∈pt ( xtmaxL 2depth(b t e)−1 + 2 √ |bte|−1 ln tα ) ≤ δ|E|xtmaxL+ (1− δ) · min
  p∈Pt ∑ e∈p ute + ∑ e∈pt ( xtmaxL 2depth(b t e)−1 + 2 √ |bte|−1 ln tα )
  Next, for ∑ e∈pt:t 6∈Te fe(x
  t e) we have∑
  e∈pt:t6∈Te
  fe(x t e) ≤ ∑ e∈pt:t 6∈Te xte,maxL = |{e ∈ pt : t 6∈ Te}|xte,maxL
  Combining this with our upper bound on E[c∗t ], we get
  E[ct − c∗t ] ≤ |{e ∈ pt : t 6∈ Te}|xte,maxL+ |E|xtmaxL tα/β2 + ∑ e∈pt ( xtmaxL 2depth(b t e)−1 + 2 √ |bte|−1 ln tα ) Summing the second term gives us4
  t∑ r=1 |E|xrmaxL rα/β2 = |E|xtmaxL t∑ r=1 1 r2 ≤ |E|xtmaxL ∞∑ r=1 1 r2 = |E|xtmaxLπ2 6
  For the first term, we further divide time steps t 6∈ Te into (1) time steps where we create a new depth 0 bucket, and (2) time steps where we use edge e for the first time. For case (1), let Qe denote the set of these time steps. Recall that we only create a depth 0 bucket when the current flow xte does not fall into any bucket we already have. In particular, that implies it is the maximum flow we have seen on this edge: formally, t ∈ Qe implies xte = xte,max. For case (2), let ze(t) be the indicator variable which takes on value 1 if t is the first time that e is used, and 0 otherwise. Since this happens at most once per edge, we have ∑t r=1 ze(r) ≤ 1 for all e ∈ E. Therefore,
  L t∑ r=1 |{e ∈ pr : r 6∈ Te}|xre,max = L t∑ r=1 xre,max ( |{e : r ∈ Qe}|+ |{e ∈ pr : ze(r) = 1}| ) ≤ L
  t∑ r=1 |{e : r ∈ Qe}|xre + L t∑ r=1 xre,max ∑ e∈pr ze(r)
  ≤ L ∑ e∈E ∑ r≤t:r∈Qe xre + L ∑ e∈E t∑ r=1 xtmaxze(r)
  ≤ L ∑ e∈E ∑ r≤t:r∈Qe xre + |E|xtmaxL
  ≤ L ∑ e∈E 2xtmax + |E|xtmaxL (Lemma A.6)
  = 2|E|xtmaxL+ |E|xtmaxL = 3|E|xtmaxL
  Putting this all together, we get
  Rt = t∑ r=1 E[ct − c∗t ] ≤ 3|E|xtmaxL+ |E|xtmaxLπ2 6 + t∑ r=1 ∑ e∈pr ( xtmaxL 2depth(b t e)−1 + 2 √ |bte|−1 ln tα )
  = |E|xtmaxL(π2 + 18)
  6 + t∑ r=1 ∑ e∈pr ( xtmaxL 2depth(b t e)−1 + 2 √ |bte|−1 ln tα ) as required.
  Let Ste be the set of buckets associated with edge e that have existed up to and including time t, and let At(b) = {r ≤ t : e ∈ pr and bte = b} be the set of time steps that we used bucket b. We know
  4Note that we could have chosen any α ≥ 2β2 and simply obtained a different constant.
  that every time we use edge e (i.e., e ∈ pt), we use exactly one bucket bte. Thus we can rewrite the bound from Lemma A.7 as
  Rt ≤ |E|xtmaxL(π2 + 12) 6 + ∑ e∈E ∑ b∈Ste ∑ r∈At(b) ( xtmaxL 2depth(b)−1 + 2 √ |bre|−1 ln tα ) Note that we use |bre| instead of |b| in order to denote the size of the bucket on time step r specifically.
  Let Rt(b) = ∑ r∈At(b) ( 21−depth(b)xtmaxL+ 2 √ |b|−1 ln tα ) be the total regret incurred by bucket
  b, and let Rt(e) = ∑ b∈Ste
  Rt(b) be the total regret incurred by edge e. The rest of the proof is devoted to bounding Rt(e); after we have done so, we can simply sum this bound across all edges.
  We next give a brief proof of a standard inequality that will be useful to us. Lemma A.8. For all n, ∑n i=1 1 √ i ≤ 2 √ n.
  Proof. The proof is by induction n. The base case of n = 1 is trivial, so consider an arbitrary n > 1 and assume the claim holds for n− 1. Then
  n∑ i=1 1√ i = 1√ n + n−1∑ i=1 1√ i
  ≤ 2√ n+ √ n− 1
  + 2 √ n− 1
  = 2( √ n− √ n− 1) + 2 √ n− 1 = 2 √ n
  as required.
  We will now bound the maximum regret a single bucket of depth m can contribute.
  Lemma A.9. Let b ∈ Ste be a bucket with depth m. Then
  Rt(b) ≤ 4 √ h(m) ln tα + xtmaxLh(m)
  2m−1
  Proof. Substituting m = depth(b), Rt(b) is defined by
  Rt(b) ≤ xtmaxL|At(b)|
  2m−1 + 2 ∑ r∈At(b) √ |b|−1 ln tα
  Next, observe that |At(b)| ≤ h(m): |b| = 1 initially, and once |b| > h(m), we split it into two new buckets and never use it again. Thus we can rewrite the above bound to sum over the number of elements in b:
  Rt(b) ≤ xtmaxL|At(b)| 2m−1 + 2 √ ln tα |At(b)|∑ i=1 1√ i
  ≤ x t maxLh(m) 2m−1 + 2 √ ln tα h(m)∑ i=1 1√ i
  ≤ x t maxLh(m) 2m−1 + 4 √ h(m) ln tα (Lemma A.8)
  as required.
  Next, we will analyze a linear program which will be useful in bounding the total regret contributed by a single edge.
  Lemma A.10. Consider the following linear program, parameterized by t, n and k:
  max x1,...,xn∈R≥0 n∑ m=1 xm2 km (1)
  s.t. n∑ m=1 22m−3xm ≤ t
  xm ≤ 2m ∀m ∈ {1, . . . , n} Assume 0 ≤ k < 2, and let (x1, . . . , xn) be an optimal solution, and suppose xm > 0. Then for all i < m, xi = 2i.
  Proof. Suppose not, and let δ = min(xm, 2i − xi) > 0. Define a new solution (y1, . . . , yn) by yi = xi + δ 22i−3 , ym = xm − δ 22m−3 , and yj = xj for j 6∈ {i,m}.
  We first claim that y is feasible. We have ym ≥ xm − δ ≥ 0, and yi ≤ xi + δ ≤ 2i. Since yj = xj for j 6∈ {i,m}, we have 0 ≤ xj ≤ 2j for all j. Also, we have
  n∑ j=1 yj2 2j−3 = ( xi + δ 22i−3 ) · 22i−3 + ( xm − δ 22m−3 ) 22m−3 + ∑ j 6∈{i,m} xj2 2j−3
  = xi2 2i−3 + δ + xm2 2m−3 − δ + ∑
  j 6∈{i,m}
  xj2 2j−3
  = n∑ j=1 xj2 2j−3
  which must be at most t, since (x1, . . . , xn) is assumed to be feasible.
  Finally, we claim that (y1, . . . , yn) has a better objective value. We have: n∑ j=1 2kjyj − n∑ j=1 2kjxj = yi2 ki + ym2 km − xi2ki − xm2km
  = 2kixi + δ2ki
  22i + xm2
  km − δ2 km
  22m − 2kixi − 2kmxm
  = δ 2(2−k)i − δ 2(2−k)m
  Since 2 − k > 0 and m > i, we have 2(2−k)i < 2(2−k)m. Thus the above expression is strictly positive. Therefore (y1, . . . , yn) has a higher objective value, which contradicts the optimality of (x1, . . . , xn).
  For now, we are primarily interested in k = 1. Let g(t, n) denote the maximum value of Program 1 for parameters t and n, with k = 1. Lemma A.10 implies that for a fixed t, n actually does not matter, assuming it is sufficiently large: the ∑n m=1 2
  2m−3xm ≤ t constraint will be saturated by smaller values of m, so any additional variables will always have value 0. Formally, for all t, there exists nt such that g(t, nt) = g(t, n) for all n ≥ nt. Thus we can simply take n to be large enough and write g(t) = g(t, nt). For example, nt = t suffices.
  The next lemma bounds the total regret contributed each “tree”, i.e., a set of buckets that share a depth 0 ancestor. Also, at this point we will substitute in h(m) = 22m. Lemma A.11. Fix an edge e and time t. Let S ⊆ Ste be a set of buckets which all have the same depth 0 ancestor. Then ∑
  b∈S
  Rt(b) ≤ (4 √ ln tα + 2xtmaxL)g(t)
  Proof. Let xm denote the number of buckets b ∈ S of depth m. Letting h(m) = 22m, Lemma A.9 implies that
  Rt(b) ≤ 4 √ h(m) ln tα + xtmaxLh(m)
  2m−1 = (4 √ ln tα + 2xtmaxL)2 m
  Thus ∑ b∈Bje Rt(b) ≤ (4 √ ln tα + 2xtmaxL) nt∑ m=0 xm2 m
  We next claim that (x1, . . . , xm) is feasible for Program 1. We know that xm ≤ 2m, since within a single binary tree, there are at most 2m nodes of depth m. It remains to show that t ≥ ∑nt m=1 2 2m−3xm.
  Note that all buckets of depth at least 1 come in pairs: spending h(m−1) steps on a bucket of depth m− 1 creates two buckets of depth m. Thus the number of time steps we spent on buckets of depth m − 1 is exactly xm2 · h(m − 1) = 2 2m−2 xm 2 = 2
  2m−3xm. Thus the total number of time steps is bounded by
  t ≥ nt∑ m=1 22m−3xm
  as required. Therefore (x1, . . . , xm) is a feasible solution to Program 1, and ∑ b∈S Rt(b) is at most (4 √ ln tα + 2xtmaxL) times the objective value of Program 1 for (x1, . . . , xm). Since the objective value for (x1, . . . , xm) is at most the optimal objective value g(t), we have ∑ b∈S Rt(b) ≤ (4 √ ln tα + 2xtmaxL)g(t).
  We are now ready to bound the total regret contributed by a single edge.
  Lemma A.12. For all e, t, we have
  Rt(e) ≤ (1 + log xtmax)(4 √ ln tα + 2xtmaxL)g(t)
  Proof. Let S1, . . . , Sq be a partition of Ste such that each Si contains exactly one depth 0 bucket, and all buckets in Si have the same depth 0 ancestor. (i.e., each Si constitutes a single binary tree). By Lemma A.6, q ≤ 1 + log xtmax. Therefore
  Rt(e) = q∑ i=1 ∑ b∈Si Rt(b)
  ≤ q∑ i=1 (4 √ ln tα + 2xtmaxL)g(t) (Lemma A.11) = q(4 √
  ln tα + 2xtmaxL)g(t)
  ≤ (1 + log xtmax)(4 √ ln tα + 2xtmaxL)g(t)
  as required.
  We are almost done. One of our last remaining tasks is to bound g(t): the optimal objective value of Program 1.
  Lemma A.13. For all t, we have g(t) ≤ 2 8
  3 t 2/3.
  Proof. Fix a time t, and let (x1, . . . , xn) be an optimal solution to Program 1 for parameter t. Let m be the minimum integer so that ∑m i=1 2
  2i−32i > t. Then there exists i ≤ m so that xi < 2i: otherwise, ∑m i=1 2 2i−3xi = ∑m i=1 2
  2i−32i > t by assumption, which would imply that (x1, . . . , xn) is infeasible.
  Since there exists i ≤ m so that xi < 2i, Lemma A.10 implies that xi = 0 for all i > m. Therefore g(t) = ∑n i=1 2 ixi = ∑m i=1 2 ixi = ∑m i=1 2 2i.
  By definition of m, we have t ≥ ∑m−1 i=1 2 2i−32i = ∑m−1 i=1 2 3i−3 ≥ 23m−9. Therefore
  3m− 9 ≤ log t
  m ≤ 1 3 log t+ 3
  m ≤ log t1/3 + 3
  Therefore
  g(t) ≤ m∑ i=1 22i
  ≤ 4 3 22m ≤ 4 3 22 log t 1/3+6 = 4
  3 · 26 · t2/3
  = 28
  3 t2/3
  as required.
  Our last lemma analyzes space and time complexity of our algorithm. Lemma A.14. The space complexity and time complexity of Algorithm 1 on time step t are O(|E|t1/3 log xtmax) andO ( |E|(log t+log log xtmax)+ShortestPath(|E|, |V |) ) , respectively.
  Proof. For the space complexity, note that each bucket b requires a constant amount of space: it simply needs to store |b|,dom(b),depth(b), and estimate(b), each of which take constant space. Thus the space complexity is the total number of buckets at time t. In fact, we will bound |Ste|, the number of buckets that have existed at any time up to time t for edge e. As in Lemma A.12, let S1, . . . , Sq be a partition of Ste such that each Si contains exactly one depth 0 bucket, and all buckets in Si have the same depth 0 ancestor. We claim that |Si| ≤ t1/3 for all i. We will show this using Program 1, but now with k = 0 instead of k = 1:
  max x1,...,xn∈R≥0 n∑ m=1 xm (2)
  s.t. n∑ m=1 22m−3xm ≤ t
  xm ≤ 2m ∀m ∈ {1, . . . , n}
  The analysis proceeds similarly to Lemmas A.11 and A.13. Let g′(t) be the optimal objective value for Program 2 with parameter t. We claim that |Ste| ≤ g′(t). Let xm denote the number of buckets of depthm that have existed up to and including time t for this edge. Since the constraints in Program 2 are the same as in Program 1, we already showed in the proof of Lemma A.12 that (x1, . . . , xn) is feasible for Program 2. Since |Ste| = ∑n m=1 xm, we have |Ste| ≤ g′(t).
  It remains to bound g′(t). Let m be the minimum integer such that ∑m i=1 2
  2i−32i > t. Then as argued in Lemma A.13, m ≤ log t1/3 + 3. Therefore g′(t) ≤ ∑m i=1 xm ≤ ∑m i=1 2 m ≤ 2m+1, so
  g′(t) ≤ 2log t 1/3+4 = O(t1/3)
  By Lemma A.6, q ≤ 1 + log xtmax. Therefore the total number of buckets for edge e at time t is at most
  |Ste| = q∑ i=1 |Si|
  ≤ q ·O(t1/3) = O(log xtmaxt 1/3)
  and thus the total space complexity is O(|E| log xtmaxt1/3). For the time complexity, each time step involves two tasks that may take non-constant time: computing ute for each e ∈ E, and computing arg minp∈Pt ∑ e∈p u t e. Once the first task has been done, the second task can by running any shortest path algorithm on the directed graph (E, V ) where edge e has nonnegative weight ute; this takes time ShortestPath(|E|, |V |). For the first task, there are two parts that may take non-constant time. The first part is searching for a bucket b such that y ∈ b. The buckets correspond to non-overlapping intervals, so this can be done by keeping the buckets in sorted order and using binary search. This approach yields a time complexity ofO(log |Ste|) = O(log t+log log xtmax) per edge and thusO(|E|(log t+log log xtmax)) total. Note that to keep the buckets in sorted order, creating a bucket now requires us to insert it into the right place in the ordering. Using a self-balancing binary tree, this be done in time O(log |Ste|) per operation as well (and at most two buckets are created per edge per time step).
  The second part that may take non-constant time is computing ymax = max ( ∪b∈Be dom(b) ) , if applicable. If the buckets are stored in sorted order, this can be done in constant time by looking at the last bucket in the ordering. This yields the desired bound.
  We are finally ready to prove Theorem 1.1. Theorem 1.1. The expected regret of Algorithm 1 after t time steps is
  Rt = O ( t2/3 · |E| log xtmax(β √ log t+ xtmaxL) ) The space complexity and time complexity on time step t areO(|E|t1/3 log xtmax) andO ( |E|(log t+
  log log xtmax) + SP(|E|, |V |) ) , respectively.
  Proof. We have
  Rt ≤ |E|xtmaxL(π2 + 12) 6 + ∑ e∈E Rt(e) (Lemma A.7)
  ≤ |E|x t maxL(π 2 + 12) 6 + ∑ e∈E (1 + log xtmax)(4 √ ln tα + 2xtmaxL)g(t) (Lemma A.12)
  = |E|xtmaxL(π2 + 12)
  6 + |E|(1 + log xtmax)(4
  √ ln tα + 2xtmaxL) · 28
  3 t2/3 (Lemma A.13)
  Plugging in α = 2β2 as in Lemma A.7 gives us
  Rt ≤ |E|xtmaxL(π2 + 12)
  6 + |E|(1 + log xtmax)(4β
  √ 2 ln t+ 2xtmaxL) · 28
  3 t2/3 = O ( |E| log xtmax(β √ log t+ xtmaxL)t 2/3 )
  Combining this with Lemma A.14 proves the theorem.