# Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage

Masatoshi Uehara 111This work is done when the author was at Cornell
University<EMAIL_ADDRESS>Genentech  Nathan Kallus
<EMAIL_ADDRESS>Genentech  Jason D. Lee<EMAIL_ADDRESS>Princeton
University  Wen Sun<EMAIL_ADDRESS>Genentech

###### Abstract

In offline RL, we have no opportunity to explore so we must make assumptions
that the data is sufficient to guide picking a good policy, and we want to
make these assumptions as harmless as possible. In this work, we propose
value-based algorithms for offline RL with PAC guarantees under just partial
coverage, specifically, coverage of just a single comparator policy, and
realizability of the soft (entropy-regularized) Q-function of the single
policy and a related function defined as a saddle point of certain minimax
optimization problem. This offers refined and generally more lax conditions
for offline RL. We further show an analogous result for vanilla Q-functions
under a soft margin condition. To attain these guarantees, we leverage novel
minimax learning algorithms and analyses to accurately estimate either soft or
vanilla Q-functions with strong $L^{2}$-convergence guarantees. Our
algorithms’ loss functions arise from casting the estimation problems as
nonlinear convex optimization problems and Lagrangifying. Surprisingly we
handle partial coverage even without explicitly enforcing pessimism.

##  1 Introduction

In offline Reinforcement Learning (RL), we must learn exclusively from offline
data and are unable to actively interact with the environment (Levine et al.,
2020). Offline RL has garnered considerable interest in a range of
applications where experimentation may be prohibitively costly or risky.

Offline RL is generally based on two types of assumptions: sufficient coverage
in the offline data and sufficient function approximation. For instance,
classical Fitted-Q-iteration (Antos et al., 2008; Chen and Jiang, 2019)
requires (a) full coverage in the offline data,
$\max_{(s,a)}d_{\pi,\mu_{0}}(s,a)/P_{\pi_{b}}(s,a)<\infty$ for any policy
$\pi$ where $P_{\pi_{b}}(s,a)$ is the offline data’s distribution on the
states and actions and $d_{\pi,\mu_{0}}(s,a)$ is the state-action occupancy
distribution under a policy $\pi$ and initial-state distribution $\mu_{0}(s)$;
(b) realizability of the $Q^{*}$-function in a hypothesis class; and (c)
Bellman completeness, _i.e._ , the Bellman operator applied to any function in
the hypothesis class remains in the class. Full coverage (a) and Bellman
completeness (c) can be particularly stringent because offline data is often
insufficiently exploratory and Bellman completeness significantly restricts
transition dynamics.

Table 1: Summary of partial-coverage-type guarantees with model-free general
function approximation. Here, $w^{\star}\coloneqq
d_{\pi^{\star},\mu_{0}}/P_{b}$ where $d_{\pi^{\star},\mu_{0}}$ is the
occupancy distribution under the optimal policy $\pi^{\star}$ starting from
$\mu_{0}$ and $P_{b}$ is the distribution over the offline data. A function
$\tilde{w}^{\star}_{\alpha}$ is a regularized marginal density ratio that
satisfies $\tilde{w}^{\star}_{0}=w^{\star}$. Functions
$q^{\star},q^{\star}_{\alpha},q_{\pi}$ are the optimal $Q^{\star}$-function,
the soft Q-function, and the Q-function under a policy $\pi$, respectively.
Functions $v^{\star}_{\alpha},l^{\star}_{\alpha}$ are Lagrange multipliers of
specific minimax optimization problems. The operator $\mathcal{B}^{\pi}$ is a
Bellman operator under a policy $\pi$. Function classes
$\mathcal{W},\mathcal{Q},\mathcal{L},\mathcal{V}$ consist of functions that
map states (and actions) to real numbers. Note the guarantees provided by
Jiang and Huang (2020); Xie et al. (2021) are more general than the below in
that the output policy can compete with any policy in the policy class $\Pi$.
For simplicity, we set the comparator policy to be the optimal policy
$\pi^{\star}$ in this table. Note that other studies (Ozdaglar et al., 2023;
Rashidinejad et al., 2022; Zhu et al., 2023) proposing model-free general
function approximation under partial coverage rely on the completeness-type
assumption as in (Xie et al., 2021) or realizability for any $\pi$ as in Jiang
and Huang (2020).

| Primary Assumptions |
---|---|---
Jiang and Huang (2020) | $w^{\star}\in\mathcal{W},\,q_{\pi}\in\mathcal{Q}\;\forall\pi\in\Pi$ |
Xie et al. (2021) | $q_{\pi}\in\mathcal{Q},\,\mathcal{B}^{\pi}\mathcal{Q}\subset\mathcal{Q}\;\forall\pi\in\Pi$ |
Zhan et al. (2022) | $\tilde{w}^{\star}_{\alpha}\in\mathcal{W},\,v^{\star}_{\alpha}\in\mathcal{V}$ |
MSQP | $q^{\star}_{\alpha}\in\mathcal{Q},\,l^{\star}_{\alpha}\in\mathcal{L}$ |
Chen and Jiang (2022) | Hard margin$,\,w^{\star}\in\mathcal{W},\,q^{\star}\in\mathcal{Q}$ |
MQP | Soft margin$,\,q^{\star}\in\mathcal{Q},\,l^{\star}\in\mathcal{L}$ |

To overcome these challenges, we here propose algorithms with guarantees under
realizability of single functions and refined partial coverage of single
policies, and without Bellman completeness. We tackle this by introducing two
novel value-based algorithms. The first algorithm, MSQP (mimimax soft-Q-
learning with penalization), comprises of two steps: learning soft Q-functions
(a.k.a., entropy-regularized Q-functions, as defined in Fox et al., 2015;
Schulman et al., 2017) from offline data, and using the softmax policies of
the learned soft Q-functions. The second algorithm, MQP (mimimax Q-learning
with penalization), consists of two steps: learning standard Q-functions from
offline data and employing the greedy policy of the learned Q function on the
offline data.

Using the above-mentioned two algorithms, we attain PAC guarantees under
partial coverage and realizability, yet without Bellman completeness. In
particular, in MSQP using soft Q-functions, we ensure strong performance under
the realizability of $q^{\star}_{\alpha}$, $l^{\star}_{\alpha}$ and the
(density-ratio-based) partial coverage
$\max_{(s,a)}d_{\pi^{\star}_{\alpha},\mu_{0}}(s,a)/P_{b}(s,a)<\infty$. Here
$q^{\star}_{\alpha}$ is a soft Q-function, $l^{\star}_{\alpha}$ is a function
that possesses a certain dual relation to $q^{\star}_{\alpha}$,
$\pi^{\star}_{\alpha}$ is the soft-max optimal policy, and $\alpha$ is the
temperature parameter for the entropy-regularization. Notably,
$\max_{(s,a)}d_{\pi^{\star}_{\alpha},\mu_{0}}(s,a)/P_{b}(s,a)<\infty$ is
significantly less stringent than the uniform coverage in that the coverage is
only imposed against a policy $\pi^{\star}_{\alpha}$. In MQP using
Q-functions, we similarly ensure strong performance under a soft margin, the
realizability of $q^{\star}$, $l^{\star}$, and the partial coverage
$\max_{(s,a)}d_{\pi^{\star},\mu_{0}}(s,a)/P_{b}(s,a)<\infty$. Here $q^{\star}$
is the vanilla Q-function and $l^{\star}$ is a function that possesses a
certain dual relation to $q^{\star}$, and $\pi^{\star}$ is the usual optimal
policy. Note the soft margin is introduced to allow realizability on standard
Q-functions rather than soft Q-functions. However, the conditions
$\max_{(s,a)}d_{\pi^{\star}_{\alpha},\mu_{0}}(s,a)/P_{b}(s,a)<\infty$ or
$\max_{(s,a)}d_{\pi^{\star},\mu_{0}}(s,a)/P_{b}(s,a)<\infty$ may still be
strong as these marginal density ratios may not exist in large-scale MDPs. For
example, this condition is easily violated when the initial distribution
$\mu_{0}$ is not covered by $P_{b}$ (_i.e._ ,
$\max_{s}\mu_{0}(s)/P_{b}(s)=\infty$ where
$P_{b}(s)\coloneqq\sum_{a}P_{b}(s,a)$). Therefore, as an additional
innovation, in our algorithms we can further relax these density-ratio-based
partial coverage conditions. Specifically, we can demonstrate results under a
_refined partial coverage_ , which is adaptive to Q-function classes, even
when the initial distribution $\mu_{0}$ is not covered by $P_{b}$.222Note
$\mu_{0}$ and $P_{b}$ could be generally different even in the contextual
bandit setting. This important setting is often considered in the literature
on external validity/transportability in causal inference, as results of
randomized clinical trials cannot be directly transported because covariate
distributions in offline data and target data are different (Cole and Stuart,
2010; Pearl and Bareinboim, 2014; Dahabreh et al., 2019).

The primary challenge lies in the design of loss functions for effectively
learning soft Q-functions and vanilla Q-functions from offline data _without
Bellman completness_. To tackle this, we devise new minimax loss functions
with certain regularization terms to achieve favorable $L^{2}$-convergence
rates on the offline data (_i.e._ , in terms of $\mathbb{E}_{(s,a)\sim
P_{b}}[\\{\hat{q}_{\alpha}-q\\}^{2}(s,a)]$ given an estimator $\hat{q}$). This
result serves as the key building block for obtaining refined partial coverage
under realizability and is of independent interest in its own right. Existing
results are often constrained to specific models, such as linear models (Shi
et al., 2022a), or they require Bellman completeness (Antos et al., 2008; Chen
and Qi, 2022; Chen and Jiang, 2019). In contrast, our guarantee is applicable
to any function approximation method, without the need for Bellman
completeness. To the best of our knowledge, this is the first guarantee of its
kind.

Our work exhibits marked improvements over two closely related studies (Zhan
et al., 2022; Chen and Jiang, 2022). Similar to our work, they propose
algorithms that operate under the realizability of specific functions and
partial coverage, yet without Bellman completeness. Zhan et al. (2022) ensures
a PAC guarantee under (a’) partial coverage in the offline data
$\max_{(s,a)}d_{\tilde{\pi}^{\star}_{\alpha},\mu_{0}}(s,a)/P_{b}(s,a)<\infty$
where $\tilde{\pi}^{\star}_{\alpha}$ is a specific near-optimal policy under
the regularization, which differs from the soft optimal policy, and (b’)
realizability of $d_{\tilde{\pi}^{\star}_{\alpha},\mu_{0}}/P_{b}$ and the
regularized value function. However, unlike MSQP, it is unclear how to refine
the abovementioned coverage, _i.e._ , the guarantee could be vacuous when the
initial distribution is not covered by offline data. A similar guarantee, but
without regularization, is obtained under the additional hard margin (a.k.a.,
gap) condition in Chen and Jiang (2022). Our soft margin is a strict
relaxation of the hard margin, which is important because, unlike the soft
margin, the hard margin generally does not hold in continuous state spaces and
involves very large constants in discrete state spaces. Lastly, although Chen
and Jiang (2022); Zhan et al. (2022) use completely different algorithms and
attain guarantees for regularized value-functions and non-regularized value
functions, respectively, our guarantee can afford guarantees for regularized
and non-regularized value-functions in a _unified_ manner since MQP can be
seen as a limit of MSQP when $\alpha$ goes to $0$.

Our contributions are summarized below and in Table 1.

  1. 1.

We establish that the optimal policy can be learned under partial coverage and
realizability of the optimal soft Q-function and its dual. Notably, we abstain
from the use of possibly stronger conditions in offline RL, such as full
coverage, Bellman completeness, and uniform realizability over the policy
class (such as $q_{\pi}\in\mathcal{Q}$ for any $\pi$ as in Jiang and Huang,
2020). In particular, while a similar guarantee is provided in Zhan et al.
(2022), our partial coverage guarantee has an advantage in that we are able to
potentially accommodate scenarios where the initial distribution is not
covered by $P_{b}$. This is feasible because our algorithm is value-based in
nature, which allows us to leverage the structure of the Q-function classes
and refine the coverage condition.

  2. 2.

We demonstrate that the optimal policy can be learned under partial coverage,
realizability of the Q-function and its dual, and a soft margin. While a
similar guarantee is obtained in Chen and Jiang (2022), our guarantee has the
advantage that the soft margin is significantly less stringent than the hard
margin required therein.

###  1.1 Related Works

We summarize related works as follows. Further related works is discussed in
Section A.

#### Offline RL under partial coverage.

There is a growing number of results under partial coverage following the
principle of pessimism in offline RL (Yu et al., 2020; Kidambi et al., 2020).
In comparison to works that focus on tabular (Rashidinejad et al., 2021; Li et
al., 2022; Shi et al., 2022b; Yin and Wang, 2021) or linear models (Jin et
al., 2020; Chang et al., 2021; Zhang et al., 2022; Nguyen-Tang et al., 2022;
Bai et al., 2022), our emphasis is on general function approximation (Jiang
and Huang, 2020; Uehara and Sun, 2021; Xie et al., 2021; Zhan et al., 2022;
Zhu et al., 2023; Rashidinejad et al., 2022; Zanette and Wainwright, 2022;
Ozdaglar et al., 2023). Among them, we specifically focus on model-free
methods. The representative work is summarized in Table 1.

#### Soft (entropy-regularized) Q-functions.

Soft Q-functions are utilized in various contexts in RL (Geist et al., 2019;
Neu et al., 2017). They have been shown to improve performance in online RL
settings, as demonstrated in Soft Q-Learning (Fox et al., 2015; Schulman et
al., 2017) and Soft Actor Critic (Haarnoja et al., 2018). In the field of
imitation learning, they play a crucial role in Maximum Entropy IRL (Ziebart
et al., 2008, 2010). Furthermore, within the realm of offline RL, these soft
Q-functions are utilized to make the learned policy and behavior policy
sufficiently similar (Wu et al., 2019; Fakoor et al., 2021). However, to the
best of the authors’ knowledge, none of these proposals in the context of
offline RL have provided sample complexity results under partial coverage.

#### Lagrangian view of offline RL.

In the realm of offline policy evaluation (OPE), Nachum and Dai (2020); Yang
et al. (2020); Huang and Jiang (2022) have formulated the problem as a
constrained linear optimization problem. Notably, within the context of policy
optimization, Zhan et al. (2022) have proposed estimators for regularized
density ratios with $L^{2}$-convergence guarantees, which is a crucial step in
obtaining a near-optimal policy. Our work is similarly motivated, but with a
key distinction: our target functions are the soft Q-function and Q-function,
rather than the regularized density ratio, which presents additional
analytical challenges due to the nonlinear constraint.

##  2 Preliminaries

