Robust Q-Learning under Corrupted Rewards
Sreejeet Maity Aritra Mitra

Gr-IoU: Ground-Intersection over Union for Robust Multi-Object Tracking with 3D Geometric Constraints
    Keisuke Toida10009-0006-4873-3651 Naoki Kato20009-0004-3815-0829 Osamu Segawa20009-0000-2469-6098 Takeshi Nakamura20009-0001-4991-3383 Kazuhiro Hotta10000-0002-5675-8713

    September 9, 2024
==============================================================================================================================================================================

[1]The authors are with the Department of Electrical and Computer Engineering, North Carolina State University. Email: {smaity2, amitra2}@ncsu.edu.
§ ABSTRACT  Recently, there has been a surge of interest in analyzing the non-asymptotic behavior of model-free reinforcement learning algorithms. However, the performance of such algorithms in non-ideal environments, such as in the presence of corrupted rewards,  is poorly understood. Motivated by this gap, we investigate the robustness of the celebrated Q-learning algorithm to a strong-contamination attack model, where an adversary can arbitrarily perturb a small fraction of the observed rewards. We start by proving that such an attack can cause the vanilla Q-learning algorithm to incur arbitrarily large errors. We then develop a novel robust synchronous Q-learning algorithm that uses historical reward data to construct robust empirical Bellman operators at each time step. Finally, we prove a finite-time convergence rate for our algorithm that matches known state-of-the-art bounds (in the absence of attacks) up to a small inevitable O(ε) error term that scales with the adversarial corruption fraction ε. Notably, our results continue to hold even when the true reward distributions have infinite support, provided they admit bounded second moments.  





§ INTRODUCTION

We study reinforcement learning (RL) within a Markov decision process (MDP) setting where an agent sequentially interacts with an environment to maximize a long-term cumulative value function. To achieve this goal without knowledge of the dynamics of the MDP, the agent plays an action at each time, receives a reward in the form of feedback from the environment, and then transitions to a new state. This process then repeats itself. Using the sequence of observed rewards, the agent learns to take “better" actions over time. In this context, one of the most widely studied model-free RL algorithms is the celebrated Q-learning algorithm of Watkins and Dayan <cit.> that  iteratively estimates the optimal state-action value function associated with the MDP. Viewing Q-learning through the lens of stochastic approximation (SA) theory, a rich body of work has investigated the asymptotic performance of this algorithm, i.e., its behavior as the number of iterations goes to infinity <cit.>. More recently, there has been a shift of interest towards providing a finer non-asymptotic/finite-time analysis of different RL algorithms <cit.>. That said, the literature discussed above exclusively pertains to scenarios where the reward feedback received from the environment is always accurate, i.e., it is generated by the true reward distribution of the underlying MDP. However, such an idealistic assumption is unlikely to hold when one seeks to deploy RL algorithms in real-world harsh environments. As such, since feedback in the form of rewards is crucial for the overall  decision-making process, our main goal in this paper is to investigate the following questions: 

    Q1. Are existing model-free RL algorithms robust to perturbations in the rewards?

   Q2. Can we obtain reliable value-function estimates under corrupted rewards?
  

Contributions. In response to the aforementioned questions, the main contributions of this work are as follows. 

∙ Problem Formulation. To systematically investigate the question of robustness of RL algorithms, we consider a strong-contamination reward attack model where an adversary with complete knowledge of the MDP and the learner's observations is allowed to arbitrarily perturb ε-fraction of the rewards acquired over time. This attack model is directly inspired from the robust statistics literature <cit.>, where a small fraction of the data points in a static data set can be corrupted by an adversary. 

∙ Vulnerability of vanilla Q-Learning. In Theorem <ref>, we prove that even under a weaker attack model than the one described above, the basic Q-learning algorithm converges to the fixed point of a perturbed Bellman operator, where the perturbation is due to reward contamination. By constructing an explicit example, we next establish in Theorem <ref> that this incorrect fixed point can be arbitrarily far away from the optimal Q function. Furthermore, this continues to be the case even when the corruption fraction ε is small. 

∙ Robust Q-Learning Algorithm. Motivated by the above findings, we develop a novel robust Q-learning algorithm in the synchronous sampling setting <cit.>, i.e., when a generative model provides independent samples for all state-action pairs. The key idea in our algorithm is to use historical data of rewards for each state-action pair to construct a robust empirical Bellman operator in each iteration. To do so, we leverage the recently developed robust trimmed mean-estimator in <cit.>, along with a novel dynamic thresholding technique.  

∙ Near-optimal Rates. Providing a rigorous finite-time convergence analysis of our algorithm is non-trivial since one needs to simultaneously contend with the benign randomness introduced by sampling and deliberate arbitrary adversarial injections. Nonetheless, in Theorem <ref>, we establish a high-probability ℓ_∞-error-rate of Õ(1/√(T))+O(√(ε)), where T is the number of iterations. In the absence of corruption (i.e., ε=0), this rate matches those in recent works <cit.>. Furthermore, we also provide an informal argument that the additive O(√(ε)) term appears to be inevitable.

Finally, we note that our proposed approach does not require the true reward distributions to be bounded or “light-tailed", i.e., we do not need to make any assumptions of sub-Gaussianity on the reward models. Instead, we only need the reward distributions to admit finite second moments. Thus, in principle, even the true reward samples (i.e., the inliers) can come from heavy-tailed distributions. This makes it non-trivial to tell apart clean reward data from corrupted rewards. Nonetheless, the approach developed in this paper overcomes this challenge.  


Related Work. The synchronous Q-learning setting we consider here has been extensively studied in several works <cit.>. More recently, its finite-time performance has been characterized in <cit.>. Asynchronous versions of Q-learning have also been analyzed  in <cit.>. 

Reward corruption models similar to what we consider here have been studied in the multi-armed bandits (MAB) literature  <cit.>, where an attacker with a finite budget can corrupt the rewards seen by the learner in a small fraction of the rounds. However, our setup, algorithm, and proof technique fundamentally differ from the MAB framework. That said, our main result in Theorem <ref> has the same flavor as the findings in the above bandit papers: one can recover the performance bounds in the absence of corruptions up to an additive term that captures the attacker's budget; in our case, this is the additive O(√(ε)) term. Finally, some recent works have studied perturbed versions of Markovian stochastic approximation algorithms <cit.>, where the perturbations are due to communication constraints (e.g., delays and compression). Unlike the structured perturbations in these papers, the perturbations injected by the adversary in our work can be arbitrary.  



