Online Learning under Adversarial Corruptions
Authors: Pranjal Awasthi
Sreenivas Gollapudi
Kostas Kollias
Apaar Sadhwani
Venue:  (2021)
Keywords: Online Learning
Learning Theory
Bandits
Robustness
Adversarial Corruptions

Abstract: We study the design of efficient online learning algorithms tolerant to adversarially corrupted rewards. In particular, we study settings where an online algorithm makes a prediction at each time step, and receives a stochastic reward from the environment that can be arbitrarily corrupted with probability $\epsilon \in [0,\frac 1 2)$. Here $\epsilon$ is the noise rate the characterizes the strength of the adversary. As is standard in online learning, we study the design of algorithms with small regret over a period of time steps. However, while the algorithm observes corrupted rewards, we require its regret to be small with respect to the true uncorrupted reward distribution. We build upon recent advances in robust estimation for unsupervised learning problems to design robust online algorithms with near optimal regret in  three different scenarios: stochastic multi-armed bandits, linear contextual bandits, and Markov Decision Processes~(MDPs) with stochastic rewards and transitions. Finally, we provide empirical evidence regarding the robustness of our proposed algorithms on synthetic and real datasets.

Under review as a conference paper at ICLR 2021
ONLINE LEARNING UNDER ADVERSARIAL CORRUP- TIONS
Anonymous authors Paper under double-blind review
ABSTRACT
We study the design of efficient online learning algorithms tolerant to adversarially corrupted rewards. In particular, we study settings where an online algorithm makes a prediction at each time step, and receives a stochastic reward from the environment that can arbitrarily corrupted with probability E [0, 2)- Here is the noise rate the characterizes the strength of the adversary. As is standard in online learning, we study the design of algorithms with small regret over a period of time steps. However, while the algorithm observes corrupted rewards, we require its regret to be small with respect to the true uncorrupted reward distribution. We build upon recent advances in robust estimation for unsupervised learning problems to design robust online algorithms with near optimal regret in three different scenarios: stochastic multi-armed bandits, linear contextual bandits, and Markov Decision Processes (MDPs) with stochastic rewards and transitions. Finally, we provide empirical evidence regarding the robustness of our proposed algorithms on synthetic and real datasets.
INTRODUCTION
The study of online learning algorithms has a rich and extensive history (Slivkins, 2019). An online learning algorithm makes a sequence of predictions, one per time step and receives reward. The predictions could involve picking an expert from a given set of experts, or picking an action from set of available actions as in reinforcement learning settings. The goal of the algorithm is maximize the long term reward resulting from the sequence of predictions made. The performance of such an algorithm is measured in terms of the regret, i.e., the difference in the total reward accumulated by the algorithm and the total reward accumulated by the best expert/action/policc in hindsight. Various online learning models have been studied in the literature depending on whether the rewards generated i..dd from some distribution (Gittins, 1979; Thompson, 1933) or are arbitrary (Auer et al., 2001), and whether the reward for all actions is observed at each time step (full information setting) (Littlestone & Warmuth, 1994) vs. observing only the reward of the chosen action (bandit setting) (Auer et al., 2002; 2001).
In this work, initiate the study of online learning algorithms with adversarial reward corruptions. Specifically, we focus on the case where the generated rewards are infrequently masked by an adversary and replaced with potentially unbounded corruptions. In doing so, we develop safeguards that minimize the impact of such corruptions on control algorithms operating in an online setting. For example, consider reinforcement learning agent that interacts with the real world environment to learn a near optimal policy mapping states to actions. For given state-action pair (s, a) while the true reward distribution may be stochastic, the observed reward associated with (s, a) will have inherent errors due to real world constraints. We would still like to have online learning algorithms that are robust to these errors and have small regret when compared the true reward distribution. These considerations
important in many applications such routing, dynamic pricing, autonomous driving and algorithmic trading. For example, a classic problem in routing involves choosing the best route in the presence of noise in the ETA estimation for any given route. Similarly, dynamic pricing algorithms need to be robust to adversarial spikes demand that may lead to unwanted price surges.
To formally study the above scenarios, consider online algorithm that proceeds sequentially, where in each step it makes a prediction and receives a reward. With probability e the observed reward is adversarially corrupted. More specifically, take inspiration from Huber's contamination

---