We consider an infinite-horizon discounted MDP
$\mathcal{M}=\langle{\mathcal{S}},\mathcal{A},P,r,\gamma,\mu_{0}\rangle$ where
${\mathcal{S}}$ is the state space, $\mathcal{A}$ is the finite action space,
$\gamma\in[0,1)$ is the discount factor, reward $r$ is a random variable
following $P_{r}(\cdot\mid s,a)$ on $[R_{\min},R_{\max}]$ ($R_{\min}\geq 0$),
$\mu_{0}$ is the initial distribution. A policy
$\pi:{\mathcal{S}}\to\Delta(\mathcal{A})$ is a map from the state to the
distribution over actions. We denote the discounted state-action occupancy
distribution under a policy $\pi$ starting from an initial distribution
$\mu_{0}$ by $d_{\pi,\mu_{0}}(s,a)$. With slight abuse of notation, we denote
$d_{\pi,\mu_{0}}(s)=\sum_{a}d_{\pi,\mu_{0}}(s,a)$. We define the value under
$\pi$ as
$J(\pi)\coloneqq\mathbb{E}_{\pi}[\sum_{t=0}^{\infty}\gamma^{t}\tilde{r}(s_{t},a_{t})]$
where the expectation is taken under $\pi$. We denote the optimal policy
$\operatorname*{arg\,max}_{\pi}J(\pi)$ by $\pi^{\star}$, and its Q-function
$\mathbb{E}_{\pi^{\star}}[\sum_{t}\gamma^{t}\tilde{r}(s_{t},a_{t})\mid
s_{0}=s,a_{0}=a]$ by $q^{\star}(s,a)$.

In offline RL, using offline data
$\mathcal{D}=\\{(s_{i},a_{i},r_{i},s^{\prime}_{i}):i=1,\dots,n\\}$, we search
for the policy $\pi^{\star}$ that maximizes the policy value. We suppose each
$(s_{i},a_{i},r_{i},s^{\prime}_{i})$ is sampled i.i.d. from $s_{i}\sim
P_{b},a_{i}\sim\pi_{b}(\cdot\mid s),r_{i}\sim P_{r}(\cdot\mid
s_{i},a_{i}),s^{\prime}_{i}\sim P(\cdot\mid s_{i},a_{i})$. We denote the
sample average of $f$ by
$\mathbb{E}_{n}[f(s,a,r,s^{\prime})]=\frac{1}{n}\sum_{i=1}^{n}f(s_{i},a_{i},r_{i},s^{\prime}_{i})$,
and the expectation of $f$ with respect to the offline data distribution by
$\mathbb{E}[f(s,a,r,s^{\prime})]$ (without any scripts). The policy $\pi_{b}$
used to collect data is typically referred to as a behavior policy. With
slight abuse of notation, we denote $P_{b}(s,a)=P_{b}(s)\pi_{b}(a\mid s)$.

Notation. We denote the support of $P_{b}(\cdot)$ by
$({\mathcal{S}}\times\mathcal{A})_{b}$, and the $L^{\infty}$-norm on
$({\mathcal{S}}\times\mathcal{A})_{b}$ by $\|\cdot\|_{\infty,b}$. The
$L^{\infty}$-norm on $({\mathcal{S}}\times\mathcal{A})$ is denoted by
$\|\cdot\|_{\infty}$. We define $w_{\pi}(s,a)=d_{\pi,\mu_{0}}(s,a)/P_{b}(s,a)$
(if it exists). We define
$\mathrm{sofmax}(h)=\frac{\exp(h(s,a))}{\sum_{a}\exp(h(s,a))}$ and
$\|h\|_{2}=\mathbb{E}_{(s,a)\sim P_{b}}[h^{2}(s,a)]^{1/2}$ for
$h:{\mathcal{S}}\times\mathcal{A}\to\mathbb{R}$. We denote universal constants
by $c_{1},c_{2},\dots$. We use the convention $a/0=\infty$ when $a\neq 0$ and
$0/0=0$.

##  3 Algorithms

In this section, we present two algorithms. The first algorithm aims to
estimate the soft optimal policy by first estimating a soft Q-function. The
second algorithm estimates the optimal policy after estimating the Q-function.

###  3.1 Minimax Soft-Q-learning with Penalization

Our ultimate aim is to mimic the optimal policy $\pi^{\star}$. As a first
step, we begin by finding a policy that maximizes the following regularized
objective: $\operatorname*{arg\,max}_{\pi}J_{\alpha}(\pi)$ where for
$\alpha>0$ we define

$\displaystyle J_{\alpha}(\pi)=(1-\gamma)^{-1}\mathbb{E}_{(s,a)\sim
d_{\pi,\mu_{0}},r\sim P_{r}(\cdot\mid
s,a)}[r-\underbrace{\alpha\log\\{\pi(a\mid s)/\pi_{b}(a\mid s)\\}]}_{\text{KL
penalty (between $\pi$ and $\pi_{b}$)}}$

This objective function is used in a variety of contexts in RL as mentioned in
Section 1.1. The optimal policy that maximizes $J_{\alpha}(\pi)$ with respect
to $\pi$ is

$\displaystyle\pi^{\star}_{\alpha}=\mathrm{softmax}(q^{\star}_{\alpha}/\alpha+\log\pi_{b}),$
(1)

where $q^{\star}_{\alpha}:{\mathcal{S}}\times\mathcal{A}\to\mathbb{R}$ is the
soft Q-function uniquely characterized by the soft Bellman equation:

$\displaystyle\forall(s,a);\mathbb{E}_{s^{\prime}\sim P(\cdot\mid
s,a)}[\gamma\Omega_{\alpha,\pi_{b}}(q^{\star}_{\alpha})(s^{\prime})+r-q^{\star}_{\alpha}(s,a)\mid
s,a]=0,$

where
$\Omega_{\alpha,\pi_{b}}:[{\mathcal{S}}\times\mathcal{A}\to\mathbb{R}]\to[{\mathcal{S}}\to\mathbb{R}]$
has
$\Omega_{\alpha,\pi_{b}}(q)(s)=\alpha\log\sum_{a}\\{\exp(q(s,a^{\prime})/\alpha)\pi_{b}(a^{\prime}\mid
s)\\}.$ As opposed to the standard objective function with $\alpha=0$, the KL
penalty term serves as a regularization term that renders
$\pi^{\star}_{\alpha}$ sufficiently proximate to $\pi_{b}$. As $\alpha$
approaches $\infty$, the optimal policy $\pi^{\star}_{\alpha}$ approaches
$\pi_{b}$. On the other hand, when $\alpha=0$, $\pi^{\star}_{\alpha}$ is
$\pi^{\star}$. Thus, in order to compete with $\pi^{\star}$, it is necessary
to keep $\alpha$ sufficiently small. We elaborate on this selection procedure
in Section 5.

The natural method for offline RL using this formulation involves learning
$q^{\star}_{\alpha}$ from the offline data and plugging it into (1). The
question that remains is how to accurately learn $q^{\star}_{\alpha}$ from the
offline data. We consider the following optimization problem:

$\displaystyle\textstyle\operatorname*{arg\,min}_{q\in\mathcal{Q}^{\prime}}0.5\mathbb{E}_{(s,a)\sim
P_{b}}[q^{2}(s,a)]$ (2)

where $\mathcal{Q}^{\prime}$ consists of all functions
$q:{\mathcal{S}}\times\mathcal{A}\to\mathbb{R}$ satisfying

$\displaystyle\mathbb{E}_{s^{\prime}\sim P(\cdot\mid
s,a)}[\gamma\Omega_{\alpha,\pi_{b}}(q)(s^{\prime})+r-q(s,a)\mid
s,a]=0~{}~{}~{}\forall(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b}.$ (3)

Here, because of the constraint (3), the solution is $q^{\star}_{\alpha}$.
Furthermore, we use $q^{2}(s,a)$ in (2) because this choice relaxes the
equality in (3) to an inequality $\leq 0$ as we will demonstrate in Section B.
Consequently, the entire optimization problem outlined in (2) and (3)
transforms into a convex optimization problem.

Then, using the method of Lagrange multipliers, (2) is transformed into

$\displaystyle\textstyle\min_{q}\max_{l}L_{\alpha}(q,l),\quad
L_{\alpha}(q,l):=\mathbb{E}\left[q^{2}(s,a)/2+\\{\gamma\Omega_{\alpha,\pi_{b}}(q)(s^{\prime})+r-q(s,a)\\}l(s,a)\right].$
(4)

Being motivated by the above formulation, our MSQP algorithm, specified in
Algorithm 1, approximates this formulation by replacing expectations with
sample averages and restricting optimization to function classes with bounded
complexity.

Algorithm 1 MSQP (Minimax Soft-Q-learning with Penalization)

1: Require: Parameter $\alpha\in\mathbb{R}^{+}$, Models
$\mathcal{Q},\mathcal{L}\subset[{\mathcal{S}}\times\mathcal{A}\to\mathbb{R}^{+}]$.

2: Estimate $q^{\star}_{\alpha}$ as follows:
$\displaystyle\hat{q}_{\alpha}\in\operatorname*{arg\,min}_{q\in\mathcal{Q}}\max_{l\in\mathcal{L}}\mathbb{E}_{n}[q^{2}(s,a)/2+\\{\gamma\Omega_{\alpha,\pi_{b}}(q)(s^{\prime})+r-q(s,a)\\}l(s,a)].$
(5)

3: Estimate the soft optimal policy:
$\textstyle\hat{\pi}_{\alpha}=\mathrm{softmax}(\hat{q}_{\alpha}/\alpha+\log\pi_{b}).$

######  Remark 1 (Computation).

Although minimax optimization is generally difficult to solve, it is
computationally feasible when we choose RKHS or linear function classes for
$\mathcal{L}$. In this case, we can solve the inner maximization problem
analytically in closed form, as the objective function is linear in $l$. As a
result, the minimax optimization problem reduces to empirical risk
minimization.

###  3.2 Minimax $Q^{\star}$-learning with Penalization

Next, we examine a policy learning algorithm utilizing $Q^{\star}$-functions.
To learn $Q^{\star}$, our objective function is derived from the constrained
optimization problem:

$\displaystyle\textstyle\operatorname*{arg\,min}_{q\in\mathcal{Q}^{\star^{\prime}}}0.5\mathbb{E}_{(s,a)\sim
P_{b}}[q^{2}(s,a)]$ (6)

where $\mathcal{Q}^{\star^{\prime}}$ consists of all functions
$q:{\mathcal{S}}\times\mathcal{A}\to\mathbb{R}$ satisfying

$\displaystyle\textstyle\forall(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b};\mathbb{E}_{s^{\prime}\sim
P(\cdot\mid
s,a)}[\gamma\max_{a^{\prime}\in\mathcal{A}}q(s^{\prime},a^{\prime})+r-q(s,a)\mid
s,a]=0.$

Next, again using the method of Lagrange multipliers, (6) is transformed into

$\displaystyle\textstyle\min_{q}\max_{l}L_{0}(q,l),\,L_{0}(q,l):=\mathbb{E}[q^{2}(s,a)/2+\\{\gamma\max_{a^{\prime}}q(s^{\prime},a^{\prime})+r-q(s,a)\\}l(s,a)].$
(7)

Note $L_{0}$ is the limit of $L_{\alpha}$ as $\alpha\to 0$.

Our MQP algorithm, specified in Algorithm 2, similarly approximates this
formulation by replacing expectations with sample averages and restricting
optimization to function classes with bounded complexity. Our final policy is
greedy with respect to the learned Q-function but restricting to the support
of the offline data in order to avoid exploiting regions not covered by the
offline data.

Algorithm 2 MQP (Minimax $Q^{\star}$-learning with Penalization)

1: Require: Models
$\mathcal{Q},\mathcal{L}\subset[{\mathcal{S}}\times\mathcal{A}\to\mathbb{R}^{+}]$.

2: Estimate $q^{\star}$ as follows:
$\displaystyle\hat{q}_{0}\in\operatorname*{arg\,min}_{q\in\mathcal{Q}}\max_{l\in\mathcal{L}}\mathbb{E}_{n}[q^{2}(s,a)/2+\\{\gamma\max_{a^{\prime}}q(s^{\prime},a^{\prime})+r-q(s,a)\\}l(s,a)].$
(8)

3: Estimate the optimal policy: $\hat{\pi}_{0}(a\mid
s)=\operatorname*{arg\,max}_{a:\pi_{b}(a\mid s)>0}\hat{q}_{0}(s,a).$

######  Remark 2 (Prominent differences).

There exist several other minimax estimators for $Q^{\star}$ including BRM
(Antos et al., 2008) and MABO (Xie and Jiang, 2020). Although these ensure
convergence guarantees in terms of Bellman residual errors, they do not ensure
the guarantee in terms of $L^{2}$-errors, which is our focus.

Our minimax objective function differs significantly from that of the
aforementioned approaches, and its unique design plays a pivotal role in
enabling $L^{2}$-rates.

##  4 $L^{2}$-convergence Rates for Soft $Q$-functions and
$Q^{\star}$-functions

To analyze our Q-estimators we first establish conditions that ensure
$q^{\star}_{\alpha}=\operatorname*{arg\,min}_{q\in\mathcal{Q}}\max_{l\in\mathcal{L}}L_{\alpha}(q,l)$
on the support $({\mathcal{S}}\times\mathcal{A})_{b}$. Building on this, we
prove $L^{2}$-convergence rates for $\hat{q}_{\alpha}$ and $\hat{q}_{0}$.
These $L^{2}$-convergence guarantees are subsequently translated into
performance guarantees of the policies we output in Section 5.

###  4.1 Identification of Soft Q-functions

Consider an $L^{2}$-space $\mathcal{H}$ where the inner product is define as
$\langle h_{1},h_{2}\rangle=\mathbb{E}_{(s,a)\sim
P_{b}}[h_{1}(s,a)h_{2}(s,a)]$. Then we define two operators and a key
function:333We use the notation $\cdot^{\top}$ because
${P^{\star}_{\alpha}}^{\top}$ is interpreted as the adjoint operator in the
non-weighted $L^{2}$-space.

$\displaystyle P^{\star}_{\alpha}\textstyle:\mathcal{H}\ni
f\mapsto\mathbb{E}_{s^{\prime}\sim
P(s,a),a^{\prime}\sim\pi^{\star}_{\alpha}}[f(s^{\prime},a^{\prime})\mid(s,a)=\cdot]\in\mathcal{H},$
$\displaystyle\\{P^{\star}_{\alpha}\\}^{\top}\textstyle:\mathcal{H}\ni
f\mapsto\int P(\cdot\mid
s,a)\pi^{\star}_{\alpha}(\cdot\mid\cdot)f(s,a)\mathrm{d}(s,a)\in\mathcal{H},$
$\displaystyle
l^{\star}_{\alpha}(s,a)\coloneqq\begin{cases}\frac{(I-\gamma\\{P^{\star}_{\alpha}\\}^{\top})^{-1}(P_{b}(s,a)q^{\star}_{\alpha}(s,a))}{P_{b}(s,a)}\quad&(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b},\\\
0&(s,a)\neq({\mathcal{S}}\times\mathcal{A})_{b}.\end{cases}$

These satisfy a key adjoint property, which we leverage to show
$(q^{\star}_{\alpha},l^{\star}_{\alpha})$ is a saddle point of
$L_{\alpha}(q,l)$.

######  Lemma 1.

$\forall q\in\mathcal{H}$, we have $\langle l^{\star}_{\alpha},(I-\gamma
P^{\star}_{\alpha})q\rangle_{\mathcal{H}}=\langle
q^{\star}_{\alpha},q\rangle_{\mathcal{H}}.$

Our first assumption ensures that $l_{\alpha}^{\star}$ exists.

######  Assumption 1.

Suppose $\|d_{\pi^{\star}_{\alpha},P_{b}}/P_{b}\|_{\infty}<\infty$. Note the
infinity norm $\|\cdot\|_{\infty}$ is over ${\mathcal{S}}\times\mathcal{A}$.

######  Proposition 1.

Under Assumption 1, we have $\|l^{\star}_{\alpha}\|_{\infty}<\infty$.

