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.

summaries: 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.

summaries: 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.

authors:
Baruch Awerbuch
Robert D Kleinberg

title: Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches

venue: In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing,

authors:
Baruch Awerbuch
Yossi Azar
Amir Epstein

title: The price of routing unsplittable flow

venue: In Proceedings of the 37th Annual ACM Symposium on Theory of Computing,

authors:
Zahy Bnaya
Ariel Felner
Solomon Eyal Shimony

title: Canadian traveler problem with remote sensing

venue: IJCAI

authors:
Anthony Chen
Zhaowang Ji

title: Path finding under uncertainty

venue: Journal of Advanced Transportation,

title: Regret theory-based route choices and traffic

venue: equilibria. Transportmetrica,

authors:
George Christodoulou
Elias Koutsoupias

title: The price of anarchy of finite congestion games

authors:
Gabriel de Oliveira Ramos
Bruno Castro da Silva
Ana L.C. Bazzan

title: Learning to minimise regret in route choice

venue: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems,

authors:
Mo Dong
Qingxi Li
Doron Zarchy
Philip Brighten Godfrey
Michael Schapira

title: PCC: rearchitecting congestion control for consistent high performance

venue: In 12th USENIX Symposium on Networked Systems Design and Implementation,

authors:
Mo Dong
Tong Meng
Doron Zarchy
Engin Arslan
Yossi Gilad
Brighten Godfrey
Michael Schapira

title: PCC vivace: Online-learning congestion control

venue: 15th USENIX Symposium on Networked Systems Design and Implementation,

authors:
András György
Tamás Linder
Gábor Lugosi
György Ottucsák

title: The on-line shortest path problem under partial monitoring

venue: J. Mach. Learn. Res.,

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

title: Via: Improving internet telephony call quality using predictive relay selection

venue: In Proceedings of the ACM SIGCOMM 2016 Conference,

authors:
Junchen Jiang
Shijie Sun
Vyas Sekar
Hui Zhang

title: Pytheas: Enabling data-driven quality of experience optimization using group-based exploration-exploitation

venue: 14th USENIX Symposium on Networked Systems Design and Implementation,

authors:
Branislav Kveton
Zheng Wen
Azin Ashkan
Hoda Eydgahi
Brian Eriksson

title: Matroid bandits: Fast combinatorial optimization with learning

venue: In Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence,

authors:
Keqin Liu
Qing Zhao

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)

authors:
Evdokia Nikolova
David R. Karger

title: Route planning under uncertainty: The canadian traveller problem

venue: Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence,

authors:
Evdokia Nikolova
Jonathan A. Kelner
Matthew Brand
Michael Mitzenmacher

title: Stochastic shortest paths via quasi-convex maximization

venue: Algorithms - ESA

authors:
Christos H. Papadimitriou
Mihalis Yannakakis

title: Shortest paths without a map

venue: Theoretical Computer Science,

authors:
Tim Roughgarden
Éva Tardos

title: How bad is selfish routing

venue: J. ACM,

title: Introduction to multi-armed bandits

venue: arXiv preprint arXiv:1904.07272,

authors:
Mohammad Sadegh Talebi
Zhenhua Zou
Richard Combes
Alexandre Proutière
Mikael Johansson

title: Stochastic online shortest path routing: The value of feedback

venue: IEEE Trans. Autom. Control.,

authors:
Jinkai Zhou
Xuebo Lai
Joseph Chow

title: Multi-armed bandit on-time arrival algorithms for sequential reliable route selection under uncertainty

venue: Transportation Research Record Journal of the Transportation Research Board, 2673:673–682,

authors:
Zhenhua Zou
Alexandre Proutière
Mikael Johansson

title: Online shortest path routing: The value of information

venue: In American Control Conference,

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.

heading: 1 INTRODUCTION

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.

heading: 1.1 MODEL

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).

heading: 1.2 OUR CONTRIBUTION

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.

heading: 1.3 RELATED WORK

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.

heading: 2 DESCRIPTION OF THE ALGORITHM

text: In this section, we define and give intuition for our algorithm for learning an optimal routing policy.

heading: 2.1 INTUITION BEHIND THE ALGORITHM

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.

heading: 2.2 OUR COST ESTIMATION SCHEME

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.

heading: 2.3 DEFINING THE ALGORITHM

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.

heading: 3 EXPERIMENTS

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.

heading: 3.1 METHODOLOGY

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.

heading: 3.2 RESULTS

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.

heading: 4 CONCLUSION

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.

heading: A PROOF OF THEOREM 1.1

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.


summaries: This paper proposes an improvement to how tokens are selected for masking in pre-training large masked language models (BERT and family). Specifically, it stipulates that purely random choice of words (or word pieces) makes the MLM task insufficiently hard. It then goes on to propose a data-driven approach for selecting n-grams to mask together. The approach, based on an extension of pointwise mutual information for n-grams, is shown to outperform random token and random spans masking strategies on performance of downstream tasks.

summaries: This paper presents a masking strategy for training masked language models (MLM). The proposed strategy builds on previous approaches that mask semantically coherent spans of tokens (such as entire words, named entities, or spans) rather than randomly masking individual tokens. Specifically, the proposed method computes the PMI of spans (and the generalization for spans of size >2) over the pretraining corpus, and randomly masks from among the 800K spans (lengths 2-5) with the highest PMI. Masking based on PMI removes the ability for the model to rely on highly local signals to fill in the mask and instead focus on learning higher level semantics. They motivate this hypothesis with an experiment demonstrating that as the size of the WordPiece vocabulary decreases (and words are more frequently split into multiple tokens rather than being their own token), the transfer performance of the resulting MLM decreases. However, using whole-word masking with this same vocabulary size recovers much of the original performance, indicating that allowing the model to rely on these strong local signals harms the transfer quality of the resulting model.

