{'fraction_non_alphanumeric': 0.05570308253746409, 'fraction_numerical': 0.016491963661774984, 'mean_word_length': 4.215940385549976, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 24, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangian

Offline reinforcement learning (RL), which refers to decision-making from a previously-collected dataset of interactions, 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."


Introduction
The goal of offline RL is to design agents that learn to achieve competence in a task using only a previously-collected dataset of interactions (Lange et al., 2012). Offline RL is a 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 is dangerous, impractical, costly, or even impossible (Levine et al., 2020). Despite this, offline RL has not yet been truly successful in practice (Fujimoto et al., 2019;Levine et al., 2020) 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 et al., 2015;Degrave et al., 2022;Fawzi et al., 2022), or expert demonstrations (Vinyals et 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 literature has focused on addressing this challenge through developing conservative algorithms, which aim at picking a 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 and 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., 2020Yu et al., , 2021; see Appendix A for further discussion on related work. 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 and Sun, 2021;Song et al., 2022), which characterizes the distribution shift between offline data and occupancy of a target (often optimal) policy, in contrast to all-policy concentrability commonly used in earlier works (Scherrer, 2014;Chen and Jiang, 2019;Liao et al., 2020;Zhang et al., 2020a;Xie and Jiang, 2021). Within this framework and in the tabular and linear function 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 and Huang, 2020) or selecting the most pessimistic option among those that fall within the confidence region implied by the offline data (Uehara and Sun, 2021;Xie et al., 2021;Chen and Jiang, 2022). However, uncertainty quantifiers are difficult to obtain when non-linear function approximation are used and existing heuristics are empirically observed to be unreliable (Rashid et al., 2019;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-based methods, but leave achieving the optimal statistical rate of 1/ √ N , where N is the size of the offline dataset, as an open problem.
Among all, the marginal importance sampling (MIS) methods, which aim at learning weights that estimate the distribution shift between induced policy occupancy and data distribution, lend themselves well to the single-policy concentrability framework. Though more popular in off-policy evaluation (Liu et al., 2018;Xie et al., 2019;Uehara et al., 2020;Zhang et al., 2020b), MIS has also been used for conservative offline RL such as in AlgaeDICE (Nachum et al., 2019b) and Op-tiDICE (Lee et al., 2021) algorithms, both of which incorporate behavior regularization. Recently, Zhan et al. (2022) theoretically studied a variant of OptiDICE, showing that MIS with behavior regularization enjoys finite-sample guarantees (though achieving a suboptimal 1/N 1/6 rate) and circumvents certain fundamental difficulties observed in value-based offline RL with function approximation (Du et al., 2019;Wang et al., 2020Wang et al., , 2021Weisz et al., 2021;Zanette, 2021;Foster et al., 2021).

Contributions and results
Motivated by the benefits offered by MIS, we study designing statistically optimal offline learning algorithms under the MIS formulation and in the general function approximation and single-policy concentrability setting. We conduct theoretical investigations and design algorithms starting from multi-armed bandits (MABs), going forward to contextual bandits (CBs), and finally Markov decision processes (MDPs). We measure the performance of different algorithms by characterizing the value suboptimality of the learned policy with respect to the optimal policy. 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 behavior regularization as a 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.
The following informal theorem states our results on unregularized MIS and MIS with behavior regularization (PRO-MAB Algorithm 2), which is a special case of PRO-RL algorithm of Zhan et al. (2022). Formal statements can be found in Propositions 1 and 2 and Theorem 1.
Theorem (informal). The following statements hold for offline learning in MABs with function approximation and single-policy concentrability.
(I) There exists a multi-armed bandit instance where the unregularized MIS fails to achieve a suboptimality that decays with the sample size N .
(III) If one searches only over the space of importance weights that induce policy occupancies that are valid probability distributions, then unregularized MIS achieves O(1/ √ N ) suboptimality.
The first part of the above informal theorem states that MIS, in its original form and without any regularization, fails even in multi-armed bandits. For the second part, we conduct a tight analysis of MIS with behavior regularization, demonstrating an optimal rate of 1/ √ N and improving over the 1/N 1/6 rate shown by Zhan et al. (2022). In our analysis of PRO-MAB, we find that the key to the success of the regularized MIS algorithm is near-validity of the learned occupancy. In the MAB setting, the validity constraint simply requires the learned occupancy to be a probability distribution, i.e., d w := a w(a)µ(a) = 1, where a represents an arm (action), w denote importance weights, and µ is the data distribution. With a proper choice of regularization hyperparameter, we show that behavior regularization enforces learned occupancy to be nearly valid: d w = Ω(1), that is the normalization factor d w is at least a positive constant. Finally, we prove that if occupancy validity constraint is satisfied (for example by eliminating all candidate weights w where a w(a)µ(a) = 1), then the unregularized MIS algorithm enjoys optimal sample complexity.
Given the fact that the occupancy validity is the constraint of the optimization problem solved by MIS (see (3)), we ask whether there are any methods for solving an empirical optimization problem that find more constraint-adhering solutions compared to those yielded by the Lagrange multiplier method 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, is a natural choice for our purpose. The ALM term can be easily estimated from offline data and forms our algorithm conservative offline MAB with augmented Lagrangian (Algorithm 2). We show that the ALM results in d w = Ω(1), ensuring near-validity of estimated occupancy and leading to the following guarantee. The formal statement is given in Theorem 2.
Our algorithm offers benefits over PRO-MAB such as eliminating the need for choosing the regularization function and only requiring single-policy concentrability instead of the two-policy requirement of PRO-MAB, which can be strong as we discuss in an example in Section 5.4. Additionally, behavior regularization introduces bias in the solution even with infinite data (Chen and Jiang, 2022) and the bias-variance tradeoff must be carefully handled. On the other hand, ALM merely enforces the optimization constraints and leads to provably unbiased solutions (Lemma 13). More importantly, as we discuss shortly, going beyond the single-state MAB setting, convergence rate of behavior regularization becomes suboptimal while ALM maintains the optimal rate.

Contextual bandits.
In offline CBs, we analyze two approaches: MIS with behavior regularization and an extension of our ALM-based algorithm. We state our results in the following informal theorem, with formal statements given in Proposition 3 and Theorem 3.
Theorem (informal). The following statements hold for offline learning in contextual bandits with function approximation and single-policy concentrability.
Informally, the failure of PRO-CB to achieve the optimal rate is because the regularization parameter has to be small to control bias, but such small regularization is not strong enough to ensure the validity of learned occupancy in important states. Therefore, one must choose larger regularization, leading to an overall suboptimal rate. Prior works Chen and Jiang (2022); Cheng et al.
(2022) also allude to this phenomenon, explaining that regularizers appear to be the culprit behind suboptimal rates. In CB, the occupancy validity constraints require conditional occupancy to be a valid probability distribution in most states. In Algorithm 3, 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 the ALM yields the above guarantee on our algorithm.
MDPs. Validity constraints in MDPs ensure that the learned state occupancy d w (s) := a w(s, a)µ(s, a) is close to the actual state occupancy d πw (s), where π w is the policy computed from weights w. 1 Unlike MABs and CBs, directly enforcing this constraint in MDPs results in an ALM term that cannot be easily estimated from offline data. We address this difficulty by expressing the ALM term in a variational form. From there, we derive model-based and one model-free variants an algorithm called conservative offline RL with augmented Lagrangian (CORAL), that enjoys the following performance upper bound.

Theorem (informal).
Model-based and model-free CORAL both achieve O(1/ √ N ) suboptimality in solving offline RL with general function approximation and single-policy concentrability.
The formal statement of the above theorem is provided in Theorem 4. This marks CORAL 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 CORAL is baked into the MIS formulation and further supported by the ALM: bounded MIS weights prevent the learned occupancy to deviate significantly from data distribution, and the ALM ensures closeness of the learned and actual occupancies. Thus when combined, CORAL learns a policy whose actual occupancy is close to the data distribution.
We proved that the ALM when combined with MIS 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 and Nemirovski, 2022). Our theoretical findings can explain the empirical observations of Yang et 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 a theoretically-founded way of introducing ALM in offline RL and our analysis shows that ALM also leads to optimal sample complexity.

