Robust Offline Reinforcement Learning with Linearly Structured $f$-Divergence Regularization
Authors: Cheng Tang
Zhishuai Liu
Pan Xu
Venue: ICML 2025 poster (2025)
Keywords: Reinforcement Learning
Robust Markov Decision Process
Primary area: reinforcement_learning
TL;DR: We provide algorithms and analysese for robust regularized Markov decision process with linear function approximation.

Abstract: The Robust Regularized Markov Decision Process (RRMDP) is proposed to learn policies robust to dynamics shifts by adding regularization to the transition dynamics in the value function. Existing methods mostly use unstructured regularization, potentially leading to conservative policies under unrealistic transitions. To address this limitation, we propose a novel framework, the $d$-rectangular linear RRMDP ($d$-RRMDP), which introduces latent structures into both transition kernels and regularization. We focus on offline reinforcement learning, where an agent learns policies from a precollected dataset in the nominal environment. We develop the Robust Regularized Pessimistic Value Iteration (R2PVI) algorithm that employs linear function approximation for robust policy learning in $d$-RRMDPs with $f$-divergence based regularization terms on transition kernels. We provide instance-dependent upper bounds on the suboptimality gap of R2PVI policies, demonstrating that these bounds are influenced by how well the dataset covers state-action spaces visited by the optimal robust policy under robustly admissible transitions. We establish information-theoretic lower bounds to verify that our algorithm is near-optimal. Finally, numerical experiments validate that R2PVI learns robust policies and exhibits superior computational efficiency compared to baseline methods.