summaries: The paper proposes a variant on the MLM training objective which uses PMI in order to determine which spans to mask. The idea is related to recently-proposed Whole Word Masking and Entity-based masking, but the authors argue the PMI-based approach is more principled. The method is straightforward--it involves computing PMIs for ngrams (in this case, up to length 5) over the training corpus, and then preferring to mask entire collocational phrases rather than single words during training. The intuition is that masking single words allows models to exploit simple collocations, thus optimizing their training objective without learning longer-range dependencies or higher level semantic features of the sentences, and this makes training less efficient than it could be. One contribution of the paper is a variant on the PMI metric that performs better for longer phrases by reducing the scores of phrases that happen to contain high-PMI subphrases, e.g. "George Washington is" should not have a high score despite the fact that "George Washington" does have a high score.

abstractText: Masking tokens uniformly at random constitutes a common flaw in the pretraining of Masked Language Models (MLMs) such as BERT. We show that such uniform masking allows an MLM to minimize its training objective by latching onto shallow local signals, leading to pretraining inefficiency and suboptimal downstream performance. To address this flaw, we propose PMI-Masking, a principled masking strategy based on the concept of Pointwise Mutual Information (PMI), which jointly masks a token n-gram if it exhibits high collocation over the corpus. PMIMasking motivates, unifies, and improves upon prior more heuristic approaches that attempt to address the drawback of random uniform token masking, such as whole-word masking, entity/phrase masking, and random-span masking. Specifically, we show experimentally that PMI-Masking reaches the performance of prior masking approaches in half the training time, and consistently improves performance at the end of training.

authors:
Roy Bar-Haim
Ido Dagan
Bill Dolan
Lisa Ferro
Danilo Giampiccolo
Bernardo Magnini
Idan Szpektor

title: The second PASCAL recognising textual entailment challenge

venue: In Proceedings of the second PASCAL challenges workshop on recognising textual entailment,

authors:
Tom B Brown
Benjamin Mann
Nick Ryder
Melanie Subbiah
Jared Kaplan
Prafulla Dhariwal
Arvind Neelakantan
Pranav Shyam
Girish Sastry
Amanda Askell

title: Language models are few-shot learners

authors:
Daniel Cer
Mona Diab
Eneko Agirre
Iñigo Lopez-Gazpio
Lucia Specia

title: Semeval-2017 task 1: Semantic textual similarity multilingual and crosslingual focused evaluation

venue: In International Workshop on Semantic Evaluation (SemEval),

authors:
Ido Dagan
Oren Glickman
Bernardo Magnini

title: The PASCAL recognising textual entailment challenge

venue: In Machine Learning Challenges Workshop,

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova

title: BERT: Pre-training of deep bidirectional transformers for language understanding

venue: In North American Association for Computational Linguistics (NAACL),

authors:
William B Dolan
Chris Brockett

title: Automatically constructing a corpus of sentential paraphrases

venue: In Proceedings of the International Workshop on Paraphrasing,

authors:
Doug Downey
Matthew Broadhead
Oren Etzioni

title: Locating complex named entities in web text

venue: In Proceedings of the 20th International Joint Conference on Artifical Intelligence,

title: Transmission of Information: A Statistical Theory of Communications. Transmission of Information: A Statistical Theory of Communications

authors:
Danilo Giampiccolo
Bernardo Magnini
Ido Dagan
Bill Dolan

title: The third PASCAL recognizing textual entailment challenge

venue: In Proceedings of the ACL-PASCAL workshop on textual entailment and paraphrasing,

authors:
Kelvin Guu
Kenton Lee
Zora Tung
Panupong Pasupat
Ming-Wei Chang

title: Realm: Retrievalaugmented language model pre-training

venue: arXiv preprint arXiv:2002.08909,

authors:
Mandar Joshi
Danqi Chen
Yinhan Liu
Daniel S Weld
Luke Zettlemoyer
Omer Levy

title: Spanbert: Improving pre-training by representing and predicting spans

venue: Transactions of the Association for Computational Linguistics,

authors:
Ioannis Korkontzelos
Ioannis P Klapaftis
Suresh Manandhar

title: Reviewing and evaluating automatic term recognition techniques

venue: In International Conference on Natural Language Processing,

authors:
Guokun Lai
Qizhe Xie
Hanxiao Liu
Yiming Yang
Eduard Hovy

title: Race: Large-scale reading comprehension dataset from examinations

venue: arXiv preprint arXiv:1704.04683,

authors:
Hector J Levesque
Ernest Davis
Leora Morgenstern

title: The Winograd schema challenge

venue: In AAAI Spring Symposium: Logical Formalizations of Commonsense Reasoning,

authors:
Yinhan Liu
Myle Ott
Naman Goyal
Jingfei Du
Mandar Joshi
Danqi Chen
Omer Levy
Mike Lewis
Luke Zettlemoyer
Veselin Stoyanov

title: RoBERTa: A robustly optimized BERT pretraining approach

authors:
Alec Radford
Jeffrey Wu
Rewon Child
David Luan
Dario Amodei
Ilya Sutskever