Proposition 1 is immediate noting that
$(I-\gamma\\{P^{\star}_{\alpha}\\}^{\top})^{-1}(P_{b}(\cdot)q^{\star}_{\alpha}(\cdot))=\sum_{t=0}^{\infty}\gamma^{t}(\\{P^{\star}_{\alpha}\\}^{\top})^{t}(P_{b}q^{\star}_{\alpha})$
and recalling the discounted occupancy measure under $\pi^{\star}_{\alpha}$
with initial distribution $\mu_{0}$ is written as
$d_{\pi^{\star}_{\alpha},\mu_{0}}=(1-\gamma)(I-\gamma\\{P^{\star}_{\alpha}\\}^{\top})^{-1}(\mu_{0})$.
Hence,
$\|l^{\star}_{\alpha}\|_{\infty}\leq(1-\gamma)^{-1}R_{\max}\|d_{\pi^{\star}_{\alpha,P_{b}}}/P_{b}\|_{\infty}$.

Note that $\|d_{\pi^{\star}_{\alpha,P_{b}}}/P_{b}\|_{\infty}$ crucially
differs with the standard density-ratio-based concentrability coefficient
$\|d_{\pi^{*}_{\alpha},\mu_{0}}/P_{b}\|_{\infty}$ in offline RL. Unlike
$\|d_{\pi^{*}_{\alpha},P_{b}}/P_{b}\|_{\infty}$ , the value of
$\|d_{\pi^{*}_{\alpha},\mu_{0}}/P_{b}\|_{\infty}$ can be infinite when the
initial distribution $\mu_{0}$ is not covered by offline data $P_{b}$ as the
practical motivating example is explained in the footnote in Section 1 and
Example 2.

Our next assumption ensures $q^{\star}_{\alpha}\geq 0$, which also guarantees
that $l^{\star}_{\alpha}\geq 0$.

######  Assumption 2.

Suppose $\alpha\log\|\pi^{*}_{\alpha}/\pi_{b}\|_{\infty}\leq R_{\min}$.

Assumption 2 can be satisfied by rescaling reward (_i.e._ , rescaling
$R_{\min}$) as long as $\|\pi^{*}_{\alpha}/\pi_{b}\|_{\infty}$ is finite.
Hence, it is very mild. Putting Lemma 1 together with our assumptions we have
the following.

######  Lemma 2.

Suppose Assumptions 1 and 2 hold. Then,
$(q^{\star}_{\alpha},l^{\star}_{\alpha})$ is a saddle point of
$L_{\alpha}(q,l)$ over $q\in\mathcal{H},l\in\mathcal{H}$, _i.e._ ,
$L_{\alpha}(q,l^{\star}_{\alpha})\geq
L_{\alpha}(q^{\star}_{\alpha},l^{\star}_{\alpha})\geq
L_{\alpha}(q^{\star}_{\alpha},l)$ $\forall q\in\mathcal{H},\forall
l\in\mathcal{H}$.

Recall that a point $(\tilde{q},\tilde{l})$ is a saddle point if and only if
the strong duality holds, and
$\tilde{q}\in\operatorname*{arg\,min}_{q\in\mathcal{H}}\sup_{l\in\mathcal{H}}L_{\alpha}(q,l),\tilde{l}\in\operatorname*{arg\,max}_{l\in\mathcal{H}}\inf_{q\in\mathcal{H}}L_{\alpha}(q,l)$
using the general characterization (Bertsekas, 2009). Hence, Lemma 2 ensures
$q^{\star}_{\alpha}\in\operatorname*{arg\,min}_{q\in\mathcal{H}}\max_{l\in\mathcal{H}}L_{\alpha}(q,l)$.

Next, we consider the constrained optimization problem when we use function
classes $\mathcal{Q}\subset\mathcal{H},\mathcal{L}\subset\mathcal{H}$. As long
as the saddle point is included in $(\mathcal{Q},\mathcal{L})$, we can prove
that $q^{\star}_{\alpha}$ is a unique minimaxer.

######  Lemma 3.

Suppose Assumptions 1 and 2 hold, $q^{\star}_{\alpha}\in\mathcal{Q}$, and
$l^{\star}_{\alpha}\in\mathcal{L}$. Then, we have that
$q^{\star}_{\alpha}=\operatorname*{arg\,min}_{q\in\mathcal{Q}}\sup_{l\in\mathcal{L}}L_{\alpha}(q,l)$
on the support $({\mathcal{S}}\times\mathcal{A})_{b}$.

This establishes that realizability
($q^{\star}_{\alpha}\in\mathcal{Q},\,l^{\star}_{\alpha}\in\mathcal{L}$) is
sufficient to identify $q^{\star}_{\alpha}$ on the offline data distribution.
At a high level,
$q^{\star}_{\alpha}\in\operatorname*{arg\,min}_{q\in\mathcal{Q}}\sup_{l\in\mathcal{L}}L_{\alpha}(q,l)$
is established through the invariance of saddle points, _i.e._ , saddle points
over original sets remain saddle points over restricted sets. Its uniqueness
is verified by the strong convexity in $q$ of $L_{\alpha}(q,l)$ induced by
$\mathbb{E}_{(s,a)\sim P_{b}}[q^{2}(s,a)]$.

###  4.2 $L^{2}$-convergence Rate for Soft Q-estimators

Based on the population-level results in Section 4.1, we give a finite-sample
error analysis of $\hat{q}_{\alpha}$

######  Assumption 3 (Realizability of soft Q-function).

Suppose $q^{\star}_{\alpha}\in\mathcal{Q}$ and $\|q\|_{\infty}\leq
B_{\mathcal{Q}}\,\forall q\in\mathcal{Q}$.

######  Assumption 4 (Realizability of Lagrange multiplier).

Suppose $l^{\star}_{\alpha}\in\mathcal{L}$ and $\|l\|_{\infty}\leq
B_{\mathcal{L}}\,\forall l\in\mathcal{L}$.

It is natural to set $B_{\mathcal{Q}}=(1-\gamma)^{-1}R_{\max}$ and
$B_{\mathcal{L}}=(1-\gamma)^{-1}R_{\max}\|d_{\pi^{*}_{\alpha},P_{b}}/P_{b}\|_{\infty}$,
but letting these be arbitrary offers further flexibility to our results.

######  Theorem 1 ($L^{2}$-convergence of soft Q-estimators).

Suppose Assumptions 1, 2, 3, and 4 hold. Then, with probability $1-\delta$,
the $L^{2}$-error $\|\hat{q}_{\alpha}-q^{\star}_{\alpha}\|_{2}$ is upper-
bounded by

$c\left(\mathcal{B}^{2}_{\mathcal{Q}}+\mathcal{B}_{\mathcal{Q}}\mathcal{B}_{\mathcal{L}}\\{\alpha+\ln(|\mathcal{A}|)\\}\right)^{1/2}\left(\ln(|\mathcal{Q}||\mathcal{L}|/\delta)/n\right)^{1/4}.$

Our result is significant as it relies on realizability-type conditions rather
than Bellman closedness. Since the majority of existing works focus on non-
regularized Q-functions, we postpone the comparison to these existing works to
the next section. Note when $\mathcal{Q}$ and $\mathcal{L}$ are infinite, we
can easily replace $|\mathcal{Q}|,|\mathcal{L}|$ with their
$L^{\infty}$-covering numbers following Uehara et al. (2021). Details are
given in the appendix.

###  4.3 $L^{2}$-convergence Rate for $Q^{\star}$-functions

Next, we give analogous finite-sample error analysis of $\hat{q}_{0}$
leveraging the same reasoning.

######  Assumption 5 (Realizability of $Q^{\star}$-functions).

Suppose $q^{\star}\in\mathcal{Q}$ and $\|q\|_{\infty}\leq
B_{\mathcal{Q}}\,\forall q\in\mathcal{Q}$.

Next, we define the Lagrange multiplier:

$\displaystyle\textstyle\\{P^{\star}\\}^{\top}$ $\displaystyle:\mathcal{H}\ni
f\mapsto\int P(\cdot\mid
s,a)\pi^{\star}(\cdot\mid\cdot)f(s,a)\mathrm{d}\mu(s,a)\in\mathcal{H},$
$\displaystyle l^{\star}$
$\displaystyle\coloneqq\\{(I-\gamma\\{P^{\star}\\}^{\top})^{-1}(q^{\star}P_{\pi_{b}})\\}/P_{\pi_{b}}.$

While $l^{\star}$ involves the density ratio, this is always well-defined as
long as $\|d_{\pi^{\star},{P_{b}}}/P_{b}\|_{\infty}<\infty$.  Then, it can be
similarly established that $(q^{\star},l^{\star})$ is a saddle point of
$L_{0}(q,l)$ over $q\in\mathcal{H},l\in\mathcal{H}$ as we show in Lemma 2. We
lastly require its realizability.

######  Assumption 6 (Realizability of Lagrange multiplier).

Suppose $\|d_{\pi^{\star},{P_{b}}}/P_{b}\|_{\infty}<\infty$ and
$l^{\star}\in\mathcal{L}$. Further suppose $\|l\|_{\infty}\leq
B_{\mathcal{L}}\,\forall l\in\mathcal{L}$.

######  Theorem 2 ($L^{2}$-convergence of Q-estimators).

Suppose Assumptions 5 and 6 hold. Then, with probability $1-\delta$, the
$L^{2}$-error $\|\hat{q}_{0}-q^{\star}\|_{2}$ is upper-bounded by

$c\left(\mathcal{B}^{2}_{\mathcal{Q}}+\mathcal{B}_{\mathcal{L}}\mathcal{B}_{\mathcal{Q}}\right)^{1/2}(\ln(|\mathcal{Q}||\mathcal{L}|/\delta)/n)^{1/4}.$

To the best of our knowledge, this is the first guarantee on $L^{2}$ errors
for learning $q^{*}$ using _general function approximation without relying on
Bellman completeness_. This is highly nontrivial, and we have carefully
crafted our algorithm to obtain this guarantee. Existing results are often
specific to particular models, such as linear models (Shi et al., 2022a), or
they require Bellman completeness (Chen and Jiang, 2019; Chen and Qi, 2022),
or they are limited to offline policy evaluation scenarios (Huang and Jiang,
2022) (_i.e._ , cases involving linear Bellman operators, but nonlinear
Bellman operators). Actually, it seems that even under the assumption of
Bellman completeness, obtaining an L2 guarantee _without strong coverage
assumptions_ remains unclear. A detailed comparison among these different
approaches is presented in Section A.

##  5 Finite Sample Guarantee of MSQP

In this section, we present our primary sample complexity guarantee for our
MSQP algorithm under the assumptions of realizability of $q^{\star}_{\alpha}$
and $l^{\star}_{\alpha}$ and partial coverage. We first show the learned
policy $\hat{\pi}_{\alpha}$ can compete with $\pi^{\star}_{\alpha}$. Finally
we show $\hat{\pi}_{\alpha}$ can compete with $\pi^{\star}$ by selecting
$\alpha$ properly.

We first introduce the flattened behavior policy $\pi^{\diamond}_{b}$, which
is uniform on the support of $\pi_{b}$. We use it as a technical device to
define a model-free concentrability coefficient following Xie et al. (2021).

######  Definition 1 (Model-free concentrability coefficient).

Define

$\displaystyle
C_{\mathcal{Q},d_{\pi^{\star}_{\alpha},\mu_{0}}}\coloneqq\sup_{q\in\mathcal{Q}}\frac{\mathbb{E}_{s\sim
d_{\pi^{\star}_{\alpha},\mu_{0}},a\sim\pi^{\diamond}_{b}(a\mid
s)}[\|q(s,a)-q^{\star}_{\alpha}(s,a)\|^{2}_{2}]}{\mathbb{E}_{(s,a)\sim
P_{b}}[\|q(s,a)-q^{\star}_{\alpha}(s,a)\|^{2}_{2}]}$

where $\pi^{\diamond}_{b}(\cdot\mid s)=\begin{cases}0\quad&\pi_{b}(\cdot\mid
s)=0\\\ 1/|\\{a\in\mathcal{A}\mid\pi_{b}(a\mid s)>0\\}|\;&\pi_{b}(\cdot\mid
s)>0\end{cases}$ is the flattened behavior policy.

Clearly, $C_{\mathcal{Q},d_{\pi^{\star}_{\alpha},\mu_{0}}}$ is smaller than
density-ratio-based concentrability coefficient, in other words,

$C_{\mathcal{Q},d_{\pi^{\star}_{\alpha},\mu_{0}}}\leq\max_{(s,a)}\frac{d_{\pi^{\star}_{\alpha},\mu_{0}}(s)\pi^{\diamond}_{b}(a\mid
s)}{P_{b}(s)\pi_{b}(a\mid s)}.$

Here, we always have $\|\pi^{\diamond}_{b}/\pi_{b}\|<\infty$ even if
$\pi_{b}(a\mid s)$ is $0$ for some $(s,a)$. In the special case where
$\pi_{b}(a\mid s)\geq 1/C^{\prime}$ for any $(s,a)$, we have
$C_{\mathcal{Q},d_{\pi^{\star}_{\alpha},\mu_{0}}}\leq
C^{\prime}\|d_{\pi^{\star}_{\alpha},\mu_{0}}/P_{b}\|_{\infty}$. The
coefficient $C_{\mathcal{Q},d_{\pi^{\star}_{\alpha},\mu_{0}}}$ is is a refined
concentrability coefficient, which adapts to a function class $\mathcal{Q}$.
For example, in linear MDPs, it reduces to a relative condition number as
follows. Similar properties are obtained in related works (Xie et al., 2021;
Uehara and Sun, 2021).

######  Example 1 (Linear MDPs).

A linear MDP is one such that, for a known feature vector
$\phi:{\mathcal{S}}\times\mathcal{A}\to\mathbb{R}^{d}$, the true density
satisfies $P(s^{\prime}\mid
s,a)=\langle\mu^{\star}(s^{\prime}),\phi(s,a)\rangle$ for some
$\mu^{\star}:{\mathcal{S}}\to\mathbb{R}^{d}$ and the reward function satisfies
$\mathbb{E}[r\mid s,a]=\langle\theta_{r},\phi(s,a)\rangle$ for some
$\theta_{r}\in\mathbb{R}^{d}$.

In linear MDPs, $q^{\star}_{\alpha}$ is clearly linear in $\phi(s,a)$. Hence,
the natural function class is
$\mathcal{Q}=\\{\langle\theta,\phi(s,a)\rangle\mid\|\theta\|\leq B\\}$ for a
certain $B\in\mathbb{R}^{+}$. Then, we have

$\displaystyle C_{\mathcal{Q},d_{\pi^{\star}_{\alpha},\mu_{0}}}=\sup_{x\neq
0}\frac{x^{\top}\mathbb{E}_{s\sim
d_{\pi^{\star}_{\alpha},\mu_{0}},a\sim\pi^{\diamond}_{b}(a\mid
s)}[\phi(s,a)\phi(s,a)^{\top}]x}{x^{\top}\mathbb{E}_{(s,a)\sim
P_{b}}[\phi(s,a)\phi(s,a)^{\top}]x}.$

We are now prepared to present our main result, which states that given the
realizability of the soft Q-function $q^{\star}_{\alpha}$ and Lagrange
multiplier $l^{\star}_{\alpha}$, it is possible to compete with
$\pi^{\star}_{\alpha}$ under the coverage condition
$C_{\mathcal{Q},d_{\pi^{\star}_{\alpha},\mu_{0}}}<\infty,\|d_{\pi^{\star}_{\alpha},P_{b}}/P_{b}\|_{\infty}<\infty$.

