# Leveraging Prior Knowledge in Reinforcement Learning via
Double-Sided Bounds on the Value Function

Jacob Adamczyk1, Stas Tiomkin2, Rahul V. Kulkarni1

###### Abstract

An agent’s ability to leverage past experience is critical for efficiently
solving new tasks. Approximate solutions for new tasks can be obtained from
previously derived value functions, as demonstrated by research on transfer
learning, curriculum learning, and compositionality. However, prior work has
primarily focused on using value functions to obtain zero-shot approximations
for solutions to a new task. In this work, we show how an arbitrary
approximation for the value function can be used to derive double-sided bounds
on the optimal value function of interest. We further extend the framework
with error analysis for continuous state and action spaces. The derived
results lead to new approaches for clipping during training which we validate
numerically in simple domains.

## Introduction

The field of reinforcement learning (RL) has seen impressive successes
(Degrave et al. 2022; Schrittwieser et al. 2020; Vinyals et al. 2019; Silver
et al. 2018) in recent years due to the development of novel algorithms in
combination with deep learning architectures. However, for complex tasks, the
amount of training time required for learning an optimal solution from scratch
can be prohibitively large and thus presents a significant obstacle to further
development. To address this challenge, approaches that leverage prior
knowledge to efficiently calculate policies for new tasks are needed. While
policies generated from prior solutions may not be the optimal policies for
the new tasks, they can serve as useful approximations that reduce training
time. Correspondingly, there is a need to develop approaches that further
leverage the use of approximations based on prior knowledge to address the
problem of solving new tasks.

Previous work has focused on addressing this problem using different
approaches such as transfer learning, curriculum learning, and
compositionality. In particular, we consider value-based RL approaches,
wherein the agent’s goal is to learn the expected value of every state and
action pair. Given this value function, $Q(s,a)$, the agent can act optimally
by choosing actions which maximize its expected future returns. In many
instances, the agent has an estimate for the value function before training
begins. For example, in the case of curriculum learning, the agent has the
$Q$-values for previously learned (progressively more challenging) tasks. In
the case of compositional or hierarchical RL, the agent can combine knowledge
by applying a function on subtasks’ $Q$-values. When using an exploratory
skill-acquisition approach such as DIAYN (Eysenbach et al. 2019) or CSD (Park
et al. 2023), the agent obtains $Q$-values for a diverse set of skills. Even
in cases where an initial estimate is not explicitly provided, the agent can
provide itself an estimate by using Q-values that were obtained during the
ongoing learning phase (bootstrapping).

An underlying question in these scenarios is the following: How can the agent
use the known value function estimate(s) for solving a new target task? Does
the estimate only serve as a zero-shot approximation or is there additional
useful information that can be extracted from it?

In the work of (Adamczyk et al. 2023a), the authors show that there exists a
method of “closing the gap” between any estimate ($Q^{*}(s,a)$) and any target
($\widetilde{Q}^{*}(s,a)$) task (with an accessible reward function) in
entropy-regularized RL. This statement is facilitated by the work of (Cao,
Cohen, and Szpruch 2021) which can be used to show that any estimate can be
viewed as an optimal value function corresponding to a suitably defined reward
function. Here, we show that since the gap between the target and estimated
value functions: $\widetilde{Q}^{*}(s,a)-Q^{*}(s,a)=K^{*}(s,a)$ is itself an
optimal value function, it can be bounded. As a consequence, instead of
providing only a zero-shot approximation or a warmstart for training the
target task, we show that the estimates available to the agent also provide a
double-sided bound on the optimal $Q$-values being learned.

A schematic illustration of our approach is provided in Fig. 1. Starting with
an estimate of the optimal value function and samples of the reward function,
we derive double-sided bounds on the true optimal value function. We find that
applying these bounds during training improves the agent’s training
performance and allows an additional method for monitoring convergence. We
provide further theoretical analysis on continuous state-action spaces,
relevant for the function approximator (FA) setting in Deep RL.

Main contributions
The main contributions of our work, applicable to both standard and entropy-
regularized RL, are:

  1. 1.

Development of a general framework for bounding optimal value functions based
on prior knowledge.

  2. 2.

Extension of derived results to include theoretical error analysis in
continuous state-action spaces.

  3. 3.

Demonstration of value-based clipping methods as practical applications of the
derived theoretical results.

Figure 1: Schematic illustration of the main contribution of this work. Given
any approximation (red curve) to the optimal value function of interest (black
curve), we derive double-sided bounds (blue curves) that lead to clipping
approaches during training. Based solely on the current approximation for
$Q(s,a)$ (red curve), we derive double-sided bounds on the unknown optimal
value function $Q^{*}(s,a)$ (black curve). In the right panel, we show the
different clipping methods, which are described further in the “Experimental
Validation” section. In “Hard Clipping”, the target is replaced with the
exceeded bound; in “Soft Clipping”, an additional loss term is appended to the
Bellman loss, proportional to the magnitude of the bound violation; in
“Smoothed Clipping”, the target update is replaced with a weighted average of
the original value and the exceeded bound.

There are multiple applications that arise from the derivation of such double-
sided bounds. The bounds (1) allow confinement of FA training to a limited
output range, (2) provide a mechanism to choose the “best” skill from a pre-
trained set of skills and (3) establish a framework that provides insights
into and extends previous results on exact compositions of value functions.

## Preliminaries

For the theoretical setup, we consider initially the case of finite, discrete
state and action spaces, and we will subsequently extend our analysis to
continuous spaces. In this setting, the reinforcement learning (RL) problem is
modeled by a Markov Decision Process (MDP) represented as a tuple
$\langle\mathcal{S},\mathcal{A},p,r,\gamma\rangle$ where $\mathcal{S}$ is the
set of available states; $\mathcal{A}$ is the set of possible actions;
$p:\mathcal{S}\times\mathcal{A}\to\mathcal{S}$ is the transition function
(dynamics); $r:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$ is a (bounded)
reward function which associates a reward (or cost) with each state-action
pair; and $\gamma\in(0,1)$ is a discount factor which discounts future rewards
and assures convergence of the total reward for an infinitely long trajectory.

The objective in standard (un-regularized) RL is to find an optimal policy
that maximizes expected rewards collected by the agent, i.e.

$\pi^{*}=\arg\max_{\pi}\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})\right].$
(1)

An important generalization is entropy-regularized RL (Ziebart 2010), which
augments the un-regularized RL objective (Eq. (1)) by including an entropic
regularization term which penalizes control over a pre-specified reference
policy:

$\pi^{*}=\arg\max_{\pi}\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}\left(r_{t}-\frac{1}{\beta}\log\left(\frac{\pi(a_{t}|s_{t})}{\pi_{0}(a_{t}|s_{t})}\right)\right)\right]$

where $\pi_{0}(a|s)$ is the fixed prior policy. The additional control cost
discourages the agent from choosing policies that deviate too much from this
prior policy. Importantly, entropy-regularized MDPs lead to stochastic optimal
policies that are provably robust to perturbations of rewards and dynamics
(Eysenbach and Levine 2022); making them a more suitable approach to real-
world problems.

The solution to the RL problem is defined by its optimal action-value function
($Q^{*}(s,a)$) from which one can derive the aforementioned optimal policy
$\pi^{*}(a|s)$. For both un-regularized and entropy-regularized RL, the
optimal value function can be obtained by iterating a recursive Bellman
equation. In un-regularized RL, the Bellman optimality equation is given by
(Sutton and Barto 2018):

$Q^{*}(s,a)=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim{}p(\cdot|s,a)}\max_{a^{\prime}}\left(Q^{*}(s^{\prime},a^{\prime})\right).$
(2)

The entropy term in the objective function of entropy-regularized RL modifies
the previous optimality equation in the following way (Ziebart 2010; Haarnoja
et al. 2018b):

$Q^{*}(s,a)=r(s,a)+\frac{\gamma}{\beta}\mathbb{E}_{s^{\prime}\sim{}p}\log\mathbb{E}_{a^{\prime}\sim{}\pi_{0}}e^{\beta
Q^{*}(s^{\prime},a^{\prime})}.$ (3)

The regularization parameter $\beta$ can be interpreted as being analogous to
an inverse temperature parameter, its value is used to control the degree of
stochasticity in the optimal policy. In the entropy-regularized setting,
$Q^{*}$ is referred to as the optimal “soft” action-value function. For
brevity, we will hereon refer to $Q^{*}$ simply as the value function.

## Prior Work

The importance of double-sided bounds on value functions has been explored in
prior work. In this section we review a set of the most relevant prior works
(Nemecek and Parr 2021; Kim, Park, and Kim 2022; Haarnoja et al. 2018a;
Adamczyk et al. 2023b; Todorov 2009; Van Niekerk et al. 2019; Tasse, James,
and Rosman 2020; Lee et al. 2021). We contrast the existing works with regard
to the following features: i) the assumption about composition and/or
transformation of known solutions in the derivation of bounds, ii) the
requirement for additional samples needed to derive bounds, iii) the
generality and applicability of bounds to un-regularized RL and entropy-
regularized RL, and to deterministic and stochastic dynamics, iv) double or
single-sided bounds.

In (Nemecek and Parr 2021), the authors have derived double-sided bounds on
the state value function $V(s)$ by the positive conical combination of subtask
rewards. The method in (Nemecek and Parr 2021) requires additional samples for
first learning the successor features before then deriving the double-sided
bounds for a downstream task. The applicability of (Nemecek and Parr 2021) is
limited to un-regularized RL.

The aforementioned work was subsequently extended by (Kim, Park, and Kim
2022), where, in the same GPI setting, they present double-sided bounds on
$Q$-values for linear combinations of subtask reward functions. They introduce
the notion of “soft clipping” which we adapt to our setting (details in the
“Experimental Validation” section), but it was not demonstrated in practice.
Similarly to (Nemecek and Parr 2021), the method in (Kim, Park, and Kim 2022)
requires firstly to learn the successor features, and it is limited to un-
regularized RL only.

The previous two works were focused on the standard (un-regularized)
reinforcement learning setting. However, the double-sided bounds presented in
(Haarnoja et al. 2018a)’s Lemma 1 are derived for the MaxEnt setting, for the
case of convex reward combinations. It is worth noting that the lower bound in
this case must be learned (the $C$ function). Extending these results to other
more general classes of functional composition, (Adamczyk et al. 2023b)
provides double-sided bounds for both entropy-regularized and un-regularized
RL. However, one side of the bound in all cases must be learned as well.

Finally, multiple prior works have focused on specific examples of
compositionality for which exact results can be obtained for the optimal value
function. These results typically involve multiple limiting assumptions on the
structure of rewards functions, nature of transition dynamics and specific
forms for the composition function. (Todorov 2009; Van Niekerk et al. 2019;
Tasse, James, and Rosman 2020). In a broader context, (Lee et al. 2021)
proposes to bound “Bellman updates”, which improves the stability of training
and sample efficiency in entropy-regularized RL. However, the method in (Lee
et al. 2021) does not leverage known solutions for new tasks, instead using a
parallel ensemble of learners for variance estimation.

In the current work we propose a novel method for the derivation of double-
sided bounds, which is not limited to a particular type of composition or
transformation of prior solution(s), and is valid for an arbitrary function.
Our method is a “zero-shot” approach for deriving double-sided bounds – it
does not require additional samples beyond those collected by the learning
agent. It is applicable to both standard and entropy-regularized RL, to
deterministic and stochastic environments, and to discrete and continuous
domains. The theoretical results are provided in the following “Results”
section, and in the “Applications” section we demonstrate the applications of
the theory in simple domains, leaving large scale experiments to future work.

## Results

In this section, we focus on entropy-regularized (MaxEnt) RL, the case
considered in (Adamczyk et al. 2023a). The analogous results for un-
regularized RL (which can be considered as a limiting case of entropy-
regularized RL) are provided later. The proofs of all results shown can be
found in the Appendix.

Our main result provides double-sided bounds on the optimal $Q$ function. We
emphasize that any (bounded) function
$Q:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$ can be used to generate a bound.
We suggestively use the notation “$Q$” for this otherwise arbitrary function
to note that it can be derived from a previous tasks’ solution, an estimate,
or other ansatz (e.g. composition or hierarchical function) of subtask
$Q$-values.

######  Theorem 4.1.

Consider an entropy-regularized MDP
$\langle\mathcal{S},\mathcal{A},p,r,\gamma,\beta\rangle$ with (unknown)
optimal value function $Q^{*}(s,a)$. Let an estimate for the value function
$Q(s,a)$ be given. Denote
$V(s)~{}\doteq~{}1/\beta\log\operatorname*{\mathbb{E}}_{a\sim\pi_{0}}\exp\beta
Q(s,a)$.

The optimal value function $Q^{*}(s,a)$ is then bounded by:

$\displaystyle Q^{*}(s,a)$ $\displaystyle\geq
r(s,a)+\gamma\left(\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}V(s^{\prime})+\frac{\inf\Delta}{1-\gamma}\right)$
(4a) $\displaystyle Q^{*}(s,a)$ $\displaystyle\leq
r(s,a)+\gamma\left(\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}V(s^{\prime})+\frac{\sup\Delta}{1-\gamma}\right)$
(4b)