§ BACKGROUND AND PROBLEM FORMULATION

 
MDP Model. We consider a Markov Decision Process (MDP) denoted by ℳ=(𝒮, 𝒜, P, R, γ), where 𝒮 is a finite state space, 𝒜 is a finite action space, P is a set of Markov transition kernels, R is a reward function, and γ∈ (0,1) is the discount factor. Upon playing action a at state s, the state of the MDP transitions to s' with probability P(s'|s,a), and a scalar stochastic immediate reward r(s,a) with distribution R(s,a) is observed. We define R(s,a) ≜𝔼[r(s,a)] to be the expected value of the random variable r(s,a), and assume that the (noisy) rewards are bounded, i.e., ∃r̅≥ 1 such that |r(s,a)| ≤r̅, ∀ (s,a) ∈S×A.[The assumption of bounded rewards is made here only to convey the key ideas in their simplest form. Later, in Section <ref>, we will see how our techniques naturally allow for reward distributions with finite second moments that can have potentially unbounded support.] We consider deterministic policies π: 𝒮→𝒜 that map states to actions. The “goodness" of a policy π is captured by a γ-discounted infinite-horizon cumulative reward V_π: S↦ℝ given by:

    V_π(s) = 𝔼[∑_t=0^∞γ^t r(s_t,a_t)  |   s_0 = s],

where s_t is the state at time t, a_t = π(s_t) is the action played at time t, and the expectation is taken w.r.t. the randomness in the states and rewards. We will refer to V_π(s) as the value function corresponding to state s. Given this premise, the goal of the learner is to find a policy π that maximizes V_π(s) simultaneously for all states s ∈S. It is well known that such a deterministic optimal policy π^* does exist <cit.>. Let us now briefly discuss how such a policy can be obtained when the MDP is known. To that end, we define the state-action value function Q_π:S×A↦ℝ as follows: 

    Q_π(s, a) = 𝔼[∑_t=0^∞γ^t r(s_t,a_t)  |   (s_0, a_0) = (s, a)].

Now let Q^* = Q_π^* denote the optimal state-action value function. Then, Q^* is the unique fixed point of the Bellman operator 𝒯^*: ℝ^|S|  × |A|→ℝ^|S|  × |A| given by:

    (𝒯^*Q)(s,a) = R(s,a) + γ𝔼_s' ∼P(· | s,a)[max_a' ∈𝒜 Q(s',a')].

In other words, T^* (Q^*) = Q^*. The Bellman operator satisfies the following contraction property ∀ Q_1, Q_2 ∈ℝ^|S| × |A|:

    ‖𝒯^* (Q_1) - 𝒯^* (Q_2)‖_∞≤γ‖ Q_1 - Q_2‖_∞.


An immediate consequence of the above property is that the iterative update rule Q_t+1 = T^*(Q_t) guarantees exponentially fast convergence to Q^*. This is precisely the idea used in dynamic programming <cit.>. In our RL setting, however, the dynamics of the MDP are unknown, rendering the above idea infeasible. We now discuss a synchronous version <cit.> of the seminal Q-learning algorithm that finds Q^* without knowledge of the MDP dynamics. 

Synchronous Q-learning. The synchronous Q-learning algorithm operates in iterations t=0, 1, …, where in each iteration t, the learner maintains an estimate Q_t of Q^*. The synchronous setting assumes the existence of a generative model such that in each iteration t, the learner gets to observe the following objects for each state-action pair (s,a) ∈S×A: (i) a new state s_t(s,a) drawn independently from P(·| s,a); and (ii) a stochastic reward r_t(s,a) drawn independently from R(s,a). Using this information, for each (s,a) ∈S×A, the learner updates Q_t(s,a) as follows: 

    Q_t+1(s,a) = (1- α_t)Q_t(s,a) + α_t  (T_tQ_t)(s,a),

where {α_t} is a suitable step-size sequence, and T_t:ℝ^|S| × |A|→ℝ^|S| × |A| is an empirical Bellman operator constructed from observations at iteration t, and defined as

    (T_tQ)(s,a) ≜ r_t(s,a) + γmax_a'∈𝒜Q(s_t(s,a),a'), ∀ Q ∈ℝ^|S| × |A|,

where r_t(s,a) ∼R(s,a), and s_t(s,a) ∼P(·| s,a). The term “synchronous" arises from the fact that in each iteration t, the learner gets to observe independent data samples for every state-action pair. As such, every component of the vector Q_t can be updated at iteration t, i.e., synchronously. Viewing synchronous Q-learning as a stochastic approximation (SA) scheme, one can show that under suitable assumptions on the step-size sequence {α_t}, Q_t → Q^* with probability 1 <cit.>. Our goal in this paper is to provide a finite-time analysis of synchronous Q-learning when the observed rewards can be potentially corrupted by an omniscient adversary. We formally describe our attack model below. 

Strong-Contamination Reward Attack Model. We consider an adversary that has complete knowledge of the MDP model and the observations of the learner in every iteration. Using this information, in each iteration t, the adversary can perturb the entire reward set {r_t(s,a)}_(s,a) ∈S×A arbitrarily. However, to make the problem meaningful, we will associate an attack budget ε∈ [0, 1/2) with the attacker: for each t ∈ℕ, the attacker is allowed to corrupt the reward sets in at most ε-fraction of the first t iterations. Our attack model is directly inspired by the strong contamination model from the robust statistics literature <cit.> where an adversary is allowed to arbitrarily perturb at most ε-fraction of the data points in a set; in our context, the reward observations constitute the data. We note that our model above is more powerful than the classical Huber attack model <cit.> where each data point can be corrupted with probability ε. In particular, the Huber model would imply that ε t reward sets are corrupted only on an average, for each t∈ℕ. In the sequel, we will use y_t(s,a) to denote the observed reward for state-action pair (s,a) in iteration t. In an iteration t where there is no corruption, y_t(s,a)=r_t(s,a), ∀ (s,a) ∈S×A. 

 Given the strong-contamination reward attack model and a failure probability δ∈ (0,1), our goal is to generate a robust estimate Q_t of the optimal value function Q^* such that with probability at least 1-δ, the ℓ_∞-error ‖Q_t - Q^* ‖_∞ is bounded from above by an error-function e(t,ε) that has optimal dependence on the number of iterations t and corruption fraction ε. 


In the next section, we show that the vanilla synchronous Q-learning algorithm fails to achieve this goal. In Section <ref>, we then proceed to develop our proposed robust algorithm.