######  Theorem 3 ($\hat{\pi}_{\alpha}$ can compete with
$\pi^{\star}_{\alpha}$).

Fix $\alpha>0$. Suppose Assumptions 1, 2, 3, and 4 hold. With probability
$1-\delta$, the regret $J(\pi^{\star}_{\alpha})-J(\hat{\pi}_{\alpha})$ is
upper-bounded by

$\displaystyle
n^{-1/4}\mathrm{Poly}\left(|\mathcal{A}|,\mathcal{B}_{\mathcal{Q}},\mathcal{B}_{\mathcal{L}},C_{\mathcal{Q},d_{\pi^{\star}_{\alpha},\mu_{0}}},\ln\left(\frac{|\mathcal{Q}||\mathcal{L}|}{\delta}\right),\frac{1}{1-\gamma},R_{\max}\right)$

The proof mainly consists of two steps: (1) obtaining $L^{2}$-errors of
$\hat{q}_{\alpha}$ as previously demonstrated in Theorem 1, (2) translating
this error into the error of $\hat{\pi}_{\alpha}$. In the second step, the
Lipshitz continuity of the softmax function plays a crucial role. If there is
no regularization ($\alpha=0$) and the greedy policy of $q^{\star}_{0}$ is
utilized, the second step does not proceed (without any further additional
assumptions).

Our ultimate goal is to compete with $\pi^{\star}$. Theorem 3 serves as the
primary foundation for this goal. The remaining task is to analyze the
approximation error $J(\pi^{\star})-J(\pi^{\star}_{\alpha})$. Fortunately,
this term can be controlled through $\alpha$ and the density ratio between
$\pi^{\star}$ and $\pi_{b}$. Then, by properly controlling $\alpha$, we can
obtain the following sample complexity result.

######  Theorem 4 (PAC guarantee of $\hat{\pi}_{\alpha}$).

Fix any $\epsilon>0$. Suppose Assumptions 1, 2, 3, and 4 hold for
$\alpha=c/n^{1/8}$ and $\|\pi^{\star}_{0}/\pi_{b}\|_{\infty}\leq C_{0}$,
$C_{\mathcal{Q},d_{\pi^{\star}_{\alpha},\mu_{0}}}<\infty$. Then, if $n$ is at
least

$\displaystyle\epsilon^{-8}\mathrm{Poly}(|\mathcal{A}|,\mathcal{B}_{\mathcal{Q}},\mathcal{B}_{\mathcal{L}},C_{\mathcal{Q},d_{\pi^{\star}_{\alpha},\mu_{0}}},\ln(|\mathcal{Q}||\mathcal{L}|/\delta),(1-\gamma)^{-1},\ln(C_{0}),R_{\max}),$

with probability at least $1-\delta$, we can ensure
$J(\pi^{\star})-J(\hat{\pi}_{\alpha})\leq\epsilon$.

In summary, the realiazability of $q^{\star}_{\alpha},l^{\star}_{\alpha}$,
per-step coverage $\|\pi^{\star}_{0}/\pi_{b}\|_{\infty}<\infty$ and partial
coverage
$C_{\mathcal{Q},d_{\pi^{\star}_{\alpha},\mu_{0}}}<\infty,\|d_{\pi^{\star}_{\alpha},P_{b}}/P_{b}\|_{\infty}<\infty$
are sufficient to compete with $\pi^{\star}$. This is a novel and attractive
result. Firstly, if we solely use the naïve FQI or Bellman residual
minimization, existing PAC results require the global coverage
$\|d_{\pi,\mu_{0}}/P_{b}\|_{\infty}<\infty$ for any possible policy $\pi$
(Munos and Szepesvári, 2008; Antos et al., 2008). Our result only requires
coverage under a single policy $\pi^{\star}_{\alpha}$ (near-optimal policy).
Secondly, we only require the realizability of two functions, and we do not
necessitate realizability-type conditions for all policies in the policy class
or Bellman completeness, unlike existing works with partial coverage (Xie et
al., 2021; Jiang and Huang, 2020).

The most similar result is Zhan et al. (2022). However, our guarantee
possesses a certain advantage over their guarantee as follows. They
demonstrate the realizability of certain functions
$\tilde{w}^{\star}_{\alpha},v^{\star}_{\alpha}$ and partial coverage
$\|d_{\tilde{\pi}_{\alpha},\mu_{0}}/P_{b}\|<\infty$ are sufficient conditions
in offline RL, where
$\tilde{w}^{\star}_{\alpha}=d_{\tilde{\pi}_{\alpha},\mu_{0}}/P_{b}$
($\tilde{\pi}_{\alpha}$ is a certain regularized optimal policy, but
fundamentally distinct from $\pi^{\star}_{\alpha}$) and $v^{\star}_{\alpha}$
is a near-optimal regularized value function parameterized by $\alpha$. Here,
we have $\tilde{w}^{\star}_{0}=w^{\star},v^{\star}_{0}=v^{\star}$. Our
guarantee has a similar flavor in the sense that it roughly illustrates
realizability and partial coverage are sufficient conditions. However, the
meanings of realizability and partial coverage are significantly different. In
particular, by employing our algorithm, we can ensure PAC guarantees under the
boundedness of the refined concentrability coefficient
$C_{\mathcal{Q},d_{\pi^{\star}_{\alpha},\mu_{0}}}<\infty$ (and
$\|d_{\pi^{\star}_{\alpha},P_{b}}/P_{b}\|_{\infty}$ through
$\mathcal{B}_{\mathcal{L}}$). As a result, the $L^{\infty}$-norm of the
density-ratio-based concentrability coefficient
$\|d_{\pi^{\star}_{\alpha},\mu_{0}}/P_{b}\|_{\infty}$ can even be infinite.
More specifically, we can permit situations where
$\max_{s}\mu_{0}(s)/P_{b}(s)=\infty$ as we will see the practical example
soon. Conversely, Zhan et al. (2022) excludes this possibility since the
algorithm explicitly estimates the density ratio $\tilde{w}^{\star}_{\alpha}$.

######  Example 2 (Contextual bandit under external validity).

We consider the contextual bandit setting where we want to optimize
$J(\pi)=\mathbb{E}_{s\sim\mu_{0},a\sim\pi(s),r\sim P_{r}(s,a)}[r]$ using
offline data $s\sim P_{b},a\sim\pi_{b}(s),r\sim P(s,a)$. This is the simplest
RL setting with $\gamma=0$. Here, note $\mu_{0}$ could be different from
$P_{b}$. This case often happens in practice as discussed in the literature on
causal inference related to external validity (Pearl and Bareinboim, 2014;
Dahabreh et al., 2019; Uehara et al., 2020), which refers to the shift between
the target population and the offline data. Here, our PAC guarantee does not
require that $\mu_{0}(s)$ is covered by $P_{b}(s)$ in terms of the density
ratio as long as the relative condition number is upper-bounded when we use
linear models. On the other hand, Zhan et al. (2022) excludes this
possibility.

Despite the aforementioned advantage of our approach, unfortunately, our
sample complexity of $O(1/\epsilon^{8})$ is slower compared to that of
$O(1/\epsilon^{6})$ in Zhan et al. (2022). In the following, we demonstrate
that MQP, which is a special version of MSQP when $\alpha\to 0$, can achieve a
faster rate of $O(1/\epsilon^{2})$.

##  6 Finite Sample Guarantee of MQP

In this section, building upon the convergence result of $\hat{q}_{0}$, we
demonstrate the finite sample guarantee of our MQP algorithm under partial
coverage. We first introduce the soft margin.

######  Assumption 7 (Soft margin).

For any $a^{\prime}\in\mathcal{A}$, there exists
$t_{0}\in\mathbb{R}^{+},\beta\in(0,\infty]$ such that

$\displaystyle\mathbb{P}_{s\sim
d_{{\pi^{\star},\mu_{0}}}}(0<|q^{\star}(s,\pi^{\star}(s))-q^{\star}(s,a^{\prime})|<t)\leq(t/t_{0})^{\beta}$

for any $t>0$. Here, we use the convention $x^{\infty}=0$ if $0<x<1$ and
$x^{\infty}=\infty$ if $x>1$.

In the extreme case, if there exists a gap in $q^{\star}$ (also known as a
hard margin) so that the best action is always better than the second-best by
some lower bounded amount, then the soft margin is satisfied with
$\beta=\infty$. Thus, the soft margin is more general than the gap condition
used in Simchowitz and Jamieson (2019); Wu et al. (2022). Crucially, a gap
generally does not exist in continuous state spaces unless Q-functions are
discontinuous or one action is always option, or a gap involves a large
$t_{0}$ constant in discrete state spaces with bad dependence on the number of
states. In contrast, a soft margin with some $\beta>0$ generally holds (see,
_e.g._ , lemma 4 in Hu et al., 2021). The soft margin is widely used in the
literature on classification, decision making, and RL (Audibert and Tsybakov,
2007; Perchet and Rigollet, 2013; Luedtke and Chambaz, 2020; Hu et al., 2021,
2022).

######  Theorem 5 (PAC guarantee of $\hat{\pi}_{0}$).

Suppose Assumptions 5, 6, and 7 hold and $\|\pi^{\star}/\pi_{b}\|_{\infty}\leq
C_{0}$. Fix any $\epsilon>0$. Then, if $n$ is at least

$\displaystyle\textstyle\\{\frac{|\mathcal{A}|}{\epsilon}\\}^{\frac{4+2\beta}{\beta}}\mathrm{Poly}\left(t^{-1}_{0},|\mathcal{A}|,\mathcal{B}_{\mathcal{Q}},\mathcal{B}_{\mathcal{L}},C_{\mathcal{Q},d_{\pi^{\star},\mu_{0}}},\ln\left(\frac{|\mathcal{Q}||\mathcal{L}|}{\delta}\right),(1-\gamma)^{-1},\ln(C_{0}),R_{\max}\right)$

with probability at least $1-\delta$, we can ensure
$J(\pi^{\star})-J(\hat{\pi}_{0})\leq\epsilon$.

The proof mainly consists of two steps: (1) obtaining $L^{2}$-errors of
$\hat{q}_{0}$ as demonstrated in Theorem 2, (2) translating this error into
the error of $\hat{\pi}_{0}$. In the second step, the soft margin plays a
crucial role.

These theorems indicate that the realizability of the $Q$-function $q^{\star}$
and Lagrange multiplier $l^{\star}$, and the soft margin are sufficient for
the PAC guarantee under partial coverage
$C_{\mathcal{Q},d_{\pi^{\star},\mu_{0}}}<\infty$ ,
$\|d_{\pi^{\star},P_{b}}/P_{b}\|_{\infty}<\infty$ . Our algorithm is
_agnostic_ to $\beta$ and operates under any value of $\beta$. In particular,
when there is a gap ($\beta=\infty$), we can achieve sample complexity of
$O(1/\epsilon^{2})$ 444Similar to the findings in Wang et al. (2022), in
general offline RL, we may potentially achieve a result of $O(1/\epsilon)$. We
leave room for further enhancements in future research. . In comparison to
Theorem 3, although we additionally use the soft margin, the realizability in
Theorem 5 is more appealing since it is imposed on the standard Q-function
$q^{\star}$. The closest guarantee to our work can be found in Chen and Jiang
(2022), which demonstrates that the existence of the gap in $q^{\star}$, the
realizability of $q^{\star},w^{\star}(:=d_{\pi^{\star},\mu_{0}}/P_{\pi_{b}})$,
and partial coverage $\|w^{\star}\|_{\infty}<\infty$ are sufficient
conditions. A similar comparison is made in Ozdaglar et al. (2023). In
comparison to their work, we use the soft margin, which is significantly less
stringent.

##  7 Conclusions

We propose two value-based algorithms, MSQP and MQP, that operate under
realizability of certain functions and partial coverage (_i.e._ , single-
policy-coverage). Notably, our guarantee does not require Bellman completeness
and uniform-type realizability over the policy class. While guarantees with
similar flavors are obtained in Zhan et al. (2022); Chen and Jiang (2022),
MSQP can potentially relax the density-ratio-based partial coverage regarding
the initial distribution as opposed to Zhan et al. (2022), and MQP can operate
under the soft-margin, which is less stringent than the hard margin imposed in
Chen and Jiang (2022). Moreover, both algorithms work on Q-functions, which
are more commonly used in practice.