where

$\Delta(s,a)\doteq
r(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}V(s^{\prime})-Q(s,a).$

In Eq. (4a) and (4b), the $\inf$ and $\sup$ are taken over the continuous
state-action space $\mathcal{S}\times\mathcal{A}$.

During training, the Bellman loss $\mathcal{L}=||\Delta||^{2}\to 0$, implying
that $\inf\Delta\to 0$ and $\sup\Delta\to 0$, hence the bounds in Eq. (4.1)
will become tight upon convergence of the soft action-value function. We note
that this is generally not the case for un-regularized RL, as will be
discussed later.

In principle, given some assumptions on the structure of the reward function
or dynamics, it is possible to tighten these bounds. As an example, we provide
a tighter lower bound when the MDP always has an “identity” action allowing
the agent to return to the same state:

######  Lemma 4.1a.

Consider an entropy-regularized MDP
$\langle\mathcal{S},\mathcal{A},p,r,\gamma,\beta\rangle$ with (unknown)
optimal value function $Q^{*}(s,a)$. Let an estimate for the value function
$Q(s,a)$ be given. Denote
$V(s)~{}\doteq~{}1/\beta\log\operatorname*{\mathbb{E}}_{a\sim\pi_{0}}\exp\beta
Q(s,a)$. Suppose there exists an “identity” action
$a_{\emptyset}(s)\in\mathcal{A}$ for each state, which deterministically
transitions the agent to the same state:
$p(s^{\prime}|s,a_{\emptyset}(s))=\delta(s^{\prime}-s)$ for all
$s\in\mathcal{S}$.

Then the lower bound on the optimal value function $Q^{*}(s,a)$ can be
improved:

$Q^{*}(s,a)\geq
r(s,a)+\gamma\left(V(s^{\prime})+\frac{1}{1-\gamma}\Delta(s^{\prime},a_{\emptyset})\right)$
(5)

In the Appendix, we show that the lower bound of Eq. (5) is indeed tighter
than Eq. (4a) at all state-actions except the minimizer
$(s^{*},a^{*})=\textrm{arginf}\ \Delta(s,a)$.

As an alternative, in practice, one can replace the $\inf$ and $\sup$ in the
previous results by a $\min$ and $\max$, respectively, over the finite dataset
provided (e.g. the current batch of replay data). Although not exact, this
substitution becomes increasingly accurate for large batch sizes. We employ
this substitution in the experiments shown in section Experimental Validation.
Nevertheless, we provide an exact extension of our results in the subsequent
section for sufficiently well-behaved state-action spaces.

In a similar manner, we may also bound the rate of suboptimality induced by
using the policy derived from some estimate $Q(s,a)$:

######  Corollary 4.2 (Suboptimality Bounds).

Let policy $\pi(a|s)$ be given with soft value $Q^{\pi}(s,a)$. The rate of the
suboptimality gap, $Q^{*}(s,a)-Q^{\pi}(s,a)$, is then bounded between

$\inf_{(s,a)}d(s,a)\leq\frac{Q^{*}(s,a)-Q^{\pi}(s,a)}{H}\leq\sup_{(s,a)}d(s,a)$
(6)

where $d(s,a)\doteq
r(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}}V^{\pi}(s^{\prime})-Q^{\pi}(s,a)$,
$V^{\pi}(s)\doteq\log\operatorname*{\mathbb{E}}_{a}\exp\beta Q^{\pi}(s,a)$ is
the soft state-value function, and $H=(1-\gamma)^{-1}$ is the effective time
horizon.

This result implies that any policy with a known soft value function has a
(lower and upper) bounded suboptimality. The typically-stated objective of
minimizing the Bellman loss can be understood as minimizing the suboptimality
suffered by the induced policy $\pi\propto\exp\beta Q$.

We conclude this section by showing that a new Bellman operator, which
includes clipping when applicable, converges to the optimal $Q$ function:

######  Theorem 4.3.

Let the functions $L(s,a),U(s,a)$ be lower and upper bounds on the optimal
value function: $L(s,a)~{}\leq~{}Q^{*}(s,a)~{}\leq U(s,a)$ for all
$s\in\mathcal{S}$ and $a\in\mathcal{A}$. The clipped Bellman operator,
$\mathcal{B}_{C}Q(s,a)~{}:=~{}\max_{s,a}\left(\min_{s,a}\left(\mathcal{B}Q(s,a),U(s,a)\right),L(s,a)\right)$
converges to the optimal value function
$Q^{*}(s,a)~{}=~{}\mathcal{B}^{\infty}Q(s,a)$.

This result shows that updates with clipping are guaranteed to converge to the
same solution. We experimentally demonstrate this in Fig. 3.

### Error Propagation in Continuous Spaces

The bounds presented in the previous section, though exact, are often
intractable due to the required global extremization over continuous state-
action spaces. One cannot access the global extrema of $\Delta$ given only
finitely many samples in state-action space. Thus, we provide the following
bounds, allowing for the extension of our results to (sufficiently well-
behaved) continuous spaces. In this section, we loosen those bounds by
relaxing the required extremization with a simpler optimization over a given
discrete batch of replay data.

We begin with some helpful definitions.

######  Definition 1.

A function $\bar{X}:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$ is an
$\varepsilon$-optimal approximation of
$X(s,a):\mathcal{S}\times\mathcal{A}\to\mathbb{R}$ if it satisfies
$\left\lvert\bar{X}(s,a)-X(s,a)\right\rvert\leq\varepsilon$ for all
$s\in\mathcal{S},a\in\mathcal{A}$.

######  Definition 2.

The diameter of a bounded metric space, $\mathcal{X}$, endowed with a metric
$d(\cdot,\cdot)\to\mathbb{R}_{\geq 0}$ is a constant $D\in\mathbb{R}_{>0}$
such that $d(x_{1},x_{2})\leq D$ for all $x_{1},x_{2}\in\mathcal{X}$.

######  Lemma 4.4.

Let $\mathcal{S}\times\mathcal{A}$ be a bounded metric space with diameter
$D$, and let $r:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$ be
$L_{r}$-Lipschitz (w.r.t. the same metric). Then the global extrema of
$r(s,a)$ on $\mathcal{S}\times\mathcal{A}$ are bounded as follows:

$\displaystyle\sup_{s\in\mathcal{S},a\in\mathcal{A}}r(s,a)$
$\displaystyle\leq\min_{(s,a)\in\mathcal{D}}r(s,a)+L_{r}D$
$\displaystyle\inf_{s\in\mathcal{S},a\in\mathcal{A}}r(s,a)$
$\displaystyle\geq\max_{(s,a)\in\mathcal{D}}r(s,a)-L_{r}D$

where $\mathcal{D}$ is the dataset of $(s,a)$ tuples available for querying
the magnitude of $r$ (e.g. the current batch or buffer).

As an example, in the case that one uses the simple upper bound,
$Q(s,a)\leq\frac{1}{1-\gamma}\sup r(s,a)$, over a finite-sized batch of replay
experience $\\{s_{i},a_{i},r_{i},s_{i+1}\\}_{i=1}^{T}$, one can bound the
(intractable) $\sup$ which is taken over all state-action space: $\sup
r(s,a)\leq\min_{i}r_{i}+L_{r}||(D_{\mathcal{S}},D_{\mathcal{A}})||_{p}$.

In the case of continuous spaces, we cannot calculate the state-value function
directly, so one typically resorts to actor-critic methods (Haarnoja et al.
2018b) where a policy network $\pi$ and value network $Q$ are trained
together. In this case, one must calculate the entropy-regularized state-value
function as
$V^{\pi}(s)=\operatorname*{\mathbb{E}}_{a\sim{}\pi}\left[Q^{\pi}(s,a)-\beta^{-1}\log\pi(a|s)\right]$.
However, the expectation over continuously many actions is intractable in the
general case. The solution to this is parameterizing the policy network by a
simple, but expressive distribution at each state, for instance a Gaussian
actor $\mathcal{N}(\mu(s),\sigma(s))$. With knowledge of the means and
variances, the sampling error can be bounded as we show below.

######  Theorem 4.5.

Let an entropy-regularized MDP be given with an $L_{Q}$-Lipschitz value
function $\bar{Q}^{\pi}$. Using a Gaussian parameterization for the associated
policy $\pi(\cdot|s)=\mathcal{N}(\mu(s),\sigma(s))$, suppose that
$\bar{Q}^{\pi}$ is an $\varepsilon$-optimal approximation of the policy’s true
value, $Q^{\pi}$.

By estimating the state-value function as:

$\bar{V}^{\pi}(s)=\bar{Q}^{\pi}(s,\mu)-\frac{1}{\beta}\operatorname*{\mathbb{E}}_{a\sim{}\pi}\log\frac{\pi(a|s)}{\pi_{0}(a|s)},$
(7)

the error in using such an approximation is upper bounded:

$|\bar{V}^{\pi}(s)-V^{\pi}(s)|\leq\sqrt{\frac{2}{\pi}}L_{Q}\sigma(s)e^{-\mu(s)^{2}/2\sigma(s)^{2}}+\varepsilon$

In the case that the function $Q$ used is an optimal value function for an
$(L_{r},L_{p})$-Lipschitz task, with a policy whose variance is lower bounded
$\sigma(s)\geq\sigma_{\text{min}}$ and $\gamma L_{p}(1+L_{\mathcal{N}})<1$,
where $L_{\mathcal{N}}=\sigma_{\text{min}}^{-2}(2\pi e)^{-1/2}$ is the
Lipschitz constant of the Gaussian distribution, then the Lipschitz constant
for $Q$ can be computed as:

$L_{Q}=\frac{L_{r}+\gamma L_{p}(\beta\sigma_{\min})^{-1}}{1-\gamma
L_{p}(1+L_{\mathcal{N}})}.$ (8)

As the policy becomes deterministic ($\sigma\to 0$), in the un-regularized
limit ($\beta\sigma\to\infty$), the error reduces to zero as expected (since
accurately sampling a deterministic policy only requires one action). Further,
the Lipschitz constant in Eq. (8) matches that of the un-regularized case
(Rachelson and Lagoudakis 2010). Although the expectation in Eq. (7) appears
intractable, the Gaussian parameterization allows it to be calculable, since
the entropy of the policy only depends on its variance. Under the stated
hypotheses, this allows us to translate our bounds in Theorem 4.1 to the
continuous setting. However, satisfying these hypotheses (e.g. the restriction
on $\gamma$) may be challenging in practice. One way of circumventing this is
to consider works such as (Fazlyab et al. 2019), where one can estimate the
Lipschitz constant of the neural net ($Q$-function) being used to generate
bounds.

We note that with the Gaussian policy parameterization, the relative entropy
(second term in Eq. (7)) can be computed exactly from the mean action. In
principle, the analysis may be extended to other policy parameterizations. For
simplicity, the analysis is carried out for single-dimensional action spaces
in the $p=1$ norm, which is easily generalized to other contexts.

These results allow us to derive the following upper and lower bounds in
continuous spaces (an extension of Theorem 4.1), when the $Q$-function used
for deriving $\Delta$ is known to be $L_{Q}$-Lipschitz, or is optimal for an
($L_{r},L_{p}$)-Lipschitz MDP:

######  Theorem 4.6.

Let the $L_{Q}$-Lipschitz value function $Q^{\pi}$ and corresponding Gaussian
policy $\pi(\cdot|s)=\mathcal{N}(\mu(s),\sigma(s))$ be given, where $Q^{\pi}$
is an $\varepsilon$-optimal estimate of the true policy’s value function. For
an $(L_{r},L_{p})$-Lipschitz task with (unknown) optimal value function
$Q^{*}$, let $\bar{V}^{\pi}$ be the one-point estimate of the (known) value
function $Q^{\pi}$, and denote
$\bar{\Delta}(s,a)=r(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}\bar{V}^{\pi}(s^{\prime})-Q^{\pi}(s,a)$.
Then:

$\displaystyle Q^{*}(s,a)\leq
r(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}\left[\bar{V}^{\pi}(s^{\prime})+A(s^{\prime})\right]$
$\displaystyle\hskip
10.00002pt+\frac{\gamma}{1-\gamma}\left(\min_{(s,a)\in\mathcal{D}}\left(\bar{\Delta}(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}A(s^{\prime})\right)+L_{\Delta}D\right)$
$\displaystyle Q^{*}(s,a)\geq
r(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}\left[\bar{V}^{\pi}(s^{\prime})-A(s^{\prime})\right]$
$\displaystyle\hskip
10.00002pt+\frac{\gamma}{1-\gamma}\left(\max_{(s,a)\in\mathcal{D}}\left(\bar{\Delta}(s,a)-\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}A(s^{\prime})\right)-L_{\Delta}D\right)$

where we let
$A(s)=\sqrt{\frac{2}{\pi}}L_{Q}\sigma(s)e^{-\mu(s)/2\sigma(s)^{2}}+\varepsilon$
and $L_{\Delta}=\max\left\\{L_{r},L_{Q},\gamma
L_{p}\left(L_{Q}(1+L_{\mathcal{N}})+(\beta\sigma_{\text{min}})^{-1}\right)\right\\}$
and $D$ denotes the diameter of the state-action space.

