Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangian
Authors: Paria Rashidinejad
Hanlin Zhu
Kunhe Yang
Stuart Russell
Jiantao Jiao
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Offline RL
Pessimism
RL Theory

Abstract: Offline reinforcement learning (RL), which aims at learning good policies from historical data, has received significant attention over the past years. Much effort has focused on improving offline RL practicality by addressing the prevalent issue of partial data coverage through various forms of conservative policy learning. While the majority of algorithms do not have finite-
sample guarantees, several provable conservative offline RL algorithms are designed and analyzed within the single-policy concentrability framework that handles partial coverage. Yet, in the nonlinear function approximation setting where confidence intervals are difficult to obtain, existing provable algorithms suffer from computational intractability, prohibitively strong assumptions, and suboptimal statistical rates. In this paper, we leverage the marginalized importance sampling (MIS) formulation of RL and present the first set of offline RL algorithms that are statistically optimal and practical under general function approximation and single-policy concentrability, bypassing the need for uncertainty quantification. We identify that the key to successfully solving the sample-based approximation of the MIS problem is ensuring that certain occupancy validity constraints are nearly satisfied. We enforce these constraints by a novel application of the augmented Lagrangian method and prove the following result: with the MIS formulation, augmented Lagrangian is enough for statistically optimal offline RL. In stark contrast to prior algorithms that induce additional conservatism through methods such as behavior regularization, our approach provably eliminates this need and reinterprets regularizers as "enforcers of occupancy validity" than "promoters of conservatism."

Published as a conference paper at ICLR 2023
OPTIMAL CONSERVATIVE OFFLINE RL WITH GENERAL FUNCTION APPROXIMATION VIA AUGMENTED LAGRANGIAN
Paria Rashidinejad Hanlin Zhu!
Kunhe Yang'
Stuart Russell'
Jiantao Jiao
'Department of Electrical Engineering and Computer Sciences
*Department of Statistics
University of California, Berkeley
(paria. rashidinejadd, hanl kunheyang, russell, jiantao) / @berkeley. edd
ABSTRACT
Offline reinforcement learning (RL), which aims at learning good policies from historical data, has received significant attention over the past years. Much effort has focused improving offline RL practicality by addressing the prevalent issue partial data coverage through various forms conservative policy learning. While the majority of algorithms do not have finite-sample guarantees, several provable conservative offline RL algorithms are designed and analyzed within the single-policy concentrability framework that handles partial coverage. Yet, in the nonlinear function approximation setting where confidence intervals are difficult obtain, existing provable algorithms suffer from computational intractability, prohibitively strong assumptions, and suboptimal statistical rates. In this paper. we leverage the marginalized importance sampling (MIS) formulation of RL and present the first set of offline RL algorithms that are statistically optimal and prac- tical under general function approximation and single-policy concentrability, by- passing the need for uncertainty quantification. We identify that the key to suc- cessfully solving the sample-base based approximation of the MIS problem is ensuring that certain occupancy validity constraints are nearly satisfied. We enforce these constraints by novel application of the augmented Lagrangian method and prove the following result: with the MIS formulation, augmented Lagrangian is enough for statistically optimal offline RL. In stark contrast to prior algorithms that induce additional conservatism through methods such as behavior regularization, our ap- proach provably eliminates this need and reinterprets regularizers as "enforcers of occupancy validity" than "promoters of conservatism."
INTRODUCTION
The goal of offline RL is to design agents that learn to achieve competence in a task using only wreliously-colletted dataset of interactions (Lange al., 2012). Offline RI. is promising tool for many critical applications, from healthcare to autonomous driving to scientific discovery, where the online mode of learning by interacting with the environment dangerous, impractical, costly, or even impossible (Levine et al., 2020). Despite this, offline RL has not yet been truly successful in practice (Fujimoto al., 2019) and impressive RL performance has been limited to settings with known environments (Silver et al., 2017; Moravčík et al., 2017), access to accurate simulators (Mnih al., 2015; Degrave et al., 2022: Fawzi et al., 2022), or expert demonstrations (Vinyals al., 2017).
One of the central challenges in offline RL is the lack of uniform coverage in real datasets and the distribution shift between the occupancy of candidate policies and offline data distribution, which pose difficulties in accurately evaluating the candidate policies. Over the past years, a body of liter- ature has focused on addressing this challenge through developing conservative algorithms, which aim at picking policy among those well-covered in the data. On the practical front, various forms of conservatism are proposed such as behavior regularization through policy constraints (Kumar et al., 2019; Fujimoto et al., 2019; Nachum & Dai, 2020), learning conservative values (Kumar et al., 2020; Liu et al., 2020; Agarwal et al., 2020), or learning pessimistic models (Kidambi et al., 2020; Yu et al., 2020; 2021); )); see Appendix B for further discussion related work.

---