§ MOTIVATION

In this section, we will show that even with a small attack budget ε, an adversary can cause the vanilla Q-learning algorithm to converge to a point in ℝ^|𝒮|×|𝒜| arbitrarily far away from Q^*. To do so, it suffices to consider the Huber attack model <cit.>. Accordingly, in each iteration t, we toss a biased coin with probability of heads 1-ε. If the coin lands heads, the observed reward y_t(s,a) is drawn from the true reward distribution R(s,a), ∀ (s,a) ∈S×A. If it lands tails, y_t(s,a) is drawn from an arbitrary distribution C(s,a), ∀ (s,a) ∈S×A. Concretely, y_t(s,a) ∼ (1-ε) R(s,a) + εC(s,a). Under this Huber attack model, suppose the perturbed expected reward for (s,a) is given by R̃_c(s,a) = 𝔼[y_t(s,a)]. We have the following simple result. 

 Consider the vanilla synchronous Q-learning algorithm in Eq. (<ref>) with rewards perturbed based on the Huber attack model described above. If the step-size sequence satisfies α_t ∈ (0,1) with  ∑_t=1^∞α_t = ∞ and ∑_t=1^∞α_t^2 < ∞, then with probability 1, Q_t →Q̃^*_c, where Q̃^*_c is the unique fixed point of the perturbed Bellman operator 𝒯̃^*_c: ℝ^|S|  × |A|→ℝ^|S|  × |A| defined by 

    (𝒯̃^*_c Q)(s,a) = R̃_c(s,a) + γ𝔼_s' ∼P(· | s,a)[max_a' ∈𝒜 Q(s',a')].




It suffices to simply note that under the Huber attack model, we end up running the synchronous Q-learning algorithm on a new MDP (𝒮, 𝒜, P, R̃_c, γ) that differs from the original MDP only in its reward function, where R̃_c is the perturbed reward function defined earlier. The claim then follows directly by appealing to the asymptotic convergence of synchronous Q-learning based on SA theory <cit.>. 


Theorem <ref> tells us that under the Huber model, an adversary can bias the iterates generated by vanilla Q-learning towards the fixed point Q̃^*_c=𝒯̃^*_c(Q̃^*_c) of a perturbed Bellman operator 𝒯̃^*_c. However, it does not provide an explicit lower bound on the gap ‖Q̃^*_c -Q^* ‖_∞. Our next result reveals that this gap can be arbitrarily large. 



 

There exists an MDP with finite state and action spaces for which the gap 

‖Q̃^*_c -Q^* ‖_∞ can be arbitrarily large under the Huber attack model. 



We will prove this result by constructing an explicit example that is inspired from <cit.>. To that end, consider the MDP in Fig. <ref>. We first describe the reward model without attacks. In state s =1, we get a deterministic reward d if a = L and -d if a = R, where d > 0 is a positive constant. For states s ∈{2,3}, irrespective of the chosen action, the reward is deterministically 1. Similarly, for states s ∈{4,5}, the reward is deterministically 0. Now consider a Huber attack model where the attacker only perturbs rewards in state s=1 as follows: for state-action pair (1, L) (resp., (1, R)), the observed reward is d (resp., -d) with probability 1-ε and -C (resp., C) with probability ε. Here, C > 0 is an attack signal that we will design carefully later. This immediately yields the following perturbed reward functions: R̃_c(1,L) = (1-ε)d-ε C and R̃_c(1,R)= -(1-ε)d+ε C. We now proceed to compute Q^* and Q̃^*_c. First, observe that given our choice of attack and MDP model, Q^* and Q̃^*_c only differ at state 1. Now using the Bellman optimality operators in (<ref>) and (<ref>), it is easy to verify that Q^*(s,a)=0 for s∈{4,5}, a ∈{L,R}, and Q^*(s,a)=(1-γ p)^-1 for s∈{2,3}, a ∈{L,R}. Next, one can similarly check that 

    Q^*(1,L)    = d + β,   Q̃^*_c(1,L) = (1-ε) d - ε C + β
    
    Q^*(1,R)    = -d + β,   Q̃^*_c(1,R) = - (1-ε) d + ε C + β,

where β = p γ (1-γ p)^-1. Now pick the corruption signal C as ((2-ε)d + κ) ε^-1, where κ >0 is a tunable parameter. With this choice, we  have Q̃^*_c(1,L)= -d - κ + β and Q̃^*_c(1,R)= d + κ + β, yielding ‖Q̃_c^* - Q^* ‖_∞ = max_a ∈𝒜|Q̃_c^*(1,a) - Q^*(1,a) | = 2d + κ. The claim of the theorem then follows from noting that κ can be chosen arbitrarily by the attacker. Additionally, since d, κ > 0, it is not hard to see that under the attack constructed above, the optimal action at state 1 also gets flipped: without the attack, the optimal action is L; under the attack, it is R.  


Collectively, Theorems <ref> and <ref> reveal the vulnerability of the vanilla Q-learning algorithm to the Huber attack model. These findings directly motivate the robust algorithm we will develop in the next section. 



§ – Q-LEARNING ALGORITHM




Motivated by the vulnerability of vanilla Q-learning to reward-corruption attacks - as revealed in the previous section - we will develop a novel robust variant of the model-free synchronous Q-learning algorithm in this section. The basic idea behind our approach will be to use historical reward data collected for each state-action pair to construct a robust empirical Bellman operator in each iteration. To achieve this objective, we will drawn upon tools from the robust statistics literature; in particular, our algorithm will employ the univariate trimmed mean estimator developed in <cit.> for robust mean estimation in the face of a strong-contamination model. Let us first briefly describe this estimator, and then explain how it can be used for our purpose. 

∙ Univariate Trimmed-Mean Estimator. The robust mean estimator in <cit.> - outlined as Algorithm <ref> - takes as input a confidence parameter δ, a known corruption fraction ε, and a corrupted data set generated as follows. Consider a clean data set comprising of M independent copies of a scalar random variable Z with mean μ_Z and variance σ^2_Z. An adversary corrupts at most ε M of these copies, and the resulting corrupted data set is then made available to the estimator. The estimation process involves splitting the corrupted data set into two equal parts, denoted by Z_1, …, Z_M/2, Z̃_1, …Z̃_M/2. One of the parts is used to compute certain quantile levels for filtering out extreme values (line 2 of Algorithm <ref>). The robust estimate μ̂_Z of μ_Z is obtained by averaging the data points in the other part, with those data points falling outside the estimated quantile levels truncated prior to averaging (line 3 of Algorithm <ref>). In what follows, we will use [ {Z_i}_i ∈ [M], ε, δ}] to succinctly describe the output of Algorithm <ref>. 