### Extension to Un-Regularized RL

Although the previous results have been discussed in the context of entropy-
regularized RL, it is possible to extend them to the un-regularized
($\beta\to\infty$) domain as well with the replacement $\Delta^{\prime}\to
r(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}}V(s^{\prime})-V(s)$. This
can be understood as taking the estimated state-value function $V(s)$ to
generate a potential function for shaping (Ng, Harada, and Russell 1999) the
original reward function $r(s,a)$, with $\Delta^{\prime}$ now representing
this shaped reward. The corresponding value functions are then related by Eq.
(3) in (Ng, Harada, and Russell 1999) which can be seen as the analog of
Theorem 1 in (Adamczyk et al. 2023a) for the un-regularized case. In the
Appendix, we show that replacing $\Delta\to\Delta^{\prime}$ in Theorem 4.1,
leaves Eq. (4a) and (4b) valid for the un-regularized case. In this case, as
the Bellman loss decreases, $\mathcal{L}\to 0$, there is no guarantee that
$\Delta^{\prime}\to 0$ as in the regularized case. Interestingly, we
nevertheless find that in the un-regularized case, the clipping does occur,
and the magnitude of bound violations decreases throughout training. We use
this form (un-regularized RL double-sided clipping) for the FA experiments
shown in the next section.

The preceding extension to un-regularized RL can be generalized to address an
open problem in research on compositionality. Specifically, we can now address
a question posed by (Nemecek and Parr 2021) concerning the possibility of
composing prior solutions in un-regularized RL. We can address this question
by deriving an extension of Theorem 10 in (Adamczyk et al. 2023a) to the case
of un-regularized RL.

######  Theorem 4.8.

Given a set of primitive tasks $\\{\mathcal{T}_{j}\\}$ with corresponding
optimal value functions $\\{Q_{j}^{*}\\}$, denote $\widetilde{Q}^{*}$ as the
optimal value function for the composition of $\\{\mathcal{T}_{j}\\}$ under
the composition function $f:\mathbb{R}^{M}\to\mathbb{R}$.

Define $K^{*}$ as the optimal value function for a task with reward function
$\kappa$ defined by:

$\displaystyle\kappa(s,a)=f(\\{r_{j}(s,a)\\})+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}}V_{f}(s^{\prime})-V_{f}(s)$
$V_{f}(s)=\max_{a}f\left(\\{Q_{j}^{*}(s,a)\\}\right)$

Then, the optimal value functions $\widetilde{Q}^{*}$ and $K^{*}$ are related
by:

$\widetilde{Q}^{*}(s,a)=V_{f}(s)+K^{*}(s,a)$ (9)

Thus, multiple primitive tasks can indeed be composed (via $V_{f}$) and
subsequently corrected (via $K^{*}$) in un-regularized RL.

## Applications

The framework developed in this work has applications on both theoretical and
experimental fronts. In this section, we discuss some applications relating to
compositionality and approaches to clipping.

### Exact Composition in Entropy-Regularized RL

One application of the framework developed is to provide new insights and
extensions of previously derived results for value function compositions, as
seen in Theorem 9. Previous work (Van Niekerk et al. 2019) on entropy-
regularized RL has shown that, for a specific choice of composition function,
an exact expression for the optimal value function of interest can be derived.
This result can be rederived from a different perspective and also extended to
a broader class of compositions using the framework developed. Specifically,
we use the composition of value functions for previously solved tasks as an
estimate for the optimal value function of the composite task. Then, using
this estimate in combination with Theorem 4.1, we derive conditions such that
both of the bounds can be saturated with $\Delta(s,a)=0$, thereby giving an
exact composition.

Using this approach, we are able to extend the results of (Van Niekerk et al.
2019), who find an instance of exact composition in entropy-regularized RL for
tasks with absorbing states. Our derivation (see Appendix) provides new
insight into why specific choices of reward compositions lead to exact
compositions of optimal value functions.

######  Theorem 5.1.

Consider $m$ solved tasks in the entropy-regularized setting, with reward
functions $\\{r_{1},\dotsc,r_{m}\\}$ varying only on the set of absorbing
states. Assume all tasks are given with the same deterministic dynamics. Given
a set of non-negative weights $w_{j}$, consider a new task with the same
reward function for the interior (i.e. non-absorbing) states and with reward
function for the absorbing states given by

$\widetilde{r}(s,a)=\tau\log\sum_{j=1}^{m}w_{j}e^{r_{j}(s,a)/\tau}.$ (10)

Then, the optimal value function for such a task is given by:

$\widetilde{Q}(s,a)=\tau\log\sum_{j=1}^{m}w_{j}e^{Q_{j}(s,a)/\tau}.$ (11)

A detailed derivation of the result is provided in the Appendix; in the
following we note some key points. We consider the setting discussed in (Van
Niekerk et al. 2019) (undiscounted, deterministic dynamics with rewards
varying only on the absorbing states for the solved tasks). By analyzing the
exponentiated version of the backup equation for the solved tasks, we obtain a
general class of reward compositions and value function compositions that
satisfy the same form of backup equation. The extension from previous work is
that the weights no longer need to be normalized to unity.

Figure 2: The discrete maze considered for the tabular experiments. The agent
begins at the green circle, and the yellow star is the only rewarding state.
The action space consists of the cardinal directions, and the state is encoded
by the location on the grid. At each step, the agent receives a small penalty
if it has not reached the goal. $\gamma=0.98$, $\beta=0.1$. On the left plot,
we show the optimal value function $V(s)$ (blue indicates high value). On the
right plot, we show the greedy policy extracted from the optimal action value
function $\text{argmax}_{a}Q(s,a)$. Figure 3: $Q$-values during training with
respect to the derived bounds. The error is the maximum difference between
consecutive Bellman updates. (Note the $\log$-scaled axes.)

### Experimental Validation

In the following experiments, we study the utility of clipping based on our
theoretical results. For simplicity, we highlight the results on a simple
discrete environment. Without any external estimates for the $Q$ function, we
use the estimate given by the previous step’s $Q$-function.

#### Tabular Experiments

In the tabular case, since we have access to the $Q$-table and we perform
exact updates, we simply clip the updated $Q$-table according to the derived
bounds. In Fig. 3 we show the results of training in a simple maze environment
(Fig. 2). In experiments across different sized environments, and with various
levels of stochasticity, we universally find the increase in convergence speed
shown in the inset plot of Fig. 3. In the main plot of Fig. 3, we depict the
mean $Q$ values over all $(s,a)$ pairs. We find that the violated upper bound
(over-optimism) occurs across many tabular domains. In this experiment, we use
stochastic transition dynamics with a $50\%$ probability of taking the
intended action and $25\%$ probability of taking an action perpendicular to
that intended. As claimed previously, we see that as the Bellman loss reduces
(inset plot), the double-sided bounds become tight (blue and orange lines
converge).

#### Function Approximator Experiments

In the DQN algorithm used, a target network is employed for stability. We can
therefore also use the target network to derive another set of bounds on the
true $Q$-values (cf. Appendix for the un-regularized RL bounds corresponding
to those given in Theorem 4.1). Since both bounds must hold, we take the
tightest bound possible. In general, given many sources of an estimate
$Q$-function, one can collectively use them to obtain the tightest bound
possible.

Figure 4: Reward curves for the MountainCar environment. We fine tune each
method’s hyperparameters, and average over 20 random initializations. The
$95\%$ confidence intervals are shaded for each method.

The derived bounds can be implemented using different approaches for clipping
of the value function during training. We highlight the different methods used
below, inspired by the methods used in (Kim, Park, and Kim 2022; Adamczyk et
al. 2023b):
(0) No Clipping: The standard training scheme for DQN is implemented, with no
clipping.
(1) Hard Clipping: At each backward pass to the function approximator we
enforce the following bounds on the target value:

$Q(s,a)\xleftarrow[]{}\hat{Q}(s,a)$ (12)

where L and U denote the lower and upper bounds derived in Theorem 4.1, and

$\hat{Q}_{\textrm{clip}}\doteq\min\\{\max\\{r(s,a)+\gamma V(s^{\prime}),\
\text{L}(s,a)\\},\text{U}(s,a)\\}$ (13)

(2) Soft Clipping: An additional term, the “clipping loss”, is added to the
function approximator’s loss function. The clipping loss is defined as

$\mathcal{L}_{\textrm{clip}}=\left\lvert
Q(s,a)-\hat{Q}_{\textrm{clip}}(s,a)\right\rvert$ (14)

This gives a total loss of
$\mathcal{L}=\mathcal{L}_{\text{Bellman}}+\eta\mathcal{L}_{\text{clip}}$. The
hyperparameter $\eta$ weights the relative importance of the bound violations
against the Bellman error. In principle it can be tuned, but we choose to fix
$\eta=10^{-5}$ for all experiments, ensuring
$\mathcal{L}_{\text{Bellman}}\sim{}\eta\mathcal{L}_{\text{clip}}$.
Alternatively, one can view this as equivalent to providing a bonus to the
reward function for states with high bound violation. This is analogous to the
UCB-style bonus applied in (Lee et al. 2021).
(3) Smoothed Clipping: The updated $Q$-values are set as an average between
those given by Hard Clipping and No Clipping, with a relative weight factor
inversely related to the bound violations.

$\displaystyle Q(s,a)\xrightarrow[]{}(1-\tau)\left(r(s,a)+\gamma
V(s^{\prime})\right)+\tau\hat{Q}_{\textrm{clip}}(s,a)$

where

$\tau=\frac{\mathcal{L}_{\text{clip}}}{1+\mathcal{L}_{\text{clip}}}$ (15)

We note that when the bound violations are zero, the standard update rule is
recovered. This value for $\tau$ is chosen to set the relative weight of the
two terms to match the magnitude of bound violations:
$\tau/(1-\tau)=\mathcal{L}_{\text{clip}}$. Therefore, the clipped values will
be preferred over the standard update rule, in direct proportion to the bound
violations.

Figure 4 indicates that clipping is able to improve the stability and speed of
training in the MountainCar environment. Here, we use a bootstrapped estimate
of $Q(s,a)$ (that is, the target $Q$-network is bounded by the actively
trained $Q$-network).

## Discussion

In summary, we have established a general theoretical framework for deriving
double-sided bounds in reinforcement learning. We have explored the use of the
double-sided bounds in tabular domains, finding that application of the bounds
through clipping is able to speed up training. We also provide some
preliminary exploration in the FA domain where new experimental methods for
clipping were presented. Furthermore, beyond the theoretical contributions, we
believe the current work has the potential to open new directions of research
as outlined below.

While the derived bounds are applicable generally to any value function
estimate and for arbitrary transition dynamics, it is possible that they are
tightened for specific classes of the estimates and restrictions on the
dynamics or structure of reward functions. For example, in (Adamczyk et al.
2023b) which analyzed compositions in RL, it was shown that one side of the
bound can be simplified further for specific classes of functional
transformations or compositions. In future work, it would be interesting to
explore under what conditions the bounds may be further simplified or
tightened.

Other promising avenues for future research include: (i) combining our results
with ensemble methods such as SUNRISE (Lee et al. 2021) which can lead to
tighter bounds on the value function, as more estimates are used to derive the
double-sided bounds in Theorem 4.1, (ii) using bound violations as a proxy for
the best prior task to transfer (minimizing bound violations) when multiple
prior solutions are known, (iii) implementing a dynamic schedule for the soft
clipping weight parameter, similar to the approach in (Haarnoja et al. 2018b)
which includes learning a dynamical temperature parameter.

The extension of (Van Niekerk et al. 2019)’s Theorem 2 (shown above in Theorem
11) for value function composition was proved for the case of deterministic
dynamics in this work. However, it still remains an open question as to
whether this result is generalizable to other domains, e.g. stochastic
dynamics. Moreover, other composition methods may yield exact results for the
composite task’s value function (cf. (Tasse, James, and Rosman 2020, 2021)).
It will be of interest to see if the framework developed in this work can be
used to provide insight into the different conditions under which exact
compositions can be obtained.