title: Language models are unsupervised multitask learners

authors:
Colin Raffel
Noam Shazeer
Adam Roberts
Katherine Lee
Sharan Narang
Michael Matena
Yanqi Zhou
Wei Li
Peter J Liu

title: Exploring the limits of transfer learning with a unified text-to-text transformer

venue: arXiv preprint arXiv:1910.10683,

authors:
Pranav Rajpurkar
Jian Zhang
Konstantin Lopyrev
Percy Liang

title: Squad: 100,000+ questions for machine comprehension of text

venue: arXiv preprint arXiv:1606.05250,

authors:
Pranav Rajpurkar
Robin Jia
Percy Liang

title: Know what you don’t know: Unanswerable questions for squad

venue: arXiv preprint arXiv:1806.03822,

authors:
Carlos Ramisch
Vitor De Araujo
Aline Villavicencio

title: A broad evaluation of techniques for automatic acquisition of multiword expressions

venue: In Proceedings of ACL 2012 Student Research Workshop,

authors:
Richard Socher
Alex Perelygin
Jean Wu
Jason Chuang
Christopher D Manning
Andrew Ng
Christopher Potts

title: Recursive deep models for semantic compositionality over a sentiment treebank

venue: In Empirical Methods in Natural Language Processing (EMNLP),

authors:
Yu Stephanie Sun
Shuohuan Wang
Yukun Li
Shikun Feng
Xuyi Chen
Han Zhang
Xinlun Tian
Danxiang Zhu
Hao Tian
Hua Wu

title: ERNIE: Enhanced representation through knowledge integration

title: Two multivariate generalizations of pointwise mutual information

venue: In Proceedings of the Workshop on Distributional Semantics and Compositionality,

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Łukasz Kaiser
Illia Polosukhin

title: Attention is all you need

venue: In Advances in Neural Information Processing Systems (NIPS),

authors:
Alex Wang
Amanpreet Singh
Julian Michael
Felix Hill
Omer Levy
Samuel R Bowman

title: Glue: A multi-task benchmark and analysis platform for natural language understanding

venue: arXiv preprint arXiv:1804.07461,

authors:
Alex Wang
Amapreet Singh
Julian Michael
Felix Hill
Omer Levy
Samuel R Bowman

venue: In International Conference on Learning Representations (ICLR),

authors:
Alex Warstadt
Amanpreet Singh
Samuel R. Bowman

title: Neural network acceptability judgments

venue: arXiv preprint arXiv:1805.12471,

authors:
Adina Williams
Nikita Nangia
Samuel Bowman

title: A broad-coverage challenge corpus for sentence understanding through inference

authors:
Xinsong Zhang
Hang Li

title: Ambert: A pre-trained language model with multi-grained tokenization

venue: arXiv preprint arXiv:2008.11869,

title: What are the productive units of natural language grammar? a dop approach to the automatic identification of constructions

venue: In Proceedings of the Tenth Conference on Computational Natural Language Learning (CoNLL-X),

heading: 1 INTRODUCTION

text:
In the couple of years since BERT was introduced in a seminal paper by Devlin et al. (2019a), Masked Language Models (MLMs) have rapidly advanced the NLP frontier (Sun et al., 2019; Liu et al., 2019; Joshi et al., 2020; Raffel et al., 2019). At the heart of the MLM approach is the task of predicting a masked subset of the text given the remaining, unmasked text. The text itself is broken up into tokens, each token consisting of a word or part of a word; thus “chair” constitutes a single token, but out-of-vocabulary words like “e-igen-val-ue” are broken up into several sub-word tokens. In BERT, 15% of tokens are chosen to be masked uniformly at random. It is the random choice of single tokens that we address in this paper: we show that this approach is suboptimal and offer a principled alternative.
To see why Random-Token Masking is suboptimal, consider the special case of sub-word tokens. Given the masked sentence “To approximate the matrix, we use the eigenvector corresponding to its largest e-[mask]-val-ue”, an MLM will quickly learn to predict “igen” based only on the context “e[mask]-val-ue”, rendering the rest of the sentence redundant. The question is whether the network will also learn to relate the broader context to the tokens comprising “eigenvalue”. When they are masked together, the network is forced to do so, but such masking occurs with vanishingly small probability. One might hypothesize that the network would nonetheless be able to piece such meaning together from local cues; however, we show that it often struggles to do so.
We establish this via a controlled experiment, in which we reduced the size of the vocabulary, thereby breaking more words into sub-word tokens. We compared the extent to which such vocabulary reduction degraded regular BERT relative to so-called Whole-Word Masking BERT (WWBERT) (Devlin et al., 2019b), a version of BERT that jointly masks all sub-word tokens comprising an out-of-vocabulary word during training. We show that vanilla BERT’s performance degrades much more rapidly than that of WWBERT as the vocabulary size shrinks. The intuitive explanation
is that Random-Token Masking is wasteful; it overtrains on easy sub-word tasks (such as predicting “igen”) and undertrains on harder whole-word tasks (predicting “eigenvalue”).
The advantage of Whole-Word Masking over Random-Token Masking is relatively modest for standard vocabularies, because out-of-vocabulary words are rare. However, the tokenization of words is a very special case of a much broader statistical linguistic phenomenon of collocation: the cooccurrence of series of tokens at levels much greater than would be predicted simply by their individual frequencies in the corpus. There are millions of collocated word n-grams — multi-word expressions, phrases, and other common word combinations — whereas there are only tens of thousands of words in frequent use. So it is reasonable to hypothesize that Random-Token Masking generates many wastefully easy problems and too few usefully harder problems because of multiword collocations, and that this affects performance even more than the rarer case of tokenized words; we show that this indeed is the case.
Several prior works have considered the idea of masking across spans longer than a single word. Sun et al. (2019) and Guu et al. (2020) proposed Knowledge Masking and Salient Span Masking, respectively, in which tokens comprising entities or phrases, as identified by external parsers, are jointly masked. While extending the scope of Whole-Word Masking, the restriction to specific types of correlated n-grams, along with the reliance on imperfect tools for their identification, has limited the gains achievable by these approaches. With a similar motivation in mind, SpanBERT of Joshi et al. (2020) introduced Random-Span Masking, which masks word spans of lengths sampled from a geometric distribution at random positions in the text. Random-Span Masking was shown to consistently outperform Knowledge Masking, is simple to implement, and inspired prominent MLMs (Raffel et al., 2019). However, while Random-Span Masking increases the chances of masking collocations, with high probability the selected spans break up correlated n-grams, such that the prediction task can often be performed by relying on local cues.
In this paper we offer a principled approach to masking spans that consistently provide high signal, unifying the intuitions behind the above approaches while also outperforming them. Our approach, dubbed PMI-Masking, uses Pointwise Mutual Information (PMI) to identify collocations, which we then mask jointly. At a high level, PMI-Masking consists of two stages. First, given any pretraining corpus, we identify a set of contiguous n-grams that exhibit high cooccurrence probability relative to the individual occurrence probabilities of their components. We for-
malize this notion by proposing an extended definition of Pointwise Mutual Information from bigrams to longer n-grams. Second, we treat these collocated n-grams as single units; the masking strategy selects at random both from these units and from standard tokens that do not participate in such units. Figure 1, detailed and reinforced by further experiments in section 5, shows that (1) PMI-Masking dramatically accelerates training, matching the end-of-pretraining performance of existing approaches in roughly half of the training time; and (2) PMI-Masking improves upon previous masking approaches at the end of pretraining.