Background
Markov decision process. An infinite-horizon discounted MDP is described by a tuple M = (S, A, P, R, ρ, γ), where S is the state space, A is the action space, P : S×A → ∆(S) is the transition kernel, R : S × A → ∆([0, 1]) encodes a family of reward distributions with r : S × A → [0, 1] as the expected reward function, ρ : S → ∆(S) is the initial state distribution, and γ ∈ [0, 1) is the discount factor. We assume S and A are finite however, our results do not depend on their cardinalities and can be naturally extended to infinite sets. A stationary (stochastic) policy π : S → ∆(A) specifies a distribution over actions in each state. Each policy π induces an occupancy density over stateaction pairs d π : S × A → [0, 1] defined as d π (s, a) := (1 − γ) ∞ t=0 γ t P t (s t = s, a t = a; π), where P t (s t = s, a t = a; π) denotes visitation probability of state-action pair (s, a) at step t, starting at s 0 ∼ ρ(·) and following π. We also write d π (s) = a∈A d π (s, a) to denote the discounted state occupancy. Additionally, operator P π is applied to any function u : S × A → R and is defined as An important quantity is the value a policy π, which is the discounted sum of rewards V π (s) := E ∞ t=0 γ t r t | s 0 = s, a t ∼ π(·|s t ) ∀ t ≥ 0 starting at state s ∈ S. Similarly, one can define the Q-function of policy as Q π (s, a) := E ∞ t=0 γ t r t | s 0 = s, a 0 = a, a t ∼ π(·|s t ) ∀ t ≥ 1 . We use the notation J(π) := (1 − γ) E s∼ρ [V π (s)] = E s,a∼d π [r(s, a)] to represent a scalar summary of the performance of a policy π. We denote by π ⋆ the 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-collected offline dataset Here, r i ∼ R(s i , a i ), s ′ i ∼ P (· | s i , a i ), and we assume s i , a i pairs are generated i.i.d. according to a data distribution µ ∈ ∆(S × A).
To streamline the analysis, we assume that the conditional distribution µ(a|s) is known. 2 The goal of offline RL is to learn a policyπ based on the offline dataset so as to minimize the sub-optimality with respect to the optimal policy π ⋆ , i.e., J(π ⋆ ) − J(π), with high probability.
Marginalized importance sampling. In this paper, we consider the marginal importance sampling (MIS) formulation that aims at learning importance weights w(s, a) so as to represent stateaction occupancy when multiplied by the offline data distribution. We adopt the following notation: (1) We define the policy induced by weights w as Offline data coverage assumption. We design and analyze our algorithms within the singlepolicy concentrability framework (Rashidinejad et al., 2021), stated below.
Definition 1 (Single-policy concentrability). Given a policy π, define C π to be the smallest constant that satisfies d π (s,a) µ(s,a) ≤ C π for all s ∈ S and a ∈ A.
C ⋆ := C π ⋆ captures the coverage of π ⋆ in the offline data and is much weaker than the widely used all-policy concentrability that assumes bounded max π C π (Scherrer, 2014). In Appendix A, we present a detailed discussion on different coverage assumptions used in offline RL.
Notation. Given a set S, we write |S| to represent its cardinality and ∆(S) to denote the probability simplex over S. For a function class W, we write |W| to denote its cardinality (discrete) or covering number (continuous). We use the notation x y when there exists a constant c > 0 such that x ≤ cy and x ≍ y if constants c 1 , c 2 > 0 exist such that c 1 |x|≤ |y|≤ c 2 |x|. We write f (x) = O(g(x)) if M > 0, x 0 exist such that |f (x)|≤ M g(x) for all x ≥ x 0 . Define clip(x, a, b) max{a, min{x, b}} for x, a, b ∈ R. We write f (x) = Ω(g(x)) if there exists some positive real number M and some x 0 such that |f (x)|≥ M g(x) for all x ≥ x 0 .

Multi-armed bandits
We start by considering the offline learning problem in the multi-armed bandit (MAB) setting, which is a special case of MDPs with γ = 0, |S|= 1, and . The goal of offline learning in MABs can be described as the following constrained optimization problem, where d represents occupancy over actions (arms) This is the special case of the well-known linear program for reinforcement learning (Puterman, 2014).