Considering further the composition of multiple previously solved tasks, one
can consider the problem of learning a composition function $f$, which takes
into account the derived bounds. As a learning objective, one could use the
magnitude of the difference in bounds, to learn a function $f$ which can be
considered an “optimal composition” (e.g. related to (Rusu et al. 2016).

The framework established in this work can be used to obtain bounds for
optimal value functions in general settings, not just limited to the
composition of tasks. Specifically, we can use any estimate for the optimal
value function as the base knowledge and use the derived results to obtain
bounds on the exact optimal value function. In combination with the regret
bound derived in this work, iterations of PE/PI can serve as the initial steps
in an iterative procedure for progressively improving the bounds to obtain
improved approximate solutions. The development of such iterative procedures
will be explored in future work.

## Technical Appendix

In this technical appendix, we provide further discussion on experimental
details and give proofs for all the results shown in the main text.

### Experiments

In the tabular setting, we perform exact updates of the Bellman backup
equation for entropy-regularized RL. At each update step, we calculate the
bounds given by Theorem 4.1, which are exact in this case. Then we perform
Hard Clipping, by following Eq. (13) in the main text. Interestingly, we see
that as the upper bound becomes tight, the $Q$-values are constantly saturated
by this value. The departure of the No Clipping and Hard Clipping $Q$-values
is also evident in the reduction of error ($\ell_{\infty}$ distance) between
consecutive iterations.

To explore the utility of clipping in function approximator (FA) systems, we
use a DQN learning algorithm (Raffin et al. 2021), while applying and
monitoring clipping given by the bounds in Theorem 4.1 for un-regularized RL.
In particular, we continuously bootstrap by using the previous estimate of the
$Q$-function to generate the bounds, and we clip the target network’s output
value accordingly. In particular, we extract bounds from both the target
network and $Q$-network at each step, and take the tighter of the two bounds.
For continuous spaces, we use the estimate $\sup
r(s,a)\approx\max_{i\in\mathcal{D}}r(s,a)$, where the $\max$ is taken over the
current batch (and similarly for $\inf r(s,a)$). We consider the three
clipping methods described in the Experiments section of the main text.

We have also performed the same experiment, with a fixed learning rate, for
the Mountain-Car environment (Brockman et al. 2016). These experiments share
the hyperparameters shown in Table Experiments and are averaged over 25 runs.

Figure 5: Mountain-Car learning curves for a fixed learning rate
$\alpha=0.004$. The mean bound violations and episode rewards throughout
training are shown for each clipping method. In the right panel, we plot the
total bound violations (magnitude of over- or under-estimation of $Q$ based on
the allowed upper and lower bounds). We find that bound violations decrease
during training (most quickly for hard and smoothed clipping), which
corresponds to better performance in terms of the mean evaluation reward (left
plot).

We use $\epsilon$-greedy exploration, with a linear schedule from $1.0$ to
$0.07$ after $20\%$ of the total ($N=500\textrm{k}$) timesteps. The remaining
hyperparameters (shared by all clipping methods) are listed below.

Hyperparameter | Value
---|---
Learning Rate | 0.004
Batch Size | 128
Buffer Size | 10,000
Discount Factor, $\gamma$ | 0.98
Gradient Steps | 8
Policy Architecture | $(256,256)$
“Learning Starts” | 1,000
Polyak Update, $\tau$ | 1.0
Target Update Interval | 600
Training Frequency | 16

Table 1: Hyperparameters shared by all Deep Q Networks. These are the
hyperparameters published by the authors of the algorithm used (Raffin et al.
2021): https://huggingface.co/sb3/dqn-MountainCar-v0.

### Proofs

In this section we provide proofs of the theoretical results in the main text.
Each proof is prefaced with a restatement of the theorem for the reader’s
convenience.

We begin with a helpful lemma which bounds the optimal action-value function
$Q^{*}(s,a)$ for any task. We note that these bounds hold for both un-
regularized RL and entropy-regularized RL.

######  Lemma A.

For a task with reward function $r(s,a)$, discount factor $\gamma$, the (soft)
optimal action-value function $Q^{*}(s,a)$ satisfies:

$\displaystyle Q^{*}(s,a)$ $\displaystyle\geq
r(s,a)+\gamma\frac{\inf_{s,a}r(s,a)}{1-\gamma}$ $\displaystyle Q^{*}(s,a)$
$\displaystyle\leq r(s,a)+\gamma\frac{\sup_{s,a}r(s,a)}{1-\gamma}$

We will prove the upper bound for un-regularized RL, but the proof is
identical in entropy-regularized RL and for the lower bound.

###### Proof.

The proof follows from induction on the Bellman backup equation:

$Q^{(n+1)}(s,a)=r(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p(s^{\prime}|s,a)}\max_{a^{\prime}}\left(Q^{(n)}(s^{\prime},a^{\prime})\right)$
(16)

The result we aim to prove is the following:

$\displaystyle Q^{(n)}(s,a)$ $\displaystyle\geq
r(s,a)+\gamma\frac{1-\gamma^{n}}{1-\gamma}\inf_{s,a}r(s,a)$ $\displaystyle
Q^{(n)}(s,a)$ $\displaystyle\leq
r(s,a)+\gamma\frac{1-\gamma^{n}}{1-\gamma}\sup_{s,a}r(s,a)$

Since $\lim_{n\to\infty}Q^{(n)}(s,a)=Q^{*}(s,a)$ and $\gamma\in(0,1)$ the
desired result will follow from this limit.

We set $Q^{(0)}(s,a)=r(s,a)$. The base case ($n=1$) holds as:

$\displaystyle Q^{(1)}(s,a)$
$\displaystyle=r(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p(s^{\prime}|s,a)}\max_{a^{\prime}}\left(Q^{(0)}(s^{\prime},a^{\prime})\right)$
$\displaystyle=r(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p(s^{\prime}|s,a)}\max_{a^{\prime}}r(s^{\prime},a^{\prime})$
$\displaystyle\leq r(s,a)+\gamma\sup_{s,a}r(s,a)$
$\displaystyle=r(s,a)+\gamma\frac{1-\gamma^{1}}{1-\gamma}\sup_{s,a}r(s,a)$

We proceed in proving the upper bound. For brevity we shall denote
$\sup_{s,a}r(s,a)\doteq R$. The inductive hypothesis is

$Q^{(n)}(s,a)\leq r(s,a)+\gamma\frac{1-\gamma^{n}}{1-\gamma}R.$ (17)

To prove that the inequality holds for $n+1$, we use the Bellman backup
equation:

$\displaystyle Q^{(n+1)}(s,a)$ $\displaystyle\leq
r(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}}\max_{a^{\prime}}\left(r(s^{\prime},a^{\prime})+\gamma\frac{1-\gamma^{n}}{1-\gamma}R\right)$
$\displaystyle\leq
r(s,a)+\gamma\left(R+\gamma\frac{1-\gamma^{n}}{1-\gamma}R\right)$

At this point, if the dynamics model were known then one could improve this
bound by including the next term,
$\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p(s^{\prime}|s,a)}\max_{a^{\prime}}r(s^{\prime},a^{\prime})$,
which we instead bound by $R$. Continuing without this term, we have

$\displaystyle Q^{(n+1)}(s,a)$ $\displaystyle\leq
r(s,a)+\gamma\left(R+\gamma\frac{1-\gamma^{n}}{1-\gamma}R\right)$
$\displaystyle=r(s,a)+\gamma\frac{1-\gamma^{n+1}}{1-\gamma}R$

which completes the proof of the inductive step. As stated above, this
completes the proof of the upper bound by taking the limit $n\to\infty$.

The lower bound follows similarly by swapping all inequalities. The same proof
also holds for the soft Bellman backup equation. ∎

We now proceed with the proof of the first result, Theorem 4.1. We do so by
applying Lemma A to the $K^{*}$ function of (Adamczyk et al. 2023a)’s Theorem
1.

######  Theorem 4.1.

Consider an entropy-regularized MDP
$\langle\mathcal{S},\mathcal{A},p,r,\gamma,\beta\rangle$ with (unknown)
optimal value function $Q^{*}(s,a)$. Let an estimate for the value function
$Q(s,a)$ be given. Denote
$V(s)~{}\doteq~{}1/\beta\log\operatorname*{\mathbb{E}}_{a\sim\pi_{0}}\exp\beta
Q(s,a)$.

The optimal value function $Q^{*}(s,a)$ is then bounded by:

$\displaystyle Q^{*}(s,a)$ $\displaystyle\geq
r(s,a)+\gamma\left(\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}V(s^{\prime})+\frac{\inf\Delta}{1-\gamma}\right)$
(18a) $\displaystyle Q^{*}(s,a)$ $\displaystyle\leq
r(s,a)+\gamma\left(\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}V(s^{\prime})+\frac{\sup\Delta}{1-\gamma}\right)$
(18b)

where

$\Delta(s,a)\doteq
r(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}V(s^{\prime})-Q(s,a).$

In Eq. (18a) and (18b), the $\inf$ and $\sup$ are taken over the continuous
state-action space $\mathcal{S}\times\mathcal{A}$.

###### Proof.

As a point of notation, $\widetilde{r}(s,a)$ in (Adamczyk et al. 2023a) is the
same as our $r(s,a)$. Using Theorem 1 of (Adamczyk et al. 2023a), we have

$Q^{*}(s,a)=Q(s,a)+K^{*}(s,a)$ (19)

where $K^{*}$ is the optimal soft action value function corresponding to a
task with reward function $\Delta(s,a)\doteq
r(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p(\cdot|s,a)}V(s^{\prime})-Q(s,a)$.
By applying Lemma A on the value function $K^{*}$, we arrive at the stated
result in Eq. (18b):

$\displaystyle Q^{*}(s,a)$ $\displaystyle=Q(s,a)+K^{*}(s,a)$
$\displaystyle\leq Q(s,a)+\Delta(s,a)+\gamma\frac{\sup\Delta}{1-\gamma}$
$\displaystyle=Q(s,a)+r(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p(\cdot|s,a)}V(s^{\prime})$
$\displaystyle\hskip 40.00006pt-Q(s,a)+\gamma\frac{\sup\Delta}{1-\gamma}$
$\displaystyle=r(s,a)+\gamma\left(\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p(\cdot|s,a)}V(s^{\prime})+\frac{\sup\Delta}{1-\gamma}\right).$

A similar proof holds for the lower bound. ∎

######  Lemma 4.1a.

Consider an entropy-regularized MDP
$\langle\mathcal{S},\mathcal{A},p,r,\gamma,\beta\rangle$ with (unknown)
optimal value function $Q^{*}(s,a)$. Let an estimate for the value function
$Q(s,a)$ be given. Denote
$V(s)~{}\doteq~{}1/\beta\log\operatorname*{\mathbb{E}}_{a\sim\pi_{0}}\exp\beta
Q(s,a)$. Suppose there exists an “identity” action
$a_{\emptyset}(s)\in\mathcal{A}$ for each state, which deterministically
transitions the agent to the same state:
$p(s^{\prime}|s,a_{\emptyset}(s))=\delta(s^{\prime}-s)$ for all
$s\in\mathcal{S}$.

Then the lower bound on the optimal value function $Q^{*}(s,a)$ can be
improved:

$Q^{*}(s,a)\geq
r(s,a)+\gamma\left(V(s^{\prime})+\frac{1}{1-\gamma}\Delta(s^{\prime},a_{\emptyset})\right)$
(20)

###### Proof.

The lower bound in Theorem 4.1 can be tightened by noting that the value
function (in both un-regularized and entropy-regularized RL) satisfies a
variational form:

$Q(s,a)=\sup_{\pi}Q^{\pi}(s,a)$ (21)

where

$Q^{\pi}(s,a)=\operatorname*{\mathbb{E}}_{p,\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})\biggr{|}\
s_{0}=s,a_{0}=a\right]$

and

$Q^{\pi}(s,a)=\operatorname*{\mathbb{E}}_{p,\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}\left(r(s_{t},a_{t})-\frac{1}{\beta}\log\frac{\pi(a_{t}|s_{t})}{\pi_{0}(a_{t}|s_{t})}\right)\right]$

for standard and entropy-regularized RL, respectively (we have dropped the
initial state-action conditioning in the latter equation for brevity).

Therefore, one can supply any policy $\pi$ into the objective $Q^{\pi}$ to
obtain a lower bound on the optimal value function. However, the expectation
(policy evaluation) is difficult to perform in practice because it corresponds
to the solution to another Bellman equation (Sutton and Barto 2018).

Nevertheless, for particular choices of the input policy $\pi$, one can obtain
a simplified expression for $Q^{\pi}$ leading to a tractable lower bound. With
this in mind, we choose the deterministic “identity policy”,
$\pi_{\emptyset}$, defined as:

$\pi_{\emptyset}(a|s)=a_{\emptyset}(s)$ (22)

where $a_{\emptyset}(s)$ is the action (for a given state $s\in\mathcal{S}$)
such that

$p(s^{\prime}|s,a_{\emptyset}(s))=\delta(s^{\prime}-s).$ (23)

In other words, the identity policy is a deterministic policy which
transitions the agent back to the same state. We note that this requires the
transition dynamics of the task to be deterministic (at least, for this
identity action).

With this in mind, we must evaluate the objective
$Q^{\pi_{\emptyset}}~{}=~{}\hat{Q}^{\pi_{\emptyset}}+S^{\pi_{\emptyset}}$,
which we split between the reward and entropic terms. First, we note that
since $\pi_{\emptyset}$ is deterministic, the relative entropy term satisfies

$S^{\pi_{\emptyset}}=\operatorname*{\mathbb{E}}_{p,\pi_{\emptyset}}\left[\sum_{t=0}^{\infty}\gamma^{t}\log\frac{\pi_{\emptyset}(a_{t}|s_{t})}{\pi_{0}(a_{t}|s_{t})}\right]=0.$
(24)

Therefore, it suffices to evaluate the reward contributions alone which can be
done as follows:

$\displaystyle\widehat{Q}^{\pi_{\emptyset}}(s,a)$
$\displaystyle=\operatorname*{\mathbb{E}}_{p,\pi_{\emptyset}}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})\biggr{|}\
s_{0}=s,a_{0}=a\right]$ $\displaystyle=r(s_{0},a_{0})+\gamma
r(s_{1},a_{\emptyset})+\gamma^{2}r(s_{1},a_{\emptyset})+\dots$
$\displaystyle=r(s_{0},a_{0})+\frac{\gamma}{1-\gamma}r(s_{1},a_{\emptyset})$

We see that the determinism of transitions arising from non-identity actions
is required for the first step away from the initial condition. Therefore, we
have $Q(s,a)\geq r(s,a)+\frac{\gamma}{1-\gamma}r(s^{\prime},a_{\emptyset})$.

Now, applying this result to the auxiliary task with optimal value function
$K^{*}$:

$K^{*}(s,a)\geq\Delta(s,a)+\frac{\gamma}{1-\gamma}\Delta(s^{\prime},a_{\emptyset}).$
(25)

Inserting this bound into Theorem 1 of (Adamczyk et al. 2023a), we find:

$\displaystyle Q^{*}(s,a)$ $\displaystyle\geq
Q(s,a)+\Delta(s,a)+\frac{\gamma}{1-\gamma}\Delta(s^{\prime},a_{\emptyset})$
$\displaystyle=r(s,a)+\gamma\left(V(s^{\prime})+\frac{1}{1-\gamma}\Delta(s^{\prime},a_{\emptyset})\right)$

∎

As claimed in the main text, we now show that this lower bound is tighter than
the previous one in Eq. 18a of the main text. Since
$\Delta(s^{\prime},a_{\emptyset})\geq\inf\Delta(s,a)$, this bound can be
saturated only for the initial state-action $(s,a)$ which transitions the
agent to $s^{\prime}=s^{*}$, the state in which the global reward function
$\Delta$ attains its minimum.

######  Corollary 4.2 (Suboptimality Bounds).

Let policy $\pi(a|s)$ be given with soft value $Q^{\pi}(s,a)$. The rate of the
suboptimality gap, $Q^{*}(s,a)-Q^{\pi}(s,a)$, is then bounded between

$\inf_{(s,a)}d(s,a)\leq\frac{Q^{*}(s,a)-Q^{\pi}(s,a)}{H}\leq\sup_{(s,a)}d(s,a)$
(26)

where $d(s,a)\doteq
r(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}}V^{\pi}(s^{\prime})-Q^{\pi}(s,a)$,
$V^{\pi}(s)\doteq\log\operatorname*{\mathbb{E}}_{a}\exp\beta Q^{\pi}(s,a)$ is
the soft state-value function, and $H=(1-\gamma)^{-1}$ is the effective time
horizon.

###### Proof.

Consider a task with the stated reward function

$d(s,a)~{}\doteq~{}Q^{\pi}(s,a)~{}-~{}\frac{\gamma}{\beta}\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}\log\operatorname*{\mathbb{E}}_{a^{\prime}\sim{}\pi}\exp\beta
Q^{\pi}(s^{\prime},a^{\prime}).$

By (Cao, Cohen, and Szpruch 2021), this task’s corresponding optimal value
function is $Q_{d}^{*}(s,a)=Q^{\pi}(s,a)$. We see that the suboptimality gap
$Q^{*}-Q^{\pi}$ is nothing but the soft value function $K^{*}(s,a)$ (Adamczyk
et al. 2023a) for a task with reward function $d(s,a)$, given above. Applying
the simple bounds $H\inf d(s,a)\leq K^{*}(s,a)\leq H\sup d(s,a)$ yields the
stated result, with $H=(1-\gamma)^{-1}$ being the time horizon. ∎

######  Theorem 4.3.

Let the functions $L(s,a),U(s,a)$ be lower and upper bounds on the optimal
value function: $L(s,a)~{}\leq~{}Q^{*}(s,a)~{}\leq U(s,a)$ for all
$s\in\mathcal{S}$ and $a\in\mathcal{A}$. The clipped Bellman operator,
$\mathcal{B}_{C}Q(s,a)~{}:=~{}\max_{s,a}\left(\min_{s,a}\left(\mathcal{B}Q(s,a),U(s,a)\right),L(s,a)\right)$
converges to the optimal value function
$Q^{*}(s,a)~{}=~{}\mathcal{B}^{\infty}Q(s,a)$.

###### Proof.

We first show convergence of the operator $\mathcal{B}_{C}$, then show that it
converges to the same fixed point. For convergence, it suffices to show that
$|\mathcal{B}_{C}Q(s,a)-Q^{*}(s,a)|\leq\gamma|Q(s,a)-Q^{*}(s,a)|$.

There are three cases for the magnitude of $\mathcal{B}Q(s,a)$ relative to the
upper and lower bounds:

  1. 1.

$\mathcal{B}Q(s,a)\in(L(s,a),U(s,a))$

  2. 2.

$\mathcal{B}Q(s,a)\in(-\infty,L(s,a))$

  3. 3.

$\mathcal{B}Q(s,a)\in(U(s,a),\infty)$

In the first case, clipping does not occur and hence
$\mathcal{B}_{C}Q(s,a)=\mathcal{B}Q(s,a)$, which contracts with rate
$\gamma$.In the second case, we can write $\mathcal{B}Q(s,a)=L(s,a)-\chi(s,a)$
where $\chi(s,a):=\mathcal{B}Q-L(s,a)>0$ is referred to as the “bound
violation”. Then,

$\displaystyle\ \ \ \ \ |\mathcal{B}_{C}Q(s,a)-Q^{*}(s,a)|$
$\displaystyle=|Q^{*}(s,a)-\mathcal{B}_{C}Q(s,a)|$
$\displaystyle=|Q^{*}(s,a)-L(s,a)|$
$\displaystyle\leq|Q^{*}(s,a)-L(s,a)+\chi(s,a)|$
$\displaystyle=|Q^{*}(s,a)-(L(s,a)-\chi(s,a))|$
$\displaystyle=|Q^{*}(s,a)-\mathcal{B}Q(s,a)|$
$\displaystyle\leq\gamma|Q(s,a)-Q^{*}(s,a)|$

A similar proof holds for case 3.

By the Banach fixed point theorem, it follows that repeated application of
$\mathcal{B}_{C}$ converges to a fixed point. It is clear that the fixed point
for $\mathcal{B}$ is also a fixed point for $\mathcal{B}_{C}$, and since it is
unique, we have
$\mathcal{B}_{C}^{\infty}Q(s,a)=\mathcal{B}^{\infty}Q(s,a)=Q^{*}(s,a)$. ∎

### Error Analysis for Continuous Spaces

In this subsection, we turn to those results specific to the bounds in
continuous spaces and their error analysis, based on Lipschitz-continuity.

######  Lemma 4.4.

Let $\mathcal{S}\times\mathcal{A}$ be a bounded metric space with diameter
$D$, and let $r:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$ be
$L_{r}$-Lipschitz (w.r.t. the same metric). Then the global extrema of
$r(s,a)$ on $\mathcal{S}\times\mathcal{A}$ are bounded as follows:

$\displaystyle\sup_{s\in\mathcal{S},a\in\mathcal{A}}r(s,a)$
$\displaystyle\leq\min_{(s,a)\in\mathcal{D}}r(s,a)+L_{r}D$
$\displaystyle\inf_{s\in\mathcal{S},a\in\mathcal{A}}r(s,a)$
$\displaystyle\geq\max_{(s,a)\in\mathcal{D}}r(s,a)-L_{r}D$

where $\mathcal{D}$ is the dataset of $(s,a)$ tuples available for querying
the magnitude of $r$ (e.g. the current batch or buffer).

Figure 6: Depiction of a continuous state-action space with a finite set of
samples (black points) used to bound the global extrema (star). The diameter
of the space is depicted in red. The distance between each sample and the
global extrema (dashed lines) is always less than the diameter (solid red
line) of the space. Since the growth of the function is linearly bounded by
Lipschitz continuity, we can derive a bound on the value of the global extrema
given the finitely many samples.

###### Proof.

We prove the upper bound on the supremum, the lower bound on the infimum
follows similarly.

Let $\mathcal{S}\times\mathcal{A}$ be a bounded metric space endowed with the
$p$-product metric (for simplicity) and let
$r:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$ (the function for which we wish
to find the global extrema) be $L_{r}$-Lipschitz continuous. Let the diameters
of state and action space be given: $D_{\mathcal{S}},D_{\mathcal{A}}$. Suppose
a finite set of samples $\mathcal{D}\subset\mathcal{S}\times\mathcal{A}$ is
given. Denote $\sup_{s\in\mathcal{S},a\in\mathcal{A}}r(s,a)=r(s^{*},a^{*})$.
For each $(s,a)\in\mathcal{D}$, the following holds:

$\displaystyle r(s^{*},a^{*})-r(s,a)$ $\displaystyle=|r(s^{*},a^{*})-r(s,a)|$
$\displaystyle\leq L_{r}d\left((s^{*},a^{*}),(s,a)\right)$

since the reward function $r$ is $L_{r}$-Lipschitz in the $d$ metric. In
practice, the distance between the extrema and an arbitrary point (right-hand
side) is unknown, and a generally applicable (albeit loose) bound on this
distance is simply the diameter of the space,
$D=||(D_{\mathcal{S}},D_{\mathcal{A}})||_{p}$. This leads to the following
bound:

$r(s^{*},a^{*})\leq r(s,a)+L_{r}D.$ (27)

This follows from the definition of Lipschitz continuity:

$\displaystyle r(s^{*},a^{*})-r(s,a)$ $\displaystyle=|r(s^{*},a^{*})-r(s,a)|$
$\displaystyle\leq L_{r}d\left((s^{*},a^{*}),(s,a)\right)$ $\displaystyle\leq
L_{r}D$

Since each $(s,a)\in\mathcal{D}$ provides such a bound, we can take the best
one (i.e. the minimum over all points in the subset $\mathcal{D}$), recovering
the stated bound:

$r(s^{*},a^{*})\leq\min_{(s,a)\in\mathcal{D}}r(s,a)+L_{r}D.$ (28)

In case the calculation $d((s_{1},a_{1}),(s_{2},a_{2}))$ is feasible, one can
replace the diameter with the furthest distance from the point in question to
any other point in the (bounded) set:

$r(s^{*},a^{*})\leq\min_{(s,a)\in\mathcal{D}}\left(r(s,a)+L_{r}\sup_{s^{\prime},a^{\prime}}d((s,a),(s^{\prime},a^{\prime}))\right)$

where the $\sup$ is over all $(s,a)\in\mathcal{S}\times\mathcal{A}$. which
follows by a similar argument as given above:

$\displaystyle r(s^{*},a^{*})-r(s,a)$ $\displaystyle=|r(s^{*},a^{*})-r(s,a)|$
$\displaystyle\leq L_{r}d\left((s^{*},a^{*}),(s,a)\right)$ $\displaystyle\leq
L_{r}\sup_{(s^{\prime},a^{\prime})\in\mathcal{S}\times\mathcal{A}}d((s,a),(s^{\prime},a^{\prime}))$

This provides a tighter bound but is less tractable in practice. ∎

We now provide some preliminary results on Lipschitz MDPs which facilitate the
proofs of the subsequent results. The following result proves Lipschitz
continuity of the value function in un-regularized RL, provided by (Rachelson
and Lagoudakis 2010).

######  Theorem 4.5a (Rachelson and Lagoudakis).

Given an $(L_{r},L_{p})$-Lipschitz continuous MDP and an $L_{\pi}$-Lipschitz
continuous, stationary policy $\pi$, if $\gamma L_{p}(1+L_{\pi})<1$, then the
infinite horizon, $\gamma$-discounted value function $Q^{\pi}$ is
$L_{Q}$-Lipschitz continuous, with:

$L_{Q}=\frac{L_{r}}{1-\gamma L_{p}(1+L_{\pi})}$ (29)

We will extend this result to the case of entropy-regularized RL where the
policy’s entropy plays a role. To extend it to the entropy-regularized case,
we begin with (and following the notation of) Lemma 1 in (Rachelson and
Lagoudakis 2010). Since the entropy of the policy appears in the calculation
of the state-value function, we require a tractable policy class. We use the
Gaussian parameterization due to its widespread use (Haarnoja et al. 2018b;
Raffin et al. 2021).

######  Lemma 4.5b.

In entropy-regularized RL, given an $L_{Q}$-Lipschitz continuous $Q$-function
$Q^{\pi}$ denoting the soft value of a Gaussian policy
$\pi(\cdot|s)\sim{}\mathcal{N}\left(\mu(s),\sigma(s)\right)$, the
corresponding value function $V^{\pi}(s)$ is $L$-Lipschitz continuous, with:

$L=L_{Q}(1+L_{\mathcal{N}})+\frac{1}{\beta\sigma_{\text{min}}},$ (30)

where $\sigma_{\text{min}}=\min_{s}\sigma(s)$ and
$L_{\mathcal{N}}=\sigma_{\text{min}}^{-2}(2\pi e)^{-1/2}$ is the maximum
Lipschitz constant of the Gaussian density across all states.

###### Proof.