Published as a conference paper at ICLR 2023
From a theoretical standpoint, partial data coverage has recently been studied within variants of the single-policy concentrability framework (Rashidinejad et al., 2021; Xie et al., 2021; Uehara & Sun, 2021), which characterizes the distribution shift between offline data and occupancy of target (often optimal) policy, in contrast to all-policy concentrability commonly used in earlier works (Scherrer, 2014; Chen & Jiang, 2019; Liao al., 2020; Zhang et al., 2020a; Xie & Jiang, 2021). Within this framework and in the tabular and linear fuunction approximation settings, pessimistic algorithms that leverage uncertainty quantifiers to construct lower confidence bounds (Jin et al., 2021; Rashidinejad et al., 2021; Yin et al., 2021; Shi et al., 2022; Li et al., 2022) enjoy optimal statistical rate. In the general function approximation setting, pessimistic algorithms largely assume oracle access to uncertainty quantification, either for constructing penalties that are subtracted from rewards (Jin et al., 2021; Jiang & Huang, 2020) or selecting the most pessimistic option among those that fall within the confidence region implied by the offline data (Uehara & Sun, 2021; Xie et al., 2021; Chen & Jiang, 2022). However, uncertainty quantifiers are difficult to obtain in non-lineat function approximation and existing heuristics Tennenholtz et al., 2021; Yu et al., 2021). Recent works by Cheng et al. (2022) and Zhan et al. (2022) propose provable alternatives to uncertainty-basee methods, but leave achieving optimal statistical rate of 1/VN, where N is the dataset size, as an open problem.
empirically observed to be unreliable (Rashid et al., 2019;
Among all, the marginal importance sampling (MIS) methods, which aim at learning weights w that estimate the distribution shift between induced policy occupancy du and data distribution μl, lend themselves well to the single-policy concentrability framework. Though more popular in off-policy evaluation (Liu et al., 2018; Xie et al., 2019; Uchara et al., 2020; Zhang et al., 2020b), MIS has also been used for conservative offline RL such as AlgaeDICE (Nachum et al., 2019b) and OPtiDICE (Lee al., 2021), both of which incorporate behavior regularization. Recently, Zhan et al. (2022) theoretically studied variant of OptiDICE, showing that MIS with behavior regularization enjoys sinite-sample guarantees (though achieving suboptimal 1 1/N2/66 rate) and circumvents certain fun- damental difficulties observed in value-based offline RL with function approximation (Du et al., 2019; Wang et al., 2020; 2021; Weisz et al., 2021; Zanette, 2021; Foster et al., 2021).
1.1 CONTRIBUTIONS AND RESULTS
Motivated by the benefits offered by MIS, we study designing statistically optimal offline learning algorithms under the MIS formulation with general function approximation and single-policy con- centrability. We conduct theoretical investigations and design algorithms starting from multi-armed bandits (MABs), going forward contextual bandits (CBs), and finally Markov decision processes (MDPs). In the rest of this section, we present a preview of our contributions and results.
Multi-armed bandits. Empirical MIS algorithms often incorporate behavior regularization, whose role is justified as promoting conservatism by keeping the occupancies of learned and behavior policies close (Nachum et al., 2019b; Lee et al., 2021). Yet, whether and why these regularizers are necessary from a theoretical perspective remain unclear. Zhan et al. (2022) motivates behav- ior regularization as way of introducing curvature in an otherwise linear optimization problem. We extensively investigate the effect of regularization, starting from the simplest setting of MABs with function approximation, as existing algorithms when specialized to offline MABs, are either intractable, have suboptimal finite-sample guarantees, or require access to uncertainty quantifiers.
We state our results on offline MABs with general function approximation and single-policy con- centrability in the informal theorem below.
Theorem (informal) (I) There exists an offline MAB instance where the unregularized MIS fails to achieve suboptimality that decays with N. (II) MIS with behavior regularization (PRO-MAB Algorithm 1) achieves O(L/VN) suboptimality. (III) If one searches only over the space of weights that induce valid occupancies (dw = =1), then unregularized MIS achieves O(1//N) suboptimality.
Here, we prove that unregularized MIS fails even in bandits and provide a tight analysis of PRO- MAB, a special case of PRO-RL algorithm, improving over the original 1/N 1//1/6 rate shown by Zhan et al. (2022). In our analysis, we find that the key to the success of PRO-MAB is near-validity of the learned occupancy d In MABs, the validity constraint simply requires the learned occupancy to be a probability distribution: d Ea (a)){(a) = 1, where is arm. With proper choice of hyperparameter. we show that behavior regularization enforces learned occupancy to be nearly valid: d, 2(1). We further prove that regularization is not required if validity is otherwise satisfied.
2

---

Published as a conference paper at ICLR 2023
Given that occupancy validity is the constraint of the optimization problem solved by MIS (see e.g. (1)), we ask whether there are any methods for solving empirical optimization problems that find more constraint- -adeerin solutions compared to those yielded by Lagrange multipliers adopted in prior works (Lee et al., 2021; Zhan et al., 2022). The augmented Lagrangian method (ALM), which adds a quadratic loss on the constraints (d. - =)²² is natural choice for our purpose. The ALM term can be easily estimated from offline data and forms Algorithm 1. We show that ALM results in du (1)), ensuring near-validity of learned occupancy and leading to the following guarantee.
Theorem (informal) The policy returned by an algorithm that combines ALM with MIS (ALMIS) for offinee MABs (Algorithm/ 1) achieves O(1 0(1/VN) suboptimality.
ALMIS offers several benefits over PRO-MAB such as eliminating the need for picking the reg- ularizer and only requiring single-policy concentrability instead of the two-policy requirement of PRO-MAB, which can be strong (Section 5.3). Additionally, behavior regularization introduces bias in the solution even with infinite data (Chen & Jiang, 2022) and the bias-variance tradeoff must be carefully handled. However, ALM merely enforces the optimization constraints and leads to provably unbiased solutions (Lemma 14). More importantly, as we see shortly, going beyond the single-state MABs, behavior regularization becomes suboptimal while ALMIS maintains optimality.
Contextual bandits. In offline CBs, we analyze two approaches: MIS with behavior regularization, and an extension of ALMIS. We state our results in the following informal theorem.
Theorem (informal) (I) There exists CB instance where MIS with behavior regularization (PRO- CB Algorithm 6) suffers from suboptimality ((NN)) with 33 > -1/2. (II) Policy returned by ALMIS for offline CBs (Algorithm 2) achieves suboptimality of (I///N).
Informally, the failure of PRO-CB to achieve the optimal rate is because the regularization parame- ter has to be small to control bias, but such small regularization is not strong enough to ensure the validity of learned occupancy in most states. Therefore, one must choose larger regularization, lead- ing to an overall suboptimal rate. Prior works Chen & Jiang (2022); Cheng et al. (2022) also allude to this phenomenon, explaining that regularizers appear to be the culprit behind suboptimal rates. In CBs, the occupancy validity constraints require conditional occupancy to be a valid probability distribution in every state. In Algorithm 2, we incorporate ALM in offline CBs by adding a weighted sum of quadratic losses describing the validity constraint in each state, where the weights are set to the state occupancies to capture their relative importance. Enforcement of the constraints by ALM without introducing any bias is the key to the optimality of our algorithm.
MDPs. Validity constraints in MDPs ensure that the learned state occupancy (s)
Ea w(s a))(s.a) a) is close to the actual state occupancy d**(ss, (s), where The is the policy computed from weights w. Directly enforcing this constraint results in an ALM term that cannot easily be es- timated from offline data. We address this difficulty by expressing the ALM term in the variational form. From there, we derive two variants, one model-based and one model-free, of the ALMIS algorithm for offline RL, that enjoy the following guarantee.
Theorem (informal) Both variants of ALMIS for offline RL. achieve O(1/VN) suboptimality.
This marks ALMIS as the first practical and statistically optimal offline RL algorithm that operates in the general function approximation and partial data coverage setting, while avoiding uncertainty quantification and additional regularizers. Conservatism of ALMIS is baked into the MIS formula- tion and supported by the ALM: bounded MIS weights prevent learned occupancy to deviate sig- nificantly from data distribution, and ALM ensures closeness of the learned and actual occupancies. When combined, ALMIS learns a policy whose actual occupancy is close to the data distribution.
We thus proved that ALM improves sample complexity compared to alternatives such as behavior regularization. This is in addition to the benefits on optimization stability that are likely to be offered by the ALM, as the ALM improves over the ill-posed Lagrange multiplier objective (Ben- Tal & Nemirovski, 2022). Our theoretical findings can explain the empirical observations of Yang al. (2020), who find MIS with behavior regularization to be unstable and propose regularizers in "the spirit of ALM" that gain superior performance and attribute performance gain to improved optimization. In this work, we present theoretically-fourt foundeed way of introducing ALM in offline RL and our analysis shows that ALM also leads to optimal sample complexity.
Notice that the validity constraints in MAB and CB are special cases of this constraint.
3

---

Published as a conference paper at ICLR 2023
2 BACKGROUND
Markoy decision process. An infinite-horizon discounted MDP is described by a tuple M = (S, A, P. R. p: 7), where is the state space, A is the action space, P: S (SS) is the transi- tion kemne,, R: S x A + A( 1)) encodes a family of reward distributions with r S x A + [0. 1] as the expected reward function, p : S - ASS) is the initial state distribution, and y E 1) the discount factor. We assume S and A are finite however, our results do not depend on their cardinal- ities and can be naturally extended to infinite sets. A stationary (stochastie) policy π .S S (AA) specifies a distribution over actions in each state. Each policy induces occupancy density over state-action pairs d' S x A + [0, 1] defined as (s, a) = (1 >) Σx= 7 Pc = s, a = a; T) where P. (sp- 8, a2 a: I7) denotes (s, a) visitation probability at step f, starting
so ~ p(.) and following и. We abuse notation and also write (s) = Eaea d" (s, a) to denote the discounted
state occupancy. Additionally, operator IP" is applied any function S x A + R and is defined as (P"")(s,a) == Es,,a' P(s'|s, (a)(a'(s'))))))))))))))))))) (s")u(s', .a).
An important quantity is the value policy π, which is the discounted sum of rewards (s) = EI 2'r So = 8, ar ~ T(- st), V 0] starting at s E S. Q-function (* a) of a policy is similarly defined. We write J(x) = (1 - ->
[s)] = Es,a--- [r(s, a)] to represent a scalar summary of the performance of a policy x. We denote by ' an optimal policy that maximizes the above objective and use the shorthand V == V** to denote the optimal value function.
Offline reinforcement learning, We focus on the offline RL, where the agent is only provided with a previously-collee
offline dataset D {(s; ag Ti, {()};²} Here, T; R(s;,,;) sf ~ P(- 8;, a;), and we assume S; a; pairs are generated i.i.d. according to a data distribution μ E A x A). To streamline the analysis, we assume that the conditional distribution (_(a(s) is known. 2 The goal of offline RL is to learn policy क based on the offline dataset so to minimize the sub-optimality with respect to an optimal policy x², i.e. J(x*) J() with high probability.
Marginalized importance sampling. In this paper, we consider marginalized importance sampling (MIS) formulation that aims at learning weights wis, a) to represent policy occupancy when mul- tiplied by data distribution: dw a) = w(s, a) (), a). Also denote (s) = EREA du ds, a). We
define the policy induced by w as T. (als) (s, (s, a) /d (s) for (s) > 0 and x (a|s) 1/|.A|
for (s) = 0.
Offline data coverage assumption. We design and analyze our algorithms within the single-policy concentrability framework (Rashidinejad et al., 2021), stated below.
Definition (Single-policy concentrability) Given a policy n, define C to be the smallest con- CC for all E S and A.
stant that satisfies (e.o)
p(a.a)
C² = C* captures coverage of n² in the offline data and much weaker than the widely used all all-policy concentrability that assumes bounded max, C*:; see Appendix B for further discussion.
Notation. We write (SS) to denote the probability simplex over a set S. For a function class F, write [F] to denote its complexity (such as cardinality in the discrete case or covering number in the continuous case). We use the notation x S y when there exists constant e > 0 such that x S cy and x y if constants C1 02 0 exist such that c1 |a|s lws ca|z:| We write f(x) O(g(z)) if M > 0, To exist such that [f(x)]s Mg(x) for all x 2 xo and use Ō(-) to be the big-O notation ignoring logarithmic factors. Define clip(x, a, b) 2 max(a, min(x, b}} for x, a, b E R.
3 MULTI-ARMED BANDITS
We start by considering the offline learning problem in the multi-armed bandit (MAB) setting, which is a special case of MDP with 7 0. S = 1, and D= { r.)) }
where a; ~ (((), R(a:)-
The goal of offline learning in MABs can be described as the following constrained optimization problem, where d represents occupancy over actions (arms)
max Ea-d [r(a)]
s.t. dd(a==1. 11
(I)
When ((aas) is unknown, hehavioral cloning can he used (Ross & Bagnell, 2014; Zhan al., 2022).
4

---

Published as a conference paper at ICLR 2023
3.1 PRIMAL-DUAL REGULARIZED OFFLINE BANDITS
To solve (1), the MIS approach with behavior regularization defines importance weights w(a) = d(a)//l p(a) and converts the problem (1) to its dual form by introducing the Lagrange multiplier
max min MAB (w, v) == Ra- [w(a)r[a)] - e (Ea=ylu(a)] - -1) - -a If (w((a))-
(2)
w20
The last term in (2) the behavior regularizer that characterizes the t f-divergence between the learned occupancy d and data distribution μ.. This term was originally proposed to induce conser- vatism by keeping the learned policy close to behavior policy (Nachum et al., 2019b; Lee et al., 2021). Problem (2) satisfies strong duality and we denote optimal primal and dual variables by w and or (Appendix C.2). When a = O, weights w² := w (might not be unique) induce optimal policy and u* := vi is the optimal reward. Approximating w and v to belong to classes W S RRAA and V E TR and solving the empirical version of (2) yields primal-dual regularized offline MAB (PRO-MAB Algorithm 5), a special case of PRO-RL algorithm of Zhan et al. (2022).
One might wonder whether the unregularized algorithm (a = 0) is sufficient for solving the offline learning problem in MABs, particularly under the natural and common assumption that elements of the function class W are bounded: w w(a) d(a)/p(( < B In the following proposition, we show that the answer is negative and there exist a MAB instance in which the unregularized algorithm finds a policy that suffers from a constant suboptimality. The proof is provided in Appendix C.3.
Proposition 1 (Unregularized MIS fails in MABs) Assume O S w(a) S Bu for w E W and Jo|s B. for v E V. Suppose realizability of any one of w² E W and V" E V and concentrability of π-' == Twy For any N 2 2, there exists a MAB instance where म returned by Algorithm 5 with satisfies (Tx) JJ J(t = 1/6 with a constant probability.
We note that Zhan et al. (2022) also argues the failure of the unregularized algorithm by giving counterexample in the MDP setting. We discuss this example in detail in Section 5.3. Proposition reveals additional insights: the objective (16) with a 0 fails not just in MDPs but also in bandits, even when the optimal policy is unique and data are collected by running a behavior policy.
Given the failure of the unregularized algorithm, we conduct a tight analysis of PRO-MAB with a > O. In the next theorem, we prove that under similar assumptions as Zhan et al. (2022) and with a proper choice of a, PRO-MAB returns a policy that enjoys optimal sample complexity.
Theorem (Suboptimality of PRO-MAB) Let f be - convex and non-negative with bounded value [f(x) < By and derivative ff' < By. Assume 0 S w(a) S Bw for w E W and Suppose
|u|ا B, for V. Fix 5 2 0 and set x B, (B. + 1) + B2)/ / ( realizability of wa E W and v2 E V and concentrability of n- == Two and T. == Fug. Then, with probability at least 6, policy ât returned by Algorithm 5 achieves
(B, Bw
By
log log((11111/8) N
J( ((t)
My
To our knowledge, this the first statistically optimal guarantee for practical offline MAB algo- rithm with function approximation and partial coverage and improves over the 1/N1/6 guarantee given by Zhan et al. (2022). We now briefly explain the differences between the analysis methods; a complete proof is deferred to Appendix C.4. Zhan et al. (2022) bounds policy suboptimality by a 1-+1/(a1/2/1/// where the first term stems from the bias caused by the regularizer and the second term emerges from bounding the difference of v and w via strong convexity of L., Optimizing the bound over a gives the final 1/N1/6 guarantee. In contrast, our analysis connects subopti- mality to occupancy validity. We prove that suboptimality is bounded by 1/(d,, VN), where de =. (()) We then show that setting x 1/vN is sufficient to ensure near-validity of occupancy de = 2(1). yielding the optimal rate. We observe a similar phenomenon in Proposition I that small d for certain w E W can cause the unregularized MIS to fail. In the following section, we investigate this phenomenon further, leading to a new offline learning algorithm.
3.2 AUGMENTED LAGRANGIAN REPLACES BEHAVIOR REGULARIZATION
The next proposition further affirms the importance of policy validity and shows that if the occu- pancy is valid, such as by searching only over the weights that induce valid occupancies, then the unregularized algorithm enjoys an optimal rate. Proof of this result can be found in Appendix C.5.
5

---

Published as a conference paper at ICLR 2023
Algorithm 1 ALM with MIS (ALMIS) for offline MAB
1: Inputs: Dataset D = {(a rz) J classes W and V.
2: Find solution U 6 the following problem
N Σ w(as) - -1) (3) N
max min MAB (w, v) = N Σ w(ai)r - v(w(a)) - -1) WEW VEV
3: Return: T6-
Proposition 2 (Constraint satisfaction is sufficient in MAB) Assume as in Theorem 1. Let it be the oulput of Algorithm 5 with a = and assume that Ea ul())a(a) = Then, for any ā > 0, the following holds with probability of at least 1 5
log/V/]W//6
J(x*) - J(A) 2 (B.
N
Motivated by the discussion above, we take a step back and ask: are there any other methods for solv- ing constrained optimization problems that find more constraint satisfying solutions when applied to the empirical approximation of the original problem? promising candidate is the augmented Lagrangian method (ALM) which adds quadratic loss on the constraints to the objective. Applied to (1), ALM forms the following objective, whose empirical version leads to Algorithm 1.
constraint-sattifyinngg
max min MAB w20
(w, v) == Ea-u [w(a)r(a)] - (E [w) - 1) (Ea-u - 1)2.
(4)
The following theorem establishes an upper bound the suboptimality of the policy returned by Algorithm 1. This theorem is a special case of Thehremm 3, whose proof is given in Appendix D.3.
Theorem (Suboptimality of Algorithm 1) Assume that O S w(a) S Bw for any w W and |o|s B. for any E V. Further suppose realizability of any one of w² E W and v² E V and concentrability of x²* Tws. For any fixed 8 > O, policy a returned by Algorithm I achieves the following bound with probability of at least 1 - -
1og((W)/11/0))
J(T') - J(t) & B (B, + 1)
(5)
N
In the proof, we show that ALM results in near-validity of à by ensuring that da = 22(1, lead- ing to the optimal rate. Note that Algorithm does not include any explicit form of conservatism through regularizers uncertainty quantifiers. Colloquially, the MIS formulation and boundedness of W elements ensure that dæ(a)/μ(a) = vi(a) < B, and ALM ensures that da is close to the actual occupancy. Thus, Algorithm 1 seeks a policy whose actual occupancy within data distribu- tion. Algorithm offers several benefits compared to PRO-MAB: it only requires x' -concentrabiliiy instead of the π :, -concentrability requirement of PRO-MAB removes the need to design regu- larization function ff and adjust a, and does not introduce bias in the objective. The main advantage of ALM, however, becomes more evident as we move beyond bandits, where the behavior regular- ization provably fails to achieve the optimal statistical rate while ALM maintains optimality.
4 CONTEXTUAL BANDITS
The problem offline contextual bandits (CB) is a special case of offline RL with y = 00 and offline dataset D {(s,, a,, r,)] where 8; u(-) p(-), a; ul- a;), and ra R(s,, The linear programming constrained optimization problem for CB is given by
max Rggand [r(s,a)) d20
Σ
d(ss,a) p(s) E.
(6)
4.1 ANALYSIS OF PRIMAL-DUAL REGULARIZED OFFLINE CONTEXTUAL BANDITS
In the following proposition, we prove a performance lower bound on the primal-dual regularized offline CB (PRO-CB) presented in Algorithm 6, which is MIS with behavior regularization.
Proposition 3 (PRO-CB is suboptimal) Let f be My-strongly convex, differentiable, and non- negative with bounded values f(x)] By and derivative [x) Bp. Assume 0 S w(s, < B. for w E W. [e(s) < B., realizability w" w", E WW v², E V, and concentrability of x²' T;,- Let be the output of Algorithm 6. Then, for N poly(5, Bw, B,, By, By) and any there exists CB instance such that J(x)) [(+) Z No with constant probability, where B 1/2.

---

Published as a conference paper at ICLR 2023
Algorithm 2 ALM with MIS (ALMIS) for offline CB
1: Inputs: Dataset D = {ss, o, rz) HE= function classes W, V
2: Find a solution W, é to the following problem
max min FCB v) = w(s (r)r. -((.)) + r(s)) WEW NEV
Σ w(6, ())((()s))))) -)) -1)
-1 (8)
3: Return: से #16-
Proposition 3 shows that behavior regularization is statistically suboptimal regardless of a. The proof is presented in Appendix D.2. The main takeaway is that ensuring occupancy validity En (ss, ())((as)) = 21)1 for nearly all states appears to be critical achieving the optimal rate. Yet, without introducing large bias, behavior regularization is insufficient for such guarantee.
4.2 OFFLINE CONTEXTUAL BANDITS WITH AUGMENTED LAGRANGIAN
To encourage occupancy validity, we extend ALM to CBs and propose the following objective: max min CB (w,o)
w2u
"
Ep a)ss,))((ssa) a)] (xll(s)(((sss)) 1)] Es>
a)] 1)
When | (7) simplifies the ALM objective (2) for MABs. The ALM term can be understood as follows. Each element encourages the validity of occupancy in each state Σ,, w(s, (s) a) = and the elements are weighted according the state distribution: validity is more important in states that are actually more likely to be visited. Denote by w" an optimal solution to (7), which is equal the optimal solution of (6), and define (s)) == V*(s). The following theorem states that ALMIS achieves optimal rate in offline CBs, whose proof is in Appendix D.3.
Theorem (Suboptimality of Algorithm 2) Assume 0 S w(ss a) I B,, for w W and v(s) S B. for v E V. Moreover, suppose realizability of any one of w* E W and v* E V and concentra- bility of x² Tun. For any fixed 8 2 O, policy ā returned by Algorithm achieves the following suboptimality bound with probability of at least 1 6
((=') - J(a) x (B, + 1) [og((W))1100)
N
5 MARKOV DECISION PROCESSES
We now turn to offline RL. In addition to the offline dataset, we assume access to a dataset Do = IN with i.i.d. samples from the initial distribution p. similar prior works (Lee et al., 2021; Zhan et al., 2022). The linear programming formulation of RL. (Puterman, 2014) solves
max E. (r,,, d20
s.t. d(s) = (1 (s) + d'sss
E
(9)
e'
The constraints are known as Bellman flow equations and restrict the search to the space of valid occupancy distributions d= that can be induced in the MDP by running policy
5.1
CONSERVATIVE OFFLINE RL WITH AUGMENTED LAGRANGIAN
Motivated by the success of ALM in bandits, we propose the following extension to offline RL: (s)(s)
1 (10)
max min MDP (w, v) (1 (1 + EE [w[s, (s.. E
d 1
#20
where (8, r(s,a) + +, P(s'|s, a)v(s')())))))))))))))))))) v(s). One can check that the first two terms are the Lagrange dual of (9) and the last term is generalization of the ALM terms in bandits. The ALM elements encourage occupancy (w) to be close in ratio to the actual occupancy d (s) in each state and as before, the ALM elements are weighted according to their actual visitation d= be intuitively understood learns bounded weights (s, a) = d a)/p(s, s, a) & B The ALM term ensures that the ratio d (s)/d= (s) = (1) which roughly translates to d (s, a)/p((ssd a) B.,
Our particular ALM construction
follows. The MIS formulation
The ALM term in (10) is difficult to estimate as involves the expectation over unknown occupancy de and the computation of the ratio d (s) dd (s). We resolve this difficulty in the next sections.
7

---

Published as a conference paper at ICLR 2023
Algorithm 3 ALM with MIS (ALMIS) for offline RL RL- Model-based
1: Inputs: Datasets D, Do. Dm function classes W, V,U, fe (x) (x)
2: Estimate transitions via maximum likelihood: p argmaxrep Σ Ei=l In P(s)(s;,,.))
N.
3: Find a solution W, 6, â to the following problem
(1 1 7)
No
max min min L madel--bsed (w, v) #EW VEV wEM/ AL
Σ
(s(s)) + Σ a)
No
(14)
w(s), as) [ro + gu(()) - v(()) - ff= (u(s,, ((
+
4: Return: म TT.
5.2 ESTIMATING THE ALM TERM AND ALMIS ALGORITHMS FOR OFFLINE RL
We view the ALM term the negative f-divergence between du and d with f(x) == (x: 1)2 and express it in the variational form (Nguyen et al., 2010):
(5) d (s)
= -dm
min Ex
- Ea, [x(,, [x](,
(11)
Here, fx is the convex conjugate of f and we used the fact that d. (s. a)/dd)/ /d (s, a) = du (s) dm (s). Notice that Eg'. [fr( a}}l is the value of Tw in the same MDP but with rewards fo (z(s, a)). Define u as the fixed point of the following Bellman equation
u(s, a) = f- f=(x(s, a)) + ((P""))(ss))
(12)
Since u(s, a) is the Q-fuctiion of Tw with rewards f. (x(s, a)). we can rewrite (11) as (11) = minnn1 " [u(s, a)] E, af, (u(s, - >PP* a))]
(13)
Equation (13) involves expectations over P and which can be estimated empirically. Below, discuss model-free and model-based methods for estimating the term involving the transition operator pat We include some details on practical implementations in Appendix E.
Model-based ALMIS. For the model-based route, we assume access to class P that contains the true transitions and an additional dataset Dm = {(s a,, st) s where 8t q; μ and s ~ Given Dm, we obtain a maximum likelihood estimate of transitions and approximate the expectations using Do and DD which leads to model-based ALMIS for offline RI. (Algorithm 3).
Model-free ALMIS. As an alternative, we consider developing a model-free that uses a single- sample estimate of f==((((,,))))) a) (P (s, a)). This, however, roughly leads to the infamous double sampling problem (Baird, 1995). To circumvent this difficulty, in Appendix E.2 we use the dual embedding trick of Nachum et al. (2019a), to derive model-free ALMIS (Algorithm 4).
Theorem shows that ALMIS for offline RL enjoys optimal rates; see Appendix E.3 for the proof.
Theorem 4 (Suboptimality of ALMIS for offline RL) Assume 0 I w(s, < B for w W, (u(s)] < for E V, and |u(s, a) < Bu- Suppose realizability of any one of w² E W and o (x) = (s)) E V and concentrability of x² Tw-- Let T. (s, a) clip(r;, ( (s, a), -Ba, Br), where x is solution to (11) and Bn = (1 /4, and define wi, as the fixed-point solution to (12) when I Zw- Assume u U for any w W. Then, Bu satisfies (1 (1-7) -B2 + BB) < B, S }
Moreover, for any fixed 8 2 0, the following statements hold:
(I) Assume N No Nu. for simplicity. P E P,, then ā returned by Algorithm 3 achieves
J(zt) - J(a) B. + B, + +1+ B.) B. Log(( (PP4
(1-7)3
N
(II) Assume N No for simplicity. Let Si, argmaxç<0 muddel (w, v, u, () defined in (54). Assume Cu. E Z for E U and B S ((ssa)] Be for < E Z, where BE.L E (0,2/(2 + Bz)) and Br, 2 2/(2 Bz). Let B = max(BBgu. B Then, returned by Algorithm 4 achieves
B, + Bu + (1 + B, + BB + 1))BB (1-7)3
log (4 M (2)/))
-(F)) S
N
8

---

Published as a conference paper at ICLR 2023
Algorithm 4 ALM with MIS (ALMIS) for offline RL- Model-free
1: Inputs: Datasets D, Do. function classes W, V,u,,, (x(2) - I 2 z.
-
2: Find solution wē, Ú, û, maX min min max LAL L (w, v, u, () defined as
No
N
(1-7)
Σ u(s)) + Σ u(si, a)T +
Σ
w088, az) [ro 70(6)) - v(s:)
No
N
1=1
(15)
+ +((s), (((s)) a.) y
Σ d'EA
(m gr(((s,, aill
3: Return: ==
In Theorem 4, we make realizability assumptions on whe for w E W and Cw for u E U. Such assumptions are common in theory of RL with function approximation (Munos & Szepesvári, 2008; Xie et al., 2021; Jiang & Huang, 2020) and removing them can be difficult or impossible (Foster al., 2021). Recently, Zhan al. (2022); Chen & Jiang (2022) propose algorithms that only require optimal solution realizability, however, these algorithms are either intractable or suboptimal.
5.3 EXAMPLE: BEHAVIOR REGULARIZATIO VS. AUGMENTED LAGRANGIAN
We examine the MDP example in Figure presented by Zhan et al. (2022). Assume V = { and W = {wr, w2), where wi always selects I from A and wy always selects R from A. One can check w1 (A, L) = 2, w1 (A, R)- = and (2 L) = 0, wy (A, R) =
A
B
Unregularized algorithm. As Zhan al. (2022) state, the unregu- larized algorithm fails to distinguish between w1 and W2 even with infinite data as the objectives w1 and Wy are exactly equal.
+0
+1
+1
Behavior regularization. Consider an instantiation of PRO- RL with regularizer -oE,, (s, a)]. Since in this example E, [wf a)] > [,[ws(s, a)). PRO-RL picks the wrong weight W2, suffering constant suboptimality. Note, however, that PRO- RL guarantees assume T ct-coneentrability Intuitively, behavior regularization causes ,,, to be more stochastic and thus requiring u(s.a) a) > 0 for more states and actions. Here, since μ covers both (A, and (A, R), behavior regularization causes T. (R) A) > O and thus d= (C) > O. To handle the MDP in Figure 1, PRO-RL additionally requires u(C)) > 0 to satisfy rf-coonentrrbbiitt.
+0
Figure 1: The agent starts from A. Action L leads to B, from where the agent collects +1 reward. Action It leads to C, from where only one action leads to a +1 reward. Nature decides which MDP is presented to the learner. Data distribution is μ(A, L.) = 1/4, μ A, R) 1/2,, pa (B = 1/4, (C() = O. which satis- fies Tw, -concentrability.
ALM. In this example, ALM successfully picks the optimal w1, as avoids mismatch between the actual and learned occupancies. This is because in (10) the ALM term is zero at due to realiz- ability whereas at W2, it has a lower bound Eg-dra (dw, (C)) (C) - 1)² (C) 0.
DISCUSSION
We present set of practical and statistically optimal algorithms for offline MAB, CB, and RL, un- der general function approximation and single-policy concentrability. Our algorithms are designed within the MIS formulation combined with novel application of augmented Lagrangian method. Importantly, our optimality guarantees hold under MIS combined with ALM alone, without any ad- ditional form of conservatism such as via regularization or uncertainty quantification. Furthermore, we investigate the role of regularizers in MIS algorithms. Although the empirical benefits of such regularizers are often attributed to conservatism, our analysis suggests that conservatism stems from the MIS formulation while the role of regularizers is to ensure the validity of learned occupancy. Interesting future directions include conducting empirical evaluations of ALM, examining the pos- sibility of removing strong realizability assumptions, and investigating practical and optimal offline RL algorithms whose guarantees hold under milder variants of aagle-policy concentrability more suited to function approximation.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
The authors are grateful to Amy Zhang and Yuandong Tian. This work occurred under Meta Al- BAIR Commons at the University of California, Berkeley, and is partially supported by NSF Grants 19S1120125 and CCF-1909499 PR is supported by the Open Philanthropy Foundation. Part of the work was done when HZ was a visiting researcher at Meta.
REFERENCES
Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. An optimistic perspective offline reinforcement learning. International Conference on Machine Learning, pp. 104-114 PMLR, 2020.
Andras Antos, Rémi Munos, and Csaba Szepesvari. Fitted Q-iteration in continuous action-space mdps. In Neural Information Processing Systems, 2007.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with Bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71(1):89-11 12999 2008.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pp. 30-37. Elsevier, 1995.
Aharon Ben-Tal Tal and Arkadi Nemirovski. Lecture notes optimization III: Convex analysis, Non- linear programming theory, Non-linear programming algorithms, 2022.
Jinglin Chen and Nan Jiang. Information -theorettc considerations in batch reinforcement learning. 2019.
arXiv preprint
Jinglin Chen and Nan Jiang. Offline reinforcement learning under value and density-ratio realiz- ability: The power of gaps. In The 38th Conference on Uncertainty in Artificial Intelligence, 2022.
Ching-An Cheng, Tengyang Xie, Nan Jiang, and Alekh Agarwal. Adversarially trained actor critic for offline reinforcement learning. In Proceedings of the 39th International Conference on Ma- chine Learning, volume 162, 2022.
Bo Dai, Niao He, Yunpeng Pan, Byron Boots, and Le Song. Learning from conditional distributions via dual embeddings. In Artificial Intelligence and Statistics, pp. 1458-1467. PMLR, 2017.
Jonas Degrave, Federico Felici, Jonas Buchli, Michael Neunert, Brendan Tracey, Francesco Carpanese, Timo Ewalds, Roland Hafner, Abbas Abdolmaleki, Diego de Las Casas, et al. Mag- netic control of tokamak plasmas through deep reinforcement learning. Nature, 602(7897):414- 419, 2022.
Simon S Du, Sham M Kakade, Ruosong Wang, and Lin F Yang. Is good representation sufficient for sample efficient reinforcement learning? In International Conference on Learning Represen- tations, 2019.
Amir Massoud Farahmand, Rémi Munos, and Csaba Szepesvári. Error propagation for approximate policy and value iteration. Advances in Neural Information Processing Systems, 2010.
Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes, Moham- madamin Barekatain, Alexander Novikov, Francisco J R Ruiz, Julian Schrittwiseer, Grzegorz Swirszez, et al. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 6 61457330 2022.
Yihao Feng, Lihong Li, and Qiang Liu. kernel loss for solving the Bellman equation. arXiv preprint arxiv:9905. 10506, 2019.
Dylan Foster, Akshay Krishnamurthy, David Simchi-Levi, and Yunzong Xu. Offline rein- forcement learning: Fundamental barriers for value function approximation. arXiv preprint arXiv:2111.10919 2021.
10

---

Published as a conference paper at ICLR 2023
Scott Fujimoto and Shixiang Shane Gu. A minimalist approach offline reinforcement learning. Advances in neural information processing systems, 14-20332-20145 2021.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. International Conference on Machine Learning, pp. 2052-2062. PMLR, 2019.
Seyed Kamyar Seyed Ghasemipour, Dale Schuurmans, and Shixiang Shane Gu. EMaQ: Expected- max Q-learning operator for simple yet effective offline and online RL. arXiv preprint arXiv:2007.11091, 2020.
Kaiyang Guo, Yunfeng Shao, and Yanhui Geng. Model-based offline reinforcement learning with pessimism-modulate dynamics belief. arXiv preprint 2rXiv:220000600 2022.
Jeff Hong, Weiwei Fan, and Jun Luo. Review on ranking and selection: A new perspective. Frontiers of Engineering Management, 8(3):311-34,, 2021.
Natasha Jaques, Asma Ghandeharioun, Judy Hanwen Shen, Craig Ferguson, Agata Lapedriza, Noah Jones, Shixiang Gu, and Rosalind Picard. Way off-policy batch deep reinforcement learning of implicit human preferences in dialog. arXiv preprint arXiv:1907.00 0044000456, 2019.
Nan Jiang. On value functions and the agent-environment boundary. arXiv: 1ea.i 2019.
arXiv preprint
Nan Jiang and Jiawei Huang. Minimax value interval for off-policy evaluation and policy optimiza- tion. Advances in Neural Information Processing Systems, 33, 2020.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline RL? In International Conference Machine Learning, pp. 5084-5096. PMLR, 2021.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In ICML, volume 2, pp. 267-274, 2002.
Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims. MOReL: Model- based offline reinforcement learning. arXiv preprint a0Xiv:2005.05551, 2020.
lya Kostrikov, Rob Fergus, Jonathan Tompson, and Ofir Nachum. Offline reinforcement learning with Fisher divergence critic regularization. In International Conference on Machine Learning, pp. 5774-5783. PMLR, 2021.
Aviral Kumar, Justin Fu, George Tucker, and Sergey Levine. Stabilizing off-policy Q-learning via bootstrapping error reduction. arXiv preprint 1iXivv:906.000 00949, 2019.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative Q-learning for offline reinforcement learning. arXiv preprint arXiv:2006. 04779, 2020.
Aviral Kumar, Jocy Hong. Anikait Singh, and Sergey Levine. Should I run offline reinforcement learning behavioral cloning? In International Conference Learning Representations, 2021.
Sascha I Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In Reinforce- ment learning, pp. 45-73. Springer, 2012.
Jongmin Lee, Wonseok Jeon, Byungjun Lee, Joelle Pineau, and Kee-Eung Kim. OptiDICE: Offline policy optimization via stationary distribution correction estimation. In International Conference on Machine Learning, pp. 6120-6130. PMLR, 2021.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tuto- rial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643 2020.
Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Settling the sample complexity of masel-based offline reinforcement learning. arXiv preprint arXiv:2004.0527,, 2022.
Peng Liao. Zhengling Qi. and Susan Murphy. Batch policy learning in average reward Markov decision processes. arXiv preprint 1771 2020.

---

Published as a conference paper at ICLR 2023
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural trust region/proximal policy optimiza- tion attains globally optimal policy. In Neural Information Processing Systems, 2019a.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite- horizon off-policy estimation. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 5361-5371, 2018.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Off-policy policy gradient with state distribution correction. arXiv preprint arXiv: 08473, 2019b.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch reinforce- ment learning without great exploration. arXiv preprint arXiv:2007.08202 2020.
Jifí Matoušek and Jan Vondrák. The probabilistic method. Lecture Notes, Department of Applied Mathematics, Charles University, Prague, 2001.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforeement learning. Nature, 518(7540):529-533 2015.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508-513) 2017.
Rémi Munos. Performance bounds in f,-norm for approximate value iteration. SIAM journal on control and optimization, 46(2):541-566 -511, 2007.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008.
Ofir Nachum and Bo Dai. Reinforcement learning via Fenchel-Rockafeller duality. arXiv preprint arXiv:2001.01866, 2020.
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. DualDICE: Behavior-agnostic estimation of discounted stationary distribution corrections. In Advances in Neural Information Processing Systems, pp. 2315-2325, 2019a.
Ofir Nachum, Bo Dai, Ilya Kostrikov, Yinlam Chow, Lihong Li, and Dale Schuurmans. AlgaeDICE: Policy gradient from arbitrary experience. arXiv preprint arXiv:19/2.02077 2019b.
Ashvin Nair, Murtaza Dalal, Abhishek Gupta, and Sergey Levine. Accelerating online reinforcement learning with offline datasets. arXiv preprint (XXx:20006093599) 2020.
XuanLong Nguyen, Martin J Wainwright, and Michael Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions Information Theory, 56(11):5847-5811 2010.
Xue Bin Peng, Aviral Kumar, Grace Zhang, and Sergey Levine. advantage-weightee regression: Simple and scalable off-policy reinforcement learning. arXiv preprint 1rXiv:1910.00117,, 2019.
Martin I. Puterman. Markov Decision Processes: Discrete Stochustic Dynamic Programming. John Wiley Sons, 2014.
Tabish Rashid, Bei Peng, Wendelin Boehmer, and Shimon Whiteson. Optimistic exploration even with a pessimistic initialisation. In International Conference on Learning Representationss 2019.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34:1 11:11700-11116 2021.
Shideh Rezacifar, Robert Dadashi. Nino Vieillard, Léonard Hussenot. Olivier Bachem, Olivier Pietquin, and Matthieu Geist. Offline reinforcement learning as anti-exploration. In Proceed- ings of the AAAI Conference Artificial Intelligence, pp. 8106-8114, 2022.
12

---

Published as a conference paper at ICLR 2023
Mare Rigter, Bruno Lacerda, and Nick Hawes. RAMBO-RI RL: Robust adversarial model- offline reinforcement learning. arXiv preprint arXiv:2204. 12581, 2022.
Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
Stephane Ross and J Andrew Bagnell. Reinforcement and imitation learning via interactive no-regret learning. arXiv preprint
2014.
Bruno Scherrer. Approximate policy iteration schemes: comparison. In International Conference Machine Learning, pp. 1314-1322, 2014.
Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczynski. Lectures on Stochastic Program- ming: Modeling and Theory. SIAM, 2021.
Laixi Shi and Yuejie Chi. Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity. arXiv preprint arXiv:2208.05700 2022.
Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Pessimistic Q-learning for offline reinforcement learning: Towards optimal sample complexity. arXiv preprint urXiv:2202. 13890, 2022.
Noah Y Siegel, Jost Tobias Springenberg, Felix Berkenkamp, Abbas Abdolmaleki. Michael Ne- unert, Thomas Lampe, Roland Hafner, and Martin Riedmiller. Keep doing what worked: Be- havioral modelling priors for offline reinforcement learning. arXiv preprint arXiv:2002.08396, 2020.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, al. Mastering the game of Go without human knowledge. Nature, 550(7676):354-335 359, 2017.
Yuda Song, Yifci Zhou, Ayush Sekhari, J Andrew Bagnell, Akshay Krishnamurthy, and Wen Sun. Hybrid RL: Using both offline and online data make RL efficient. arXiv preprint arXiv:2210.067118 2022.
Adith Swaminathan and Thorsten Joachims. Batch learning from logged bandit feedback through counterfactual risk minimization. The Journal of Machine Learning Research, 16(1):1331-1755, 2015.
Csaba Szepesvári and Rémi Munos. Finite time bounds for sampling based fitted value iteration. In Proceedings of the 22nd international conference on Machine learning, pp. 880-887, 2005.
Guy Temnenholtz, Nir Baram, and Shie Mannor. Latent geodesics of model dynamics for offline reinforcement learning. In Deep RL Workshop NeurIPS 2021, 2021.
Masatoshi Uchara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. In International Conference Learning Representations, 2021.
Masatoshi Uehara, Jiawei Huang, and Nan Jiang. Minimax weight and Q-function learning for off- policy evaluation. In International Conference on Machine Learning. pp. 9659-9668. PMLR, 2020.
Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline RL in low-rank MDPs. arXiv preprint arXiv:2110.04632, 2021.
Sara Van de Geer. Empirical Processes in M-estimation, volume Cambridge university press, 2000.
Oriol Vinyals, Timo Ewalds. Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets, Michelle Yeo, Alireza Makhzani. Heinrich Küttter, John Agapiou, Julian Schrittwieser, et al. Stareraft II: A new challenge for reinforcement learning. arXiv preprint /708 2017.
Lingxiao Wang. Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. In International Conference on Learning Representationss 2019.
13

---

Published as a conference paper at ICLR 2023
Ruosong Wang. Dean P Foster, and Sham M Kakade. What are the statistical limits of offline RL with linear function approximation? arXiv preprint arXi::0100.1895, 2020.
Xinqi Wang, Qiwen Cui, and Simon $ Du. On gap-dependent bounds for offline reinforcement learning, arXiv preprint arXiv:2206.00/1 2022.
Yuanhao Wang, Ruosong Wang, and Sham Kakade. An exponential lower bound for linearly realiz- able MDP with constant suboptimality gap. Advances in Neural Information Processing Systems, 34:9521 -9333, 2021.
Gellért Weisz, Philip Amortila, and Csaba Szepesvári. Exponential lower bounds for planning in MDPs with pp. 1237-1264. PMLR, 2021.
optimal action-value functions. In Algorithmic Learning Theory,
Yifan Wu, George Tucker, and Ofir Nachum. Behavior regularized offline reinforcement learning. arXiv preprint arXiv: /9/1.1 1361, 2019.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. In Inter- national Conference on Machine Learning, pp. 11404-11413, PMLR, 2021.
Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. Towards optimal off- off-policy evaluation for rein- forcement learning with marginalized importance sampling. Advances Neural Information Processing Systems, 32, 2019.
Tengyang Xie, Ching-An An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consister pessimism for offline reinforcement learning. Advances neural information processing systems, 34:6683-6694, 2021.
Yuling Yan, Gen Li, Yuxin Chen, and Jianqing Fan. The efficacy of pessimism in asynchronous Q-learning, arXiv preprint arXiv:2203.071 073668 2022.
Mengjiao Yang. Ofir Nachum, Bo Dai, Lihong Li, and Dale Schuurmans. Off-policy evaluation via the regularized Lagrangian. Advances Neural Information Processing Systems, 33:6551-65611 2020.
Ming Yin and Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pes- simism. Advances in neural information processing systems, 34:4065 4078, 2021.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal offline reinforcement learning via double variance reduction. arXiv preprini arXiv:2102.01748, 2021.
Ming Yin, Yaqi Duan, Mengdi Wang, and Yu-Xiang Wang. Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism. arXiv preprint Xiv::2033005800 2022.
Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. MOPO: Model-based offline policy optimization. arXiv preprint arXiv:2005. 13239, 2020.
Tianhe Yu, Aviral Kumar, Rafacl Rafailov, Aravind Rajeswaran, Sergey Levine, and Chelsea Finn. COMBO: Conservative offline model-based policy optimization. arXiv preprint arXiv:2102.08363, 2021.
Andrea Zanette. Exponential lower bounds for batch reinforcement learning: Batch RL can be exponentially harder than online RL. In International Conference on Machine Learning, pp. 12287-12297. PMLR, 2021.
Andrea Zanette, Martin J Wainwright, and Emma Brunskill. Provable benefits of actor-critic meth- ods for offline reinforcement learning. Advances in neural information processing systems, 34: 13626-13640, 2021.
Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and single-policy concentrability. In Conference on Learning Theory, pp. 2730-2775. PMLR, 2022.
14

---

Published as a conference paper at ICLR 2023
Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Varia- tional policy gradient method for reinforcement learning with general utilities. arXiv preprint arXiv:2007.02151, 2020a.
Ruiyi Zhang, Bo Dai, Lihong Li, and Dale Schuurmans. GenDICE: Generalized offline estimation of stationary values. In International Conference on Learning Representations, 2020b.
Shantong Zhang. Bo Liu, and Shimon Whiteson. GradienDDICE: Rethinking generalized offline estimation of stationary values. arXiv preprint arXiv:2001.11113. 2020c.
Xuezhou Zhang, Yiding Chen, Xiaojin Zhu, and Wen Sun. Corruption- cobuust offline reinforcement learning. In International Conference Artificial Intelligence and Statistics, pp. 5757-5773. PMLR, 2022.
15

---

Published as a conference paper at ICLR 2023
A
RESULTS SUMMARY
Table 1: Summary of suboptimality bounds on the MIS objective with different added terms.
Setting
Algorithm
Added term
Concentrability
Suhoptimality
MAB
Unregularized MIS
single-policy x²
((1) (Proposition
MIS + hehavior reg.
((,o(((((
twa-policy nt,
(Theorem
(Algorithm 5)
(a 1/VN)
VX
MIS + ALM
[En[w(a) - 1)2
single-policy x
(Theorem 2)
(Algorithm 1)
MIS + hehavior reg.
CB
twa-policy n², m
2 22 (Proposition 3)
(Algurithm 6)
(a 20)
MIS + ALM
B Ca wis, a)p((a/s) > - 1)²
single-policy x
(Theorem 3)
(Algurithm 2)
MIS + ALM
du(a) [T -1)
MDP
Er
single-policy n²*
(Theorem
(Algorithms 3, 4)
B RELATED WORK
We covered a number of related works in the introduction and throughout the paper. In this section, review more related literature.
B. CONCENTRABILITY ASSUMPTIONS
The lack of sufficient coverage in the offline dataset is one of the main challenges in offline RL. In RI. theory, dataset coverage has often been characterized by concentrability definitions (Munos, 2007; Scherrer, 2014). Earlier works offline RL impose all-policy concentrability on the density ratio for all states and actions (Scherrer, 2014; Liu et al., 2019a; Chen & Jiang, 2019; Jiang, 2019; Wang et al., 2019; Liao al., 2020; Zhang al., 2020a), with some requiring this ratio to be bounded for every time step (Szepesvári & Munos, 2005; Munos, 2007; Antos et al., 2008; Farahmand et al., 2010; Antos al., 2007). The works Xie & Jiang (2021); Feng al. (2019); Uehara al. (2020) use slightly milder definitions, such as requiring a bound on a weighted norm of density ratios. The work Xie & Jiang (2021) makes even stronger assumptions such as lower bounded conditionals u(als) and exploratoriness of state marginals to circumvent the Bellman completeness requirement.
To handle partial coverage, recent algorithms are analyzed based on variants of single-policy con- centrability (Rashidinejad et al., 1021). Some variants such as the ones presented in works Uehara & Sun (2021) pmoodel-basedi or Xie al. (2021); Song et al. (2022) (model-free) are more suited to function approximation they avoid bounded ratio assumption for all states and actions. How- ever, existing offline RL algorithms based on these weaker definitions are either computationally intractable (Uchara & Sun, 2021; Xie et al., 2021) their statistical rate is suboptimal (Cheng al., 2022). The most related works are Zhan et al. (2022), which requires two-policy concentrability, and Chen & Jiang (2022), which requires single-policy concentrability density ratio for all states and actions.
B.2 CONSERVATIVE OFFLINE RL
series of recent works on offline RL have focused on addressing partial coverage of offline dataset through conservative algorithm design. Broadly speaking, these methods can be broken down into several categories. The first category of methods applies policy constraints, enforcing the learned policy to be close to the behavior policy. Such constraints
applied either explicitly (Fujimoto et al., 2019; Ghasemipour et al., 2020; Jaques et al., 2019; Siegel et al., 2020; Kumar et al., 2019; Wu et al., 2019; Fujimoto & Gu, 2021), implicitly (Peng et al., 2019; Nair et al., 2020), through importance sampling (Liu et al., 2019b; Swaminathan & Joachims, 2015; Nachum et al., 2019b; Lee al., 2021; Zhang et al., 2020c:b). Another category involves learning conservative values
16

---

Published as a conference paper at ICLR 2023
such conservative Q-learning (Kumar et al., 2020), fitted Q-iteration with conservative update (Liu et al., 2020), subtracting penalties (Rezaeifar et al., 2022), and critic regularization (Kostrikov et al., 2021). The last category includes model-based methods such as learning pessimistic models (Kidambi et al., 2020; Guo et al., 2022), adversarial model learning (Rigter et al., 2022), forming penalties using model ensembles (Yu et al., 2020), or incorporating combination of model and values (Yu et al., 2021).
On the theoretical side, as discussed in the introduction, the majority of works design pessimistic offline RL algorithms that rely on some form of uncertainty quantification (Yin & Wang, 2021; Ue- hara et al., 2021; Zhang al., 2022: Yan et al., 2022; Yin et al., 2022; Kumar et al., 2021; Shi & Chi, 2022: Wang et al., 2022). One exception is the work of Zanette et al. (2021) that uses perturbation with actor-critic in linear function approximation setting. Other examples include the recent theoretical works on MIS (Zhan et al., 2022; Chen & Jiang, 2022) and adversarially trained actor-critic (Cheng et al., 2022).
Most related to our work are methods that focus on provable conservative offline RL under general function approximation and partial coverage, summarized under the pessimistic algorithms segment of Table B.2. Uehara & Sun (2021) propose a pessimistic model-base algorithm that under generalization of single-policy concentrability to bounded TV distance ratio, enjoys a 1/vN rate but is computationally intractable. The work of Xie et al. (2021) presents a pessimistic model- free algorithm under variant of single-policy concentrability framework that requires bounded ratio of average Bellman error and Bellman completeness. While the original version of the algo- rithm achieves the optimal 1/vN rate, it is computationally intractable. practical version of the algorithm is presented and has a suboptimal 1/N1/5 guarantee. Another related work by Chen & Jiang (2022) studies MIS combined with value function approximation under x² -concentrabillity and proves 1 1/v //V/gp(("') ( rate, yet the guarantee degrades with Q' gap and the algorithm is compu- tationally intractable. Cheng et al. (2022) propose an adversarially trained actor-critic method that enjoys provable 1 1/3 rate under the single-policy concentrability definition of Xie et al. (2021) and Bellman completeness and performs well in offline RL benchmarks when combined with deep neural networks.
Table 2: Comparison of provable offline RL algorithms with general function approximation.
Algorithm
Computation
Uncertainty
Assumption
Coverage
Unbiased
Suhoptimality
Uniform coverage algorithms
Munos & Szepesvári (2008)
Efficient
N/A
Completeness
pol-policy
Yes
0
JN
Antos et al. (2008)
Efficient
N/A
Completeness
all-policy
Yes
0
vW
Pessimistic algorithms
Xie al. (2021)
Intractable
Required
Completeness
single-policy
Yes
0
+
Uehara & Sun (2021)
Intractable
Required
Completeness
single-poliy,
Yes
0
VN
Chen & Jiang (2022)
Intractable
Required
Realizability only
single-policy
Yes
0
Zhan et (20122
Efficient
Realizahility only
two-policy
0 (yim)
Cheng et al. (2022)
Efficient
No
Completeness
single-policy
No
0 ( (xt)
ALMIS (this work)
Efficient
No
Completeness
Angle-poliy
Yes
0 (VN
B.3
OTHER TOPICS
Apart from RL, our work on bandits is related to the selection problem (Hong et al., 2021), though the majority of works in this area are in the online setting. Additionally, in our analysis, we solve a subset of stochastic optimization problems with possibly large or infinite stochastic constraints involving conditional expectations. To our knowledge, finite-sample properties of such stochastic optimization problems have not been addressed (Shapiro et al., 2021) and our work may open up avenues for further research in this area.
17

---

Published as a conference paper at ICLR 2023
C SUPPLEMENTARY MATERIALS FOR MULTI-ARMED BANDITS
We start by presenting a pseudocode for the behavior regularized MIS algorithm in Appendix C.I. In Appendix C.2, we characterize the bias caused by adding the behavior regularization in the primal- dual objective (2). In Appendix C.3, we prove Proposition that demonstrates the failure of unregu- larized MIS for solving offline MABs, even when the optimal solutions are realizable and optimal policy is covered in the offline data. Appendix C.4 is devoted to the proof of Theorem 1, which gives tight performance upper bound of the PRO-MAB algorithm. Finally in Appendix C.5, we prove Proposition 2, showing that constraint satisfaction is sufficient for the success of unregularized MIS.
C.I PRIMAL-DUAL REGULARIZED OFFLINE MULTI-ARMED BANDITS (PRO-MAB)
Algorithm Primal-dual Regularized Offline Multi-Armed Bandits (PRO-MAB)
1: Inputs: Dataset D {aa; r.) )== classes V [-B,, Bu] and W, function f(-), parameter a. Find solution w, i to the following problem
2:
1 Σ w(a.)r; - af(w(a;)) v(w(a;) - 1).
max min f.MAB (w, v) = N NEW vEV
(16)
3: Return: #(a) = (a)p(a) E. w(a)n(a)
if E. w(a)m(a) > 0. and 1
[ otherwise.
C.2 SOLUTIONS THE PRIMAL-DUAL REGULARIZED OBJECTIVE
In the following lemma, we characterize the optimal solution (wa, v²) to the behavior-regularizee population objective (2) as well as the suboptimality of the policy induced by w
Lemma (Regularized primal-dual solutions, MAB) Let I be difserentiable, strictly convex, nonnegative, and bounded by B-- Denote r² == max.EA r(a). Then, the following statements hold:
(I) w/ w", where wn is the importance weight corresponding optimal policy; (II) va x* co2, where 0 S ('('):
(III) policy n. == Twg satisfies J( ( S aBy
Proof. Part (I) follows directly by strong duality. For part (II), notice that KKT conditions imply the following relation between w (a) and :
" (a) max (o. ((()) (
(00)0(())--0000 va
Since is strictly convex, f is monotonically increasing function. Therefore, the optimal arm at has the largest w (a), which should be nonzero due to realizability of w,, In other words,
" (a") (f')-1 ("
a =2(6)
via = al (a"()))
(17)
We now proceed to find bound on ('(w)(a*)) Since w is the optimal solution to (2), it must satisfy the constraint
Σ aEA
= (taaa))
p(a*) SC.
where the last inequality stems from the songle-policy concentrability assumption of x*. Since f increasing function, we have (((w((a)) < (C')), which combined with (17) yields the following lower bound on v
3 -d aC
18

---

Published as a conference paper at ICLR 2023
Moreover, the convexity of f immediately gives the upper bound on va S r*, which completes the proof part (II).
We now prove the last part. Since wa is the optimal solution to the regularized population objective (2), by strong duality, we have
Eandw; [r(a)] a.aa (w (a))) 2 Easa [r(a)] -
where dmy: (a) u(a)ucz (a) by definition given in Section and we used the fact that Beanal [wi (a) -1 Baaayll (10" (a)] - 0. Therefore, the suboptimality of n can be bounded as follows
J(x²) - J(Ta) = Eard [r(a)] - Eandw; [r(a)]
I aBa If(w" (a)) |- ([
I al aBarhl (w" (a)) S af(C*) S aBy,
where the second to last inequality we used the non-negativity of f and in the last equality, we used the boundedness of f.
C.3 PROOF PROPOSITION
Consider 2-armed bandit instance with the following reward distributions, data distribution, and function classes
Reward distributions: The first arm is optimal with deterministic reward and the second arm has Bernoulli distribution:
((1)
w.p.
r(2) Bernoull((/33).
Data distribution: We consider scenario where most data are concentrated the optimal arm:
((1) = N ((2) = N
Here, the single-policy concentrability coefficient is C* = (1) and is finite for N 2. Let (a) denote the number of samples on arm a. To obtain upper and lower bounds on (a), we resort the following lemma, which is direct consequence of the Chernoff bound for binomial variables.
Lemma 2 (Chernoff bounds, binomial)
(I) With probability at least 1 cxp(-Nu(a)03/e + 8w)), one has N(a) I (1 + N,(a)(()) for any d, > O;
(II) With probability at least 1 - 1i-eepp-NN((j)) /2), one has (1 (1- (1) & (a) any d1
We condition on the event that the number of samples on the second arm is between and
which occurs with probability larger than - exp - 0.9²)
exp (-2 1.95+2
1.95²
2 0.4
due to Lemma 2 when setting 6; 0.9 and 6,, = 1.95:
(1 0.9) N2(2) S (2) < (1 + 1.95) N2)2) # 1 1 55
Function classes: Assume that W = {wi = (C*, W2 = (0. Bw)) and V (1/2). By Lemma 1, have og p² 1/2. Therefore, the problem is realizable as V/ E and w = w = (C*.0) E W. Furthermore, notice that for the second candidate Wa (0, B.) E W. the normalization factor is small for constant B, as dmng = E. W2 (2)))((a) = 2B./N.
Consider the case where all N(a) samples on the second arm observe reward of 1, which happens with probability of at least z5 conditioned on the event that N((2 & 5. We now compute
19

---

(22 Published as a conference paper at ICLR 2023
w by solving the empirical objective (16) with 0. Note that since M/ 1, it suffices compute vi arg wax M.MAB (w, 1/2). We have
MAA (wi, 1/2) (1)
1
(2)) 1
C*
(C* - 1)
+
N
2
2
2N
2
N(1)
(2)
1 (Be - 11
1 +
MMA (w2, 1/2) 2N
B
N
2
2
2N
Since we conditioned on the event with N(2) 2 1, solving the optimization problem
max (W, 1/2) finds w = (0, Bw), ). leading to a policy that picks the second arm with probability one. Therefore, with constant probability of 0.4 1/3 0.001, have
-
J(t)) 3 6
C.4 PROOF OF THEOREM 1
Before embarking on the main proof, we present two lemmas related the primal-dual regularized approach. The first lemma shows the closeness of population objective (2) to its empirical approx- imation used in Algorithm I, which is a direct consequence of Hoeffding's inequality. We also show that closeness of objectives results in the closeness of w and w, which are respectively the optimums to (2) and (16). The proof this lemma is deferred to end of this subsection.
Lemma (Empirical and population closeness, PRO-MAB) Fix 8 > 0 and define
MAR Sstar = ((B, + 1) + 1) aBi +Ba)) log
W1///
(18)
N
For any w E W and v E V. the following bounds hold with probability at least
MAB (I) T, MAB (w,, U) - i, MAB (w, 5)|5 e stat,ac'
(II) MAB (w v) MAB (w, v) < 2E
The second lemma finds lower bound on the occupancy normalization factor da = Ea (aa)((()) enforced by the behavior regularization.
Lemma 4 (Occupancy validity enforced by behavior regularization) Let f be M--strongly- convex and fix Then, with probability at least ô, one has
MAR
dg 2
aM,
where Stat, is defined in (18).
For the rest of this proof, we condition on the high probability events of Lemmas 3 and 4. Define
CD Σ n (a)((((()r(a)) vi(a)u(a)r(a).
(19)
By part (II) of Lemma 3, we have MA (v wx) I,MBB (w; w) < MAB Therefore, stat,o
6,.r aBylS(1 (a)) ((((()))) "/ (di 1) 2c MAB stat,a
(20)
Recall from Lemma that we have V = ac, where < fC(C)). Thus, combined with (20), we write
6 + r (do - 1) 5 2e MAB
(f - ((ú(a))) + ac(da - -1)
stat
2 star,o
+ a2B + (C"((")
(21)
where in the second line used the bounds [f(x)|5 B, and d. < B.- Note that setting 16c MAB My, Lemma 4 asserts that d. 2 1/2. Since du 1/2, the learned policy is written as
20

---

Published as a conference paper at ICLR 2023
= (())u(a)/da With simple algebraic manipulations, find the following expression for the suboptimality of with respect to :
(( - ((z) Σ (a(l))((ar(aa) - d
(())((a)r(a))
Σ (ol(o)((arraa) - ((a)(()r(a)))) (11-2))
cop ( u a(a))(a)((a)
cùr + (dg 1) E di
((a)u(a)r(a)
Cür + (dg - 1) (
Cär + (dg - 1) [( ()) J()).
Let Erog = - = - ((Ta) denote the suboptimality suffered due to behavior regular-
ization. Suboptimality J ( (ft) can be expressed
1
J(xa)) J(A)
(nrrr + (dia I(ra))
d (curr + (di -1) (r* -(re))
1
S du
(earr + (dio - -11 1)r*)
(dh-1)) 1) ereg
dui
We the above inequality bound the suboptimality with respect an optimal policy:
J(x)) ((t) ((xx(( (( + ((= ((F)
Esog + (( - J(ā)
S <reg + da
(Krir + (dhi - -1)r*)
(di
1) creg
di
1 (errr + (dhi - 1)r")== + di
du
Ereg-
Recall that we have 1/d,. S and that Geg is bounded by aB by Lemma 1. Therefore,
J(TT) ((t) - (Ewrr + (dá - 1))*) +
Ereg
di
dip
s 2 (Ew.r r + (du - 11)r") 2aBB
< 4e 4e + a(AB, + (C')) + 2aB,
S aB + Bw))
where the penultimate inequality relies on the bound derived (21).
Proof of Lemma 3. ĪMAR (w, v) an empirical average over independent and bounded random variables, where the bound individual variables is computed
w(aa)): - aw(()) v(w(a,) 1)1 s B + aB, + B. +1) S (Bw + L)(B, + 1) - aBy.
It is easy to see that Ep Ep MAB (w, v)] MAB (w, v), where the expectation is taken with respect to the randomness in dataset D. Part (I) of this lemma is proved by applying Hoeffding's inequality along with union bound on and v.
The proof of part (II) is similar to Lemma 7 of Zhan al. (2022) and relies on decomposing the objective difference and using the fact that (w), 0) correspond the saddle points of I, MAB and MAB For any W. define
Pu = arg min Í.B vEV
(w, v)
(22)
21

---

Published as a conference paper at ICLR 2023
We write
L
MAB (war v) - -La LMAB LA 0)
La
MAB
(war v)
MAB
(w Dws + La MAB (war ows)) ) LMABB (w Owy
=-1
==
+ La
MAB
(wa Owg
-.MB (v0, 0)+ + MAB (w0 0) M.M (eo, v)
T=Ts + MAB (w, v)
T
La (ri, v).
Each term is bounded as follows:
Ti because w, satisfies the constraint Ea wx (a)u((a and for any vi, U2 have
I. MAB (wa: v1) T.MAB (wa,?2). 12).
T2 S éstar due to Lemma 3.
Ty S because ú arg max EW (0w, w).
T4 S O because i = arg min.ev L MAB (u, 1)).
T3 S Gaa due Lemma
Summing up the bounds on each term yields the desired bound.
Proof of Lemma 4. This lemma is a direct consequence of Lemma 8 in Zhan et al. (2022). For completeness, we present a simplified proof for the multi-armed bandit setting.
First, observe that since f is My-strongly-commers the function LA (va, concave with respect and norm I1-12,,.. Furthermore, since w arg max, LMAB (v* w), we have
LMAB(1a w) is aM AMM-strongly
(W,, 2 2(L (w 1z) - LMAB (MA v;
|| 12
aM1
The above bound along with the bound on L Lemma 1, give following bound on |dw- -1
LAB L Un) - MAB (w, vn)) S
MAB
showed in
MAB a.My
do - 1 Σ (a))((a)) - E Emz(a)m(a) S $1100 wall 11 11:0 wal 2,
which completes the proof.
C.5 PROOF OF PROPOSITION 2
Consider the difference between population objective with a = 0 at wiz = wn and úh which is bounded by Lemma 3:
L(w", ,²*) L(w, v*) (ra))r(()(w")))))) (a) w(a))] - v En-p (w (w) - w(a)) MAB
(23)
stataa
We have Egrz [w* [a)] = 1 due to realizability and Ea~u[(ú()) the second term in (23) zero. Moreover, note that (())
1 is our assumption. Thus (ull))//Euullllaa
(a)).
Substituting the expression for saat from (18) with a O. we obtain
logl VI|Wi/S
J Bo-alr(a)( v(aa)) S (B, +1)
N
where we used the fact that B., x B + since B.. > 1 due to realizability of w*.
D PROOFS FOR CONTEXTUAL BANDITS
This section of the appendix is organized as follows. In Appendix D.I, we present details of the PRO-CB algorithm. Appendix D.2 is devoted to the proof of Proposition which shows that the PRO-CB algorithm fails to achieve the statistically optimal rate of 1/ //N. The proof of subopti- mality upper bound for the conservative offline CB algorithm with ALM is presented Theorem 3.
22

---

Published as a conference paper at ICLR 2023
D.1 PRIMAL-DUAL REGULARIZED OFFLINE CONTEXTUAL BANDITS (PRO-CB)
Define importance weights wiss, d(s, p(p, a) to denote the ratio occupancy and data dis- tribution. The primal-dual regularized approach (Zhan et al., 2022) solves the following population objective
max min T. (w, v) Ba (olss, a)r(s, a)] E (Vs)) 1)] aB (f (w(x,
(24)
The above optimization problem satisfies strong duality. We define wa v to respectively denote the optimal solutions to the primal and dual variables. Approximating to belong to function classes W, and solving the empirical version of objective (24) leads to the PRO-CB given in Algorithm 6.
Algorithm 6 Primal-dual Regularized Offline Contextual Bandits (PRO-CB)
1: Inputs: Dataset D {s;, dg r;) Ji function classes W, V, function f(-), parameter
2: Find a solution w to the following problem
NV
max min i.CB (w, v) = WEW eEV
w(si, as)r:: - as((w(s;,a)) ((s:)(u0(s);)) -1). (25)
N
2=1
3: Return: ==
T.. =
D.2 PROOF OF PROPOSITION 3
We separate the proof into two cases: a 2 No for >> -1/2 and a < ((N-1/2) When a is large, we show that the large bias caused by regularization results in suboptimality of even in MABs. When a is small, we construct a two-state CB instance (as the single-state case is indeed successful due to Theorem 1), showing that such small a does not sufficiently enforce occupancy validity in states with relatively small but still significant state distribution p(s).
D.2.1 PROOF FOR LARGE
If there exists - < 3 such that a 2 8 then consider simple single-state two-arm contextual bandit (equivalently multi-armed bandit) instance:
Reward distribution: Both arms have deterministic rewards and the suboptimal arm has value gap of a:
r(1) =1 w.p. 1, r(2) max (0,1-aa) w.p.
Data distribution: We construct the data distribution such that both arms have constant probability density, which implies a constant concentrability ratio C*. Here we assume Mj < 100 for convenience, but if M2 is larger even larger constant as the denominator.
the same construction with an
Mj 100
M₁
((1)
((2)
100
Function classes: assume both W and contain only the optimal regularized solutions (wa, vx)) and the optimal unregularized solutions (w* o*), which satisfy the realizability requirements of PRO-CB:
W = (w., w*) V {u 0*}.
Our argument is broken down two steps. In the first step, we show that the suboptimality of the optimal regularized policy, which is the policy induced by the regularized optimal weights x Tag. is at least of order min(1, a}. Then, in the second step, we prove that w is chosen with constant probability.
23

---

Published as a conference paper at ICLR 2023
Step 1: Suboptimality of n2. In the particular offline bandit instance above, we show the follow- ing lower bound on suboptimality of =
J(x²) - [(Ta) = (2) (r(1) - r(2)) = (2) min(1, a} = (1,
(26)
To establish (26), we show that wa (2) > for fixed constant 2- tion. Suppose
We prove this by contradic-
" (2) Sc
(27)
By KKT conditions we have
wa (2) max (0.1))-1 (r(2) U/ )} 2 22(0)=1 (F)) (((2) - 2
Therefore, using the fact that f is strictly increasing since f is strictly convex, we lower bound 22 according to
0 2 r() - (w 2 r(1) - (r(1) - r(2)) - a (c).
Combining the above bound on 2xz with the KKT condition on w we then obtain
w (1) r(1) 1
(F))
f (())
(28)
Here, we used the fact that v2 2 y+ Moreover, since the regularization function ʃ is -strrongyy convex, we write
=r(1) and that f(0) 0 (f)))((r(1)) wa)/a) 2 0.
( cq(2) ( 5 M, (
1
e) (--((()--==
(²-cH(e)
M, 1-c 100(1 > >1
(1)
(11)
1(1)
(11) r2) + ff (c) 11+ < (1 m(1)
(1-cu(2) cu(2)
1
(29)
a Therefore, we can continue to upper bound the RHS of (28):
(r(1) (r(1)-r(2) a
((')) (5' (1- (f(
1- c-cu(2
" (1) S (f))-
(c)
u(1)
11(1)
229
which further implies that w (1))))(1) < <1- - ccu(2) S 1 n (2)
= Ewa(a)p(a) <1.
(30)
by (27)
Note that (30) contradicts with the fact that (wa,, v1) is the optimal min-max solution of I.MAB because violates the constraint [ [w([a]] 1. Therefore, (27) should not hold in the first place, and we must have
(r()) r())) > c (1- Mr min(1, 2 min(1,a) (31) 100
J(x*) -
Step 2: w is picked with large probability. We now show that w is picked by the algorithm
with at least a constant probability. Note that since w and w" both satisfy the constraint E, [w]-1= 0. objectives 1MAB(ww,, v) and T.MAB (w.,,) v) do not depend on the Lagrange multiplier variable v.
We argue that at the population level, we have the following lower bound on the gap 7.MAB (w v)
MAB (w",, v) Z a. Using the definition of M.M one has &
MAAB (w :) MAM (w+,-)
= [. (a)) f(w2( - ((2) r(2))
((1) ((1) [f(w (1)) (1)) (w: (w))) ((2) (F) - f(w;(21)) (11) ((2) =())=c r(2))
Za (n(1) w (1)- (w; ((2) (2)) -
r()))
(32)
=ou(22) (()) w2(2) f(w. w (2). r(1) r2() r(2)
(33)
24

---

Published as a conference paper at ICLR 2023
In (32), used the convexity of regularization function f as well as the fact that f(w" (2))
f(0) = 0. Moreover, (33) holds because
1 p(1) (w)(1) w2 = u(1)
( (ल(T) - wa(l1) (1() 1(2))
By KKT conditions we also have
(' r(1) 00 r(1) -(1)-r(2) + (w r(1) (()--r() + (2)) (34)
Plugging (34) back into (33), we obtain
MAB/ (Wa: :) LA (w",) 20x((2) (s' (w, (2)) w2(() ( 2ap((2)
Mj w (2)2 > ap((2) M 2 a,
(35)
where (35) is based on the fact that f is --strongly convex, and that w (2) > proved in Step 1. We now prove that such large lower bound on population objective difference leads the algorithm to select w Recall from Lemma that with at least constant probability (c.g. setting ó 0.1), for any v E V, w E W, one has the following bound on difference between the population and empirical objectives
MAB (w, v)
LMMBB (w, v)
x
MAB stat,a
MAB where stala is of order L/VN VNaa defined in (18). Combining the above inequality with (35), for any v E V we have
MAB
(w v) MMB (w* (w*t,') o')
2
MAB
2 (1 (1+a)N+ Z No9 - -
statia
Therefore, since 1/2, we conclude that w chosen by the algorithm with constant proba- bility:
min f MAB VEV
(w"")) u)
min
MAB (w", v) > "
argmax min MAB
(w, vw)
.EV
weW vE
Combining the above result with the suboptimality lower bound of x in (31) completes the proof for 8
D.2.2 PROOF FOR SMALL
Now suppose Ō(N- b), where Ô hides the logarithmic factors. In this case, consider the following two-state two-arm contextual bandit instance:
State and reward distributions: We construct the states such that state has a very small probability mass. For state 1, the first arm is optimal with a Bernoulliddistribuee reward and the second arm is suboptimal with deterministic reward. For state 2, both arms have deterministic rewards. Importantly, state has constant value gap in its suboptimal action.
1
p(1) - r(1, 1) Bernoulli
r(1,2) 3
2
1
((2) = 1 1(2,1) = r(2,2) =
Data distribution: We assume that for both states, most of the probability density con- centrated on the optimal arm.
m(s) p(s), 1,2.
(1111) = p(1/2) = N ((2 = (2222) = N
25

---

Published as a conference paper at ICLR 2023
Function classes: Let be defined as 22(2,a) a) w2(2 a) and ((1 for 1,2. Consider the following function classes W and V/
W = { w) V (va j"
(36)
The proof is broken down into 4 steps. In the first step, we show that when a S Ö(N- and N sufficiently large, the regularized optimal policy is the same the unregularized optimal policy, le., w w". Therefore, the function class W defined in (36) is realizable wa = w* E W. In the second step, we prove that with constant probability va = argmin f. (tū, v). Then, we show that solving the saddle point of the empirical objective L (w, v) selects over w with a constant probability. Finally, we prove that to induces a policy Ta that suffers from suboptimality of order N-1/1, which completes the proof.
Step 1: Regularized optimal weights coincides with unregularized optimal weights. Since the population optimization problem (24) is independent across states a population level, we can use the result of Lemma 1 to conclude that
(s) = r (*) c(s)a, and
wo (8. a) = max { (0(())-) r((., ((( a) - -26(5) max {o,(1))' (((s) r*(s) - r(ss
where 0 v c(s) - (C') for & E (1,2). Since r' (s) r(s, 2) = = 011, for N 2 (C*), we have w (s, 2) = 0 for the suboptimal arm 2. Thus w (s) = w m(la) Correspondingly,
we can use the KKT conditions to compute (s) = (*) af p(1bs)
Step 2: " argmin vvv L
i (w, v) with constant probability. Let f denote the empirical state- arm distribution and f denote the empirical mean reward. Define the following event:
Σ Σ (alss) a) s for s [1.2]
(37)
Recall that we defined (1, = and ((2, a) = w (2, a). Thus, the above event can be equiva- lently written as
(dd <1
Σ (i(a))) - ((ll2))wwa( (2, S.O
(38)
Here we used the fact that Σ. ((al2) (s. 2) = 1. Moreover, in Step we showed that w w²,
thus w (2 = 0 and (38) corresponds to the following event
{ p(112) 50)
(39)
Since A(122) an empirical version of the conditional probability p(1[2), event & happens with probability 1.
We condition on the event for the rest of the proof. Using the fact that (5)) S (s) = (s),, conclude that
CC ( v
i.B (w. v*)
i.C. (17, vx) min i. vEV
(w. v).
(40)
Step 3: Analyzing the probability of picking w Now we compare the value of LCB (, (.,u)) evaluated w and w We use the definition (2, a) w a) and write
(C v2)) LCB (w, v
((all) (1)(1)))))0(((10))))
=i(1) ((1, (1,1)) (11 (1))
26

---

Published as a conference paper at ICLR 2023
Noting that (1) r(1,1) - af (w a1), ((1, = 0, and (1, w= (1, adny>
further simplify the above equation
i ia((" (war
Li (ūē, v(a)
=p(1)
(((1,))-((111))))))))))) af
p(l[1) (
((111)
+ ap(1)1))
(41)
f(1,1) (11,))-(4L.1) +
(WaTT
(<(IT)
(
-)1,
(42)
We then prove that with constant probability, the first term in (42) is negative with a magnitude larger than the second term:
F(1, (1,11)-r(1, -r(1,) 2 3/8
(43)
(1(1
The proof of this inequality relies on anti-concentrattin bounds of binomial random variables and is presented at the end of this section. By Inequality (43) combined with (40), we conclude that
min CB vEV
"o (w,, v) FBB (w, mg)) > f (w): 1 2 min I I.a (wa. v),
(44)
vEV
which guarantees that the algorithm picks v with constant probability.
Step Suboptimality of Tm Finally, for the policy The induced by w, we have
N
[( - J(TT) μ(s) (T)1)) r(1, r(1,))
2 2(N*),
12
- Proof of Inequality (43). Using the Chernoff bounds for binomial random variables given in Lemma 2 (adapted from Proposition 7.3.2 of Matoušek & Vondrák (2001)), one can conclude that the fol- lowing event 8' happens with probability least 0.5:
for 3 = = >
2. as desired. The proof for small a is thus complete.
E' E² (=(N(L.)) 0.1, 0.05N
(45)
Furthermore, & and 8' are independent because the random variable f(s1, a1) ) is independent from the arm distribution within state $2. Therefore, conditioning on Eng' which happens with probabil- ity 0.5 x 0.5 = 0.25, we use the anti-connentrattio bounds for Binomial random variables Lemma to obtain the following lower bound:
-V log(2c1) c2N(111) S CNN- 33 2 0.5,
Pr 1(1,1)-((11))
(46)
where d' 20 is a universal constant. Therefore, we have established that (43) holds with
constant probability.
Lemma 5 (Anti-concentration of Binomial random variables) Let X1...., Xn be independent random variables following the Bernoulli distribution with mean 3, and let 1 Σ X₁ be the empirical mean. Then we have that for any I. E [0, El and universal constants C1, C2.
Pr Pr < X t) 2 die c2ln
(47)
D.3 PROOF OF THEOREM 3
Proof of this theorem largely follows similar steps the proof we presented for Theorem 1. In particular, we start by presenting two lemmas. The first lemma leverages Hoeffding's inequality to establish the closeness of the population objective (7) and empirical objective (8). Additionally, show that this result leads to the closeness population objective at wn and t. Proof of this lemma is presented at the end of this subsection.
27

---

Published as a conference paper at ICLR 2023
Lemma 6 (Empirical and population closeness, CB) Fix 5 > 0 and define
stnt = 3(B + 1)² + DV log( (11())
(48)
N
For any w E W and v E V, the following statements hold with probability at least 1 ò
(1) C (w, v) I.C v) S c
'AL
ssarr
(II) I CB C.C (w", U) LB (w) v) S CB
In the second lemma, prove that the ALM term enforces lower bound normalization factors the (s) = E. a))(aa) for significant states.
Lemma (Occupaney validity enforced by the ALM) Define the state space subset
de
11 25
S
S
(49)
For any fixed 8 >> 0, the following statements hold with probability least 1 - 6,
(I) E Es (s) a(s, cB.
(II) Exes, pls) S stor
where stat defined in (48).
Given the two lemmas above, suboptimality analysis can be broken down into two simple steps. First, we partition the states based on S₃ defined in (49) and decompose the policy suboptimality accordingly:
= Σ (V) + Σ (s))
SES,
#gS.
CB Eual
+ Σ
-
(50)
sgS,
cal
Σ
dz v*())
(51)
In (50), used part (II) in Lemma 7 to bound the first term and (51) uses the fact that by definition, for all S, we have pus) 2d(s) and V*(s) V* (s) 2 0. Moreover, the second term in (51) is bounded by part (I) of Lemma 7 since
Σ (o(s)(V - v*())) = Σ da(s) (*(ss - Σ H(als)r(s.a))
s:dw (+)
E dos(s,a)r*(s) (s) ((s,a))(ssa) a)
Σ
ds(s) r(s,a)
(=da(s)
Σ "u(s,a)((s,a)) -(s,,))(ss.0) sda(s)>0
Σ
Σ ()) a(), S
CB
estato
8,8
where the equations follow from the definition of noting that (B,, + 1)2 B² since B,, 2 1 due realizability of w (s,a") 1.
न. The final suboptimality bound is proved by
28

---

Published as a conference paper at ICLR 2023
Proof of Lemma To prove part (I, notice that E, L
[ (w. w)] = AL (w, v).
Furthermore,
CB AL (w, t) is an empirical average ii.d. random variables which are bounded by
Σ woss a))(als) -1)
(((s,a)r(s,d) - (( -1
$ B + (B + + B
2 3(, + (B, 1)
Applying Hoeffding's s inequality along with union bound on w W and v E V finishes the proof' of part (I),
We now prove part (II). For the primal-dual objective without the AL term
max min LB (w, v) == Es (w(s ()r(a, a)] Es (as)sa(((((((((ss))))) 1)],
#20
have (w*, v*) argmax,220 argmin, I (w, u) by strong duality. Moreover, since w is realizable, it satisfies the validity constraint Ea>y(-1s) (s, (s, 1 for all s. Therefore, by Lemma 14 adding the ALM term does not change the optimal solution and we have (w", u*) argmax argmin, AL (w, v).
We follow similar steps as in the proof of Lemma and decompose ( (w*,t) - AL v) ac- cording
L AL. (w", b) L (w0, v)
AL ALL"", v) L CB AL (w* ((w0)( + LL ((w*)) CCB (w* 6(w*))
T1
T2
+ i CB [Ai, (w" ((ww))
L ().6))++
LCB L i)
CBB (w v)
TT's
T=
+ i Al. (b, 2) (2. v).
where e. arg min LCB AL. (w, v). Each term is bounded as follows:
T 0 because w² satisfies the optimization constraints.
T2 stat
due to Lemma
Ta S because ú = arg max J.BB 'AL (ww, w).
T4 0 because 8 arg min.ey CCB
AL (v, w).
T3 < CB due to Lemma 6. stat
Summing up the bounds on each term proves part (II).
Proof of Lemma 7, We leverage the closeness of the objective w² and u established in Lemma to show that the ALM term small. Since w* satisfies the validity constraints, the objective at w" simplifies to
CB w",, ,)) Eg (r(s, (s, + Eg [o(s) - w (s,a)) - E (Er_a(Ennn a)] 1)
Eg ar) (8,
29

---

Published as a conference paper at ICLR 2023
Consider the objective difference at e(s) r*((s max, r(s,a)
(w", (w, rT) A (A, AL
Σ ((s))((()) Eule,,)r(ss --rr-ss) (m(s) Em(s(a)((saa))
de (((())-1) 27
+ Eeuu
(1)
Σ [((s,a)lr"((0 - r(s, a)) a) + Esru
3,0
Since [ u)) L (i, u) by Lemma 6, we conclude that
( die (s) 10-1)
27
((s. r(ss)ss Banu
-
CB stat
1
Moreover, since the first term is nonnegative due to 0(s, a) 2 and (s)) - r(s, a) 2 0, both of the terms in the above inequality are bounded by CB and thereby proving part (I).
The above result also allows us to bound the mass on the subset S₂ that contains the states that violate state occupancy validity
Em(s) p(s) ((2
27
( (s) - (s)
(Li())
dhi
CB Stall
-
Σ m(s)
2 Σ ((s)
Σ m(s).
SES,
#ES.
#ES.
de * (s) where used the fact that du (s) 1/f and thus concludes the proof of part (II).
1 by definition of S. This
E PROOFS FOR MDPs
In this section, we begin by introducing some additional notation. The original primal-dual objective without ALM term is given by
max min L MDP (w, = (1- (1_o))ee)((((s) Ba [w(s, (s) #20
(52)
Define w² (s. one has (w",0", E arg max 20 arg min, MDP MDD (w Additionally, define Sü... arg maxç<o L. model-tteee (w, u, 5), Vw E W,uu E U and C Su Vw E W where ut is de- fined in Theorem 4. Also, denote Ç* = Ct and w² ui
d= (s.a)/p(ss0)
and (s)))
(*(s). By strong duality,
AL.
The rest of this section organized as follows. In Appendix E.I. we provide some details regarding practical implementation of the offline learning algorithm with ALM. In Appendix E.2, we derive the objective of model-free ALMIS algorithm. Appendix E.3 contains the proof of performance upper bound model-based and model-fres ALMIS algorithms (Theorem 4), which relies several lemmas subsequently proved in Appendices E.4 through E.7.
E ON PRACTICAL IMPLEMENTATIONS
In our algorithms for CB and MDP, we need to compute summations of form ΣGEA This can be implemented efficiently when |A| is small. When [A] is large even infinite, can utilize numerical methods to estimate the summation with desired precision. Additionally, in Algorithm 3, we need evaluate a term Ev.ar ((ss(ss,)TTwl (osss/((s,,,,)) ((s''''), a'). In practice, we can evaluate this term by numerical integration.
For MAB, CB, and model-based RL, our algorithms need to solve a max-min(-min problem. For model-free RI,, the mox-min--in-man be converted to max(-max)-min(-min problem. This is
30

---

Published as a conference paper at ICLR 2023
because first exchange min, and maxç since mmnde--fre as defined in (54) is convex AA.. w.r.t (w,{) (). Then, we can exchange min, and max; since and Ç are not coupling in T.modchffre Therefore, our algorithms only require a max-min oracle, which is also required in prior works on provable conservative offline RL with general function approximators such as (Zhan et al., 2022). Moreover, many practically successful offline RL algorithms also solve minimax problems such as the DICE family (Nachum al., 201 20;9b;a; Yang et al., 2020; Lee et al., 2021)
"AL
E.2
DERIVATION THE MODEL-FREE ALMIS OBJECTIVE
For f(x) = (x 1)², the Fenchel conjugate f. is given by
2
+
(x) max(ay f(v)) max (ry 8² + 2y - y
- 1.
(53)
2
Since dio (s0(5)/d= (8) 2 O, we have (s, a) 2 and thus it is sufficient to only consider domain ((85a) 22 over which fx(x) is invertible.
Let (etg(z) - (x)
2-220++1 which is convex function |-1, +ox). Similar Nachum et al. (2019a), we use Fenchel duality to estimate [u(s, a) - ->P" u(s, a)). By Fenchel duality, any convex function ((x) can be written as g(x) max; xς (c). In the case of g(x), the Fenchel conjugate is given by 9- (z) = 2 - 1/1 with domain x < 0. Therefore, we write En (w((,, a)g (u(s, a) 7pa a())a))]
(, a) max (u(s, a) - 7 uI (-)((())))))))
5<0
= [w[[ a) max (u(s, a) - uI a)) + (cO
The interchangeability principle (Rockafellar & Wets, 2009; Dai et al., 2017) allows us to convert the inner maximization step over scalar Ç to an overall maximization over Ç S A RR. Replacing this term in the objective (13) results in the following objective:
max min min max L free (w, v, u. () = (1 - 7)) o(()) + u(( Eu(o,a)mo(uls #20
AL 5<0
(54)
+ ((e,,ss)
nn a' ( (c (u(s, a) 7u(ss, ((((s))))))
E.3 PROOF OF THEOREM
We start by deriving expression for =t and characterizing bounds ut, and C in the following lemma. The proof is presented in Appendix E.4.
Lemma For any w E W and v E V, one has x (s, = 2d (s) (8) 2, |u (8, a)ls
1- (B2/4 4 B.), and (s, (8) 2+B, 2-B
Bounding the suboptimality of policies returned by both model-based and model-free variants of ALMIS follow similar analysis. We first characterize the statistical error in approximating popu- lation objectives by their empirical versions and use it to establish the closeness ń and w*. The lemma below captures these approximation errrr for the model-based objective, whose proof can be found Appendix E.5.
Lemma (Empirical and population closeness, model-based ALMIS) Fix and define
model--baze = (Bu, Bc) Ba, [ (I(1111)))))))) stat
(55)
N
For any w E W, E V, and E U, the following statements hold with probability at least 1 - 8
(I) L model baved (w, U, u) L model- (w, U, u) S
modell-ased.
Estat
(II) I modell-based (w= w² u²) AL
model-bussed (úr, w* ut)))
2c model-baued
AL
stat
31

---

Published as a conference paper at ICLR 2023
In Appendix E.6, prove similar lemma for the model-free objective.
Lemma 10 (Empirical and population closeness, model-free ALMIS) Fix ò and define
=Bu + (1+ + B. + Bc(B,+1))Bul) log( u \ M 2//6)
model-free Cata
(56)
N For any E W EV, and E U, the following statements hold with probability at least 1 - 8
(I) L model free (w, v. u)
free
(w, v, u) S
freee-free, free:
AL
A'AL
Stta
(II) L AL
Lmodet-free u"","", u²) LA
mmmeeet-free (10, v², (
2c
star
model-free
The final key lemma demonstrates that in model-based and model-free ALMIS, the ALM terms enforce lower bounds on the ratio of the estimated occupancy of learned weights (s) and the actual occupancy of the learned policy d (s) in most states. The proof of this lemma is given in Appendix E.7.
Lemma 11 (Occupancy validity by the ALM, MDP) For w computed by the model ALMIS Algorithm 3, define the state space subspace S, = {s dda(s) S 3d (s)}- For any fixed >> 0, the following statements hold with probability at least -6
(I) E Es (s, (s:)))((s.)) Z
mmodel-based,
Estat
d ($) S (1 eman model-based (II) Exes, a
Similarly, for it computed by the model-free ALMIS Algorithm 4, define the state space subspace S. =
at least dd)(s) S =dd (s)} For any fixed ô > O, the following statements hold with probability
(I) E Es | (s. a))((s(ss))) a)] S
model-free stot
(II) EEEs, a (s) S (1 7)- 2 model-free
Given the above lemmas, we proceed to prove the suboptimality bounds terms of statistical errors defined in (55) and (56). In the rest of this section, we drop the superscripts model-based and model-free from statistical errors to avoid cluttered notation.
In view of the performance difference lemma in Kakade & Langford (2002, Lemma 6.1), one has
- J(+) Egndd
A[ (a(s))(((s)))
Exwat Σ (ss,
where dt = = Here, we used the fact that the expectation of the optimal advantage over opti- 0. Lemma 11 links an expectation of -A" ( a) to the
mal policy is zero E. Ar,s, as,aa))**( (a)s) statistical error. With this lemma at hand and using the definition S, = {s d S d= (s)/2]. we continue decompose and bound the suboptimality
Egnd'
Σ
- (s)
Σ d
Σ
+ (s)
Σ
1 (s.
8.
sgS,
(=)
(1 733 Eatar +
A (ss,a))((s
(57)
sgSS (x)) (s)
Σ
(3((s)
(s,
A
a
(1 7)3 Estar +
Σ
A As ((ss))0((8,0)))5s
(58)
SgS.
32

---

Published as a conference paper at ICLR 2023
In (57), used part (II) in Lemma 11 and that as) 1/(1 >) and in (58) used the definition of S to bound the ratio d (s))/daa by and the fact that (s) = implies dd (s) 0 for & S.. We then apply part (I) in in Lemma 11 to bound the second term by Exgamal- A (s, a) (8 a)] and thus the overall suboptimality:
1
J(=t) - J(+) S
(1 7)3 san + E, Es |- Ar Ar, (s)
(1 7)3 Ssta-
E.4 PROOF OF LEMMA
Derivation of T. Recall from Appendix E.2 that for (xx (x 1)², the Fenchel conjugate is f.(x) = (
Therefore, for any (s,a).
w s, a) = arg max
(mm())) - (s)(s)
(
-1) -1) = th (8)
du
ds((s 2, - -Ba Br
+ Tw (s, a) = clip
nm
Bound on uw- Recall that w is defined the fixed point of the following Bellman-like equation
u(s, a) - f. (T (s. a)) T(P" (s, a).
(59)
The above equation has solution since f. ( a)) is bounded
(²2 2
2 2 1 1 (.
Bz
2
2
One can view uw the Q-function of policy Tw with the reward function f- (s, a)), which leads
to Iut (s, a)ls max
{1
(2-B- B_
BB,22)
1) r B.).
Bound on Cu To see the bound on Sü. recall that by definition,
Su, arg max "as
((u(s,) a) - yu(s', 1)((s,a) + 1/((s, (
<<0
(60)
is easy to show that 1st (8, a)l= (u(s, 1) ( +
Since (8, [- Bz, BR), we have (8,
2 2
24B, 2-B
E.5 PROOF OF LEMMA
E.5.1 PROOF OF PART (I)
We decompose the difference between the population and empirical objective into three terms
modde--hnsed_ - mondel-based
Ti T2 + T3s defined follows
AL
AL
No
Ti (1-7)B, u(s)+ + + ulss ((ssaa)mm(ass)) - - -
1 71
u(s)) Σ u(si, (mls)
No
T3 = E, w(s.0)(((s,0+ +
w(s a:) |r - (((5/) - u(ss)l
N
T3 Ey [wo(s, (f- pppu)((ss)))))))
1
Σ
w(si, ai) [5-] (u(st, ai) -7 7pp= u(si, u(si,
N
33

---

Published as a conference paper at ICLR 2023
We subsequently show that the absolute values of the above error terms satisfy the following high probability upper bounds:
log|V| /
MTl S (B, + B
(6la)
No
log/V//W//8
T2l < (1 + B.)
(61b)
N
Bu log PI
[T& S B
(61c)
N
Taking No N and noting that B 2 1 due to realizability of w" yield that
log 1///8
Bu log([P]
W (1/6))
model-based
model-based
< (B, + Bw)
(1 (1+BB)B...
AL
AL
No
N
model-based stal
Proof of bound (61a) [7/. Since le(s)]s Bu, [u(s, a)|s Bu for all v E V and U and 8; are independent, we can apply Hoeffding's inequality and union bound to conclude the advertised bound (6la) [
Proof of the bound (61b) on T/l/- By boundedness of w, we have
(u)ss yo(s') v(s)) B (2+ (1 + 7) B,).
As before, due to boundedness and independence of variables w(s,, ar)lTa + yu(s{) - v(s;).. Ho- effding's inequality be applied, giving the bound (61b) [T2).
Proof of the bound (61c) on [gg) We decompose T3 = Ta. + Ta.2, where T3, and T3.2 are defined as
T3.1 = Ep [w(s (fr (u(s,a) >F== u)) a)))] - Ey (s(s (1.² -
T3.2 Ep (u(s,a) a) (1o (u(s,a) ((p (s: (s)s)aa))]]
Σ u(s; ai) 15 (u(s;,a) - > (f (si,
Recall that (x) = 2/ + from Appendix E.2. The absolute value of T3.2 can be immedi- ately bounded using Hoeffding's inequality:
Ba Bo log W
TT.22 Bu
(62)
N
To bound [7,, we first use the inequality given Lemma 13, setting bi, Fi, yt for each (s,a) according to
1 + a(s,a)
i i 0 1 i (S
6;
( Ear Thd (a')s' (a()s"))()s(aa))
1=0
= {1 P()(s,,))
i=
4; P(())s,))
1sis
1 1si515 [S)
34

---

Published as a conference paper at ICLR 2023
Thus by Lemma 13, we obtain the following bound on T3,1
By [w(s, a) (f= (u(s, a) -pp"uu(s,a))) - -Eu (w(ssa) (1r² (((sa)) u
T3,1
< B
By
1 + a( -2 Σ P(s'|s, a) Σ (a'ls') (s)(sss))ss'saa)
Ey
1 + u(s -7 - P(s'|s, Σ Tm (am(a'ss")
Σ -VPPel8.0)-VP((sss)s
< B Bp
-
(63)
Note that the terms under square root are always nonnegative because for any transition P
1 u(s - 7 E P(s'|s, a) Σ Tnlld(s')ul a') 1 Bu BB, 2 2B 2 0.
Then, the concentration result maximum likelihood model estimation stated in Theorem and a union bound on w E W and E to conclude that
Bu log P U WI/8
|Ta1 Buy
(64)
N
E.5.2 PROOF OF PART (II)
To prove the second part, let ün and uu denote the solutions to the model-based empirical objective
E Uay argmin argmin
L model- pmadel-basedd
AL
(W, U, u.
uell
Decompose the objective difference according to
L model-based (w", -²," u²) - -mddel-basce (10, v², (.1g))
AL.
L AL
model-based (w", 8², u²") L LAL
madel-bbaed (w", Bw uw-) Ti
L AL (w= Degi (ww)) L masel-based (w", Ome Umy)) = T2
model--bsed
+ AL
model-based (w" Oen (mp=)
i model-bbacd Al.
(w. 0. (sp))
= T33
L model based
(b, De. Ug)))
i model hased
(1, v² u = T's
+ i model based
(b, 0², u.) L
model based
(w, U*, U = Ts
AL
We bound each term:
Ti because o* u² = arg min, arg min, AL
madel-hhased (wunssedddwwwdd (w* U, u);
Ta bosel-based by Lemma 9;
Ta S because ú = arg max i model mmpdel-bmed (w. Uway (bwr); All
Ta because E.. بي arg minegy arg mingeu i Al.
hasel (w: (w, U, u))
T model-based by Lemma 9.
35

---

Published as a conference paper at ICLR 2023
E.6
PROOF OF LEMMA 10
E. PROOF OF PART (I)
We decompose the difference
AL
mrdel--free
- mrdel--free = + T2 AL
T3s into three error terms
T = (1-7)BB v(s) + Eu(s,a)Tu(() - -11-7)
1
v(()) Σ u( uu ((lo)))))))
No
==1
T2 Ey ((ss))(((ssa)++ P(s(ls,,a)(()) u(s))
1
w(s; at) In (o(6)) v(s,))
N
N T3
[(oa.s") (wss, a) ((u(s, -uu(s' d')()(ss
ru(s',
g (C(ss
Σ
w(st, a:)
(uter.ns) -
Σ u(s's, (' ((st, - g=(((ss; (a))
N
a'EA
The absolute values of the error terms above satisfy the following upper bounds with high probability
log((V[[(118)
S (B, (B. + BuDy
(65a)
No
log((>)[WW)/0)
Th $ (1+ B.)
(65b)
N
log
T3 - (1 + BB(B, + 1))
(65c)
The bounds on the first two error terms Ti and [T2] are already shown in Appendix E.5.1. To bound [Ts), recall that 9+ (x) = - x. Vx < Also, (((s, a)le (Be.L. B₃,)) for any Ç E and any (s, a). and Bę a max Bg,u, B. Therefore, the individual error terms [Tg] satisfy the following bound
lwss, a) ((u(s,a) - yuls, (()))( g. (C(s, <B.. (11 + Be, + B + 2).
Thus, by Hoeffding's inequality and a union bound on W,U, and Z, we obtain the upper bound (65c) on Tal. Summing up the bounds given in (65a), (65b), and (65c) and noting that B., > 1 due realizability of w", we obtain
trode (w. u. 5) immdee--tree (W., () AL.
log 1/128//8
log/u/| W 1///8
(Ba + Bu)
+ (1 + B1+ BB 1))
No
model- free Stat
E.6.2 PROOF PART (II)
Define the following solutions the empirical model-free objective
Ow, Dw Sam arg min arg min arg max model-free (w, v, (),, Yw W VEV
AA. (E2
well
Č(w, u) arg max i model-free
(w, U. u. Yu E W,ueu
AL
CE2
36

---

Published as a conference paper at ICLR 2023
Decompose the objective difference according to
LA..
model--reee (w", -,, uuu" .5* L'A.
moedel-rree (vê, , Sid)
L AL. At (w", "0""" v², uu,"., _ineeee--tee (w", Ow twe S (w² Ugw))) = Ti
+ AA
modell-fre free (w= Des Uww Sw aew
L
AL freeel-free (w", Bur, Dw Sur,a
T2
+ m free
(w" Bwn, Urw Swo Ben.
An (w" Owr tha Swi)
== TT:
+ L. freee--rre (w- Cery Uwer Suo)) AL
AL
i. freee-frre (w, Go Unii Sai) == T4
+ I. model free
ALL (ni, Bay thi Gai
T. (ii, v", w Sa.nn))
== Ts.
AL
+ i AL mreel-ffree (á, v², u Sa. - L'LL (ré, o0, ua (minee))
model--free (1ē, 2n u Sa.)))
= To
+ L modell-free
-L model--rre (úē, o², ui Cū)
We bound each term:
Ti S because v*, u² = arg minp,a mmmoel-ftre (w* U, U, S (w", u));
At.
T2 S Emodel-fiee by part (I);
T3 < O because Gw- Sum = arg max z L (w", Owr Uwo S);
T4 < O because u = arg max Li free (w,, Sw, uw Sw);
T3 S O because Gi, Us arg mitleey,weu immdeet-tee (w) U, U, Sui
AL
Te Emodel-free by part (I);
T7 S because G = Sā,ug = arg maxç<0 maddl free (w) 0², u C).
E.7 PROOF OF LEMMA 11
We provide proof only for the model-based algorithm and let w = model--based for notation convenience. The proof for model-free algorithm follows analogously, noting the fact that AL fi (w, v², uh ( = - hased hased(w, (w, v², ) and we can replace Lemma 9 with Lemma 10 to prove the model-free version.
E.7.1 PROOF OF PART (I)
Consider the expression of the model-based objective AL where = W
madel--based (w* v², u²) at the optimal solution
I model based (wo", ,0", u²)
( dw (s) di (s) -1)
-(1-))B (0)))(((ss]]00) + E, Es,arp as, (s) - E Ea-di
=(1 =1 + Es,arp (w" (s.
(66)
The first equation comes from the fact that u" is the optimal solution to the variational lower bound, making it equal to the f-divergence. To see this, recall from Lemma 8 that x (s, = 2dw (s) Jn (s = x (s, a) and thus u" recovers the f-divergence.
2 and (s,
tiip (s. -B,, B.). Since x; (s, 0, we have
In Equation (66), we wrote (s) V*(s) since u*()) is the optimal solution to the primal-dual program without the ALM term and is equal to the optimal value function (Zhan et al., 2022). We also used the fact that eur (s,a) = =ss () +7 E. P(s'ls, a)"aa)""( P(s''s,a))""S (5")=="""(( (s) A* a) is the optimal advantage function, and that d (s) = == (s) by definition and realizability of w", Moreover, the second term in (66) zero since it captures the optimal advantage of optimal policy. Therefore, conclude that
L masel-based (w", 0², o²"="")=="""")))r" (1 7) Egnp VV' (s)).
(67)
AL.
37

---

Published as a conference paper at ICLR 2023
Given the above expression of the objective (w*, U*, ut), write the following objective differ- ence
mmedet-boood
(w* (w=
u², u²) L AL
model--aasd (10, v², u
AL
=(1 --)
[V [s)] - (1 - 7) Bo - E s [i a)ex (s,
(s)]
+ (1 71) Bspparn (n (s) B, (1(( ff (u 7 us)
(68)
- -e [iñs,, a (s, Bar= [f (s, a))l + (s,
The last line uses ev- (s, a) = A (s, a) as well as the definition of up as the tixed point solution to (s. a) f- (a a)) + +PP** (s,
which allows to write (68) in the original f-divergence variational form (11) with T as variable. Lemma 9 asserts that AL. modell-busd (w= 00, u²) L model buused (Ø, 2², u S stat
model based Therefore,
AL.
-Bs (s, a) A (s, a)] - Ex If (s, a) + Ed [T a)) S
Stat
madet-based
(69)
We next argue that both terms in inequality above are nonnegative and conclude that
- By (10(8, a A a)] S
model-based
(70a)
stal
-Ea (ā a} + Ex, [T (s, a)] S
model-bbssd
(70b)
Stal
The first term is nonnegative because for the optimal advantage function we have A*(s, a) S for all E S and E AA We write the second term
dia(s) d (s)
Es (Z a))] + E.d. (ira (s, a)] E
(nl J (.
We then show that each term inside the expectation is nonnegative:
(s) (s a) fa f=(n((s)) 2 0 vs S.
(71)
d (s)
Proof of bound (71). we separate the argument into three cases and use the expression of T., given in Lemma 8.
1. When 1- Bz/2 < da(e) (e) < BB/2++ 1, we have (s. = =(2
(2 du(a) -2) and therefore
n (s)
(s)
(s)
n= (8) J (s, a) (s
te -1) 0.
2. When (s)
> BB 2 + 1, substitute (s, a) = BB to arrive at
dn (+)
(s)
(Bx
B +1 B3
B²
B²
BB th (8)
+ 1
2
B,
2
2
4
4
3. Similarly, when (s) [ow
< 1 - B2/2, substitute (
(3, = BB to arrive at
(s)
B
B
B
B2
-
1
2
- 1
B3
B
2 0.
(72)
2
2
4
E.7.2 PROOF OF PART (II)
We derive the second part by using the bound (70b) restricted on the set S,. When s E S,, we have da(s) < and thus the variational form falls into the case 3 in the proof of bound (71). Therefore,
d=a
for S., we have (s, a) BB, and
ds)(s) (s a) fa (1 (1 7)2 As S..
(73)
d= (s)
38

---

Published as a conference paper at ICLR 2023
We use the bound in (70b) well (73) to conclude that model-based
2 Bd (Tro (8, a)]
- Egg [f.
stat
du (s)
Σ d (s)
(a(s,a) ( (1(8
d (s)
2 Σ - d (s):
#ES.
which leads to the second advertised claim EeEs, a (s) S 7) 7) Estat
E.8 ALM BASED ON BELLMAN FLOW ERROR CONSTRAINT IS INSUFFICIENT
We demonstrated that Lagrange multipliers not sufficient to enforce occupancy validity and need to use additional penalty terms. Furthermore, we discussed why ensuring ratio-based occu- pancy validity is compatible with the single-policy concentrability definition, resulting in learning policy whose actual occupancy is within the data distribution.
However, might wonder whether adding a squared penalty on Bellman flow error, leads to a similar policy validity guarantee. This idea is appealing because it avoids variational lower bound and additional variables. However, here we provide an intuitive argument that a penalty term on Bellman flow error does not appear to be sufficient ensure ratio-based occupancy validity guarantee.
standard application of the ALM term, which involves
We use (s) to denote Bellman flow error defined as
c(s) = (1 - (1-))((s +
Σ P(als', d') d'')''' d') - a)((s)) s'
We show that even such strong state-wise guarantee Bellman error cannot generally lead to da (s) being bounded by constant. We argue this by contradiction. Assume that for 0 S <<1 (s)
d 1 = ds - ds(s) S cd
(74)
(s)
Since th satisfies the Bellman flow equations, we can show d du (1-7Pra) Moreover, we have a = (T 1P-7PP= ) Substituting these equations to (74), we conclude that for 0 S <c11
(I - -PaPPa) clI 7PPe) ) )-
S cp.
da(s) we require Bellman flow error to be pointwise this means that the Bellman flow emor is required to be nonpositive: (s)) < 0. However, even state-wise minimization of squared penalty terms such as 2x(s) can only ensure |e(s)] be small.
Therefore, to ensure a constant bound on d= (s)
smaller than the initial distribution. For state with p(s)
F ROBUSTNESS TO MODEL MISSPECIFICATION AND OPTIMIZATION ERROR
In this section, we study the sample complexity of our algorithm the presence of model misspec- ification and optimization error similar to Zhan et al. (2022).
Since practice, might be the case that our function classes W, V do not contain w o*, similar to Zhan et al. (2022), we measure the approximation errors of W and 1 by
C,r0 min v 0² 111 - 111 o 1,,,' #EV
(75)
min || w' 11.
Er,00,0*
wEW
where w* = d' and d' is the (discounted) occupancy frequency of any optimal policy n², I1-111,p weighted norm w.r.t. p. and ps(s) Es,ar P(sss', , a ())"(sss, (()s",a). The model misspecification error is measured in / norm, which is weaker than Lo norm.
39

---

Published as a conference paper at ICLR 2023
Furthermore, also consider the optimization error of practical optimization algorithms since in real-world scenarios it is unlikely that an algorithm can recover the exact optimal solution. Instead, a typical optimization algorithm is able to find approximate solution that is close enough to the true optimal solution. Formally, we assume that the solution (w, 6) that the optimizer obtained satisfies
(w, 8)
min (w v) S 60,0: vEV
(76)
max min (ww, v) min ((ú, v) S c0,w: NEW VEV
where the objective Ż can be substituted by any objective with ALM term in different settings (e.g., f. C. in contextual bandits).
The assumption above is also similar to Zhan et al. (2022), and it assumes that [ú ö) Ro
max minley L(w, v),, which shows that (1ē, é) is an approximate max-min solution of L.
With definition (75) and (76), the main result of this section is stated follows:
Theorem (Robust version of Theorem Assume concentrability of an optimal policy x² (Defi- nition 1) and let w² (s, a) = d= (s,a)/u(ss (((//(s,),, e" J(x*). Assume that [u[s]]s B, for V and O S w(s,a) S Bw for w E W. Moreover, assume (75) and (76) hold. Then for any fixed > O, policy ât returned by Algorithm (where (10, 0) satisfies (76) with f. = 'AL instead of the exact max-min solution as in (8)) achieves
1og((>>/111/6))
J(mT) - J(A)) S (Bw + 1), + 1)/
Capt + Cyis-
with probability at least 1 8, where Copt = Co.w Co.o and Emis (B + B + +) + (Bw + 1)e,,--
Note that we only present the robustness result for contextual bandit settings conciseness. Similar results also hold for MAB, model-based MDP, and model-free MDP settings.
Proof. Note that the proof is almost the same as Appendix D.3, except for part (II) of Lemma 6. Part (I) of Lemma directly holds in model misspecification and optimization error by the same proof. Now show part (II) of Lemma 6. For convenience, we use L, L to represent AAL AL
respectively, and let Eata 3(B + ()²(B, + v (og() Also, let
dy arg min | v² 11 - of +| I1a,"'s
VEV
wyy = arg min ||w - 111
wew
By the same argument in Appendix D.3, (w", o*) argmax argmin, L(w, v). Also, decompose L(w", ,u*) I[w,, v*) according to
L(w", u²) L(w, v²) ,W" - L(w", ((ww)) + L(w", ((w()) L(wwr ((ww))
=n
=
L(wi, (wwx))
i(wiys ((wt))) + L(uiy ((wwy)) 1----i- L(
T
-T
L(w 0) L(wi, ut)
L(w, L(w, vt) + L(w, wt) I(rd, v²).
=TB
TT
=T,
where ((w) = arg min [(w, v). Each term is bounded as follows:
because w satisfies the optimization constraints.
Th (B B, ar by Lemma 12.
Ta Esta due part (I) of Lemma 6.
40

---

Published as a conference paper at ICLR 2023
T4 c because w min.ey [(w, v) min L(w, u) co and wyy W.
T3 I f, because [[w,, 6) mingey L(ū, v) S Ca and u3 V.
To I Sta due to part (1) of Lemma 6.
T7 (Bw 1)e,,v by Lemma 12.
Summing the bounds on each term, we have
L(w", ,,) - L(uē, v*) S 2eamt + Copt + Cmis-
The remaining steps are the same Appendix D.3, and we can finally obtain that
log(MW))1100))
- - (B. ()) + +1)
+ Copt + Emis
N
Remark Note that the suboptimality caused by model misspecification and optimization error in our algorithm is of order Ofe + mis)) This is much better than the result of Zhan et al. (2022) where the suboptimality caused by model misspecification and optimization ervor is of order O( (Eops + a.))
Finally, we show and prove the following lemma which is key to the proof of our main theorem (Theorem 5) in this section. This is also similar Zhan al. (2022).
Lemma 12 Under the same setting as Theorem 5, for any v E V and any w1, u2 W. it holds that
[LW, v1) L(w, v2)15 (Bw + 1)(1e1 02111, well +1101 U2 p.
Also, for any U1, 1/2 V and any W, it holds that [T(w1, v) I(w2, w)|s (Bu B, 3)]lwn welli.
Proof. Recall that
L(w, u) E. (u(ssa))(( a)] - (E)lo(()(((sss)) a) 1)] (Bar 1) and in contextual bandits have p Jr. Therefore, by definition,
L[w, 01) - L(w, v2)l
[Bul(vi (s) (=(s))(u(ssaa) 1)]
(Ell((ii(8 (E) - v2())] u2))))
Bullun llv U/ w2ll,,, +|| -
< Bw + 1)((l - 111
-0 - 1211 w2ll1,w)-
Similarly, we have
L(wi, v) L(w2, w)1
Ep (8, u2 ((((sa) us)))l
Egnuu [[ 1)2 (La~n(()k) (u2(s,)) 1)
<( BB + 1) 1)||m] - -
+ Ex- [ (8, (8,a) w2(s, (ar a) wz( - 2)
<B,, + 1)|[ - + - + 2) - wa 1.
= =(B,. B. 3) [w1 w2 1
41

---

Published as a conference paper at ICLR 2023
G AUXILIARY RESULTS
Theorem (Convergence of MLE for learning transitions (Van de Geer, 2000)) Given a real- izable model class P = {P (S, A) + A(S)} that contains the true model P and a dataset sid
Dm = {(s) 04 $ with (ss, az) ~ u, s ~ (- as), let P be
P arg max PEP
Σ In a.).
Fix the failure probability 8 > O. Then, with probability at least 1 - 8, we have the following concentration the squared Hellinger distance between P and P
E Es,
Σ
- (oo))s.))-VPP(0100
27
24
(1/0)
Lemma 13 For any 0 s b, S B and F4, Vi 2 0f i {o.... ,.. .n),
the following holds
n
n B
Σ
biz:
Σ
biyk
V - vvi)
(77)
i=0
We expend the left-hand side of (77), use Cauchy-Schward inequality, and then complete the square:
Proof.
2
n
n2
Σ
b
Σ
biyl
Σ bys +
Σ biyt biyi- 1 Σ bioi
Σ bzyl
1=1
1=1
Σb ba + Σ bist -2 Σ be bi
Σ (VDE viyi)) S SBBB E (Vzi - v1i)²
Lemma 14 For any two arbitrary sets X. let f(..)) : X x + R be an arbitrary function. Let No fo= X infyey f(x,y) > -00 and assume Xo is non-empty. For any E Xn. assume there exists y² (z) E v s.t. f(r, f(x,y"(x) (x)) = minyey fIx y). Also, let X; = {x E Xo x E arg Eax f(z.y" (x)) and assume X2 is non-emphy For a nonnegative funncionnv A(-) on X, let
X' = ffx E X2 A(x) = 0} and assume X is non-empty. Define f f v) = f(x, v) - A(r). Then
x x E + inf ( > -00.
yEy
for any x E No.
E X' 5 arg max min fAL (x. y).
EE vEy
Proof. Note that for any fixed x, fat v) is a constant shift of f(x v). which implies that inlyey f(x,1) > -x + inl faL (I, > -x. This also implies that for any x Xg. arg minyey f(x v) arg min fAL (z,
For any x E Xg, let y² (x) denote any one of y E E s.t. f(x, y (x)) = min f(a,0).
Now for any x¹ X², we have
f(x",v) (x")) 2 fa, (x)), Vr E Xo.
>(0", ,y" (x*) - A(x*) 2 f(x " (z)) A(r), Vx E No.
= PAL("" (x" yy (x*)) 2 s ( (x)), Vo Xo-
min pAL (2" v) 2 min (LL 4). Vo E Xo.
yey
yEy
-r E arg max min f AL (a.y). x yEy
42

---

Published as a conference paper at ICLR 2023
For the other direction, given any z0 arg maxxedo mingey (A v). we have
min f (zo. v) z min fALl (A y). Vr No. NEY
yEy
(78)
fAL (zo. of (xo)) 2 fAL (z. 1/ (z)). Vr Xo-
Fix any x² X S No. we have f(x (x*)) 2 f(zo, yy (1o)) and -Axx)) 2 - by definition. Now assume to & X Then either f(x", y (a*)) > f(zo, y (zo)) if $ X2 or -A(x") > A(xo) if xo E X (t Either one of the above two conditions implies that
,,("))"(")))))"""))))))))))))))) - A(x*) > (1 y (xo)) A(ro) = / (x" y (xxx)) > (N0 y (rn)), which contradicts with (78). Therefore, zp X
43


Reviews:
[{"review_id": "nxTcCAV4HT6", "reviewer": "Reviewer_bCR3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper deals with offline RL problems, i.e. learning an optimal policy given some data sampled from a behavior policy. \n\nHere, while the behavior policy itself is assumed known, its state-action occupancy distribution is available only through samples. The offline RL approach considered is \"marginal importance sampling\": the goal is to learn weights for each state-action pair that will transform the estimated behavior occupancy into a new occupancy for the optimal policy. Another key assumption is \"single-policy concentrability\": in particular there is some $C^*$ which upper bounds the largest importance-sampling ratio required (for any state-action pair) between the behavior policy and the optimal policy.\n\nOffline RL with these assumptions is relatively well-studied previously. The previous approaches the authors compare to all have a general theme: they are primal-dual methods, maximizing expected reward, and using a Lagrangian to enforce a constraint that the occupancy distribution be a valid probability distribution. Such approaches also include a regularization term to keep the learned policy close to the behavior policy. The authors' improvement is to replace this regularization with an extra quadratic penalty on the weight feasibility (forgoing behavior regularization), which improves performance in MAB, contextual bandits, and full MDP settings.", "summary_of_the_review": "The paper seems like a reasonable theoretical contribution to a topic relevant to the ICLR audience, so I recommend acceptance.", "strength_and_weaknesses": "Strengths: The paper gives a clear presentation of improved algorithms for a topic which, while somewhat niche, is convincingly relevant.\n\nWeaknesses: there aren't any obvious weaknesses to the paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "ceU7XF7SWay", "reviewer": "Reviewer_WYf4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies offline RL (MAB/CB/MDP) under general function approximation and single-policy coverage. The authors leverage MIS formulation plus augmented Langragian method (ALM) and identify that the key for solving problem is to ensure that certain state occupancy validity constraints are nearly satisfied.", "summary_of_the_review": "I lean towards acceptance. I would appreciate if the author could address my questions.\n\n--\nScore 6 --> 8 after rebuttal.", "strength_and_weaknesses": "## Strengths\n\nCompared with Zhan et al. (2022), the rate is better and the realizability assumption is on the true density function instead of the regularized one.\n\nCompared with Chen & Jiang (2022), this paper drops the gap assumption.\n\nSome investigations in CB/MAB are interesting. For example, a lower bound on PRO-CB in prop 3 shows that PRO-RL cannot get the optimal rate.\n\n## Weaknesses\n\nIn the MDP case, the assumption is stronger. Compared with prior works Zhan et al. (2022) and Chen & Jiang (2022), this paper requires an additional realizable model class for model-based CORAL or a completeness-type U class for model-free CORAL.\n\nThe results could be presented in a clearer way. This paper includes many results, and it is very hard to track and compare them. I think adding a table that summarize the assumptions and results in the current paper and the most related works will be very helpful and beneficial to readers.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "auxoSLzLFM", "reviewer": "Reviewer_sKtr", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose an augmented lagrangian approach to various offline decision making learning problems based on marginal importance sampling using function approximation. The authors show that their method exhibits improved qualities over behavior regularization, such as improved (sub)optimality. The present 4 variants of their approach, specialized for multi-arm bandits, contextual bandits and MDPs (model-based and model-free). The authors conclude with a small illustrative example comparing their approach to behavior regularization.", "summary_of_the_review": "This paper is interesting and of high quality, and I support it's acceptance.", "strength_and_weaknesses": "The results are conclusive and insightful. Assist by their theoretical contributions, the authors make a strong case for the impact of occupancy validity on the performance in offline learning and provide an interesting explanation for the limitations of behavior regularization. Their proposed approach seems likely to inspire future work, both theoretical and empirical.\n\nMinor nitpicks and questions\n============\n\nNot that it matters much, but the authors might want to consider a different acronym. I would avoid CORAL since it's already quite popular (in general) and already has a notable presence in some parts of ML where it is known as \"correlation alignment\", for instance [1] (one of several top search results). \n\nBig nitpick, \"THE optimal policy\", should be \"some\" or maybe add a quick word to say we'll only consider one arbitrary optimal policy from this point on.\n\nOn a related topic, what impact does having multiple optimal policies have? I would expect that it would only make some definitions and theorem statements more tedious. If the authors are willing to indulge my curiosity, do you think considering multiple policies could offer anything useful, for instance, looser occupancy validity requirements, in some interesting special cases with many such policies?\n\np. 5, \"the objective (15)\", should this be a reference to (2) instead?\n\nI've mostly seen augmented lagrangian methods with a coefficient scaling the penalty term which typically grows over time. Is it's omission at all relevant or is it simply an irrelevant implementation detail (in the context of this work)?\n\np. 6, I wasn't able to allocate enough time to figure out the steps going from (10) to (12). Could the authors provide some additional details or point me to a similar derivation in related work?\n\nSomewhat tangential to this work, but the discussions related to the significance of the occupancy validity reminded me of recognizers [2], which was proposed as a way to describe target policies in the context of off-policy learning. The basic idea is that you can define the policy by probabilistically accepting or rejecting actions sampled by the behavior policy. This offers leads to better behaved off-policy learning than standard importance sampling. This is most likely the result of constraining target policies, but I wonder if this work's insight and analysis could reveal something interesting? Maybe new useful ways to constrain the target policies in cases where we don't seek optimality (e.g., in off-policy learning)?\n\n\n[1] Sun, B., Feng, J. and Saenko, K., 2017. Correlation alignment for unsupervised domain adaptation. In Domain Adaptation in Computer Vision Applications (pp. 153-171). Springer, Cham.\n[2] Precup, Doina, Cosmin Paduraru, Anna Koop, Richard S. Sutton, and Satinder Singh. \"Off-policy learning with options and recognizers.\" Advances in Neural Information Processing Systems 18 (2005).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Bc2xIevWkpf", "reviewer": "Reviewer_f5U7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper addresses the offline reinforcement learning problem with general function approximations and the partial coverage of offline data. Existing works either are computationally intractable or are suboptimal in statistical rates. The paper presents the first offline RL algorithms that are practical and optimal in regret under the assumption of single-policy concentrability. To obtain these properties, the paper uses the marginalized importance sampling (MIS) formulation combined with the augmented Lagrangian method.  \n\n\n\n", "summary_of_the_review": "This is a good paper. I recommend the acceptance. ", "strength_and_weaknesses": "Strengths:\n- The paper addresses an important problem of offline reinforcement learning.\n- The theoretical results are original in this setting. \n- While the MIS formulation has been used in PRO-RL (Zhan et al., 2022) to achieve the sample efficiency of offline RL under weak assumptions, this paper shows that the MIS formulation combined with the augmented Lagrangian method can reach the optimality in sample efficiency of offline RL. This is an interesting result. \n\nWeaknesses:\n- The paper makes many typos. For example, the first sentence in Section 3.2: \"... cements...\"; a typos in Proposition 2; $B_v$ has not been defined in Theorem 2;...\n- It would be nice if the authors can explain intuitively why replacing behavior regularization with the augmented Lagrangian is key for the optimality of their proposed algorithms.\n- The authors claim that their algorithms are practical but do not provide any experiments. \n\n\n     ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%