The Power of Duality Principle in Offline Average-Reward
Reinforcement Learning

Asuman Ozdaglar 1 Sarath Pattathil 1 Jiawei Zhang 1 Kaiqing Zhang 2

Abstract
Offline reinforcement learning (RL) is widelyused to find an optimal policy using a precollected dataset, without further interaction withthe environment. Recent RL theory has made significant progress in developing sample-efficientoffline RL algorithms with various relaxed assumptions on data coverage, with specific focuses on either infinite-horizon discounted or
finite-horizon episodic Markov decision processes(MDPs). In this work, we revisit the LP framework and the induced duality principle for offline RL, specifically for infinite-horizon averagereward MDPs. By virtue of this LP formulation and the√ duality principle, our result achieves
the Õ(1/ n) near-optimal rate under partial data
coverage assumptions. Our key enabler is to relax
the equality constraint and introduce proper new
inequality constraints in the dual formulation of
the LP. We hope our insights can shed new lights
on the use of LP formulations and the induced
duality principle, in offline RL.

1. Introduction
Reinforcement Learning (RL) has achieved remarkable empirical success in solving sequential decision-making problems in recent years (Mnih et al., 2015; Silver et al., 2016;
Vinyals et al., 2017; Levine et al., 2016). Two key factors
have contributed to these successes: 1) the use of powerful
function approximators, such as deep neural networks, and2) access to large amounts of interaction data with the environment. Many successful RL applications rely on online
data collection through simulators, such as game engines(Silver et al., 2016; Vinyals et al., 2017) and physics simulators (Todorov et al., 2012).
*

Equal contribution 1 Department of EECS, Massachusetts
Institute of Technology 2 Department of ECE, University of
Maryland, College Park. Correspondence to: Jiawei Zhang<jwzhang@mit.edu>.
ICML 2023 Workshop on Duality for Modern Machine Learning,
Honolulu, Hawaii, USA. Copyright 2023 by the author(s).