## References

  * Antos et al. (2008) András Antos, Csaba Szepesvári, and Rémi Munos.  Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path.  _Machine Learning_ , 71(1):89–129, 2008.
  * Audibert and Tsybakov (2007) Jean-Yves Audibert and Alexandre B Tsybakov.  Fast learning rates for plug-in classifiers.  _The Annals of statistics_ , 35(2):608–633, 2007\.
  * Bai et al. (2022) Chenjia Bai, Lingxiao Wang, Zhuoran Yang, Zhihong Deng, Animesh Garg, Peng Liu, and Zhaoran Wang.  Pessimistic bootstrapping for uncertainty-driven offline reinforcement learning.  _arXiv preprint arXiv:2202.11566_ , 2022.
  * Bertsekas (2009) Dimitri Bertsekas.  _Convex optimization theory_ , volume 1.  Athena Scientific, 2009.
  * Chang et al. (2021) Jonathan Chang, Masatoshi Uehara, Dhruv Sreenivas, Rahul Kidambi, and Wen Sun.  Mitigating covariate shift in imitation learning via offline data with partial coverage.  _Advances in Neural Information Processing Systems_ , 34:965–979, 2021.
  * Chen and Jiang (2019) Jinglin Chen and Nan Jiang.  Information-theoretic considerations in batch reinforcement learning.  In _International Conference on Machine Learning_ , pages 1042–1051. PMLR, 2019.
  * Chen and Jiang (2022) Jinglin Chen and Nan Jiang.  Offline reinforcement learning under value and density-ratio realizability: the power of gaps.  _arXiv preprint arXiv:2203.13935_ , 2022.
  * Chen and Qi (2022) Xiaohong Chen and Zhengling Qi.  On well-posedness and minimax optimal rates of nonparametric q-function estimation in off-policy evaluation.  _arXiv preprint arXiv:2201.06169_ , 2022.
  * Cole and Stuart (2010) Stephen R Cole and Elizabeth A Stuart.  Generalizing evidence from randomized clinical trials to target populations: the actg 320 trial.  _American journal of epidemiology_ , 172(1):107–115, 2010.
  * Dahabreh et al. (2019) Issa J Dahabreh, Sarah E Robertson, Eric J Tchetgen, Elizabeth A Stuart, and Miguel A Hernán.  Generalizing causal inferences from individuals in randomized trials to all trial-eligible individuals.  _Biometrics_ , 75(2):685–694, 2019.
  * Fakoor et al. (2021) Rasool Fakoor, Jonas W Mueller, Kavosh Asadi, Pratik Chaudhari, and Alexander J Smola.  Continuous doubly constrained batch reinforcement learning.  _Advances in Neural Information Processing Systems_ , 34:11260–11273, 2021.
  * Fox et al. (2015) Roy Fox, Ari Pakman, and Naftali Tishby.  Taming the noise in reinforcement learning via soft updates.  _arXiv preprint arXiv:1512.08562_ , 2015.
  * Gao and Pavel (2017) Bolin Gao and Lacra Pavel.  On the properties of the softmax function with application in game theory and reinforcement learning.  _arXiv preprint arXiv:1704.00805_ , 2017.
  * Geist et al. (2019) Matthieu Geist, Bruno Scherrer, and Olivier Pietquin.  A theory of regularized markov decision processes.  In _International Conference on Machine Learning_ , pages 2160–2169. PMLR, 2019.
  * Haarnoja et al. (2018) Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  In _International conference on machine learning_ , pages 1861–1870. PMLR, 2018.
  * Hu et al. (2021) Yichun Hu, Nathan Kallus, and Masatoshi Uehara.  Fast rates for the regret of offline reinforcement learning.  _arXiv preprint arXiv:2102.00479_ , 2021.
  * Hu et al. (2022) Yichun Hu, Nathan Kallus, and Xiaojie Mao.  Fast rates for contextual linear optimization.  _Management Science_ , 68(6):4236–4245, 2022\.
  * Huang and Jiang (2022) Audrey Huang and Nan Jiang.  Beyond the return: Off-policy function estimation under user-specified error-measuring distributions.  In _Neurips_ , 2022.
  * Jiang and Huang (2020) Nan Jiang and Jiawei Huang.  Minimax value interval for off-policy evaluation and policy optimization.  _Advances in Neural Information Processing Systems_ , 33:2747–2758, 2020.
  * Jin et al. (2020) Ying Jin, Zhuoran Yang, and Zhaoran Wang.  Is pessimism provably efficient for offline rl?  _arXiv preprint arXiv:2012.15085_ , 2020.
  * Kidambi et al. (2020) Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims.  Morel: Model-based offline reinforcement learning.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 21810–21823. Curran Associates, Inc., 2020.
  * Levine et al. (2020) Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu.  Offline reinforcement learning: Tutorial, review, and perspectives on open problems.  _arXiv preprint arXiv:2005.01643_ , 2020.
  * Li et al. (2022) Gene Li, Cong Ma, and Nathan Srebro.  Pessimism for offline linear contextual bandits using lp confidence sets.  _arXiv preprint arXiv:2205.10671_ , 2022.
  * Luedtke and Chambaz (2020) Alex Luedtke and Antoine Chambaz.  Performance guarantees for policy learning.  In _Annales de l’IHP Probabilites et statistiques_ , volume 56, page 2162. NIH Public Access, 2020.
  * Munos and Szepesvári (2008) Rémi Munos and Csaba Szepesvári.  Finite-time bounds for fitted value iteration.  _Journal of Machine Learning Research_ , 9(5), 2008.
  * Nachum and Dai (2020) Ofir Nachum and Bo Dai.  Reinforcement learning via fenchel-rockafellar duality.  _arXiv preprint arXiv:2001.01866_ , 2020.
  * Neu et al. (2017) Gergely Neu, Anders Jonsson, and Vicenç Gómez.  A unified view of entropy-regularized markov decision processes.  _arXiv preprint arXiv:1705.07798_ , 2017.
  * Nguyen-Tang et al. (2022) Thanh Nguyen-Tang, Ming Yin, Sunil Gupta, Svetha Venkatesh, and Raman Arora.  On instance-dependent bounds for offline reinforcement learning with linear function approximation.  _arXiv preprint arXiv:2211.13208_ , 2022.
  * Ozdaglar et al. (2023) Asuman E Ozdaglar, Sarath Pattathil, Jiawei Zhang, and Kaiqing Zhang.  Revisiting the linear-programming framework for offline rl with general function approximation.  In _International Conference on Machine Learning_ , pages 26769–26791. PMLR, 2023.
  * Pearl and Bareinboim (2014) Judea Pearl and Elias Bareinboim.  External validity: From do-calculus to transportability across populations.  In _Statistical Science_ , pages 451–482. 2014.
  * Perchet and Rigollet (2013) Vianney Perchet and Philippe Rigollet.  The multi-armed bandit problem with covariates.  _The Annals of Statistics_ , 41(2):693–721, 2013\.
  * Rashidinejad et al. (2021) Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell.  Bridging offline reinforcement learning and imitation learning: A tale of pessimism.  _arXiv preprint arXiv:2103.12021_ , 2021.
  * Rashidinejad et al. (2022) Paria Rashidinejad, Hanlin Zhu, Kunhe Yang, Stuart Russell, and Jiantao Jiao.  Optimal conservative offline rl with general function approximation via augmented lagrangian.  _arXiv preprint arXiv:2211.00716_ , 2022.
  * Schulman et al. (2017) John Schulman, Xi Chen, and Pieter Abbeel.  Equivalence between policy gradients and soft q-learning.  _arXiv preprint arXiv:1704.06440_ , 2017.
  * Shi et al. (2022a) Chengchun Shi, Sheng Zhang, Wenbin Lu, and Rui Song.  Statistical inference of the value function for reinforcement learning in infinite-horizon settings.  _Journal of the Royal Statistical Society Series B: Statistical Methodology_ , 84(3):765–793, 2022a.
  * Shi et al. (2022b) Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi.  Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity.  _arXiv preprint arXiv:2202.13890_ , 2022b.
  * Simchowitz and Jamieson (2019) Max Simchowitz and Kevin G Jamieson.  Non-asymptotic gap-dependent regret bounds for tabular mdps.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Uehara and Sun (2021) Masatoshi Uehara and Wen Sun.  Pessimistic model-based offline reinforcement learning under partial coverage.  _ICLR 2022_ , 2021.
  * Uehara et al. (2020) Masatoshi Uehara, Masahiro Kato, and Shota Yasui.  Off-policy evaluation and learning for external validity under a covariate shift.  _Advances in Neural Information Processing Systems_ , 33:49–61, 2020.
  * Uehara et al. (2021) Masatoshi Uehara, Masaaki Imaizumi, Nan Jiang, Nathan Kallus, Wen Sun, and Tengyang Xie.  Finite sample analysis of minimax offline reinforcement learning: Completeness, fast rates and first-order efficiency.  _arXiv preprint arXiv:2102.02981_ , 2021.
  * Wang et al. (2022) Xinqi Wang, Qiwen Cui, and Simon S Du.  On gap-dependent bounds for offline reinforcement learning.  _Advances in Neural Information Processing Systems_ , 35:14865–14877, 2022.
  * Wu et al. (2022) Jingfeng Wu, Vladimir Braverman, and Lin Yang.  Gap-dependent unsupervised exploration for reinforcement learning.  In _International Conference on Artificial Intelligence and Statistics_ , pages 4109–4131. PMLR, 2022.
  * Wu et al. (2019) Yifan Wu, George Tucker, and Ofir Nachum.  Behavior regularized offline reinforcement learning.  _arXiv preprint arXiv:1911.11361_ , 2019.
  * Xie and Jiang (2020) Tengyang Xie and Nan Jiang.  Q* approximation schemes for batch reinforcement learning: A theoretical comparison.  In _Conference on Uncertainty in Artificial Intelligence_ , pages 550–559. PMLR, 2020.
  * Xie et al. (2021) Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal.  Bellman-consistent pessimism for offline reinforcement learning.  _Advances in neural information processing systems_ , 34:6683–6694, 2021.
  * Yang et al. (2020) Mengjiao Yang, Ofir Nachum, Bo Dai, Lihong Li, and Dale Schuurmans.  Off-policy evaluation via the regularized lagrangian.  _Advances in Neural Information Processing Systems_ , 33:6551–6561, 2020.
  * Yin and Wang (2021) Ming Yin and Yu-Xiang Wang.  Towards instance-optimal offline reinforcement learning with pessimism.  _Advances in neural information processing systems_ , 34:4065–4078, 2021.
  * Yu et al. (2020) Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Y Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma.  Mopo: Model-based offline policy optimization.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 14129–14142, 2020.
  * Zanette and Wainwright (2022) Andrea Zanette and Martin J Wainwright.  Bellman residual orthogonalization for offline reinforcement learning.  _arXiv preprint arXiv:2203.12786_ , 2022.
  * Zhan et al. (2022) 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_ , pages 2730–2775. PMLR, 2022\.
  * Zhang et al. (2022) Xuezhou Zhang, Yiding Chen, Xiaojin Zhu, and Wen Sun.  Corruption-robust offline reinforcement learning.  In _International Conference on Artificial Intelligence and Statistics_ , pages 5757–5773. PMLR, 2022.
  * Zhu et al. (2023) Hanlin Zhu, Paria Rashidinejad, and Jiantao Jiao.  Importance weighted actor-critic for optimal conservative offline reinforcement learning.  _arXiv preprint arXiv:2301.12714_ , 2023.
  * Ziebart et al. (2008) Brian D Ziebart, Andrew L Maas, J Andrew Bagnell, Anind K Dey, et al.  Maximum entropy inverse reinforcement learning.  In _Aaai_ , volume 8, pages 1433–1438. Chicago, IL, USA, 2008.
  * Ziebart et al. (2010) Brian D Ziebart, J Andrew Bagnell, and Anind K Dey.  Modeling interaction via the principle of maximum causal entropy.  In _ICML_ , 2010.

##  Appendix A More Related Works

We elaborate on the challenge and novelty of our guarantees in comparison to
previous related works.

#### Existing $L^{2}$-guarantees for offline RL (Shi et al., 2022a).

Shi et al. (2022a) derived the $L^{2}$ convergence rate for learning the
optimal $Q^{\star}$-function. However, their result is restricted to linear
models. While linear models allow for converting Bellman residual errors into
$L^{2}$-errors under mild assumptions regarding the non-singularity of the
covariance matrix, this guarantee can be achieved through various methods such
as modified BRM (Antos et al., 2008). However, it remains unclear how to
extend this guarantee to general function approximation settings.

#### Existing $L^{2}$-guarantees for off-policy evaluation (Huang and Jiang,
2022; Zhan et al., 2022).

According to Huang and Jiang (2022), $L^{2}$-rates were obtained in the
context of offline policy evaluation, while Zhan et al. (2022) obtained the
$L^{2}$-rate for the (regularized) optimal marginal density ratio function.
While our approach builds upon these works, it is still considered novel due
to the nonlinear constraints we consider, which provide an additional
challenge in the analysis. In contrast, the constraints considered by Huang
and Jiang (2022); Zhan et al. (2022) were linear.

In order to grasp the difficulty at a high level, suppose that the state space
is tabular 555Note our theory still proceeds in the non-tabular case.. Recall
our estimator is motivated by the constrained optimization problem (3).
Although the left-hand side of (3) is convex in $q$, the constraint induced by
the equality is generally not convex. As a result, this problem is not a
convex optimization problem. Therefore, it is not straightforward whether the
saddle point exists when we consider the minimax form. This differs from
previous works (Huang and Jiang, 2022; Zhan et al., 2022), where the
constraint from the linear equality remains convex.

The key insight for addressing this issue is the realization that the equality
constraint ($=$) in (3) can be relaxed to an inequality constraint ($\leq$) in
(3). This relaxation is surprisingly valid in our problem. As a result, the
resulting optimization problem is convex, and a saddle point exists. For
further discussion, see Section B.

#### Bellman residual minimization (Antos et al., 2008; Chen and Jiang, 2019;
Chen and Qi, 2022).

Chen and Jiang (2019) derived convergence rates for Q-functions in terms of
Bellman residual errors: $\mathbb{E}_{(s,a)\sim
P_{b}}[(\mathcal{B}^{\star}q-q)^{2}(s,a)]$ where $\mathcal{B}^{\star}$ is a
Bellman operator. While the convergence of the $L^{2}$-error implies that of
the Bellman residual error since we have

$\displaystyle\mathbb{E}_{(s,a)\sim
P_{b}}[(\mathcal{B}^{\star}q-q)^{2}(s,a)]\leq(1+\gamma^{2}\mathbb{E}_{(s,a)\sim
P_{b}}[(\pi^{\star}/\pi_{b})^{2}(s,a)])\|q-q^{\star}\|^{2}_{2},$

the reverse direction does _not_ generally hold. Although Chen and Qi (2022)
demonstrated the reverse direction by postulating several potentially
stringent conditions 666These conditions would implicitly impose restriction
of the coverage of the offline data. of offline data regarding OPE, it does
not generally hold in the absence of these assumptions. Furthermore, we
consider the more challenging setting, offline policy optimization where the
Bellman operator is nonlinear. Thus, it is imperative to utilize our
specialized objective function to ensure a stronger guarantee in terms of
$L^{2}$-errors.

##  Appendix B Intuition of Why Saddle Points Exist

In this section, in the tabular setting, we explain how the original
optimization problem is reduced to a convex optimization problem in detail.
Note proofs in our theorems do not directly use the facts in this Section B.
Hence, they hold even in the non-tabular setting.

###  B.1 $Q^{\star}$-functions

We consider the optimization problem:

$\displaystyle\operatorname*{arg\,min}_{q\in\mathcal{Q}^{\star^{\prime}}}0.5\mathbb{E}_{(s,a)\sim
P_{b}}[q^{2}(s,a)]$

where $\mathcal{Q}^{\star^{\prime}}$ is a space that consists of
$q\in([{\mathcal{S}}\times\mathcal{A}]\to\mathbb{R})$ that satisfies

$\displaystyle\forall(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b};\mathbb{E}_{s^{\prime}\sim
P(\cdot\mid
s,a)}[\gamma\max_{a^{\prime}\in\mathcal{A}}q(s^{\prime},a^{\prime})+r-q(s,a)\mid
s,a]=0.$

The solution (on the offline data) is clearly $q^{\star}_{0}$. However, this
optimization problem is not a convex optimization problem. Hence, the
associated minimax optimization might not have a saddle point.

Here, we want to claim the following:

$\displaystyle
q^{\star}_{0}(s,a)=\operatorname*{arg\,min}_{q\in\mathcal{Q}^{\star^{\prime}}}0.5\mathbb{E}_{(s,a)\sim
P_{b}}[q^{2}(s,a)](\forall(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b})$ (9)

where $\mathcal{Q}^{\star^{\prime}}$ is a space that consists of
$q\in([{\mathcal{S}}\times\mathcal{A}]\to\mathbb{R})$ that satisfies

$\displaystyle\forall(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b};\mathbb{E}_{s^{\prime}\sim
P(\cdot\mid
s,a)}[\gamma\max_{a^{\prime}\in\mathcal{A}}q(s^{\prime},a^{\prime})+r-q(s,a)\mid
s,a]\leq 0.$

This is a convex optimization problem. Hence, we can expect the associated
minimax optimization would have a saddle point. In fact, this is proved as
follows.

######  Lemma 4.

The equation (9) holds.

###### Proof.

Suppose $q(s,a;c)$ is a minimum $L^{2}$-norm solution that satisfies

$\displaystyle\forall(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b};\mathbb{E}_{s^{\prime}\sim
P(\cdot\mid
s,a)}[\gamma\max_{a^{\prime}\in\mathcal{A}}q(s^{\prime},a^{\prime})+r-q(s,a)\mid
s,a]=-c(s,a)$

and $c(s,a)\geq 0$.

Suppose $c(s,a)\neq 0$ on some $(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b}$.
Then, we obtain

$\displaystyle\forall(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b};q(s,a;c)=\mathbb{E}_{\pi^{\star}(c)}[r_{t}+c(s_{t},a_{t})\mid(s_{0},a_{0})=(s,a)]$

where $\pi^{\star}(c)$ is the optimal policy when the reward is
$\tilde{r}(s,a)+c(s,a)$. This is derived by a contraction mapping theorem on
the $L^{\infty}$-space on $({\mathcal{S}}\times\mathcal{A})_{b}$. Here, recall

$\displaystyle\forall(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b};q^{\star}(s,a)=q(s,a;0)\geq
0$