Primal-dual regularized offline bandits
To solve (3), the MIS approach with behavior regularization defines importance weights according to w(a) = d(a)/µ(a) and converts the problem (3) to its dual form by introducing the Lagrange multiplier v: The last term in (4) is the behavior regularizer that characterizes the f -divergence between the learned occupancy d and data distribution µ, with α determining the strength of regularization. This term was originally proposed to induce conservatism by keeping the learned policy close to behavior policy (Nachum et al., 2019b;Lee et al., 2021). The optimization problem (4) satisfies strong duality and we denote optimal solutions to the primal and dual variables by w ⋆ α v ⋆ α , whose characteristics are established in Appendix B.1. Importantly, when α = 0, weights w ⋆ := w ⋆ 0 induce an optimal policy and v ⋆ := v ⋆ 0 becomes the optimal value (reward). Approximating w and v to belong in classes W ⊆ R + |A| and V ⊆ R and solving an empirical approximation of (4) yields Algorithm 1, which we call primal-dual regularized offline MAB (PRO-MAB) as it is a special case of PRO-RL algorithm of Zhan et al. (2022).
Algorithm 1 Primal-dual regularized offline multi-armed bandits (PRO-MAB) , classes V and W, function f (·), parameter α. 2: Find a solutionŵ,v to the following problem 3: Return:π = πŵ One might wonder whether the unregularized algorithm (α = 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, i.e., w(a) = d(a)/µ(a) ≤ B w for any w ∈ W. In the following proposition, we show that the answer is negative and there exist an offline MAB instance in which the unregularized MIS finds a policy that suffers from a constant suboptimality. The proof is provided in Appendix B.2.
Proposition 1 (Unregularized MIS fails in MABs). Assume 0 ≤ w(a) ≤ B w for any w ∈ W and |v|≤ B v for any v ∈ V. Further suppose realizability of w ⋆ ∈ W and v ⋆ ∈ V and concentrability of optimal policy π ⋆ := π w ⋆ . For any N ≥ 2, there exists a two-armed offline bandit instance where policyπ returned by Algorithm 1 with α = 0 satisfies J(π ⋆ )− J(π) = 1/6 with a constant probability.
We note that Zhan et al. (2022) also argues the failure of the unregularized algorithm by giving a counterexample in the MDP setting. We discuss this example in detail in Section 5.4. Proposition 1 reveals additional insights to the MDP failure example: the objective (5) with α = 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 MIS algorithm, we conduct a tight analysis of PRO-MAB with α > 0. In the next theorem, we prove that under similar assumptions as Zhan et al. (2022) and with a proper choice of hyperparameter α, PRO-MAB returns a policy that enjoys near-optimal sample complexity.
Theorem 1 (Suboptimality of Algorithm 1). Let f : R → R be M f -strongly convex, differentiable, and non-negative with bounded values |f (x)|≤ B f and bounded first-order derivative |f ′ (x)|≤ B f ′ . Assume 0 ≤ w(a) ≤ B w for any w ∈ W and |v|≤ B v for any v ∈ V. Fix δ ≥ 0 and set Suppose realizability of w ⋆ α ∈ W and v ⋆ α ∈ V and concentrability of π ⋆ := π w ⋆ and π ⋆ α := π w ⋆ α for the α given in (6). Then, with probability at least 1 − δ, policyπ returned by Algorithm 1 achieves To our knowledge, this is the first statistically optimal guarantee for a practical offline MAB algorithm with function approximation and partial coverage and improves over the 1/N 1/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 B.3. Zhan et al. (2022) bounds policy suboptimality by α + 1/(α 1/2 N 1/4 ). Here, the first term α in the bound stems from the bias caused by the regularizer. The second term emerges by connecting the difference betweenŵ and w ⋆ α to the statistical approximation error via strong convexity of L MAB α induced by behavior regularization, which is inversely related to α. Optimizing the bound over α gives the final 1/N 1/6 guarantee. In contrast, our analysis connects suboptimality to occupancy validity. In particular, we prove that suboptimality is bounded by (α + 1/ √ N )/dŵ, where dŵ = aŵ (a)µ(a). We then show that setting α ≍ 1/ √ N is sufficient to ensure near-validity of occupancy dŵ = Ω(1), which yields the statistically optimal rate.
We observe a similar phenomenon in Proposition 1 that small d w for certain w ∈ W can cause the unregularized MIS algorithm to fail. In the following section, we investigate this phenomenon further, leading to a new offline learning algorithm.

Augmented Lagrangian replaces behavior regularization
The next proposition further affirms the importance of occupancy validity. This result shows that if one ensures that the optimization constraint is satisfied, such as by searching only over the weights that induce valid occupancies, then the unregularized algorithm achieves an optimal rate. Proof of this result can be found in Appendix B.4.
Proposition 2 (Constraint satisfaction is sufficient for unregularized MIS in MAB). Assume as in Theorem 1. Letπ be the output of Algorithm 1 with α = 0 and assume that a µ(a)ŵ(a) = 1. Then, for any fixed δ > 0, policyπ achieves the following bound with probability of as least 1 − δ Motivated by the discussion above, we take a step back and ask: are there any other methods for solving constrained optimization problems that find more constraint-satisfying solutions when applied to the empirical approximation of the original problem? A promising candidate is the augmented Lagrangian method (ALM) which adds a quadratic loss on the constraints to the objective. Applied to the offline bandits problem (3), ALM forms the following objective, whose empirical version leads to Algorithm 2.
Algorithm 2 Conservative Offline MAB with Augmented Lagrangian Since the last term in (7) is zero for the optimal solution w ⋆ , the saddle point solution to (7) is equal to the solution to the original constrained optimization problem; see Lemma 13 for a general result.
The following theorem establishes an upper bound on the suboptimality of the policy returned by Algorithm 2. This theorem is a special case of Theorem 3, whose proof is given in Appendix C.3.
Theorem 2 (Suboptimality of Algorithm 2). Assume that 0 ≤ w(a) ≤ B w for any w ∈ W and |v|≤ B v for any v ∈ V. Further suppose realizability of w ⋆ ∈ W and v ⋆ ∈ V and concentrability of π ⋆ = π w ⋆ . For any fixed δ > 0, policyπ returned by Algorithm 2 achieves the following bound with probability of at least With a tabular deterministic parameterization of W, choosing V = [0, 1], δ = 1/N , and setting B w = C ⋆ to the smallest possible value, the bound in (9)  In the proof of Theorem 2, we show that ALM results in near-validity ofŵ by ensuring that dŵ = Ω(1), leading to the optimal suboptimality rate. Importantly, Algorithm 2 does not include any explicit form of conservatism through regularizers or uncertainty quantifiers. Colloquially, the MIS formulation and boundedness of W elements ensure that dŵ(a)/µ(a) =ŵ(a) ≤ B w . The ALM term ensures that dŵ is lower bounded by a constant c, which means that the actual occupancy over the armsπ(a) = dŵ(a)/dŵ ≤ dŵ(a)/c. Thus, Algorithm 2 finds a policyπ that satisfieŝ i.e., it it finds a policy whose actual occupancy is supported by the behavior data distribution µ. Algorithm 2 offers several benefits compared to PRO-MAB: it only requires π ⋆ -concentrability instead of the π ⋆ , π ⋆ α -concentrability requirement of PRO-MAB, removes the need to design regularization function f and adjust α, 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 regularization provably fails to achieve the optimal statistical rate while ALM maintains optimality.

Contextual bandits
The problem of offline contextual bandits (CB) is a special case of offline RL with γ = 0 and offline The linear programming constrained optimization problem for CB is given by

Analysis of the primal-dual regularized offline contextual bandits
Similar to the MAB setting, the offline learning problem (10) can be turned into the primal-dual form with behavior regularization, leading to the primal-dual regularized offline CB (PRO-CB). Details of the PRO-CB objective, optimal primal and dual variables w ⋆ α , v ⋆ α , and pseudocode are provided in Appendix C.1. In the following proposition, we prove a performance lower bound on the PRO-CB algorithm, whose proof is presented in Appendix C.2.
Proposition 3 (Performance lower-bound on Algorithm 6 (PRO-CB)). Let f : R → R be M fstrongly convex, differentiable, and non-negative with bounded values |f (x)|≤ B f and bounded first- Letπ be the output of Algorithm 6. Further, assume that N ≥ n 0 , where n 0 is a polynomial function of Proposition 3 shows that behavior regularization fails to achieve the optimal 1/ √ N rate regardless of α, even under boundedness, realizability, and concentrability assumptions. The main takeaway of our construction in the proof of Proposition 3 is that ensuring occupancy validity aŵ (s, a)µ(a|s) = Ω(1) for nearly all states appears to be critical in achieving the optimal rate. Yet, without introducing a significant bias, behavior regularization is insufficient to induce the state-wise occupancy validity.

Conservative offline CB with augmented Lagrangian
To enforce the occupancy validity constraints, we propose to incorporate augmented Lagrangian in the following form: Notice that when |S|= 1, (11) simplifies to the ALM objective (4) in the MAB setting. The ALM term can be understood as follows: each element in the ALM sum encourages the validity of occupancy in each state a w(s, a)µ(a|s) ≈ 1, and the elements are weighted according to the true state distribution since validity is more important in states that are actually more likely to be visited. As before, denote by w ⋆ the optimal solution to (11), which is equal to the optimal solution of the original constrained optimization problem. Additionally, we define v ⋆ (s) := V ⋆ (s) to be equal to the optimal reward at each state s ∈ S.
Algorithm 3 Conservative Offline CB with Augmented Lagrangian Solving a sample-based approximation to objective (11) and using function approximation for w and v gives us conservative offline CB with augmented Lagrangian as given in Algorithm 3. We analyze the suboptimality of Algorithm 3 and present the following theorem, showing that the ALM achieves the optimal rate without requiring behavior regularization. The proof of this theorem can be found in Appendix C.3.
Theorem 3 (Suboptimality of Algorithm 3). Assume 0 ≤ w(s, a) ≤ B w for w ∈ W and v(s) ≤ B v for v ∈ V. Moreover, suppose realizability of w ⋆ ∈ W and v ⋆ ∈ V and concentrability of π ⋆ = π w ⋆ . For any fixed δ ≥ 0, policyπ returned by Algorithm 3 achieves the following suboptimality bound with probability of at least 1 − δ

Markov decision processes
We now turn our focus to offline RL. In addition to the offline dataset of interactions, we assume access to a dataset samples from the initial distribution ρ, similar to prior works (Lee et al., 2021;Zhan et al., 2022). The linear programming formulation of RL (Puterman, 2014) solves the following constrained optimization problem: The constraints are known as the Bellman flow equations and restrict the search to the space of valid occupancy distributions d π that can be induced in the MDP by running a policy π.

Conservative offline RL with augmented Lagrangian
Motivated by the success of ALM in bandits, we propose the following extension to offline RL: where e v (s, a) := r(s, a) + γ s ′ P (s ′ |s, a)v(s ′ ) − v(s). One can check that the first two terms equate to the Lagrange dual of (13) and the last term is a generalization of the ALM terms in bandits. Each iterand of the ALM sum encourages the occupancy d w (s) to be close in ratio to the actual occupancy d πw (s) in each state and as before, the ALM iterands are weighted according to actual state visitations d πw (s). Our particular ALM construction can be intuitively understood as follows: the MIS formulation learns bounded weightsŵ(s, a) = dŵ(s, a)/µ(s, a) ≤ B w , and the ALM term ensures that dŵ(s, a)/d πŵ (s, a) = dŵ(s)/d πŵ (s) = Ω(1) for most states, which translates to d πŵ (s, a)/µ(s, a) B w . The ALM term in (14) is difficult to estimate as it involves an expectation over the unknown occupancy d πw and computing the ratio d w (s)/d πw (s). In the following section, we resolve this difficulty by converting the ALM term into a variational form.

Estimating the ALM term and CORAL algorithm
We view the ALM term as the negative f -divergence 3 between d w and d πw with f (x) := (x − 1) 2 and express it in the variational form (Nguyen et al., 2010): Here, f * is the convex conjugate of f and we used the fact that ] is the value of π w in the same MDP but with rewards f * (x(s, a)). Define u as the fixed point of the following Bellman equation Since u(s, a) is the state-action value function (Q-function) of π w with rewards f * (x(s, a)), we can rewrite (15) as Equation (17) involves expectations over ρ and µ, which can be estimated empirically using interaction dataset D and dataset of initial states D 0 , yet, it also includes a term that involves the transition operator P πw . In the rest of this section, we discuss model-free and model-based methods for estimating the term involving the transition operator P πw . We include some details on practical implementations in Appendix D.1.