However, in numerous real-world domains, online interaction is impractical due to the high cost or impracticality ofdata collection, or the inability to simulate the environment
accurately. Examples of such domains include robotics andautonomous driving (Levine et al., 2018; Maddern et al.,2017), healthcare (Tseng et al., 2017), and recommendersystems (Swaminathan et al., 2017). Moreover, even incases where online interaction is available, leveraging previously collected data is crucial for effective generalization,
as it requires large datasets (Levine et al., 2020). Offline RL
has emerged as a promising framework for deploying RL in
real-world scenarios.
Most existing works on offline RL focus on learning in
discounted reward Markov Decision Processes (MDPs) witha discount factor γ < 1. However, in many applications,learning problems are modeled as average-reward MDPs
(Sutton & Barto, 2018)[Chapter 10], (Naik et al., 2019;
Farias et al., 2022). Despite the rich literature on offline RL
for discounted MDPs, to the best of our knowledge, there
is no existing result studying offline RL for average-reward
MDPs that achieve optimal sample complexity. In this paper,
we address offline RL in average-reward MDPs and design√
algorithms with a statistical convergence rate of Õ(1/ n).
Offline RL in discounted MDPs. Offline RL is known tosuffer from the training instability issue caused by the distribution shift between the offline data distribution and thetarget (optimal) policy distribution (Fujimoto et al., 2019;
Kumar et al., 2020). Consequently, earlier offline RL works
relied on strong assumptions regarding the dataset to provide
sample-efficiency guarantees. Many of these results (Munos& Szepesvári, 2008; Scherrer, 2014; Chen & Jiang, 2019;
Zhang et al., 2021) required the dataset to have full coverage,
meaning that the data covers the state distributions inducedby all policies. These assumptions are strong and can beviolated when using richer function classes, and they are
more stringent than the common assumption of realizability
in statistical learning theory. Moreover, the full coverageassumption requires the offline data to cover all possible
state-action pairs, which is often violated in real-world applications. Recent advancements have made progress inrelaxing these assumptions. For example, (Liu et al., 2020;
Jin et al., 2020; Rashidinejad et al., 2021; Xie et al., 2021;

Submission and Formatting Instructions for the DP4ML workshop

Uehara & Sun, 2021; Chen & Jiang, 2022) have shownthat by employing a pessimistic mechanism that selects theworst-case value function or model from an uncertainty
set during learning, the full coverage assumption can be relaxed to a single-policy coverage assumption. More recently,(Zhan et al., 2022; Rashidinejad et al., 2022; Ozdaglar et al.,2023) propose linear programming-based methods that relax
the data coverage assumptions and provide computationallytractable algorithms when using function approximation.
RL in average-reward MDPs using LP. To the best of
our knowledge, there is no finite-sample complexity results
for average-reward offline RL, with partial data coverage.
The most related results which also exploited the LP framework and duality principle in average-reward RL, are thosefor the case with a generative model (Wang, 2020; Jin &Sidford, 2020).
1.1. Our Goal and Challenges
For discounted MDPs, several algorithms
achieve a nearly√
optimal convergence rate of Õ(1/ n). However, it remains unknown whether we can achieve this rate foraverage-reward MDPs. The convergence rate for discounted
MDPspwith a discount factor γ is always in the form ofO(1/ poly(1 − γ)n), which can become large as γ → 1.
Consequently, the results and analysis for discounted MDPs
cannot be directly applied to average-reward MDPs.
Contributions. In this paper, we propose a linear
programming-based algorithm for solving offline RL in
average-reward MDPs.
√ Our algorithm achieves a convergence rate of Õ(tmax / n) under the single-policy coverageassumption. Here, n represents the number of samples, andtmax denotes the worst-case mixing time of the MDP.
Our techniques. The main idea behind our approach is to
study properly constrained versions of the linear programming (LP) reformulation of the underlying MDP. Specifically, we focus on a variant of the standard LP reformulation based on the marginal importance sampling framework(Nachum et al., 2019; Lee et al., 2021), where the dual
variable corresponds to the density ratio, which is the ratio
between the state-action occupancy measure and the offline
data distribution. A distinctive feature of our algorithm isthe relaxation of equality constraints in the empirical LP
and the boundedness constraints on the density ratio. The
convergence result relies on a crucial error bound lemmathat relates the suboptimality of the value function to the`1 -norm violation of the validity constraint on the stationary
distribution in the LP (see Lemma 5). Additionally, concentration bounds on the constraints and objective functions
play a crucial role in our analysis.

2. Background2.1. Model and Setup
Markov decision processes. Consider an infinite-horizon
MDP characterized by a tuple hS, A, P, R, µ0 i, where S ={s1 , · · · , s|S| } and A = {a1 , · · · , a|A| } denote the state
and action spaces of the agent, R : S × A → [0, 1] is the
reward function1 , P : S × A → ∆(S) denotes the transition
kernel, and µ0 ∈ ∆(S) denotes the initial state distribution.
Let π : S → ∆(A) denote a Markov stationary policy of theagent, determining the distribution over actions at each state.
We denote Pπ ∈ R|S|×|S| to be the transition matrix corresponding to policy π. Each π leads to stationary distributions over the state spaces and state-action spaces, denotedby βπ and θπ , where βπ ∈ R|S| denote the stationary distribution of transition matrix Pπ and θπ (s, a) = βπ (s)π(a|s).
We assume that the MDP is ergodic and irreducible forany π. Define Jµ0 (π) = Es0 ∼µ0 limT →∞ T1 Eπ r(st , at ),where (st , at ) follows the policy π.
Note that Jµ0 is independent of µ0 due to ergodicity. We let
J(π) = Jµ0 (π), which can also be represented as
J(π) = r> θπ , wherer = [r(s1 , a1 ), · · · , r(s|S| , a|A| )]> ∈ [0, 1]|S||A| .
The goal of reinforcement learning is to learn a π ∗ thatmaximizes J(π). We sometimes denote m = |S||A|.
Offline RL. Consider an offline RL problem, where one
has collected a dataset D containing n samples drawn fromsome distribution. Suppose D = {(si , ai , s0i , ri )}ni=1 , where
the independent and identically distributed (i.i.d.) samples(si , ai ) are
P drawn from some distribution µ(·, ·). We letµ(s) = a µ(s, a) which implies that si are drawn i.i.d.
from the distribution µ(·). We denote the conditional distribution of a given s induced from µ as πµ (a | s), i.e.,πµ (a | s) = µ(s, a)/µ(s) if µ(s) > 0; and πµ (· | s) can be
defined as any distribution in ∆(A), e.g., a uniform one withπµ (a | s) = 1/|A|, if µ(s) = 0. πµ can also be definedas the behavior policy if µ happens to correspond to thestationary distribution of some policy.
In this paper, we assume that the behavior policy πµ (a | s)is known, as in (Zhan et al., 2022; Rashidinejad et al., 2022).
Given a state-action pair (si , ai ), we have ri = r(si , ai )and s0i ∼ Psi ,ai (·). Moreover, let nD (s, a) be the subset ofthe sample indices {1, · · · , n} that includes the indices ofthe samples in D that visit state-action pair in the sense of(si , ai ) = (s, a). Similarly, we use nD (s, a, s0 ) and nD (s)to denote the sets of indices of data samples in D such
1

Note that we stick to the case of deterministic reward for easeof presentation. Our results can be readily extended to the case of
random rewards.

Submission and Formatting Instructions for the DP4ML workshopthat (si , ai , s0i ) = (s, a, s0 ) and si = s, respectively. We
define the empirical version of µ, i.e., µD , as µD (s, a) =nD (s, a)/n. The goal of offline RL is to make use of thedataset D to learn a policy π̂, such that the optimality gap
Jµ0 (π ∗ ) − Jµ0 (π̂) is small.
Partial data coverage. Throughout the paper, we consider
the scenario where the offline data only has partial coverage,
instead of a full one. To illustrate the difference, we first
introduce the following definition of policy concentrability.
Definition 1 (Policy Concentrability). For any policy π ,and the given offline data distribution µ, we define Cπ > 0
to be the policy concentrability coefficient, which is theπ (s,a)smallest upper-bound such that θµ(s,a)≤ Cπ for all(s, a) ∈ S × A.
Note that Cπ characterizes how well the trajectory generated
by the policy π is covered by the offline data. Throughout,
we make the following assumption:
Assumption 1. Cπ∗ ≤ C ∗ < ∞ for some constant C ∗ .
√Our goal: finding an O(1/ n) nearly optimal policy
For discounted MDP, a number of algorithms have been pro√
posed to achieve a nearly optimal accuracy, say, O(1/ nfor offline RL for a fixed discounted factor γ. A natural
question arises: can we find a nearly optimal
policy for√
AMDP by offline RL approach with O(1/ n) accuracy?
The naive approach: Using discounted MDP to approximate. As stated before, there is a rich literature about of1
fline RL algorithms in discounted MDP with √poly((1−γ)n)accuracy, where γ is the discounted factor and poly(·)
means polynomial order. Moreover, by (Jin & Sidford,
2021; Wang et al., 2022), we know that there is a (1 − γ)
gap between the optimal policy in discounted MDP andthat in average-reward
MDP. Therefore, we√√ should take1 − γ ≤ O(1/ n) if we require an O(1/ n) accuracy
for average-reward MDP. However, this results in at least
1/n1/4 sub-optimality gap for the discounted MDP. Therefore, this naive approach√ does not help us find a nearly
optimal policy with 1/ n accuracy.
2.2. LP-based Reformulations
Let P(s,a) = [Ps,a (s1 ), · · · , Ps,a (s|S| )]> ∈ ∆(S)
be the vector of state transition probabilities
for the state-action pair (s, a).
Let P=[P(s1 ,a1 ) , · · · , P(s1 ,a|A| ) , · · · , P(s|S| ,a1 ) , · · · , P(s|S| ,a|A| ) ] ∈R|S|×m and 1|A| = [1, 1, · · · , 1]> ∈ R|A| . Then define>
the matrix M as: M := Diag(1>|A| , · · · , 1|A| ) − P. The
optimality condition, i.e., the Bellman equation, of theaverage-reward MDP can be equivalently written as thefollowing linear program (Puterman, 1994):
minv,hv
v · 1 + (I − Pa )h − ra ≥ 0, ∀a ∈ A,

s.t.

(1)

where Pa ∈ R|S|×|S| denotes the matrix whose (s, s0 )component is Ps,a (s0 ), and ra ∈ R|S| such that ra (s) =r(s, a). This can be derived by the definition of Bellman
equation in the average-reward case.
It is well-known that the LP (1) admits the following dual
program, which also gives the optimal solution of the problem (Puterman, 1994):maxθ

r> θ :=s.t.

M θ = 0,P

s∈S,a∈A r(s, a) · θ(s, a)P

s,a θ(s, a) = 1,

(2)

Note that the optimal solution of the dual problem corresponds to the stationary distribution corresponding to an
optimal policy (see (Puterman, 1994)). Hence, we use thenotation θ to denote the optimization variable of the dual
problem.
The optimal θ∗ can be used to generate a policy πθ∗ , whereπθ is defined asπθ (a | s) = P

θ(s, a),θ(s, a0 )

(3)

a0 ∈A

P
if a0 ∈A θ(s, a0 ) > 0; and πθ (· | s) can be defined as any
distribution
P in ∆(A), e.g., a uniform one with πθ (a | s) =1/|A|, if a0 ∈A θ(s, a0 ) = 0. This πθ∗ then corresponds toan optimal policy π ∗ of the MDP (Puterman, 1994).
To better study the relationship between the stationary distribution and the data distribution, we also consider the scaled
version of the LP. This is also referred to as the marginal importance sampling formulation of the MDP in the literature(Nachum et al., 2019; Lee et al., 2021; Zhan et al., 2022).
First, we define w ∈ Rm
+ such that w(s, a)µ(s, a) = θ(s, a),i.e., w(s, a) denotes the ratio between the stationary distribution of the target policy and the offline data distribution.
For each (s, a, s0 ) ∈ S × A × S, let Ks0 ,(s,a) ∈R|S|×m be a matrix satisfying Ks0 ,(s,a) (s, (s, a)) = 1,
Ks0 ,(s,a) (s0 , (s, a)) = −1 and all other entries are zeros.
Define the distributions ν and νD over S × A × S as follows: ν(s, a, s0 ) := Ps,a (s0 )µ(s, a) and νD (s, a, s0 ) :=|nD (s, a, s0 )|/n. Finally, we also define the matrices
K = E(s,a,s0 )∼ν Ks0 ,(s,a) , KD = E(s,a,s0 )∼νD Ks0 ,(s,a) . (4)Furthermore, we define u ∈ Rm such that u(s, a) :=r(s, a)µ(s, a). Then, we have the following lemma which
relates these quantities to the ones in Problem (2).
Lemma 1. We have u> w = r> θ and Kw = M θ.

Submission and Formatting Instructions for the DP4ML workshop

Proof. Note that the first inequality directly follows fromthe definitions of u and w.

becomes:max

The second equality can be derived as follows. Let
K(s0 , (s, a)) and M (s0 , (s, a)) denote the (s0 , (s, a))-th element of the matrices K and M , respectively. Note that
K(s0 , (s, a)) = M (s0 , (s, a)) · µ(s, a) for all (s, a, s0 ) ∈S × A × S. Now:X
[Kw]s =K(s, (s̃, ã))w(s̃, ã)(s̃,ã)=X

M (s, (s̃, ã))µ(s̃, ã)w(s̃, ã) = [M θ]sw∈W :=[0,Bw ]|S||A|

s.t.

uTD w

KD w = 0Xw(s, a)µD (s, a) = 1.

(8)

s,a

However, (8) may not have a feasible solution due to the additional constraint w ∈ W = [0, Bw ]|S||A| . To address thisissue, in the next section we relax the equality constraints toguarantee the feasibility of the problem.

(s̃,ã)3. Average-Reward MDP Case

thereby completing the proof.
Using Lemma 1, we can rewrite Problem (2) as follows:
max u> w s.t.

Kw = 0,w≥0Xw(s, a)µ(s, a) = 1.

(5)∗

Let w be the solution to (5), then we can obtain the optimal
policy by computing πw∗ , where with a slight abuse ofnotation, πw is defined asπw (a | s) :=P

w(s,a)πµ (a|s)
00
a0 ∈A w(s,a )πµ (a |s)1|A|

min (−uTD w)

w∈W

s,a

(

To make sure the feasibility of the empirical LP, we relax theequality constraints in (8) and solve the following empiricalproblem:, if c > 0
if c = 0(6)P
where c := a0 ∈A w(s, a0 )πµ (a0 | s). We recall that πµ is
the conditional distribution of a given s under µ, which canalso be viewed as the behavior policy.

s.t. kKD wk1 ≤ En,δ , ∀x ∈ B.
X|
w(s, a)µD (s, a) − 1| ≤ En,δ ,

(9)

s,a

p
√
where En,δ := 2Bw |S| log((2|A| + 2)/δ)/ n. Let wD
be the solution to the above problem. We can obtain thepolicy πD by setting πD = πθ̃D , where for each (s, a) ∈S×Aθ̃D (s, a) = wD (s, a)πµ (a | s).

(10)

2.3. The empirical version

Definition 2. For a policy π, we let βπ be the stationary
distribution of the transition
Pmatrix Pπ . For some θ, we letβθ ∈ R|S| satisfy βθ (s) = a θ(s, a).

However, we only get access to the empirical estimates of
K and u. Consider the empirical version of (5)We make the following assumption on the worst case mixing
time of the transition matrix.
Assumption 2. There exists some T0 > 0 such thatkPπT0 β − βπ k1 ≤ 1/2 for any π and any state distribution β ∈ ∆(S).

max uTD w
w≥0

s.t.

KD w = 0Xw(s, a)µD (s, a) = 1,

(7)

s,a

By the above assumption, we have the following immediate
result:where we recall the definition of KD in (4), and defineuD ∈ Rm as uD (s, a) = r(s, a)µD (s, a), with µD (s, a) =nD (s, a)/n.

Lemma 2. Let k0 ≥ t0 log2 (1/En,δ ). Then kPπk0 β −βπ k1 ≤ En,δ for any π and any state distribution β ∈∆(S).

To ensure that the empirical and the population versionof LP are closed to each other, we need to make use ofconcentration inequalities for (K − KD )w, (u − uD )T w,
which require certain boundedness of w.

Proof. For a vector ζ, define ζ + = max(ζ, 0) and ζ − =max(−ζ, 0). Then we have ζ + − ζ − = ζ and kζk1 =kζ + k1 + kζ − k1 . It suffices to prove that for j > 0,kPπjt0 β − Pπkt0 β 0 k1 ≤ (1/2)j−1 . We prove itby induction. For j = 1, the result holds by Assumption 2 andtriangular inequality. Suppose that the result holds forj. Let ζ = Pπjt0 β − Pπjt0 β 0 . Then kζk ≤ kPπjt0 (β −Let Bw ≥ C ∗ be some upper bound of C ∗ . Combining Assumption 1, we insert the infinity norm constraint
kwk∞ ≤ Bw to (7) and the resulting empirical formulation

Submission and Formatting Instructions for the DP4ML workshop

βπ )k1 + kPπjt0 (β 0 − βπ )k1 ≤ (1/2)j−1 . Since Pπjt0 β andPπjt0 β 0 are probability distributions, 1T ζ = 0. Therefore,kζ + k1 = 1T ζ + = 1T ζ − = kζ − k1 . Hence, kζ − k1 =kζ + k1 ≤ (1/2)j since kζk1 = kζ + k1 + kζ − k1 . Let β +be a probability distribution such that β + = λζ + for someλ ≥ 2j−1 . Also let β − = λβ − is also a probability distribution. ThenkPπ(j+1)t0 (β − β 0 )k1= kPπt0 ζk1(11)
1 t0 +=
kP β − Pπt0 β − k1(12)λ π≤ (1/2)j−1 · (1/2)(13)=(1/2)j ,(14)

Proof. First, by Assumption 1 and the definition of w, there
exists somePw∗ ∈ W . We fix the w∗ and notice thatKw∗ = 0, s,a w∗ (s, a)µ(s, a) = 1. Then kKD w∗ k1 =≥ 1 − δk(KDP− K)w∗ k1 ≤ En,δ with probability
P
and | s,a w∗ (s, a)µD (s, a) − 1| = | s,a w∗ (s, a)(µD −µ(s, a))| ≤ En,δ with probability ≥ 1 − δ. Therefore, theresult follows from union bound.
By this lemma, we haveuTD wD ≥ uTD w∗
with probability ≥ 1 − 2δ. According to Lemma 3, we
further havecompleting the proof.

uT wD ≥ uT w∗ − En,δ = J(π ∗ ) − En,δ .

(15)Theorem 1. We have∗J(π ) − J(πD ) ≤ Õ(k0p√|S|/ n)with probability at least 1 − 3δ.
3.1. Proof

We next relate uT wD to J(πD ). Let θ ∈ R|S||A| satisfying
θ(s, a) = w(s, a)µ(s, a). We have the following lemma
relating rT θ = uT w to J(πθ ) = J(πw ).
1. If θ ∈ ∆(S × A), and (P − E)θ = 0, we

Lemma 5.
haverT θ = J(πθ ).

Let B = [−1, 1]|S| be the L∞ -norm ball centered at 0.
First, we have the following concentration bounds similar
to the ones in the proof of Theorem 2 in (Ozdaglar et al.,2023).

2. We havekβθ − βπθ k1≤ k0 k(I − Pπθ )βθ k1
X+ 3k0 |
w(s, a)µ(s, a) − 1| + En,δLemma 3. We haves,a1. For any w ∈ W, x ∈ B, with probability ≥ 1 − δp√|x> (K−KD )w| ≤ 2Bw |S| log((2|A| + 2)/δ)/ n
2. For any w ∈ W with probability ≥ 1 − δ.
p√|(u − uD )> w| ≤ 2Bw |S| log((2|A| + 2)/δ)/ n
3. For any w ∈ W with probability ≥ 1 − δ.
p√|(µ − µD )> w| ≤ 2Bw |S| log((2|A| + 2)/δ)/ n
According to this lemma, we conclude that some optimalw∗ is feasible to problem (9) with high probability.
Lemma 4. There exists some optimal w∗ = θπ∗ /µ(s, a)for some optimal policy π ∗ such that the following three
conditions hold with probability ≥ 1 − 2δ:
1. w∗ ∈ W ;2. kKD w∗ k1 ≤ En,δ ;P
3. | s,a w∗ (s, a)µ(s, a) − 1| ≤ En,δ .

= k0 kKwk1 + 3k0 |X

w(s, a)µ(s, a) − 1| + En,δ .

s,a

(16)

Proof of Lemma 5. We only prove the second part and thefirst part is just a special case. First, it is easy to see that
there exists some β̄θ such that1.

Ps β̄θ (s) = 1 and β̄θ (s) ≥ 0;

2. kβθ − β̄θ k1 ≤ |Ps,a w(s, a)µ(s, a) − 1|.

Notice that by Assumption 2,kβπθ − β̄θ k1 − En,δ ≤ kβ̄θ − Pπkθ0 β̄θ k1≤ k0 k(I − Pπθ )β̄θ k1≤ k0 k(I − Pπθ )βθ k1 + 2k0 kβ̄θ − βθ k1 ,which, combined with triangle inequality, gives the final
bound.
Finally, we can prove our main result, Theorem 1.

Submission and Formatting Instructions for the DP4ML workshop

Proof of Theorem 1. Let w = wD and θ(s, a) =w(s, a)µ(s, a). Also let rπD ∈ R|S| defined as rπD (s) =r(s, ·)T πD (s, ·).
Then by Lemma 5, we have|J(πD ) − uT wD |=|rπTD (βπθ − βθ )|≤kβθ − βπθ k1≤

k0 kKwD k1 + 3|

X

References
Chen, J. and Jiang, N. Information-theoretic considerations
in batch reinforcement learning. In International Conference on Machine Learning, pp. 1042–1051. PMLR,
2019.
Chen, J. and Jiang, N. Offline reinforcement learning undervalue and density-ratio realizability: the power of gaps.
arXiv preprint arXiv:2203.13935, 2022.

wD (s, a)µ(s, a) − 1| + En,δ ,s,awhere the first inequality is because of the boundedness ofr, and the second inequality is because of Lemma 5. By
Lemma 3 as well as the constraints in (9), we further have|J(πD ) − uT wD | ≤ 5k0 En,δ .
Finally combined with (15), we have the desired result.

Farias, V., Li, A., Peng, T., and Zheng, A. Markovian interference in experiments. Advances in Neural Information
Processing Systems, 35:535–549, 2022.
Fujimoto, S., Meger, D., and Precup, D. Off-policy deep
reinforcement learning without exploration. In Proceedings of the 36th International Conference on Machine
Learning (ICML), 2019.
Jin, Y. and Sidford, A. Efficiently solving MDPs withstochastic mirror descent. In International Conference on
Machine Learning, pp. 4890–4900. PMLR, 2020.
Jin, Y. and Sidford, A. Towards tight bounds on the sample complexity of average-reward mdps. In International Conference on Machine Learning, pp. 5055–5064.
PMLR, 2021.
Jin, Y., Yang, Z., and Wang, Z. Is pessimism provably efficient for offline rl? In arXiv preprint arXiv:2012.15085,
2020.
Kumar, A., Zhou, A., Tucker, G., and Levine, S. Conservative q-learning for offline reinforcement learning. In
Conference on Neural Information Processing Systems(NeurIPS), 2020.
Lee, J., Jeon, W., Lee, B.-J., Pineau, J., and Kim, K.E. Optidice: Offline policy optimization via stationary distribution correction estimation. arXiv preprint
arXiv:2106.10783, 2021.
Levine, S., Finn, C., Darrell, T., and Abbeel, P. End-toend training of deep visuomotor policies. The Journal of
Machine Learning Research, 17(1):1334–1373, 2016.
Levine, S., Pastor, P., Krizhevsky, A., Ibarz, J., and Quillen,
D. Learning hand-eye coordination for robotic graspingwith deep learning and large-scale data collection. The
International Journal of Robotics Research, 37(4-5):421–
436, 2018.
Levine, S., Kumar, A., Tucker, G., and Fu, J. Offline reinforcement learning: Tutorial, review, and perspectives onopen problems. arXiv preprint arXiv:2005.01643, 2020.

Submission and Formatting Instructions for the DP4ML workshop

Liu, Y., Swaminathan, A., Agarwal, A., and Brunskill, E.
Provably good batch off-policy reinforcement learning
without great exploration. Advances in Neural Information Processing Systems, 33:1264–1274, 2020.

Swaminathan, A., Krishnamurthy, A., Agarwal, A., Dudik,
M., Langford, J., Jose, D., and Zitouni, I. Off-policy
evaluation for slate recommendation. Advances in Neural
Information Processing Systems, 30, 2017.

Maddern, W., Pascoe, G., Linegar, C., and Newman, P. 1
year, 1000 km: The oxford robotcar dataset. The International Journal of Robotics Research, 36(1):3–15, 2017.

Todorov, E., Erez, T., and Tassa, Y. Mujoco: A physics
engine for model-based control. In 2012 IEEE/RSJ international conference on intelligent robots and systems, pp.
5026–5033. IEEE, 2012.

Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness,
J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al. Human-level control
through deep reinforcement learning. Nature, 518(7540):
529–533, 2015.

Tseng, H.-H., Luo, Y., Cui, S., Chien, J.-T., Ten Haken,
R. K., and Naqa, I. E. Deep reinforcement learning forautomated radiation adaptation in lung cancer. Medical
Physics, 44(12):6690–6705, 2017.

Munos, R. and Szepesvári, C. Finite-time bounds for fitted
value iteration. In Journal of Machine Learning Research,
volume 9, pp. 815–857, 2008.

Uehara, M. and Sun, W. Pessimistic model-based offline RL:
Pac bounds and posterior sampling under partial coverage.
arXiv e-prints, pp. arXiv–2107, 2021.

Nachum, O., Dai, B., Kostrikov, I., Chow, Y., Li, L., andSchuurmans, D. Algaedice: Policy gradient from arbitrary experience. arXiv preprint arXiv:1912.02074, 2019.
Naik, A., Shariff, R., Yasui, N., Yao, H., and Sutton, R. S.
Discounted reinforcement learning is not an optimization
problem. arXiv preprint arXiv:1910.02140, 2019.
Ozdaglar, A., Pattathil, S., Zhang, J., and Zhang, K. Revisiting the linear-programming framework for offline RL
with general function approximation. In International
Conference on Machine Learning, 2023.
Puterman, M. L. Markov decision processes: Discrete
stochastic dynamic programming, 1994.
Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell,
S. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural
Information Processing Systems, 34:11702–11716, 2021.
Rashidinejad, P., Zhu, H., Yang, K., Russell, S., and Jiao,
J. Optimal conservative offline rl with general function
approximation via augmented lagrangian. arXiv preprint
arXiv:2211.00716, 2022.
Scherrer, B. Approximate policy iteration schemes: A comparison. In International Conference on Machine Learning, pp. 1314–1322. PMLR, 2014.
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L.,
Van Den Driessche, G., Schrittwieser, J., Antonoglou, I.,
Panneershelvam, V., Lanctot, M., et al. Mastering thegame of Go with deep neural networks and tree search.
nature, 529(7587):484–489, 2016.
Sutton, R. S. and Barto, A. G. Reinforcement learning: An
introduction. MIT press, 2018.

Vinyals, O., Ewalds, T., Bartunov, S., Georgiev, P., Vezhnevets, A. S., Yeo, M., Makhzani, A., Küttler, H., Agapiou,J., Schrittwieser, J., et al. Starcraft II: A new challenge forreinforcement learning. arXiv preprint arXiv:1708.04782,
2017.
Wang, J., Wang, M., and Yang, L. F. Near sample-optimal
reduction-based policy learning for average reward mdp.
arXiv preprint arXiv:2212.00603, 2022.
Wang, M. Randomized linear programming solves themarkov decision problem in nearly linear (sometimes
sublinear) time. Mathematics of Operations Research, 45(2):517–546, 2020.
Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P., and Agarwal,
A. Bellman-consistent pessimism for offline reinforcement learning. arXiv preprint arXiv:2106.06926, 2021.
Zhan, W., Huang, B., Huang, A., Jiang, N., and Lee, J. D. Offline reinforcement learning with realizability and singlepolicy concentrability. arXiv preprint arXiv:2202.04634,
2022.
Zhang, K., Yang, Z., Liu, H., Zhang, T., and Başar, T. Finitesample analysis for decentralized batch multiagent reinforcement learning with networked agents. IEEE Transactions on Automatic Control, 66(12):5925–5940, 2021.