Robust Offline Reinforcement Learning with Linearly Structured f f-Divergence Regularization
Cheng Tang Zhishuai Liu
2 Pan Xu²
Abstract
the policy deployment environment differs from the one where the dataset was collected, robust policies that remain effective under the environment shift are required (Garcia & Fernández, 2015; Packer et al., 2018; Zhang et al., 2020; Wang et al., 2024b; Guo et al., 2024). A widely adopted framework for learning such policies is the distribution- ally robust Markov decision process (DRMDP) (lyengar, 2005; Nilim & El Ghaoui, 2005), which models dynam- ies changes as an uncertainty set around the nominal tran- sition kernel. In this setup, an agent seeks policies per- forming well even in the worst-case environment within the uncertainty set. The most common design of uncer- tainty sets the (s, .ertecctngyll (lyengar, 2005; Nilim & El Ghaoui, 2005), which independently models uncer- tainty for each state-action pair. Although mathematically elegant, the (s, a) rectangullariy can result in overly conser- vative policies, especially when the state and action spaces are large. To address this issue, Goyal & Grand-Clement (2023) introduce the r-rectangular uncertainty set, which parameterizes transition kernels using latent factors. This concept has since been incorporated into d-rectangular lin- ear DRMDPs (d-DRMDPs, Ma et al. (2022)), extending its applicability to robust decision-making with linear func- tion approximation. Building on d-DRMDPs, recent works (Blanchet et al., 2024; Wang et al., 2024a; Liu & Xu, 2024b) propose provably efficient algorithms that leverage function approximation for robust policy learning.
The Robust Regularized Markov Decision Pro-
cess (RRMDP) is proposed to learn policies ro- bust to dynamics shifts by adding regularization to the transition dynamics in the value function. Existing methods mostly use unstructured reg- ularization, potentially leading to conservative policies under unrealistic transitions. To address this limitation, we propose novel framework, the d-rectangular linear RRMDP (d-RRMDP), which introduces latent structures into both tran- sition kernels and regularization. We focus on offline reinforcement learning, where an agent learns policies from a precollected dataset the nominal enviromment. We develop the Robust Regularized Pessimistic Value Iteration (R2PVT) algorithm that employs linear function approxi- mation for robust policy learning in d-RRMDPs with f-divergence based regularization terms on transition kernels. We provide instance- dependentt upper bounds on the suboptimality gap of R2PVI policies, demonstrating that these bounds are in- fluenced by how well the dataset covers state- action spaces visited by the optimal robust policy under robustly admissible transitions. We estab- lish ceermation-thhoredd lower bounds to verify that our algorithm is near-optimal. Finally, numer- ical experiments validate that R2PVI learns robust policies and exhibits superior computational effi- ciency compared to baseline methods.
However, the d-DRMDP framework has several problems that remain unaddressed, which we summarize follows. Theoretical Gaps: Current understanding of d-DRMDPs is largely restricted to uncertainty sets defined by the Total Variation (TV) divergence (Liu & Xu, 2024a:b). For uncer- tainty sets defined by the Ballback-Leibles (KL) divergence, prior works (Ma et al., 2022; Blanchet et al., 2024) rely on additional regularity assumptions regarding the KL dual variable, which is hard validate in practice. Moreover, the xd=divergence defined uncertainty set has demonstrated effectiveness in certain empirical applications (Panaganti & Kalathil, 2022; Xu et al., 2023) and has also been ana- lyzed under the (s, a) -rectangullarity (Shi et al., 2024). Yet there are no theoretical results or efficient algorithms for d- d-DRMDPs. Practical challenges: Existing practical al- gorithms (Ma et al., 2022; Liu & Xu, 2024b; Wang et al.,
1. Introduction
Offline reinforcement learning (RL) (Levine et al., 2020) facilitates policy learning from fixed datasets, eliminating the need for direct interaction with the environment. When
Equal contribution University of Illinois Urbana- ChammaaCaa, work was done when Cheng was in Tsinghua University "Duke University. Correspondence to: Pan Xu <pan. <<pan.xu@duk..dd ddu..uuuuu
Proceedings of the 4 International Conference on Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Robust Offline Reinforcement Learning with Linearly Structured f- f-Divergence Regularization
2024a) depend on dual optimization oracle (see Remark 4.2 in Liu & Xu (2024a)) to estimate the robust value func- tion. The computation complexity of these methods is pro- portional to the feature dimension d and the planning hori- zon H. While heuristic methods like the Nelder-Mead algo- rithm (Nelder & Mead, 1965) can approximate the oracle, they become computationally expensive when dealing with high-dimensional features (large d) and extended planning horizons (large H), which are common in real-world appli- cations. These limitations raise an important question:
regularization parameter, and 3 is problem-dependent parameter whose specific form depends on the choice of the divergence (see Section 5.1 for details). The set (P())) is derived from our theoretical analysis, and it does not represent an uncertainty set in the conventional DRMDP framework. We further construct an information- theoretic lower bound, demonstrating that this instance- dependent uncertainty function intrinsic.
We conduct experiments in simulated environments, in- cluding a linear MDP setting (Liu & Xu, 2024a) and the American Put Option environment (Tamar et al., 2014), Our findings show that: 1. The d-RRMDP framework yields equivalent robust policies as d-DRMDP with appro- priately chosen regularization parameters. 2. R2PVI sig- nificantly improves algorithms designed for d-DRMDPs in terms of the computation complexity, and is compara- ble to algorithms designed for standard linear MDPs.
Can we design efficient offline robust RL algorithms using general f f-divergence' uncertainty models with linearly structured transitions?
In this work, we provide a positive answer to this ques- tion. Inspired by the robust regularized MDP (RRMDP) framework with the (s, a) o)reettangll condition (Yang et al., 2023; Zhang et al., 2020; Panaganti et al., 2024a), where the uncertainty set constraint in DRMDP is replaced by a regularization penalty term measuring the divergence between the nominal and perturbed dynamics, we propose the d-rectangular linear RRMDP (d-RRMDP) framework. Specifically, d-RRMDP replaces the d-rectangular uncer- tainty set in d-DRMDPs with a carefully designed penalty term that preserves the linear structure. The motivations are two folds: (1) it has been shown by Yang et al. (2023) that the robust value function under the RRMDP is equiv- alent to that under the DRMDP with (s, rrecttnguuly as long as the regularizer is properly chosen: (2) removing the uncertainty set constraint simplifies the dual problem for certain divergences (Zhang et al.. 2024), potentially im- proving computational efficiency and facilitating theoretical analysis. We summarize our contributions as follows:
Notations. In this paper, we denote (SS) as the proba- bility distribution in the state space S. For any H E N. [H] represents the set 11. ,H). For vector v E Rd. we denote Uj as the i-th element. For any function V : S - [0, H), we denote Vmin = min.es V(s) and Viaax = max.es V(s). For any distribution l E (S)), we denote Var ((s) as the variance of the random vari- able Vss) under μ. For any two probability measures P and Q satisfying that P is absolute continuous with re- spect to Q, the f-divergence is defined as (y(l))Q) Ss ((P(s) ((s)))((s()))))))) on R and differentiable on R, satisfying f(1) = 0 and f(t) = +oo, Vt < O. The Total Variation (TV) diver- gence, Kullback- (KI.) divergence and Chi-Square (x2) divergence between P and Q are defined by (x) x log x. f(x) = (x 1)2, respectively. Given a scalar a, we denote [V())] = min(V(s), a). Given an interval I, we define [V(s)] as the result of clip- ping (ss) to lie within the interval I. We denote I as the identity matrix and 1, E IR as the one-hot vector with the i-th element equals to one.
where f is a convex function
1/2,
We establish that key dynamic programming principles, including the robust Bellman equation and the existence of deterministic optimal robust policies, hold under the d-RRMDP framework. Additionally, we derive dual for- mulations of robust Q-functions with TV, KL and x2 di- vergences defined regularization, highlighting their linear structures.
2. Related Work
We propose a computationally tractable meta-algorithm, Robust Regularized Pessimistic Value Iteration (R2PVI), for offline d-RRMDPs with general /-divergence regu- larization. For TV, KL, and x2 divergences, we provide -nstance-dependent upper bounds on the suboptimality gap of policies learned by R2PVI, in general form of B suppeu> (Po) Σ ET P [[ [|,,(s, a) ailll
Distributionally Robust MDPs. The seminal works of Satia & Lave Jr (1973); Iyengar (2005); Nilim & El Ghaoui (2005) proposed the framework of DRMDP. There are sev- eral lines of works studying DRMDPs under different set- tings. Zhou et al. (2021); Panaganti et al. (2022: 2024b): (2022;2024b): Shi & Chi (2024); Liu & Xu (2025) studied the offline DRMDP assuming access to an offline dataset and provided sample complexity bounds under the coverage assumption on the offline dataset. Liu & Xu (2024a); Liu et al. (2024); Lu et al. (2024) studied the online DRMDP where an agent learns robust policies by actively interacting with the nominal envi- ronment. Blanchet et al. (2024); Panaganti et al. (2022) stud-
$1 s) where d is the feature dimension, H is the horizon length, Φ(s, a) is the feature mapping, À is the
'The general f-divergence includes widely studied divergences such as Total Variation, Sullback-Leibler and x² divergences.
2

---

Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization
ied the DRMDP with general function approximation, they focused on the offline setting with the (s, -retangggnnl assumption. Ma et al. (2022); Liu & Xu (2024b); Wang et al. (2024a) studied the offline d- 1-DRMDP, they proposed prov- ably efficient and computationally tractable algorithms and provided sample complexity bounds under different kinds of coverage assumptions on the offline dataset.
iey n, the robust regularized value function is de-
fined as (s) = inf RP P Ei=h [ra(st, + AD(Pe(-Ise, (P 8/ = s, and robust Q- function as 0% (s. a) = inf BaPerBB[XX E [rx(st, az) + XD(P((-lse, (- ax))]
s, an a.
The RRMDP framework has been referred to by different names in the literature, including the penalized robust MDP (Yang et al., 2023), the soft robust MDP (Zhang et al., 2024), and the robust @-regularized MDP (Panaganti et al., 2024a). For consistency, we adopt the term RRMDP in this work. In RRMDPs, the perturbed transition kernel class J typi- cally encompasses all possible kernels. However, for envi- ronments with large state-action spaces, FF may be overly broad, including transitions that are unrealistic or irrelevant. To address this, we introduce latent structures on transi- tion kernels and design regularization terms that penalize changes in the latent structure, sharing similar ideas with the design of r-rectangular (Goyal & Grand- meand-Clement, 2023) and d-rectangular (Ma et al., 2022) uncertainty sets.
RRMDPs. The work of Yang et al. (2023); Zhang et al. (2024) proposed the RRMDP, which can be regarded as generalization of the DRMDP by substituting the uncer- lainty set constraint in DRMDP with the regularization term defined as the divergence between the perturbed model and the nominal model. In particular, Yang et al. (2023) studied the tabular RRMDP and proposed a model-free algorithms assuming access simulator. Zhang et al. (2024) studied the offline RRMDP, they established connections between RRMDPs with risk sensitive MDPs, and derived the policy gradient principle. Moreover, they studied general function approximation and proposed a computationally efficient al- gorithm, RFZI, for RRMDPs with KL-divergence defined regularization terms. Zhang et al. (2024) firstly discovered that the duality of the robust value function has a closed ex- pression under the KL--divergence Panaganti al. (2024a) studied the offline RRMDP with regularization terms de- fined by the general f f-divergence. They studied general function approximation and provided sample complexity results. They further proposed a hybrid algorithm, which learns robust policies with both historical data and inter- active data collection, for RRMDPs with TV-divergence defined regularization term. Existing works focus on the (s, a) ceetetttngyllrityy uncertainty regularization, which is dif- ferent from ours.
The d-rectangular linear RRMDP (d-RRMDP). In this paper, we propose the novel d-RRMDP, which admits a lin- ear structure of the feasible set and reward function. Specif- ically, a d-RRMDP is a RRMDP where the nominal envi- ronment pd is a special case of linear MDP with a simplex feature space (Jin al., 2020, Example 2.2), and the feasible set JF involves kernels defined based on the linear structure of the nominal transition kernel. We make the following assumption on reward functions and transition kernels:
Assumption 3.1 (Jin et al. (2020)). Given a known state- action feature mapping & : S x A + Ed satisfying Σ 0s a) = 1, 1, a) 2 0. we assume the re- ward function {ra))/ and the nominal transition ker- nels {PP h==1
3. Problem Formulation
/1 admit linear structures. Specifically, for all
(h, 8, a) E [M] S A, we have rn(ss, a) = (((ss, a). Oz). (-)). where {0.) known vectors with bounded norm ||0xll2 S vd and ph: = / .Ihra)) p.,() E A(S), vi e [d].
In this section, we provide preliminaries for RRMDPs.
and (- a) (Ø(s, 1o
are
Markov decision process (MDP). We first introduce the concept of MDPs, which is the basis of our settings. Specif- ically, we denote MDP(S, A, H, p0, ()) as a finite horizon MDP, where S is the state space, A is the action space, H is the horizon length, p0 = (P)) H Jh=1 are nominal transi- tional kernels, and the r(s, a) E [0, is the deterministic reward function assumed to be known in advance. For any policy ı,, the value function and Q-function time step h are defined as (s) E [EE= (e( (s) = 8, and Q7 a) E
With Assumption 3.1, the robust regularized value function and Q-function are defined as
H
Vr (x) =
B(P.H (VEA(S))
inf
Σ
[ra(Se,
1=h
+ M(p(s,, D(Hill14))
8h = =T
(3.1)
[ H E re(Se, 1ss s, s,a, a, m]
2h (s,a)= mEA(Sy
inf E(P.)MA
Σ
[ro(se, ac)
Robust regularized MDP (RRMDP) We define a finite horizon RRMDP as RRMDP(S, A, H, pa, r, D, F), where À is the regularizer, D is the probabil- ity divergence metric, and F is the feasible set of all perturbed transition kernels. For any pol-
t=h
+ X(0(st, D(Hl))))))))) - 8, a,
where D(ullu))= = =D((:ll4)))et In other words, we
3

---

Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization
only consider perturbed kernels in the linear feasible set
of (1g))))) r = rn (5h aj), and 8 P (-10% (b) for any h [H.] The agent aims learn the optimal robust policy x3 from the offline dataset D. Given a learned policy It, we evaluate ã by the suboptimality gap defined as follows
Fi. {P= -P=((P)) (P ((b(,))))))))))))))))))))))))))) (1(s,.),, pa(-)), 14 = (Mh,1, 14.2 (.),(.) A(S), Vi e [d].
The optimal robust regularized value function and Q- function are defined as:
SubOpt(ft $1, A1 =- V2 (s1)-
(3.5)
4. Robust Regularized Pessimistic Value Iteration (R2PVI)
(s) = sup (s),
(3.2)
(s. = sup ~
In this section, we first develop a meta-algorithm for d- RRMDPs with general f f-divergence defined regulariza- tion. To instantiate the meta-algorithm under specific f- divergences, we provide exact dual formulations of Q- functions with TV, KL and x >'vdieergence defined regu- larization, respectively.
Based on (3.2), the optimal robust policy is defined as the policy that achieves the optimal robust regularized value function, x * = argmax= (s), Vs E.
Dynamic programming principles for d-RRMDPs For completeness, we first show that the dynamic programming principles (Sutton& & Barto, 2018) hold for d-RRMDPs.
We first show that robust Q-functions admit linear represen- tations under d-RRMDPs.
Proposition 4.1. Under Assumption 3.1, for any tuple (T, 8, a, h), we have Oh (s, 07:7 where wh A.A = (W W h.2 (hd
Proposition 3.2. (Robust Regularized Bellman Equation) Under the d-rectangular linear RRMDP, for any policy и and any (,,8,a) a) E [H] x S x A, we have
= (Ø(s, a). On + tw A.A) E Rd, and
=.A := p. "hi
E W (s)] + (D(p,,lllA).))
= (s,a)===((s) 2%
Q.A
+ m
inf
The linear representation of the robust Q-function enables linear function approximation for parameter estimation. The definition of parameter wa. involves a regularized optimiza- tion. For any function V : S - IR, the dual formulation of the regularized optimization problem (Yang et al., 2023) is:
E Ex (VT [s]] + ((o(s, D(unl p.))]
(s)= Es)s( 10 (s,
(3.3)
Next, we show that the optimal robust policy is deterministic and stationary. Hence, we can restrict the policy class to the deterministic and stationary one.
Bang V(x) + (DD(ullm() MEA(S)
inf
Proposition 3.3. Under the d-rectangular linear RRMDP, there exists a deterministic and stationary policy n², such that for any (h, 8, a) E [H] x S x A, Vi, ((s) = V/ (s),
-BB a (-(--116) V(s)
)] +a].
= sup o
(s),
where f is the conjugate function of f. We propose to estimate w/ through the ridge regres- sion. We define the intermediate variable (a, := (a) :=
and 0% (s, a) 0 as.
With Proposition 3.2 and Proposition 3.3, we can derive the following robust regularized Bellman optimality equation:
E If and obtain an estimation
[argmin we E a-- (V X||wa13] - - then estimate wh, by wh sup f-xu,, (a) + a).
(65 o7))
w)) + We
(s, = a)(s,a)+
inf
K af a- (() (+)
(.EA5))"P..=0... Ey-Pat 2,0) V (s')] + M(p(s,)) a), ((H)))))))
supaER
Leveraging Proposition 3.2 and the pessimism principle
(s) max Qh as, aEA
(3.4)
(Jin et al., 2021) developed to take account for the distribu- tion shift arising from the offline dataset, we propose the meta-algorithm in Algorithm
A direct consequence of (3.4) is the optimal policy m (=)")) J=z is the greedy policy with respect to the optimal robust Q-functions (Q",") Jh= 1- Thus, in order to estimate t it suffices to estimate Q vh E [H].
Remark 4.2. We emphasize that this general framework may encounter numerical challenges when computing the supremum over a, especially depending the choice of the divergence function f. In particular, the smoothness and cur- vature of the conjugate function f" can significantly affect the stability and efficiency of the optimization. For instance, some divergences lead to non-smooth or non-strongly con- vex conjugates, making the maximization problem harder to
Offline dataset and learning goal. An agent works with an offline dataset D with K i..dd. trajectories collected from the nominal environment by a behavior policy T². Specif- we have
ically, for the 7-th trajectory (8), of f=
4

---

Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization
Algorithm 1 R2PVI under general /-divergence
we estimate the parameter wi as follows
Require: Dataset D, Regularizer
1: init (+) =0 H.... 1 do
4 argmin
Σ (1V (8h+1))om11 wER'
2: for episode
(4.1)
3: Compute A₁ Σ== 0(8 of (56 at +1I
<5 (1) mn) 7 wl2
4: (a))(()= + [x ( of (1 ( D]
> Duality Estimation for general f f-divergence
where 7 is the regularizer in the ridge regression.
5: "h SuPEER ( (a) + +
Remark 4.5. Thanks to the closed form expression of the duality for TV in Proposition 4.3, R2PVI does not need the dual optimization oracle as the DRPVI algorithm proposed for the d-DRMDP (Liu & Xu, 2024b, see their equation (4.4) and Algorithm 1 for more details). DRPVI needs to solve the dual optimization oracle separately for each dimension in each iteration, which is not necessary in algorithm.
6: Construct the penalty (")().).
7: Estimate (--) < min 9, 0n + =
-,, H - -h+ 1
8: Construct ( f argmmx TM
(t
and (-) < (2)())),m
9: end for
4.2. R2PVI with the KI.-Divergence
solve accurately. Therefore, while this framework is general, we highlight that divergence-specifie algorithm designs are necessary to ensure tractability and numerical stability.
Similar to the TV-divergence, we next derive the estimation in Line 4 and Line 5 of Algorithm 1 for KL divergence defined regularization. We first present the duality result.
Proposition 4.6. (Zhang et al., 2024, Example 1) Given any probability measure μ E ASS) and value function V S - (0, H]. if the probability divergence D is chosen as the KL.-divergence, then the dual formulation of the original reg- ularized optimization problem is: inf pEA(s) Esnp (s) + XDxL (allp²) = - -À E [e- (e-Vss)/A..
Next, we instantiate the f-divergence with TV, KL and -dvierggeeee respectively, and specify the estimation pro- cedure corresponding different divergences.
4.1. R2PVI with the TV-Divergence
In this section, we show how get the estimation in Line 4 and Line 5 of Algorithm for TV divergence defined regularization. We first present the following duality result.
The duality of KL also has a closed form. we will shown in Section 5 and Section 6 the closed form solution will reduce the computational cost and also ease the theoreti- cal analysis. Next, we present the parameter estimation procedure. According the linear representation of Q- functions in Proposition 4.1, the duality for KL-divergence in Proposition 4.6 and the linearly structured nominal ker- nel in Assumption 3.1, we estimate the parameter W by two-step procedure. Given an estimated robust value func- tion VA k+t1 we first estimate Egyzee (s)/2 by wh argmin Σ (e- (e-Viri(tL-11>> (65 af) TT)J") + >/ Then we take log- trantsffformaioon to get an estima- tion of wx:
Proposition 4.3. Given any probability measure μ² E A(S) and value function V S + [o, H). if the dis- tance D is chosen as the TV-divergence, the dual for- mulation of the original regularized optimization prob- lem is formed as: inf ((S) Eann (s) + ADrv(ellx()) Ex-no] (s))
Remark 4.4. We compare the duality of the regularized problem in Proposition 4.3 with the duality of the constraint problem in DRMDPs with TV-divergence defined uncer- tainty sets (Shi& & Chi, 2024): inf (Po) (s) = (Vain [Veae. {E>" (V p(a - min. m (a))) The former has a closed form, while the later involves an optimization over the dual variable a. We show later this dis- tinction makes R2PVI much more computationally efficient compared to algorithms designed for DRMDPs.
W Alog max -H/AA.
(4.2)
Note that the max operator is to ensure the vidge-regressinn estimator is well-defined to take the log-tranfformation, and eHHAA is the lower bound on Ex~yuee (a)/A
Remark 4.7. The algorithm proposed by Ma et al. (2022) relies dual optimization oracles under DRMDPs with KI. divergence defined uncertainty sets, while our algorithm takes advantages of the closed-form duality solution. Their algorithm also relies on an additional value shift technique to guarantee the estimated parameter is well-defined to take the tog-rransformation, while our algorithm does not.
Next, we present the parameter estimation procedure. Given an estimated robust value function V/ we denote a1+1 min. 1 + + X. By the linear representation in Proposi- tion& 4.1, the duality for TV-dieereence in Proposition 4.3 and the linearly structured nominal kernel in Assumption 3.1,
5

---

Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization
4.3. R2PVI with the x -Divergence
5. Suboptimality Analysis
remains to derive the estimation in Line 4 and Line 5 of Algorithm for x² <dvieeegee defined regularization. We first present a result on the duality of the >dddiverge Proposition 4.8. Given any probability measure μ² E (SS) and value function V : - [0, H). if D is chosen as the di-dieerge the dual formulation of the original regularized optimization problem is:
In this section, we establish theoretical guarantees for al- gorithms proposed Section First, we derive instance- dependent upper bounds on the suboptimality gap of policies learned by the instantiated algorithms. Next, under par- tial coverage assumption on the offline dataset, we present instance-independee
upper bounds for the suboptimality gap and compare them with results from previous works, Finally, we provide an information cooomatton-thhoreiic lower bound to highlight the intrinsic characteristics of offlin d- d-RRMDPs.
inf Eann ((s) + ADx=(1lll))
(4.3)
(EA(S)
1
sup Vainn Vanx.
T E (V()]a
Var [V))aa}-
Algorithm R2PVI under TV, KL and x² divergence
4A
Require: Dataset D, Regularizer À > 0
I: init v (+) = 0
Next, we present the parameter estimation procedure. Ac- cording to the linear representation of the Q-function in Proposition 4.1, the duality for x x=-divergence in Proposi- tion 4.8 and the linear structure of the nominal kernel in Assumption 3.1, we estimate the parameter w as follows. First, we propose new method motivated by the variance estimation in Liu Xu (2024b) to estimate the variance of the value function (4.3). Specifically, given an esti- mated robust value function V2 and dual variable a, the estimations of E, E (V (s)lax and Ex [V/4,
for episode h = H, ..... do
Compute A. f Σr= 0(5 af (05 aT)" + 71
Obtain the parameter estimation w follows: TV-divergence: use (4.1)
KL--divergence: use (4.2)
Duality Estimation
>=-divergence: use (4.6)
5:
Construct the penalty (t.
> Pessimism
6:
Estimate (.-,)) + min (o)((()))))))))) (,), 0n + w
In( H h + 1)
1+41 (s)la
are:
Construct n.. (-1.) < arginx NA. (Q)())) *x)))
K
and V2(() < (QA(.)) (,-))))))
B [V2) (s)]a= = argmin WER"
h+1 1 (1)+
8: end for
- (s8 a?)) T w2 + 1
(4.4)
5.1. Instance-Dependees Upper Bound
[0.H]
K (1 h+1
Theorem 5.1. Suppose Assumption 3.1 holds. We set y and I's a) = 3 >i
B [V/+ (s)]a =
argmin
(8%
in Algorithm 2. Let 8 (0, 1). /3 is chosen as follows.
we Rd
r=1
(5% a7)) T w) + 2|
(4.5)
(TV) B = 16Hl
[0.
(KL) 8 = 16dXe B/X
/(H/A + EKI.),
where the superscript represents the i-th element of a vector. Then we construct the estimator (. wisel:
(x2) 3 = SLH (1A)))) Ex.
where ετV
2 1124HH and Ex² = log(192K &1 + H/)))*/0). Then with probability at least 1 8. for any E S, we have SubOpt(# s, A) S EHE E PE as)
EKL
1i [V.) (s)
(V)
log(1024d2
max (V((V)) )miin V.A Janan]
(4.6)
4A (V2%
1 Re (V
4A
2 sup (Po) s). where (P'))) is the robustly admissible set defined as
We note that the above parameter estimation procedure in- volves an optimization, which is distinct from that of TV and KL, since the duality of x2 does not admit a closed form expression. Specifically, it estimates the parameter w) clement-wisely. For each dimension, it solves an opti- mization problem over an estimated dual formulation. This parameter estimation procedure shares similar spirit with that in d-DRMDPs with TV divergence defined uncertainty sets (Liu& & Xu, 2024b; Wang et al., 2024a).
(²(P=)=
(5.1)
(Maa))(MM
and UA (
{E (i a))n,
D(H,,illH( S max.es VIA (s)/A, vi [d]}.
up- per bounds on the suboptimality gap, closely resembling the bounds established for algorithms tailored to d' d-DRMDPs with TV divergence defined uncertainty sets (Liu & Xu,
Remark 5.2. Theorem 5.1 provides instance-depente
To conclude, we summarize the TV, KL and x² divergences instantiation of Algorithm Algorithm 2.
6

---

Robust Offline Reinforcement Learning with Linearly Structured f- f-Divergence Regularization
2024b; Wang et al., 2024a). Notably, (PP)) in Theo- rem 5.1 represents a subset of the feasible set Ft. in the d-RRMDP. While the RRMDP framework does not impose explicit uncertainty set constraints, this term naturally arises from our theoretical analysis (see Lemma C.1 and its proof for details). Specifically, we show that only distributions within (P9) are relevant when considering the infimum in the robust regularized value and Q-functions (3.1). Intu- itively, the regularization term in (3.1) should not exceed the change in expected cumulative rewards, so it should be upper bounded by the optimal value function. Similar terms are also found in Zhang et al. (2024, Definition I) and Panaganti et al. (2022, Assumption 1).
For the case with KL-divergence, existing theoretical results (Ma et al., 2022; Blanchet et al., 2024) rely on additional regularity assumption regarding the KL dual variable, stat- ing that the optimal dual variable for the KL duality admits a positive lower bound / under any feasible transition kernel (see Blanchet et al. (2024, Assumption F.1)). However, this assumption presents the following drawbacks. First, is challenging to verify the assumption's 's validity in practice; second, even if such lower bound holds, there is no straight- forward method to determine the magnitude of the lower bound. It can be seen from Table I that the suboptimality bound of R2PVI matches that of DRVI-L (Ma et al., 2022) in terms of d and H. However, our result depends on À which the regularization parameter and can arbitrarily chosen, while the result of DRVI-L depends on 3 which can be extremely small such that / /Be"/22 > H/A More- over, Zhang et al. (2024)² studied the RRMDP with the regularization term defined by the KL-divergence in their Theorem 5 and the suboptimality bound also depends on the term R/A Further, comparing the bounds of P2MPO (Blanchet et al., 2024) and R2PVI, we can qualitatively conclude that the regularization parameter À in d-RRMDDs plays a role analogous to 1/p in d-DRMDPs. This relation aligns with the intuition that a smaller À in d- d-RRMDPs or a larger p in d-DRMDPs can induce more robust policy.
5.2. Instance-Independene Upper Bound
Next, we derive instance-independeee upper bounds on the suboptimality gap, building on Theorem 5.1. To achieve this, we adapt the robust partial coverage assumption on the offline dataset, originally proposed for d-DRMDPs (As- sumption A.2 of Blanchet et al. (2024)). This adaptation is straightforward and involves replacing the uncertainty set in the d-DRMDP framework with the robustly admissible set defined in (5.1).
Assumption 5.3 (Robust Regularized Partial Coverage). For the offline dataset D. we assume that there exists some constant ct 0, such that v(h, s, P)
E [H] x S x (PO).
For the case with x² divergence, our bound is the first result in literature. Compared with the TV divergence, the com- plexity is higher due to the more complex geometry and dual formulation of x² divergence. This observation aligns with findings of tabular DRMDPs with TV and x" divergence defined uncertainty sets (Shi al., 2024). While existing works have focused on the (s, rerttanggl structured reg- ularization, our work fills the theoretical gap in RRMDPs by introducing the d-rectangular structured regularization. a contribution that may be of independent interest.
Ao ビ 1 K c!_ ET . (. |s - s]. s].
Intuitively, Assumption 5.3 assumes that the offline dataset has good coverage on the (s, a)-space visited by the optimal robust policy x" under any transition kernel in the robustly admissible set. With Assumption 5.3 and Theorem 5.1, we present instance-independen bounds as follows.
Corollary 5.4. Under the same setting as Theorem 5.1, if we further assume Assumption 5.3 holds, then for any 5 e 1) and s E S, with probability at least 1 - 8, we have
5.3. -heorrettt Lower Bound
We highlight that in Theorem 5.1, suboptimality bounds under cases with TV, KI., x² ddiverggen share the same term SUpPEz>(PO) Σm= E= .P [[> s). In this section, we establish information theoretic lower bounds to show that this term is intrinsic in offline d-RRMDPs.
(TV) SubOpt(fi 8, A) < /6//2//ETv//eet
(KL) SubOpt (ft, s, A) < 16te x & H + +KL) + Vek:
dd [|o as. 1.ll A, |s1
(x3) SubOpt(ft, s, A) < 8df + 1/AI /VeK.
We compare Algorithm 2 with algorithms proposed in pre- vious works for the offline d-DRMDP in Table 1. For the case with TV-divergence, the suboptimality bound of R2PVI matches that of P2MPO (Blanchet et al.. 2024) in terms of d and H. DRPVI (Liu & Xu, 2024b) and DROP (Wang et al., 2024a) admit tighter bounds on the suboptimality gap, simply because their bounds are derived based on ad- decomposi-
In order to give a formal presentation of the information- theoretical lower bound, define M as class of d- RRMDPs and SubOpt M, R, s, p) as the suboptimality gap specific to one d' d-RRMDP instance M E M. We state the tnforration-theorrttic lower bound in the following theorem.
vanced techniques, such as reference-advantee tion (Xiong et al., 2022). We remark that our analysis can be tailored to adopt the same techniques and assumption, and thus get tighter bounds.
'Zhang et al. (2024) studied the infinite horizon RRMDP with discounted factor 7, we replace the effective horizon length i- by the horizon length H in the finite horizon setting.
7

---

Robust Offline Reinforcement Learning with Linearly Structured f- f-Divergence Regularization
Table 1. Comparison of the suboptimality gap between this and previous works. The * symmol denotes results that require an additional assumption (Assumption 4.4 of Ma et al. (2022) and Assumption F.1 of Blanchet et al. (2024)) on the KI. dual variable, an assumption not required by our R2PVI algorithm. The parameter p represents the uncertainty level in DRMDPs, while À represents the regularization term in RRMDPs. The Coverage column indicates the assumption used to derive the suboptimality gap: the robust partial coverage assumption refers to Assumption A.2 of Blanchet et al. (2024), and the regularized partial coverage assumption represents Assumption 5.3.
Algorithm
Setting
Divergence
Coverage
Suboptimality Gap
DRPVI
d-DRMDP
TV
full
(Liu & Xu, 2024b)
DROP
d-DRMDP
TV
robust partial
0(8/2)22-112)
(Wang et al., 2024a)
P2MPO (TV)
d-DRMDP
TV
robust partial
O(d222--1/2)
(Blanchet et al., 2024)
R2PVI-TV (ours)
d-RRMDP
TV
regularized partial
Ö(P 1/2)
DRVI-L
d-DRMDP
KL
robust partial
O H/
(Ma et al., 2022)
P2MPO (KL)
d-DRMDP
KI
robust partial
(Blanchet et al., 2024)
R2PVI-KL (ours)
d-RRMDP
KL
regularized partial
R2PVI-x² (ours)
d-RRMDP
X2
regularized partial
O(d2 X x-1
Theorem 5.5. Let K > ((d HTcHH//X0 be the sample size, where we have regularizer X, dimension d, horizon length H. There exists a class of d-rectangular linear RRMDPs M and an offline dataset of size K such that for any 8 E (0, s S, divergence D among DTv. DKL and Dx2, with probability at least 1- 6, we have inf; SUPMEM SubOpt(M, ft, 8, X, D) 2 (P Exen ET "E (so, ax) A, 1|s1 =
been used in the literature (Ma et al., 2022; Liu & Xu, 2024a). All experiments are conducted on machine with an 11th Gen Intel(R) Core(TM) i5-1 1300H @ 3.10GHz processor, featuring logical CPUs, 4 physical cores, and threads per core. The implementation of our R2PVI al- gorithm is available at http://giwb..oo///paaaaala//oooe Regularized-Pessin
Value-Iteratee
s). where e is a universal constant.
Baselines. We compare our algorithms with three types of baseline frameworks: (1) non-robust pessimism-base based algorithm: PEVI (Jin et al., 2021), (2) algorithms for d- DRMDPs with TV divergence defined uncertainty sets: DR- PVI (Liu & Xu, 2024b), (3) algorithms for d-DRMDPs with KL divergence defined uncertainty sets: DRVI-L (Ma et al., 2022). We do not implement P2MPO and DROP mentioned in Table I in our experiment, due to the lack of code base and numerical experiment in their works.
Theorem 5.5 is universal information theoretic lower bound for d-RRDMPs with all three divergences studied in Section 5. Theorem 5.5 shows that the cestance-dependen term is actually intrinsic to the offline d-RRDMPs, and Al- gorithm 2 is near-optimal up to a factor 3, for which the definition varies among different divergence metric D as shown in Theorem 5.1. The proof outline of Theorem 5.5 is inspired by that of Theorem 6.1 in Liu & Xu (2024b), but here we need careful treatment on bounding the robust regu- larized value function by duality under different choices of f-divergences. We provide more details on the hard instance construction, the proof techniques, and the comparison with existing results in Appendix D.
6.1. Simulated Linear MDPs
We borrow the simulated linear MDP constructed in Liu & Xu (2024a) and adapt it to the offline setting. We set the behavior policy n² such that it chooses actions uniformly at random. The sample size of the offline dataset set to 100. For completeness, we present more details on the experiment set up and results in Appendix A.
6. Experiment
In this section, we conduct numerical experiments to ex- plore (1) the robustness of R2PVI regarding dynamics shifts, (2) how the regularizer À affects the robustness of R2PVI, and (3) the computation cost of R2PVI. We evalu- ate our algorithm in two off off-dynamics problems that have
In Figure ((a), we compare R2PVI with its non-robust coun- terpart PEVI (Jin et al., 2021). We conclude that PEVI outperforms R2PVI when the perturbation of the environ- ment is small, but underperforms when the environment encounters significant shift, which verifies the robustness
8

---

Robust Offline Reinforcement Learning with Lincarly Structured f-Divergence Regularization
FBVI
10p1
DIMM R2PVI
PEVI (bow))
R2PVLTV
R2PV1
R2PV1
ronord
Average Reverd
DAPVI
R2PVS2"
4-0.6
25
Perfarbation
Perturbation
2/A
priceuu prdc-taliyy
(a) A= 0.1
(b) R2PVI
(c) 9 = 0.9
(d) (up to down) = 1, p 0.2, 0.00..
0.025.
Figure 1. Simulated results for linear MDP. In Figure I(a) and Figure 1(b), the a-axis refers to the perturbation in the testing environment. In Figure I(c), the axi represents different robust level and regularized penalty A, respectively. Figure I(d) shows the robustness of algorithms under different robust level p (DRPVI) regularization penalty À (R2PVI).
dataset learn policy which decides each state whether not exercise the option. To implement our algorithm, we use manually designed feature mapping of dimension d. For more details, we refer readers to Appendix A.2.
(base)
(basc)
R2PATTVV
R2PM-TVV (ours)
R2PAI-I (ours)
Timeda
DRV L
DRPS1
All experiment results are shown in Figure 2. In particular, from Figure ((a) and Figure 2(b), we can conclude that the computation cost of R2PVI as low as its non-robust coun- terpart PEVI (Jin al., 2021). and improves that of DRPVI (Liu & Xu, 2024b) and DRVI-L (Ma et al., 2022) designed for the d-DRMDP. This is due the closed form duality of TV and KI. under the d-RRMDP framework. From Fig- ure I(d), we conclude that R2PVI not only demonstrates robustness to environment perturbations but also matches DRPVI's performance for appropriate values of the robust regularizer and uncertainty level p.
execution time w.E.t N.
(b) execution time w.r.t d.
Figure 2. Simulation results for simulated American put option lask. Figure 2(a) shows the computation time of R2PVI with respect to the sample size N. Figure 2(b) shows the computation time of algorithms with respect the feature dimension d.
of R2PVI. The regularizer À controls the extent of robust- ness of R2PVI by determining the magnitude of the penalty as shown Proposition 3.2. By Figure 1(b), we conclude that a smaller À leads to a more robust policy. To illustrate the relation between the d-RRMDP and the d-DRMDP, we fix target environment, and then test R2PVI with different A and DRPVI (Liu & Xu, 2024b) with different p. We find from Figure 1(c) that the ranges of the average reward are about the same for the two algorithms, though the behaviors w.r.t. À and p are opposite. Thus, we verify that the regu- larizer plays similar role in the RRMDP as the inverted robustness parameter 1/p in the DRMDP.
7. Conclusion
We introduced the d-rectangular linear Robust Regularized Markov Decision Process (d-RRMDP) framework to ad- dress limitations of the d-rectangular DRMDP framework for robust policy learning in literature, improving both the- oretical robustness and computational efficiency. We de- veloped R2PVI, a provably effective algorithm for learning robust policies from offline datasets using f-divergence- based regularization. Our results highlight the advantages of d- d-RRMDPs, particularly in simplifying the duality oracle. Experiments confirm R2PVI's robustness and efficiency. remains an intriguing open question to improve the current upper and lower bounds to study the fundamental hardness of d-RRMDPs.
6.2. Simulated American Put Option
In this section, we test our algorithm in a simulated Amer- ican Put Option environment (Tamar et al., 2014; Zhou et al., 2021) that does not belong to the d-rectangular linear RRMDP. This environment is finite horizon MDP with H = 20, and is controlled by hyperparameter Po. which is set to be 0.5 in the nominal environment, We collect the offline data from the nominal environment by a uniformly random behavior policy. An agent uses the collected offline
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.

---

Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization
Acknowledgements
Liu, Z., Wang, W., and Xu, P. Upper and lower bounds for distributionally robust off-dynamics reinforcement learning, arXiv preprint arXiv:2409.20522 2024.
Z. Liu and P. Xu are supported part by the National Sci- ence Foundation (DMS-2323112) and the Whitehead Schol- ars Program at the Duke University School of Medicine.
Lu, M., Zhong, H., Zhang, T., and Blanchet, Distribu- tionally robust reinforcement learning with interactive data collection: Fundamental hardness and near-optimal algorithms. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024.
References
Blanchet, Lu, M., Zhang, T., and Zhong, H. Double pessimism is provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. Advances in Neural Information Processing Systems, 36, 2024.
Ma, X., Liang, Z., Xia, L.., Zhang. J., Blanchet, J., Liu, M., Zhao, Q., and Zhou, Z. Distributionally robust offline re- inforcement learning with linear function approximation. arXiv preprint arXivv220PP 2209006220 2022.
Garcia, J. and Fernández, F. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, (6(1):1437-143) 2015.
Nelder, and Mead, R. simplex method for func- tion minimization. The computer journal, 7(4):308-313, 1965.
Goyal, V. and
J. Robust markov decision processes: Beyond rectangularity. Mathematics of Oper- ations Research, (8(1):203-22 2023.
Nilim, A. and El Ghaoui, L. Robust control of markov decision processes with uncertain transition matrices. Op- erations Research, 53(5):780-798, 2005.
Guo, Y. Wang, Y., Shi, Y., Xu, P., and Liu, A. Off-dynamics reinforcement learning via domain adaptation and reward augmented imitation. In Advances Neural Informa- tion Processing Systems, volume 37, pp. 1133366-136660 2024.
Packer, C., Gao, K., Kos, J., Krähenbühh, P., Koltun, V., and Song, D. Assessing generalization in deep reinforcement learning. arXiv preprint arXiv: /810. /2282, 2018.
Panaganti, K. and Kalathil, D. Sample complexity of ro- bust reinforcement learning with a generative model. In International Conference on Artificial Intelligence and Statistics, pp. 9582-9602. PMLR, 2022.
Iyengar, G. N. Robust dynamic programming. Mathematics of Operations Reseurch, 30(2):257-285 2005.
Jin, C., Yang, Z., Wang, Z., and Jordan, M. Provably efficient reinforcement learning with linear function ap- proximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020.
Panaganti, K., Xu, Z., Kalathil, D., and Ghavamzadeh, M. Robust reinforcement learning using offline data. Ad- vances in Neural Information Processing Systems, 35: 32211-32224, 2022.
Jin, Y., Yang, Z. and Wang, Z. Is pessimism provably efficient for offline ri? In International Conference on Machine Learning, pp. 5084-5096 5096. PMLR, 2021.
Panaganti, K., Wierman, A., and Mazumdar, E. Model-free robust é-divergence reinforcement learning using both offline and online data. In Proceedings of the 41st Inter- national Conference on Machine Learning, pp. 39324- 39363, 2024a.
Levine, S., Kumar, A., Tucker, G., and Fu, J. Offline rein- forcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint TrXiiv2005.006644 2020.
Liu, and Xu, P. Distributionally robust off-dynamics reinforcement learning: Provable efficiency with linear function approximation. In International Conference Artificial Intelligence and Statistics, pp. 2727. PMLR, 2024a.
Panaganti, K., Xu, Z., Kalathil, D., and Ghavamzadeh, M. Bridging distributionally robust learning and offline rl: An approach to mitigate distribution shift and partial data coverage. In ICML 2024 Workshop: Foundations of Reinforcement Learning and Control-Connection and Perspectives, 2024b.
Liu, Z. and Xu, P. Minimax optimal and computation- ally efficient algorithms for distributionally robust offline reinforcement learning. In Advances in Neural Informa- tion Processing Systems, volume 37, pp. 16602-866544 2024b.
Satia, K. and Lave Jr, R. E. Markovian decision pro- cesses with uncertain transition probabilities. Operations Research, 21(3):728-74 1973.
Shi, L. and Chi, Y. Distributionally robust model-base offline reinforcement learning with optimall sample complexity. Journal of Machine Learning Research, 25 (200):1-91, 2024.
Liu, Z. and Xu, P. Linear mixture distributionally robust markov decision processes. arXiv preprint arXiv:2505. 18044, 2025.
10

---

Robust Offline Reinforcement Learning with Linearly Structured f- f-Divergence Regularization
Shi, L.,, Li, G., Wei, Y., Chen, Y., Geist, M., and Chi, Y. The curious price of distributional robustness in reinforcement learning with a generative model. Advances in Neural Information Processing Systems, 36, 2024.
Zhou, Z., Zhou, Z.,, Bai, Q.. Qiu, L.., Blanchet, J., and Glynn, P. Finite-sample regret bound for distributionally robust offline tabular reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pp. 3331-3339. PMLR, 2021.
Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018.
Tamar, A., Mannor, S., and Xu, H. Scaling up robust mdps using function approximation. In International Confer-
ence on Machine Learning, pp. 181-189. PMLR, 2014.
Tsybakov, A. B. Introduction to Nonparametric Estimation. Springer, New York, 2009.
Vershynin, R. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:101 1.3027, 2010.
Vershynin, R. High-dimensional probability: An introduc- tion with applications in data science, volume 47, Cam- bridge university press, 2018.
Wang, H., Shi, L.. and Chi, Y. Sample complexity of offline distributionally robust linear markov decision processes. In Reinforcement Learning Conference, 2024a.
Wang, R., Yang, Y., Liu, Z., Zhou, D., and Xu, Return augmented decision transformer for off-dynamics rein- forcement learning. arXiv preprint arXiv:2410.2345. 2024b.
Xiong, W., Zhong, H., Shi, C., Shen, C., Wang, L., and Zhang, T. Nearly minimax optimal offline reinforcement learning with linear function approximation: Single-agent mdp and markov game. arXiv preprint arXiv:2205. 15512, 2022.
Xu, Z., Panaganti, K., and Kalathil, D. Improved sample complexity bounds for distributionally robust reinforce- ment learning. In International Conference Artificial Intelligence and Statistics, pp. 9728-9754. PMLR, 2023.
Yang, W., Wang, H., Kozuno, T., Jordan, S. M., and Zhang, Z. Robust markov decision processes without model estimation. arXiv preprint arXiv:2302.01228, 2023.
Zhang, H., Chen, H., Xiao, C., Li, B., Liu, M., Boning, D., and Hsieh, C.-J. Robust deep reinforcement learning against adversarial perturbations state observations. Advances in Neural Information Processing Systems, 33: 21024-21037, 2020.
Zhang, R., Hu, Y., and Li, N. Soft robust mdps and risk- sensitive mdps: Equivalence, policy gradient, and sample complexity. In The Tweifth International Conference on Learning Representations, 2024.

---

Robust Offline Reinforcement Learning with Linearly Structured /Diivegeence Regularization
A. Additional Details on Experiments
In this section, we provide details on experiment setup.
A.1. Simulated Linear MDPs
Construction of the Simulated Linear MDP We leverage the simulated linear MDP instance proposed by Liu & Xu (2024a). The state space is S = {-1, 2z and the action space is A { R At each episode, the initial state always 21- From T1, the next state can be 22, 24, 25 with probability defined on the arrows. Both 24 and 23 are absorbing states, 24 the fail state with 0 reward and Is the goal state with reward 1. The hyperparameter & E IR is designed determine the reward functions and transition probabilities and ò is the parameter defined to determine the environment. We perturb the transition probability at the initial stage to construct the source environment. The extend of perturbation is controlled by the hyperparameter E (0, 1). For more details on the simulated linear DRMDP, we refer readers to the Supplementary A.1 Liu & Xu (2024a).
The hyper- parameerrsestrss in our setting are shown Table The horizon 3, the B, , 6 are set the same in all tasks, the [|]| is 0.3, 0.2, 1.1 in Figure I in order to illustrate the versatility of our algorithms.
Hyperparameters
Table 2. Hyper-parameters.
Hyper-parameters
Value
H (Horizon)
3
/ (pessimism parameter)
1
?
0.1
6
0.3
||||]
0.3, 0.2, 0.1
A.2. Simulated American Put Option
Construction of the Simulated American Put Option dynamics evolves following the Bernoulli distribution:
In each episode, there H 20 stages, and each state h, the
1.028h, w.p Po
8/
(A.1)
0.98sh, w.p 1 Po
where Po E (0, 1) is the probability of price up. At each step, the agent has two actions to take: exercise the option dg = or not exercise a If exereising the option a; the agent will obtain reward 14 = max 100 sj and the state comes an end. If not exercising the option as The state will continue transit based on (A.1) and no reward will be received. To implement our algorithms, we use the following feature mapping:
@ (sh, a) = { [1 (sk) PP (su) .0]
if
.0. O, max {0, 100 |n
if 0
where (s) = max {0. 1 - |sy sı/ Ad], { are anchor states, = 80 8;41 details on the simulated American put option environment, we refer readers to the Appendix C of Ma et al. (2022).
A and A = 60/d. For more
Offline Dataset and Hyperparameters We set Po 0.5 the nominal environment, from which trajectories are collected by fixed behavior policy, which chooses an 0. The 3 0.1 and y are set hyper--arameters in all tasks. For the time efficiency comparison in Figure 2(a) and Figure 2(b), counted the time it took for the agent train once and repeated 5 times take the average.
B. Proof of Properties of d-RRMDPs
In this section, we provide the proofs of results in Sections 3 and 4, namely, the robust regularized Bellman equation, the existence of the optimal robust policy, and the linear representation of the robust regularized Q-function under the
12

---

Robust Offline Reinforcement Learning with Linearly Structured /Diivegeence Regularization
d-rectangular linear RRMDP.
B.1. Proof of Proposition 3.2
Proof. We prove the stronger proposition by induction from the last stage H. Specifically, besides the equations in Proposition 3.2 hold, we further assume that there exist transition kernels (fr) Pt (db pe), such that for any (h, [H] x S.
V/ (s) = B(A)) Σ ar) + X(o(s,, at). ((pella()) = s, (s)
(B.1)
As there is no transitional kernel involved, the base case holds trivially, Suppose the conclusion holds for stage h 1, that say, there exists Prş L h 1, 2. H such that
H
( (s) = 1
Σ
[re(se, az) + a.), 8h+1 = 8,
1=
For the case of h, recall the definition of Q7, we have
H
(s,
inf m= =r)(s,a)+ mEA(S)(T:=(00..
18 PA
Σ
((meelll))))) [re(se az) + X(o(s;,))) D(peel sh s, a,
inf
A(O(sn, an). D(umllu))
H
+ [ Pr(ds'ls,ay () S
Σ (re(se, + X( 0z). D( 8ht1 = S'
1=
S a)
inf
M(o(s, an), D(Hallua))
H
+ / ())
Σ
(re(se, + X(p(s + oz). D(peel 9ht1 = s',
1mh+1
= +x(88,)+ +
PA ((p(sn, an): D(Hall1)) + By (Wtr)
inf
(B.2)
where (B.2) follows by the inductive hypothesis of h+l
(s). On the other hand, we can lower bound 2 ~ a)
= =s)(s,a)= +
inf ME
M(p(sn, an). D(wull())
+ - Pn(ds'ls, ()
Σ 1=++1
[r)(se + A(p(s1, D(pelln))) sh+] s',
2 (n((8,a++
inf ()EA(S)"
Masss an); D(unllm)))
(B.3)
H
+ Pi (ds'(ss))
inf MEAAST"
(PP))
Σ 1=
(re(st, + A(p(s at), D ((ullpu!)) 8441 = =',
=rn(s,a)
inf (hEA(S)).PA-(6..)
X(o(s,; an). D(mmllm))) + EewPh(tlaa) (it
(B.4)
where (B.3) follows by the Fatou's 's lemma, (B.4) follows by the definition of V. (s). Hence, combining the two above inequalities, we conclude the proof of the first equation. Next we focus on the proof of the (B.1), by which we aim to proof the existence of transition kernel [ By the fact that
(s, a) = (n(
inf P.
[E (V [V + A(o(s, a), {|
13

---

Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization
notice that the inf problem above is constraint by the distance D. Therefore by Lagrange duality and the closeness of distribution ((),, there exists fán A(S) Pa (n) such that
( (s, + Ba [+1( + x(o(s, (()))l))))
(B.5)
Now it remains to proof (3.3). By the definition of ( we have
Vi (8)
(B.6)
inf PE=
E (())
(Te az) M(o(s;; D(pella))) =,
H
inf
((P
Σ
[re(s;; a.) + X(0((;, at), ((up)lae)))
= 8, An. = a, π
mEA(S) (0.
REAA
T(cls) PA)
(re(se, + Moo(s, D() [3)1]] sn a, a,
aEA
Σ Q(als) (s,a),
(B.7)
where (B.7) comes from (B.5) and the inductive hypothesis. On the other hand, by the definition of Q (s, a), we have
Σ
(s,
aEA
= ((uss)
inf R==(
E(P (alls))((P1)
Σ (st, ax) + (((()))))) D(uulll)))) -, 8, = a, π
aEd
H
a, where (B.8) comes from the definition of (s). Combining the two inequalities (B.7) and (B.8), we have
< I. aEA
inf
Σ
[re(se, ar) + A(o(st, D( D(u
= Vs),
(B.8)
V (1-)(()>)) (s.
This proves the (3.3) for stage h. Therefore, by using an induction argument, we finish the proof of Proposition 3.2.
B.2. Proof of Proposition 3.3
Proof. We define the optimal stationary policy x* = { as: for all (h E [H] S,
T (s)
argmax (s) (.E
inf
[Ba-A)(la V (s)) A(o(s, D(H
aEA
Now it remains to show that the regularized robust value function V A Qr A induced by policy n is optimal, i.c. for all (h, s) E [H] x S,
V (s) -
V,, -
O7 (8, 2 (s.
By the (3.2), we only need to prove the first equation above, then the optimality of the Q holds trivially. we prove this statement by induction from H 1. For stage H, the conclusion holds by:
V (s) (s) sup ViT. (s)
sup
PN [TH(SH ax) + N(b(H,,H)) D(u ((1m|1p)))) = =, ( ((
inf
14

---

Robust Offline Reinforcement Learning with Linearly Structured /Divergeence Regularization
sup ( (sH))) +
inf (HEAIS)),P=-0ou A(o(s, a), D(u ((
Vi (t).
Now assume that the conclusion holds by stage h + 1. Hence, we have that for all E S,
(s) = Vi44 (8).
For the case of h, by (3.2), we have
Vi ~ (s)
= -aanz
2k
1 (s,aa
-Bawat
a)(s,a)+ +
inf P.
[B Vntt
(s')) (s') + X(o(s, a), ((
a)) + m. Ea (115)
inf
E E |i (s') + X(o(s, a), D (mu
(B.9)
-max
inf (T)(8,))+ ( aEA
[Rgr Vit (s') + (( D( 1()11
(B.10)
where (B.9) holds by the inductive hypothesis, (B.10) holds by the definition of x² On the other hand, recall the definition of A V*) then for any S, by (3.2) have
V (s)
sup VITAA()
"
sup Barnat (-16)
0t 0% (s)
suup Bar
(h(s, + (nEA(S))Rhh=d0m Ex- ( (s)) + A(o(s,)), D(unlla?))]]
inf
sup E Bantu(tb))
inf an( + MEA(S)) ()) + max aEA
[ [B (VTT) + M(D(s,a), D(un (B.11)
inf MEEd1S)
(VTh [ D(p 1(pM))10))]]
V.T (>)),
(B.12)
where (B.11) holds by the fact that (s) S (s), E S, (B.12) holds by (B.10). In turn, we trivially have Vit 2 V/" (s) due to the optimality of the value function. Hence, we obtain V/,"" . (s) (s), Vs E S. Therefore, by the induction argument, we conclude the proof.
B.3. Proof of Proposition 4.1
Proof. By Proposition 3.2, we have
(s, = (s(
inf PA [emPP((ee)) (VTr) ((p(s, a), D(n
(b(s,a),0) + inf m)EA(S)
Eor + A (x a) ()m.H))llee)).))
< a), 0n) + ( w
= (Ø(s.a) a). 0 + w.A.).
Hence we conclude the proof.
15

---

Robust Offline Reinforcement Learning with Linearly Structured f- /Divergeence Regularization
B.4. Proof of Proposition 4.3
Proof. The optimization problem can be formalized as:
inf Es-a V(s) ADrv(ullu²) subject Eu(s) 1,,s(s) 2 o.
1
Denote u(s) u(s) (s), the objective function can be rewritten as:
B (s) + ADrv(ullu)) [(s)V(s)+ Σ (m(s) - =²
[v())(())+*00)) + + 1/2 Σ [x(s)]
Ba V(5)+ Σ ((s)v(()) + 1/2 Σ ly(())-
Recall the constraint Σ. = 00) 2 (s), by the Lagrange duality, we establish the Lagrangian function:
=
max y #20,rER
(Ev(s)(V(s) uls) r)) + 2/2] Σ (())))(s))
In order to achieve the minimax optimality, for any s, term (V (us) -)) + 2/2) should obtain a bounded lower bound with respect to y(s). which requires that p(s); r should satisfy the following conditions:
Vs E (v)) (ss) - - 2/2 + max m - (s)-(ss))
(V() ((ss) S A.
.ES
With the constraint above, we denote g(s) = V(s) u(s), we have
L = max min #20.rER y
>
(V) m(s) ((s) +/2)b/ -
[m(s))((s)}
-E Em(s)a((s)
max max.es (V))) mile
max max, min, g (A { [E(s))((s)) - (8))
Thus have,
Exnp ((s) + (DTv(ulla))
g(s) min, s(5)) { (s(s))((s} Bonu V(s)
= EEsny V(s)+ +
max
= E [V())]Vinutt.)
(B.13)
where (B.13) holds by directly solving the max problem. Hence conclude the proof.
B.5. Proof of Proposition 4.8
Proof. Similar the proof of Proposition 4.3, define y(s) pls) - 1 (s), with lagrange duality, we have:
y(5)2
C Σ v(s)(u(s) + ())))
+ ((()))=)()))())) Σ v(s))
(s)
- (u(()) + (+)((((()) mss) r) + Σ v(s))'(s) Σn
(0(s) C
Noticing that L quadratic function with respect to y(s), therefore after we fix the term p(s), r and compute the min with respect to y(s), we have
1 Σ (s)((()) m(s) r)2 + Σ V(s)u((s) - - -n (s)(()s))
C
41
16

---

Robust Offline Reinforcement Learning with Lincarly Structured f- f-Divergence Regularization
1 4A
Eon IV u!?
(Bonspo (v m1]² Esupo IV 1d]
(B.14)
1
B IV ss]
41 VaT μd]
sup ae(Vmin Vmox]
Bo (V())aa
Var Vareago Vara))o((())la
(B.15)
41
where (B. comes from maximizing r, and (B.15) comes from maximizing (us), 8 and the observation that ((s) (s), Vs E S when achieving its maximum. Hence, we conclude the proof.
C. Proof of the Upper Bounds of Suboptimality
In this section, we prove Theorem 5.1 and Corollary 5.4. For simplicity, we denote o% = O( a,)) According to the robust regularized Bellman equation Proposition 3.2, we first define the robust regularized Bellman operator: for any (h, a,)) E [H] x S x and any function V S A + [0, H].
inf as) == rs)(aa)))+ P.E
[ (e (s') + A( D(unllal))
(C.1)
We have (s, = VT
C.1. Proof of Theorem 5.1
We start from bounding the suboptimality gap by the estimation uncertainty in the following Lemma.
Lemma C.1. If the following inequality holds for any (h, a, [H] 8 A:
VA (8, a) (d(s, ( S (x)
then have
H
SupOpt(2,, 2
sup (EU)(1)) h=1
Σ
B [[Tn(sh = s].
C.I.1. PROOF OF THEOREM 5.1 CASE WITH THE TV DIVERGENCE
Algorithm 3 Robust Regularized Pessimistic Value Iteration under TV distance (R2PVI-TV)
Require: Dataset D, regularizer À 0, y >> 0 and parameter 3
1: init (-) =
2: for episode h = H,
do 3: An +- Σナ=1 (68,, (p( a))) +
4: an+1 min.est 1/ 1 (s)} + A
5:
vn + A. 1 r= (68,, ( 4-1 1 ( (8h+1)
Estimated by (4.1)
Tn(;s) + Di Σi= | )ill
6:
7: (A(+))) + ( (((), + ) - -n( H 11+
8:
(....))) + argmax,, (2)(;)) (+)))) and 1/2 -
9: end for
For completeness, we present R2PVI specific to the TV distance in Algorithm 3, which gives closed form solution of (4.1).
Now we present the upper bound of weights as follows.
Lemma C.2. (Bound of weights TV) For any h E [H] we have
Kd γ
| 112
HVd.
|
H
17

---

Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization
Proof of Theorem 5.1 -V. The R2PVI with TV-divergence is presented in Algorithm 3. We derive the upper bound the estimation uncertainty (s, a) prove the theorem. We first decompose the difference between the regularized robust bellman operator Th and the empirical regularized robust bellman operator Ty
Th 4+1 (s, (0(s, a), 2
(C.2)
Σ a)s v
Σ (8 a) (10,( - mnAi)]
K
( ():A, 2 + Σ a)
Σ
Φ a D (+))amn
(C.3)
S 7
(1:
Σ 0(5% 0 mn ( (saant))lll)
(C.4)
(
where (C.3) comes from the definition of wi while (C.44 follows by the Sauchy-Schwarte inequality. By Lemma C.2 and the fact that h+1 (s) S H and = I, we have
ii
AA
A 1/2 w ll S HVd.
where the last inequality comes from the fact that || ب Now it remains to bound term (ii), as V depends on data, which makes difficult to bound it directly by concentration equality. Instead, we consider focus on the function class Vn (Rg, Ba. 7):
VA (Ro, Bo, 7) = [Vi (,,0,,;,,,,000 A) S + [0, H1, 1111|2 S Ro, 3 E [0, Bol, Ymin (An) 2 7h.
where
m T T Ede (1, 1 By Lemma C.2 and the definition of V k+1 when we set Rg H KK/d BB B = 16Hd/EEv.... suffices show that V V441(Ro, Bo, 7). Next aim to find union cover of the Vh+ (Ro Bo. 7), hence the term (ii) can be upper bounded. Let Ne: (;; Ro, Bo, 7) be the minimum e-cover of Vn (Ro, Bo, A) with respect to the supreme norm, No, H)) be the minimum e-cover of [0, H respectively. In other words, for any function V E V4a Ro, Bu, 7), an+1 E [0, H). there exists a function V E Vv (R. Bo, 7) and a real number a₂ [0, Hf] such that:
sup
V++) V'()) S Se,aa, la, -a+il S.
SES
By Cauchy-Schwartz inequality and the fact that ||a + b1l S 221|a|3,,, + 211b11 and the definition of the term (ii), we have
K
(V -Vitalooe) |
( < 2
(5s%, a
+2
Σ
(6%% (1
A,
A,
T=1
T=1
K
Ss at an - (V/+1lae) /2
2 (C.5)
< 4
(5s), (1
+4
Σ
A-
A-1
?
where (C.5) follows by the fact that
K
2²²K²
(1h,
- -V/4
2
Σ
3 -1 06
A,
7
r=,,-==
18

---

Robust Offline Reinforeement Learning with Lincarly Structured f-Divergence Regularization
Meanwhile, by the fact that ila. [Vi+ila.
1V2 Vittl have
4
Σ
( o
([V [Vitllan A
(C.6)
K
4
A 0% max (1V 1l.))
T= 1,t/=1
K
S
4c
T=1,7/m1
(C.7)
?
By applying the (C.7) into (C.5), have
6c2
(ii)² < 4
sup
Σ S (1
A
(C.8)
(e o, eNa (()
By Lemma F3, applying union bound over Nu Ra, Bo, ?) and N₁. (10, HI],, with probability at least 8/2H, we have
K
6E2
4 V (e (0..
sup
Σ
(
+
A_1 7
W Ro, Bo, 7) [[, H)) + d (dlog(++//1)) + 6e
411² 22og
(C.9)
6
Applying Lemma F.1. we have
log (e; Ro, Bo, A)1 - dlog(1 + 4Ro/c) + log(1 + 8d 8d2/2B8/773
= dlog(1 + 3 + d log(1 + 8d- BB K2 H-2)
S 2d log(1 + 3/2 x
(C.10)
Similarly, by Lemma F.2, we have
(() S 311ee.
Combining (C.10) with (C.8) and (C.9), by setting e = dH/K, we have
2H| (e; Ro, Bo, n) ([,, + looggll11111 + KK/)) 6E²K²
(i)² < 2 2 2og
< 16H (g dlog( K) + 2H/5) 6d H²
log 8d
+ =
3/8 - log H/
< 2d log 8d 3/2 13
22 log 1024Hd <TV/6
=32H² 6 (log 1024Hd R2 5 (Tv)
< 64HH2 ETV == g²
Recall the upper bound in (C.4), we have with probability at least 1 - 6,
[T/ V/ (s, a) (cb(,, a), w
K
(o: // + Σ (s)
Σ
p(s ((s). (1V) (8))a))))))))
A7
1m1
19

---

Robust Offline Reinforcement Learning with Linearly Structured f- /Divergennce Regularization
( 1oo1:,0).1la--
(C.11)
where (C.11) follows by the fact that 2H < 3. Hence, the prerequisite satisfied in Lemma C.I, we can upper bound suboptimality gap as:
SubOpt(
2 5
sup
Σ ET
(sh, =s]
PEU (PO)
H
= 28.
sup
E
10: a) a) =
PEU (PO)
h=1
This concludes the proof.
C.1.2. PROOF OF THEOREM 5.1 CASE WITH KL DIVERGENCE
Algorithm Robust Regularized Pessimistic Value Iteration under KL. distance (R2PVI-KL.
Require: Dataset D. regularizer > 0, > 0 and parameter 3
1: init (.) = 0
2: for episode
H,
do
Ap Σ Φ ( ST 9))
K
T + Plays (o
un t A (E $18%/ Je
4:
5:
f - log max { 11//- e -HIA]
6:
Tx(:s)) + Di= | -)ill,,,
7:
(A())) (i ((O, + ( In(-,),, -
8:
(....)) + argmax,, (QA(,))) T (-I-)) and (2) (.
9:
end for
For completeness, we present the R2PVI algorithm specific to the KI. distance in Algorithm Note that we have used the following closed form solution
Vi Vatil
W// argmin weRd
(655h10)) w)) + 7
(C.12)
K
2 (5
A
(C.13)
Our proof relies on the following lemmas on bounding the regression parameter and c-covering number of the robust value function class. Lemma C.3 (Bound of weights KL), For any h E [H].
Kd
w l2 S Vd. (dd1 S
Lemma C.4 (Bound of covering number KL). For any h E [H] let Vn, denote class of functions mapping from S to R with the following form:
(x; 0,3,A)) = max { a) Alog (1
aEA
i=1
20

---

Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization
the parameters (0, A,)) satisfy ||0||2 L, [0, Ymin 7min 2 7. Nete) be the e-covering number of V with respect the distance dist(Vi, V2) sup, [V)))) |2(er)|TThen
log (c) - d + 4L/c) + de log(1 (X
Proof. The R2PVI with KL-divergence is presented in Algorithm 4. Similar to the proof of TV divergence, decompose the estimation uncertainty between Th and T% as:
(1t2 (0(s, a), الاهع = [ a) (0n - Aog w 0, + Alog max( h/1
= ()) (A (Alog max (20/, H/1} - > log w/)
d
max
H//}
Σ (s, log
What
d
max
11/23
$
X
(1 a)
log
wh
$ A
Σ
$1(8, a) log (1 + 4/² max -H/A wh,l))
(C.14)
1=1
<
01(3, a) log (1 e eete // wh.el)
(C.15)
==1
d
< Alog
Φi(s,a) + 1/1 Σ Øi(s. a)1t - whil)
(C.16)
= Alog (1+ Σ or a)1,71011 100h -wwh))
where (C) and (C.15) comes from the fact that:
E Eo [e 1 = - -/A ||log A log B = log (1
IA B
Wha =
min A, B}
and (C.16) comes from the Jensen's inequality applying to function log(x). Therefore, our next goal is to bound the term Ee ()) 100%, w Specifically, have
d (s, 110%, - -wAl
K
(1 1) w// - -A,""
-A Σ
1b))
A
k
P (on+))
Σ
(5(8, a)1] w// -,711 11
(T()))
wa + A Σ
(T(
wp -A,77 Σ (0))e
K
k
k
= Σ (i(8, a),
(1w
A
(10)))
+ A
A Σ
(0%)e
Next, we upper bound term (i) and (ii), respectively. For the first term, we have:
as (0 Σ (1 a)s - (A, - -
21

---

Robust Offline Reinforcement Learning with Linearly Structured /-Divergence Regularization
0i(s, a)1; A 1
S Y
[ a)la))11111 "l, ///w A
(C.17)
d
$ rvd
|o, a)l,ll,,*
(C.18)
where (C.17) follows from the
incquality, (C.18) follows from the fact that:
| || 11
S vd/r,
where the last inequality follows from Lemma C.3 and the fact that || S s Now remains to bound the term (ii), by the definition of 77 (f) E E 12 f11 the term (ii) can rewritten as:
1 (0)) wh - R (ma+1)
(ii) Σ 0i(8, 1 A Σ
T=1
(i a)1, A
1 Σ
K
1h (e
)
7=1
(1: (0)(s,a)lillA,
Σ
Th
mh
A
(ii)
For the rest of the proof, it's left to bound the term (iii. As the V depends on the offline dataset, which makes it difficult to upper bound directly from concentration equality due to the dependence issue, we seek for providing a uniform concentration bound applied to the term (iii), i.c. we aim to upper bound the following term:
T (e *) AR
sup VE 1 B,))
Here for all h E [L)) the function class is defined as:
VrRR (V An) 11112 R, B), Jmin (nn)(An) 7},
Alog(1 where (2; 0 3, m --olog(11111) +
+ (1.l1,)) - In order ensure V
Vn+1 (Ro, Bo, A), we need to bound 0, = 0₁ - A llog max f , H/2j. Following the fact that:
1 - |0 + Al| log max f H1/x
By Lemma C.3, e- 1// < max ///3 < max ||0x1110011111 m1/3 s max / Kd/A, e m/A3, therefore the term be bounded as:
Kd .H/2)
10 Vd XVamax (log V
< <HVd+aVKX
$ 2HHVKKA
(C.19)
Hence, we can choose Rg 2H KA and B, = 3 = 16d 1/X
(H/+ + EKL). then we have for all [H], V e
Va+i Ro, Bo, 2). Next we aim find a union cover the VA+1 Ro, Bo, 7). hence the term (iii) can be upper bounded.
22

---

Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization
For all e (0, A), [i) let (e R, B) supreme norm. In other words, for any function V E V4 (R, A), there exists function V E (N)11(c) such that
(e)e) denote the minimal e-cover of (R, B, with respect the
12 (z) (+)+(t)) S.
sup #E$
Hence, given 1 4/4 satisfying the incquality above, recall the definition of nh = (T( = PRd 15)+))) we have:
mh e
(
mi e V/4z1(0)
)
(ot)
E Vitz(1))
< E P2(10011))))
-
+e
P Vh+sle))
Patilent1) e + x - Vhtilent?
s 2e/X+ + 20/A = 4E/2,
(C.20)
where (C.20) follows from the fact that for any E S.
(0) 1i4
Se
- -1 -1 1 26/2,
where the last inequality is held by the fact that e E A). By the Schwartz inequality, for any two vectors b E Rd and positive definite matrix A E Rdddd it holds that |la + bll $ 2||a||2 + 211bll2 hence for all à E [H) we have:
(1ii) 2 <
2
Σ
K
(o x
2
K
0
mh
ni (e
A
T=1
(/
2
K
< 2
Σ
+ 32222/A /X3
Σ
1 |
T=1
T,T'=1
2 sup (eN
Σ
K
V(el
|
+
3262K2
(C.21)
A,
X27
We set f()) = = V(a)
x, by applying Lemma F.3, for any fixed h E [H] 6 E (0, 1), we have:
P sup veN
Σ
K
Honh c (1)) ) KK, A,
2 22(2 H + dlog (1+ K x 8//H.
(C.22)
1=1
Hence, combining (C.22) with (C.21) and let y = 1, then for all h E [H] it holds that
K
1oi (z)
I|a_. < 82(100 ((N)+ + d log(1 + K) +
1=2K2
(C.23)
8
X2
T=1
with probability at least 8. By Lemma C.4, recall L Ro 222HHKKK
KX in this setting, we have
log((Nn+1(e))) dlog(1 + 4Ro/e) + di log + 8X 3x
(C.24)
We then set = dA/K E (0, A) and define 3' = 3/>e = 16d (H/d/ EKL) for brevity, then (C.24) can be bounded as:
log((NN++1(E))) < dllog1 + k/oK/d)) + di log(1 32 3/2 2 gr2)
= dlog(1 + (RoK/ + of log(e 2H/A + 8x2 -3/23 + 2d H/A
< 2d
+ 2d l/
23

---

Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization
Therefore, by combining the result with the inequality (C.23), we can get
Σ
K
(c
||2 An"
2 (2
+ 4d H/X 4d log(8X k2 + 4d + d'log(1 + k))
88(4d 4d log 8X Hd 8/2
(C.25)
8 H + 4d log 8X K Hd Hd2 (8) + 4ef log(
s 1/4
(C.26)
where (C.25) follows by the fact that 2og # 4d + dlog + K) I 4d log( 8 and (C.26) is held due the fact that
1024dA
/4 64d
H// log
8
1024d/222K
= 8((8 H/1 H/8ddH/A>-1
4d log 8X K Hd 3/2 3/2/8) + 4d log
+ 4d log
5
2 8 4d - 4 18g K Hd 3/2 3/2 + 4d log 10g(
8
(C.27)
where (C.27) holds by
1024dA2K'
log(B²3) = log (256d H// + log
8
1024dA2
< log(256d
(H/2 + log
1024d + H/X.
- log((28) + log 5
By the bound on (i), (ii), (iii), for all h H and (8, a) 8 x A. with probability at least 6, it holds that
IAAV T a) (Ø(s. a), w s Alog
( (VV $8/2)//12)))) Σ (oo(ss ())lla.))
< Alog
1 + /l/l//g gr
(C.28)
a
(C.29)
where (C.28) follows by the fact that 3' > 2dd, (C.29) follows by the fact that log(1 + x) s æ holds for any positive Thus, by Lemma C.1, we can upper bound the suboptimality gap
SubOpt(f1 (f) 2
sup (PM)
E P PPPPP
1=1
H
d
= 28
sup rEU (Po)
E
(ore(s a
h=1
Therefore, we conclude the proof.
C.1.3. PROOF OF THEOREM 5.1 CASE WITH x² DIVERGENCE
For completeness, we present the R2PVI algorithm specific to the x2 distance in Algorithm 5, which gives closed form solution of (4.4) and (4.5). Before the proof, we first present the bound on weights under -ivveregeeee: Lemma C.5 (Bound of weights x²). For any [H].
H²
|ج l2 S Vd H
2X
24

---

Robust Offline Reinforcement Learning with Linearly Structured f- /-Divergence Regularization
Algorithm 5 Robust Regularized Pessimistic Value Iteration under x² distance (R2PVI-X²)
Require: Dataset D, regularizer À >> 0, > 0 and parameter B
1: init (-) =
2: for episode
H .... do
3: An f -Er @65 ( RR) T 71
4: E
(8)1 (V
( @(8 ah) h+1 (8% 1511131))lo.m
[V/
Estimated by (4.4)
5:
BA (V44 + [A
(1==1 (5% ah TV
h+2 (5% (6 1o
Estimated by (4.5)
6:
Estimate 2i,,, according (4.6)
7:
Tn(:s-) + 3 Di (| A)AA,
8:
+26,)) minf (T + wx [x(: - 11+1
9: (....))) +- argmax,, nn (2)(.)), TH (+)))) and ())() < (QA()))
end for
Proof of Theorem 5.1 xx2. The R2PVI with x² diveerggee is presented in Algorithm 5. By the definition of Th Th
have
Ty V/ (8, a) (0(s, a), w = ((), ( (0)- + w - 0n 20²)
(c(s, wh/a))
= Σ (s, a)
sup
[aang (V + (Bs
1
[V (+))a))
1
Bonag
1 (+)
()(0,
41
41
sup [E(U,H]
Ti (12+1 (s))a
(BBRh. (V (5))a))
1
Rr
(V2 (s)
(C.30)
41
To continue, for any E [d], we denote
1 Bonpg (V/ (+)]
a₂ = argmax oE(O,H]
E Bowag (s)la + 41 (Bowng,
41
Hence, (C.30) can be further upper bounded as
Th as) (p(s, a))
(1 a) () (Eanpp IV++ (s)]ar - Buh (V2 (5))as) (1. (Eamag, [VA+ (s) + Buh 1
(8))ar) +1)
d
Σ
0 a) (Es-ng ( (s)a,,)) - Ech. (
(C.31)
Next, we bound (i) and (ii), respectively.
Bounding term (i). We define
S [V:1
h+ (s)]a-
argmin
Σ
(o (5h+1))a $68 aT) w) 7//
25

---

Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization
Considering the gap between the Eul.: (V (s)la, and B ( due the definition that Buth (V) [BAR.: [V h+ (0,1. we eliminate the clip operator first. We rewrite (i) follows:
① Σ (i(s, (s)lo, E ( ( (Bo-OR (5)1
+B (htt,, +
($))))) +1)
Σ (s) [ (s)]a. EaR.. S (s)las)
B [V h+ (s)]o.
Bah. [V 1+ (s)la.
(Br-gg 17 (+))())) + +B (1/+
41
B [V2 h++ (s)la:
Ea8.1 (
We claim that 112 Vi H). We prove the claim by discussing the value of Buh.. (s)]a the following three cases:
Case I.
B (1 (t)la, S O. By the fact that Eanpy
I (s)]a, S H. we have:
E Eanug 1V (s))a.
[c,| ( Wo (V (s)lor +1)
$1+
E Eauph IVA, h+ (s)la, BAh IV (s))
where the equality holds by Ta (V (s) + +1 H/4X. Hence the claim holds by Case I.
Case II. 5 2 [V (s) S H. The claim holds trivially, as we have:
|C = 4X
+1 E (Eamp (V2 (s)]o, + +Euh [V ()) +1 H/2x.
Hence, we conclude the claim.
Case III. G 1+1 (s)]a, > H. Notice that
(1)
1 B Bawu (s)l + +H) +1)
E Bawph [V2
h++ (s)]a, H
|c,|
44
41
E Bxp [V/2
h+1 (8) (8)) Beuh, (V (8))
H E Egnph 1V/ (s)
4A (Eampg
(V (5) + H) +1
& [V (s)la, Esnuo (V (s)]or
S H/2x+1,
(C.32)
where (C.32) holds by the fact that E IV. ( (s)) H. With the upper bound for C₁,, we can upper bound (i) as
(
0i (V - (V
K
d. a 1,
(V) C++ + Σ 0s
"
S05 a
(12
1=1
1=1
r=1
K
[0((s.a)1:llA; (H (,H + Σ
< (1 + H/2X)
(C.33)
26

---

Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization
Bounding term (ii).
Similar bounding (i), we can deduce that:
d =
(i)
Σ
(s a) (B 1 (ot1(s) - BBRR 1V/ (s))
1=1
K
$ H Σ
+
Σ (o.
Σ
O(s a
((V Ar
(C.34)
where (C.34) follows by the Cauchy Schwartz inequality and the fact that Bg combining (C.31), (C.33) and (C.34), we have
[s) S 11, E [d]. Hence
T (s, (Ø(s, a), (,,)
d $ (1 + H/2A) (
K
1 1 1)l +
Σ
(
Σ
( a MT (1 A.
1=1
K
+ Σ (0)
Σ
1 oh 11 (1V 1 |
On the other hand, we can similarly deduce that there exists a4 s.t.
(Ø(s, w) - Th
V.A VA Wh+ (s,
<1 H1/2) (H Σ a
Σ
() Σ als (1 (1
K
+ + Σ a))ll, +
Σ (l.
Σ
Sss and
(1
i=1
Then for all i E [d]. there exists à, E {as, agJ. such that
[T 1 a) (Ø(s, a). e
< (1 + H/2A) (7 Σ (1) + +HH² Σ (s
K
1))(a, H12
H/2X)
Σ (S5 ab) mI ([V
+
Σ
(b a
A.
Now it remains to bound the terms
K
K
(S a mn ht 11
and
Σ
(
a
12.
(ii)
(iv)
Similar to the proof in KL divergence, we aim to find union function class Vh+1 (Ro Bo, A), which holds uniformly that 1411 E (Ro, Bu, X), here for all h [H], the function class is defined as:
(Ro, Bo, A) = (Vi 0, A) S + [o, HJ 101|2 S Ro, 3 E [0, Bol, 7min (Ap) 2 2
where Vx; 0, A) = maxxcxl((55 a) To TO 3 3 (s, a) A -1o. By Lemma C.5, when we set Ro Vd(H + 2 /22) By = 3 = 21 + /Ex> it suffices to show that V E Vh+i Bo, 7). Next we aim to find a union cover of the Mh+1 (Ro, 7). hence the term (iii) and (iv) can be upper bounded. Let Mu(e; Ro, Bo 7) be the minimum e-cover of (R, B, X) with respect to the supreme norm, N₁. (i, H]) be the minimum c-cover [0, H]
27

---

Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization
respectively. In other words, for any function V E (RR B, [0, H], there exists function V' E VR B) and real number o, E [0, HJ such that:
sup
IV(s) ['()) c, l se.sc.
#SS
Recall the definition (iii) and (iv). By Cauchy- Schwartz inequality and the fact that ||a + bll - 22||al A,'' we have
+ +211b12,,"
k
k
(iii) 2 < 2
( 0 ([
+
Σ
( 0 mT ([V - -1 (Vetalaa)
12
A
Ax
2E2
(5 a (LV
+ 4
Σ
(( 0 m. (T
+
(C.35)
A
A,
7
r=1
where (C.35) follows by the fact that
2
k
Ssh of 11
(1
(V 1V A
)|2
K $26
Σ
222
h
T=1,7'=1
Meanwhile, by the fact that IV%+il.,1 $ $1i==1 Vi4tt. we have
K
(VV/41la - (V AT (s af mm
K
< 4
Σ
10 ( n 05 max bo (17 bl110. (Vo+1l.))
1=1,7/=1
K
< 46
A
-
1=1,7'=1
4c2 4e2K2 K
By applying the above two inequalities and the union bound into (C.35), we have
K
)/2
662
(iii) < 4
sup
Σ
(5 (l
(e EN ())
A,
7
By Lemma F.3, applying union bound over (n; Ra, Bo, 7) and N₁. (10, HI),, with probability at least - 8/2H1 we have
K
6E2
4 sup Bee (N.
Σ
S0s a a
A,
2H WN(e; Ro, Bo, 1) (10 H)) + dog((1 + k//))= 6e2
< 4112((100))
5
Similarly, by the fact that ||a + bll2 A,
S 2||a|13 A,"
+ 21112
noticing (iv) has the almost same form as (iii), we have
(iv)2
2
K
2 a. mm (1V2)
||3
2
+2
Σ
S a Dmd (1V)
12
2
A
A
T=1
1=1
K
24H2
<
Σ
(s a, m (1V2
(C.36)
A
28

---

Robust Offline Reinforcement Learning with Linearly Structured /Divergeence Regularization
where (C.36) follows by the fact that
K
2
2
( a (
-
SH² 18Anle
Σ
A 8 -
7
1=,,7=1
and
K
Σ
(sh o
([V h+1le 11
7=1
<
0% A -1
max 1 (1V
[V++
f=1,7/=1
K
< 16
A Φ
-=1,-/=
16H
We upply the union bound and Lemma E.3, with probability at least 8/2H
(iv)2 s 4H1 (21og 2H (Nae; Ro, Bo, 1)l H])l + dlogg11 + k//i) + 24H12 K2
5
?
Therefore, with probability at least 1 - 6,
1 1 (8, a) (1((s, a), wb2i
(C.37)
$ hH((1 + H/2A) Σ [ 2
aillll)
d
K ( (1+ H/2A)
K Σ
+
Σ
Σ
Ssh az (n (172
+
Φ( a nm
(1V. b+ 12.12
1=1
Σ
(1 a 1
7H(1 H H/2X)
1=1
2H WH(N Ro, Bu, (1,, H))
6E2 622
+ (1 + H/22))
4H2 2log
+ dog((1 + (K/7))
[H Ro, Bo, W0, H)) + dlog(1 + dlog(1+K//)) +k/1))
24H22K2
+ AH (2
2
(C.38)
By the fact that Ro Vd(H /22),,, Lemma F.l and Lemma F.2, upper bound the term [N (E; Ro, Bo, 7)1 and [[, H)) as follows:
log (c; Ro, Bu, 7)1 & dlog(1 + 4Ra/c) + d² log(1 + ////////)))) (a, HI) s log(3H/c).
We K.7 1, with the upper bound above, have
WN( Ro, Bo, (o, H)) + dlog(1 + K/1)) + K22
2 2log
6
< 4H² 2 log
+ d log(1 + K) + dlog(1 /2 + H| (/) + df log(1 + 122 + +3/2)
K
< 4H²
2d
+ 2dlog(K) K) + doog(d /2 + H K) + 2d log 1/2 3222k²²))
8
29

---

Robust Offline Reinforcement Learning with Linearly Structured f- f-Divergence Regularization
6H K
S &H log
+ log K) + log(d" K/2X)K) + log 8d
= (log 48K d + H/2
Similarly, we can upper bound the third term in (C.38) as follows:
4H (2 2H]Nu[e; Ro, Bo. (O, HD) d'log(1 + (llo((++K/7)) + 24H2
5
H2 (2 WH/ Ro, Bo, ((O, HI) dlog(1 + K//))) + 24c2K2 K2
8
7
< &8 de (log 48K H² d(1 + H/2x)/6).
Hence, apply this bound into the (C.38), have Ko(s, a), w
TV 11
0 ()),,)))lll,; (H H H/2X) (1 (D
(C.39)
[ 1 H 8(log 192 log Ex²)
Σ 22H H))dd /8(5x + tog
x 8
( a)
(C.40)
where (C.39) comes from the fact that + 1/A S 1+ H/2X, the (C.40) comes from the fact that 1xz S Exa. Hence, the prerequisite satisfied in Lemma C.I, upper bound the suboptimality gap as:
H
SubOpt(ft, 8, 2
sup PELL (PD)
E
11) = s]
23 sup (PM))(P))
ET
P
(1)l,, -
h=1
This concludes the proof.
C.2. Proof of Corollary 5.4
Proof. The proof follows the argument in (F.15) and (F.16) of (Blanchet et al., 2024). Specifically, we denote
P = E=", .P (oe( as an) (dhi((,, (n)())),.))1.)) 81 = s). v(h,i, P) E [M] x [d] x (PO).
(C.41)
By Assumption 5.3, setting 1, we have
sup (EM((19)
Σ B
(oi()))a))) dilila =
H
E= pP
TTr (o) an) A A =
sup (PU)(PP)
hm 1=1
30

---

Robust Offline Reinforcement Learning with Linearly Structured /-Divergence Regularization
sup (EMA((P)
Tr (B (nn |s1 =s
(C.42)
h=1 t=1
sup (PU)
Tr pA (I+ K. A
(C.43)
1=1
H
(Ba* Ploee(nn )8) s))²
sup (PU)(PP)
1 ct K. (E** , por Sh: s12 s))2
h=l i=1
sup (P
e
(C.44)
dHl
V
where (C.42) is due the Jensen's inequality, (C.43) holds by the definition in (C.41) and Assumption 5.3, (C.44) holds by the fact that the only nonzero element of A is the i-th diagonal element. Thus, by Theorem 5.1, with probability at least 1 - 8, for any E S the suboptimality can be upper bounded as:
d
3dH
SubOpt(# 8, S 8
sup PEU
Σ
E
( =s
Vet
where
STHdVEET.
if TV;
8
16d V(H/+ {KL),
if KL; x
8dH (1+1/
Hence, we conclude the proof.
D. Proof of the Intormation-Thooreele Lower Bound
In this section, we prove the information-theorrtic lower bound. We first introduce the construction of hard instances in Appendix D.1, then we prove Theorem 5.5 in Appendix D.2
D.I. Construction of Hard Instances
1- D)
1-6
1
81
81
82
+ A D)
6
(a) The source MDP environment.
(b) The target MDP environment.
Figure The nominal environment the worst case environment. The value on each arrww represents transition probability. The MDP has two states, 81 and 82, and H steps. For he nominal environment on the left, the is the good state where the transition is determined by an error term é, and 82 is fail state with reward 0 and only transitions to itself. The worst case environment on the right obtained by perturbing the transition probability at each step of the nominal environment. The magnitude of the perturbation () D) each stage h depends on the divergence metric D, the regularized À and the parameter
The construction of the information theooretc lower bound relies on a novel family of hard instances. We illustrate one such instance in Figure 3. Both the nominal and target environments satisfy Assumption 3.1. The environment consists of
31

---

Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization
Two states, 81 and 82. In the nominal environment Figure 3(a), 81 represents the good state with a positive reward. For any transition originating from 81, there is probability of transitioning itself and probability of transitioning 82 regardless of the action taken, where is parameter to be determined. The state 82 is a fail state with zero reward and can only transition to itself. The worst-case target environment Figure 3(b) is obtained by perturbing the transition probabilities in the nominal environment. The perturbation magnituee ( D) depends on the stage h, regularizer X, divergence metric D, and parameter
The family of d-rectangular linear RRMDPs are parameterized by Boolean vector & (Eetn where &n {-1,1] For given & and regularizer the corresponding d-rectangular linear RRMDP M constructed as follows. The state space S = [2) and the action space A = {0, 13. The initial state distribution fi is defined as
(s())) = + and Mo(x2) d+2 d ++2
The feature mapping Φ 5 R is defined as
d
2(81,0) (4)
ad
Σ
a
d
((32, =0,,0, .,0,..,,,,0011,
which satisfies (s, a) 2 and Σ 0i(s, a) The nominal distributions (12 [ he(m]
are defined as
1 (1 e) + ed (1 ()-e) + ......... ... , (1-e)de, ed doz) T wh E [M]]
where is an error term injected into the nominal model, which is to be determined later. Thus, the transition is homogeneous and does not depend on action but only on state. The reward parameters (en)e are defined as
0 5 [hi +
EΛ2 +
End + 1 wh E [M],
2
2
where is a parameter to control the differences among instances, which is to be determined later. The reward ra is generated from the normal distribution ra. ~N(rn an), 1), where (s, a) $(s, a) On. Note that
The (s,, a) = a))11a)) TO, = 2 (EE. a) + +d) 2 o and (5 a) = ( a) T o = O, Va NaEA A,
2d
Thus, the worst case transition kernel should have the highest possible transition probability to $2, and the optimal robust policy should lead to transition probability to 82 small as possible. Therefore the optimal action at step h is
1 + Ev1
1 Ex2
1 End
2
We illustrate the designed d-rectangular linear RRMDP Ma in Figure 3(a) and Figure 3(b).
Finally, the offline dataset is collected by the following procedure: the behavior policy n² (m/) be(H] is defined as
o Unif((e1, , ea. 0}), wh [H],
where (erheedd are the canonical basis vectors in Rd. The initial state is generated according to po and then the behavior policy interact with the nominal environment K episodes to collect the offline dataset D.
Remark D.1. We would like to highlight the difference between our hard instances and the hard instances developed in Liu & Xu (2024b). We find out that instances developed in Liu & Xu (2024b) only allow perturbations measured in TV-divergence. The reason is that in their nominal environment, both s₁ and $2 are absorbing states, and thus ( (s, a) only has support on s, which could be either 81 82, In this case, any perturbation to (- a) would cause violation of the absolute continuous condition in the definition of the KL-divergence and the x² -iveerggeec In comparison, we inject
It has been shown in Proposition 2.5 of Lu et al. (2024) that the TV divergence be extended to allow for two distributions with different support.
32

---

Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization
small error in the nominal kernel such that (-]ss, a) has full support {51, $2) when the transition starts from 81- Hence, can make perturbations (-1ss,,, a) safely without violating the absolutely continuous condition. Additionally, Liu & Xu (2024b) only construct perturbation in the first stage, while we admit perturbation in every stage h in order make our instance more general.
D.2. Proof of Theorem 5.5
With this family of hard instances, are ready to prove the information--theoree lower bound. For any & E (-1, let Qe denote the distribution of dataset 'D collected from the instance Mg. Denote the family of parameters as S = 1-1,1 and the family of hard instances as M = {M & E 22. Before the proof, we introduce the following lemma bounding the robust value function.
Lemma D.2. Under the constructed hard instances in Appendix D.I, let å = d3/2/v2K and K > d (2AF). For any E H. we have
<
2d Σ (1-c)
(1-c)i-haa (d+
Σ S (T
(s)) S fi(())
(D.1)
where (e) is a error term, which is defined as:
0, (H h)dele - 1), (H - -h))a(1 - e)/4,
if TV;
(e)
if KL; Ds
Furthermore, if we set the as
2-1/
if TV; if is KI. is
min(1 2-11/H 83/2 (6/2/(64X22K))
(D.2)
min(1 - 1-111 8/2 /
then we have fh(() S 8/2 H/22222
Proof of Theorem 5.5. Invoking Lemma D.2, have
8 H
(1+ (1+-)11100)) EX azs) (C(()
VTT (s1) -VT (s1)
N Σ
c)- (1-c)--1(
(1
2d
5
1) E,,, (2ass 1)) - SP(()
4d
im
H
e)² - - 1)) fP(e)
ET(2aje -ET
4d
H
Σ
e)- -1,3 E. (2a;; - 1)) - -A())
(D.3)
4d
jml
8
K5 E. 12) 1)1 f((c),
(D.4)
4d
jml
where (D.3) follows from the fact that Eji 1-1,1), 1). To continue,
8
H
8
H
E
ET (2ags
1)1
Ex E E²(2aj; 1))1 * sign(B(2a.; 1))
4d
4d
j=1
j=1
33

---

Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization
5
H
1ihii + sign(B(2aj; 1))}
4d
J=1
6 (H((,)"),
(D.5)
4d
where (:(:.)) is the Hamming distance. Then applying the Assouad's method (Lemma 2.12 in Tsybakov (2009)), we have
dH
inf sup (Drt,,)
min inf inf(Q:(((D) () (v> {")]
EES
2 D=(E,ET)=1
dH
max DKL ( (25=)) 1/2 )TA) 2 D=(E,E-)=1
2 1
(D.6)
where DKL represents the KL divergence. Next we bound DeL (Qe [Q=e) according to the definition of Qe(D), we have
(D) III
15 of (r
k=1
where (r af.) refers to the density funetion of (r (s of). at r By the fact that the difference between the
two distributions (D) and Qe (D) lie only in the reward distribution corresponding to the index where & and g differ,
we have
K
DEL (N d 8, 0, 1
(
d d- b.1)
K 82 + d2 S 2'
(KL(Qe(P1IQe=
(D.7)
where the last inequality follows from the definition 5. By the fact that = /012/V2K, we have
8H(1 - e)
(1- (
DxL (Qel(e())))) 1/2 (e)())
inf sup subopt(M, A)
max D=
(D.8)
# MEM
4
5H(1 c)H-1
(ch(c)
(D.9)
8
63/2 ((1
6) H-
(c)
8/2K
83/2
63/2H
(D.10)
16v2K
32V 2K
ET
Σ |0, a)lal 1/51 =
(D.11)
128
where (D.8) holds by applying the inequality (D.4), (D.5) and (D.6) in order, (D.9) holds by (D.7), (D.10) holds by the definition of in (D.2), and (D.11) holds by Lemma F.4. Hence, it is sufficient for taking 1/128 This concludes the proof.
E. Proof of Technical Lemmas
E.1. Proof of Lemma C.1
Proof. We first decompose the SubOpt(TT X) follows:
SubOpt(ft, ft, 8, A) (s) (s) Vita (8) - 11((s) + (s)) - V (s).
(
34

---

Robust Offline Reinforcement Learning with Linearly Structured f- J-Divergence Regularization
where (s) is computed in the algorithm. We next bound the term (i) and (ii) respectively. For term (i), the error comes from the estimated error of the value function and the Q-function, therefore by (3.2) and the definition of the (, a) in meta-algorithm, for any h E [M1] we can decompose the error
Vi
(s) 2h (1, - Qhss, #s)))
S SQ - (s, - (
(E.1)
-TA (s)) Th V ( (s)) + (s, (sss
-T (()) (+ (s,
(E.2)
where (E.1) comes from the fact that an is the greedy policy with respect (s, a). the regularized robust Bellman update error o defined
(s, = (s, (h(s, V(s,a) ESx
(E.3)
which aims to eliminate the clip operator in the definition of (s, a). Denote the worst transition kernel w.r. the regularized Bellman operator as P = {Pr heEM,, where P/. is defined as:
Pa(-)s,a)== argmin (.E [Es~PA(HH,a) [V [s')] + M(b(s,)) D(ual [())]
di(s,a) argmin [ES' (V2 AD (AA))
(
= ()n,))
where the Ah.s is defined as A argmin :E()) Eer=pa,,.[ [V)+1(s5)] AD(,,,,lllle Hence the difference between the regularized Bellman operator and the empirical regularized Bellman operator can be bounded as
A T (s, - TA V (s, (s))
= =rass, 7H (s)) + (p.
inf
( + (o(ss,T())) D(ualla)))]
-rn(s, - P.EA(S)).Ph
inf
E (Er-Pa (7 (s') + A(o(s (z)) 1(m
(E ( E Pr (x))
(8')
(x..A,()..))))) (5)) [V (5') (s').
(E.4)
Combining inequality (E.2) and (F.4), we have for any E [H]
VI (A) - (x) & (o (1)) + (())
(F.5)
Recursively applying (E.5), we have
(i = 1= (s) (s) <
E ( an)lss s).
h=1
Next we bound term (ii), similar to term (i), by (C.1), the error can be decomposed to
(x) V A (s) = (8, (x)))))())))))))))))))()({)))( g (s,
TA (5)) (s Th V (s))
(E.6)
Denote pa (Pfh where P is defined as: V(s. a) ESXA
())s,
A. [BSPPa(Haa) (s')] A(p(ss)) a), D(palle)))
argmin
35

---

Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization
Hence similar the bound in (E.4), the difference between the regularized Bellman operator and the empirical regularized Bellman operator can be bounded as
Vi fn(ss) V h+ (T((s)) S E Bag.erg ( (s'))
(E.7)
Combining inequality (E.6), (E.7), we have for any h E [H]
V. (s) Vn (8) S Byr (Hadaaa))))) (1) - (=') 5 tx (+)).
(E.8)
Recursively applying (E.8), we have the "pessimisim" of the estimated value function that Vh E [H]
(s)s) (s)
E EAPP* -
(5 an)llsi s).
h=
Therefore combining the two bounds above, we have
H
LubOpt(ff,... s, A) (i)
+
E P
(6 ax) = =s] +
BR.P*
(sp, an)lss = s].
(E.9)
h=1
4=1
Hence, it requires estimate the range of the regularized Bellman update error (s, a). Recall the definition in (E.3), claim that
0 S (s. S (s,
(E.10)
holds for v(s,a, E 8 x A [H]. For the LHS of (E.1 first notice that if (ø(ss, a), wx)) (s, a) 0, the inequality holds trivially as (x, a) = 0. Next we consider the case where (#(8, a), vxt) (x, 2 0. By the definition of (s, a) and the assumption in the lemma, we have
(s) Th (s a))
= Th V a) min ( ((0(s, - h
TAVA (s, (b)s, w + as)ssa)
0.
On the other hand, by the assumption in the lemma, we have
(Ø(s,a), w -T, a) S TAVA 1 a) -
Hence, we can upper bound 8/ a) as
(s,
Th Th -))(s
T max ( w - as,
Th (. (Ø(s,a), w + (s,
s as)
This concludes the claim. Now it remains to bound the empirical transition kernel P. Noticing the fact that Vh. E [H], (s) E S x A,
AD(pn,)lpph.)) S Ex' (VA (s')] AD(
inf
Be [x41(' + xD(Mn,.ll(R.))
EA(S)
s inf (A())((S)
Edimas Vi (s')) AD
(E.11)
< Bernpp
IV (s'))
36

---

Robust Offline Reinforcement Learning with Linearly Structured /Divergeence Regularization
max V
SES (s),
where (E. comes from the pessimism of value function, i.e ( S (s), vh [M]. Hence, the empirical
transition kernel Pr(-|s, a) is contained in the set (P") defined in (5.1). Hence, by (E.9) and 10), we have
H
"1
SubOpt(ft f. 8, A) S
(s on)ss =s] + E"
Σ
E E
8% (5p. an]lss =
h=1
1=1
2
E
P II's (sh, an)ss =s]
h=1
H Σ
2 PEU
sup
E" "gn..Pp (T((s)) = =s].
h=1
This concludes the proof.
E.2. Proof of Lemma C.2
Proof. For all h [H], from the definition of wh.
W l12
|| Wh+ (s))an+1 S HVd.
where the inequality follows from the fact that Vi+t1 I H, for all h [H]. Meanwhile, by the definition of u in Algorithm 3, and the triangle inequality,
K
= A
Σ
12) 2 (s)lant
7=1
K
< H
A 005) a2)12
V ((5% aT)TT A 1/2 AT AA 1/2 111200655.000
015%. 0%)
H
(65% aR) TA (65,
(E.12)
HVK
K
(65 07) A ((5%
(E.13)
V7
HVR
VTR(AT -1))
V
HVR
Tr(I)
VT
_H Kd
where (2.12) follows from the fact that ||A S -1, (E.13) follows from the Cauchy-Schwarde inequality. Then conclude the proof.
E.3. Proof of Lemma C.3
Proof. By definition, have
lwlll = 1|B0-n0 c
11
/1
|le
(2
()(s))
ds
/ [11(()) S Vd,
37

---

Robust Offline Reinforcement Learning with Linearly Structured f- /Divergeence Regularization this concludes the proof of woz For 20
Va (on4))
R 12
A
A (18 a7)ll2
V0(5 a An 11/2 An An 1/2 (55 07.)
(( (7) T An (5)
(E.14)
Σ (5 07) T A, (65, 07
(E.15)
K
TT (An -A))
Kd Tr(II= V
where (E.14) follows from the fact that || S 1T-1 (E.15) follows from the Cauchy-Schwartz inequality. Then we conclude the proof.
E.4. Proof of Lemma C.4
Proof. Denote A = AF then we have |10||2 S T., ||A S B2y-1 For any two functions V1, V/2 E V with parameters (0), A1), (02, A2), since both (-11,.th+1 and max, are contraction maps,
dist(V, V1, V2)
(E.16)
< sup 8a
((s a) ( (0) 02) >(10g (++)
(ov(s, - log (1+ Σ
(s, aa)ll.)))ll
1=1
1+1 11 a)lll,
Φ (01 02) Alog
sup
11
1+1 i= |1 a) 1) 1
1
sup HER $1
16 (0: 02)1 A
sup +E
log
(E.17)
1+ == [1bb(s)
we notice the fact that: for any
0,y > 0,
1 log
1 1 +1) s log(1x yl 0/+10 1) s |r v/.
log
1+ +
Therefore, (E. can be bounded as:
(E.17) < sup
(T0 02)l +
sup
(o((s,a)1illA Σ (
|
d
sup
1 (0) 02) +
sup
Σ V 1.11 A10:1 Σ
V 1111 A20:1
$ER
< ||0 - -1112 + A
sup
1 (Ai A2)0.1;
(E.18)
$ER
<1 im1
38

---

Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization
< |00 02112 + AVIIA A2l
sup $ER*: 1
1011,|
K |0 - 02112 + AV - F2
(E.19)
where the (E.18) follows from the triangular inequality and the fact VV v S v1 - yl. and || || denotes the Frobenius norm. We next define that Co is an c/2-cover of {0 E R I LJ, and the Ca an e² 22/4X- cover of {A E Rddd || A|lF S B2 }. }. By Lemma F.5, we have that:
Col S (1 4L/e)", ICAl S (1+8X /
By (E.19), for any Vi E V, there exists 02 Co and A E CA s.t 1/2 parametrized by (02, A2) satisfying dist( V22) S e. Therefore, we have the following:
log [W(e) I log /Col + log [CAl dlog(1 + 4L/e) + log(1 2 /²1
Hence we conclude the proof.
E.5. Proof of Lemma C.5
Proof. By definition, we have that
|
Buh.s
[V (s)la
1
(B.
1V2 h+ (s)
1
(V2) h+ (s)1z
max CVEEC 6+1 miin. (V..
A Jmax]]
41
41
iE(d
H
(E.20)
2A
iE|d 12
2
Vi H +
2X
where (E.20) follows by the fact that (.H,, (V)
(s)la E [0, H], Eah. (VA4 E [0, H².
E.6. Proof of Lemma D.2
Proof. We first proof the LHS of the lemma by induction from last stage H. From the definition of ViT.A and On, we can learn that
8 (d+ Σ
(s)) = (s (H()) ((s1, (s)))) 0,
EH oH.)
2d
i=1
This is the base case. Now suppose the conclusion holds for stage h + 1, that to say.
(s1)
Σ (1- (1-cy-h-11 (d+ ( S,,"aaa))
2d j=
Recall the regularized robust bellman equation in Proposition 3.2 and the regularized duality of the three divergences, have
2 (s), = (51, +
inf meA(S)) (
Ex (VTr) + ())ss.)) ((
Sm a) + Ex- (VT
(E.21)
r a) + ())
(E.22)
Then with regularized robust bellman equation in Proposition 3.2 and the inductive hypothesis, we have
(s)) = 0 ( (81, ((1)))
39

---

Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization
S
(T(( + -e) (+1
(E.23)
8
d +
d Σ
Eni and
+
8
Σ
H
(1
(1--)a-h
-
-)+-h(d+ ( Eyil" ags)
d
2d
2d
1=1
8
H
d
Σ
-1-e)-- e)i-h
dd+
Σ
En azt
2d j=h
i=1
Hence, by the induction argument, we conclude the proof of the RHS. Furthermore, for any E [H]] we can upper bound (8) as
V
x (s) S Σ (1
8
ay-h(d+
Σ Ennd"aa)))
& 8(1 h) M X,
(E.24)
2d j=h
where the third inequality holds by the definition of 8. For the left, we prove by discussing the KL, x² and TV cases respectively.
Case I TV. The case for TV holds trivially as by Proposition 4.3, we have
( = a)) +
inf PA [B (V + M(((s,)). D(m
=r,(s1, a) + (#(5), a), Ex (i (8 Imm (1726)))))))))))
(E.25)
= =r a) + Pg( M+1 (s')]
= -s, a) + (1 - <) V (81);
(E.26)
where (E.26) holds by (E.24). Hence, the inequality in (E.23) holds for equality. This concludes the proof for TV-divergence.
Case II KL. We prove by induction. The case holds trivially in last stage H. Suppose
H
d
V (si)
Σ (1-
(d+ Σ oT)))
(H- -H- h))e(e 1).
2d
j=h+1
Recall the duality form of Proposition 4.6, the Q-function stage h can be upper bounded
(s1,a) = (x(81, a) +
inf (4)
Ex [V)++ss)] + A(o(s, ((mm)111))
MEA(S))t
= a) + (Ø(5), a). -Alog E Es sn 111101/11
rh(51,a) Alog (e (1 E)E (()(()))/1
r)(51,a) + (s1) - > Alog (ee (iti + (1 - c))
2 ()) + ( (si) Xe(e Xe(e' /
(E.27)
2 () + (si) - Ae(e - 1),
(E.28)
where (E.27) follows by the fact that log(1 + x) S x, Vx 0, (E.28) follows by (E.24). Therefore, by the inductive hypothesis, have
V.L (81) = ( क (81))
rn(s TA +1 - vird(s) xe(e-1) 1)
H
d
Σ (1 - 0)- (p--))-(aaa (a+ ( GrTTTaas) - (H- -h)acle- -1).
2d
This finishes the KI. setting.
40

---

Robust Offline Reinforcement Learning with Lincarly Structured f- /-Divergence Regularization
Case III x2. Similar the case in TV, KL, by the duality of x² in Proposition 4.8, we have
Q (T (s1,
(T((11,)) a) +
inf
[x [v+41 (s)) + ((((s,)), ((un)ll)))
= =r,(s1, a) + (1 -)
sup
<
(111)))))
am(Vmin Vmax
41
2 a) + -) (i
- (V
41
a + - (1-c))
(E.29)
4
where (E.29) follows by (E.24). Hence, similar to Case II, by induction, have
Σ Egil andR"ay)) aj:)) -(H - -1]- -))a(1-o)
(81)
Z
Σ
o) c)-h((u
j=b
This finishes the x2 setting, and we complete the proof.
F. Auxiliary Lemmas
Lemma F.1 (Lemma D.3 of Liu & Xu (2024a)). For any E [H], let Vn. denote a class of functions mapping from S to R with the following form:
Va 0,0, = max (b(s0)) aEA
2 1=1
|o (ellA, 10.H
the parameters 30,3,4 A satisfy |01|2 S L, E B), 7mia (At) 2 Let Na(e) be the e-covering number of V with respect to the distance dist(Vi, V2) = sup, [v: - V2(x))- Then
log.N < d dllo(1 + 4L/e) + dl log(1 + /2 /² /
Lemma F2 (Corollary 4.2.11 of Vershynin (2018)). Denote the e-covering number of the closed interval [a, b] for some real
number > a with respect to the distance metric d(an, (22) = |o 02 as (Ca, b)), then we have NN((a, b]) S 3(b - a)/e. Lemma F3 (Lemma B.2 of Jin et al. (2021)). Let f S + [0, R 1] be any fixed function. For any d (0, 1), we have
P
Σ
(5s) of (f)) 2 R² (2log(1100) dlog(1 + dllg(
k/>1)) 5
where (f) Eg Pf (
[f())) p
f(%42))
Lemma E.4 (Lemma F.3 of Liu & Xu (2024b)). If 2 O(d)) and the feature map is define as Appendix D.1, then with probability at least 1 - ó, we have for any transition P.
H
3/2
ET
10,(s a)l.ll 1/s: ss
VK
A=1
Lemma F.5 (Lemma 5.2 Vershynin (2010)). For any 0, the -covering number of the Euclidean ball in R2d with radius R 0 is upper bounded by (1 2R/c)


Reviews:
[{"review_id": "jLuiX9m2JB", "reviewer": "Reviewer_k882", "summary": "This paper studies ways to learn a good policy in offline RL with Linear MDPs such that the policy is robust to changing the model within some f-divergence neighborhood.  More precisely, the authors consider linear MDPs and suppose they have access to an offline data set of trajectories.  Unlike standard offline RL, the authors aim to find policies that have optimal robust-regularized value, where this function is defined as the infimum over a set of feasible models (transition densities) of the expected cumulative reward of a policy plus a regularization parameter multiplied by some divergence between the model and some baseline model.  The authors consider three f-divergences: TV, KL, and chi^2 divergence and introduce an algorithmic framework based on dynamic programming, which essentially produces pessimistic estimates of the regularized Q function at each time step using an elliptic bonus.  The linearity of the model allows for a tractable decomposition of the f-divergence regularized Q-function as represented by a linear function of the features, where the representation is the sum of the reward representing vector and another vector that solves a variational problem representing the regularized value function; again, this decomposition holds due to the linearity of the MDP.  The authors express this latter variational problem as alearning problem and demonstrate htat this vector can be learned, which is how the reward estimates are constructed.  As mentioned above, pessimism is introduced through a standard elliptic bonus.  The authors use this approach to show that their dynamic programming algorithm achieves robustness and, given suffficient feature coverage of the offline dataset, good performance.  The authors show through a lower bound that the feature coverage is necessary information theoretically.  Finally, the authors conclude with a small experimental suite comparing their approach to pessimistic algorithms that do not incorporate robustness and other recent robust offline algorithms.\n\n\n####\n\nAfter the rebuttal, I maintain my original (positive) score.  I remain a little bit concerned about the numerical issues in long-horizon, sparse reward settings for the KL regularization setting, where we expect to see expressions like $e^{O(H)}$.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for positive feedback on our work. We hope our response fully addresses your questions\n\n---\n**Q**: “While I understand it is important for the analysis, it seems to me that requiring robustness to changes on $\\mu$ is a fairly weak notion and more applicable notions of robustness might be policies that are robust to imperfectly learning the featurization (as in low-rank MDPs) or policies that are robust to small perturbations of the linearity assumptions themselves.” \n\n\n**A**: Thank you for your insightful comment. We fully agree that considering different notions of robustness is crucial in policy learning, as the literature on robust MDPs explores diverse structured uncertainty sets.\nRegarding your reference to “policies that are robust to imperfectly learning the featurization (as in low-rank MDPs) and or policies that are robust to small perturbations of the linearity assumptions themselves”, we interpret this as pertaining to policies derived under an more general uncertainty set, such as (s,a)-uncertainty set. In such cases, the worst-case transition kernel may not admit linear structure, distinguishing it from our focus.\nWe further highlight the difference between the difference of d-rectangular uncertainty structure and (s,a)-uncertainty set structure. \n- (s,a)-Uncertainty sets permit correlated perturbations across state-action pairs, leading to more conservative min-max policies (Iyengar, 2005; Wiesemann et al., 2013).\n- d-Rectangular Uncertainty sets assume independent worst-case dynamics for each (s,a) pair, resulting in less conservative policies.\nAs noted in our work (Lines 75–90, left column), prior research has established the tractability of regularization-based frameworks under (s,a)-uncertainty sets. Our contribution fills the theoretical gaps for d-rectangular settings, which we believe is of independent interest. \n\n---\n**Q**: The clearly written of robustness\n\n\n**A**: We sincerely thank the advice for removing the notation back to the main text. We remove the notation to the appendix mainly for satisfying the page limit required by the ICML. We have moved the notation to the main text.\n\n---\n**Q**: “What is the [0,H] in the second line of equation 4.4?\"\n\n\n**A**: The subscript of [0,H] refers to clip the vector into interval [0,H]. We have provided illustrations in the main text and notation.\n\n---\n**Q**: Numerical issues when solving on O(H/lambda)\n\n\n**A**: We appreciate the reviewer's insightful comment regarding potential numerical instability in the KL divergence case. In our current experimental setting (with limited horizon H and bounded value functions), we did not encounter such numerical issues.\nAs for potential numerical issues, we assume that the numerical issues may result from taking log-transformation of $e^{H/\\hat{V}}$ (line 250- 258). However, thanks to the homogeneity and linear properties of Robust Regularized Bellman Equation (prop 3.2), the reward can be normalized in [0,1] to adjust to different circumstances, this may avoid numerical problems raised from the estimation of $e^{H/\\hat{V}}$.\n\n---\n**Q**: “Is there a formulation for general f-divergences beyond those considered in the paper?\"\n\n\n**A**: For the definition of general f-divergence, we direct the reviewer to the notation introduced in our article (Line 551), which aligns with prior works (e.g., Yang et al. and Panaganti et al.).  While our RRMDP framework and algorithms can be extended to general f-divergence (see appendix A for details), we also highlight that we provide specific theoretical analysis with TV, KL, chi2 for two key reasons: \n- Practical Relevance: the TV, KL, chi2 divergence have already been adopted and commonly used  in empirical RL. (Shi et al.)\n- Theoretical Challenges: Analyzing sample complexity under general f divergence  remains an open problem due to the varying dual formulations induced by different divergences (see appendix A for detailed discussion). A unified framework for general f-divergences is an exciting direction for future work.\n---\n\nWe hope that we have addressed all of your questions/concerns. If you have further questions, we would be happy to answer them and if you don’t, would you kindly consider increasing your score?\n\n---\n\nReferences\n\n[1] Iyengar, G. N. Robust dynamic programming. Mathematics of Operations Research, 30(2):257–280, 2005.\n\n[2] Wiesemann, W., Kuhn, D., Rustem, B.: Robust Markov decision processes. Mathematics of Operations Research 38(1), 153–183 (2013)\n\n[3]Yang, W., Wang, H., Kozuno, T., Jordan, S. M., and Zhang, Z. Robust markov decision processes without model estimation. arXiv preprint arXiv:2302.01248, 2023.\n\n[4]Panaganti, K., Wierman, A., and Mazumdar, E. Model-free robust $\\phi$-divergence reinforcement learning using both offline and online data. arXiv preprint arXiv:2405.05468, 2024a.\n\n[5]Shi, L. and Chi, Y. Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity. JMLR, 2024.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "I think the methods are in general reasonable, given the limited number of naturally occurring linear MDPs.", "theoretical_claims": "I checked some of the proofs of the theoretical claims, in particular the proofs of Proposition 4.1 and Theorem 5.1.  The remaining results are believable given standard RL theory, but the reviewing time was insufficient to provide a detailed check.", "experimental_designs_or_analyses": "They seem fine.", "relation_to_broader_scientific_literature": "See summary.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I think one minor weakness of this work is the notion of robustness.  While I understand it is important for the analysis, it seems to me that requiring robustness to changes on $\\mu$ is a fairly weak notion and more applicable notions of robustness might be policies that are robust to imperfectly learning the featurization (as in low-rank MDPs) or policies that are robust to small perturbations of the linearity assumptions themselves.  I also think that the paper could be significantly more clearly written, with notation defined before it is used as opposed to deferred to the appendix.", "other_comments_or_suggestions": "What is the [0,H] in the second line of equation 4.4?", "questions_for_authors": "- Are there not potential numerical issues with the expression for the w_h in the KL case considering that solving this problem requires exponenentiating something on the order $\\Theta(H / \\lambda)$?\n\n- Is there a formulation for general f-divergences beyond those considered in the paper?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hiPfBdvNXj", "reviewer": "Reviewer_HBar", "summary": "The authors proposed a framework to solve the d-rectangular linear RRMDP. They extend the previous work under the distributional robust MDP framework by unifying three ways that define the potential MDPs consistent with the offline datasets and provide the theoretical analysis on the proposed method. Some brief experimental results are given to show the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for positive feedback on our work. We hope our response fully addresses your questions\n\n---\n**Q**: Difference with [Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity]\n\n\n**A**: We claim the difference between our work and [Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity]. \n1. Different objectives: \n- Shi et al. primarily address dynamics shift and sample complexity challenges in standard MDPs, focusing on learning a policy under the empirical transition dynamics.\n- Our work studies the Robust RL (RMDP) framework, which optimizes policies under the worst-case transition kernel within a structured uncertainty set. This leads to fundamentally different problem formulations and optimal policies.\n2. Different Environments and Assumptions:\n- Shi et al. operates in tabular settings with finite state and action spaces.\n- Our work adopts a linear MDP structure, enabling scalable function approximation and extending the analysis to high-dimensional settings.\n\n---\n**Q**:  Clarify of computation efficiency\n\n\n**A**: We emphasize that our computational efficiency is evaluated relative to the standard Distributionally Robust MDP (DRMDP) framework and its associated algorithms.\n\nUnder both TV and KL divergence measures, our approach achieves superior computation efficiency by leveraging closed-form duality solutions, which are more tractable than those in the conventional DRMDP framework. In large state-action spaces, solving the dual problem under the DRMDP framework becomes computationally prohibitive, whereas our method remains scalable. For a detailed comparison of computational complexity, we refer the reader to Figure 2.\n\n---\n\nWe hope that we have addressed all of your questions/concerns. If you have further questions, we would be happy to answer them and if you don’t, would you kindly consider increasing your score?\n\n---\n\nReferences\n\n[1] Shi, L., Li, G., Wei, Y., Chen, Y., and Chi, Y. (2022). Pessimistic Q-learning for offline reinforcement learning: Towards optimal sample complexity. In Proceedings of the 39th International Conference on Machine Learning, volume 162, pages 19967–20025. PMLR.", "claims_and_evidence": "The paper is clear-structured and the theoretical performance of the proposed method is good.", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "1. In the introduction, the authors raised two main problems of previous method: Theoretical gaps and computation complexity. Although the authors theoretically prove the previous one, about the latter, only a simple experiment is provided, which is not sufficient to prove this point - computation complexity, is well addressed. Could the authors provide more discussion about this? For instance, compare with [Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity].\n\n2.The whole framework is based on the linear MDP, as assumed in 3.1, which may hinder the practical application of the proposed method.", "experimental_designs_or_analyses": "Experiments are too simple. could the proposed methods be suitable for  more complicated benchmarks, such as MuJoCo?", "relation_to_broader_scientific_literature": "n/a", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "n/a", "other_comments_or_suggestions": "n/a", "questions_for_authors": "see above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "S4auElcmeg", "reviewer": "Reviewer_8c9y", "summary": "This paper introduces a new framework, the $d$-rectangular linear robust regularized Markov decision process ($d$-RRMDP), for offline RL and develops a family of algorithms called robust regularized pessimistic value iteration (R2PVI) to learn robust policies. Upper bounds on the sub-optimality gap and the information theoretic lower bounds for $d$-RRMDPs are also provided. Numerical results are included to support the theoretical guarantees.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for positive feedback on our work. We hope our response fully addresses your questions\n\n---\n**Q**: A more comprehensive discussion on how choosing λ affects robustness while maintaining efficiency compared to prior methods would strengthen the argument. (more experiment)\n\n\n**A**: Figure 1b demonstrates how the parameter $\\lambda$ controls the robustness of our policy, where robustness is defined as the policy's resistance to performance degradation under environmental disturbances. In general, larger values of $\\lambda$ yield more robust optimal policies. However, we caution against direct comparisons of $\\lambda$ values across different divergence measures (TV, KL, chi2), as varying $\\lambda$ fundamentally alters the optimization objective and thus the resulting optimal policy. For a rigorous theoretical analysis of the relationship between λ and the robustness radius $\\lambda$, we direct the reviewer to the discussion in Line 318.\n\n---\n**Q**:  Clarify of computation efficiency\n\n\n**A**: While our work primarily focuses on the theoretical analysis of the RRMDP framework, we acknowledge that extending this framework to more general experimental settings represents an important complementary research direction.  Such extensions present distinct challenges that differ fundamentally from theoretical analysis, requiring careful consideration of practical implementation issues. Nevertheless, recent research has highlighted the promising potential of extending theoretical frameworks like RRMDP to more complex and realistic environments.\n- The learning of feature mapping. Recent advancements, such as [1], demonstrate the feasibility of generalizing linear MDPs to more flexible representations. This line of work offers valuable insights into how complex scenarios can be modeled through linear MDP settings.\n- The development of specialized benchmarks like [2] provides valuable infrastructure for systematically evaluating different approaches to uncertainty modeling, including both DRMDP and RRMDP frameworks.\nThese developments highlight the feasibility of extending theoretical results to practical applications. However, given our current focus on establishing fundamental theoretical guarantees and the associated time constraints, we leave the design of comprehensive experiments in more general environments as an important direction for future research.\n\n---\n\nWe hope that we have addressed all of your questions/concerns. If you have further questions, we would be happy to answer them and if you don’t, would you kindly consider increasing your score?\n\n---\n\nReferences\n\n[1] Zhang, Tianjun, Tongzheng Ren, Mengjiao Yang, Joseph Gonzalez, Dale Schuurmans, and Bo Dai. \"Making linear mdps practical via contrastive representation learning.\" In International Conference on Machine Learning, pp. 26447-26466. PMLR, 2022.\n\n[2] Shangding Gu and Laixi Shi and Muning Wen and Ming Jin and Eric Mazumdar and Yuejie Chi and Adam Wierman and Costas Spanos. \"Robust Gymnasium: A Unified Modular Benchmark for Robust Reinforcement Learning.\" arXiv preprint arXiv: 2502.19652.", "claims_and_evidence": "The baseline selection is reasonable, but incorporating more comprehensive evaluation criteria would further strengthen the analysis.", "methods_and_evaluation_criteria": "The baseline selection is reasonable but a more complex evaluation criteria will be benificial.", "theoretical_claims": "Most claims are well-supported, but the comparison of upper bounds with existing works lacks a thorough analysis of the robustness-efficiency trade-off. Since $\\lambda$ controls the degree of regularization and robustness, evaluating only its scale relative to $\\beta$ in the suboptimality gap is insufficient. A more comprehensive discussion on how choosing $\\lambda$ affects robustness while maintaining efficiency compared to prior methods would strengthen the argument.", "experimental_designs_or_analyses": "Is that possible to validate the algorithms in a more complex setup, like mujoco?", "relation_to_broader_scientific_literature": "1. This paper introduces a new framework for enhancing robustness in offline RL, incorporating a broad class of divergences to improve generalization.\n2. It establishes upper bounds on suboptimality and information-theoretic lower bounds for $d$-RRMDPs.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\nThis work presents a comprehensive theoretical analysis, establishing both upper and lower bounds for the newly proposed framework and algorithms.\n\nWeaknesses:\nThe discussion on the practical impact and applicability of the method in real-world scenarios is limited.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization 


Paper-Summary: This paper introduces a new framework called the d-rectangular linear robust regularized Markov decision process (d-RRMDP) to address the limitations of existing robust RL methods under dynamics shifts in offline settings. Unlike prior approaches that rely on unstructured or rectangular uncertainty sets, this framework introduces latent linear structure into both the transition kernels and the regularization terms, thereby improving both computational efficiency and theoretical robustness. The authors propose an algorithmic family called R2PVI (Robust Regularized Pessimistic Value Iteration), which leverages general f-divergence regularization (including TV, KL, and χ² divergences) and linear function approximation to learn robust policies from pre-collected datasets. They provide both instance-dependent and instance-independent upper bounds on the suboptimality gap of R2PVI, and establish an information-theoretic lower bound demonstrating the fundamental hardness of robust offline learning in the d-RRMDP setting. 



Review and feedback: We received 3 expert reviews, with scores, 3, 3, 3, and the average score is 3.00.  

The reviewers are generally positive about the technical contribution of this paper. The reviewers noted that theoretical contributions are strong and well-structured. The paper derives minimax-optimal bounds for offline RL with robustness regularization under linear MDP assumptions. The introduction of the $\phi$-rectangular uncertainty sets adds flexibility and generality, unifying various prior robust RL approaches. Reviewers appreciated the clarity of the analysis and proofs, especially the treatment of KL-divergence-based uncertainty sets and the duality approach to derive computationally tractable updates. 

Reviewers have also made suggestions for improvement, including additional experimental results, computational tractability, and comparison with other algorithms. Please address these comments/suggestions while preparing the final submission.
Decision: Accept (poster)