Model-based CORAL
The model-based ALM population objective is obtained by directly substituting the variational form (17) in the original objective (14) max Note that optimal solution w ⋆ of (14) is also the optimal solution to (19) since d w ⋆ = d π w ⋆ (c.f. Lemma 13).
To obtain a sample-based approximation of the above objective, we assume access to a realizable function class P that contains the true transitions and an additional dataset on interactions Given D m , we obtain a maximum likelihood estimate of transitions and then approximate the expectations using D 0 and D. We assume access to the independent dataset D m to simplify the proofs and practical implementations can reuse interaction dataset D instead. This leads to Algorithm 4, which we call model-based conservative offline RL with augmented Lagrangian (CORAL).

Model-free CORAL
As an alternative, we consider developing a model-free that uses a single-sample estimate of f −1 * u(s, a) − γ(P πw u)(s, a) . Using a single-sample estimate leads to the infamous double sampling problem (Baird, 1995). To circumvent this difficulty, in Appendix D.2 we use the dual embedding trick in Nachum et al. (2019a) to derive the following model-free population objective where g * (x) := x + 2 + 1/x. Empirical approximation of objective (20) leads to model-free CORAL presented in Algorithm 5.

CORAL performance upper bound
Theorem 4 shows that both variants of CORAL enjoy optimal rates; see Appendix D.3 for the proof.
Moreover, for any fixed δ ≥ 0, the following statements hold: ζ,L }. Then,π returned by Algorithm 5 achieves In Theorem 4, we make realizability assumptions on u ⋆ w ∈ U for w ∈ W and ζ ⋆ w ⋆ ,u ∈ Z for u ∈ U . Such assumptions are common in the theory of RL with function approximation (Munos and Szepesvári, 2008;Xie et al., 2021;Jiang and Huang, 2020) and removing them can be difficult or even impossible. For example, Bellman completeness is proved to be necessary for polynomial sample complexity in value-based methods (Foster et al., 2021). Recently, Zhan et al. (2022); Chen and Jiang (2022) propose algorithms that only require optimal solution realizability, however, these algorithms are either computationally intractable or statistically suboptimal.