Furthermore, $\forall(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b};q(s,a;0)\leq
q(s,a;c)$ clearly holds, and, especially, the strict inequality holds on some
point in $({\mathcal{S}}\times\mathcal{A})_{b}$. This is because if
$q(s,a;0)=q(s,a;c)$, we get the contradiction:

$\displaystyle\forall(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b};0=\mathbb{E}_{s^{\prime}\sim
P(\cdot\mid
s,a)}[\gamma\max_{a^{\prime}\in\mathcal{A}}q(s^{\prime},a^{\prime})+r-q(s,a)\mid
s,a]=c(s,a).$

However, in this situation, we have

$\displaystyle\mathbb{E}_{(s,a)\sim P_{b}}[q^{2}(s,a;0)]<\mathbb{E}_{(s,a)\sim
P_{b}}[q^{2}(s,a;c)].$

Thus, it contradicts $q^{2}(s,a;c)$ takes a least $L^{2}$-norm. Therefore, it
is concldued $c(s,a)=0$ for any
$(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b}$. Thus, using the contraction
mapping theorem, this implies the least $L^{2}$-norm solution is unique and
$q^{\star}(s,a)$ on $(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b}$.

∎

###  B.2 Soft $Q$-functions

We consider the optimization problem:

$\displaystyle\operatorname*{arg\,min}_{q\in\mathcal{Q}^{\prime}}0.5\mathbb{E}_{(s,a)\sim
P_{b}}[q^{2}(s,a)]$ (10)

where $\mathcal{Q}^{\prime}$ is a space that consists of
$q\in([{\mathcal{S}}\times\mathcal{A}]\to\mathbb{R})$ that satisfies

$\displaystyle\forall(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b};\mathbb{E}_{s^{\prime}\sim
P(\cdot\mid
s,a)}[\gamma\alpha\log\sum_{a^{\prime}}\\{\exp(q(s^{\prime},a^{\prime})/\alpha)\pi_{b}(a^{\prime}\mid
s^{\prime})\\}+r-q(s,a)\mid s,a]\leq 0.$ (11)

######  Lemma 5.

Suppose $\alpha\log\|\pi^{\star}/\pi_{b}\|_{\infty}\leq R_{\min}$. Then, the
solution to (10) is $q^{\star}_{\alpha}$.

###### Proof.

Suppose $q_{\alpha}(s,a;c)$ is a minimum $L^{2}$-norm solution that satisfies

