Corruption-Robust Offline Reinforcement Learning with General Function Approximation
Authors: Chenlu Ye
Rui Yang
Quanquan Gu
Tong Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: offline RL; adversarial corruption; general function approximation
TL;DR: We propose corruption-robust algorithms that incorporate uncertainty-related weights to address offline RL under adversarial corruption and general function approximation.

Abstract: We investigate the problem of corruption robustness in offline reinforcement learning (RL) with general function approximation, where an adversary can corrupt each sample in the offline dataset, and the corruption level $\zeta\geq0$ quantifies the cumulative corruption amount over $n$ episodes and $H$ steps. Our goal is to find a policy that is robust to such corruption and minimizes the suboptimality gap with respect to the optimal policy for the uncorrupted Markov decision processes (MDPs). Drawing inspiration from the uncertainty-weighting technique from the robust online RL setting \citep{he2022nearly,ye2022corruptionrobust}, we design a new uncertainty weight iteration procedure to efficiently compute on batched samples and propose a corruption-robust algorithm for offline RL. Notably, under the assumption of single policy coverage and the knowledge of $\zeta$, our proposed algorithm achieves a suboptimality bound that is worsened by an additive factor of $\mathcal O(\zeta \cdot (\text CC(\lambda,\hat{\mathcal F},\mathcal Z_n^H))^{1/2} (C(\hat{\mathcal F},\mu))^{-1/2} n^{-1})$ due to the corruption. Here $\text CC(\lambda,\hat{\mathcal F},\mathcal Z_n^H)$ is the coverage coefficient that depends on the regularization parameter $\lambda$, the confidence set $\hat{\mathcal F}$, and the dataset $\mathcal Z_n^H$, and $C(\hat{\mathcal F},\mu)$ is a coefficient that depends on $\hat{\mathcal F}$ and the underlying data distribution $\mu$. When specialized to linear MDPs, the corruption-dependent error term reduces to $\mathcal O(\zeta d n^{-1})$ with $d$ being the dimension of the feature map, which matches the existing lower bound for corrupted linear MDPs. This suggests that our analysis is tight in terms of the corruption-dependent term.

Corruption-Robust Offline Reinforcement Learning with General Function Approximation
Chenlu Ye*
The Hong Kong University of Science and Technology cyeab @ coabenotntt..u..kk
Rui Yang*
Quanquan Gu
The Hong Kong University of Science and Technology ryangam@comm connec.ststtt
University of California, Los Angeles
agu@cs.ucla.edi.
Tong Zhang
The Hong Kong University of Science and Technology tongzhang @ ust.hk
Abstract
We investigate the problem of corruption robustness in offline reinforcement learn- ing (RL) with general function approximation, where adversary can corrupt each sample in the offline dataset, and the corruption level Ç 2 0 quantifies the cumulative corruption amount over episodes and H steps. Our goal is find policy that is robust to such corruption and minimizes the suboptimality gap with re- spect the optimal policy for the uncorrupted Markov decision processes (MDPs). Drawing inspiration from the
technique from the robust on- we design new uncertainty weight iteration procedure efficiently compute on batched samples and propose a cnrruption-robuss algorithm for offline RL. Notably, under the assumption of single policy coverage and the knowledge of Ç, our proposed algorithm achieves a suboptimality bound that is worsened by an additive factor of O (CC(A, F, z. )) (C(FF ()) 1/ due the corruption. Here CC(A, Z.!) the coverage coefficient that depends on the regularization parameter X, the confidence set F, and the dataset 2 and C(², μ)) is coefficient that depends on F and the underlying data distribution μ. When specialized linear MDPs, the -eruption-deeeddett error term reduces to (((dn=) with d being the dimension of the feature map, which matches the existing lower bound for corrupted linear MDPs. This suggests that our analysis is tight in terms of the corruption-dependen term.
line RL setting | 1551
Introduction
Offline reinforcement learning (RL) has received tremendous attention recently because it tackle the limitations of online RL in real-world applications, c.g., healthcare [45] and autonomous driving [35. where collecting online data is risky, expensive and even infeasible. By leveraging batch of pre-collected datasets, offline RL aims to find the optimal policy that is covered by the dataset without further interaction with the environment. Due the restriction of the offline dataset, the utilization of pessimism in the face of uncertainty is widespread []]
53
40
[6] and plays central role in
These authors contributed equally this work.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Notably, these theoretical works demonstrate that a single-policy coverage sufficient guarantee sample efficiency.
providing theoretical guarantees for efficient learning 24 36 14
51
56
57
63 52
In this paper, we study offline RL under adversarial corruption and with general function approxi- mation. Adversarial corruption refers to adversarial attacks on the reward functions and transition dynamics on the data at each step before the learner can access the dataset. The learner only knows the cumulative corruption level and cannot tell whether the corruption occurs at each data point. Our corruption formulation subsumes the model misspecification [2 and the fixed fraction of data contamination [60] as special cases. Various real-world problems are under the threat of ad adversarial corruption, such as chatbots misled by discriminative or unethical conversations [2] 61], and au- tonomous vehicles tricked by hacked navigation instructions or deliberately contaminated traffic signs
12. On the other hand, general function approximation (approximating the value function with a nonlinear function class, such as deep neural networks) plays pivotal role in modern large-scale RL problems, such as large language model TC. robotics
22 and medical treatment (8 Recent works
have established different frameworks to explore the minimal structure condition for the function class that enables sample efficiency 19 47
64]. In particular, Wang et al. 47 leverage the 33 and construct the least squares value iteration (LSVI) framework,
M 21 6
concept of eluder dimension which establishes optimism at each step for online RL.
For adversarial cortuption and general function approximation, a significant amount of research has focused on the online setting. However, offline RL in this setting is still understudied due to restricted coverage conditions and lack of adaptivity. One notable exception is Zhang et al. [60]. which assumes e-fraction of the offline dataset is corrupted, and their algorithm suffers from a suboptimal bound on the corruption term. Our work moves a step further and achieves corruption robustness under the LSVI framework 47 in offline RL with general function approximation by generalizing the uncertainty weighting technique [18 55 We also propose an algorithm robust to additional known distribution shift. Due to space limit, we defer it to Appendix C We summarize our contributions as follows:
We formally define the corruption level in offline RL. With knowledge of the corruption level, we design algorithm that draws inspiration from the PEVI algorithm [24] and the uncertainty- weighting technique. The uncertainty for each data point, serving as the bonus function, is quantified by its informativeness with respect the whole dataset. We propose the uncertainty weight iteration algorithm to calculate the weights efficiently and prove that the output, an approximation of the uncertainty, is sufficient to control the corruption term.
Theoretically, our proposed algorithm enjoys a suboptimality bound of Õ(H /CI/4(In N)) (CC(((C((F (4))=1/4p 1/44 episode length, is the number of episodes, N is the covering number, CC is the coverage coefficient, and C(F,u) is the coefficient depicting how well the underlying data distribution μ explores the feature space, and ft is the confidence set. The porruptionddepedder term reduces to O(Cdn-J) )) in the linear model of dimension d, thus matching the lower bound for corrupted linear MDPs. It is worth highlighting that our novel analysis enables us to climinate the uncertainty-related weights from the coverage condition.
11/2 1/2 + < CC)/2(C(F,))) -))- where H is the
Motivated by our theoretical findings, we present practical offline RL algorithm with uncertainty weighting and demonstrate its efficacy under diverse data corruption scenarios. Our practical implementation achieves a 104% improvement over the previous state-of-the-an art incertainty-basee offline RL algorithm under data corruption, demonstrating its potential for effective deployment in real-world applications.
1.1 Related Work
Corruption-Robust Bandits and RL. There is an emerging body of theoretical literature on bandits and online RL with corruption. The adversarial corruption is first formulated in the multi-armed bandit problem by Lykouris et al. BC where an adversary corrupts the reward in each round t
by G. and the corruption level is measured by < Σ Kt]- Then, lower bound with a linear dependence on Ç is constructed by Gupta et al. 17 indicating that the ideal regret bound should
achieve a "parallel" relationship: (T) (T)) + O()), and the corruttin-independee term
approximates the non-corrupted bound. When extending to linear contextual bandits, line of
2

---