Example: Behavior regularization vs. augmented Lagrangian
We examine a hard offline RL instance (  (14) with α = 0, fails to distinguish between w 1 and w 2 even with infinite data since the objectives at w 1 and w 2 are exactly equal.

Behavior regularization. Consider an instantiation of PRO-RL with regularizer
, PRO-RL picks the wrong weight w 2 and thus suffers from a constant suboptimality. However, note that this does not contradict theoretical guarantees of PRO-RL as these guarantees additionally assume concentrability of π ⋆ α . Intuitively, behavior regularization causes π ⋆ α to be more stochastic and thus requiring µ(s, a) > 0 for more states and actions. Here, since µ covers both (A, L) and (A, R), behavior regularization causes π ⋆ α (R|A) > 0 and thus d π ⋆ α (C) > 0. Therefore to handle the MDP in Figure  1, PRO-RL additionally requires µ(C) > 0 to satisfy π ⋆ α -concentrability.
ALM. In this example, ALM successfully picks the optimal w 1 , as it avoids a mismatch between the actual and learned occupancies. This is because in (14) the ALM term is zero at w 1 due to realizability whereas at w 2 , it has a lower bound Figure 1: The agent always starts from state A. Action L leads to state B, from where the agent collects a +1 reward. Action R leads to state 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, µ(B) = 1/4, µ(C) = 0, which satisfies π w 1 -concentrability.

Discussion
We present a set of practical and statistically optimal algorithms for offline MAB, CB, and RL, under general function approximation and single-policy concentrability. Our algorithms are designed within the MIS formulation combined with a novel application of the augmented Lagrangian method. Importantly, our optimality guarantees hold under MIS combined with ALM alone, without any additional 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. 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. Other interesting future directions include conducting empirical evaluations of ALM, examining the possibility of removing strong realizability assumptions, and investigating practical and optimal offline RL algorithms whose guarantees hold under milder variants of single-policy concentrability.
Jinglin Chen and Nan Jiang. Offline reinforcement learning under value and density-ratio realiz

A Related work
We covered a number of related works in the introduction and throughout the paper. In this section, we review more related literature.

A.1 Concentrability assumptions
The lack of sufficient coverage in the offline dataset is one of the main challenges in offline RL. In RL theory, dataset coverage has often been characterized by concentrability definitions (Munos, 2007;Scherrer, 2014). Earlier works on offline RL impose all-policy concentrability on the density ratio for all states and actions (

A.2 Conservative offline RL
A 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 are applied either explicitly ( Most related to our work are methods that focus on provable conservative offline RL under general function approximation and partial coverage. Uehara and Sun (2021) propose a pessimistic model-based algorithm that under a generalization of single-policy concentrability to bounded TV distance ratio, enjoys a 1/ √ N rate but is computationally intractable. The work of Xie et al. (2021) presents a pessimistic model-free algorithm under a variant of single-policy concentrability framework that requires a bounded ratio of average Bellman error and Bellman completeness. While the original version of the algorithm achieves the optimal 1/ √ N rate, it is computationally intractable. A practical version of the algorithm is presented and has a suboptimal 1/N 1/5 guarantee. Another related work by Chen and Jiang (2022) studies MIS combined with value function approximation under π ⋆ -concentrability and proves a 1/ gap(Q ⋆ )N rate, yet the guarantee degrades with Q ⋆ gap and the algorithm is computationally intractable. Cheng et al. (2022) propose an adversarially trained actor-critic method that enjoys provable 1/N 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.

B Proofs for multi-armed bandits
We start in Appendix B.1 by characterizing the bias caused by adding the behavior regularization in (4). In Appendix B.2, we prove Proposition 1 that demonstrates the failure of unregularized MIS for solving offline MABs, even when the optimal solutions are realizable and the optimal policy is covered in the offline data. Appendix B.3 is devoted to the proof of Theorem 1, which gives a tight performance upper bound of the PRO-MAB algorithm. Finally in Appendix B.4, we prove Proposition 2, showing that constraint satisfaction is sufficient for the success of unregularized MIS.

B.1 Solutions to the primal-dual regularized objective
In the following lemma, we characterize the optimal solution (w ⋆ α , v ⋆ α ) to the behavior-regularized population objective (4) as well as the suboptimality of the policy induced by w ⋆ α . Lemma 1 (Regularized primal-dual solutions, MAB). Let f be differentiable, strictly convex, nonnegative, and bounded by B f . Denote r ⋆ := max a∈A r(a). Then, the following statements hold: where w ⋆ is the importance weight corresponding to an optimal policy; Part (I) follows directly by strong duality. For part (II), notice that KKT conditions imply the following relation between w ⋆ α (a) and v ⋆ α : Since f is strictly convex, f ′ is a monotonically increasing function. Therefore, the optimal arm a ⋆ has the largest w ⋆ α (a), which should be nonzero due to realizability of w ⋆ α . In other words, We now proceed to find a bound on f ′ (w ⋆ α (a ⋆ )). Since w ⋆ α is the optimal solution to (4), it must satisfy the constraint where the last inequality stems from the single-policy concentrability assumption of π * . Since f ′ is an increasing function, we have f ′ (w ⋆ α (a ⋆ )) ≤ f ′ (C ⋆ ), which combined with (22) yields the following Moreover, the convexity of f immediately gives the upper bound on v ⋆ α ≤ r ⋆ , which completes the proof of part (II).
We now prove the last part. Since w ⋆ α is the optimal solution to the regularized population objective (4), by strong duality, we have (1) and we used the fact that E a∼µ [w ⋆ α (a)] − 1 = E a∼µ [w ⋆ (a)] − 1 = 0. Therefore, the suboptimality of π ⋆ α can be bounded as follows where in the second to last inequality we used the non-negativity of f and in the last equality, we used the boundedness of f .

B.2 Proof of Proposition 1
Consider a 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 a Bernoulli distribution: • Data distribution: We consider a scenario where most data are concentrated on the optimal arm: Here, the single-policy concentrability coefficient is C ⋆ = 1/µ(1) and is finite for N > 2. Let N (a) denote the number of samples on arm a. To obtain upper and lower bounds on N (a), we resort to the following lemma, which is a direct consequence of the Chernoff bound for binomial variables.
Consider the case where all N (a) samples on the second arm observe a reward of 1, which happens with a probability of at least 1 3 5 as we conditioned on the event that 1 ≤ N (2) ≤ 5. We now computeŵ by solving the empirical objective (5) with α = 0. Note that since |V|= 1, it suffices to computeŵ = arg max w∈WL MAB 0 (w, v = 1/2). We havê Since we conditioned on the event with N (2) ≥ 1, solving the optimization problem max w∈WL MAB 0 (w, v = 1/2) findsŵ = (0, B w ), leading to a policy that picks the second arm with probability one. Therefore, with constant probability of 0.4 × 1/3 5 > 0.001, we have

B.3 Proof of Theorem 1
Before embarking on the main proof, we present two lemmas related to the primal-dual regularized approach. The first lemma shows the closeness of population objective (4) to its empirical approximation used in Algorithm 2, which is a direct consequence of Hoeffding's inequality. We also show that closeness of objectives results in the closeness of w ⋆ α andŵ, which are respectively the optimums to (4) and (5). The proof of this lemma is deferred to the end of this subsection.
Lemma 3 (Empirical and population closeness, PRO-MAB). Fix δ > 0 and define For any w ∈ W and v ∈ V, the following bounds hold with probability at least 1 − δ The second lemma finds a lower bound on the occupancy normalization factor dŵ = aŵ (a)µ(a) enforced by the behavior regularization.
Lemma 4 (Occupancy validity enforced by behavior regularization). Let f be an M f -stronglyconvex function and fix δ > 0. Then, with probability at least 1 − δ, one has For the rest of this proof, we condition on the high probability events of Lemmas 3 and 4. Define By part (II) of Lemma 3, we have L MAB Recall from Lemma 1 that we have . Thus, combined with (25), we write where in the second line we used the bounds |f (x)|≤ B f and dŵ ≤ B w . Note that setting α = 16ǫ MAB stat,1 /M f , Lemma 4 asserts that dŵ ≥ 1/2. Since dŵ ≥ 1/2, the learned policy is written aŝ π =ŵ(a)µ(a)/dŵ. With simple algebraic manipulations, we find the following expression for the suboptimality ofπ with respect to π ⋆ α : Let ǫ reg = J(π ⋆ ) − J(π ⋆ α ) = r ⋆ − J(π ⋆ α ) denote the suboptimality suffered due to behavior regularization. Suboptimality J(π ⋆ α ) − J(π) can be expressed as We use the above inequality to bound the suboptimality with respect to the optimal policy: Recall that we have 1/dŵ ≤ 2 and that ǫ reg is bounded by αB f by Lemma 1. Therefore, where the penultimate inequality relies on the bound derived in (26).
Proof of Lemma 3.L MAB α (w, v) is an empirical average over independent and bounded random variables, where the bound on individual variables is computed as We write Each term is bounded as follows: • T 1 = 0 because w ⋆ α satisfies the constraint a w ⋆ α (a)µ(a) = 1 and for any v 1 , v 2 we have • T 2 ≤ ǫ stat due to Lemma 3.
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 M f -strongly-convex, the function L MAB α (v ⋆ α , w) is αM f -stronglyconcave with respect to w and norm · 2,µ . Furthermore, since w ⋆ α = arg max w L MAB The above bound along with the bound on L MAB which completes the proof.

B.4 Proof of Proposition 2
Consider the difference between population objective with α = 0 at w ⋆ 0 = w ⋆ andŵ, which is bounded by Lemma 3: We have E a∼µ [w ⋆ (a)] = 1 due to realizability and E a∼µ [ŵ(a)] = 1 is our assumption. Thus the second term in (28) is zero. Moreover, note thatπ(a) =ŵ(a)µ(a)/E a∼µ [w(a)] =ŵ(a). Substituting the expression for ǫ MAB stat,α from (23) with α = 0, we obtain where we used the fact that B w ≍ B w + 1 since B w ≥ 1 due to realizability of w ⋆ .

C Proofs for contextual bandits
This section of the appendix is organized as follows. In Appendix C.1, we present details of the PRO-CB algorithm. Appendix C.2 is devoted the proof of Proposition 1, which shows that the PRO-CB algorithm fails to achieve statistically optimal rate of 1/ √ N . The proof of suboptimality upper bound for the conservative offline CB algorithm with ALM is presented in Theorem 3.

C.1 Primal-dual regularized offline contextual bandits (PRO-CB)
Define importance weights w(s, a) = d(s, a)/µ(s, a) to denote the ratio of occupancy and data distribution. The primal-dual regularized approach (Zhan et al., 2022) solves the following population objective The above optimization problem satisfies strong duality. We define w ⋆ α , v ⋆ α to respectively denote the optimal solutions to the primal and dual variables. Approximating w, v to belong to function classes W, V and solving the empirical version of objective (29) leads to the PRO-CB given in Algorithm 6.

C.2 Proof of Proposition 3
We separate the proof into two cases: α ≥ N β for β > −1/2 and α ≤ O(N −1/2 ). When α is large, we show that the large bias caused by regularization results in suboptimality of α even in MABs.
When α 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 α does not sufficiently enforce occupancy validity in states with a relatively small but still significant state distribution ρ(s).
• 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 M f < 100 for convenience, but if M f is larger we can use the same construction with an even larger constant as the denominator.
• Function classes: We assume both W and V contain only the optimal regularized solutions (w ⋆ α , v ⋆ α ) and the optimal unregularized solutions (w ⋆ , v ⋆ ), which satisfy the realizability requirements of PRO-CB: Our argument is broken down in 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 π ⋆ α := π w ⋆ α , is at least of order min{1, α}. Then, in the second step, we prove that w ⋆ α is chosen with a constant probability.
To establish (31), we show that w ⋆ α (2) > c for a fixed constant c = 1 2 . We prove this by contradiction. Suppose By KKT conditions we have Therefore, using the fact that f ′ is strictly increasing since f is strictly convex, we lower bound Combining the above bound on v ⋆ α with the KKT condition on w ⋆ α (1), we then obtain Here, we used the fact that v ⋆ α ≥ r ⋆ = r(1) and that f (0) = 0 so (f ′ ) −1 ((r(1) − v ⋆ α )/α) ≥ 0. Moreover, since the regularization function f is M f -strongly convex, we write Therefore, we can continue to upper bound the RHS of (33): which further implies that Note that (35) contradicts with the fact that (w ⋆ α , v ⋆ α ) is the optimal min-max solution of L MAB α because it violates the constraint E µ [w(a)] = 1. Therefore, (32) should not hold in the first place, and we must have 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 L MAB α (w ⋆ α , v) and L 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 In (37), we used the convexity of regularization function f as well as the fact that f (w ⋆ (2)) = f (0) = 0. Moreover, (38) holds because By KKT conditions we also have Plugging (39) back into (38), we obtain where (40) is based on the fact that f is M f -strongly convex, and that w ⋆ α (2) > c 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 3 that with at least constant probability (e.g. setting δ = 0.1), for any v ∈ V, w ∈ W, one has the following bound on difference between the population and empirical objectives where ǫ MAB stat,α is of order 1/ √ N as defined in (23). Combining the above inequality with (40), for Therefore, since β > −1/2, we conclude that w ⋆ α is chosen by the algorithm with constant probability: Combining the above result with the suboptimality lower bound of π ⋆ α in (36) completes the proof for α ≥ N β .

C.2.2 Proof for small α
where O hides the logarithmic factors. In this case, we consider the following two-state two-arm contextual bandit instance: • State and reward distributions: We construct the states such that state 1 has a very small probability mass. For state 1, the first arm is optimal with a Bernoulli-distributed reward and the second arm is suboptimal with a deterministic reward. For state 2, both arms have deterministic rewards. Importantly, state 1 has a constant value gap in its suboptimal action.
• Data distribution: We assume that for both states, most of the probability density is concentrated on the optimal arm. µ(s) = ρ(s), s = 1, 2.
• Function classes: Let w be defined asw(2, a) = w ⋆ α (2, a) andw(1, a) = 0 for a = 1, 2. Consider the following function classes W and V: The proof is broken down into 4 steps. In the first step, we show that when α ≤ O(N − 1 2 ) and N is sufficiently large, the regularized optimal policy is the same as the unregularized optimal policy, i.e., w ⋆ α = w ⋆ . Therefore, the function class W defined in (41) is realizable w ⋆ α = w ⋆ ∈ W. In the second step, we prove that with constant probability v ⋆ α = arg min v∈VL CB α (w, v). Then, we show that solving the saddle point of the empirical objectiveL CB α (w, v) selectsw over w ⋆ α with a constant probability. Finally, we prove thatw induces a policy πw that suffers from suboptimality of order N −1/4 , which completes the proof.
Step 4: Suboptimality of π w Finally, for the policy π w induced by w, we have J(π ⋆ α ) − J(π w ) = µ(s 1 )π w (2|1)(r(1, 1) − r(1, 2)) = for β = − 1 4 > − 1 2 , as desired. The proof for small α is thus complete. Proof of Inequality (48). Using the Chernoff bounds for binomial random variables given in Lemma 2, one can conclude that the following event E ′ happens with probability at least 0.5: Furthermore, E and E ′ are independent because the random variabler(s 1 , a 1 ) is independent from the arm distribution within state s 2 . Therefore, conditioning on E ∩ E ′ which happens with probability 0.5 × 0.5 = 0.25, we use the anti-concentration bounds for Binomial random variables Lemma 5 to obtain the following lower bound: where c ′ = 20 log(2c 1 ) c 2 is a universal constant. Therefore, we have established that (48) holds with constant probability.
Lemma 5 (Anti-concentration of Binomial random variables, adapted from Proposition 7.3.2 of Matoušek and Vondrák (2001)). Let X 1 , · · · , X n be independent random variables following the Bernoulli distribution with mean 1 2 , and let X = 1 n n i=1 X i be the empirical mean. Then we have that for any t ∈ [0, 1 8 ] and universal constants c 1 , c 2 ,

C.3 Proof of Theorem 3
Proof of this theorem largely follows similar steps as 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 (11) and empirical objective (12). Additionally, we show that this result leads to the closeness of population objective at w ⋆ andŵ. Proof of this lemma is presented at the end of this subsection.
Lemma 6 (Empirical and population closeness, CB). Fix δ > 0 and define For any w ∈ W and v ∈ V, the following statements hold with probability at least 1 − δ In the second lemma, we prove that the ALM term enforces a lower bound on normalization factors dŵ µ (s) := aŵ (s, a)µ(a|s) for significant states.
Given the two lemmas above, our suboptimality analysis can be broken down into two simple steps. First, we partition the states based on S s defined in (54) and decompose the policy suboptimality accordingly: In (55) where the equations follow from the definition ofπ. The final suboptimality bound is proved by noting that (B w + 1) 2 ≍ B 2 w since B w ≥ 1 due to realizability of w ⋆ (s, a ⋆ ) ≥ 1.
Proof of Lemma 6. To prove part (I), notice that Applying Hoeffding's inequality along with a union bound on w ∈ W and v ∈ V finishes the proof of part (I).
We now prove part (II). For the primal-dual objective without the AL term we have (w ⋆ , v ⋆ ) ∈ arg max w≥0 arg min v L CB (w, v) by strong duality. Moreover, since w ⋆ is realizable, it satisfies the validity constraint E a∼µ(·|s) [w ⋆ (s, a)] = 1 for all s. Therefore, by Lemma 13 adding the ALM term does not change the optimal solution and we have (w ⋆ , v ⋆ ) ∈ arg max w≥0 arg min v L CB AL (w, v). We follow similar steps as in the proof of Lemma 1 and decompose L CB . Each term is bounded as follows: • T 1 = 0 because w ⋆ satisfies the optimization constraints.
Summing up the bounds on each term proves part (II).
Proof of Lemma 7. We leverage the closeness of the objective at w ⋆ andŵ established in Lemma 6 to show that the ALM term atŵ is small. Since w ⋆ satisfies the validity constraints, the objective at w ⋆ simplifies to Consider the objective difference at v(s) = r ⋆ (s) := max a r(s, a):  Moreover, since the first term is nonnegative due toŵ(s, a) ≥ 0 and r ⋆ (s) − r(s, a) ≥ 0, both of the terms in the above inequality are bounded by ǫ CB stat and thereby proving part (I). The above result also allows us to bound the mass on the subset S s that contains the states that violate state occupancy validity where we used the fact that dŵ µ (s) ≤ 1 2 and thus dŵ µ (s) − 1 2 ≥ 1 4 by definition of S s . This concludes the proof of part (II).

D Proofs for MDPs
In this section, we begin by introducing some additional notation. The original primal-dual objective without ALM term is given by Define w ⋆ (s, a) = d π ⋆ (s, a)/µ(s, a) and v ⋆ (s) = V * (s). By strong duality, one has (w ⋆ , v ⋆ ) ∈ arg max w≥0 arg min v L MDP (w, v).
Additionally, define ζ ⋆ w,u = arg max ζ<0 L model-free AL (w, v, u, ζ), ∀w ∈ W, u ∈ U and ζ ⋆ w = ζ ⋆ w,u ⋆ w ∀w ∈ W where u ⋆ w is defined in Theorem 4. Also, denote ζ ⋆ = ζ ⋆ w ⋆ and u ⋆ = u ⋆ w ⋆ . The rest of this section is organized as follows. In Appendix D.1, we provide some details regarding practical implementation of the offline learning algorithm with ALM. In Appendix D.2, we derive the objective of model-free CORAL algorithm. Appendix D.3 contains the proof of performance upper bound on model-based and model-free CORAL algorithms (Theorem 4), which relies on several lemmas subsequently proved in Appendices D.4 through D.7.

D.1 On practical implementations
In our algorithms for CB and MDP, we need to compute summations of form a∈A . This can be implemented efficiently when |A| is small. When |A| is large or even infinite, one can utilize numerical methods to estimate the summation with desired precision. Additionally, in Algorithm 4, we need to evaluate a term s ′ ,a ′ P (s ′ |s, a)π w (a ′ |s ′ )u(s ′ , a ′ ). In practice, we can evaluate this term by numerical integration.

D.2 Derivation of the model-free CORAL objective (20)
For f (x) = (x − 1) 2 , the Fenchel conjugate f * is given by Since d w (s)/d πw (s) ≥ 0, we have x ⋆ w (s, a) ≥ −2 and thus it is sufficient to only consider domain x + 1, which is a convex function on [−1, +∞). Similar to Nachum et al. (2019a), we use Fenchel duality to estimate g (u(s, a) − γP πw u(s, a)). By Fenchel duality, any convex function g(x) can be written as g(x) = max ζ xζ − g * (ζ). In the case of g(x), the Fenchel conjugate is given by g * (x) = −x − 2 − 1/x with domain x < 0. Therefore, we write The interchangeability principle (Rockafellar and Wets, 2009;Dai et al., 2017) allows us to convert the inner maximization step over scalar ζ to an overall maximization over ζ : S ×A → R − . Replacing this term in the objective (17) results in the model-free objective in (20).

D.3 Proof of Theorem 4
We start by deriving an expression for x ⋆ w and characterizing bounds on u ⋆ w and ζ ⋆ w,v in the following lemma. The proof is presented in Appendix D.4.
Lemma 8. For any w ∈ W and v ∈ V, one has x ⋆ w (s, a) = 2d w (s)/d πw (s) − 2, |u ⋆ w (s, a)|≤ Bounding the suboptimality of policies returned by both model-based and model-free variants of CORAL follow a similar analysis. We first characterize the statistical error in approximating population objectives by their empirical versions and use it to establish the closeness ofŵ and w ⋆ . The lemma below captures these approximation errors for the model-based objective, whose proof can be found Appendix D.5.
Lemma 9 (Empirical and population closeness, model-based CORAL). Fix δ > 0 and define For any w ∈ W, v ∈ V, and u ∈ U , the following statements hold with probability at least 1 − δ In Appendix D.6, we prove a similar lemma for the model-free objective.
Lemma 10 (Empirical and population closeness, model-free CORAL). Fix δ > 0 and define For any w ∈ W, v ∈ V, and u ∈ U , the following statements hold with probability at least 1 − δ The final key lemma demonstrates that in model-based and model-free CORAL, the ALM terms enforce lower bounds on the ratio of the estimated occupancy of learned weights dŵ(s) and the actual occupancy of the learned policy d πŵ (s) in most states. The proof of this lemma is given in Appendix D.7. Given the above lemmas, we proceed to prove the suboptimality bounds in terms of statistical errors defined in (59) and (60). 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 and Langford (2002, Lemma 6.1), one has J(π ⋆ ) − J(π) = E s∼dπ a A ⋆ (s, a) (π ⋆ (a|s) −π(a|s)) = E s∼dπ a −A ⋆ (s, a)π(a|s) , where dπ = d πŵ . Here, we used the fact that the expectation of the optimal advantage over optimal policy is zero a A ⋆ (s, a)π ⋆ (a|s) = 0. Lemma 11 links an expectation of −A ⋆ (s, a) to the statistical error. With this lemma at hand and using the definition S s = {s | dŵ(s) ≤ dπ(s)/2}, we continue to decompose and bound the suboptimality It is easy to show that |ζ ⋆ w,u (s, a)|= (u(s, a)− γ(P πw u)(s ′ , a ′ )+ 1) −1/2 = (f * (x w (s, a))+ 1) −1/2 . Sincẽ x w (s, a) ∈ [−B x , B x ], we have |ζ ⋆ w,u (s, a)|∈ We subsequently show that the absolute values of the above error terms satisfy the following high probability upper bounds: Taking N 0 = N and noting that B w ≥ 1 due to realizability of w ⋆ yield that Proof of bound (65a) on |T 1 |. Since |v(s)|≤ B v , |u(s, a)|≤ B u for all v ∈ V and u ∈ U and s i are independent, we can apply Hoeffding's inequality and union bound to conclude the advertised bound (65a) on |T 1 |.
As before, due to boundedness and independence of variables w(s i , a i )[r i +γv(s ′ i )−v(s i )], Hoeffding's inequality can be applied, giving the bound (65b) on |T 2 |.
Then, we use the concentration result on maximum likelihood model estimation stated in Theorem 5 and a union bound on w ∈ W and v ∈ V to conclude that

D.5.2 Proof of part (II)
To prove the second part, letv w andû w denote the solutions to the model-based empirical objectivê v w ,û w = arg min v∈V arg min u∈UL model-based AL (w, v, u) Decompose the objective difference according to The absolute values of the error terms above satisfy the following upper bounds with high probability |T 3 | (1 + B ζ (B u + 1))B w log|U ||W||Z|/δ N .

D.7 Proof of Lemma 11
We provide proof only for the model-based algorithm and letŵ =ŵ model-based for notation convenience. The proof for a model-free algorithm follows analogously, noting the fact that L model-free AL (w, v ⋆ , u ⋆ w , ζ ⋆ w ) = L model-based AL (w, v ⋆ , u ⋆ w ) and we can replace Lemma 9 with Lemma 10 to prove the model-free version.

D.7.1 Proof of part (I)
Consider the expression of the model-based objective L model-based The first term is nonnegative because for the optimal advantage function we have A ⋆ (s, a) ≤ 0 for all s ∈ S and a ∈ A. We write the second term as

E Auxiliary results
Theorem 5 (Convergence of MLE for learning transitions ( Van de Geer, 2000)). Given a realizable model class P = {P : (S, A) → ∆(S)} that contains the true model P ⋆ and a dataset D m = {(s i , a i , s ′ i )} with (s i , a i ) iid ∼ µ, s ′ i ∼ P ⋆ (·|s i , a i ), letP bê ln P (s ′ i |s i , a i ).
and for any x ∈ X 0 , x ∈ X * ⇐⇒ x ∈ arg max x∈X 0 min y∈Y f AL (x, y).
Proof. Note that for any fixed x, f AL (x, y) is a constant shift of f (x, y), which implies that inf y∈Y f (x, y) > −∞ ⇐⇒ inf y∈Y f AL (x, y) > −∞. This also implies that for any x ∈ X 0 , arg min y∈Y f (x, y) = arg min y∈Y f AL (x, y).