As in SAC (Haarnoja et al. 2018b; Raffin et al. 2021) we assume a Gaussian
parameterization with bounded variance $\sigma(s)\geq\sigma_{\textrm{min}}$.
We begin by finding the Lipschitz constant for $V^{\pi}(s)$ in the entropy-
regularized setting. Using the definition of the soft state-value function
(Haarnoja et al. 2018b),

$\displaystyle\big{|}V^{\pi}(s)-V^{\pi}(\hat{s})\big{|}$
$\displaystyle\leq\bigg{|}\operatorname*{\mathbb{E}}_{a\sim{}\pi}Q^{\pi}(s,a)-\operatorname*{\mathbb{E}}_{a\sim{}\pi}Q^{\pi}(\hat{s},a)\biggr{|}$
$\displaystyle+\beta^{-1}\biggl{|}\left(\mathbb{H}\left[\pi(\cdot|s)\right]-\mathbb{H}\left[\pi(\cdot|\hat{s})\right]\right)\bigg{|}$
$\displaystyle=\bigg{|}\operatorname*{\mathbb{E}}_{a\sim{}\pi}Q^{\pi}(s,a)-\operatorname*{\mathbb{E}}_{a\sim{}\pi}Q^{\pi}(\hat{s},a)\biggr{|}+\beta^{-1}\biggl{|}\log\frac{\sigma(s)}{\sigma(\hat{s})}\bigg{|}$
$\displaystyle\leq\bigg{|}\operatorname*{\mathbb{E}}_{a\sim{}\pi}Q^{\pi}(s,a)-\operatorname*{\mathbb{E}}_{a\sim{}\pi}Q^{\pi}(\hat{s},a)\biggr{|}+\beta^{-1}\big{|}\log(s)-\log(\hat{s})\big{|}$
$\displaystyle\leq
L_{Q}(1+L_{\pi})\big{|}s-\hat{s}\big{|}+\frac{1}{\beta\sigma_{\text{min}}}\big{|}s-\hat{s}\big{|}$
$\displaystyle=\left(L_{Q}(1+L_{\pi})+\frac{1}{\beta\sigma_{\text{min}}}\right)\big{|}s-\hat{s}\big{|}.$

The second line follows from the entropy of the Gaussian distribution. The
fourth line follows from (Rachelson and Lagoudakis 2010) and from the
Lipschitz-continuity of $\log(\cdot)$ on the domain
$(\sigma_{\text{min}},\infty)$. In practice, one must choose some
$\sigma_{\text{min}}$ to ensure numerical stability. In the case
$\beta\sigma_{\min}\to\infty,\sigma_{\text{min}}\to 0$, the policy becomes
deterministic and the RL objective reduces to un-regularized RL and the
previous result is recovered.

Since the Gaussian distribution is continuous everywhere, its Lipschitz
constant $L_{\mathcal{N}}=\sigma^{-2}(2\pi e)^{-1/2}$ is easily found by
finding the maximum magnitude of the first derivative. Since we are interested
in a globally applicable Lipschitz constant, we take the upper bound given by
$\sigma_{\text{min}}$. Substituting $L_{\pi}=L_{\mathcal{N}}$ above gives the
stated result. ∎

Now, we extend Lemma 2 of (Rachelson and Lagoudakis 2010) to the entropy-
regularized setting with a Gaussian policy:

######  Lemma 4.5c.

Given an $(L_{p},L_{r})$-Lipschitz continuous entropy-regularized MDP and a
Gaussian policy with bounded variance $\sigma(s)\geq\sigma_{\text{min}}$, the
$n$-step, finite horizon, $\gamma$-discounted soft value function
$Q^{\pi}_{n}$is $L_{Q_{n}}$-Lipschitz continuous and $L_{Q_{n}}$ obeys the
recurrence relation

$L_{Q_{n+1}}=L_{r}+\gamma\left((1+L_{\mathcal{N}})L_{Q_{n}}+(\beta\sigma_{\text{min}})^{-1}\right)L_{p}$

###### Proof.

The proof is identical to that of Lemma 2 in (Rachelson and Lagoudakis 2010)
except the penultimate line, where we instead use the Lipschitz constant
computed for $V^{\pi}(s)$ in Lemma 4.5b:

$\displaystyle\left\lvert
Q^{\pi}_{n+1}(s,a)-Q^{\pi}_{n+1}(\hat{s},\hat{a})\right\rvert$
$\displaystyle\leq\left(L_{r}+\gamma
L_{V_{n}}L_{p}\right)\left(|s-\hat{s}|+|a-\hat{a}|\right)$
$\displaystyle=\left(L_{r}+\gamma\left(L_{Q_{n}}(1+L_{\mathcal{N}})+\frac{1}{\beta\sigma_{\text{min}}}\right)L_{p}\right)\times$
$\displaystyle\hskip 130.0002pt\left(|s-\hat{s}|+|a-\hat{a}|\right)$
$\displaystyle=L_{Q_{n+1}}\left(|s-\hat{s}|+|a-\hat{a}|\right).$

∎

We are now ready to prove the extension of Theorem 29 in entropy-regularized
RL:

######  Theorem 4.5d.

Given an $(L_{r},L_{p})$-Lipschitz continuous MDP and a Gaussian policy
$\mathcal{N}(\mu(s),\sigma(s))$ with bounded variance
$\sigma(s)\geq\sigma_{min}$, if $\gamma L_{p}(1+L_{\mathcal{N}})<1$, then the
infinite horizon, $\gamma$-discounted value function $Q^{\pi}$ is
$L_{Q}$-Lipschitz continuous, with:

$L_{Q}=\frac{L_{r}+\gamma L_{p}(\beta\sigma_{\min})^{-1}}{1-\gamma
L_{p}(1+L_{\mathcal{N}})}$ (31)

###### Proof.

We follow the same steps as given in the proof of Theorem 1 of (Rachelson and
Lagoudakis 2010), concluding by considering the recurrence relation in the
convergent limit $L_{Q_{n}}\to L_{Q}$:

$L_{Q}=L_{r}+\gamma\left((1+L_{\mathcal{N}})L_{Q}+(\beta\sigma_{\text{min}})^{-1}\right)L_{p}$
(32)

Solving for $L_{Q}$ yields

$L_{Q}=\frac{L_{r}+\gamma L_{p}(\beta\sigma_{\min})^{-1}}{1-\gamma
L_{p}(1+L_{\mathcal{N}})}.$ (33)

∎

######  Theorem 4.5.

Let an entropy-regularized MDP be given with an $L_{Q}$-Lipschitz value
function $\bar{Q}^{\pi}$. Using a Gaussian parameterization for the associated
policy $\pi(\cdot|s)=\mathcal{N}(\mu(s),\sigma(s))$, suppose that
$\bar{Q}^{\pi}$ is an $\varepsilon$-optimal approximation of the policy’s true
value, $Q^{\pi}$.

By estimating the state-value function as:

$\bar{V}^{\pi}(s)=\bar{Q}^{\pi}(s,\mu)-\frac{1}{\beta}\operatorname*{\mathbb{E}}_{a\sim{}\pi}\log\frac{\pi(a|s)}{\pi_{0}(a|s)},$
(34)

the error in using such an approximation is upper bounded:

$|\bar{V}^{\pi}(s)-V^{\pi}(s)|\leq\sqrt{\frac{2}{\pi}}L_{Q}\sigma(s)e^{-\mu(s)^{2}/2\sigma(s)^{2}}+\varepsilon$

In the case that the function $Q$ used is an optimal value function for an
$(L_{r},L_{p})$-Lipschitz task, with a policy whose variance is lower bounded
$\sigma(s)\geq\sigma_{\text{min}}$ and $\gamma L_{p}(1+L_{\mathcal{N}})<1$,
where $L_{\mathcal{N}}=\sigma_{\text{min}}^{-2}(2\pi e)^{-1/2}$ is the
Lipschitz constant of the Gaussian distribution, then the Lipschitz constant
for $Q$ can be computed as:

$L_{Q}=\frac{L_{r}+\gamma L_{p}(\beta\sigma_{\min})^{-1}}{1-\gamma
L_{p}(1+L_{\mathcal{N}})}.$ (35)

###### Proof.

We first note that although the relative entropy appears in Eq. (7), we will
substitute it with the entropy alone. This is the typical scenario for MaxEnt
RL, where the prior policy is ignored. However, in the case of a Gaussian-
parameterized prior policy, the remaining term
$\operatorname*{\mathbb{E}}_{a\sim{}\pi}\log\pi_{0}(a|s)$ has an analytical
form. Continuing with the entropy, we see that if the variance is known, it is
easily expressed as:

$\mathbb{H}[\mathcal{N}(\mu,\sigma)]=\frac{1}{2}\log(2\pi\sigma^{2})+\frac{1}{2}.$
(36)

Alternative to the variance, the log-probability of the mean is sometimes used
in the parameterization (Raffin et al. 2021), which encodes the same
information:

$-\log(p(\mu))=-\log\left(\frac{1}{\sqrt{2\pi\sigma^{2}}}\right)=\mathbb{H}[\mathcal{N}(\mu,\sigma)]-\frac{1}{2}.$

Therefore, we only take into account the error in the first term, the
estimation of $\operatorname*{\mathbb{E}}_{a\sim{}\pi}Q^{\pi}(s,a)$ given only
the mean action $\mu$. We drop the $s$ dependence, denoting $\mu=\mu(s)$ and
$\sigma=\sigma(s)$.

$\displaystyle\ \ \ \ \left\lvert\bar{V}^{\pi}(s)-V^{\pi}(s)\right\rvert$
$\displaystyle=\left\lvert\operatorname*{\mathbb{E}}_{a\sim{}\pi}Q^{\pi}(s,a)-Q^{\pi}(s,\mu)\right\rvert+\left\lvert\operatorname*{\mathbb{E}}_{a\sim{}\pi}Q^{\pi}(s,a)-\bar{Q}^{\pi}(s,\mu)\right\rvert$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{a\sim{}\pi}\left|Q(s,a)-Q(s,\mu)\right|+\varepsilon$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{a\sim{}\pi}L_{Q}|a-\mu|+\varepsilon$
$\displaystyle=\frac{L_{Q}}{\sqrt{2\pi\sigma^{2}}}\int_{-\infty}^{\infty}e^{-\frac{(a-\mu)^{2}}{2\sigma^{2}}}|a-\mu|da+\varepsilon$
$\displaystyle=\frac{L_{Q}}{\sqrt{2\pi\sigma^{2}}}2\sigma^{2}e^{-\mu^{2}/2\sigma^{2}}+\varepsilon$
$\displaystyle=\sqrt{\frac{2}{\pi}}L_{Q}\sigma
e^{-\mu^{2}/2\sigma^{2}}+\varepsilon$

Here we have used the one-dimensional absolute value norm for actions, but the
result can be readily extended in a similar way for particular choices of the
metric on the action space. The fifth line follows from the $Q$ function being
$L_{Q}$-Lipschitz continuous, and the final line follows from substituting in
Theorem 29 for $L_{Q}$. ∎

Interestingly, this result has shown that there is maximum potential error
obtained in iterations of policy evaluation, with a non-trivial dependence on
the variance of the distribution in question.

To prove Theorem 4.6 we first provide some lemmas detailing the error analysis
for the $V^{\pi}(s)$ and $\Delta(s,a)$ terms appearing in the double-sided
bounds of Theorem 4.1 and Lemma 4.4; both of which are prone to estimation
errors.

######  Lemma 4.6a.

The maximum error in replacing $\Delta$ with $\bar{\Delta}$ (as defined in
Theorem 4.6, i.e. by using the one-point estimate for the expected $Q$-value)
is upper bounded:

$|\Delta(s,a)-\bar{\Delta}(s,a)|\leq\gamma\sqrt{\frac{2}{\pi}}L_{Q}\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}A(s^{\prime})$

where we introduce the shorthand
$A(s)=\sigma(s)e^{-\mu(s)^{2}/2\sigma(s)^{2}}+\varepsilon$.

###### Proof.

$\displaystyle\ \ \ \ |\Delta(s,a)-\bar{\Delta}(s,a)|$
$\displaystyle=\gamma\big{|}\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}\left(V(s^{\prime})-\bar{V}(s^{\prime})\right)\big{|}$
$\displaystyle\leq\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}\big{|}V(s^{\prime})-\bar{V}(s^{\prime})\big{|}$
$\displaystyle\leq\gamma\left(\sqrt{\frac{2}{\pi}}L_{Q}\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}\sigma(s^{\prime})e^{-\mu(s^{\prime})^{2}/2\sigma(s^{\prime})^{2}}+\varepsilon\right)$

∎

######  Lemma 4.6b.

The reward function $\Delta$ generated from an $L_{Q}$-Lipschitz continuous
function $Q(s,a)$,
$\Delta(s,a)~{}\doteq~{}r(s,a)~{}+~{}\gamma~{}\operatorname*{\mathbb{E}}_{s^{\prime}}V(s^{\prime})-Q(s,a)$
with ($L_{r},L_{p}$)-Lipschitz rewards and dynamics, is Lipschitz continuous
with

$L_{\Delta}=\max\left\\{L_{r},L_{Q},\gamma
L_{p}\left(L_{Q}(1+L_{\mathcal{N}})+(\beta\sigma_{\text{min}})^{-1}\right)\right\\}.$