heading: 2 MOTIVATION: MLMS ARE SENSITIVE TO TOKENIZATION

text:
In this section we describe a simple experiment that motivates our PMI-Masking approach. We examined BERT’s ability to learn effective representations for words consisting of multiple subword tokens, treating this setting as an easily controlled analogue for the multi-word collocation problem that truly interests us. Our experiment sought to assess the performance gain obtained from always masking whole words as opposed to masking each individual token uniformly at random. We
compared performance across a range of vocabulary sizes, using the same WordPiece Tokenizer1 that produced the original vocabulary of ∼ 30K tokens. As we decreased a 30K-token vocabulary to 10K and 2K tokens, the average length of a word over the pretraining corpus increased from 1.08 tokens to 1.22 and 2.06 tokens, respectively. Thus, by reducing the vocabulary size, we increased the frequency of multi-token words by a large factor.
Table 1 presents the performance of BERT models trained with these vocabularies, measured as score on the SQuAD2.0 development set (the experimental setup is described in section 4). The downstream performance of Random-Token Masking substantially degraded as vocabulary size decreased and the number of spans of sub-word tokens increased. One reason for such degradation might be the model seeing less text as context (512 input tokens cover less text when more words are broken into multiple tokens). This possibly plays a role; however, for models with the same vocabularies trained via Whole-Word Masking, this degradation was significantly attenuated. We therefore conjecture that this degradation occurred primarily because of the random masking strategy, which allows the model to use “shortcuts” for minimizing its loss, thus hindering its ability to learn the distribution of the entire multi-token word.
If our conjecture is correct, such shortcuts are just as problematic in the case of inter-word collocations. In fact, for the regular 30K-token vocabulary, divided words are rare, so inter-word collocations would pose a larger problem than intra-word collocations in the common setting. One possible mitigation might be to expand the vocabulary to include multi-word collocations. However, there are millions of these, and such vocabulary sizes are currently infeasible. Even if we could get around the practical issue of size, this approach may suffer from generalization problems: the frequency of each multi-word collocation can be lower than the sample complexity for learning a meaningful representation. An alternative, more practical approach is to leave the vocabulary as is, but jointly mask co-located words, with the intention of cutting off local statistical “shortcuts” and allowing the model to improve further by learning from broader context. This is the approach we take in this paper. In what follows we detail such a masking approach and show its advantages experimentally.
3 MASKING CORRELATED n-GRAMS

heading: 3.1 EXISTING MASKING APPROACHES