Under review as a conference paper at ICLR 2021
model that has been successfully applied to study various robust estimation problems in unsupervised learning (Huber, 2011; Tukey. 1975; Chen et al., 2018; Lai et al., 2016; Diakonikolas et al., 2019a). Assuming that P is the true distribution of the rewards, in our model the reward each step is generated from (1 - <) P + eQ where Q is an arbitrary distribution. Here e < is the noise rate. design online algorithms with near optimal regret, scaling with e, for three important cases: 1) multi-armed stochastic bandits, 2) linear contextual bandits, and 3) learning in finite state MDPs with stochastic rewards.
Under this model
Overview of results. We first consider the setting of stochastic multi-armed bandits. In this scenario there are arms numbered 1, .....k k. In the standard multi-armen bandit model, at each time step, the algorithm can pull arm i and get a real valued reward Tt generated from normal distribution with mean μ4 and variance o². ! We let i* represents the best arm, that is, pe. 2 pa, Vi. In the e-corrupted model we assume that the reward for pulling arm at time ł is F ~ (1 - -cW o²) + cQt, where Qt is an arbitrary distribution chosen by an adversary. We assume that the adversary has complete knowledge of the sequence of predictions and rewards up to time t - -1 as well as the true mean rewards and any internal state of the algorithm. Over time steps, the pseudo-regret of an algorithm A that pulls arms (i1, i2, ....... (r) is defined as
Reg = Mi. T E r.
(1)
Notice that while the adversary masks the true rewards with the corrupted ones, we still measure the overall performance with respect to the true reward distribution. While this setting has been studied in recent works (Lykouris et al., 2018: Gupta et al., 2019; Kapoor et al., 2019) they either assume corruptions of bounded magnitude, or provide sub-optimal performance guarantees (see the discussion in Section A). In particular, we provide the following near-optimal regret guarantee based on a robust implementation of the UCB algorithm (Auer et al., 2002).
Theorem (Informal Theorem). For the adversarially corrupted stochastic multi armed bandit problem, there is an efficient robust online algorithm that achieves a pseudo regret bounded by ((oVkT)) + O(geT").
The first term in the above bound is the optimal worst case regret bound achievable for the standard stochastic multi armed bandit setting (Auer et al., 2002). The second term denotes the additional regret incurred due the corruptions. Furthermore, the work of Kapoor et al. (2019) showed that additional oel" penalty is unavoidable in the worst case, thereby making the above guarantee optimal up to constant factor. Furthermore, as in the case of stochastic bandits with no corruptions, we can also obtain instance wise guarantees where the first term above depends on logarithmically in T and on an instance dependent quantity that captures how fare off are the arms as compared to the best one. See Appendix B for details.
Next we consider the case of contextual stochastic bandits. We study adversarially corrupted línear contextual bandits. In the standard setting of linear contextual bandits (Li et al., 2010) there are k & E TR.d At time i, the online algorithm
arms with ie associated (unknown) mean vectors vi,,.... sees context vectors zf.... 21 E Rd. one per arm. If the algorithm pulls arm i then the reward is generated from the distribution N( a/, o²). ). In the corrupted setting, we allow at certain time steps, the rewards to be corrupted by an adversary. In particular, we assume that the context vectors drawn i.i.d. from (O, Given the true context xf. in the stochastic bandits setting the observed reward be generated from rf ~ (1 e) xi. o²) + eQ, where Qt is an arbitrary distribution. Given sequence of arm pulls (i (f1...., ir) we define the pseudo-regret of algorithm as
let
Reg Σ E [max pz: x11 E > rc.l
(2)
In the above definition, the expectation is again taken over the distribution of contexts, the stochastic rewards and the internal randomness of the algorithm. For this case we provide the following near optimal regret guarantee
For simplicity we assume that the variance for each arm distribution is the same. Our results can also be casily extended to handle different variance and also handle the more standard setting where the true rewards are hounded in (0, 1).
2

---

Under review as a conference paper at ICLR 2021
Theorem (Informal Theorem). For the adversarially corrupted linear contextual malti armed bandit problem, there is an efficient robust online algorithm that achieves a pseudo regret bounded by Ólodydk (T) + OOo (LoL/e)))..
As in the of stochastic bandits, the first term is simply the regret bound for the standard linear contextual bandits problem achieved by the LinUCB algorithm (Chu et al., 20.1), The second term is the additional penalty due to the corruptions and is off from the lower bound of ev vv by a log(1/e) factor. Theorem 2 proved in Appendix C
Finally, we consider the most general setting of learning in Markov Decision Processes (MDPs) under corruptions. We consider Markov Decision Process (MDP) with state space 8, action space A and transition probabilities specified by P. If an action E A is taken from state s E 8, then the next state distribution is specified as p(s"(s, a). Moreover a stochastic reward rssa is received where Va.a N (Us,,a o²). The parameters Ussa and the transition probabilities are unknown the learning agent. We assume that the agent start in fixed state E 8 and given a policy т 8 + A, follows the trajectory ($1, (s1)), ($2, π (32))..... ...., (ST, (sT)). The total reward accumulated over time steps equals
T
R = Σ (ou)()))
(3)
Let π² be the optimal policy defined as n² arg max, E R[ Here the expectation is taken over the randomness in the state transitions, the stochastic rewards and the randomness in the policy itself. Given any other policy w we define the pseudo-regret
be
Reg. R- R[Rx).
(4)
In the above setting, the UCRL2 algorithm (Auer al., 2009) achieves regret of ((D))) T) where D is the diameter of the MDP. This is almost tight as there is a matching lower bound of 9 ((DD//|AATT))
We extend the above basic model with adversarial reward corruptions. In particular, we assume that at each time step i, given a state action pair (8,, 0z). the reward T Fec.a, observed by the agent is drawn from (1 - (Js., x²) + eQ.. Here e is the noise rate and Q: is an arbitrary distribution chosen by adversary. Furthermore, we will assume that the adversary can choose Qs using complete knowledge of the full history of the learning algorithm up to time t. Furthermore, by taking action from state s at time t, the observed transition is generated from the corrupted transition matrix described as (1 - <)p(s') |s, a) + eq' (s'|s, a), where again of is an arbitrary distribution chosen by an adversary. Our goal in this setting would be to aim for a regret guarantee of Ö (D]S) v [A[7)+ As in the previous two applications, we are interested in designing policies with low regret with respect to the observations from true MDP. For this case we provide the following near optimal guarantee.
Theorem (Informal Theorem). For the e-adversarially corrupted MDP model as described above, there is an there is an efficient robust online algorithm A that achieves a pseudo regret bounded by
Reg.
(|AT)) + O(oeT).
The first term corresponds the regret achieved by the UCRL2 algorithm (Auer et al., 2009) for the standard MDP setting. The second term is the additional penalty due to corruptions and is again unavoidable in the worst case.
Techniques. Our work combines classical no-regret learning algorithms with recent advances in designing robust algorithms for problems in unsupervised learning. For the case of stochastic multi-armed bandits we modify the standard UCB algorithm (Auer et al., 2002). The UCB algorithm works by maintaining optimistic estimates for the true mean reward of each arm. These optimistic estimates are obtained by using confidence intervals build around the average observed rewards. However, in the presence of adversarial corruptions, these estimates could be arbitrarily bad as we demonstrate in Lemma 1. Instead, we build confidence intervals around the median that is known to be robust to corruptions in Huber's 's model (Lai et al., 2016; Diakonikolas et al., 2018a). For the case of linear contextual bandits modify the popular LinUCB algorithm. The LinUCB algorithm
3

---

Under review as a conference paper at ICLR 2021
works by maintaining uncertainty estimates around the true vectors and picking arms according to these estimates. These estimates are built by solving a least squares problem at each time step. Under adversarial corruptions one would like to build these estimates in robust manner. However, a straightforward extension of the stochastic bandits case leads to a suboptimal additive penalty of (edTT). Instead, build upon the recent work of Diakonikolas al. (2019b) for robust high dimensional linear regression to build better uncertainty estimates resulting in the near optimal penalty of Ve log(()Zz
For the of learning in MDPs, first consider MDPs with deterministic transition and adver- sarially corrupted. Here we show that an extension of a UCB style exploration scheme achieves an optimal penalty of O by maintaining robust optimistic estimates of rewards at each state-action pair. We then extend this to the more general case where we modify the UCRL2 algorithm (Auer al., 2009) by maintaining robust estimates of the estimated rewards and transition probabilities.
2 STOCHASTIC BANDITS
In this section we consider the setting of stochastic multi armed bandits. Here one has arms. In each time step, a learning algorithm can pull arm and observe reward r; distributed as N (pe, a²). Let 2" be the arm with the highest expected reward. Then over I" time steps, the pseudo-regret of an algorithm A that pulls arms (i1, i2.................... .22.....)) is defined
Reg = pi T E
r.
(5)
There are many algorithms the near-optimal regret of Ō kT) in this setting. The most popular among them is the UCB algorithm (Auer et al., 2002; Slivkins, 2019). When the rewards are in [0, 1]. the UCB algorithm works by maintaining optimistic estimates of the average reward seen for each arm. Specifically, the estimate 7H, for arm at time / is defined as
log KT
Ra = pu. + 40
(6)
7i.t
Here Ar,e is the average reward observed for arm i till time step t. and ni,, is the number of times arm i has been pulled up to and including time step The UCB algorithm starts by pulling each arm once, and then at each time pulling the arm with the best current optimistic estimate as defined in (6).
UCB can be arbitrarily bad under ad adversarial corruptions. We now consider the adversarial model as defined in Section I where the e-corrupted rewards ï; are observed each time. In this case it easy that the regret of the UCB algorithm can be arbitrarily bad. This is formalized in the lemma below.
Lemma 1. For any c > O and E (to an adversary such that the pseudo-regret of the UCB algorithm is at least e T.
1), there exists stochastic multi armed bandit setting and
We next show simple modification of the UCB algorithm that will achieve near optimal regret of Ö(oVKT)) + O T). The algorithm maintains the following optimistic estimates
Hh.t = ius, + 40 log log(kT (max)
Here, Mmax an upper bound on the mean rewards, and fa., defined be the median reward obtained for arm i so far. The robust algorithm is sketched in Figure 1. For the robust UCB algorithm we have the following guarantee.
Theorem 4. Under the adversarially corrupted stochastic bandits model the algorithm Figure I achieves a reeudo-regret of ((aVkT) + O(aeT).
Proof. Is it known that the median is a more robust estimate than the mean. In particular, the result of Lai al. (2016) implies that with probability at least 1 Pmaz 7 for each arm and each time
4

---

Under review as a conference paper at ICLR 2021
Input: The k: arms, reward variance o².
1. Play each arm once and update the estimates as in (7).
2. For each subsequent time step i, pick the arm is with the highest estimate as defined in (7). Play arm i and update the estimates.
Figure 1: A robust UCB algorithm.
step & S T, it will hold that
log(A:
| - 14 & c()
(8)
Th.t
Conditioned on the above good event we have that for each time step and each arm
log KT
(e(KKPmmax)
14 O e) S The S pi + O(a e) 60
V
Thit
Next, consider arm that is pulled ni,r, times in total, where is the last time step when it is pulled. Then at time / it must hold that
log log(kTuu log(kTTmmax) Umax)
#4 + O( + 60
2 Yitts 2 ,tttt
(10)
nhitt
(11)
log (eT (maox)
+ (0)
pi- pi.
(12)
nii
Hence, conditioned on the good event, the total regret accumulated by playing arm is
niite (MiS - 14) S O(a -em,a + +0 1 (mm))
Using the fact that E, ni,e; S T with Jensen's 's inequality and that the good event happens with proba- bility at least 1 T4 we get that the total pseudo-regret is bounded by O KT log(kT
LoogkTTPmanl (max)) +
O(a e)T..
To contrast the above theorem with the performance of UCB we show the following stonger version of the lower bound in Lemma 1.
Lemma 2. For any e > 0 and e ( and an adversary such that the pseudo-regret of the UCB algorithm is at least e whereas the algorithm in Figure achieves vanishing regret of Ö(VKT).
+ there exists a stochastic multi armed bandit setting
Proof. We consider a set of l arms with means U2...., 14 E (1,4c) such that the difference between the best arm and all the other arms is at least 2c. Furthermore, we set the variance o² in the true Gaussian reward distribution to be 1. It is easy to see that the robust algorithm will achieve regret of ((KT)) from the guarantee of Theorem 4.
When running UCB, since = ((IvVT), with high probability the adversary will get perturb the rewards within the first O(VT) time steps. When this happens, the adversary will choose a reward of -L for the best arm and L for all the other arms with L > T. Hence, no matter which arm the UCB algorithm chooses at that time step. the best arm will always be suboptimal choice for the algorithm going forward since a large value of L will highly skew the mean reward estimates in the wrong direction for the best arm. As result, the pseudo regret of UCB will be at least T. I1
5

---

Under review as a conference paper at ICLR 2021
Input:
The state space 8, action space A, reward variance x².
1. Play each (s, a) E s x A once and update the estimates as in (20).
2. For episodes h = 1,2.... do:
Set start time of episode h to be the current time t.
For each (s,a) set (s, a)
For each (s, a) compute the previous count N₂. (s, (8) =rer 1(8, a, ar = 0).
For each 5, s', compute pa (s'1s,, a) using estimates up to time 1.
For each 8, compute En (8, o) robustly using estimates up to time
Let MA be the set of all MDPs that whose reward distribution A, and transition proba- bilities p satisfy
|og([S)|AA]]] (max)
[Fss, a) - (s, 20
(13)
Nn (s, a)
[S] (oog(A||T) Mmax)
[p( a) pr(l1,, a) S 20
(14)
Nn (s, a)
Find the best policy Ty that lies in Mn-
While un (s,, TA (ar)) < (s,, (a)
choose action ar according to my and update the corresponding ep values. Set 1=t+1.
Figure 2: A robust algorithm for general MDPs.
LEARNING IN MDPs
In this section study the most general application of our model in learning MDPs under adversarial corruptions. Recall from Section that we consider a Markov Decision Process (MDP) with state space S, action space A and transition probabilities specified by P. If action A taken from state E S, then the next state distribution is specified as p(s' s, a). Moreover stochastic reward rs.e is received where Ts.a N (Ms,a d²). We will consider scenario where at each time step, both the reward distribution and the transition matrix is corrupted with
probability. We study settings, one concerning MDPs with deterministic transitions (hence only corrupted rewards) followed by the case of more general MDPs. Due space constraints we discuss the case of deterministic MDPs in Appendix D.
Handling General MDPs
To design efficient algorithms for general MDPs. as before we will maintain robust estimates of the rewards and the transition probabilities and use these to guide the search for a near optimal policy. Our proposed algorithm is reminiscent of the UCRL2 algorithm (Auer al., 2009) and is sketched in the algorithm in Figure 2. For the general case we have the following guarantee. The proof can be found in Appendix E.
Theorem 5. The algorithm from Figure achieves a pseudo regret bounded by + ( Here Pmaax is the maximum mean reward of any state action pair in the MDP.
Reg = lo
4 EXPERIMENTS
We empirically validate the robustness of our algorithms to adversarial corruptions. In Section 1, we use a real world routing task to benchmark the performance the robust UCB in Figure when compared to the standard UCB algorithm. Similarly, for the MDP setting, in Section 4.2 we consider routing on randomly generated graphs to compare the performance of the robust UCRL2 in Figure 2 with that of UCRL.2. By varying the levels of corruption in the reward structure, find in both

---

Under review as a conference paper at ICLR 2021
Bdeadd UC3
UCB
340
200
61
(a) Regret vs step for weak (b) Regret vs step for (c) Regret vs c for weak ad- (d) Regret vs e for strong adversary (e = 0.3, strong adversary (c = 0.1, versary (5 = 10", step= adversary (6 = 10", step= 10*).
== 10
10%).
10").
Figure 3: Comparison of vanilla and robust versions of the UCB algorithm.
these settings that the learned policies and the regret incurred are far more resilient under our robust algorithms.
In our experiments, we consider two modes of adversarial corruptions:
weak adversary that corrupts rewards with U10, 60 for all actions, and
strong adversary that corrupts rewards with U[-6, 0] for the optimal actions and with U|00, 6] for others.
Here U[0, 5] denotes the uniform distribution in 6). Note that weak adversary shrinks the mean rewards for all actions towards 8/2; this makes the learning harder but otherwise preserves the ranking of actions. strong adversary on the other hand enhances bad actions and minimizes good ones, hence obfuscating the ranking of actions. For each of these modes, we vary the adversary's 's strength via probability and magnitude of the corruptions e and 6, respectively.
4.1 ROAD TRAFFIC ROUTING
We illustrate the robustness of algorithms introduced in Section 2. We consider routing application, where an agent needs to select one of many alternative routes between two locations. We use the road network and link travel times from the New York City Taxi dataset (Donovan & Work, 2017), which contains hourly average travel times on road segments across New York City. We focus on Manhattan for which dense data is available. We first sample N origin-destination pairs and then K alternative routes for each pair. Note that here routes correspond to arms. The competing routes here computed using a standard algorithm that utilizes bidirectional Dijkstra search and filters paths for diversity and near- meer-optimality. The distribution of costs for each action is given by observing the costs of the corresponding path in the historical data on every weekday 9am.
In our experiments, for N = 200 origin-destination pairs we considered K E [4, 6] alternative routes. For each source-destinttion pair, form stochastic bandit problem with the corresponding routes as available arms. We report the average performance across all bandit problems involving multiple source-destination pairs. We study for each adversary mode the effect of corruption probability <= 0, 0.1, 0.4 and magnitude ò E [10, 10000] on the regret of UCB and its robust counterpart. Figure 3a shows representative curve of the per step regret as function of the step count for weak adversary. Observe the significant improvement offered by robust UCB at each time step. Under strong adversary, the performance deteriorates for both algorithms, but the robust variant more resilient. For example, Figure 3b shows one such setting where UCB fails to learn while the robust version learns and the regret asymptotes. Finally, as expected, this pattern continues to hold for both adversary modes for range of and d; see Figures 3c and 3d.
4.2 LEARNING SHORTEST PATHS ON GRAPHS
We next illustrate the robustness of algorithms introduced in Section 3 here. We consider the problem of learning shortest paths on road network. We cast this problem as an MDP whose reward and transition structure must be learned while minimizing regret.
7

---

Under review as a conference paper at ICLR 2021
The road network is modeled as a graph G (V, E)) whose nodes represent locations and the edges E' the links con- necting them. The edge costs correspond to the link commute times. Given a destination E V while standing at a location E VV agent wishes to use that link (s, 8') E E which minimizes its overall commute time from s to t. That is, must lie on the shortest path from
t. We cast this as an MDP with the state (s, t) E 8 V x V and the action space (1,.... (l..... .), where = m Outdegree(v). In state (8, (), the first Outdegree(s) actions correspond to taking an edge (8, 8)), which changes the state to (s'.(); the remaining actions are invalid and preserve the state. Upon reaching the destination in state (t, t). we choose the next destination e' by cycling through the nodes in deterministic fashion and ran- domly sampling a start node s', leading to state (s', t'). This ensures that the states in 8 are connected and any trajectory is infinitely long. Finally, the reward is structured as follows: N Nuc, o²) for optimal actions (e.g. staying on the shortest path), N (un, o²) for suboptimal but valid actions, and N (ur,, o²) for invalid actions, where > PB РH. Observe that this aligns the agent's 's objective of maximizing the cumulative reward with finding the shortest path on the original graph G.
Figure 4: The Erdos-Renyi graph for MDP experiments. The edge thickness indicates its cost.
In our experiments, we use a 20-node Erdos-Rent Renyi graph (Erdōs & Rényi, 1960) with edge costs sampled from {1, 33 and maximum outdegree of 10, as shown in Figure 4. Thus our MDP has [8] 400 states and A = 10 actions in each state, yielding 4000 state-action pairs that need to be -2 and
assessed. For the random rewards, we set HaG = 0. MB -1, adversary mode weak and strong the rewards are corrupted with probability = 0, 00.,.....00 0.4 and magnitudes E [10, 10000]. For each setting, we employ two learning algorithms: the UCRL2 algorithm (Auer et al., 2009) and robust adaptation in Figure 2. For rigorous comparison, both implementations share all code except that for computing the empirical reward estimates. For this, in the robust version, the streaming median is estimated using a pool of 10,000 samples updated via reservoir sampling (Vitter, 1985).
Under each
Our results indicate that the algorithm is significantly more resilient to reward corruptions across a wide range of corruption probabilities and magnitudes 6. Under a weak adversary, as Figure 5a shows, increasing the frequency of corruption significantly deteriorates UCRL2 performance relative to our robust counterpart. Even so, both algorithms learn near-optimal policies as indicated by the regret values (per step regret near or greater than 1 Pp indicates that learning failed). Increasing the magnitude of corruption, however, completely breaks down the learning for vanilla UCRL2, while the robust version unaffected; see Figure 5b. Under a strong adversary, the performance both the algorithms deteriorates but the aforementioned trends continue to hold. UCRL2 fails to learn at = 0.1, while our robust version has near-optimal performance (Figure 5c). As before though, our robust version continues to learn well under high corruption magnitudes (Figure 5d). In general, we see that that the regret of robust UCRL2 better at nearly all time steps (Figure 5e). Further, the number of states in which the prescribed action differs from the optimal one is fewer and drops faster (Figure 5f).
5 CONCLUSIONS
In this work we initiated the study of robust algorithms for online learning settings. Several open directions come out of our work. It would be interesting to design robust algorithms for linear contextual bandits under more general distribution of context vectors. This would require new algorithms for performing robust regression under more general co-variate distributions.
An important distinction between our proposed robust algorithms and the classical no-regret coun- terparts is the amount of space usage. We need to store all the rewards (and contexts) observed up to time to compute good uncertainty estimates. It is interesting open question to reduce this gap. Finally, it would be interesting to study other scenarios in online learning under adversarial corruptions.
8

---

Under review as a conference paper at ICLR 2021
1.50
UCAL robust UCRL
UCAL
UCIL
0.19
roburt UCRL
Fooust UCAL
1.00
0.75
0.75
0.90
0.23
0.25
0.00
0.00
0.00
10000
Dct
(a) Regret vs e for weak adversary
(b) Regret vs 5 for weak adversary
(c) Regret vs E for strong adver-
(ō = 10, step= 10").
(c = 0.1, step= 10').
sary (5 = 10, step= 10').
UCAL robust UCAL
200
1.00
UCAL robust UCRL
0.75
200000 400000 GE0000 B05030 1000000
0.00
30
100
1000
10000
250han a00on6 (Atons aconon tonian6
Oeto
Shops
(1) Delta from Optimal Policy vs step for weak adversary (c 0.4, 6 10).
(d) Regret vs 8 for strong adver- sary (e 0.1, step= 10").
(e) Regret vs step for weak adver- sary (c 0.4, 10).
Figure 5: Comparison of vanilla and robust versions of the UCRL22 algorithm.
REFERENCES
Peter Auer, Nicolo Cesa-Bias Bianchi, and Yoav Freund Robert E Schapire. The non-stochastic multi- armed bandit problem. 2001.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235-256 2002.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement
learning. In Advances in neural information processing systems, pp. 89-96, 2009.
Sivaraman Balakrishnan, Simon S Du, Jerry Li, and Aarti Singh. Computationally efficient robust sparse estimation in high dimensions. In Conference on Learning Theory, pp. 169-212, 2017.
Moses Charikar, Jacob Steinhardt, and Gregory Valiant. Learning from untrusted data. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 47-60. ACM, 2017.
Mengjie Chen, Chao Gao, Zhao Ren, et al. Robust covariance and scatter matrix estimation under huber's s contamination model. The Annals of Statistics, 46(5):1932-1960, 2018.
Yu Cheng, Tlaas Diakonikolas, and Rong Ge. High-dimensional robust mean estimation in nearly- linear time. In Proceedings of the Thirfieth Annual ACM-SIAM Symposium on Discrete Algorithmss pp. 2755-227777 SIAM, 2019a
Yu Cheng, Ilias Diakonikolas, Rong Ge, and David Woodruff. Faster algorithms for high-dimensional robust covariance estimation. arXiv preprini arXiv: 2019b.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208-214, 2011.
Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 73-84. IEEE, 2017.
Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robustly learning gaussian: Getting optimal error, efficiently. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2683-2702. Society for Industrial and Applied Mathematics, 2018 8a.

---

Under review as a conference paper at ICLR 2021
Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Jacob Steinhardt, and Alistair Stewart. Sever: A robust mlea-algoor for stochastic optimization. arXiv preprint arXiv:180. 0eee.8033.0000 02810 2018b.
Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in digh-dimensions without the computational intractability. SIAM Journal on Computing, 48(2):442 864, 2019a.
Ilias Diakonikolas, Weihao Kong, and Alistair Stewart. Efficient algorithms and lower bounds for robust linear regression. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2745-2754, SIAM, 2019b.
B. Donovan and B. Work. Empirically quantifying city-scale transportation system resilience to extreme events. Transporiation Research Part C: Emerging Technologies, 79:333-346, 2017.
Paul Erdós and Alfréd Rényi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60, 1960.
John C Gittins. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society: Series B (Methodological), 41(2):148-164, 1979.
Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with 2019.
adversarial corruptions. arXiv preprint
Samuel B Hopkins and Jerry Li. How hard is robust mean estimation? arXiv:1903.07870, 2019.
arXiv preprint
Peter Huber. Robust statistics. Springer, 2011.
Sayash Kapoor, Kumar Kshitij Patel, and Purushottam Kar. Corruption-toleral bandit learning. Machine Learning, 108(4):687-715, 2019.
Adam Klivans, Pravesh K Kothari, and Raghu Mcka. Efficient algorithms for outlier-robust regression. arXiv preprint arXiv: /803.0321, 2018.
Pravesh K Kothari and David Steurer. Outlier-robust moment-estimation via sum-of-squares. Pro- ceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2018.
Kevin A Lai, Anup B Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 665-674. IEEE, 2016.
Lihong Li, Wei Chu, John Langford, and Robert Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings the 19th international conference World wide web, pp. 661-670, 2010.
Nick Littlestone and Manfred K Warmuth. The weighted majority algorithm. Information and computation, 108(2):212-261, 1994.
Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust to adversarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 114-122, 2018.
Thodoris Lykouris, Max Simchowitz, Aleksandrs Slivkins, and Wen Sun. Corruption robust explo- ration in episodic reinforcement learning, arXiv preprint 15f1::991106661 2019.
Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, and Pradeep Ravikumar. Robust estima- tion via robust gradient estimation. arXiv preprint arXiv:1802.06488, 2018.
Alcksandrs Slivkins. Introduction to multi-armed bandits, arXiv preprint arXiv:1904.0722. 2019.
Jacob Steinhardt, Moses Charikar, and Gregory Valiant. Resilience: A criterion for learning in the presence of arbitrary outliers. arXiv preprint arXiv: (et.: 2017.
10

---

Under review as a conference paper at ICLR 2021
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285 -224, 1933.
John W Tukey, Mathematics and the picturing of data. In Proceedings of the International Congress of Mathematicians, Vancouver, 1975, volume 2, pp. 523-531, 1975.
Jeffrey $ Vitter. Random sampling with a reservoir. ACM Transactions on Mathematical Software (TOMS), 11(1)377-57, 1985.


Reviews:
[{"review_id": "f8L96-ySvSv", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies regret minimizing algorithms for stochastic MABs, linear stochastic bandits, and finite-SA MDPs where epsilon-fraction of rewards/transitions are corrupted by noise of unbounded magnitude. In each case, the resultant regret bound has a epsilon-dependent linear term in T, in addition to standard T^0.5 term. In the latter two settings, the results are the first of their kind; in the first, they improve (in the linear term) over a known result. The general algorithmic approach here is to replace parameter/mean estimation with robust estimators (median, robust regression).\n\nStrengths:\n+ The regret bounds are novel, and offer an improvement upon known.\n+ The algorithms are fairly natural & modular.\n\nNot ideal:\n+ Lemma 1 could be more precise. In the current form, it is unclear if it is better or worse than epsilon * sigma * T. Sigma needs to be large enough for the proof to hold -- so comparisons to c*T remain uncertain. Similarly, at other places, the  writing could be a bit more rigorous.\n+ For stochastic linear bandits, typically the regret bound does not scale with the size (or number of vectors) in the decision set. The finitude of the latter is only needed for computational tractability. Why is such a dependence on K necessary here?\n+ Finally, could algorithms with tighter regret bounds (as in S^0.5, particularly) be adapted?\n\nTo what extent the work here is suitable for ICLR (finite SA MDPs, no func approx); I leave such considerations to the discretion of the other reviewers and the AC. My scores are independent of such aspects.", "extra_scores": {}, "extra_text": {}}, {"review_id": "cIgCsqf7AEt", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The work studies three online learning problems with corrupted rewards as the feedback. The three problems are the stochastic multi-armed bandit, the linear contextual bandit, and the reinforcement learning of the Markov Decision Process optimization.\n\nThe major contributions are three improved regret bounds for each of the problems, where the key to success is to replace the empirical mean in the arm/action selection scoring function by the median. Then, robust estimation bounds in the literature are leveraged to achieve the regret analysis. Experiments also support the theoretical findings.\n\nConcerns\n\nBesides the above positive contributions, following are some concerns:\n\n1. The target of optimization. All analyses bound the regrets with respect to the best arm/policy in the uncorrupted situation. This requires more elaboration to connect with the routing example in the introduction. If the actual routing time is the signal to measure the performance, then one does not need to take any ETA estimation into learning. If the actual routing time for the performance evaluation is the time affected by some noise, the regret definition makes no sense. It seems a reasonable situation is that the observations are corrupted but the performance feedback is not. The concern becomes stronger when it comes to the MDPs, as the trajectory of a policy in the corrupted environment will be different from that in the non-corrupted environment. It would be great if the authors can elaborate on the target chosen. Why is regret compared to the uncorrupted situation instead of the corrupted one? How does the trajectory from the corrupted observations affect or not affect the MDP analysis?\n\n2. The key modifications in the algorithms and the key inequalities in the regret analyses are from the literature. The analyses also mainly follow the similar steps in the previous works. Without observing novel technical contributions, the work is considered incremental.\n\n3. There is another work (http://proceedings.mlr.press/v32/seldinb14.html) also dealing with with the mixture of stochastic and the adversarial rewards which is worth mentioning or comparing.\n\n=====================\n\nPost Rebuttal\n\nI went through the authors' reply. My first concern is resolved by the reply. Form the authors' replies to all reviewers, I believe this is an incremental work. It is technically sound, but the lack of involved and novel technical contributions makes it more belong to an incremental work. Thus, I will keep my score unchanged.", "extra_scores": {}, "extra_text": {}}, {"review_id": "4m6MYm8OCS6", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nAs the title of this paper suggests, the authors look at online learning in three settings of increased generality (stochastic multi-armed bandits, linear contextual bandits and general MDPs), with the added feature that an adversary may corrupt reward (and in the case of MDPs, transition probability) distributions. Corruption may occur on a given turn with probability $\\epsilon$, thoguh in general, the degree of corruption an adversary can incur is unbounded. In this model, the authors study regret as the performance metric of their online algorithms, and they provide algorithms for each setting where their regret guarantees can be decomposed into a component which is comporable to state-of-the-art solutions in the no-corruption model, and a second term which depends on the corruption rate, $\\epsilon$, and quantified the degree to which ``power'' of the adversary can increase worst-case regret. \n\nTo give a brief overview of the algorithmic techniques presented, for the stochastic MAB setting, the authors propose a variant of UCB, whereby the baseline average representing historical performance of an arm is its median rather than the mean of its rewards (which makes sense as a more robust statistic when faced with corruptions), as well as an upper confidence bound similar to UCB. For MDPs, the proposed algorithm maintains a list of feasible policies (those with transitions and rewards ``close'' to what has been observed), and acts optimally according to this feasible set of MDPs (these details are still a bit unclear to me) for a certain number of turns, thus updating the set of feasible MDPs in the process. \n\nFinally, the authors validate their models using simluations on real-world data (road traffic routing in NYC where an agent has to pick a travel route from point A to B, coresponding to arms in the MAB), and on simulated data for the MDP (Erdos Reny Random graphs of 20 nodes where an agent has to find the shortest path of the graph). \n\n\nReasons for Score:\n\nI agree with the authors that it is relevant to explore adversarial information production in ML, and this model furthers our knowledge in terms of how to adapt successful online algorithms to adversarial scenarios. Furthermore, the fact that the paper covers online settings of increasing generality is of use in terms of techniques, and indeed the theoretical contributions are interesting in their own right.\n\n\nQuestions / Points of Discussion:\n-In general I think it would be great to hear more details on the linear contextual bandits algorithm at the crux of Thm 2. I understand that space is limited, but more details expanding on the line: \"Instead we build upon the recent work of Diakonikolas...\" could also help transition between the MAB to MDP\n-I wonder whether there can be more of a discussion on the dependence of $\\mu_{max}$ in your regret bounds. \n-I am still a bit confused on the MDP algorithm on page 6. First of all, you mention that $M_h$ is the set of all \"close\" MDPs to what has been observed, and then $\\pi_h$ is called the best policy that \"lies in $M_h$\". What does this exactly mean? The policy is not an MDP, but I'm guessing it is the best policy against a worst-case MDP from that family of consistent MDPs? This could be clarified a bit\n-In relation to this MDP algorithm, I am also curious what its runtime is. It seems to me that it would be computationally expensive to find say the best policy against a worst-case consistent MDP from $M_h$, but this could be clarified as well. \n-A final question for the MDP algorithm is also with respect to the initial sampling of all state-action pairs. What does the algorithm do if this is not possible (in a degenerate MDP), or if a single $(s,a)$ is only attainable with extremely low probability?\n-As for the simulations, I am curious why such a simple model of adversarial noise was used?:\n    -I like that the power of the adversary is bounded by $\\delta$, this should be further studied in the theoretical framework\n    -On the other hand, the fact that corruptions are either unilateral for all actions, or all but the best action (with a uniform distribution of corruptions), seems to be very limited in the scope of the theoretical framework. Could it be that the algorithms are performing well empirically because of this limited adversarial framework?  \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "2b5bYF1LnGW", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies online learning under adversarial corruptions in three settings in the regret minimization setup. The first setting is the classical stochastic multi-armed bandit. The second one is contextual stochastic bandit, and finally, the third is learning in MDPs. In each setting, it is assumed that the rewards (and transition distributions) are corrupted by an adversary with probability $\\epsilon$, for some fixed $\\epsilon$. For each setting, the paper presents a no-regret algorithm that is robust against such corruption. \n\nMain Comments:\n\nThe paper studies interesting online learning problems, which parallels several recent studies on bandits with corruptions. The considered corruption model is however different from the ones in the existing literature. \n\nFor each of the studied settings, the paper presents a variant of the classical algorithm for that setting, which is tailored to be robust against $\\epsilon$-corruption. For example, for classical stochastic bandits, the paper presents a variant of UCB that achieves a sublinear regret against $\\epsilon$-corruption. This is a strong aspect of the paper, as the presented algorithms have similar designs and complexities to their corruption-oblivious counterparts.  \n\nThe paper is overall well-written and is clearly presented. The paper, however, could still benefit from polishing, and in particular, by fixing typos listed below. \n\nOn the technical side, I have some comments:\n\n- For the three settings considered in the paper, it turns out that the price to pay for being robust against $\\epsilon$-corruption is an additive penalty of $O(\\epsilon T)$ to the regret. This further implies that the interesting regime happens when $\\epsilon$ is $O(1/\\sqrt{T})$, or decays as $O(1/\\sqrt{t})$, since otherwise all the reported regret bounds would scale as $O(T)$ no matter how small a “fixed” $\\epsilon$ is. This way, Lemma 1 renders useless as it assumes a fixed $\\epsilon$.\n\n- The presented algorithms mildly require some prior knowledge of $\\mu_{\\max}$. While for bounded rewards, this is no longer the case for, e.g., Gaussian distributed rewards, as $\\mu_{\\max}$ can be arbitrarily large. This is relevant in particular for the contextual stochastic bandit setting. In addition, for classical stochastic bandits, UCB is presented for Gaussian rewards.   \n\n\n- In the stochastic bandit setting, a median estimator for mean rewards is used instead of the empirical estimates. However, it is not crystal clear to me where in the proof you used the properties of such a median estimator. Is it only in the concentration of good events?\n\n- It would be also tempting to use median estimators in the MDP setting too. Why did you use there only empirical estimates for mean rewards (and transition probabilities?)\n\n- There is a mistake in the analysis for the MDP setup (which is straightforward to fix): In the right-hand side of (31) and (32), a term of $\\widetilde {\\mathcal O}(\\sqrt{T})$ is missing; see the analysis of UCRL2 in (Jaksch et al., 2010). \n\nOverall I do not see the presented results of enough significance to make the paper eligible for ICLR. \n\nSome typos:\n\np. 2: depend on logarithmically in $T$ => logarithmically depend on $T$ \n\np. 2: let $i^*$ represents => … represent\n\np. 3: agent start => agent starts \n\np. 3: from true MDP => … the true MDP\n\np. 3: confidence intervals build => … built\n\np. 4: Is it known => It is …\n\np. 11: A recent of => A recent work of \n\np. 11: foe => for\n\np. 12: time spend => time spent\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The discussion with the expert reviewers reached the consensus that the paper lacks in novel *technical* contributions, and as such it does not meet the bar for a theory-oriented paper at ICLR.
Decision: Reject