###### Proof.

The Lipschitz constant of a sum of Lipschitz functions:
$r(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}}\bar{V}(s^{\prime})-Q(s,a)$
is itself Lipschitz continuous, with the Lipschitz constant being the maximum
of all terms’ Lipschitz constants:

$L_{\Delta}=\max\left\\{L_{r},L_{Q},\gamma L_{p}L_{V}\right\\},$ (37)

where $L_{V}$ is given in Lemma 4.5b. Since the relative magnitude of each
Lipschitz constant is unknown a prior, we can make no further simplification
without additional assumptions. ∎

Now we are positioned to prove Theorem 4.6, the double-sided bounds on the
soft $Q$-function with estimation errors included.

######  Theorem 4.6.

Let the $L_{Q}$-Lipschitz value function $Q^{\pi}$ and corresponding Gaussian
policy $\pi(\cdot|s)=\mathcal{N}(\mu(s),\sigma(s))$ be given, where $Q^{\pi}$
is an $\varepsilon$-optimal estimate of the true policy’s value function. For
an $(L_{r},L_{p})$-Lipschitz task with (unknown) optimal value function
$Q^{*}$, let $\bar{V}^{\pi}$ be the one-point estimate of the (known) value
function $Q^{\pi}$, and denote
$\bar{\Delta}(s,a)=r(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}\bar{V}^{\pi}(s^{\prime})-Q^{\pi}(s,a)$.
Then:

$\displaystyle Q^{*}(s,a)\leq
r(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}\left[\bar{V}^{\pi}(s^{\prime})+A(s^{\prime})\right]$
$\displaystyle\hskip
10.00002pt+\frac{\gamma}{1-\gamma}\left(\min_{(s,a)\in\mathcal{D}}\left(\bar{\Delta}(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}A(s^{\prime})\right)+L_{\Delta}D\right)$
$\displaystyle Q^{*}(s,a)\geq
r(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}\left[\bar{V}^{\pi}(s^{\prime})-A(s^{\prime})\right]$
$\displaystyle\hskip
10.00002pt+\frac{\gamma}{1-\gamma}\left(\max_{(s,a)\in\mathcal{D}}\left(\bar{\Delta}(s,a)-\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}A(s^{\prime})\right)-L_{\Delta}D\right)$

where we let
$A(s)=\sqrt{\frac{2}{\pi}}L_{Q}\sigma(s)e^{-\mu(s)/2\sigma(s)^{2}}+\varepsilon$
and $L_{\Delta}=\max\left\\{L_{r},L_{Q},\gamma
L_{p}\left(L_{Q}(1+L_{\mathcal{N}})+(\beta\sigma_{\text{min}})^{-1}\right)\right\\}$
and $D$ denotes the diameter of the state-action space.

###### Proof.

We will prove the upper bound, with the lower bound following accordingly.

Beginning with the exact form in Theorem 4.1, the main idea is to propagate
the errors due to the single-point estimation for $\bar{V}$, the resulting
error in the calculation of $\Delta$ itself, and the $\sup(\Delta)$
estimation.

$\displaystyle Q(s,a)$ $\displaystyle\leq
r(s,a)+\gamma\left(\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}V^{\pi}(s^{\prime})+\frac{\sup\Delta(s,a)}{1-\gamma}\right)$
$\displaystyle\leq
r(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}\biggr{[}\big{|}V^{\pi}(s^{\prime})-\bar{V}^{\pi}(s^{\prime})\big{|}+\bar{V}^{\pi}(s^{\prime})\biggr{]}$
$\displaystyle\hskip
40.00006pt+\frac{\gamma}{1-\gamma}\left(\min_{(s,a)\in\mathcal{D}}\Delta(s,a)+L_{\Delta}D\right)$
$\displaystyle\leq
r(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}\left[\bar{V}^{\pi}(s^{\prime})+A(s^{\prime})\right]$
$\displaystyle\hskip
40.00006pt+\frac{\gamma}{1-\gamma}\left(\min_{(s,a)\in\mathcal{D}}\Delta(s,a)+L_{\Delta}D\right)$
$\displaystyle\leq
r(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}\left[\bar{V}^{\pi}(s^{\prime})+A(s^{\prime})\right]$
$\displaystyle+\frac{\gamma}{1-\gamma}\left(\min_{(s,a)\in\mathcal{D}}\left(\bar{\Delta}(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}A(s^{\prime})\right)+L_{\Delta}D\right)$

where
$A(s)=\sqrt{\frac{2}{\pi}}L_{Q}\sigma(s)e^{-\mu(s)^{2}/2\sigma(s)^{2}}+\varepsilon$
and $L_{\Delta}=\max\left\\{L_{r},L_{Q},\gamma L_{p}L_{V}\right\\}$. The
second line follows from Lemma 4.4, the third line follows from Theorem 4.5,
and the fourth line follows from Lemma 4.6a. ∎

### Un-Regularized RL

We now turn to proofs of the analogous results in standard (un-regularized)
RL. We begin by using (Ng, Harada, and Russell 1999) to connect to the results
of (Adamczyk et al. 2023a) and (Cao, Cohen, and Szpruch 2021). In un-
regularized RL (Adamczyk et al. 2023a) Theorem 1 holds,

######  Theorem 6.1a (Ng, Harada, and Russell).

Let a (standard RL) primitive task $\mathcal{T}$ with reward function $r$ be
given, with the optimal value function $V^{*}(s)$. Consider another (standard
RL) task, $\widetilde{\mathcal{T}}$ with reward function $\widetilde{r}$, with
an unknown optimal action-value function, $\widetilde{Q}^{*}$. Define
$\kappa(s,a)\doteq\widetilde{r}(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}}V^{*}(s^{\prime})-V^{*}(s)$.
Denote the optimal action-value function $K^{*}$ as the solution of the
following Bellman optimality equation

$K^{*}(s,a)=\kappa(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}\max_{a^{\prime}}K^{*}(s^{\prime},a^{\prime})$
(38)

Then,

$\widetilde{Q}^{*}(s,a)=V^{*}(s)+K^{*}(s,a)$ (39)

###### Proof.

Since $\kappa(s,a)$ is simply the reward function $\widetilde{r}(s,a)$ shaped
by the potential function $V^{*}(s)$, this is simply a re-writing of Eq. (3)
in (Ng, Harada, and Russell 1999). ∎

Now we provide a lemma before proving a similar result for compositions.
Motivated by (Cao, Cohen, and Szpruch 2021)’s Theorem 1, we provide the same
result for standard (un-regularized) RL:

######  Lemma 4.8a.

Let $Q(s,a)$ be given. Define $V^{*}(s)=\max_{a}Q(s,a)$ as the corresponding
state value functions for a un-regularized RL task. Then

$R(s,a)=Q(s,a)-\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}V^{*}(s^{\prime})$
(40)

is the reward function for a task with optimal action-value function
$Q^{*}(s,a)=Q(s,a)$.

###### Proof.

The proof is trivial, given by rearrangement of the Bellman optimality
equation. ∎

######  Theorem 4.8.

Given a set of primitive tasks $\\{\mathcal{T}_{j}\\}$ with corresponding
optimal value functions $\\{Q_{j}^{*}\\}$, denote $\widetilde{Q}^{*}$ as the
optimal value function for the composition of $\\{\mathcal{T}_{j}\\}$ under
the composition function $f:\mathbb{R}^{M}\to\mathbb{R}$.

Define $K^{*}$ as the optimal value function for a task with reward function
$\kappa$ defined by:

$\displaystyle\kappa(s,a)=f(\\{r_{j}(s,a)\\})+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}}V_{f}(s^{\prime})-V_{f}(s)$
$V_{f}(s)=\max_{a}f\left(\\{Q_{j}^{*}(s,a)\\}\right)$

Then, the optimal value functions $\widetilde{Q}^{*}$ and $K^{*}$ are related
by:

$\widetilde{Q}^{*}(s,a)=V_{f}(s)+K^{*}(s,a)$ (41)

###### Proof.

Let $f\left(\\{Q_{j}^{*}(s,a)\\}\right)$ stand for the primitive task’s
solution, as in Theorem 39. Then, by Lemma 40, such a value function is
optimal for a un-regularized RL task with reward function
$R(s,a)=f\left(\\{Q_{j}^{*}(s,a)\\}\right)-\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}V_{f}^{*}(s^{\prime})$,
where $V_{f}(s)=\max_{a}f\left(\\{Q_{j}^{*}(s,a)\\}\right)$. By Theorem 39,
the corrective task has a reward function

$\kappa(s,a)=f\left(\\{r_{j}(s,a)\\}\right)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}}V_{f}(s^{\prime})-V_{f}(s)$
(42)

with corresponding optimal value function $K^{*}(s,a)$, related to
$\widetilde{Q}^{*}(s,a)$ by

$\widetilde{Q}^{*}(s,a)=V_{f}(s)+K^{*}(s,a)$ (43)

Again, this result can be seen as (Ng, Harada, and Russell 1999)’s reward
shaping with a potential function $\Phi(s)=V_{f}(s)$. ∎

We now note that Lemma A applies to the cases of Theorem 39 and 41, which
results in double-sided bounds given any estimate of the state value function
$V(s)$:

######  Theorem 4.9.

Consider a (standard RL) task with reward function $r(s,a)$ and (unknown)
optimal value function $Q^{*}(s,a)$. Let an estimate for the state value
function be given as $V(s)$.

The optimal value function $Q^{*}(s,a)$ is then bounded by:

$\displaystyle Q^{*}(s,a)$ $\displaystyle\geq
r(s,a)+\gamma\left(\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}V(s^{\prime})+\frac{\inf\Delta}{1-\gamma}\right)$
(44) $\displaystyle Q^{*}(s,a)$ $\displaystyle\leq
r(s,a)+\gamma\left(\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}V(s^{\prime})+\frac{\sup\Delta}{1-\gamma}\right)$
(45)

where

$\Delta(s,a)\doteq
r(s,a)+\gamma\operatorname*{\mathbb{E}}_{s^{\prime}\sim{}p}V(s^{\prime})-V(s).$

In Eq. (45), the $\inf$ and $\sup$ are taken over the continuous state-action
space $\mathcal{S}\times\mathcal{A}$.

###### Proof.

The proof is identical to that of Theorem 4.1, except with the proper
replacement of $\Delta$. ∎

## Exact composition in entropy regularized RL

Here, we provide a new proof and extension of Theorem 2 in (Van Niekerk et al.
2019) to highlight that our results can provide new insight to exact
compositions in entropy-regularized RL.

To align with the assumptions of (Van Niekerk et al. 2019), we consider the
undiscounted, finite horizon setting with deterministic dynamics. We first
note the observation which forms the starting point of our analysis: the
difference between the true optimal value function ($Q^{*}(s,a)$),
corresponding to reward function $r(s,a)$, and any estimate of the value
function ($Q(s,a)$) can itself be represented as another optimal value
function, with the corresponding reward function given by (Adamczyk et al.
2023a):

$\Delta(s,a)\doteq r(s,a)+\gamma V(s^{\prime})-Q(s,a)$

It is straightforward to show that this observation remains valid in the
undiscounted ($\gamma=1$) setting as well. Now, if the estimate of the value
function is exact, we must have $\Delta(s,a)=0$. In the following, we
determine conditions which lead to $\Delta(s,a)=0$ and correspondingly to
exact compositions.

###### Proof.

We consider $M$ solved tasks with reward functions $\\{r_{1},\dotsc,r_{M}\\}$
varying only on the set of absorbing states ($s\in\mathcal{G}$). Let
$Q_{i}(s,a)$ denote the optimal value function for the $i^{\mathrm{th}}$ task.
Consider the composite task with the following reward structure:

  * •

For the absorbing states ($s\in\mathcal{G}$), the reward function is given by
the reward composition function $\widetilde{r}(s,a)=g(\\{r_{i}(s,a)\\})$.

  * •

For the interior states ($s\not\in\mathcal{G}$), the reward function is taken
to be the same as the solved tasks and will be denoted by $r(s,a)$.

For the composite task defined in this way, we wish to determine if the
corresponding optimal value function can be expressed exactly as some global
composition of the known value functions for the solved tasks, denoted by
$f(\\{Q_{i}(s,a)\\})$. In other words, the estimate of the optimal value
function is given by $f(\\{Q_{i}(s,a)\\})$, and we will show how a specific
form for $f$ corresponds to $\Delta(s,a)=0$ (exact composition).

In the following, we will first show that we must have $f=g$, i.e the value
composition function must be identical to the reward composition function for
the absorbing states. We will then determine a specific form of
$f(\\{Q(s,a)\\})$ such that the corresponding reward function (i.e.
$f(\\{Q(s,a)\\})-V_{f}(s^{\prime})$, by (Cao, Cohen, and Szpruch 2021)) is
equal to the reward function for the composite task ($\widetilde{r}(s,a)$),
thus yielding $\Delta(s,a)=0$. We will do so by deriving the soft back-up
equation for $f(\\{Q(s,a)\\})$ using the soft back-up equations for the
subtasks.