text:
We now more formally present the MLM setup as well as existing masking approaches, which we implement as baselines. Given text tokenized into a sequence of tokens, Masked Language Models are trained to predict a set fraction of “masked” tokens, where this fraction is called the masking budget and is traditionally set to 15%. The modified input is inserted into the Transformer-based architecture (Vaswani et al., 2017) of BERT, and the pretraining task is to predict the original identity of each chosen token. Several alternatives have been proposed for choosing the set of tokens to mask.
Random-Token Masking (Devlin et al., 2019a) The original BERT implementation selects tokens for masking independently at random, where 80% of the 15% chosen tokens are replaced with [MASK], 10% are replaced with a random token, and 10% are kept unchanged.
Whole-Word Masking (Devlin et al., 2019b) The sequence of input tokens is segmented into units corresponding to whole words. Tokens for masking are then chosen by sampling entire units at random until the masking budget is met. Following Devlin et al. (2019a), for 80%/10%/10% of the units, all tokens are replaced with [MASK]tokens/ random tokens/ the original tokens, respectively.
1https://github.com/huggingface/tokenizers
Random-Span Masking (Joshi et al., 2020) Contiguous random spans are selected iteratively until the 15% masking budget is spent. At each iteration, a span length (in words) is sampled from a geometric distribution ` ∼ Geo(0.2), and capped at 10 words. Then, the starting point for the span to be masked is randomly selected. Replacement with [MASK], random, or original tokens is done as above, where spans constitute the units.
3.2 PMI: FROM BIGRAMS TO n-GRAMS
Our aim is to define a masking strategy that targets correlated sequences of tokens in a principled way. Of course, modeling such correlations in large corpora was widely studied in computational linguistics (Zuidema (2006); Ramisch et al. (2012); inter alia). Particularly relevant to our work is the notion of Pointwise Mutual Information (Fano, 1961), which quantifies how often two events occur, compared with what we would expect if they were independent. Define the probability of any n-gram as the number of its occurrences in the corpus divided by the number of all the n-grams in the corpus. PMI leverages these probabilities to give a natural measure of collocation of bigrams: how surprising the bigram w1w2 is, given the unigram probabilities of w1 and w2. Formally, given two tokens w1 and w2, the PMI of the bigram “w1w2” is
PMI(w1w2) = log p(w1w2)
p(w1)p(w2) . (1)
Importantly, PMI is qualitatively different from pure frequency: a relatively frequent bigram may not have a very high PMI score, and vice versa. For example, the bigram “book is” appears 34772 times in the WIKIPEDIA+BOOKCORPUS dataset but is ranked around position 760K in the PMI ranking for bi-grams over this corpus, while the bigram “boolean algebra” appears 849 times in the corpus but is ranked around position 16K in the PMI ranking.
What about contiguous spans of more than two tokens? For a given n-gram, we would again like to measure how strongly its components indicate one another. We thus require a measure that captures correlations among more than two variables. A standard and direct extension of the PMI measure to more than two variables, referred to as ‘specific correlation’ in Van de Cruys (2011), and as ‘NaivePMIn’ in this paper, is based on the ratio between the n-gram’s probability and the probabilities of its component unigrams:
Naive-PMIn(w1 . . . wn) = log p(w1 . . . wn)∏n
j=1 p(wj) (2)
As in the bivariate case, this measure compares the actual empirical probability of the n-gram in the corpus with the probability it would have if its components occurred independently. However, the above definition suffers from an inherent flaw: an n-gram’s Naive-PMIn will be high if it contains a segment with high PMI, even if that segment is not particularly correlated with the rest of the n-gram. Consider for example the case of trigrams:
Naive-PMI3(w1w2w3) = log{ p(w1w2w3) p(w1)p(w2)p(w3) · p(w1w2) p(w1w2) } = PMI(w1w2) + log p(w1w2w3) p(w1w2)p(w3)
Where PMI(w1w2) is defined in eq. 1. When PMI(w1w2) is high, the Naive-PMI3 measure of the trigram “w1w2w3” will start at this high baseline. The added term of log
p(w1w2w3) p(w1w2)p(w3) quantifies the actual added information of “w3” to this correlated bigram, i.e., it quantifies how far p(w1w2w3) is from being separable w.r.t. the segmentation into “w1w2” and “w3”. For example, since the PMI of the bigram “Kuala Lumpur” is very high, the Naive-PMIn of the trigram “Kuala Lumpur is” is misleadingly high, placing it at position 43K out of all trigrams in the WIKIPEDIA+BOOKCORPUS dataset. It is in fact placed much higher than obvious collocations such as the trigram “editor in chief ”, which is ranked at position 210K out of all trigrams.
In order to favor n-grams that cannot be easily subdivided into shorter unrelated spans, we propose a measure of distance from separability with respect to all of an n-gram’s possible segmentations rather than with respect only to the segmentation into single tokens:
PMIn(w1 . . . wn) = min σ∈seg(w1...wn)
log p(w1 . . . wn)∏
s∈σ p(s) (3)
Here, seg(w1 . . . wn) is the set of all contiguous segmentations of the n-gram “w1 . . . wn” (excluding the identity segmentation), where any segmentation σ ∈ seg(w1 . . . wn) is composed of sub-spans which together give “w1 . . . wn”. Intuitively, this measure effectively discards the contribution of high PMI segments; the minimum in Eq. 3 implies that an n-gram’s collocation score is given by its weakest link, i.e., by the segmentation that is closest to separability. When ranked by the above PMIn measure, the trigram “Kuala Lumpur is” is demoted to position 1.6M, since the segmentation into “Kuala Lumpur” and “is” yields unrelated segments, while the trigram “editor in chief ” is upgraded to position 33K since its segmentations yield correlated components. As we will see, this definition is not only conceptually cleaner, but also leads to improved performance.

heading: 3.2.1 PMI-MASKING

text:
We implement our strategy of treating highly collocating n-grams as units for masking by assembling a list of n-grams as a masking vocabulary in parallel to the 30K-token vocabulary. Specifically, we make use of the entire pretraining corpus for compiling a list of collocations. We consider word n-grams of lengths 2–5 having over 10 occurrences in the corpus, and include the highest ranking collocations over the corpus, as measured via our proposed PMIn measure (Eq. 3). Noticing that the PMIn measure is sensitive to the length of the n-gram, we assemble per-length rankings for each n ∈ {2, 3, 4, 5}, and integrate these rankings to compose the masking vocabulary. After conducting a preliminary evaluation of how an n-gram’s quality as a collocation degrades with its PMIn rank (detailed in the appendix), we chose the masking vocabulary size to be 800K, for which approximately half of pretraining corpus tokens were identified as part of some correlated n-gram.
In order to get some sense of the differences between the attained masking vocabulary and prior approaches, we annotated a random sample of 500 bigrams and 500 trigrams from the masking vocabulary with Entity/Not-Entity labels. We found that only around 14% of the entries in the bigrams/trigrams lists were annotated as entities, while the rest are other types of collocations. Moreover, we found that while named entities are very prevalent at the very top of the list, they are scarce otherwise. By refining the view into highest and lowest ranking PMI bigram groups, we get that 50% of the top 20% are entities while only 1% of the bottom 20% are entities, and similar trends are attained for trigrams. This breakdown can illuminate a natural intuition regarding high ranking PMI n-grams representing entities (employed also by previous works (Downey et al., 2007; Korkontzelos et al., 2008)) – indeed the top ranking PMI entries are largely entities. But we chose a much larger PMI-based masking vocabulary (see appendix 1 on the process of choosing its size), and the proportion of entities drops to around 1/7, with many of the added entries representing other types of collocations (the annotated lists are given as supplementary material).
After composing the masking vocabulary, we treat its entries as units to be masked together. All input tokens not identified with entries from the masking vocabulary are treated independently as units for masking according to the Whole-Word Masking scheme. If one masking vocabulary entry contains another entry in a given input, we treat the larger one as the unit for masking, e.g., if the masking vocabulary contains the n-grams “the united states”, “air force”, and “the united states air force”, the latter will be one unit for masking when it appears. In the case of overlapping entries, we choose one at random as a unit for masking and treat the remaining tokens as independent units, e.g., if the input text contains “by the way out” and the masking vocabulary contains the n-grams “by the way” and “the way out”, we can choose either “by the way” and “out” or “by” and “the way out” as units for masking.
After we segment the sequence of input tokens into units for masking, we then choose tokens for masking by sampling units uniformly at random until 15% of the tokens (the standard tokens of the 30K-token vocabulary) in the input are selected. As in the prior methods, replacement with [MASK](80%), random (10%), or original (10%) tokens is done at the unit level.

heading: 4 EXPERIMENTAL SETUP

text:
To evaluate the impact of PMI-Masking, we trained Base-sized BERT models (Devlin et al., 2019a) with each of the masking schemes presented in Section 3. Rather than relying on existing implementations for baseline masking schemes, which vary in training specifics, we reimplemented each scheme within the same framework used to train our PMI-Masked models. For control, we trained within the same framework models with Naive-PMI-Masking and Frequency-Masking, following
the procedure described above for PMI-Masking, but ranking by the Naive-PMIn measure (Eq. 2) and by pure-frequency, respectively. In Section 5, we compare our PMI-Masking to all internallytrained masking schemes (Table 2) as well as with externally released models (Table 3).

heading: 4.1 PRETRAINING

text:
We trained uncased models with a 30K-sized vocabulary that we constructed over WIKIPEDIA +BOOKCORPUS via the WordPiece Tokenizer used in BERT. We omitted the Next Sentence Prediction task, as it was shown to be superfluous (Joshi et al., 2020), and trained only on the Masked Language Model task during pretraining. We trained with a sequence length of 512 tokens, batch size of 256, and a varying number of steps detailed in Section 5. For pretraining, after a warmup of 10, 000 steps we used a linear learning rate decay, therefore models that ran for a different overall amount of steps are not precisely comparable after a given amount of steps. We set remaining parameters to values similar to those used in the original BERT pretraining, detailed in the appendix.
We performed the baseline pretraining over the original corpus used to train BERT: the 16GB WIKIPEDIA+BOOKCORPUS dataset. We show that PMI-Masking achieved even larger performance gains relative to the baselines when training over more data, by adding the 38GB OPENWEBTEXT (Gokaslan & Cohen, 2019) dataset, an open-source recreation of the WebText corpus described in Radford et al. (2019). As described in section 3, we compose our PMIn-based masking vocabulary according to the pretraining corpus in use.

heading: 4.2 EVALUATION

text:
We evaluate our pretrained models on two question answering benchmarks: the Stanford Question Answering Dataset (SQuAD) and the ReAding Comprehension from Examinations (RACE), as well as on the General Language Understanding Evaluation (GLUE) benchmark. Additionally, we report the Single-Token perplexity of our pretrained models.
• SQuAD (Rajpurkar et al., 2016) has served as a major question answering benchmark for pretrained models. It provides a paragraph of context and a question, and the task is to answer the question by extracting the relevant span from the context. We focus on the latest more challenging variant, SQuAD2.0 (Rajpurkar et al., 2018), in which some questions are not answered in the provided context, and the task includes identifying such cases.
• RACE (Lai et al., 2017) is a large-scale reading comprehension dataset collected from English examinations in China, designed for middle and high school students. Each passage is associated with multiple questions; for each, the task is to select one correct answer from four options. RACE has significantly longer context than other popular reading comprehension datasets and the proportion of questions that requires reasoning is very large.
• GLUE (Wang et al., 2018) is a collection of 9 datasets for evaluating natural language understanding systems. Tasks are framed as either single-sentence classification or sentence-pair classification tasks. For full details, please see the appendix.
• Single-Token perplexity We evaluate an MLM’s ability to predict single-tokens by measuring perplexity over a held out test set of 110K tokens from OPENWEBTEXT. For each test example, a single token for prediction is masked and the remainder of the input tokens are unmasked.
In Tables 2 and 3, for every downstream task we swept 8 different hyperparameter configurations (batch sizes ∈ {16, 32} and learning rates ∈ {1, 2, 3, 5} · 10−5). We report the best median development set score over five random initializations per hyper-parameter. When applicable, the model with this score was evaluated on the test set. The development set score of each configuration was attained by fine-tuning the model over 4 epochs (SQuAD2.0 and RACE) or 3 epochs (all GLUE tasks except RTE and STS – 10 epochs) and performing early stopping based on each task’s evaluation metric on the development set. In the preliminary experiments of Table 1, and in Figures 1 and 2 for which we evaluate many pretraining checkpoints per model, we report the average of the three middle scores out of 5 random initializations for a single set of hyper-parameters (batch size 32 and learning rate 3 · 10−5).

heading: 5 EXPERIMENTAL RESULTS

text: We evaluated the different masking strategies in two key ways. First, we measured their effect on downstream performance throughout pretraining to assess how efficiently they used the pretraining phase. Second, we more exhaustively evaluated downstream performance of different approaches at the end of pretraining. We examine how the advantage of PMI-Masking is affected by the size of the pretraining corpus and by amount of examples seen during pretraining (batch size × training steps).

heading: 5.1 EVALUATING DOWNSTREAM PERFORMANCE THROUGHOUT PRETRAINING

text:
By examining the model’s downstream performance after each 200K steps of pretraining, we demonstrate that PMI-Masking speeds up MLM training. Figure 1 investigates the standard BERT setting of pretraining on the Wikipedia+BookCorpus dataset for 1M training steps with batch size 256. It shows that the PMI-Masking method clearly outperformed a variety of prior approaches, as well as the baseline pure frequency based masking, on the SQuAD2.0 development set for all examined checkpoints (these patterns are consistent on RACE, see detailed scores in the appendix). PMIMasking achieved the score of Random-Span Masking, the best of the existing approaches, after roughly half as many steps of pretraining.
We ran a second experiment that increased the number of steps from 1M to 2.4M, while maintaining the batch size and the pretraining corpus; this was the setting used by Joshi et al. (2020) when proposing Random-Span Masking. We observed that while PMI-masking learned much more quickly, it eventually reached a plateau, and Random-Span Masking caught up after enough training steps. Figure 2 (left) details these results.
Finally, we increased the amount of training data by adding the OPENWEBTEXT corpus (∼ 3.5× more data). Figure 2 (right) demonstrates that the plateau we previously observed in PMIMasking’s performance was due to limited training data. When training for 2.4M training steps on the Wikipedia+BookCorpus+OpenWebText dataset, PMI-masking reached the same score that Random-Span Masking did at the end of training after roughly half of the pretraining, and continued to improve. Thus, PMI-Masking definitively outperformed Random-Span masking in a scenario where data was not a bottleneck, as is ideally the case in MLM pretraining (Raffel et al., 2019).

heading: 5.2 EVALUATING DOWNSTREAM PERFORMANCE AFTER PRETRAINING

text:
Table 2 shows that after pretraining was complete, PMI-Masking outperformed prior masking approaches in downstream performance on the SQuAD2.0, RACE, and GLUE benchmarks. In agreement with Figure 2, for longer pretraining (2.4M training steps) the absolute advantage of PMIMasking is boosted across all tasks when pretraining over a larger corpus (adding OPENWEBTEXT). The table also shows that Naive-PMI Masking, based on the straightforward extension in eq. 2 to the standard bivariate PMI, significantly falls behind our more nuanced definition in eq. 3, and is often on par with Random-Span Masking.
We also compared our PMI-Masking Base-sized models to published Base-sized models (Table 3), and again saw PMI-Masking increase both pretraining efficiency and end-of-training downstream performance. Zhang & Li (2020) trained their ‘AMBERT’ model over a vocabulary of n-grams in parallel to the regular word/subword level vocabulary, performing the hard task of n-gram prediction in parallel to the easy Random-Token level prediction task during pretraining. This approach yielded a model with 75% more parameters than the common Base size of our PMI-Masking model. By using the PMI-masking scheme on a regular BERT architecture and vocabulary, we attained a significantly higher score on the RACE benchmark, despite training over a corpus 3× smaller and showing the model 2× fewer examples during pretraining.
Joshi et al. (2020) and Liu et al. (2019) only reported scores for SpanBERT and RoBERTa (respectively) for Large-sized models in their original papers, but did release weights for Base-sized models. We fine-tuned these models on the RACE development set via the same fine-tuning procedure we employed for our PMI-Masking models (described in Section 4), and evaluated the best performing model on the publicly available RACE test set. A PMI-Masking Base-sized model scored more than 2 points higher than the SpanBERTBASE trained by Random-Span Masking over the same pretraining corpus when shown the same number of examples. Remarkably, a PMI-Masking Base-sized model scored slightly higher than RoBERTaBASE trained by Random-Token Masking, even though RoBERTa was given access to a pretraining corpus 3× larger and shown 6×more training examples.
Lastly, we note that the measure of Single-Token perplexity is not indicative of downstream performance, when reported for models trained with different masking schemes. Comparing the adjacent table with the downstream evaluation of the same models in Table 2, it is clear that the ability to predict single tokens from context is not correlated with performance. This reinforces our observation that by minimizing their training objective, standard MLMs, which mask tokens randomly, train to excel on relatively many easy tasks that do not reflect the knowledge required for downstream understanding.

heading: 6 CONCLUSION

text: Bidirectional language models hold the potential to unlock greater signal from the training data than unidirectional models (such as GPT). BERT-based MLMs are historically the first (and still the most prominent) implementation of inherently bidirectional language models, but they come at a price. A hint of this price is the fact that Single-Token perplexity, which captures the ability to predict single tokens and which has a natural probabilistic interpretation in the autoregressive unidirectional case, ceases to correlate with downstream performance across different MLMs (see Table 4). This means that the original MLM task, which is focused on single token prediction, should be reconsidered. This has been the focus of this paper, which points to the inefficiency of random-token masking, and offers PMI-masking as an alternative with several advantages: (i) It is a principled approach, based on a nuanced extension of binary PMI to the n-ary case. (ii) It leads to better downstream performance, for example it surpasses RoBERTa (which uses vanilla random token masking) on the challenging reading comprehension RACE test with 6× less training over a 3× smaller corpus, and it dominates the more naive, heuristic approach of random span masking at any point during pretraining, matches its end-of-training performance halfway during its own pretraining, and at the end of training improves on it by 1-2 points across a variety of downstream tasks. Perhaps due to their conceptual simplicity, unidirectional models were the first to break the 100B parameter limit with the recent GPT3 (Brown et al., 2020). Bidirectional models will soon follow, and this paper can accelerate their development by offering a way to significantly lower their training costs while boosting performance.

heading: A DETERMINING THE MASKING VOCABULARY SIZE

text:
The PMIn measure, defined in eq. 3, provides an n-gram ranking function that is intended to rank an n-gram higher if its components are more indicative of one another. However, this measure alone is not enough for composing a masking vocabulary: we need to decide on its size M (the masking vocabulary will be composed of the top-M ranked n-grams). One could advocate for an ablation study in which M is varied, and models are pretrained per M and evaluated. This can be done in future work, and perhaps an even stronger result can be shown for PMI-Masking with masking vocabulary size chosen by such optimization.
As a proxy, we determined the masking vocabulary size M via a small scale evaluation of an ngram’s “collocation quality” as a function of its PMIn rank. Specifically, we created an ad hoc test set composed of 1000 n-grams that we labeled either as collocation or not a collocation (available upon request). We did that by choosing at random 10 words with frequency above 10000 in WIKIPEDIA+BOOKCORPUS, and for each word sampled 25 n-grams per length n ∈ {2, 3, 4, 5} that contain it. Finally, we manually labeled each collected n-gram, where the textbook definition of collocation was given to the annotators (the annotator agreement was 80% over 100 shared examples).
Then, we increased a list size M in steps of 50K, adding n-grams from the top ranking PMIn downwards. For each M -sized list we computed two different scores on the test set. The first is the recall of the positive examples in the list, denoted r: the percent of all positively labeled examples from the test set that appear within the given list. The second is the recall of the negative examples in the complement of the list, dubbed complement-recall, denoted c: the percent of all negatively labeled examples from the test set that do not appear within the given list. By these definitions, the recall r starts low and increases with list size and the complement-recall c follows an opposite trend, as can be seen in Figure 3. Our desired masking vocabulary size should yield a list with many n-grams labeled as collocation while containing little n-grams labeled not a collocation. we define f = 2r·cr+c as a measure for optimization which balances the two requirements, and Figure 3 shows that this measure is highest at sizes of around 700-800, so we set the masking vocabulary size to be 800K.

heading: B PRETRAINING AND MODEL DETAILS

text: Table 5 shows the pretraining hyper-parameters we used, as well as the architecture specifics, both follow the standard implementation of BERT.

heading: C EVALUATION OF DIFFERENT CHECKPOINTS DURING PRETRAINING

text: Tables 6 and 7 respectively present the development set scores on SQuAD2.0 and RACE, attained for models at different checkpoints during pretraining. The SQuAD2.0 scores are depicted in Figures 1 and 2.

heading: D GLUE TASKS AND DETAILED SCORES

text:
The General Language Understanding Evaluation (GLUE) benchmark (Wang et al., 2019) consists of 9 sentence-level tasks. Sentence-level classification tasks: CoLA (Warstadt et al., 2018) (evaluating linguistic acceptability) and SST-2 (Socher et al., 2013) (sentiment classification). Sentencepair similarity tasks: MRPC (Dolan & Brockett, 2005) (binary paraphrasing classification task), STS-B (Cer et al., 2017): (graded similarity scoring task), and QQP2 (binary paraphrasing classification task). Natural language inference tasks: MNLI (Williams et al., 2018), QNLI (Rajpurkar et al., 2016), RTE (Dagan et al., 2005; Bar-Haim et al., 2006; Giampiccolo et al., 2007) and WNLI (Levesque et al., 2011). Table 8 shows the detailed per-task scores of our examined models.
2https://data.quora.com/First-Quora-Dataset-Release-Question-Pairs

title: PMI-MASKING: PRINCIPLED MASKING OF CORRELATED SPANS