$\displaystyle\forall(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b};\mathbb{E}_{s^{\prime}\sim
P(\cdot\mid
s,a)}[\gamma\alpha\log(\sum_{a^{\prime}}\exp(q(s^{\prime},a^{\prime})/\alpha)\pi_{b}(a^{\prime}\mid
s^{\prime})+r-q(s,a)\mid s,a]=-c(s,a)$

and $c(s,a)\geq 0$.

Suppose $c(s,a)\neq 0$ on some $(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b}$.
Then, we obtain

$\displaystyle\forall(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b};q_{\alpha}(s,a;c)=\mathbb{E}_{\pi^{\star}_{\alpha}(c)}[r_{t}+c(s_{t},a_{t})\mid(s_{0},a_{0})=(s,a)]$

where $\pi^{\star}_{\alpha}(c)$ is the optimal policy when the reward is
$\tilde{r}(s,a)+c(s,a)$. This is derived by a contraction mapping theorem on
the $L^{\infty}$-space on $({\mathcal{S}}\times\mathcal{A})_{b}$ 777Recall the
soft Bellman operator is a contraction mapping in $L^{\infty}$-space. .Here,
recall

$\displaystyle\forall(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b};q^{\star}_{\alpha}(s,a)=q_{\alpha}(s,a;0)\geq
0$

The proof is performed as in the first step of the proof of Lemma 2. We use
the assumption in this step.

Furthermore,
$\forall(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b};q_{\alpha}(s,a;0)\leq
q_{\alpha}(s,a;c)$ clearly holds, and, especially, the strict inequality holds
on some point in $({\mathcal{S}}\times\mathcal{A})_{b}$. This is because if
$q_{\alpha}(s,a;0)=q_{\alpha}(s,a;c)$, we get the contradiction:

$\displaystyle\forall(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b};0=\mathbb{E}_{s^{\prime}\sim
P(\cdot\mid
s,a)}[\gamma\alpha\log(\sum_{a^{\prime}}\exp(q(s^{\prime},a^{\prime})/\alpha)\pi_{b}(a^{\prime}\mid
s^{\prime})+r-q(s,a)\mid s,a]=c(s,a).$

However, in this situation, we have

$\displaystyle\mathbb{E}_{(s,a)\sim
P_{b}}[q^{2}_{\alpha}(s,a;0)]<\mathbb{E}_{(s,a)\sim
P_{b}}[q^{2}_{\alpha}(s,a;c)].$

Thus, it contradicts $q^{2}_{\alpha}(s,a;c)$ takes a least $L^{2}$-norm.
Therefore, it is concluded $c(s,a)=0$ for any
$(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b}$. Thus, using the contraction
mapping theorem, this implies the least $L^{2}$-norm solution is unique and
$q^{\star}_{\alpha}(s,a)$ on $(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b}$.

∎

##  Appendix C Proof in Section 4.1

###  C.1 Proof of Lemma 1

We define an $L^{2}$-space $H^{\prime}$ with no weight on the support of
$({\mathcal{S}}\times\mathcal{A})_{b}$. In other words, we define

$\displaystyle\langle q_{1},q_{2}\rangle_{\mathcal{H}^{\prime}}$
$\displaystyle\coloneqq\int
q_{1}(s,a)q_{2}(s,a)\mathrm{I}(P_{b}(s,a)>0)\mathrm{d}(s,a).$

Then, we have

$\displaystyle\langle l^{\star}_{\alpha},(I-\gamma
P^{\star}_{\alpha})q\rangle_{\mathcal{H}}$ $\displaystyle=\langle
P_{b}l^{\star}_{\alpha},(I-\gamma
P^{\star}_{\alpha})q\rangle_{\mathcal{H}^{\prime}}$
$\displaystyle=\langle(I-\gamma\\{P^{\star}_{\alpha}\\}^{\top})^{-1}(P_{b}q^{\star}_{\alpha}),(I-\gamma
P^{\star}_{\alpha})q\rangle_{\mathcal{H}^{\prime}}$
$\displaystyle=\langle(I-\gamma\\{P^{\star}_{\alpha}\\}^{\top})(I-\gamma\\{P^{\star}_{\alpha}\\}^{\top})^{-1}(P_{b}q^{\star}_{\alpha}),q\rangle_{\mathcal{H}^{\prime}}$
$\displaystyle=\langle
P_{b}q^{\star}_{\alpha},q\rangle_{\mathcal{H}^{\prime}}=\langle
q^{\star}_{\alpha},q\rangle_{\mathcal{H}}.$

Here, letting $P^{\star}_{\alpha}(s^{\prime},a^{\prime}\mid
s,a)=P(s^{\prime}\mid s,a)\pi^{\star}(a^{\prime}\mid s^{\prime})$ we use

$\displaystyle\langle
g_{1},P^{\star}_{\alpha}g_{2}\rangle_{\mathcal{H}^{\prime}}$
$\displaystyle=\int
g_{1}(s,a)g_{2}(s^{\prime},a^{\prime})P^{\star}_{\alpha}(s^{\prime},a^{\prime}\mid
s,a)\mathrm{I}(P_{b}(s,a)>0)\mathrm{d}\mu(s,a,s^{\prime},a^{\prime})$
(Definition) $\displaystyle=\int
g_{1}(s,a)g_{2}(s^{\prime},a^{\prime})P^{\star}_{\alpha}(s^{\prime},a^{\prime}\mid
s,a)\mathrm{I}(P_{b}(s,a)>0)\mathrm{I}(P_{b}(s^{\prime},a^{\prime})>0)\mathrm{d}\mu(s,a,s^{\prime},a^{\prime})$
(Recall we assume $\|\pi^{\star}/\pi_{b}\|\leq\infty$. )
$\displaystyle=\langle\\{P^{\star}_{\alpha}\\}^{\top}g_{1},g_{2}\rangle_{\mathcal{H}^{\prime}}.$

Note $\langle
g_{1},P^{\star}_{\alpha}g_{2}\rangle_{\mathcal{H}}=\langle\\{P^{\star}_{\alpha}\\}^{\top}g_{1},g_{2}\rangle_{\mathcal{H}}$
does _not_ generally hold.

###  C.2 Proof of Lemma 2

It is obvious that

$\displaystyle\forall
l\in\mathcal{H};L_{\alpha}(q^{\star}_{\alpha},l^{\star}_{\alpha})=L_{\alpha}(q^{\star}_{\alpha},l).$

Hence, we show

$\displaystyle\forall q\in\mathcal{H};L_{\alpha}(q,l^{\star}_{\alpha})\geq
L_{\alpha}(q^{\star}_{\alpha},l^{\star}_{\alpha})$

To achieve this goal, we show

$\displaystyle 0.5\mathbb{E}_{(s,a)\sim
P_{b}}[(q-q^{\star}_{\alpha})(s,a)^{2}]\leq
L_{\alpha}(q,l^{\star}_{\alpha})-L_{\alpha}(q^{\star}_{\alpha},l^{\star}_{\alpha}).$
(12)

Using Lemma 1, a function $l^{\star}_{\alpha}$ satisfies a key adjoint
property:

$\displaystyle\mathbb{E}_{(s,a,s^{\prime})\sim
P_{b},a^{\prime}\sim\pi^{\star}_{\alpha}(s^{\prime})}[l^{\star}_{\alpha}(s,a)\\{\gamma
q(s^{\prime},a^{\prime})-q(s,a)\\}]=-\mathbb{E}_{(s,a,s^{\prime})\sim
P_{b},a^{\prime}\sim\pi^{\star}_{\alpha}(s^{\prime})}[q^{\star}_{\alpha}(s,a)q(s,a)].$
(13)

for any $q\in\mathcal{H}$.

#### First Step: Show $l^{\star}_{\alpha}(s,a)\geq 0$ and
$q^{\star}_{\alpha}(s,a)\geq 0$ for any
$(s,a)\in{\mathcal{S}}\times\mathcal{A}$.

Recall

$\displaystyle
q^{\star}_{\alpha}(s,a)=\mathbb{E}_{\pi^{\star}_{\alpha}}[r_{0}+\sum_{t=1}^{\infty}\\{\gamma^{t}r_{t}-\alpha\gamma^{t}\log\pi^{\star}_{\alpha}(a_{t}\mid
s_{t})/\pi_{b}(a_{t}\mid s_{t})\\}\mid s_{0}=s,a_{0}=a]$

where the inside of the expectation is taken under a policy
$\pi^{\star}_{\alpha}$. Hence,

$\displaystyle
q^{\star}_{\alpha}(s,a)\geq\gamma(1-\gamma)^{-1}(R_{\min}-\alpha\log(\|\pi^{\star}_{\alpha}/\pi_{b}\|_{\infty})).$
(14)

Therefore, using Assumption 2, we have

$q^{\star}_{\alpha}(s,a)\geq 0$

for any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$. Finally, from the definition
of $l^{\star}_{\alpha}$, we obtain

$l^{\star}_{\alpha}(s,a)\geq 0$

for any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$.

#### Second Step: Show $0.5\mathbb{E}_{(s,a)\sim
P_{b}}[(q-q^{\star}_{\alpha})(s,a)^{2}]\leq
L_{\alpha}(q,l^{\star}_{\alpha})-L_{\alpha}(q^{\star}_{\alpha},l^{\star}_{\alpha})$
for any $q\in\mathcal{H}$.

Then, for any $q\in\mathcal{H}$, we have

$\displaystyle
L_{\alpha}(q,l^{\star}_{\alpha})-L_{\alpha}(q^{\star}_{\alpha},l^{\star}_{\alpha})$
$\displaystyle=0.5\mathbb{E}_{(s,a)\sim
P_{b}}[q^{2}(s,a)-q^{\star}_{\alpha}(s,a)^{2}]+$
$\displaystyle+\mathbb{E}_{(s,a,s^{\prime})\sim
P_{b}}[l^{\star}_{\alpha}(s,a)\\{\gamma\alpha\log\sum_{a^{\prime}}\\{\exp(q(s^{\prime},a^{\prime})/\alpha)\pi_{b}(a^{\prime}\mid
s^{\prime})\\}-q(s,a)\\}]$ $\displaystyle-\mathbb{E}_{(s,a,s^{\prime})\sim
P_{b}}[l^{\star}_{\alpha}(s,a)\\{\gamma\alpha\log\sum_{a^{\prime}}\\{\exp(q^{\star}_{\alpha}(s^{\prime},a^{\prime})/\alpha)\pi_{b}(a^{\prime}\mid
s^{\prime})\\}-q^{\star}_{\alpha}(s,a)\\}]$ $\displaystyle\geq
0.5\mathbb{E}_{(s,a)\sim P_{b}}[q^{2}(s,a)-q^{\star}_{\alpha}(s,a)^{2}]+$
$\displaystyle+\mathbb{E}_{(s,a,s^{\prime})\sim
P_{b}}\left[l^{\star}_{\alpha}(s,a)\gamma\frac{\sum_{a^{\prime}}\exp(q^{\star}_{\alpha}(s^{\prime},a^{\prime})/\alpha)\pi_{b}(a^{\prime}\mid
s^{\prime})\\{q(s^{\prime},a^{\prime})-q^{\star}_{\alpha}(s^{\prime},a^{\prime})\\}}{\sum_{a^{\prime}}\exp(q^{\star}_{\alpha}(s^{\prime},a^{\prime})/\alpha)\pi_{b}(a^{\prime}\mid
s^{\prime})}\right]$ (Convexity ) $\displaystyle+\mathbb{E}_{(s,a)\sim
P_{b}}[-l^{\star}_{\alpha}(s,a)q(s,a)+l^{\star}_{\alpha}(s,a)q^{\star}_{\alpha}(s,a)]$
$\displaystyle=0.5\mathbb{E}_{(s,a)\sim
P_{b}}[q^{2}(s,a)-q^{\star}_{\alpha}(s,a)^{2}]+$
$\displaystyle+\mathbb{E}_{(s,a,s^{\prime})\sim
P_{b},a^{\prime}\sim\pi^{\star}_{\alpha}(s^{\prime})}[l^{\star}_{\alpha}(s,a)\\{\gamma
q(s^{\prime},a^{\prime})-q(s,a)-\gamma
q^{\star}_{\alpha}(s^{\prime},a^{\prime})+q^{\star}_{\alpha}(s,a)\\}].$

In the convexity part, what we use is

$\displaystyle f(x)-f(y)\geq\sum_{i=1}^{|\mathcal{A}|}\frac{\partial
f}{\partial y_{i}}(x_{i}-y_{i}),\quad
f(x)=\alpha\log(\sum_{i=1}^{|\mathcal{A}|}\exp(x_{i}/\alpha)).$

and

$\forall(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b};l^{\star}_{\alpha}(s,a)\geq
0.$

Finally, by using an adjoint propety of $l^{\star}_{\alpha}$ in (13),

$\displaystyle
L_{\alpha}(q,l^{\star}_{\alpha})-L_{\alpha}(q^{\star}_{\alpha},l^{\star}_{\alpha})$
$\displaystyle\geq 0.5\mathbb{E}_{(s,a)\sim
P_{b}}[q^{2}(s,a)-q^{\star}_{\alpha}(s,a)^{2}]-\mathbb{E}_{(s,a)\sim
P_{b}}[q^{\star}_{\alpha}(s,a)\\{q(s,a)-q^{\star}_{\alpha}(s,a)\\}]$
$\displaystyle=0.5\mathbb{E}_{(s,a)\sim
P_{b}}[\\{q(s,a)-q^{\star}_{\alpha}(s,a)\\}^{2}].$

Then, (12) is concluded.

###  C.3 Proof of Lemma 3

We denote the solution of
$\operatorname*{arg\,min}_{q\in\mathcal{Q}}\sup_{l\in\mathcal{L}}L_{\alpha}(q,l)$
by $\hat{q}$. Let

$\displaystyle\hat{l}(q)=\operatorname*{arg\,max}_{l\in\mathcal{L}}L_{\alpha}(q,l),\quad\hat{l}=\hat{l}(\hat{q}).$

Then, we have

$\displaystyle
L_{\alpha}(\hat{q},l^{\star}_{\alpha})-L_{\alpha}(q^{\star}_{\alpha},l^{\star}_{\alpha})$
$\displaystyle=\underbrace{-L_{\alpha}(q^{\star}_{\alpha},l^{\star}_{\alpha})+L_{\alpha}(q^{\star}_{\alpha},\hat{l}(q^{\star}_{\alpha}))}_{(a)}\underbrace{-L_{\alpha}(q^{\star}_{\alpha},\hat{l}(q^{\star}_{\alpha}))+L_{\alpha}(\hat{q},\hat{l})}_{(c)}\underbrace{-L_{\alpha}(\hat{q},\hat{l})+L_{\alpha}(\hat{q},l^{\star}_{\alpha})}_{(d)}$
$\displaystyle\leq 0.$

In (a), we use the property of the saddle point in Lemma 2. In (c) and (e), we
use the definition of estimators. Hence,

$\displaystyle 0$ $\displaystyle\leq 0.5\mathbb{E}_{(s,a)\sim
P_{b}}[\\{q(s,a)-q^{\star}_{\alpha}(s,a)\\}^{2}]$ $\displaystyle\leq
L_{\alpha}(\hat{q},l^{\star}_{\alpha})-L_{\alpha}(q^{\star}_{\alpha},l^{\star}_{\alpha})$
(Recall (12)) $\displaystyle\leq 0.$

This concludes the statement.

###  C.4 Proof of Theorem 1

In this proof, the expectation is taken with respect to the offline data. We
define

$\displaystyle\hat{L}_{\alpha}(q,w)$
$\displaystyle=\mathbb{E}_{n}[0.5q^{2}(s,a)+l(s,a)\\{r+\alpha\gamma\log(\sum_{a^{\prime}}\exp(q(s^{\prime},a^{\prime})/\alpha)\pi_{b}(a^{\prime}\mid
s^{\prime}))-q(s,a)\\}],$ $\displaystyle\hat{l}(q)$
$\displaystyle=\operatorname*{arg\,max}_{l\in\mathcal{L}}\mathbb{E}_{n}[0.5q^{2}(s,a)+l(s,a)\\{r+\alpha\gamma\log(\sum_{a^{\prime}}\exp(q(s^{\prime},a^{\prime})/\alpha)\pi_{b}(a^{\prime}\mid
s^{\prime}))-q(s,a)\\}],$ $\displaystyle\hat{l}$
$\displaystyle=\hat{l}(\hat{q}_{\alpha}).$

We use the following decomposition:

$\displaystyle L_{\alpha}(\hat{q}_{\alpha},l^{\star}_{\alpha})$
$\displaystyle=\underbrace{-L_{\alpha}(q^{\star}_{\alpha},l^{\star}_{\alpha})+L(q^{\star}_{\alpha},\hat{l}(q^{\star}_{\alpha}))}_{(a)}\underbrace{-L_{\alpha}(q^{\star}_{\alpha},\hat{l}(q^{\star}_{\alpha}))+\hat{L}_{\alpha}(q^{\star}_{\alpha},\hat{l}(q^{\star}_{\alpha}))}_{(b)}$
$\displaystyle\underbrace{-\hat{L}_{\alpha}(q^{\star}_{\alpha},\hat{l}(q^{\star}_{\alpha}))+\hat{L}_{\alpha}(\hat{q}_{\alpha},\hat{l})}_{(c)}\underbrace{-\hat{L}_{\alpha}(\hat{q}_{\alpha},\hat{l})+\hat{L}_{\alpha}(\hat{q}_{\alpha},l^{\star}_{\alpha})}_{(d)}\underbrace{-\hat{L}_{\alpha}(\hat{q}_{\alpha},l^{\star}_{\alpha})+L_{\alpha}(\hat{q}_{\alpha},l^{\star}_{\alpha})}_{(e)}.$

Here, terms (a) is than $0$ using the saddle point property in Lemma 2. Term
(c) and (d) are less than $0$ using the construction of estimators. Besides,
using Hoeffding’s inequality, with probability $1-\delta$, terms (b) and (e)
are less than

$c\left(\mathcal{B}^{2}_{\mathcal{Q}}+\mathcal{B}_{\mathcal{Q}}\mathcal{B}_{\mathcal{L}}+\gamma\mathcal{B}_{\mathcal{L}}\\{\alpha+\alpha\ln(|\mathcal{A}|)\\}\right)\sqrt{\frac{\ln(|\mathcal{Q}||\mathcal{L}|/\delta)}{n}}.$

Hereafter, we condition on this event. Here, we use

$\displaystyle|0.5q^{2}(s,a)+l(s,a)\\{r+\alpha\gamma\log(\sum_{a^{\prime}}\exp(q(s^{\prime},a^{\prime})/\alpha)\pi_{b}(a^{\prime}\mid
s^{\prime}))-q(s,a)\\}|$ $\displaystyle\leq|\alpha
l(s,a)\gamma\log(\sum_{a^{\prime}}\exp(q(s^{\prime},a^{\prime})/\alpha)\pi_{b}(a^{\prime}\mid
s^{\prime}))|+|0.5q^{2}(s,a)+l(s,a)\\{r-q(s,a)\\}|$ $\displaystyle\leq
0.5\mathcal{B}^{2}_{\mathcal{Q}}+\mathcal{B}_{\mathcal{L}}\\{R_{\max}+\mathcal{B}_{\mathcal{Q}}\\}+\gamma\mathcal{B}_{\mathcal{L}}\alpha\max_{a^{\prime}}(\mathcal{B}_{\mathcal{Q}}/\alpha+\pi_{b}(a^{\prime}\mid
s^{\prime}))+\gamma\mathcal{B}_{\mathcal{L}}\ln(|\mathcal{A}|)$ (Use Lemma 7
and $l(s,a)\geq 0$ for any $(s,a)$.)
$\displaystyle\lesssim\mathcal{B}^{2}_{\mathcal{Q}}+\mathcal{B}_{\mathcal{L}}\mathcal{B}_{\mathcal{Q}}+\gamma\mathcal{B}_{\mathcal{L}}\\{\alpha+\alpha\ln(|\mathcal{A}|)\\}.$

Therefore,

$\displaystyle 0.5\mathbb{E}_{(s,a)\sim
P_{b}}[\\{\hat{q}_{\alpha}(s,a)-q^{\star}_{\alpha}(s,a)\\}^{2}]$
$\displaystyle\leq
L(l^{\star}_{\alpha},\hat{q}_{\alpha})-L(l^{\star}_{\alpha},q^{\star}_{\alpha})$
(Recall (12)) $\displaystyle\leq
c\left(\mathcal{B}^{2}_{\mathcal{Q}}+\mathcal{B}_{\mathcal{L}}\mathcal{B}_{\mathcal{Q}}+\mathcal{B}_{\mathcal{L}}\gamma\\{\alpha+\alpha\ln(|\mathcal{A}|)\\}\right)\sqrt{\frac{\ln(|\mathcal{Q}||\mathcal{L}|/\delta)}{n}}.$

In the first inequality, we use (12).

###  C.5 Proof of Theorem 2

In this proof, the expectation is taken w.r.t. the offline data. We define

$\displaystyle L_{0}(q,l)$
$\displaystyle=\mathbb{E}[0.5q^{2}(s,a)+l(s,a)\\{r+\gamma\max_{a^{\prime}}(q(s^{\prime},a^{\prime})-q(s,a)\\}],$
$\displaystyle\hat{L}_{0}(q,l)$
$\displaystyle=\mathbb{E}_{n}[0.5q^{2}(s,a)+l(s,a)\\{r+\gamma\max_{a^{\prime}}q(s^{\prime},a^{\prime})-q(s,a)\\}],$
$\displaystyle\hat{l}(q)$
$\displaystyle=\operatorname*{arg\,max}_{l}\mathbb{E}_{n}[0.5q^{2}(s,a)+l(s,a)\\{r+\max_{a^{\prime}}q(s^{\prime},a^{\prime})-q(s,a)\\}],$
$\displaystyle\hat{l}$ $\displaystyle=\hat{l}(\hat{q}_{0}).$

#### Part1: Show $l^{\star}(s,a)\geq 0$ for any
$(s,a)\in{\mathcal{S}}\times\mathcal{A}$.

First, since $R_{\min}\geq 0$, we have $q^{\star}(s,a)\geq 0$. Then, recalling
the definition:

$l^{\star}\coloneqq\\{(I-\gamma\\{P^{\star}\\}^{\top})^{-1}(q^{\star}P_{\pi_{b}})\\}/P_{\pi_{b}},$

we obtain $l^{\star}(s,a)\geq 0$ for any
$(s,a)\in{\mathcal{S}}\times\mathcal{A}$.

#### Part 2: Showing $0.5\mathbb{E}_{(s,a)\sim
P_{b}}[(q-q^{\star})(s,a)^{2}]\leq
L_{0}(q,l^{\star})-L_{0}(q^{\star},l^{\star}).$

Note $l^{\star}(s,a)$ satisfies

$\displaystyle\mathbb{E}_{(s,a,s^{\prime})\sim
P_{b},a^{\prime}\sim\pi^{\star}(s^{\prime})}[l^{\star}(s,a)\\{\gamma
q(s^{\prime},a^{\prime})-q(s,a)\\}]=-\mathbb{E}_{(s,a,s^{\prime})\sim
P_{b},a^{\prime}\sim\pi^{\star}(s^{\prime})}[q^{\star}(s,a)q(s,a)].$ (15)

for any $q(s,a)\in\mathcal{Q}$.

Then, for any $q\in\mathcal{Q}$, we have

$\displaystyle L_{0}(q,l^{\star})-L_{0}(q^{\star},l^{\star})$
$\displaystyle=0.5\mathbb{E}_{(s,a)\sim
P_{b}}[q^{2}(s,a)-q^{\star}(s,a)^{2}]+\mathbb{E}_{(s,a,s^{\prime})\sim
P_{b}}[l^{\star}(s,a)\\{\gamma\max_{a^{\prime}}q(s^{\prime},a^{\prime})-q(s,a)\\}]$
$\displaystyle-\mathbb{E}_{(s,a,s^{\prime})\sim
P_{b}}[l^{\star}(s,a)\\{\gamma\max_{a^{\prime}}q^{\star}(s^{\prime},a^{\prime})-q^{\star}(s,a)\\}]$
$\displaystyle\geq 0.5v\mathbb{E}_{(s,a)\sim
P_{b}}[q^{2}(s,a)-q^{\star}(s,a)^{2}]+\mathbb{E}_{(s,a,s^{\prime})\sim
P_{b}}[l^{\star}(s,a)\\{\gamma q(s^{\prime},\pi^{\star}(s))-\gamma
q^{\star}(s^{\prime},\pi^{\star}(s))\\}]$ (Convexity )
$\displaystyle+\mathbb{E}_{(s,a)\sim
P_{b}}[-l^{\star}(s,a)q(s,a)+l^{\star}(s,a)q^{\star}(s,a)]$
$\displaystyle=0.5\mathbb{E}_{(s,a)\sim
P_{b}}[q^{2}(s,a)-q^{\star}(s,a)^{2}]+$
$\displaystyle+\mathbb{E}_{(s,a,s^{\prime})\sim
P_{b},a^{\prime}\sim\pi^{\star}(s^{\prime})}[l^{\star}(s,a)\\{\gamma
q(s^{\prime},a^{\prime})-q(s,a)-\gamma
q^{\star}(s^{\prime},a^{\prime})+q^{\star}(s,a)\\}].$

In the convexity part, what we use is

$\displaystyle\max_{i}\\{f(x_{i})\\}-\max_{i}\\{f(y_{i})\\}\geq
f(x_{\operatorname*{arg\,max}_{i}\\{f(y_{i})\\}})-\max_{i}\\{f(y_{i})\\}$

and

$\displaystyle\forall(s,a)\in({\mathcal{S}}\times\mathcal{A})_{b};l^{*}(s,a)\geq
0.$

Finally, by using the adjoint property (15),

$\displaystyle L_{0}(q,l^{\star})-L_{0}(q^{\star},l^{\star})$
$\displaystyle\geq 0.5\mathbb{E}_{(s,a)\sim
P_{b}}[q^{2}(s,a)-q^{\star}(s,a)^{2}]-\mathbb{E}_{(s,a)\sim
P_{b}}[q^{\star}(s,a)\\{q(s,a)-q^{\star}(s,a)\\}]$
$\displaystyle=0.5\mathbb{E}_{(s,a)\sim
P_{b}}[\\{q(s,a)-q^{\star}(s,a)\\}^{2}].$

#### Part 3: Showing the final bound.

We use the following decomposition:

$\displaystyle L_{0}(\hat{q}_{0},l^{\star})$
$\displaystyle=\underbrace{-L(q^{\star},l^{\star})+L_{0}(q^{\star},\hat{l}(q^{\star}))}_{(a)}\underbrace{-L_{0}(q^{\star},\hat{l}(q^{\star}))+\hat{L}_{0}(q^{\star},\hat{l}(q^{\star}))}_{(b)}$
$\displaystyle\underbrace{-\hat{L}_{0}(q^{\star},\hat{l}(q^{\star}))+\hat{L}_{0}(\hat{q}_{0},\hat{l})}_{(c)}\underbrace{-\hat{L}_{0}(\hat{q}_{0},\hat{l})+\hat{L}_{0}(\hat{q}_{0},l^{\star})}_{(d)}\underbrace{-\hat{L}_{0}(\hat{q}_{0},l^{\star})+L_{0}(\hat{q}_{0},l^{\star})}_{(e)}.$

Here, (a) is equal to $0$ since $q^{\star}$ satisfies the Bellman equation.
Besides, using Hoeffding’s inequality, with probability $1-\delta$, terms (b)
and (e) are less than

$c\left(\mathcal{B}^{2}_{\mathcal{Q}}+\mathcal{B}_{\mathcal{L}}\mathcal{B}_{\mathcal{Q}}\right)\sqrt{\frac{\ln(|\mathcal{Q}||\mathcal{L}|/\delta)}{n}}.$

Terms (c) and (d) are greater than $0$ using the construction of estimators.
This implies

$\displaystyle 0.5\mathbb{E}_{(s,a)\sim
P_{b}}[\\{\hat{q}_{0}(s,a)-q^{\star}(s,a)\\}^{2}]$ $\displaystyle\leq
L_{0}(\hat{q}_{0},l^{\star})-L_{0}(q^{\star},l^{\star})$ (Second step.)
$\displaystyle\leq
c\left(\mathcal{B}^{2}_{\mathcal{Q}}+\mathcal{B}_{\mathcal{L}}\mathcal{B}_{\mathcal{Q}}\right)\sqrt{\frac{\ln(|\mathcal{Q}||\mathcal{L}|/\delta)}{n}}.$

##  Appendix D Proof in Section 5

###  D.1 Proof of Theorem 3

Using Theorem 1, with probability $1-\delta$, the following holds

$\displaystyle\mathbb{E}_{(s,a)\sim
P_{b}}[\\{\hat{q}_{\alpha}(s,a)-q^{\star}_{\alpha}(s,a)\\}^{2}]\lesssim\mathrm{Error},$
(16)
$\displaystyle\mathrm{Error}=\left(\mathcal{B}^{2}_{\mathcal{Q}}+\mathcal{B}_{\mathcal{Q}}\mathcal{B}_{\mathcal{L}}+\mathcal{B}_{\mathcal{L}}\gamma\\{\alpha+\alpha\ln(|\mathcal{A}|)\\}\right)\sqrt{\frac{\ln(|\mathcal{Q}||\mathcal{L}|/\delta)}{n}}.$

Hereafter, we condition on this event. Then, letting $\hat{\pi}_{\alpha}(a\mid
s)=\mathrm{softmax}(\hat{q}_{\alpha}/\alpha+\log\pi_{b})$, we have

$\displaystyle J(\pi^{\star}_{\alpha})-J(\hat{\pi}_{\alpha})$
$\displaystyle\leq(1-\gamma)^{-1}R_{\max}\mathbb{E}_{s\sim
d_{\pi^{\star}_{\alpha}}}[\sum_{a}|\pi^{\star}_{\alpha}(a\mid
s)-\hat{\pi}_{\alpha}(a\mid s)|]$ (Performance difference lemma in Lemma 6)
$\displaystyle\leq(1-\gamma)^{-1}R_{\max}\mathbb{E}_{s\sim
d_{\pi^{\star}_{\alpha}}}\left[\sqrt{|\mathcal{A}|}\left(\sum_{a}\\{\pi^{\star}_{\alpha}(a\mid
s)-\hat{\pi}_{\alpha}(a\mid s)\\}^{2}\right)^{1/2}\right]$ (CS inequality)
$\displaystyle=(1-\gamma)^{-1}R_{\max}\mathbb{E}_{s\sim
d_{\pi^{\star}_{\alpha}}}\left[\sqrt{|\mathcal{A}|}\left(\sum_{a:\pi_{b}(a\mid
s)>0}\\{\pi^{\star}_{\alpha}(a\mid s)-\hat{\pi}_{\alpha}(a\mid
s)\\}^{2}\right)^{1/2}\right].$

From the second line to the third line, we use a relation that
$\pi^{\star}_{\alpha},\hat{\pi}_{\alpha}$, and $\pi_{b}$ have the same
support.

Now, we want to connect this bound with $L^{2}$-error of Q-functions. This is
possible since the softmax function with Lipschitz constant $1/\alpha$ is
Lipschitz continuous with constant $1/\alpha$ in Gao and Pavel (2017,
Proposition 4). Hence, the right hand side is upper-bounded by

$\displaystyle(1-\gamma)^{-1}\sqrt{|\mathcal{A}|}/\alpha
R_{\max}\mathbb{E}_{s\sim
d_{\pi^{\star}_{\alpha}}}\left[\left\\{\sum_{a:\pi_{b}(a\mid
s)>0}\\{\hat{q}_{\alpha}(s,a)-q^{\star}_{\alpha}(s,a)\\}^{2}\right\\}^{1/2}\right].$

From Jensen’s inequality, this is further upper-bounded by

$\displaystyle(1-\gamma)^{-1}\sqrt{|\mathcal{A}|}/\alpha
R_{\max}\mathbb{E}_{s\sim d_{\pi^{\star}_{\alpha}}}\left[\sum_{a:\pi_{b}(a\mid
s)>0}\\{\hat{q}_{\alpha}(s,a)-q^{\star}_{\alpha}(s,a)\\}^{2}\right]^{1/2}.$

Then, using the definition of $\pi^{\diamond}_{b}$, this is upper-bounded by

$\displaystyle(1-\gamma)^{-1}|\mathcal{A}|/\alpha R_{\max}\mathbb{E}_{s\sim
d_{\pi^{\star}_{\alpha}},a\sim\pi^{\diamond}_{b}(\cdot\mid
s)}\left[\\{\hat{q}_{\alpha}(s,a)-q^{\star}_{\alpha}(s,a)\\}^{2}\right]^{1/2}$

Finally, by combining this result with (16), we get the final guarantee.

###  D.2 Proof of Theorem 4

We have

$\displaystyle
J(\pi)-J_{\alpha}(\pi)=R_{\max}\alpha(1-\gamma)^{-1}\mathbb{E}_{s\sim
d_{\pi},a\sim\pi(s)}[\log\pi(a\mid s)/\pi_{b}(a\mid s)]\geq 0$ (17)

for any $\pi$. Then,

$\displaystyle J(\pi^{\star})-J(\pi^{\star}_{\alpha})$
$\displaystyle=J(\pi^{\star})-J_{\alpha}(\pi^{\star})+\underbrace{J_{\alpha}(\pi^{\star})-J_{\alpha}(\pi^{\star}_{\alpha})}_{(a)}+\underbrace{J_{\alpha}(\pi^{\star}_{\alpha})-J(\pi^{\star}_{\alpha})}_{(b)}$
$\displaystyle\leq J(\pi^{\star})-J_{\alpha}(\pi^{\star}).$

Note the term (a) is less than $0$ since $\pi^{\star}_{\alpha}$ is the optimal
softmax policy and the term (b) is less than $0$ using (17). Furthermore,

$\displaystyle J(\pi^{\star})-J_{\alpha}(\pi^{\star})=(1-\gamma)^{-1}\alpha
R_{\max}\mathbb{E}_{s\sim
d_{\pi^{\star}},a\sim\pi^{\star}(s)}[\log\pi^{\star}(a\mid s)/\pi_{b}(a\mid
s)]$ $\displaystyle\leq(1-\gamma)^{-1}\alpha R_{\max}\log C_{0}.$

Therefore, by combining with Theorem 3, we have

$\displaystyle J(\pi^{\star})-J(\hat{\pi}_{\alpha})$ $\displaystyle\leq
cR_{\max}\frac{|\mathcal{A}|C^{1/2}_{\mathcal{Q},d_{\pi^{\star}_{\alpha},\mu_{0}}}\\{\mathcal{B}_{\mathcal{Q}}+\gamma\mathcal{B}_{\mathcal{L}}\\{\mathcal{B}_{\mathcal{Q}}\alpha+\ln(|\mathcal{A}|)\\}\\}^{1/2}\\{\ln(|\mathcal{Q}||\mathcal{L}|/\delta)\\}^{1/4}}{(1-\gamma)\alpha
n^{1/4}}$ $\displaystyle+c\frac{R_{\max}\alpha\log C_{0}}{1-\gamma}.$

The sample complexity is easily obtained from this result.

##  Appendix E  Proof in Section 6

From Section D, with probability $1-\delta$, the following holds

$\displaystyle\mathbb{E}_{(s,a)\sim
P_{b}}[\\{\hat{q}(s,a)-q^{\star}(s,a)\\}^{2}]\lesssim\mathrm{Error},$ (18)
$\displaystyle\mathrm{Error}=\left(\mathcal{B}^{2}_{\mathcal{Q}}+\gamma\mathcal{B}_{\mathcal{L}}\mathcal{B}_{\mathcal{Q}}\right)\sqrt{\frac{\ln(|\mathcal{Q}||\mathcal{L}|/\delta)}{n}}.$

Hereafter, we condition on this event. Then, letting

$\hat{\pi}(a\mid s)=\operatorname*{arg\,max}_{a\in\mathcal{A}:\pi_{b}(a\mid
s)>0}\hat{q}(s,a),$

we have

$\displaystyle(1-\gamma)^{2}R_{\max}^{-1}\\{J(\pi^{\star})-J(\hat{\pi})\\}$
$\displaystyle\leq\mathbb{E}_{s\sim
d_{\pi^{\star}}}[\mathrm{I}(\pi^{\star}(s)\neq\hat{\pi}(s))]$ (Performance
difference lemma in Lemma 6) $\displaystyle\leq\mathbb{E}_{s\sim
d_{\pi^{\star}}}\left[\sum_{a^{\prime}:a^{\prime}\sim\pi_{b}(a\mid
s)>0}\mathrm{I}(\hat{q}(s,a^{\prime})-\hat{q}(s,\pi^{\star}(s))\geq
0\,\&\,q^{\star}(s,a^{\prime})-q^{\star}(s,\pi^{\star}(s))<0)\right].$

Hence, we have

$\displaystyle\mathbb{E}_{s\sim
d_{\pi^{\star}}}\left[\sum_{a^{\prime}:a^{\prime}\sim\pi_{b}(a\mid
s)>0}\mathrm{I}(\hat{q}(s,a^{\prime})-\hat{q}(s,\pi^{\star}(s))\geq
0\,\&\,q^{\star}(s,a^{\prime})-q^{\star}(s,\pi^{\star}(s))<0)\right]$
$\displaystyle\leq\mathbb{E}_{s\sim
d_{\pi^{\star}}}\left[\sum_{a^{\prime}:a^{\prime}\sim\pi_{b}(a\mid
s)>0}\mathrm{I}(0>q^{\star}(s,a^{\prime})-q^{\star}(s,\pi^{\star}(s))\geq-t)\right]+$
$\displaystyle+\mathbb{E}_{s\sim
d_{\pi^{\star}}}\left[\sum_{a^{\prime}:a^{\prime}\sim\pi_{b}(a\mid
s)>0}\mathrm{I}(\hat{q}(s,a^{\prime})-\hat{q}(s,\pi^{\star}(s))-q^{\star}(s,a^{\prime})+q^{\star}(s,\pi^{\star}(s))\geq
t)\right]$

In the first term, we can use a margin assumption:

$\displaystyle\mathbb{E}_{s\sim
d_{\pi^{\star}}}\left[\sum_{a^{\prime}:a^{\prime}\sim\pi_{b}(a\mid
s)>0}\mathrm{I}(0>q^{\star}(s,a^{\prime})-q^{\star}(s,\pi^{\star}(s))\geq-t)\right]\leq
c|\mathcal{A}|(t/t_{0})^{\beta}.$

In the second term, we can use

$\displaystyle\mathbb{E}_{s\sim
d_{\pi^{\star}}}\left[\sum_{a^{\prime}:a^{\prime}\sim\pi_{b}(a\mid
s)>0}t^{2}\mathrm{I}(\hat{q}(s,a^{\prime})-\hat{q}(s,\pi^{\star}(s))-q^{\star}(s,a^{\prime})+q^{\star}(s,\pi^{\star}(s))\geq
t)\right]$ $\displaystyle\leq\mathbb{E}_{s\sim
d_{\pi^{\star}}}\left[\sum_{a^{\prime}:a^{\prime}\sim\pi_{b}(a\mid
s)>0}|\hat{q}(s,a^{\prime})-\hat{q}(s,\pi^{\star}(s))-q^{\star}(s,a^{\prime})+q^{\star}(s,\pi^{\star}(s))|^{2}\right]$
$\displaystyle\leq 2\mathbb{E}_{s\sim
d_{\pi^{\star}}}\left[\sum_{a^{\prime}:a^{\prime}\sim\pi_{b}(a\mid
s)>0}|\hat{q}(s,a^{\prime})-q^{\star}(s,a^{\prime})|^{2}_{2}+|\hat{q}(s,\pi^{\star}(s))-q^{\star}(s,\pi^{\star}(s))|^{2}\right]$
$\displaystyle\leq 2|\mathcal{A}|\mathbb{E}_{s\sim
d_{\pi^{\star}},a\sim\pi^{\diamond}_{b}(s)}[|\hat{q}(s,a^{\prime})-q^{\star}(s,a^{\prime})|^{2}]+2|\mathcal{A}|\mathbb{E}_{s\sim
d_{\pi^{\star}},a\sim\pi^{\star}(s)}[|\hat{q}(s,a)-q^{\star}(s,a)|^{2}].$

Therefore,

$\displaystyle(1-\gamma)^{2}R_{\max}^{-1}\\{J(\pi^{\star})-J(\hat{\pi})\\}$
$\displaystyle\leq
c_{2}\\{|\mathcal{A}|(t/t_{0})^{\beta}+t^{-2}\\{2|\mathcal{A}|\mathbb{E}_{s\sim
d_{\pi^{\star}},a\sim\pi^{\diamond}_{b}(s)}[|\hat{q}(s,a^{\prime})-q^{\star}(s,a^{\prime})|^{2}]$
$\displaystyle+2|\mathcal{A}|\mathbb{E}_{s\sim
d_{\pi^{\star}},a\sim\pi^{\star}(s)}[|\hat{q}(s,a)-q^{\star}(s,a)|^{2}]\\}\\}$
$\displaystyle\leq
c_{3}\\{|\mathcal{A}|t^{-2\beta/(2+\beta)}_{0}\\{\mathbb{E}_{s\sim
d_{\pi^{\star}},a\sim\pi^{\diamond}_{b}(s)}[|\hat{q}(s,a^{\prime})-q^{\star}(s,a^{\prime})|^{2}]^{\beta/(2+\beta)}$
$\displaystyle+\mathbb{E}_{s\sim
d_{\pi^{\star}},a\sim\pi^{\star}(s)}[|\hat{q}(s,a)-q^{\star}(s,a)|^{2}]^{\beta/(2+\beta)}\\}\\}.$

Hence,

$\displaystyle(1-\gamma)^{2}R_{\max}^{-1}\\{J(\pi^{\star})-J(\hat{\pi})\\}\leq
c|\mathcal{A}|t^{-2\beta/(2+\beta)}_{0}\left(C_{\mathcal{Q},d_{\pi^{\star}_{0},\mu_{0}}}C_{0}\left(\mathcal{B}^{2}_{\mathcal{Q}}+\gamma\mathcal{B}_{\mathcal{L}}\mathcal{B}_{\mathcal{Q}}\right)\\{\ln(|\mathcal{Q}||\mathcal{L}/\delta)/n\\}^{1/2}\right)^{\beta/(2+\beta)}.$

This concludes the statement by some algebra.

##  Appendix F Auxiliary Lemmas

We prove two auxiliary lemmas used in the proof.

######  Lemma 6 (Performance Difference Lemma ).

$\displaystyle J(\pi)-J(\pi^{\prime})$
$\displaystyle=(1-\gamma)^{-1}\mathbb{E}_{s\sim d_{\pi}}[\langle\pi(\cdot\mid
s)-\pi^{\prime}(\cdot\mid s),Q^{\pi^{\prime}}(s,\cdot)\rangle]$
$\displaystyle\leq(1-\gamma)^{-2}R_{\max}\mathbb{E}_{s\sim
d_{\pi}}[\|\pi(\cdot\mid s)-\pi^{\prime}(\cdot\mid s)\|_{1}].$

######  Lemma 7 (LogSumExp Inequality).

$\displaystyle\max\\{x_{1},\cdots,x_{|\mathcal{A}|}\\}\leq\log(\sum_{i=1}^{|\mathcal{A}|}\exp(x_{i}))\leq\max\\{x_{1},\cdots,x_{|\mathcal{A}|}\\}+\ln(|\mathcal{A}|).$