We begin by observing that, on the absorbing set $\mathcal{G}$, we have
$r(s,a)=Q(s,a)$ for all $s\in\mathcal{G}$, implying that
$\widetilde{Q}(s,a)=\widetilde{r}(s,a)=g(\\{r_{i}(s,a)\\})=g(\\{Q_{i}(s,a)\\})$.
Thus, for exact composition on the absorbing set $\mathcal{G}$, the value
composition function must be the same as the reward composition function (i.e
$f=g$), for any reward composition function $g$. Since we are interested in a
global value composition function, this means that the reward composition
function $g$ also determines the composition function $f(\\{Q(s,a)\\})$ for
states $s\not\in\mathcal{G}$. However, for arbitrary choices of $g$, the
corresponding $f(\\{Q(s,a)\\})$ will not, in general, correspond to the exact
optimal value function for states $s\not\in\mathcal{G}$.

We now consider a special class of reward composition functions $g$, such that
the corresponding value composition function $f$ is an exact composition
globally. Consider $g$ such that we have, for the absorbing states $s$,

$e^{\widetilde{r}(s,a)}=\sum_{i}w_{i}e^{r_{i}(s,a)}$ (46)

with weights $w_{i}>0$ and we have set $\tau=1$ for simplicity.

For deterministic dynamics, focusing on the non-absorbing states (i.e.
$s\not\in\mathcal{G}$ ) the soft backup equation for the subtask $m$ can be
expressed as

$e^{Q_{m}(s,a)}=e^{r_{m}(s,a)}e^{V_{m}(s^{\prime})}.$ (47)

Since the subtask reward functions are identical for those
$s\not\in\mathcal{G}$, this simplifies to

$e^{Q_{m}(s,a)}=e^{r(s,a)}e^{V_{m}(s^{\prime})}.$ (48)

Since the state space is made of disjoint absorbing and non-absorbing (i.e.
boundary and interior as in (Todorov 2009)), we can split to two cases as
$s,a$ which transition to $s^{\prime}\in\mathcal{G}$ and otherwise.

Now, consider the backup equation for each subtask, where we split those
states $s\not\in\mathcal{G}$ and $s\in\mathcal{G}$.

$\displaystyle e^{Q_{i}(s,a)}$ $\displaystyle=e^{r(s,a)}\times$
$\displaystyle\left(\sum_{s^{\prime}\in\mathcal{G}}p(s^{\prime}|s,a)e^{V_{i}(s^{\prime})}+\sum_{s^{\prime}\not\in\mathcal{G}}p(s^{\prime}|s,a)e^{V_{i}(s^{\prime})}\right)$

But for $s\in\mathcal{G}$, the state value function is simply
$V_{m}(s)=r_{m}(s)$. Thus we have

$\displaystyle e^{Q_{i}(s,a)}$ $\displaystyle=e^{r(s,a)}\times$ (49)
$\displaystyle\left(\sum_{s^{\prime}\in\mathcal{G}}p(s^{\prime}|s,a)e^{r_{i}(s^{\prime})}+\sum_{s^{\prime}\not\in\mathcal{G}}p(s^{\prime}|s,a)e^{V_{i}(s^{\prime})}\right)$

Now, since we have $f=g$, the optimal value composition function is given by

$e^{f(\\{Q_{i}(s,a)\\})}=\sum_{i}w_{i}e^{Q_{i}(s,a)}$ (50)

Multiplying each of the subtask backup equations (above) by the respective
weight ($w_{i}$) and summing up we obtain

$\displaystyle e^{f(\\{Q_{i}(s,a)\\})}=e^{r(s,a)}\times$
$\displaystyle\sum_{i}w_{i}\biggl{(}\sum_{s^{\prime}\in\mathcal{G}}p(s^{\prime}|s,a)e^{r_{i}(s^{\prime})}+\sum_{s^{\prime}\not\in\mathcal{G}}p(s^{\prime}|s,a)e^{V_{i}(s^{\prime})}\biggr{)}.$

Now we observe that for $f$ as defined above, the soft state-value function
$V_{f}(s)$ derived from $f(Q)$ satisfies:

$\displaystyle e^{V_{f}(s)}$
$\displaystyle=\operatorname*{\mathbb{E}}_{a^{\prime}\sim{}\pi_{0}}~{}e^{f(\\{Q_{i}(s^{\prime},a^{\prime})\\})}$
$\displaystyle=\operatorname*{\mathbb{E}}_{a^{\prime}\sim{}\pi_{0}}\sum_{i}w_{i}~{}e^{Q_{i}(s^{\prime},a^{\prime})}$
$\displaystyle=\sum_{i}w_{i}~{}\operatorname*{\mathbb{E}}_{a^{\prime}\sim{}\pi_{0}}~{}e^{Q_{i}(s^{\prime},a^{\prime})}$
$\displaystyle=\sum_{i}w_{i}~{}e^{V_{i}(s^{\prime})}$

Using the above, we obtain

$\displaystyle e^{f(\\{Q_{i}(s,a)\\})}=e^{r(s,a)}\times$
$\displaystyle\left(\sum_{s^{\prime}\in\mathcal{G}}p(s^{\prime}|s,a)e^{\widetilde{r}(s,a)}+\sum_{s^{\prime}\not\in\mathcal{G}}p(s^{\prime}|s,a)e^{V_{f}(s^{\prime})}\right)$

Comparing the above equation with the backup equation for the subtask Eq.
(49), we obtain that $f(\\{Q_{i}(s,a)\\})$ (defined in Eq. (50)) is the exact
optimal value function for the composite task with reward function
$\widetilde{r}(s,a)$ for the absorbing states ($s\in\mathcal{G}$) and $r(s,a)$
for the non-absorbing states ($s\not\in\mathcal{G}$). The result stated in the
main text (Theorem 5.1) follows, given that
$\widetilde{Q}(s,a)=f(\\{Q_{i}(s,a)\\})$. ∎

## References

  * Adamczyk et al. (2023a) Adamczyk, J.; Arriojas, A.; Tiomkin, S.; and Kulkarni, R. V. 2023a.  Utilizing Prior Solutions for Reward Shaping and Composition in Entropy-Regularized Reinforcement Learning.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 37(6): 6658–6665.
  * Adamczyk et al. (2023b) Adamczyk, J.; Makarenko, V.; Arriojas, A.; Tiomkin, S.; and Kulkarni, R. V. 2023b.  Bounding the optimal value function in compositional reinforcement learning.  In Evans, R. J.; and Shpitser, I., eds., _Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence_ , volume 216 of _Proceedings of Machine Learning Research_ , 22–32. PMLR.
  * Brockman et al. (2016) Brockman, G.; Cheung, V.; Pettersson, L.; Schneider, J.; Schulman, J.; Tang, J.; and Zaremba, W. 2016.  Openai gym.  _arXiv preprint arXiv:1606.01540_.
  * Cao, Cohen, and Szpruch (2021) Cao, H.; Cohen, S.; and Szpruch, Ł. 2021.  Identifiability in inverse reinforcement learning.  _Advances in Neural Information Processing Systems_ , 34: 12362–12373.
  * Degrave et al. (2022) Degrave, J.; Felici, F.; Buchli, J.; Neunert, M.; Tracey, B.; Carpanese, F.; Ewalds, T.; Hafner, R.; Abdolmaleki, A.; de Las Casas, D.; et al. 2022.  Magnetic control of tokamak plasmas through deep reinforcement learning.  _Nature_ , 602(7897): 414–419.
  * Eysenbach et al. (2019) Eysenbach, B.; Gupta, A.; Ibarz, J.; and Levine, S. 2019.  Diversity is all you need: Learning skills without a reward function.  _International Conference on Learning Representations_.
  * Eysenbach and Levine (2022) Eysenbach, B.; and Levine, S. 2022.  Maximum Entropy RL (Provably) Solves Some Robust RL Problems.  In _International Conference on Learning Representations_.
  * Fazlyab et al. (2019) Fazlyab, M.; Robey, A.; Hassani, H.; Morari, M.; and Pappas, G. 2019.  Efficient and accurate estimation of lipschitz constants for deep neural networks.  _Advances in Neural Information Processing Systems_ , 32.
  * Haarnoja et al. (2018a) Haarnoja, T.; Pong, V.; Zhou, A.; Dalal, M.; Abbeel, P.; and Levine, S. 2018a.  Composable deep reinforcement learning for robotic manipulation.  In _2018 IEEE international conference on robotics and automation (ICRA)_ , 6244–6251. IEEE.
  * Haarnoja et al. (2018b) Haarnoja, T.; Zhou, A.; Abbeel, P.; and Levine, S. 2018b.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  In _International conference on machine learning_ , 1861–1870. PMLR.
  * Kim, Park, and Kim (2022) Kim, J.; Park, S.; and Kim, G. 2022.  Constrained GPI for Zero-Shot Transfer in Reinforcement Learning.  In Koyejo, S.; Mohamed, S.; Agarwal, A.; Belgrave, D.; Cho, K.; and Oh, A., eds., _Advances in Neural Information Processing Systems_ , volume 35, 4585–4597. Curran Associates, Inc.
  * Lee et al. (2021) Lee, K.; Laskin, M.; Srinivas, A.; and Abbeel, P. 2021.  Sunrise: A simple unified framework for ensemble learning in deep reinforcement learning.  In _International Conference on Machine Learning_ , 6131–6141. PMLR.
  * Nemecek and Parr (2021) Nemecek, M.; and Parr, R. 2021.  Policy caches with successor features.  In _International Conference on Machine Learning_ , 8025–8033. PMLR.
  * Ng, Harada, and Russell (1999) Ng, A. Y.; Harada, D.; and Russell, S. 1999.  Policy invariance under reward transformations: Theory and application to reward shaping.  In _Proceedings of the 16th International Conference on Machine Learning_ , volume 99, 278–287.
  * Park et al. (2023) Park, S.; Lee, K.; Lee, Y.; and Abbeel, P. 2023.  Controllability-Aware Unsupervised Skill Discovery.  arXiv:2302.05103.
  * Rachelson and Lagoudakis (2010) Rachelson, E.; and Lagoudakis, M. G. 2010.  On the Locality of Action Domination in Sequential Decision Making.  In _11th International Symposium on Artificial Intelligence and Mathematics (ISIAM 2010)_ , 1–8. Fort Lauderdale, US.
  * Raffin et al. (2021) Raffin, A.; Hill, A.; Gleave, A.; Kanervisto, A.; Ernestus, M.; and Dormann, N. 2021\.  Stable-Baselines3: Reliable Reinforcement Learning Implementations.  _Journal of Machine Learning Research_ , 22(268): 1–8.
  * Rusu et al. (2016) Rusu, A. A.; Rabinowitz, N. C.; Desjardins, G.; Soyer, H.; Kirkpatrick, J.; Kavukcuoglu, K.; Pascanu, R.; and Hadsell, R. 2016.  Progressive neural networks.  _arXiv preprint arXiv:1606.04671_.
  * Schrittwieser et al. (2020) Schrittwieser, J.; Antonoglou, I.; Hubert, T.; Simonyan, K.; Sifre, L.; Schmitt, S.; Guez, A.; Lockhart, E.; Hassabis, D.; Graepel, T.; et al. 2020.  Mastering atari, go, chess and shogi by planning with a learned model.  _Nature_ , 588(7839): 604–609.
  * Silver et al. (2018) Silver, D.; Hubert, T.; Schrittwieser, J.; Antonoglou, I.; Lai, M.; Guez, A.; Lanctot, M.; Sifre, L.; Kumaran, D.; Graepel, T.; Lillicrap, T.; Simonyan, K.; and Hassabis, D. 2018.  A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play.  _Science_ , 362(6419): 1140–1144.
  * Sutton and Barto (2018) Sutton, R. S.; and Barto, A. G. 2018.  _Reinforcement learning: An introduction_.  MIT press.
  * Tasse, James, and Rosman (2020) Tasse, G. N.; James, S.; and Rosman, B. 2020.  A Boolean task algebra for reinforcement learning.  _Advances in Neural Information Processing Systems_ , 33: 9497–9507.
  * Tasse, James, and Rosman (2021) Tasse, G. N.; James, S.; and Rosman, B. 2021.  Generalisation in Lifelong Reinforcement Learning through Logical Composition.  In _Deep RL Workshop NeurIPS 2021_.
  * Todorov (2009) Todorov, E. 2009.  Compositionality of optimal control laws.  _Advances in neural information processing systems_.
  * Van Niekerk et al. (2019) Van Niekerk, B.; James, S.; Earle, A.; and Rosman, B. 2019.  Composing value functions in reinforcement learning.  In _International conference on machine learning_ , 6401–6409. PMLR.
  * Vinyals et al. (2019) Vinyals, O.; Babuschkin, I.; Czarnecki, W. M.; Mathieu, M.; Dudzik, A.; Chung, J.; Choi, D. H.; Powell, R.; Ewalds, T.; Georgiev, P.; et al. 2019.  Grandmaster level in StarCraft II using multi-agent reinforcement learning.  _Nature_ , 575(7782): 350–354.
  * Ziebart (2010) Ziebart, B. D. 2010.  _Modeling purposeful adaptive behavior with the principle of maximum causal entropy_.  PhD Dissertation, Carnegie Mellon University.