propose various methods but either derive sub-optimal regrets or require particular assumptions. The gap later closed by He et al. [8], which achieves the minimax lower bound using novel sample-dependent weighting technique. Specifically, the weight for each sample adaptive to its confidence, which is also called uncertainty. Beyond bandits, earlier works on consider the setting where only the rewards are corrupted, and the transitions remain intact. Wu et al. 50) begin to handle corruption on both rewards and transitions for tabular MDPs. Wei et al. ES establish unified framework for RL with unknown corruption under weak adversary, where the corruption happens before the decision is made in each round. Later, Ye al. [55] extend the weighting technique [8S to corrupted RL with general function approximation and achieve a linear dependence on the cumulative corruption level Ç. Particularly, Wei et al. [48], Ye et al. 155 both impose corruption on the Bellman operator, which is the same as the corruption model considered in this paper.
work A 13
27 62 25
MDPs 5
20
2
2
531
57
Offiine RL Against Attacks. The emergence of poisoning attacks in real-world scenarios poses new challenges for offiin RL and necessitates improved defenses 49] There are generally two types of attacks 3 namely test-time attacks and training-time attacks. In test-time attacks, the training data is clean, and the learned policy must contend with an attacker during test time. For example, Yang et al. [50 propose learning conservative and smooth policies robust to different test-time attacks. In contrast, our paper focuses on the training-tinn time attack as another line of work [3 49 600 where part of the training data is corrupted maliciously. Wu et al. [49] propose two certification criteria and a new aggregation- based method to improve the learned policy from corrupted data. To the best of our knowledge, [60] is the only theoretical work corrupted offline RL, which considers that an e-fraction (e = C/nH) of samples are corrupted on both rewards and transitions for linear MDPs and achieves an O(51/2 dn-ddd-//// 1/2) suboptimality bound. Notably, distinct from the setting in Zhang et al. 600 that clean data is first collected and then corrupted by adversary, we consider the setting that data collection and corruption occur at the same time (thus corruption at one step affects the subsequent trajectory). Therefore, our setting is different from that of Zhang al. 600
2 Preliminaries
In this section, we formulate the episodic Markov decision process (MDP) with adversarial corruption and under general (nonlinear) function approximation. Before the formal introduction, we introduce some notations to facilitate our presentation.
Notations. Let [n]] denote the set {l,...,,] ,n). For spaces X' and A and function f X'Xx x A- R. let f(z)= m f(z a). Given a semi-definite matrix M and a vector u, we define ||и||ar Vo Mv. For two positive sequences [n)]_=] {g(n)] ] let f(n = (g(n)) if there exists constant C > O such that f(n) I Cg(n) for all n 2 and f(n (()(n) if there exists
constant C such that f(n) 2 Cg(n) for all n > We use Õ(-) to omit polylogarithmic factors. Sometimes we use the shorthand notation z = (I,a).
2.1 Episodic MDPs
We consider an episodic MDP (X,A,H,P,) with the state space X, action space A, episode length H, transition kernel P = he and reward function r = (rr) ]Ne(z]) Suppose that the rewards are bounded: n 2 0 for any h E [M], and Elz Ma"",, ,a²) S 1 almost surely. Given any policy π = h X + A)ne(H]) we define the Q-value and V-value functions starting from step h as
1
dh ad)
Σ E [ (a* a 10 aa) M/=h
(=
Σ
E |rh (ot"
)
|1>²)
(I)
h/=h
where the expectation E, is taken with respect to the trajectory under the policy There exists an optimal policy n, and optimal value functions V. == V (x) = sup, V²(2) and Q2
Qhe (x, a) = sup, (x, a) that satisfy the Bellman optimality equation:
Q7 a) = E,a h4tz (s. + max (x/+11 .a) |2, a] == (T*
(2)
d'E.A
where T is called the Bellman operator. Then we define the Bellman residual as (f, d²)) ("(""" - (7" gh+ pht1)(a"
(3)
3

---

2.2 General Function Approximation
We approximate the Q-value functions by a function class F F= .... FH where Fk & A - [0. for h E [H] and fu+1 = 0 since no reward is generated at step H + 1. Generally, the following assumption is common for the approximation function class.
Assumption 2.1 (Realizability and Completeness). For all h E [H], Q. E Fh. Additionally, for all (*++((²+)2) E [0, 1]. (("gg+1()(0 "a",,""))) F
The realizabilitty assumption 21 ensures the possibility of learning the true Q-value function by considering the function class FF. The Bellman completeness (adopted from Wang et al. 47 and Assumption 18.22 of Zhang [59] is stronger than that in Jin et al. M1 The former applies the least squares value iteration (LSVI) algorithm that establishes optimism at each step, while the latter proposes the GOLF algorithm that only establishes optimism at the first step. We use the standard covering number depict the scale of the function class F.
Definition 2.1 (c-Covering Number). The c-covering number [(c,F, of a set F under metric p the smallest cardinality of a subset Fo S F such that for any f E F, there exists a g E Fo satisfying that p( 9) We say Fo is an (e, p) cover of F.
2.3
Offline Data Collection Process
Offline Clean Data. Consider an offline clean dataset with n trajectories D = {(x, aa,, , r iiker
We assume the dataset 'D is compliant with an MDP (H,,), with the value functions Q, V and the Bellman operator T: for any policy и.
P((T"Q h+ (a a.) r' + (x') (x))((()))) d ( [et try ()))))+)))))e) 1/ = =P(r"(a* (x", a²) = r', xht1 x' z'|aa =,, a = a.
2h*1)
where the realizability and completeness in Assumption 2.T The compliance assumption is also made in Jin et al. 20 Zhong et al. [33, which means that remains the Markov property and allows D to be collected by an adaptive behavior policy. The induced distribution of the state-action pair is denoted by μ = {n² { ].([)]
Adversarial Corruption. During the offline dataset collection process, after observing the state- action pair (ath a chosen by the data collector, an adversary corrupts rh and ^^+1 each step before they are revealed to the collector. For the corrupted dataset 'D we define the corrupted value function QD, Vp. and the Bellman operator To satisfying 4 To measure the corruption level, we notice that characterizing the specific modification on each tuple (s, a, s', ,r) is hard and unnecessary since once one modifies tuple, the subsequent trajectory changes. Therefore, it is difficult to tell whether the change is caused by the corruption at the current step previous step. In fact, we only care about the part of the change that violates the Bellman completeness. Therefore, following the measure the corruption level by the gap between TD and T as follows. Definition 2.2 (Cumulative Corruption). The cumulative corruption Ç if at any step [H) for C. X x A chosen by the data collector and a sequence of functions 1 we have for all l E [H].
online setting [55] 48
a sequence {< a qf)))
(g" X [0, 1)
H
Σ
=h:
h=1
where ch (T"gh+1 ( ( at)
The learning objective is to find policy n that minimizes the suboptimality of given any initial state x= = x: (T, = (x) - (z),, where V(-) is the value function induced by the uncorrupted MDP.
3 Algorithm
In this section, we first highlight the pivotal role that uncertainty weighting plays controlling the coruppiion-reatted bound. To extend the uncertainty weighting technique to the offline setting, we propose an iteration algorithm. With the proposed algorithm, the theoretical result for the suboptimality is presented.

---

3.1 Uncertainty-Rest -Reatte Weights
In this subsection, we discuss the choice of weight for simplified model without state transition (H- 1) and use the notation 2, = (z4, a.). Given dataset {(z,. 84) hejn]] we have yi f(2)) + Ci + c3 for i E (n], where f E F is the uncorrupted true value, the noise E; is zero-mean and conditional 1ysubGaausian, and the corruption level Ç = Σm Ks./-
We begin with delineating the consequence caused by the adversarial corruption for the traditional
least-square regression: f = minser Di=1 (J(z)) - yı) Some calculations lead to the following decomposition:
E(s(s) - [(x))) - [((()) = (0)))=aa) w) +2 - (())) +2 - ((x))).
1050
Nooss tenu
JoConpapiion tonm
The term I S 0 since f is the solution to the least-square regression. The term 12 is bounded by OIn N) because of the n-subGaussainity of c,. where N is the covering number of F. The term I3 ruined by corruption: I3 S E |Gl (()) Hence, the confidence radius (E/=(((z))
f()))) = ÓVV will explode whenever the corruption level Ç grows with n.
To control the corruption term, motivated by the uncertainty-weigheee technique from online settings 55 18 655,
we apply the weighted regression: f f= min min Ex=1 (f(z))- (o:)))-))//// /o?, where ideally, we desire the following uncertainty-related weights:
1 1,
(f(z)) - ff
of = max
sup JTEF VA+ プー= (0(=)) - ((ss))
i= ,....,n n,
(5)
Uncertainty
where a, x > 0 are pre-determined parameters. The uncertainty quantity in the above equation the supremum of the ratio between the prediction error If(z.) f and the training error v () ('=z)) over J E F. Intuitively, the quantity depicts the relative informa- tion of sample 2, against the whole training set {21...., Z, We can use the linear function class as a special example to explain it. When the function space Fhh is embedded into a d-dimensional vector space: 5hhh {(w(f), ((-)) :2 R}, the uncertainty quantity becomes
(w/(f) w('',
[ww([) - w(J'), ((2)))
sup LIEF V Σド= ((w(() ((()),(=;))))))
sup ISEEF / ((w(f) - w(f)) A(w(f) w(ft))
((Er)))
S SV
where A d (z))/o7. Moreover, (o (2))AAA o(2)) represents the effective number of samples in the 1r along the d(2;)'s direction. We discuss in Lemma B.3 that under mild conditions the linear and nonlinear uncertainty quantities are almost equivalent.
However, since the uncertainty also depends on weights, it is impossible to determine all the weights (ar Jeej) simultaneously. Compared with the online setting where the weight in each round can be determined sequentially (iteratively in rounds), we face two challenges in the offline setting: (a) how to compute uncertainty-relann weights iteratively? (b) will an approximate solution to the uncertainty play equivalent role in controlling the corruption term?
To solve the first challenge, demonstrate the convergence of this algorithm by the monotone convergence theorem in the following lemma, which ensures that the output weights are sufficiently close desired ones The proof provided in Appendix B.I
we propose the weight iteration algorithm in Algorithm I Moreover, we
Lemma 3.1. There exists a T such that the output of Algorithm 1 (o, := of N satisfy:
of 2 max (1, ((x)/22,
of max (1, (z:)),
(6)
where ((z)) =su (1>)
(x.))
5

---

Algorithm Uncertainty Weight Iteration
Input: ((z,, a=)
2: Initialization: t = O, of =1,i=1,... 1....,
3: repeat
4: t f
5: (ot)² max (1.SuPy,'EF /1= 1yp 1....,
6: until maxie|n| (0//0) 22
7: Output: {o?)
For the second challenge, the weighted version Ln == (f=(((z)) - foz))) can also be decomposed into three terms correspondingly. We can demonstrate that an approximate choice of weights satisfying (6) is sufficient to control the corruption term as
(f(z) - [())
(f(z)) [(2)))< Lm
( -(,))/))) S 2ac D
Since the corruption-unrelated terms (corresponding to J, I2) can still bounded by Ó(n N), we have Ln = ÓIn N + 2a / LL), leading to an Õ + /In N) confidence radius. Therefore, with sufficiently small a, the effect of corruption can be countered.
3.2
Corruption- Algorithm
Algorithm 2 CR-PEVI
1: Input: D ((a,', a A H F
:i
2: Initialization: Set f 1M+1 1 + 0
3: for step à HT
do
4: Choosing weights {a, ) by proceeding Algorithm with inputs ((a!, )²" a
Find the weighted eaast-squares solution in
6: Find 8h and construct confidence set
Fdh
{ ( X ( at) -
= (8))2)
Construct bonus function as
8: Let fh (:: max ( 8h (b.)).)))
9: Set 4 arginax (.)aa)
10: end for
Output: { fhm1
Now, for the offline RL with general function approximation, we integrate the uncertainty weight iter- ation algorithm with the pessimistic value iteration (PEVI) algorithm 24] and propose Corruption- Robust PEVI (CR-PEVI) in Algorithm 2 Our algorithm employs backward induction from step H to 1. Set estimated value function fi + 0. At each step h [H]. having obtained fh+11 calculate S by solving the following weighted least-square regression:
(f(a). rf fhat (2
argmin fhe
(o
where the weights are obtained via Algorithm As opposed to online RL where the necessity of
exploration stimulates optimistic estimation, the literature on offline RL [4 63 is more inclined to pessimism due the limitation of offline data coverage. Hence, we construct a confidence set
f&h = (f
Frh A ( (((ff//a))) af - f*( ( /d)))²((?)) < (8"3²) such that the uncorrupted Bellman operator T converts the value function fh+ +1 into the function class f (i.c., The ph++1

---

Fh) with high probability. For the bonus function, we follow [5 and choose it as
1f a) f( a)l
(x, = sup E.
(8)
VA+ E ; - ((
which is seldom used in practical algorithms due to its unstability. Specifically, the covering number of the space containing @ may be uncontrollable. According to Appendix E in [55], the issue of the covering number can be addressed under mild conditions by some techniques. Therefore, to maintain readability and consisteney in this paper, we assume the corresponding bonus function space B of @ has a bounded covering number. Then we introduce pessimism by subtracting 6 from the estimated value function: ft (x. a) = max(0, (ar a) (rb
Theoretical Analysis
4.1 Coverage Condition
No guarantee for the suboptimality can be provided with insufficient data coverage. Based on pessimism, Jin et al. (20], Rushidinejad et al. [66] have demonstrated that the coverage the optimal policy is sufficient for sample-efficient offline RL. The following condition covers the optimal policy under general function approximation.
Definition 4.1 (Coverage Coefficient). Consider the offline dataset {zy a 1 Ji,h=1 state x² x E X, the coverage coefficient is:
n.H
For any initial
n(f(2" a²) (=" )²))
CC(A,F,2") max Ex, sup f X (i ( of))))))22
HE(H]
where Ex,, is taken with respect to the trajectory induced by in the underlying uncorrupted MDP.
In the face of corruption, require single-policy coverage over the uncorrupted trajectory. This coefficient depicts the expected uncertainty of sample (x.", a²) induced by the optimal policy n, compared the training samples. We use the linear MDP to interpret this condition, where the function space 5sh is embedded into a dddimensional vector space: F = (ww (f), o(-) )) + IRJ, where 2 denotes the state-action pair (x, a). With the notation A AI + Ei= o(2 (+ we can demonstrate that if the sufficient "coverage" in Jin et al. (2 holds: there exists constant cf such that A > T _ ((=)))))(="))))))))))))))))))))) x x) for all h [M]. our coverage coefficient is bounded: CC(X, F, 2 S d/ct oc. Therefore, the sufficient "coverage" condition implies our coverage
condition in the linear setting. We will discuss the connection formally in Lemma B.I
4.2 Main Result
Before presenting the main theorem, introduce general version of the well-explored dataset condition, which is the key to eliminating the uncertainty-related weights from the suboptimality bound and deriving the final result.
Assumption 4.1 Well-Explore Dataset). There exists constant C(F, ,,) 8n-1 such that for (n-1.]) (lx)) cover of Frh denoted by Fh, and for any two distinct f. FA,
min KE(H]
Σ (F())) f'(x"))2 C(F 11).
(10)
AEXXA
We interpret this condition with the linear model, where the condition 10 becomes: for any two
distinct f, E Fhh minne(H] (w(S) w(J")) A (w((S) w(')) > C(F.p). As proved in
Lemma B.2 with high probability, the above condition holds with C(F,u) ((d-)) when the
trajectories of 'D are independent, and the data distribution /² satisfies the minimum eigenvalue condition:
miin (E (o(="))(=") z/d,
where > 0 is an absolute constant. This is a widely-adopte assumption in the literature I Note that ((d-1) !) is the largest possible minimum eigenvalue since for any data distribution P. mmin (E [0(2*) )0(2)) TT) < d- by using [| < 1 for any 2 X x A.
46 63
7

---

Theorem 1. the coverage coefficient in Definition 4.7 is finite, under Assumption 4.1 for corruption <= En=r and > O, choose the covering parameter y 1/ max,, 3 (h5")),,h (n)),(()).. the weighting parameter a / Nn)(/S, and the confidence radius
8 = cs(acch + VIn(HN.((:)00)) for l -H....,.
where Na(7) = max, ((t/n, (n/nn, Fh+t)- (7//n, ((,,B++++))))) Then, with probability at least 1 25, the sub-optimality of Algorithm 2 is bounded by
SubOpt(fr, x) = (HHCCCIA, F, 2, ) (In (a(2)) n A/2(C((F,)))
F, (IC(F.,))L
2
When < = O(vn), our algorithm achieves the same order of suboptimality as the uncorrupted o(n), our algorithm is sample-efficient. Moreover, when specialized to
case. Whenever the linear MDP with dimension d, where CC(A,F, = = Odd/c),, C(F,μ) = O(d=1) and
In (v) = Odd), the suboptimality bound in Theorem 1 becomes (( 1/2 1/ '(n The
Corruptioninneeeendee term Õ ((Hdd/2 d matches that of PEVI 24 The corrutiion-dependem term nearly matches the lower bound, as will be discussed later.
Remark 4.1. Although the theory requires known corruption level Ç. in the experiments, we treat the uncertainty ratio a = O(1/C) as a tuning hyperparameter. The use of independent and identically distributed (i.id.) trajectories in our experiments renders the hyperparameter tuning process straightforward and conducive to optimizing the performance. Additionally, we can offer a choice of a = -O1I This choice finds support in the online setting (55 188, where this specific choice of a ensures that suboptimality remains in the order of uncorrupted error bound, even when Ç <=0( =V.n)
Proof sketch. The detailed proof Theorem D is provided in Appendix A Here we present a brief proof sketch for the suboptimality bound, which is accomplished by three steps: (1) by Lemma A. if the uncorrupted Bellman backup Th fn E F for each h [H], we bound the suboptimality
by the sum of the bonus Σ ,. """.,"""("" a²)) x² = æ]; (2) by Lemma A.2 we demonstrate that an approximate uncertainty weight satisfying (6) is the key to bound the weighted Bellman error (E==(())
(x?", at ))² ( 1/2 by 9th ca +
and
(3) combining the results in the first two steps, we can obtain the suboptimality bounded by:
1/2 SubOpt x) = ÓHHCCC (A, ",, 1/ (In N.)) 1/ + CCC% (A, F, 2, . ").
Here CC (,, denotes the weighted coverage coefficient follows
max E.. sup - S A ++ELI at) fx) {() x =
CC (A, F, z
(12)
NE[H]
where the weight for the trajectory induced by the optimal policy n is
max (1,
If(x", - a'',a"))1/
(a" a² a²))²=
sup 1. V ΣN (f f(x (()))
(13)
To control the weighted coverage coefficient CC by its unweighted counterpart CC, which is challenging task due to the intricate form of uncertainty-relate employed. The main idea behind this technique is to transform CC into a modified version of CC multiplied by a term that can be bounded by leveraging a cover of the function class. The connection between CC and CC is shown in the following lemma.
weights, novel technique has been
Lemma 4.1. Under Assumption 4.1 and choose 3h CaVin (where Cg 0 contains the logarithmic terms that are omitted) and X given in Theorem 7 we have
1/2 (C(F ()) -1/2).
Intuitively, because the weights themselves are closely related to the uncertainty, the weighted coverage coefficient CC where the high-uncertain samples are down-weighted can be upper-bounded by the square root of the unweighted coefficient CC. See Appendix B.3 for details.

---

SMC-6
100
2009
1900
550
(a)
(b)
(d)
Figure Performance on the Walker2d and the Halfcheetah tasks under (a) random reward, (b) random dynamics, (c) adversarial reward, and (d) adversarial dynamics attacks.
Lower Bound. We construct lower bound for linear MDPs with adversarial corruption Ç to show that the O(dCn-) ) corruption term of our suboptimality is optimal. The construction of the lower bound is adapted from Zhang et al. [60] where an e-constant fraction of the dataset is contaminated. We present the proof of Theorem 2 in Appendix B.4
Theorem 2 (Minimax Lower Bound for Linear MDPs). Under linear MDPs with corruption (Defini- tion 2.2 for any fixed data data-collecting distribution v. any algorithu L: - II with the knowledge o cannot find a better policy than O(dCn (/ddCn"")-opiimmll "optimal policy with probability more than 1/4:
min max SubOpt(#L) (d) L, MDP,D
where 'D is the corrupted dataset initially generated from the MDP and then corrupted by adversary, and ā is the policy generated by the algorithm L.
5 Experiments
Based on our theoretical results, we propose a practical implementation for CR-PEVI and verify its effectiveness simulation tasks with corrupted offline data.
Practical Implementation. To make estimate the Q function (i.e., f in our theory) and the weight function a. In linear MDPs, under sufficiently broad function approximation class Fhh and sufficiently small parameter À in Eq. (8. the bonus function can be simplified as the bootstrapped uncertainty of Q functions, which in turn can be estimated via the standard deviation of an ensemble of Q networks. We defer the detailed discussion to Appendix B.5 Following the state-of-the-ar uncertainty- based offline RL algorithm Model handard-deviation Gradients (MSG) [16], we learn group of Q networks Q 1, 1,..., K with independent targets and optimize a policy me with a lower-confidence bound (LCB) objective [6 Specifically, Qw, is learned to minimize weighted regression objective similar to Eq.
algorithm more practical, use neural networks to
7 The weight function is estimated via bootstrapped uncertainty: (Iz a) max( / V/i......K Qwi, (I. a)], 1), where Vi=1....K [Qw.] is the variance between the group of Q functions. This uncertainty estimation
method has also been adopted by prior works 2 16. 54) We refer to practical algorithm as Uncertainty Weighted MSG (UWMSG) and defer details to Appendix D
Experimental Setup. We assess the performance of our approach using continuous control tasks from [15 and introduce both random and adversarial attacks on either the rewards or dynamics for the offline datasets. Details about the four types of data corruption and their cumulative corruption levels are deferred to Appendix D The ensemble size is set to 10 for all experiments. For evaluation, we report average returns with standard deviations over 10 random seeds. More implementation details are also provided in Appendix D
Experimental Results. We compare UWMSG with the state-of-the-ant uncertainty- base offline RL methods, MSG (16), EDAC (1, and SAC-N M under four types of data corruption. In particular, MSG can be considered as UWMSG with a constant weighting function (ss, a) = 1. As demonstrated Table and Figure ! our empirical results find that (1) current offline RL methods are susceptible to data corruption, e.g., MSG, EDAC. SAC-N achieve poor performance under adversarial attacks, and (2) our proposed UWMSG significantly improves performance under different data corruption scenarios, with average improvement of 104% over MSG. More results can be found in Appendix F

---

Table 1: Comparison of different offline RL algorithms under different environments and different data corruption types.
Environment
Attack Type
UWMSG
MSG
EDAC
SAC-N
Random Reward
7299.9 + 169.0
4339.5 3958.7
7128.2 = 120.5
7357.5 = 165.2
Random Dynamics
1425,0 + 1639,5
2 793.3
-12.3 131.8
-66.2 = 169.9
Halfcheetah
Adversarial Reward
1016.7 503.9
243.1
-127.2 30.3
-5.77 24.0
Adversarial Dynamies
4144.3 1437.6
1055.6 -87.3
374.0 589.5
-26.8
Random Reward
2189.7 603.0
$39.1
1.27
1.4
Random Dynamics
2278,9 = 706.4
2122.8 2122.88822 821.5
+3.6
33.1 3.1
Walker2d
Adversarial Reward
1433.4 + 592.1
605.8 310.7
61.0 120.6
9.5 21.6
Adversarial Dynamics
946.0 + 300.4
506.0 + 175.5
-48 +:
-5.1 0.7
Random Reward
2021.1 888.6
1599.6 814.5
107.7 65.5
1788
Random Dynamies
2116.2 618.6
1552.7 532.8
5.9
3,9
Hopper
Adversarial Reward
751.4 72.5
651.0 + 58.0
29.2
111.8 62.7
Adversarial Dynamics
931.2 + 227.8
717.7 + 204.3
5.9 1.2
3,9 39=222
Average
2212.8
1083.6
630.0
607.1
In summary, the experimental results validate the theoretical impact of data corruption for value-based offline RL algorithms. Our practical implementation algorithm demonstrates superior efficacy under different data corruption types, thereby highlighting potential for real-world applications.
6 Conclusion
This work investigates the adversarially corrupted offline RL with general function approximation. We propose the uncertainty weight iteration and a weighted version of PEVI. Under a partial coverage condition and well-explored dataset, our algorithm achieves suboptimality bound, where the peruptiin-independeee term recovers the uncorrupted bound, and the corruption-related term nearly matches the lower bound in linear models. Furthermore, our experiments demonstrate promising results showing that our practical implementation, UWMSG, significantly enhances the performance of the state-of-thee -hr offline RL algorithm under reward and dynamics data corruptions.
Our work suggests several potential future directions. First, it remains unsolved whether one can design robust algorithms to handle additional distribution shifts of the state-action pairs. Second, when the corruption level is unknown, how design theoretically robust offline RL algorithm and overcome the lack of adaptivity in the offline setting requires further research. Finally, we hope that our work sheds light on applying uncertainty weights improve robustness in deep offline RL works and even practical applications.
Acknowledgements
We thank Wei Xiong for valuable discussions and feedback an early draft of this work. We also thank the anonymous reviewers for their helpful comments.
References
[1] An, G., Moon, S., Kim, J.-H., and Song, H. O. (2021). Uncertainty- offline reinforcement learning with diversified eennemble.. Advances in neural information processing systems, 34:7436- 7447.
[2] Bai, C., Wang, L., Yang, Z., Deng. Z., Garg, A., Liu, P., and Wang, Z. (2022). Pessimistic boot- strapping for uncertainty-driven offline reinforcement learning. arXiv preprint 2rXiv:2202.11566
[3] Behzadan, V. and Munir, A. (2018). Mitigation of policy manipulation attacks on deep q nentwworks with parameter-space noise. In Computer Safety, Reliability, and Security: SAFECOMP 2018 Workshops, ASSURE, DECSoS, SASSUR, STRIVE, and WAISE, Västerås, Sweden, September 18, 2018, Proceedings 37, pages 406-417. Springerr
[4] Bogunovic, I., Losalka, A., Krause, A., and Scarlett, J. (2021). Stochastic linear bandits robust to adversarial attacks. In International Conference on Artificial Intelligence and Statisties, pages 991-999, PMLR.
10

---

[5] Chen, L. and Luo, H. (2021). Finding the stochastic shortest path with low regret: The adversarial cost and unknown transition case. In International Conference on Machine Learning, pages 1651-1660. PMLR.
[6] Chen, Z., Li, C. J., Yuan, A., Gu, Q. and Jordan, M. I. (2023). A general framework for sample-efficien function approximation in reinforcement learning. International Conference on Learning Representations.
[7] Deng, D., Chen, G., Yu, Y., Liu, F,, and Heng, P.-.. (2023). Uncertainty estimation by fisher information-bant evidential deep learning. arXiv preprini arXiv:2303.
[8] Ding, Q. Hsich, C.-J., and Sharpnack, J. (2022). Robust stochastic linear contextual bandits under adversarial attacks. In International Conference on Artificial Intelligence and Statisties, pages 7111-7123, PMLR.
[9] Du, S., Kakade, S., Lee, J., Lovett, S., Mahajan, G., Sun, W., and Wang, R. (2021). Bilinear classes: A structural framework for provable generalization rl. In International Conference on Machine Learning, pages 2826-2836. PMLR.
[10] Du, Y., Watkins, O., Wang, Z.,, Colas, C., Darrell, T., Abbeel, P., Gupta, A., and Andreas, J. (2023). Guiding pretraining in reinforcement learning with large language models. arXiv preprint arXiv:2302.0m6 06692.
[11] Duan, Y., Jia, Z., and Wang. M. (2020). Minimax-optimal off-policy evaluation with linear function approximation. In International Conference on Machine Learning, pages 2701-2709, PMLR.
[12] Eykholt, K., Evtimov, I., Fernandes, E., Li, B., Rahmati, A., Xiao, C., Prakash, A., Kohno, T., and Song, D. (2018). Robust physical-world attacks on deep learning visual classification. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1625-1634.
[13] Foster, D. J., Gentile, C., Mohri, M., and Zimmert, J. (2020). Adapting to misspecification in contextual bandits. Advances in Neural Information Processing Systems, 33:1 14:1114881111 1489.
[14] Foster, D. J., Kakade, S. M., Qian, J., and Rakhlin, A. (2021). The statistical complexity of interactive decision making, arXiv preprint arXiv:21
[15] Fu, J., Kumar, A., Nachum, O., Tucker, G., and Levine, S. (2020). D4rl: Datasets for deep data-driven reinforcement learning. arXiv preprint arXiv:2004.07219
[16] Ghasemipour, K., Gu, S. S., and Nachum, O. (2022). Why so pessimistic? estimating uncertain- ties for offline rl through ensembles, and why their independence matters. Advances in Neural Information Processing Systems, 35:18267-181 18:18887-1.
[17] Gupta, A., Koren, T., and Talwar, K. (2019). Better algorithms for stochastic bandits with adversarial corruptions. In Conference Learning Theory, pages 1562-1578. PMLR.
[18] He, J., Zhou, D., Zhang, T., and Gu, Q. (2022). Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. arXiv preprint 22X.v:2205.06811.
[19] Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. (2017). Contextual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, pages 1704-1713, PMLR.
[20] Jin, C., Jin, T., Luo, H., Sra, S., and Yu, T. (2020a). Learning adversarial markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning, pages 4860 4869. PMLR.
[21] Jin, C., Liu, Q. and Miryoosefi, (2021a). Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. Advances in Neural Information Processing Systems, 34.
[22] Jin, C., Yang, 7.,, Wang, 7., and Jordan, M. I. (2020b). Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pages 2137-2143. PMLR.

---

[23] Jin, T. and Luo, H. (2020). Simultaneously learning stochastic and adversarial episodic mdps with known transition. Advances neural information processing systems, 33:16557-16566.
[24] Jin, Y., Yang, Z., and Wang, Z. (2021b). Is pessimism provably efficient for offline rl? In International Conference on Machine Learning, pages 5084-5096. PMLR.
[25] Kang, Y., Hsich, C.-J., and Lee, T. (2023). Robust lipschitz bandits to adversarial corruptions. arXiv preprint arXiv:2305.1854.
[26] Kober, J., Bagnell, J. A., and Peters, J. (2013). Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32(11))1228-1227.
[27] Lee, C.-W., Luo, H., Wei, C.-Y., Zhang, M., and Zhang, X. (2021). Achieving near instance- optimality and minimax-optimality in stochastic and adversarial linear bandits simultaneously. In International Conference on Machine Learning, pages 6142-6151. PMLR.
[28] Liu, Y., Logan, B.. Liu, N., Xu, Z. Tang, J., and Wang, Y. (2017). Deep reinforcement learning for dynamic treatment regimes on medical registry data. In 2017 IEEE international conference on healthcare informatics (ICHI), pages 380-385. IEEE.
[29] Luo, H., Wei, C.-Y., and Lee, C.-W. (2021). Policy optimization in adversarial mdps: Improved exploration via dilated bonuses. Advances in Neural Information Processing Systems, 34:22931- 22942.
[30] Lykouris, T., Mirrokni, V., and Paes Leme, R. (2018). Stochastic bandits robust to adversarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. pages 114-122.
[31] Ma, Y., Zhang, X., Sun, W., and Zhu, J. (2019). Policy poisoning in batch reinforcement learning and control. Advances in Neural Information Processing Systems, 32.
[32] Neff, G. (2016). Talking to bots: Symbiotic agency and the case of tay. International Journal of Communication.
[33] Neu, G., György, A., Szepesvári, C., et al. (2010). The online loop-free stochastic shortest-path problem. In COLT, volume 2010, pages 231-243. Citeseer.
[34] Osband, I., Blundell, C., Pritzel, A., and Van Roy, B. (2016). Deep exploration via bootstrapped dqn. Advances in neural information processing systems, 29.
[35] Pan, Y., Cheng, C.-A,, Saigol, K., Lee, K., Yan, X., Theodorou, E., and Boots, B. (2017). Agile autonomous driving using end-to-end deep imitation learning. arXiv preprint perxiv:1709.00 174.
[36] Rashidinejad, P., Zhu, B., Ma. C., Jiao, J., and Russell, S. (2021). Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34:1 14:11772-1177
[37] Rosenberg, A. and Mansour, Y. (2019). Online convex optimization in adversarial markov decision processes. In International Conference on Machine Learning, pages 5478-5486 PMLR.
[38] Rosenberg, A. and Mansour, Y. (2020). Stochastic shortest path with adversarialyy changing costs. arXiv preprint arXiv:2006. 1561."
[39] Russo, D. and Van Roy, B. (2013). Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26.
[40] Sun, H., Han, L., Yang, R., Ma, X., Guo, J., and Zhou, B. (2022a). Exploit reward shifting palue-based deep-rl: Optimistic curiosity-based exploration and conservative exploitation via linear reward shaping. Advances in Neural Information Processing Systems, 35:37719-37734.
[41] Sun, H., van Breugel, B., Crabbe, J., Seedat, N., and van der Schaar, M. (2022b). Daux; a bassi approach for uncertainty explanations. arXiv preprint
12

---

[42] Tarasov, D., Nikulin, A., Akimov, D., Kurenkov, V., and Kolesnikov, S. (2022). CORL: Research-oriented deep offline reinforcement learning library. 3rd Offline RL Workshop: Offline RI. as a "I "Iaunchpad".
[43] Tropp, J. A. (2012). User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics,
[44] Uchara, M. and Sun, W. (2021). Pessimistic model-based offline reinforcement learning under partial coverage. arXiv preprint wrXiv:2107.06226.
[45] Wang, L.,, Zhang, W., He, X., and Zha, H. (2018). Supervised reinforcement learning with recurrent neural network for dynamic treatment recommendation. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 2447-2456.
[46] Wang, R.,. Foster, D. P., and Kakade, S. M. (2020a). What are the statistical limits of offline rl with linear function approximation? arXiv preprint arXiv:2010..1899
[47] Wang, R., Salakhutdinov, R. R., and Yang. L. (2020b). Reinforcement learning with gen- eral value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33:6123-46 6135.
[48] Wei. C.-Y., Dann, C., and Zimmert, J. (2022). A model selection approach for corruption robust reinforcement learning. In International Conference on Algorithmic Learning Theory, pages 1043-1096. PMLR.
[49] Wu, F., Li, L., Zhang, H., Kailkhura, B., Kenthapadi, K., Zhao, D., and Li, B. (2022). Copa: Cer- tifying robust policies for offline reinforcement learning against poisoning attacks. In International Conference on Learning Representations.
[50] Wu, T., Yang, Y., Du, S., and Wang, L. (2021). On reinforcement learning with adversarial corruption and its application to block mdp. In International Conference on Muchine Learning, pages 1 1296-113300 PMLR.
[51] Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P., and Agarwal, A. (2021). Bellman-consistent pessimism for offline reinforcement learning. Advances in neural information processing systems, 14:6683-6694
[52] Xiong, W., Zhong, H., Shi, C., Shen, C., Wang, L., and Zhang, T. (2022). Nearly minimax optimal offline reinforcement learning with linear function approximation: Single-agent mdp and markov game. arXiv preprint 22t5::220055551111
[53] Yang, R., Bai, C., Ma, X., Wang. Z., Zhang, C., and Han, L. (2022). Rorl: reinforcement learning via conservative smoothing. In Advances in Neural Information Processing Systems.
Robust offline
[54] Yang, R., Yong, L., Ma, X., Hu, H., Zhang, C., and Zhang, T. (2023). What is essential for unseen goal generalization of offline goal-conditioned r!? In International Conference on Machine Learning, pages 39543-39571. PMLR.
[55] Ye, C., Xiong, W., Gu, Q. and Zhang, T. (2022). Corruption-robust algorithms with uncertainty weighting for nonlinear contextual bandits and markov decision processes.
[56] Yin, M. and Wang, Y.-X. (2021). Towards -nstance-optimal offline reinforcement learning with pessimism. Advances in neural information processing systems, 34:4065-4078.
[57] Zanette, A., Wainwright, M. J., and Brunskill, E. (2021). Provable benefits of actor-critic methods for offline reinforcement learning. Advances in neural information processing systems, 34:13626-1366
[58] Zhang, H., Chen, H., Xiao, C., Li, B., Liu, M., Boning, D., and Hsich, C.-J. (2020a). Robust deep reinforcement learning against adversarial perturbations state observations, Advances in Neural Information Processing Systems, 33:21024-2
[59] Zhang, T. (2023). Mathematical Analysis of Machine Learning Algorithms. Cambridge University Press. in press, also available as http: httpp///bongchang-. ml. org/ orgglttbook..... html
13

---

[60] Zhang, X., Chen, Y., Zhu, X., and Sun, W. (2022). Corruption-rouust offline reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 5757-5773. PMLR.
[61] Zhang, X., Ma, Y., Singla, A., and Zhu, X. (2020b). Adaptive reward-poisoning attacks against reinforcement learning. In International Conference on Machine Learning, pages 11225-11 1234. PMLR.
[62] Zhao, H., Zhou, D., and Gu, Q. (2021). Linear contextual bandits with adversarial corruptions. arXiv preprint arXiv:21 10. 12615.
[63] Zhong, H., Xiong, W., Tan, J., Wang, L., Zhang, T., Wang, Z., and Yang, Z. (2022a). Pes- simistic minimax value iteration: Provably efficient equilibrium learning from offline datasets. In International Conference on Machine Learning, pages 27117-27142, PMLR.
[64] Zhong, H., Xiong, W., Zheng, S., Wang, L.., Wang. 7., Yang, Z.,, and Zhang, T. (2022b). A posterior sampling framework for interactive decision making. arXiv preprint arXiv:2211.0090
[65] Zhou, D. and Gu, Q (2022). Computationally efficient horizon-free reinforcement learning for linear mixture mdps Advances in neural information processing systems, 35:36337-36349.
14


Reviews:
[{"review_id": "QvF6u650De", "reviewer": "Reviewer_H58a", "summary": "This work considers corrupted offline RL with general function approximation, and propose an algorithm based on PEVI and the uncertainty weighting technique. Under certain date coverage and well-explored dataset assumptions, the proposed algorithm achieves neal-optimal bound, where the corruption-independent term matches with the uncorrupted bound while the corruption-dependent term nearly matches the lower bound for linear models. Futher, experiments showcase the efficetiveness of the algorithm.", "questions": "1 Is the result comparable to the existing corrupted online RL with general function approximation? \n\n2 Could the authors comment more on Eqn. (6) and give intuition? It is unclear what tuning parameter $\\alpha$ and $\\lambda$ are designed for in this uncertainty-related weights. \n\n3 For the lower bound shown in Theorem 2, it would be great if the authors provide any insight.\n\nIn line 12, ''$\\widehat{F}$'' -> (or <-) ''$\\hat{F}$''.", "limitations": "NA", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1 This work is well-organized and well-written.\n\n2 The studied corrupted offline RL with general function approximation is not being widely explored.\n\n3 Adapting uncertainty-related weights technique to offline setting may be of interest.", "weaknesses": "1 The uncertainty-weighting technique and the PEVI are not new.\n\n2 This work extends the corrupted online setting to corrupted offline setting\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and valuable comments!\n\n**Q1** The uncertainty-weighting technique and PEVI are not new. This work extends corrupted online setting to offline setting.\n\n**A1** Our work is not a trivial extension from online RL to offline RL. We would like to highlight our technical novelties in two main aspects.\n- While PEVI has been introduced for offline learning of linear MDPs, our innovation lies in its extension to the eluder-type general function approximation. To achieve this, we introduce a new partial coverage coefficient in Definition 4.1 and assume that the coefficient is finite, which implies the single-policy coverage condition for offline linear MDPs (Lines 225-232).\n- Second, our uncertainty-weighting techniques substantially differ from the online RL setting in algorithm and theoretical analysis. \n    - For the algorithm, we propose the Uncertainty Value Iteration algorithm in Algorithm 1 to address the challenges posed by the inability of offline algorithms to iterate over timesteps like online counterparts. Furthermore, in Lemma 3.1, we prove the convergence of this iteration using the monotone convergence theorem, and an approximation of the uncertainty quantity is sufficient for robust estimation.\n    - For the analysis, we develop a novel technique to eliminate the dependence of the suboptimality on the uncertainty-related weights. Specifically, the original suboptimality bound contains the weighted coverage coefficient $\\text{CC}^{\\sigma}(\\lambda,\\hat{\\mathcal F},\\mathcal Z_n^H)$ defined in Eqn. (13), which makes the bound instance-dependent and hard to compare with existing results. Unlike the online setting where one can assume the bounded eluder dimension and try to bound the sum of bonus by the eluder dimension, we demonstrate in Lemma 4.1 that if the dataset is well-explored (Assumption 4.1),\n$$\n\\text{CC}^{\\sigma}(\\lambda,\\hat{\\mathcal F},\\mathcal Z_n^H) = \\tilde O\\Big(\\sqrt{\\text{CC}(\\lambda,\\hat{\\mathcal F},\\mathcal Z_n^H)/C(\\hat{\\mathcal F},\\mu)}\\Big),\n$$\nwhere $\\text{CC}(\\lambda,\\hat{\\mathcal F},\\mathcal Z_n^H)$ is the (unweighted) coverage coefficient, and $C(\\hat{\\mathcal F},\\mu)$ is a constant measuring the complexity of the function space $\\hat{\\mathcal F}$. To obtain this conclusion, we use the uncertainty structure in the weights, decompose the coefficient into the product of the coverage term and density term, and apply the Cauchy-Schwarz inequality.\n\n---\n\n**Q2** Is the result comparable to the existing corrupted online RL with general function approximation?\n\n**A2** Since online and offline RL adopt distinct assumptions, such as the bounded eluder dimension and coverage condition, their results are not directly comparable. Here we compare their results in a less formal manner.  Regardless of their different assumptions, our offline RL result aligns with the online RL result in terms of sample complexity. Specifically, our work establishes that achieving an $\\epsilon$-suboptimality in the offline setting requires a number of samples that is at most $\\tilde O(\\epsilon^{-2}+\\zeta\\cdot\\epsilon^{-1})$. As a comparison, the $\\tilde O(\\sqrt{n} + \\zeta)$ regret proved in [1] also implies an $\\tilde O(\\epsilon^{-2}+\\zeta\\cdot\\epsilon^{-1})$ sample complexity.\n\n---\n\n**Q3** Could the authors comment more on Eqn. (6) and give intuition?\n\n**A3** The uncertainty quantity is a ratio between the prediction error and the training error, which depicts the diversity of a sample $z_i$ against the whole training samples $\\{z_1,\\ldots,z_n\\}$. If the uncertainty quantity is larger than $\\alpha$, \n$\n\\sigma_i^2 = 1/\\alpha\\cdot \\text{Uncertainty};\n$\nelse, $\\sigma_i=1$.\n- We also use linear function class to give intuition. When the function space $\\mathcal F^h$ is embedded into a $d$-dimensional vector space: $\\mathcal F^h=\\{\\langle w(f), \\phi(\\cdot) \\rangle : z\\rightarrow\\mathcal R\\}$. Then, the uncertainty quantity becomes\n$$\n\\sup_{f,f'\\in\\mathcal F} \\frac{|\\langle w(f)-w(f'), \\phi(z_i) \\rangle|}{\\sqrt{\\lambda+\\sum_{j=1}^n\\big(\\langle w(f)-w(f'), \\phi(z_j) \\rangle\\big)^2/\\sigma_j^2}} \\le \\sup_{f,f'\\in\\mathcal F} \\frac{|\\langle w(f)-w(f'), \\phi(z_i) \\rangle|}{\\sqrt{\\big(w(f)-w(f')\\big)^{\\top} \\Lambda \\big(w(f)-w(f')\\big)}}\n\\le \\sqrt{\\phi^{\\top}(z_i)\\Lambda^{-1}\\phi(z_i)},\n$$\nwhere $\\Lambda=\\sum_{j=1}^n\\phi(z_j)\\phi^{\\top}(z_j)/\\sigma_j^2$. The $\\sqrt{\\phi^{\\top}(z_i)\\Lambda^{-1}\\phi(z_i)}$ is the bonus/uncertainty in the linear setting. $\\big(\\phi^{\\top}(z_i)\\Lambda^{-1}\\phi(z_i)\\big)^{-1}$ represents the effective number of samples in the $\\{z_i\\}_{i=1}^n$ along the $z_i$ direction. Moreover, we discuss in Lemma B.3 that under mild conditions the linear and nonlinear uncertainty quantities are almost equivalent.\n\n---\n\n**Q4** What tuning parameter is designed for $\\alpha$, $\\lambda$ in this uncertainty-related weights.\n\n**A4** In Theorem 1, we choose $\\alpha=H\\sqrt{\\ln N_n(\\gamma)}/\\zeta$, $\\lambda=\\ln(N_n(\\gamma))$, where $H$ is the horizon of the MDP, $N_n$ is the covering number, and $\\zeta$ is the cumulative corruption level. We can add a multiplicative constant to $\\alpha$ and $\\lambda$ respectively, and tune the constant in practice.\n\n---\n\n**Q5** Provide insight the lower bound in Theorem 2.\n\n**A5** Following [2], we consider the tabular MDP with $d=SA$ and corruption on the reward. By the pigeonhole principle, there must exist a sample $(s,a)$ with the smallest empirical distribution $\\nu(s,a)\\le 1/SA$.  Subsequently, an adversary strategically introduces corruption to all instances of $(s,a)$, thus modifying the reward to $\\tilde r(s,a)=r(s,a)+SA\\zeta/(nH)$. Then, a confusing pair $(s',a')$ satisfying that $r(s',a')=r(s,a)+SA\\zeta/(2nH)$ will make it hard to distinguish $(s,a)$ and $(s',a')$, leading to at least $SA\\zeta/(2n)$ suboplimality gap. \n\n[1] Ye et al. Corruption-robust algorithms with uncertainty weighting for nonlinear contextual bandits and Markov decision processes.\n\n[2] Zhang et al. Corruption-robust offline reinforcement learning."}, {"review_id": "1okP2JtJdX", "reviewer": "Reviewer_p9Rd", "summary": "This paper proposed a new robust offline RL algorithm called the Corruption Robust PEVI (CR-PEVI). The CR-PEVI achieves smaller suboptimality error compared to existing methods. The key idea behind CR-PEVI is to utilize the uncertainty-weighting technique when solving the least-squares problem in PEVI. The weights in the proposed method do not have closed-form solution, thus the authors proposed an iterative approach and relies on the monotone convergence theorem to prove convergence to the target weights. Based on that and several other assumptions, e.g., dataset needs to be well-explored, the paper proved an upper bound on the suboptimality of the policy learned by the CR-PEVI algorithm. When specializing to the linear function approximation with dimension d, the proposed CR-PEVI achieves O(eta*d/n) convergence rate. Experiments demonstrate the effectiveness of the CR-PEVI method.", "questions": "(1). Why the paper chooses to define the cumulative corruption based on the Bellman operator instead of the modification on the dataset? Is the goal to favor theoretical analysis? How does the theory changes if the corruption level is defined differently, e.g., total change on the rewards?\n\n(2). It's important to report the corruption level induced by different attack and victim RL algorithms in the experiment section. Furthermore, I was wondering how the cumulative corruption level affects the policy learned by CR-PEVI in practical scenarios.", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "(1). This paper studied robust offline RL, which is a hot and timely topic in recent years. Prior works mostly consider test-time attacks that are relatively easier to defend. However, less is understood about robustness against training-time attacks. This paper pushes the frontier in this domain and gained deeper understanding on how to design poisoning-resilient offline RL algorithms in the function approximation scenario, which is important and fascinating work.\n\n(2). The theoretical analysis is intriguing. The authors combined the uncertainty-weighting technique and the PEVI algorithm to propose a new algorithm that is robust to offline poisoning attacks. The analysis is based on several critical theoretical results established in the paper, which are complete and solid. Overall, the paper has strong theory contributions.\n\n(3). The empirical results are also convincing. On all the tasks, the CR-PEVI achieves much better performance compared to baselines.", "weaknesses": "(1). It seems like the definition of cumulative corruption is not commonly used by prior works. It is defined as the gap between the Bellman operators induced by the clean dataset and corrupted dataset, which is less intuitive and harder to quantize. In contrast, it makes more sense to define corruption level as the real modification on the reward/state transition over the trajectories.\n\n(2). In the experiment, the setup does not strictly conform with attacks under limited budget. The authors implemented different attacks without reporting the corruption level for every different attack and victim algorithm.  Furthermore, there is not parameter study on the corruption level eta as well. This makes me wonder if the comparison to prior works, in particular, Zhang et al, is fair enough.\n\n(3) Missing a few related references on training-time attacks in RL:\n\n[1]. Policy Poisoning in Batch Reinforcement Learning and Control\n\n[2]. Adaptive Reward-Poisoning Attacks against Reinforcement Learning", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and suggestions!\n\n**Q1** The definition of cumulative corruption is less intuitive and harder to quantize. Is the goal to favor theoretical analysis? It makes more sense to define corruption level as the real modification of the reward/state transition over the trajectories. How does the theory change if the corruption level is the total change in rewards?\n\n**A1** \n- The definition of cumulative corruption is the same as that in the online RL literature [1,2].\n- This definition is more general and concise, which contributes to a sense of uniformity and clarity within our analysis, as it avoids segregating the analysis of corruption effects on rewards and transition probabilities. In particular, since\n$$\n(\\mathcal T^h g)(x,a) = r^h(x,a) + (\\mathbb P^h g^{h+1})(x,a),\n$$\nthe modification on $r^h$ or $\\mathbb P^h$ contributes to the modification on $\\mathcal T^h$.\n- In our setting, during the offline dataset collection, the agent assembles complete trajectories with a horizon length $H$, while an adversary systematically corrupts $r^h$ and $x^{h+1}$ at each step $h$ before they are unveiled to the agent. Measuring the real modification on each tuple $(s,a,s',r)$ is hard in our setting since once one modifies a tuple, the subsequent trajectory shifts. It is difficult to tell whether the shift is due to corruption or the change from a previous step. Actually, we care about the part of the shift that violates the Bellman completeness.\n- Our corruption setting differs from [3], where each tuple can be corrupted independently. As a result, our framework does not supersede the results of [3]. We will restate this point in the revision and consider the corruption in this alternative setting as a future work.\n- The theory will not change if the corruption level is defined as the total change in the rewards because reward change is only a special case of our definition.\n\n---\n\n**Q2** In the experiment, the setup does not strictly conform with attacks under a limited budget. There is no parameter study on the corruption level eta. If the comparison to prior works, in particular, [3], is fair enough?\n\n**A2** \n- We would like to clarify that the attacks in our experiments are under a limited budget and the comparison is fair. To control the cumulative corruption level, we use corruption rate $c\\%$ and corruption scale $\\epsilon$ as the fact that  $\\zeta_i \\leq |r-r_{\\mathcal{D}}| + D_{TV}(P\\\\|P_{\\mathcal{D}}) \\leq |r-r_{\\mathcal{D}}| + \\sqrt{\\frac{1}{2} D_{KL}(P\\\\|P_{\\mathcal{D}}})$. When we consider $P$ and $P_{\\mathcal{D}}$ are both diagonal Gaussian distributions with the same constant variance, $\\zeta_i \\leq |r-r_{\\mathcal{D}}| + \\sqrt{\\frac{1}{2}} \\|\\mu - \\mu_{\\mathcal{D}}\\|= \\epsilon$. Then the cumulative corruption level $\\zeta = |D| \\times c\\% \\times \\epsilon$, where $|D|$ is the size of the dataset.\n- The cumulative corruption levels for each attack in our experiments are $5.99 \\times 10^6$, $2.72\\times 10^6$, $4.00 \\times 10^5$, $1.51 \\times 10^4$, $5.99 \\times 10^5$, $1.81\\times 10^5$, $3.60 \\times 10^5$, $9.05 \\times 10^3$, according to the order in Table 3 (Appendix D). **We applied the same corruption level for every victim under each attack, so the comparison is  fair**. In **A4**, we provide further parameter study about the cumulative corruption level $\\zeta$.\n- Regarding [3], it is a pure theoretical work without giving implementation details about the robust least-square oracle. As a result, we are not able to compare with it.\n\n---\n\n**Q3** Missing related references on training-time attacks in RL\n\n**A3** Thanks for the suggestion. We will add them in the revision.\n\n---\n\n**Q4** How the cumulative corruption level affects the policy learned by CR-PEVI in practical scenarios. \n\n**A4** In the following tables, the performance of CR-PEVI generally decreases with the increase in cumulative corruption level $\\zeta$. However, it is worth noting that CR-PEVI exhibits a remarkable ability to handle a certain level of corruption, resulting in only a small performance loss, e.g., in the cases of Halfcheetah random reward and Walker2d random reward.\n\n|$\\zeta$| 0.00|1.50 $\\times 10^6$|3.00 $\\times 10^6$|5.99 $\\times 10^6$|8.99$\\times 10^6$|1.20$\\times 10^7$|\n|-:|:-|:-|:-|:-|:-|:-|\n|Halfcheetah random reward|8233.27$\\pm$116.27|7791.98$\\pm$125.79|7587.58$\\pm$147.51|7287.53$\\pm$157.53|6821.02$\\pm$272.65|6156.51$\\pm$105.38|\n\n|$\\zeta$| 0.00|1.00$\\times10^5$|2.00$\\times10^5$|4.00$\\times10^5$|6.00$\\times10^5$|8.00$\\times10^5$|\n|-:|:-|:-|:-|:-|:-|:-|\n|  Halfcheetah random dynamics | 8132.66 $\\pm$ 102.65 | 7184.59 $\\pm$ 209.46 | 6063.33 $\\pm$ 320.4 | 1477.29 $\\pm$ 519.26 | 219.32 $\\pm$ 293.97 | -123.52 $\\pm$ 117.3 |\n\n|$\\zeta$|4.53$\\times 10^5$| 9.07$\\times 10^5$|1.81$\\times10^6$|2.72$\\times10^6$|3.63$\\times10^6$|\n|---:|:-------------------|:-------------------|:------------------|:-------------------|:------------------|\n|Walker2d random reward|2375.03$\\pm$528.4|2912.6$\\pm$637.09|3086.47$\\pm$406.06|3181.08$\\pm$114.53|1060.2$\\pm$1181.39|\n\n|$\\zeta$|7.55$\\times10^3$|1.51$\\times10^4$|2.27$\\times10^4$|3.02$\\times10^4$|4.53$\\times10^4$ \n|---:|:-------------------|:-------------------|:------------------|:-------------------|:------------------|\n|Walker2d random dynamics|2154.99$\\pm$797.72|2063.97$\\pm$851.61|1107.42$\\pm$364.81|498.34$\\pm$156.48|302.09$\\pm$38.13|\n\n[1] Ye et al. Corruption-robust algorithms with uncertainty weighting for nonlinear contextual bandits and Markov decision processes.\n\n[2] Wei et al. A model selection approach for corruption robust reinforcement learning.\n\n[3] Zhang et al. Corruption-robust offline reinforcement learning."}, {"review_id": "9nlDQHRzzS", "reviewer": "Reviewer_GirP", "summary": "The research investigates the issue of corruption robustness in offline reinforcement learning with general function approximation, where an adversary can corrupt samples in the offline dataset. The objective is to find a policy that remains robust against such corruption and minimizes the suboptimality gap compared to the optimal policy in uncorrupted Markov decision processes. To address this, a new uncertainty weight iteration procedure inspired by the robust online RL setting is designed, enabling efficient computation on batched samples. The proposed corruption-robust algorithm achieves a suboptimality bound, considering single policy coverage and knowledge of the corruption level. The analysis reveals that the corruption-dependent error term matches the existing lower bound for corrupted linear MDPs, indicating the tightness of the analysis in terms of corruption dependence.", "questions": "please see weaknesses for more.", "limitations": "Limitations is marked Yes, but I couldn't find the discussion in the main paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "I think this work really pushes the data-corruption solving real-world RL community research efforts further by answering:\n\n> Can we design a generic algorithm for data-corrupted offline RL in the context of function approximation?\n\nThe main contribution: algorithmic introduction to uncertainty reweighting idea. Both theoretical and practical performances have been shown. This is good for publication at NeurIPS.", "weaknesses": "I have only one minor weakness for this work as follows:\n\nOn Assumption 2.1. The recent offline RL theoretical guarantees proposing pessimism is to avoid completeness assumption and having weaker concentrabilities, like that of [23]. I don't see what is pessimism helping in this work if not to avoid the completeness. Maybe I am missing something. I am okay with this assumption if the work is trying to address the corruption-robust problem which requires (?) completeness?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and valuable comments!\n\n**Q1** On Assumption 2.1. I don't see what is pessimism helping in this work if not to avoid completeness. I am okay with this assumption if the work is trying to address the corruption-robust problem which requires (?) completeness?\n\n**A1** \n- Pessimism is used to relax the coverage condition (e.g., concentrability condition) rather than completeness. Completeness is for general function approximation.  Specifically, in the domain of linear MDPs [1,2,3], where the value functions exhibit a linear structure, completeness holds trivially. Nevertheless, pessimism remains necessary even in this linear framework. Without pessimism, a uniform coverage assumption becomes necessary, as demonstrated by Theorem 3.2 in [4]. In contrast, leveraging pessimism enables us to rely on a less restrictive partial coverage, as demonstrated by Corollary 4.5 in [1] and Theorem 3.3 in [4].\n- In general function approximation, completeness plays a pivotal role, ensuring that the Bellman backup of the value function resides within the confines of the considered function space. In [3], they also assume completeness and use pessimism.\n- In conclusion, completeness is used for general function approximation. Pessimism is established for offline RL without a uniform coverage condition. They lack direct connections.\n\n---\n\n**Q2** Limitations are marked Yes, but I couldn't find the discussion in the main paper.\n\n**A2** We discuss the limitation in Lines 318-323, which are left as future works.\n\n\n[1] Jin, Y., Yang, Z., and Wang, Z. (2021b). Is pessimism provably efficient for offline rl?\n\n[2] Xiong et al. Nearly minimax optimal offline reinforcement learning with linear function approximation: Single-agent mdp and Markov game.\n\n[3] Xie et al. Bellman-consistent pessimism for offline reinforcement learning\n\n[4] Zhang et al. Corruption-robust offline reinforcement learning."}, {"review_id": "e2lImlVoms", "reviewer": "Reviewer_wcW2", "summary": "The paper studies offline RL with general function approximation in the presence of adversarial corruption. Specifically, an adversary can corrupt the rewards and transitions in the offline dataset with a fixed cumulative budget. The corruption formulation encompasses prior corruption formulations. The proposed algorithm is based on an uncertainty-weight iteration subroutine, inspired by similar techniques in prior robust online RL papers. The authors conduct a finite-sample analysis, showing a tighter result on the corruption term. The theory is accompanied by a practical implementation tested over a couple of D4RL tasks.", "questions": "Suggestions:\n- Perhaps comparison with an implementation of Zhang et al instead of uncertainty-based offline RL is more appropriate.", "limitations": "Yes, clearly stated.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The authors propose a corruption formulation, which admits prior formulations such as fixed fraction contamination of Zhang et al. as special cases.\n- The theoretical result improves over the most relevant prior work Zhang et al. from $\\sqrt{\\epsilon}$ dependency to $\\epsilon$ dependency of the corruption term, which matches the lower bound when specialized to the linear case.\n- Inspired by the uncertainty weighting approach in robust online RL, the authors propose a similar weight iteration method in the offline RL case. However, in the offline case, the\n- The authors implement their algorithm over a subset of continuous control tasks in D4RL.", "weaknesses": "- The main limitation of this work is that the proposed algorithm requires the corruption level to be known. I did not find any attempts on possible heuristics for estimating the corruption level, which limits the practicality of the proposed approach.\n- The experiments section is generally weak. The practical implementation is limted to only two continous control tasks (Walker and Half Cheetah) from D4RL that are artificially corrupted. It would be good to see and compare performance with other tasks in D4RL as well. Furthermore, the approach is compared with uncertainty-based offline RL algorithms that are not designed to be corruption robust, making the comparison unfair.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review and constructive evaluation!\n\n**Q1** The main limitation of this work is that the proposed algorithm requires the corruption level to be known. I did not find any attempts at possible heuristics for estimating the corruption level, which limits the practicality of the proposed approach.\n\n**A1** \n- In the simulation, we can treat the uncertainty ratio $\\alpha=O(1/\\zeta)$ as a hyperparameter that can be tuned during the experimentation phase. The use of independent and identically distributed (i.i.d.) trajectories in our experiments facilitates the adjustment of this parameter, rendering the tuning process straightforward and conducive to optimize the performance.\n- We can also offer a choice of $\\alpha$, which is $\\Theta(1/\\sqrt{n})$. This choice finds support in the online setting, as demonstrated in [1], where this specific $\\alpha$ configuration ensures that suboptimality remains aligned with uncorrupted conditions, even when $\\zeta=O(\\sqrt{n})$.\n\n---\n\n**Q2** The experiments section is generally weak. The practical implementation is limited to only two continuous control tasks (Walker and Half Cheetah) from D4RL that are artificially corrupted. It would be good to see and compare performance with other tasks in D4RL as well.\n\n**A2** \n- Thanks for your suggestion. Since we consider 4 types of training-time attacks for each task, the computational burden is much higher compared to typical empirical offline RL works. However, we agree that incorporating more tasks would strengthen the empirical validation of our approach.\n- To solve your concern, during the rebuttal period, we have conducted additional experiments on the Hopper task (another D4RL task). The results from these experiments consistently align with our empirical findings in the paper, demonstrating that EDAC and SACN struggle to handle corrupted data, while our empirical algorithm UWMSG achieves robust performance. More results will be provided in the revision.\n\n|  Hopper  | UWMSG                         | MSG            | EDAC                            |  SACN                              \n|---:|:-------------------|:-------------------|:------------------|:-------------------|\n|  Hopper random reward | **2481.21 $\\pm$ 866.62** | 1488.48 $\\pm$ 522.98 | 77.74 $\\pm$ 31.13 | 225.65 $\\pm$ 138.14 |\n|  Hopper random dynamics | **1511.44 $\\pm$ 521.08** | 951.82 $\\pm$ 187.02 | 5.79 $\\pm$ 1.38 | 3.37 $\\pm$ 2.3 | \n\n---\n\n**Q3** The approach is compared with uncertainty-based offline RL algorithms that are not designed to be corruption robust, making the comparison unfair.\n\n**A3** To our knowledge, there is very little empirical work on corruption-robust offline RL. Zhang et al. assume that there exists a robust regression oracle, but they didn't give specific implementation details about the oracle. We will try to find a corruption-robust estimation method to implement Zhang et al. or other corruption-robust algorithms in the revision.\n    \n[1] Ye et al. Corruption-robust algorithms with uncertainty weighting for nonlinear contextual bandits and Markov decision processes.\n\n[2] Zhang et al. Corruption-robust offline reinforcement learning."}]

Author rebuttal:
We express our gratitude to the reviewers for their positive feedback and constructive suggestions! 

During the rebuttal period, we make some explanations and illustrations for our theory. For experiments, we complement two experiments and present the results in the following pdf. Firstly, we show the performance of our algorithm under different cumulative corruption levels in Figure 1. Secondly, we conduct additional experiments on the Hopper task in Table 1. We will add more empirical results in the revision according to the suggestions of reviewers.

Meta-review: After the discussion, the reviewers agree that that paper provides a new contribution to the offline corruption robust RL by improving the previous work's bound so that it matches the lower bound now. The reviewers agree that the paper should be accepted.
Decision: Accept (poster)