The following result characterizes the performance of Algorithm <ref>, and will be invoked by us in our subsequent analysis.

 <cit.> 

Consider the trimmed mean estimator in Algorithm <ref>. Suppose ε∈ [0,1/16), and let δ∈ (0,1) be such that δ≥ 4 e^-M/2. Then, there exists an universal constant C, such that with probability at least 1-δ,

    |μ̂_Z - μ_Z| ≤ Cσ_Z(√(ε)+√(log(4/δ)/M)).




We now describe how the estimator in Algorithm <ref> can be used to generate robust estimates of the optimal Q function. 

∙ ε-Robust Q-Learning Algorithm. Our proposed robust Q-learning algorithm - outlined in Algorithm <ref> - starts with an initial Q-function estimate Q_0, and takes as input a corruption fraction ε, and a failure probability δ∈ (0,1). In each iteration t, for each (s,a) ∈S×A, the learner gets to observe s_t(s,a) drawn independently from P(·| s,a) (as in the standard synchronous Q-learning setting), and a potentially corrupted version of r_t(s,a) ∼R(s,a) denoted by y_t(s,a). Here, the corruption adheres to the strong contamination reward attack model specified in Section <ref>. Our strategy to safeguard against adversarial reward contamination is twofold: reward-filtering and thresholding. We describe these ideas below. 

Reward-Filtering: First, instead of directly using y_t(s,a) to update Q_t(s,a), we instead compute a robust estimate of the expected reward R(s,a) for state-action pair (s,a) by using the univariate trimmed mean estimator in Algorithm <ref>. This is done by invoking Algorithm <ref> with (i) data set {y_k(s,a)}_0 ≤ k ≤ t comprising of the history of reward observations for (s,a), (ii) the corruption fraction ε, and (iii) a finer (relative to δ) confidence parameter δ_1=δ/(2 |S| |A| T). We denote the operation carried out by Algorithm <ref> succinctly by using the  function in line 6 of Algorithm <ref>. Let the output of this operation be denoted r̃_t(s,a). While it is tempting to use r̃_t(s,a) to update Q_t(s,a), one needs to exercise caution as we explain next. 

Reward-Thresholding. From Theorem <ref>, a couple of points are worth noting about the  guarantee afforded by Algorithm <ref>. First, the guarantee holds only if the number of data samples exceeds T_lim, where 
 
    T_lim≜2 log(4/δ_1).


 

Second, the guarantee is not deterministic; instead, it only holds with high probability. For technical reasons that will become apparent later in our analysis, we need the sequence {Q_t} of iterates generated by our algorithm to be uniformly bounded deterministically. However, the above discussion suggests that simply using the output of the  function to perform updates will not suffice to achieve this goal. As such, we employ a second layer of safety by carefully defining a threshold function as follows: 

    G_t=
          2 ,    0 ≤ t ≤ T_lim
    
          C (√(log(4/δ_1)/t)+ √(ε))+,    t ≥ T_lim+1

where C is the universal constant in Eq. (<ref>). 





[->, >=stealth', auto, thick] (-3,0.5) – (-1.5,0.5) node[midway,above] y_1(s,a);
[->, >=stealth', auto, thick] (-3,-0.1) – (-1.5,-0.1) node[midway,above] y_2(s,a);
at (-2.25,-0.3) ⋮;
[->, >=stealth', auto, thick] (-3,-0.7) – (-1.5,-0.7) node[midway,below] y_t(s,a);
[black,thick,fill=black] (-4,-0.3) rectangle (-3.6,0.1);

[thick] (-1.3,-1.1) rectangle (1.7,1);
at (-3.3,-0.1) :=;
at (-3.9,-0.5) ;
[thick] (-1.0,-0.20) – (-0.8,-0.20); 
[thick] (-0.8,-0.20) – (-0.6,-0.20);
[thick] (-0.6,-0.20) – (0.2,-0.20);
[thick,dotted] (0.2,-0.20) – (1,-0.20);
[thick] (1,-0.20) – (1.25,-0.20);


in -1.0,-0.8,-0.6 
    [red] (,-0.20) circle (1 pt); 

in -0.4,-0.2,0,0.2,0.4,0.8 
    [blue] (,-0.20) circle (1.5pt); 

in 1, 1.25 
    [red] (,-0.20) circle (1 pt); 



[dotted,purple,semithick, dash pattern=on 2pt off 1pt] (-0.50,-0.7) rectangle (0.9,0.3);
[below] at (0.15, 0.9) ;


[->, >=stealth', auto, thick] (1.75,0) – (3.5,0) node[midway,above] r̃_t(s,a);
[thick] (3.6,-0.35) rectangle (4.45,0.35);
[] at (4.05, 0)G_t;
[below] at (4.10, -0.40) ;


    
  [thick,black] (-0.7,-6.3) rectangle (1.1,-5.3);
  [below] at (0.2, -5.6) ;  
    
    
    [thick,black] (-0.8,-1.75) rectangle (1.2,-2.75);
    [right] at (-0.3,-2.25) ;
    
    
    [thick, >=stealth'] (1.3,-2.3) -> (2.6,-2.3);
    [thick, >=stealth', auto] (2.6,-2.3) -> (2.6,-5.8);
    [right] at (2.6,-4.1) ;
    [black,thick,fill=black] (-2.2,-3.7) rectangle (-1.8,-4.1);
    [thick,->, >=stealth', auto] (2.6,-5.8) -> (1.2,-5.8);
    [thick, >=stealth', auto] (-0.8,-5.6) -> (-2.0,-5.6);
    [thick, >=stealth', auto] (-2.0,-5.6) -> (-2.0,-2.4);
    [right] at (-1.9,-4.5);
    [right] at (-1.9,-3.2);
    [right] at (0.4,-3.2)  {r̃_t(s,a)};
    [right] at (-1.98,-4.8)  {y_i(s,a), ∀ i ∈ [t]};
    [right] at (-1.76,-3.88);
    [thick,->, >=stealth', auto] (-2.0,-2.4) -> (-0.9,-2.4);
    [thick, >=stealth', auto] (-2.4,-6.0) -> (-0.8,-6.0);
    [thick, >=stealth', auto] (-2.4,-2.0) -> (-2.4,-6.0);
    [left] at (-2.5,-4) ;
    [thick,->, >=stealth', auto] (-2.4,-2) -> (-0.9,-2);
[below] at (0.14, -7.5) Fig.1: Schematic Diagram of ε- Q-Learning Algorithm at time instant t ∈ [T].;





Whenever the output of the  function exceeds G_t in magnitude, we control it via the thresholding operation in line 8 of Algorithm <ref>. This ensures boundedness of iterates. When adequate data samples have not been collected, i.e., t≤ T_lim, we cannot rely on the statistical bound from Theorem <ref>; hence, we use the crude bound  on the rewards to design G_t. However, once enough samples have in fact been collected, we would expect the output of  to concentrate around R(s,a) with high-probability. This motivates the choice of G_t for t ≥ T_lim+1 based on Eq. (<ref>). As we argue later in Lemma <ref>, the above choice of G_t ensures that for t ≥ T_lim+1, the condition in line 7 of Algorithm <ref> gets violated with high probability, and r̃_t(s,a) remains the output of the  function instead of the more conservative estimate in line 8. This turns out to be crucial for achieving tight rates. After filtering and thresholding, Q_t(s,a) is updated as 

    Q_t+1(s,a)    = (1- α)Q_t(s,a) + α(r̃_t(s,a) + γmax_a'∈𝒜Q_t(s_t(s,a),a')).


This completes the description of Algorithm <ref>. To state our main result concerning its finite-time performance, let us define d_t ≜‖ Q_t - Q^*‖_∞. Our main result is as follows.

 (Robust Q-learning bound) Suppose the corruption fraction satisfies ε∈ [0,1/16). Then, given any δ∈ (0,1), the output of Algorithm <ref> with step-size α = log T/(1-γ)T  satisfies the following bound with probability at least 1-δ:

    d_T ≤d_0/T + O( /(1-γ)^5/2log T/√(T)√(log(|𝒮||𝒜|T/δ)) +  √(ε)/1-γ).



We defer the proof of this result to Section <ref>. 

Discussion. To parse the guarantee in Theorem <ref>, let us simplify the bound in the theorem to obtain 

    d_T ≤d_0/T+Õ( r̅/(1-γ)^5/2√(T))_T_1 + O( √(ε)/1-γ)_T_2.

From the above display, we note that our proposed Robust Q-Learning algorithm yields a high-probability ℓ_∞ sample-complexity bound that features two dominant terms: term T_1 captures the behavior of the algorithm in the absence of attacks, while term T_2 captures the effect of reward corruption. The dependence of term T_1 on both 1/(1-γ) and the number of iterations T exactly matches that in the recent works <cit.> and <cit.>. Thus, in the absence of attacks, our result is consistent with prior art. In the presence of strong-contamination attacks, our algorithm guarantees convergence to Q^* up to an additive error that scales as O(r̅√(ε)). We conjecture that such a term is unavoidable. To see why, consider a trivial MDP that comprises of just one state s and one action a. In this case, the problem of learning Q^* essentially boils down to estimating the mean R(s,a) using a set of noisy and corrupted data points. With this reduction, we can now invoke fundamental lower bounds from the robust mean-estimation literature which tell us that an error of Ω(σ√(ε)) is unavoidable <cit.> when the clean noise samples have variance σ^2 . Since the noisy rewards in our setting come from the interval [-, ], ^2 is precisely the variance-proxy for our setting. While the above argument can be formalized, we omit it here due to space constraints. To sum up, our work provides the first near-optimal guarantee for Q-learning under a strong reward corruption model.  



Notice that our proposed algorithm uses knowledge of the bound r̅ on the rewards to design the dynamic threshold in Eq. (<ref>). At this stage, one might consider a much simpler algorithm that simply ignores rewards that have magnitude larger than r̅. Unfortunately, such a strategy is not guaranteed to work when the true reward distributions have infinite support. However, in Section <ref>, we will explain that with minor modifications to Algorithm <ref>, one can continue to handle reward distributions with infinite support, under the assumption of bounded second moments. 

 



§ PROOF OF THEOREM <REF>

In this section, we will provide a detailed proof of our main result, namely Theorem <ref>. There are two sources of error in our update rule: one due to the randomness (i.e., noise) that originates from the sampling process, and the other due to reward-poisoning by the adversary. As such, the first step in our analysis is to set up an error-decomposition that clearly separates out the statistical  terms in our update rule from those originating due to adversarial contamination. To that end, with some simple algebra, observe that our proposed Robust Q-learning update rule in Eq. (<ref>) takes the following form:
     
    Q_t+1(s,a) = (1- α)Q_t(s,a) 
        + α(R(s,a) +γ𝔼_s' ∼ P(· | s,a)[max_a' ∈𝒜 Q_t(s',a')])_(𝒯^* Q_t)(s,a) + α [r̃_t(s,a)- R(s,a)]_ℰ_t(s,a)
        + α(γmax_a'∈𝒜Q_t(s_t(s,a),a')- γ𝔼_s' ∼ P(· | s,a)[max_a' ∈𝒜 Q_t(s',a')])_𝒟_t(s,a),

where we used the definition of the Bellman operator in Eq. (<ref>). Stacking up the components Q_t(s,a), ℰ_t(s,a), and 𝒟_t(s,a) for each state-action pair (s,a) ∈𝒮×𝒜 into vectors Q_t, ℰ_t, and 𝒟_t ∈ℝ^|𝒮| |𝒜|, respectively, the display in Eq. (<ref>) takes the following compact form: 

    Q_t+1 = (1-α)Q_t + α(𝒯^* (Q_t)  +ℰ_t+𝒟_t).

Now subtracting Q^* from both sides of Eq. (<ref>), using 𝒯^* (Q^*) =Q^*, and rolling out the resulting equation yields: 

    Q_t+1-Q^*     = (1-α)^t+1(Q_0-Q^*) 
        + ∑_k=0^tα (1-α)^t-k (𝒯^* (Q_k) - 𝒯^* (Q^*))+∑_k=0^tα (1-α)^t-kℰ_k
        + ∑_k=0^tα (1-α)^t-k𝒟_k.

Defining d_t ≜‖ Q_t - Q^*‖_∞, ∀ t ≥ 0, and taking the infinity norm on both sides of Eq. (<ref>), we obtain:

    d_t+1≤ (1-α)^t+1d_0 + γ∑_k=0^tα (1-α)^t-k d_k + A_1,t + A_2,t,
    
where 

    A_1,t≜‖∑_k=0^tα (1-α)^t-k𝒟_k‖_∞, A_2,t≜‖∑_k=0^tα (1-α)^t-kℰ_k‖_∞.

To arrive at Eq. (<ref>), we used the contraction property of the Bellman operator in Eq. (<ref>) to infer that 
  ‖𝒯^* (Q_k) - 𝒯^* (Q^*)‖_∞≤γ‖ Q_k - Q^*‖_∞≤γ d_k. We have thus proved the following lemma. 

 (Error-Decomposition) 

The robust update rule in Eq. (<ref>) satisfies the error-bound in Eq. (<ref>) for all t≥ 0. 


The remainder of our analysis will focus on providing bounds for the terms A_1,t and A_2,t featuring in Eq. (<ref>). 

∙ Bounding the Effect of Noise. We first turn our attention to bounding the term A_1,t in Eq. (<ref>). To that end, let ℱ_t denote the σ-algebra generated by {Q_k}_0 ≤ k ≤ t. Now for each (s,a) ∈𝒮×𝒜, since s_t(s,a) is generated independently from P(·|s,a), and Q_t is ℱ_t-adapted, it is easy to see that 𝔼[𝒟_t(s,a)|ℱ_t]=0. Thus, ∑_k=0^tα (1-α)^t-k𝒟_k has a martingale structure that we can hope to exploit by appealing to the Azuma-Hoeffding bound for martingales. However, this requires care, as we describe next. To apply Azuma-Hoeffding in its standard form, we need to argue that the martingale difference sequence {D_t(s,a)} is uniformly bounded with probability 1. This difference sequence features Q_t, which, in turn, contains the filtered reward r̃_t(s,a); see Eq. (<ref>). Since r̃_t(s,a) depends on the sequence of observations {y_k(s,a)}_0 ≤ k ≤ t, and some of these observations can be arbitrarily corrupted by the adversary, we need to carefully justify the boundedness of 𝒟_t(s,a). Unfortunately, Theorem <ref> cannot help us in this regard since it only provides a bound that holds with high-probability; however, we seek a bound that holds almost surely. As revealed by our next result, this is precisely where the additional robustness afforded by the trimming step in line 8 of Algorithm <ref> will play a crucial role. To simplify the analysis, we will assume without loss of generality that Q_0=0.




 (Boundedness of Iterates)  The following is true for the iterates generated by Algorithm <ref>: 

    | Q_t(s,a) |≤3C/1-γ, ∀ (s,a) ∈𝒮×𝒜, ∀ t ≥ 0,

where C is the universal constant in Eq. (<ref>).
    
We will prove this result via induction. Fix any (s,a) ∈S×A. Since Q_0=0, the claim of the lemma holds trivially at t=0. This completes the base case of induction. Now suppose the bound claimed in the lemma holds for all 0 ≤ k ≤ t. To show that it also holds at iteration t+1, we first need an estimate on |r̃_t(s,a)|. From lines 7 and 8 of Algorithm <ref>, it is evident that |r̃_t(s,a)| ≤ G_t, where G_t is the trimming radius in Eq. (<ref>). Thus, to control |r̃_t(s,a)|, it suffices to bound G_t. Now from the definition of T_lim in Eq. (<ref>), and the fact that ε∈ (0,1), it is easy to see from Eq. (<ref>) that G_t ≤ 3C , ∀ t ≥ T_lim+1; here, we used C ≥ 1. Since G_t = 2 for 0 ≤ t ≤ T_lim, we conclude |r̃_t(s,a)| ≤ 3C , ∀ t ≥ 0. To proceed with the induction step, let us now observe from Eq. (<ref>) that 
        
    | Q_t+1(s,a) |≤ (1 - α) | Q_t(s,a) | + α|r̃_t(s,a) + γmax_a'∈𝒜Q_t(s_t(s,a),a')|
       ()≤(1 - α) | Q_t(s,a) | + α(|r̃_t(s,a)| + γmax_a'∈𝒜| Q_t(s_t(s,a),a')|) 
       ()≤ (1 -α) 3C/1-γ + α( 3C + γ3C/1-γ) 
        = (1 -α) 3C/1-γ + α3C/1-γ = 3C/1-γ,

where for (a), we used the triangle inequality, and for (b), we used the induction hypothesis in tandem with the previously established fact that |r̃_t(s,a)| ≤ 3C , ∀ t ≥ 0. This completes the induction step and the proof. 
       


Armed with Lemma <ref>, we can now appeal to the Azuma-Hoeffding Theorem for martingales to control the noise-induced term A_1,t. To do so, we note that a sequence of random variables Z_1, Z_2, Z_3, … is called a martingale difference sequence w.r.t. some filtration G_t if, for each t, it holds that 𝔼[Z_t| G_t-1]=0. To keep the paper self-contained, we recall the following version of Azuma-Hoeffding from <cit.>. 

 (Azuma-Hoeffding)

Let Z_1, Z_2, Z_3, … be a martingale difference sequence with |Z_i| ≤ c_i for all i ∈ℕ, where each c_i is a positive real. Then, for all λ≥ 0:

    ℙ(|∑_i=1^n Z_i| ≥λ) ≤ 2e^-λ^2/2∑_i=1^nc_i^2.



We have the following result that controls the effect of noise in our update rule. 


 (Noise Bound) With probability at least 1- δ/2, the following bound holds simultaneously ∀ t ∈ [T]: 
    
    ‖∑_k=0^tα (1-α)^t-k𝒟_k‖_∞≤6Cγ/1-γ√(2αlog(4|𝒮||𝒜|T/δ)),

where 𝒟_k is as defined in Eq. (<ref>).
    
Let us fix a state-action pair (s,a) ∈S×A, and a time-step t ∈ [T]. We have already argued that 𝔼[𝒟_t(s,a)|ℱ_t]=0, i.e., {D_k(s,a)} is a martingale difference sequence. Furthermore, from Lemma <ref>, we have 

    |𝒟_t(s,a)|   = |γmax_a' ∈𝒜 Q_t(s_t(s,a), a') - γ𝔼_s' ∼ P(· | s, a)max_a' ∈𝒜 Q_t(s', a') |
       ≤γmax_a' ∈𝒜|  Q_t(s_t(s,a), a') | + γ𝔼_s' ∼ P(· | s, a)max_a' ∈𝒜| Q_t(s', a') |
       ≤6Cγ/1-γ≜Δ.

Noting that {α (1-α)^t-kD_k(s,a)} is also a martingale difference sequence, and applying Lemma <ref>, we note that the following bound holds with probability at least 1-δ_2: 
        
    |∑_k=0^tα(1-α)^t-k𝒟_k(s,a)|    ≤Δ√( 2 α^2 log(2/δ_2) ∑_k=0^t (1-α)^2(t-k))
       ≤Δ√( 2 α^2 log(2/δ_2) ∑_k=0^t (1-α)^(t-k))
       ≤Δ√( 2 α^2 log(2/δ_2) ∑_i=0^∞ (1-α)^i)
        = Δ√( 2 αlog(2/δ_2)),

where for the second inequality, we used (1-α) < 1. Using the above fact, and union-bounding over all (s,a) ∈S×A, we conclude that the following bound holds with probability at least 1-δ_2|S| |A|: 
        
    ‖∑_k=0^tα (1-α)^t-k𝒟_k‖_∞   = max_(s,a) ∈𝒮×𝒜|∑_k=0^tα (1-α)^t-k𝒟_k(s,a)|
       ≤Δ√( 2 αlog(2/δ_2)).

Union-bounding over all t∈ [T], we conclude that the bound in Eq. (<ref>) holds simultaneously for all t ∈ [T] with probability at least 1-δ_2 |𝒮||𝒜| T. The claim of the lemma now follows by setting δ_2 = δ/(2|𝒮||𝒜| T).        



With the above developments, we now have a handle over the term A_1,t in the main error bound of Eq. (<ref>). 




∙ Bounding the Effect of Adversarial Contamination. The effect of adversarial contamination gets manifested in the term A_2,t of Eq. (<ref>). The following key result helps us control this term. 

  (Adversarial Corruption Bound) Suppose ε∈ [0,1/16). Then, with probability at least 1- δ/2, the following bound holds simultaneously ∀ t ∈ [T]:

    ‖∑_k=0^tα (1-α)^t-kℰ_k‖_∞≤ 8 α C √(T  log(8|𝒮||𝒜|T/δ))+C√(ε),

where ℰ_k is as defined in Eq. (<ref>).
 We will split our analysis into two separate cases.

Case I. Consider first the case when t ∈ [T_lim]. Fix any (s,a) ∈S×A. Recalling that ℰ_t(s,a) = r̃_t(s,a)- R(s,a), we have

    |E_t(s,a)| ≤ |r̃_t(s,a)| + |R(s,a)| ≤ G_t + ≤ 3,

where we used |r̃_t(s,a)| ≤ G_t, ∀ t ≥ 0 (based on lines 7 and 8 of Algorithm <ref>), and Eq. (<ref>). We also used the fact that since the uncorrupted reward r_t(s,a) ∈ [-, ], the expected value of r_t(s,a), namely R(s,a), can have magnitude no larger than . Thus, for t ∈ [T_lim], we have 

    |∑_k=0^tα(1-α)^t-kℰ_k(s,a)|    ≤∑_k=0^tα(1-α)^t-k|ℰ_k(s,a)|
       ≤ 3 α∑_k=0^t(1-α)^t-k
       ≤ 3 α∑_k=0^T_lim(1-α)^t-k
       ≤ 3 α T_lim.

Since the above argument applies identically to every (s,a) ∈S×A, we conclude that for every t ∈ [T_lim], 

    ‖∑_k=0^tα (1-α)^t-kℰ_k‖_∞   = max_(s,a) ∈𝒮×𝒜|∑_k=0^tα (1-α)^t-kℰ_k(s,a)|
       ≤ 3 α T_lim.

Note that the above bound holds deterministically. 

Case II. Now suppose T_lim+1 ≤ t ≤ T, and fix a (s,a) ∈S×A as before. To control E_t(s,a) in this case, we wish to use the bound from robust mean estimation in Theorem <ref>. To that end, we make the following observations. First, under our synchronous sampling model, the reward samples {r_k(s,a)}_0 ≤ k ≤ t are i.i.d. random variables with mean R(s,a). Second, since r_t(s,a) ∈ [-, ], ∀ t≥ 0, the variance of these samples is at most ^2. Third, under the assumptions on our attack model, at most ε-fraction of the samples in {r_k(s,a)}_0 ≤ k ≤ t can be corrupted by the adversary. Thus, invoking Theorem <ref>, we note that the output r̃_t(s,a) of the  function in line 6 of Algorithm <ref> satisfies the following bound with probability at least 1-δ_1:

    |r̃_t(s,a) - R(s,a)| ≤C (√(log(4/δ_1)/t)+ √(ε))_(*).

Now consider an event X where the above bound holds simultaneously for all (s,a) ∈S×A, and for all T_lim+1 ≤ t ≤ T. Union-bounding over all state-action pairs and time-steps in the above interval, we note that event X has measure at least 1- δ_1 |S| |A| (T-T_lim) > 1 - δ_1 |S| |A| T. For the remainder of the analysis, we will condition on the event X. Since |R(s,a)| ≤, observe that given our choice of G_t in Eq. (<ref>), the output r̃_t(s,a) of the  function satisfies |r̃_t(s,a)| ≤ G_t on event X. Thus, the condition in line 7 of Algorithm <ref> gets violated and line 8 gets bypassed. In other words, r̃_t(s,a) remains as in line 6 of Algorithm <ref>, and we obtain that |E_t(s,a)| is bounded from above by (*) on event X, implying 
    
    |∑_k=T_lim+1^tα (1-α)^t-kℰ_k(s,a)|≤∑_k=T_lim+1^tα (1-α)^t-k|ℰ_k(s,a) |
       (a)≤ C ∑_k=T_lim+1^tα (1-α)^t-k( √(log(4/δ_1)/k) + √(ε))
       ≤α C √(log(4/δ_1))∑_k=T_lim+1^t1/√(k) +  α C ∑_k=0^∞ (1-α)^k√(ε)
       (b)≤2α C √(T log(4/δ_1)) +  C√(ε).

For (a), we used |E_t(s,a)| ≤ (*) on event X, and for (b), we used a standard trick of bounding a sum by an integral to control the first term in the inequality. Combined with our analysis for Case 1, we then have on the event X:

    |∑_k=0^tα(1-α)^t-kℰ_k(s,a)|    ≤|∑_k=0^T_limα(1-α)^t-kℰ_k(s,a)|
       +|∑_k=T_lim+1^tα(1-α)^t-kℰ_k(s,a)|
       ≤ 3αr̅ T_lim +  2α C √(T log(4/δ_1)) +  C√(ε)
       (a)≤ 3αr̅√(T_lim)√(T) + 2α C √(T log(4/δ_1)) +  C√(ε)
       (b)≤8 α C √(T log(4/δ_1)) +  C√(ε),

where for (a), we used T_lim≤ T, and for (b), we used the expression for T_lim in Eq. (<ref>), and simplified using C≥ 1. We conclude that on the event X, the bound in Eq. (<ref>) applies simultaneously to all t ∈ [T], and all (s,a) ∈S×A. The claim of the lemma now follows immediately by picking δ_1 = δ/(2 |S| |A| T).



We are now ready to complete the proof of Theorem <ref>.
 (Proof of Theorem <ref>) Our claim is that with probability at least 1-δ, the following bound holds simultaneously ∀ t∈ [T]∪{0}:

    d_t ≤ (1-α(1-γ))^t d_0 + W/1-γ, where


    0.7!W ≜6Cγ/1-γ√(2αlog(4|𝒮||𝒜|T/δ)) + 8 α C √(T  log(8|𝒮||𝒜|T/δ))+C√(ε).

We remind the reader here that d_t = ‖  Q_t - Q^* ‖_∞. We will prove the above claim via induction. Trivially, the induction claim holds deterministically for t=0. Now from Lemmas <ref> and <ref>, let us note that there exists an event - say Y - of measure at least 1-δ on which A_1,t+A_2,t≤ W, ∀ t ∈ [T], where A_1,t and A_2,t are as defined in Eq. (<ref>). We will condition on the “good" event Y for the remainder of the analysis. As our induction hypothesis, suppose on the event Y, the claim in Eq. (<ref>) holds for all k ∈ [t]. To argue that it also holds for iteration t+1, we invoke the error decomposition in Lemma <ref> to obtain:

    d_t+1   ≤ (1-α)^t+1d_0 + γ∑_k=0^tα (1-α)^t-k d_k + A_1,t + A_2,t
       ≤ (1-α)^t+1 d_0 + αγ∑_k=0^t (1-α)^t-k(1-α(1-γ))^k d_0_(**)
        + αγ W/1-γ∑_k=0^t (1-α)^t-k  + W
       ≤ (1-α)^t+1d_0 + (**) + αγ W/1-γ∑_k=0^∞ (1-α)^k + W
        =  (1-α)^t+1d_0 + (**) + γ W/1-γ + W
        = (1-α)^t+1d_0 + (**) + W/1-γ,

where for the second inequality, we used the induction hypothesis in tandem with the fact that on the event Y, A_1,t+A_2,t≤ W, ∀ t ∈ [T]. Now observe that

    (**)    = αγ (1-α)^t d_0 ∑_k=0^t(1+ αγ/(1-α))^k
       =(1-α)^t+1d_0 [ (1+ αγ/(1-α))^t+1-1           ]
       =(1-α (1-γ))^t+1d_0 - (1-α)^t+1d_0.

Combining the above display with Eq. (<ref>) establishes the induction claim for iteration t+1. We have essentially argued that the bound in Eq. (<ref>) holds for all t∈ [T] on the event Y. The claim we set out to prove follows by noting that Y has measure at least 1-δ. All that remains now is to simplify the bound in Eq. (<ref>) with t=T and α set to log T/(1-γ)T. Using 1-x ≤exp(-x), ∀ x ≥ 0, we obtain (1-α(1-γ))^T d_0 = d_0/T. Furthermore, a bit of simple algebra reveals that

    W/1-γ = O( /(1-γ)^5/2log T/√(T)√(log(|𝒮||𝒜|T/δ)) +  √(ε)/1-γ).

This completes the proof of Theorem <ref>. 




§ TACKLING UNBOUNDED REWARD DISTRIBUTIONS

In this section, we will significantly relax the assumption of the rewards being bounded. In fact, we will not even require the true reward distributions to be sub-Gaussian. Let us now formalize the reward model. In the absence of corruptions, as before, an agent gets to observe a noisy reward r(s,a) ∼R(s,a) upon playing action a in state s. Moreover, R(s,a) ≜𝔼_r(s,a) ∼R(s,a)[r(s,a)], and 𝔼_r(s,a) ∼R(s,a)[(r(s,a)- R(s,a))^2] ≤σ^2. In words, playing action a in state s generates a noisy reward random variable r(s,a) with mean R(s,a) and variance upper-bounded by σ^2. The key departure from the model in Section <ref> is that we no longer require r(s,a) to be bounded; this naturally rules out the possibility of using trivial thresholding algorithms that ignore rewards falling outside a certain interval since the reward distribution R(s,a) can potentially have an infinite support. Moreover, since we only require finiteness of the second moment, the reward distributions can be heavy-tailed. This makes it particularly challenging to distinguish between a corrupted reward sample and a clean reward sample drawn from the tail of the distribution. Nonetheless, with little to no modifications to our developments thus far, we can handle the challenging setting described above. To make this precise, we make the basic assumption that the means of all reward functions are uniformly bounded[Note that this should not be confused with the noisy reward realizations being uniformly bounded.]; without such an assumption, one cannot even guarantee the finiteness of the state-action value functions. Accordingly, let B ≥ 1 be such that |R(s,a)| ≤ B, ∀ (s,a) ∈S×A. If we re-define r̅ as max{B, σ}, and plug in this definition of r̅ into the threshold in Eq. (<ref>), then with no further modifications to the algorithm or analysis, our main result in Theorem <ref> goes through. This follows by simply revisiting the argument in Case II of Lemma <ref>. The main message here is that even in the absence of corruptions, one can employ our proposed algorithm to handle heavy-tailed rewards, i.e., the additional robustness to heavy-tailed rewards comes essentially for free with our approach. 








§ NUMERICAL RESULTS

    




§ CONCLUSION

We studied model-free synchronous Q-learning under a strong-contamination reward attack model, and developed a robust algorithm that provides near-optimal guarantees. There are several immediate directions that are part of our ongoing work: establishing fundamental lower bounds, considering the effect of asynchronous sampling, and studying the function approximation setting. In addition, the design of our algorithm requires knowledge of an upper bound on the means and variances of the reward distributions. It would be interesting to see if one can continue to achieve the bounds in this paper without such knowledge; this appears to be quite non-trivial. 
unsrt


