# A Counterexample and a Corrective to the Vector Extension of the Bellman
Equations of a Markov Decision Process

Anas Mifrani

###### Abstract.

Under the expected total reward criterion, the optimal value of a finite-
horizon Markov decision process can be determined by solving the Bellman
equations. The equations were extended by D. J. White to processes with vector
rewards in 1982. Using a counterexample, we show that the assumptions
underlying this extension fail to guarantee its validity. Analysis of the
counterexample leads us to articulate a sufficient condition for White’s
functional equations to be valid. The condition is shown to be true when the
policy space has been refined to include a special class of non-Markovian
policies, or when the dynamics of the model are deterministic, or when the
decision making horizon does not exceed three time steps. The paper
demonstrates that, in general, the solutions to White’s equations are sets of
Pareto efficient policy returns over the refined policy space. Our results are
illustrated with an example.

††footnotetext: *: Toulouse Mathematics Institute, University of Toulouse, 118
Rte de Narbonne, Toulouse, France††footnotetext: Email address:
<EMAIL_ADDRESS>ORCID: 0009-0005-1373-9028

Keywords: Vector-valued Markov decision processes; Dynamic programming; Multi-
objective optimization; Optimality equations; Pareto fronts.

##  1\. Introduction

In a seminal paper on vector-valued Markov decision processes, Douglas J.
White (White, 1982, J. Math. Anal. Appl. 89(2)) presents an inductive scheme
for determining the Pareto efficient set of policy returns from any period $t$
onward given any initial state $s_{t}$. The scheme is intended as a
generalization of the value iteration algorithm (Puterman, 2014) for scalar
Markov decision processes, and is based accordingly on equations reminiscent
of Bellman’s, though the unknowns in White’s case are set-valued rather than
real-valued functions. There is abundant reference to White’s equations in the
technical literature (Wiering De Jong, 2007; Hayes ., 2022; Mannor Shimkin,
2004; Roijers ., 2021; Van Moffaert Nowé, 2014; Ruiz-Montiel ., 2017), and
their continuing relevance is evidenced by the recent publication of a paper
(Mandow ., 2022) which uses them explicitly as the basis for a novel multi-
objective dynamic programming algorithm. Unfortunately, however, the equations
are invalid under White’s own assumptions. By means of a counterexample, we
shall demonstrate that their solution does not yield the desired efficient
sets, contrary to White’s chief claim (see Theorem 2 (White, 1982), reproduced
below). We shall also see that the proof of this “theorem” 1††1 Throughout
this paper, the use of scare quotes around the word “theorem” indicates that
the word is not accurate, since theorems are true statements by definition.
(White, 1982, p. 7) relies critically on a rather intuitive, but in fact
erroneous, argument.

It is also the purpose of this paper to develop conditions in which the
equations are applicable. In particular, it shall be shown that the equations
hold when the decision making horizon spans two or three time steps (Section
3), or when the dynamics of the model are deterministic (Section 4), or when
the policy space is augmented with a class of non-Markovian policies (Section
5). By analyzing the latter case, we discover that the actual solutions to
White’s equations are Pareto efficient sets of policy returns over the
augmented policy space (Theorem 5, Sec. 5). To our knowledge, this paper
carries the first such analysis, and is the first to disprove the said
“theorem”.

To make for a relatively self-contained paper, we shall restate White’s
assumptions (White, 1982), changing the notation slightly. Let $S$ be a finite
set of states. For each state $s\in S$, let $A_{s}$ be the set of actions that
can be taken in state $s$; suppose $A_{s}$ is compact, and let $A=\cup_{s\in
S}A_{s}$. A decision maker observes the process over $N$ epochs, $N\geq 2$. At
each $t=1,...,N$, they receive a vector reward $R_{t}(s,a)\in\mathbb{R}^{m}$,
$m\geq 1$, for selecting action $a$ in state $s$; suppose that reward
components are continuous on $A_{s}$ for all $s\in S$. Call $p_{t}(j|s,a)$ the
probability that the system will occupy state $j$ at epoch $t+1$ given that
action $a$ was selected in $s$ at epoch $t$; suppose it is continuous on
$A_{s}$. A Markovian decision rule $d_{t}\in F(S,A)$ dictates the action that
should be taken in each state at epoch $t$. The set of decision rules, $D$, is
assumed to be compact. No decision is taken at epoch $N$, but a terminal
state-dependent reward $R_{N}(s)$ is generated. A policy specifies the
decision rule that should be used at each epoch, and will be identified with
its corresponding sequence of decision rules $(d_{1},...,d_{N-1})$. Let
$P_{W}$ denote the set of all policies.

For any policy $\pi=(d_{1},...,d_{N-1})\in P_{W}$ and any $t<N$, let

$u_{t}^{\pi}(s)=\mathbb{E}_{\pi}^{s}[\sum_{i=t}^{N-1}R_{i}(X_{i},d_{i}(X_{i}))+R_{N}(X_{N})]$
(1)

be the expected total reward for using $\pi$ at epochs $t,t+1,...,N-1$ if the
state at epoch $t$ is $s\in S$, where $X_{i}$ denotes the (random) state at
epoch $i$. Since $X_{t}=s$, it follows from basic probability operations that

$u_{t}^{\pi}(s)=R_{t}(s,d_{t}(s))+\sum_{j\in
S}p_{t}(j|s,d_{t}(s))u_{t+1}^{\pi}(j)$ (2)

where, in a way consistent with the definition above,

$u_{N}^{\pi}(s)=R_{N}(s)$ (3)

For $t\leq N$, $s\in S$, write $V_{t}(s)=\bigcup_{\pi\in
P_{W}}\\{u_{t}^{\pi}(s)\\}$. The broad expression “policy return”, where time
and state are omitted for brevity, shall refer to any member of $V_{t}(s)$ for
some $t\leq N$ and $s\in S$.

Define the (Pareto) efficient subset of any set $X\subseteq\mathbb{R}^{m}$ as

$e(X)=\\{\,x\in X\mid\forall y\in X,\,y\geq x\implies y=x\,\\}$ (4)

where $\geq$ denotes the componentwise order on $\mathbb{R}^{m}$, i.e $x\geq
y\iff\forall i\in\llbracket 1,m\rrbracket,\,x_{i}\geq y_{i}$ for all
$x,y\in\mathbb{R}^{m}$. Elements of $e(X)$ are called efficient, or Pareto
optimal, or admissible, or – in set-theoretic language – maximal (Geoffrion,
1968).

With this as a background, the “theorem” states

######  Theorem.

(White, 1982) For all $t\leq N$ and $s\in S$, $e(V_{t}(s))$ is the unique
solution $U_{t}(s)$ to either of the following equations:

$U_{t}(s)=e\Biggl{(}\bigcup_{a\in
A_{s}}\biggl{(}\\{R_{t}(s,a)\\}\bigoplus\sum_{j\in
S}p_{t}(j|s,a)U_{t+1}(j)\biggr{)}\Biggr{)};\begin{array}[]{l}t<N\\\
\end{array}$ (5) $U_{t}(s)=\\{R_{N}(s)\\};\begin{array}[]{l}t=N\\\
\end{array}$ (6)

where for any nonempty sets $A$ and $B$, $A\bigoplus B=\\{\,a+b\mid a\in
A,b\in B\,\\}$.

When $m=1$, (4) and (5) reduce to the Bellman equations referred to earlier,
and the “theorem” reduces to the correct claim that $\max_{\pi\in
P_{W}}u_{t}^{\pi}(s)$, which exists under the aforementioned assumptions
(Puterman, 2014, Proposition 4.4.3.), is the unique solution for all $t\leq N$
and $s\in S$. When $m>1$, the “theorem” no longer holds, as the next section
shows.

##  2\. A Counterexample

Consider the stationary vector-valued Markov decision process defined by
$N=4;\,S=\\{s_{1},s_{2}\\};\,A_{s_{1}}=A_{s_{2}}=A=\\{a_{1},a_{2}\\};\,p_{t}(s_{1}|s_{1},a_{1})=\frac{3}{4};\,p_{t}(s_{1}|s_{1},a_{2})=p_{t}(s_{1}|s_{2},a_{1})=p_{t}(s_{1}|s_{2},a_{2})=\frac{1}{2};\,R_{t}(s_{1},a_{1})=(11,-5);\,R_{t}(s_{1},a_{2})=(9,5);\,R_{t}(s_{2},a_{1})=(5,5);\,R_{t}(s_{2},a_{2})=(5,-10);\,R_{N}(s_{1})=(1,0);\,R_{N}(s_{2})=(0,1)$.

There are four decision rules in this model, namely the one that prescribes
$a_{1}$ in $s_{1}$ and $a_{2}$ in $s_{2}$, the one that prescribes $a_{2}$ in
$s_{1}$ and $a_{1}$ in $s_{2}$, and the two that prescribe the same action in
both states. This gives rise to a total of $4^{N-1}=64$ policies. A full
search of $V_{1}(s_{1})$ based on (1) and (2) yielded

$e(V_{1}(s_{1}))=\\{(26.5,5.5),(23.5,15.5),(28.7,-2.0),(25.0,10.5),(27.6,0.4),(30.3,-9.0)\\}$
(7)

whereas successive evaluation of (4) and (5) for all $t\leq N$ produced, at
$t=1$ and $s=s_{1}$,

$U_{1}(s_{1})=\\{(30.3,-9.0),(30.0,-7.8),(29.0,-3.3),(28.7,-2),(27.6,0.4),(27.3,1.6),(26.8,4.2),\\\
(26.5,5.5),(25.8,6.6),(25.6,7.9),(25.0,10.5),(24.1,12.9),(23.5,15.5)\\}$ (8)

Clearly, $U_{1}(s_{1})\neq e(V_{1}(s_{1}))$. This concludes the
counterexample.

The problem is that for any $t<N$ and $s\in S$, $U_{t}(s)$ may contain
infeasible vectors, that is, total rewards that are unattainable for all
policies over the period spanning $t,t+1,...,N$ given initial state $s$. Put
differently, for some $w\in U_{t}(s)$, we may have $w\notin V_{t}(s)$. Indeed,
in the example above, $(30.0,-7.8)\in U_{1}(s_{1})$, yet a full search
revealed no policy $\pi$ such that $u_{1}^{\pi}(s_{1})=(30.0,-7.8)$. If
$U_{t}(s)\not\subseteq V_{t}(s)$, one obviously cannot have
$U_{t}(s)=e(V_{t}(s))$, and the “theorem” fails.

At the root of the problem is the possibility that, for some $s\in S$ and
$t<N$,

$F_{t}(s):=\bigcup_{a\in A_{s}}\biggl{(}\\{R_{t}(s,a)\\}\bigoplus\sum_{j\in
S}p_{t}(j|s,a)U_{t+1}(j)\biggr{)}\not\subseteq V_{t}(s)$ (9)

On the page of (White, 1982) devoted to proving the “theorem”, page 7, we find
that Professor White, proceeding on the induction hypothesis that
$U_{t+1}(j)=e(V_{t+1}(j))$ for all $j\in S$, for some $t<N$, merely asserts
that if $w=R_{t}(s,a)+\sum_{j\in S}p_{t}(j|s,a)v_{j}\in F_{t}(s)$, with
$v_{j}\in U_{t+1}(j)$, $a\in A_{s}$, we must have $w\in V_{t}(s)$. This, of
course, need not be true, as we have just illustrated with our counterexample
with $w=(30.0,-7.8)$.

It is therefore important to inquire into the following property, which we
call (P):

$\forall s\in S,\ \forall t<N,\ F_{t}(s)\subseteq V_{t}(s)$ (10)

Property (P) not only ensures $U_{t}(s)\subseteq V_{t}(s)$, but also that
White’s equations are valid, i.e $U_{t}(s)=e(V_{t}(s))$ for all $s\in S$ and
$t\leq N$. Because the demonstration of this fact is quite lengthy, we defer
it to the next section.

It should be emphasized from the outset that (P) can only be violated when
$m>1$. Recall our earlier comment that when $m=1$, White’s equations coincide
with Bellman’s, since

$e(F_{t}(s))=\\{\max(F_{t}(s))\\}$ (11)

for all $t<N$ and $s\in S$, so that we may write
$U_{t}(s)=\\{u_{t}(s)\\}\subseteq\mathbb{R}$ for all $s\in S$ and $t\leq N$,
where

$u_{t}(s)=\max_{a\in A_{s}}\ [R_{t}(s,a)+\sum_{j\in S}p_{t}(j|s,a)u_{t+1}(j)]$
(12)

for all $s\in S$ if $t<N$, and

$u_{N}(s)=R_{N}(s)$ (13)

for all $s\in S$. In fact, for each $s\in S$, $t<N$ and $a\in A_{s}$, one can
demonstrate the existence of a policy $\pi(s,a,t)\in P_{W}$ such that

$R_{t}(s,a)+\sum_{j\in S}p_{t}(j|s,a)u_{t+1}(j)=u_{t}^{\pi(s,a,t)}(s),$ (14)

thus ensuring $F_{t}(s)\subseteq V_{t}(s)$ and therefore (P). Such a
$\pi(s,a,t)$ can be constructed in two steps. First, construct a policy
$\pi^{*}=(d_{1}^{*},...,d_{N-1}^{*})\in P_{W}$ as follows: for each $t<N$,
starting at $t=N-1$ then decreasing $t$, evaluate Equation (12) for each $s\in
S$, then choose a maximizing action $a^{*}\in A_{s}$ and let
$d_{t}^{*}(s)=a^{*}$. This policy satisfies $u_{t}(s)=u_{t}^{\pi}(s)$ for all
$s\in S$ and $t\leq N$. Second, for each $s\in S$, $t<N$ and $a\in A_{s}$,
choose $\pi(s,a,t)$ to be any policy that prescribes $a$ in $s$ at time $t$
and uses $\pi^{*}$ from $t+1$ onward, i.e any policy $(d_{1},...,d_{N-1})$ of
the form

$d_{t}(s)=a;\ d_{k}(j)=d_{k}^{*}(j),\forall k\in\llbracket
t+1,N-1\rrbracket,\,\forall j\in S\,$ (15)

Clearly, for any such policy, we have
$u_{t}^{\pi(s,a,t)}(s)=R_{t}(s,a)+\sum_{j\in S}p_{t}(j|s,a)u_{t+1}(j)$, hence
property (P), hence the validity of the Bellman equations.

We have demonstrated, then, that (P) is a property of scalar Markov decision
processes, whereas it need not be a property of vector-valued Markov decision
processes with $m>1$. In the sequel, we shall develop two overlapping classes
of models which possess (P) as their property. These are:

  1. (1)

Deterministic dynamic programs, i.e vector-valued Markov decision processes
where actions, conditional on the present state, determine the next state with
certainty.

  2. (2)

Vector-valued Markov decision processes where the definition of “decision
rule” has been refined to include a broader range of rules than that
considered by White.

Before treating these cases (Sections 4 and 5, respectively), we shall first
justify our claim that (P) is sufficient to ensure the validity of the White
equations (Section 3). We shall adopt the same method of proof as White on
page 7 of (White, 1982), namely induction on $t$ and appeal to a lemma that
will be introduced in due course. Note that since we shall be dealing with a
different notion of policy in our treatment of the second case, (P) shall have
to be recast accordingly, though this is a minor change, and the property’s
tenor as well as implication for the White equations shall remain the same.
All assumptions made in the succeeding sections supplement those set forth in
the Introduction, unless it is stated explicitly that a new assumption repeals
an old one. Finally, it should by now be clear that in carrying out this
investigation, we have an $m>1$ in mind, though all the results presented in
the following also hold when $m=1$.

##  3\. On (P) as a Sufficient Condition for the Validity of the White
Equations

As a prelude to showing that (P) implies $U_{t}(s)=e(V_{t}(s))$ for all $s\in
S$ and $t\leq N$, where $U_{t}(s)$ is given by Equations (4) and (5), we
borrow the following lemma from White (1982):

######  Lemma 1.

(White, 1982, Lemma 2) Let $t=1,...,N$ and $s\in S$. For each $u\in V_{t}(s)$,
there is a $v\in e(V_{t}(s))$ such that $v\geq u$.

This lemma generalizes the fact that for a partially ordered set $(X,\succeq)$
that admits a maximum, we have $\max(X)\succeq x$ for all $x\in X$. Actually,
if $V_{t}(s)$ does admit a maximum, such as is the case when $m=1$, the lemma
says precisely that $\max(V_{t}(s))\geq u$ for all $u\in V_{t}(s)$. An
equivalent statement is “for all $t\leq N$, $s\in S$, $e(V_{t}(s))$ is the
kernel of $V_{t}(s)$ with respect to $\geq$”, where “kernel” is the decision-
theoretic term for the unique antichain2††2 An antichain is a subset of a
partially ordered set in which no elements are comparable. Formally,
$K\subseteq(X,\succeq)$ is an antichain in $X$ if for all $x,y\in K$,
$x\not\succeq y$ and $y\not\succeq x$. $K$ in a partially ordered set
$(X,\succeq)$ with the property that for all $x\in X$, there exists $y\in K$
with $y\succeq x$ (White, 1977).

The next lemma will also be useful in proving our result. Because it can be
inferred directly from the definition of $\geq$, we state it without proof:

######  Lemma 2.

Let $p_{1},...,p_{n}$ be $n\geq 1$ nonnegative reals and
$x_{1},...,x_{n},y_{1},...,y_{n}\in\mathbb{R}^{m}$. Let $x,y,z$ be any vectors
in $\mathbb{R}^{m}$. Then

  1. (1)

If $x_{i}\geq y_{i}$ for all $i=1,...,n$, we have
$\sum_{i=1}^{n}p_{i}x_{i}\geq\sum_{i=1}^{n}p_{i}y_{i}$;

  2. (2)

$x\geq y$ implies $z+x\geq z+y$.

We may now state our result.

######  Proposition 1.

(P) implies $U_{t}(s)=e(V_{t}(s))$ for all $s\in S$ and $t\leq N$.

Proof.  Suppose (P) is true. Proceed by induction on $t$. For $t=N$, we have,
independently of (P), $V_{N}(s)=\\{R_{N}(s)\\}=U_{N}(s)$, and thus
$U_{N}(s)=e(V_{N}(s))$ for all $s\in S$. Suppose $U_{t+1}(s)=e(V_{t+1}(s))$
for all $s\in S$, for some $t<N$.

Let $s\in S$ and $v\in e(V_{t}(s))$. We shall prove that $v\in U_{t}(s)$.
Since $v\in V_{t}(s)$, there exists a policy $\pi=(d_{1},...,d_{N-1})$ such
that $v=R_{t}(s,d_{t}(s))+\sum_{j\in S}p_{t}(j|s,d_{t}(s))u_{t+1}^{\pi}(j)$.
By Lemma 1, there is, for all $j\in S$, a policy $\pi_{j}$ such that
$u_{t+1}^{\pi_{j}}(j)\geq u_{t+1}^{\pi}(j)$ and $u_{t+1}^{\pi_{j}}(j)\in
e(V_{t+1}(j))$. Let $w=R_{t}(s,d_{t}(s))+\sum_{j\in
S}p_{t}(j|s,d_{t}(s))u_{t+1}^{\pi_{j}}(j)$. By the induction hypothesis,
$u_{t+1}^{\pi_{j}}(j)\in U_{t+1}(j)$ for all $j\in S$, hence $w\in F_{t}(s)$.
Furthermore, $w\geq v$ by Lemma 2, and $w\in V_{t}(s)$ by (P). But $v\in
e(V_{t}(s))$, thus $v=w$. Therefore, $v\in F_{t}(s)$. Ergo, because $v\in
e(V_{t}(s))$ and $F_{t}(s)\subseteq V_{t}(s)$ (P), we have $v\in
e(F_{t}(s))=U_{t}(s)$. This proves that $e(V_{t}(s))\subseteq U_{t}(s)$.

To show the converse inclusion, let $u\in U_{t}(s)$. We may write
$u=R_{t}(s,a)+\sum_{j\in S}p_{t}(j|s,a)v_{j}$ for some $a\in A$ and $v_{j}\in
U_{t+1}(j)$ for all $j\in S$. From (P), $u\in V_{t}(s)$. Suppose that $u\notin
e(V_{t}(s))$. Then there exists, applying Lemma 1, $v\in e(V_{t}(s))\subseteq
U_{t}(s)$ such that $v\geq u$ and $v\neq u$. This contradicts the fact that
$u\in U_{t}(s)$, and shows that $u\in e(V_{t}(s))$. Consequently,
$U_{t}(s)\subseteq e(V_{t}(s))$.

Because $s$ is arbitrary, we have established $U_{t}(s)=e(V_{t}(s))$ for any
$s\in S$ and $t=1,...,N$. $\Box$

Before examining the case of deterministic dynamic programs, we argue that (P)
is necessarily true when $N=2$ or $3$.

######  Proposition 2.

Suppose $N=2$ or 3. Then (P) is true.

Proof.  Suppose $N=2$. For $t=1$, we have that for all $s\in S$, for each
$v\in F_{1}(s)$, $v=R_{1}(s,a)+\sum_{j\in S}p_{1}(j|s,a)R_{2}(j)$ for some
$a\in A_{s}$. Thus $v=u_{1}^{\pi}(s)\in V_{1}(s)$ for any policy $\pi\in
P_{W}$ that uses $a$ in $s$ at time 1. Therefore, (P) is true.

Suppose $N=3$. For $t=2$, we have that for all $s\in S$, for each $v\in
F_{2}(s)$, $v=R_{2}(s,a)+\sum_{j\in S}p_{2}(j|s,a)R_{3}(j)$ for some $a\in
A_{s}$. Thus $v=u_{2}^{\pi}(s)$ for any policy $\pi\in P_{W}$ that prescribes
$a$ in $s$ at time 2. For this reason $F_{2}(s)\subseteq V_{2}(s)$, and
therefore $e(F_{2}(s))=U_{2}(s)\subseteq V_{2}(s)$, for all $s\in S$.

For $t=1$, for each $s\in S$ and $v\in F_{1}(s)$, there exists an $a\in A_{s}$
such that $v=R_{1}(s,a)+\sum_{j\in S}p_{1}(j|s,a)v_{j}$ for some $v_{j}\in
U_{2}(j)\subseteq V_{2}(j)$ for all $j\in S$. For each $j\in S$, there exists
a policy $\pi_{j}\in P_{W}$ such that $v_{j}=u_{2}^{\pi_{j}}(j)$. Then
$v=R_{1}(s,a)+\sum_{j\in S}p_{1}(j|s,a)u_{2}^{\pi_{j}}(j)=u_{1}^{\pi}(s)$ for
any policy $\pi\in P_{W}$ which prescribes $a$ in $s$ at time 1, then uses
$\pi_{j}$ if the state at time 2 is $j$. Thus $F_{1}(s)\subseteq V_{1}(s)$ for
all $s\in S$. $\Box$

We now know, by Proposition 2, that the White equations are valid when $N=2$
or $3$.

######  Corollary 1.

If $N=2$ or $3$, then $e(U_{t}(s))=V_{t}(s)$ for all $t\leq N$ and $s\in S$.

In what follows, we assume that $N>2$. This makes subsequent inductive proofs
less tedious by eliminating consideration of $N=2$.

##  4\. Deterministic Dynamic Programs

Having established that property (P) ensures the validity of the White
equations, we may now use it to show that these equations are applicable to
vector-valued Markov decision processes with deterministic dynamics. By
“deterministic dynamics” we mean specifically that

######  Assumption 1.

For each $s\in S$, $a\in A_{s}$ and $t=1,...,N-1$, there exists $s^{+}\in S$
such that $p_{t}(s^{+}|s,a)=1$.

We claim that (P) is true under Assumption 1.

######  Theorem 1.

Under Assumption 1, (P) is true, that is,

$\forall s\in S,\ \forall t<N,\ F_{t}(s)\subseteq V_{t}(s)$

Proof.  We proceed by induction on $t$. For $t=N-1$, for any $s\in S$ and
$a\in A_{s}$, by letting $f=R_{N-1}(s,a)+\sum_{j\in S}p_{N-1}(j|s,a)v_{j}$
where $v_{j}\in U_{N}(j)=\\{R_{N}(j)\\}$ for all $j\in S$, we have that
$f=R_{N-1}(s,a)+v_{s^{+}}=R_{N-1}(s,a)+R_{N}(s^{+})$ where $s^{+}\in S$ is the
state such that $p_{N-1}(s^{+}|s,a)=1$, and thus $f=u_{N-1}^{\pi}(s)$ for any
policy $\pi$ that prescribes $a$ for $s$ at time $N-1$. As a result,
$F_{N-1}(s)\subseteq V_{N-1}(s)$ for all $s\in S$.

Suppose that for all $s\in S$, $F_{t+1}(s)\subseteq V_{t+1}(s)$ for some
$t<N-1$. Let $s\in S$, and let $f=R_{t}(s,a)+\sum_{j\in S}p_{t}(j|s,a)v_{j}$
where $v_{j}\in U_{t+1}(j)=e(F_{t+1}(j))$ for all $j\in S$. By Assumption 1,
we may write $f=R_{t}(s,a)+v_{s^{+}}$, where $s^{+}\in S$ satisfies
$p_{t}(s^{+}|s,a)=1$. By the induction hypothesis, $v_{s^{+}}\in V_{t+1}(s)$,
hence there exists a policy $\pi$ such that $f=R_{t}(s,a)+u_{t+1}^{\pi}(j)$.
Let $\pi^{\prime}$ be any policy that prescribes $a$ in $s$ at time $t$ then
uses $\pi$ from $t+1$ onward. We have $f=u_{t}^{\pi^{\prime}}(s)$, so $f\in
V_{t}(s)$. Consequently, $F_{t}(s)\subseteq V_{t}(s)$ for all $s\in S$.

In summary, for all $t<N$ and $s\in S$, $F_{t}(s)\subseteq V_{t}(s)$. $\Box$

From Proposition 1 follows the validity of the White equations under
Assumption 1.

######  Corollary 2.

Under Assumption 1, the White equations are valid, i.e $U_{t}(s)=e(V_{t}(s))$
for all $t\leq N$ and $s\in S$.

##  5\. The White Equations and Non-Markovian Policies

Before turning to another class of models which have (P) as their property, we
start with some useful background. Recall that the motivation for introducing
(P) was the observation that, for some $t<N$ and $s\in S$, vectors in
$F_{t}(s)$ may have no corresponding policies in $P_{W}$. This allows for the
possibility that $F_{t}(s)\not\subseteq V_{t}(s)$, and thus for the
possibility that $U_{t}(s)=e(F_{t}(s))\not\subseteq V_{t}(s)$. Suppose now
that the “theorem” was true under some special set of assumptions, and that we
were to show this by proving (P). Furthermore, suppose we were to proceed by
induction, having noticed that the base case ($t=N-1$) holds, because for any
$f=R_{N-1}(s,a)+\sum_{j\in S}p_{N-1}(j|s,a)R_{N}(j)\in F_{N-1}(s)$, we have
$f=u_{N-1}^{\pi}(s)\in V_{N-1}(s)$ where $\pi$ is any policy that prescribes
$a$ in $s$ at time $N-1$.

To carry out the induction, assume that for some $t<N-1$,

$\forall s\in S,\ F_{t+1}(s)\subseteq V_{t+1}(s)$ (16)

Our task is to show that for all $s\in S$, for any $w\in F_{t}(s)$, $w\in
V_{t}(s)$. Let $s\in S$ and $w\in F_{t}(s)$. By definition of $F_{t}(s)$,
there is an $a\in A_{s}$ and, by the induction hypothesis, $|S|$ policies
$\pi_{1},...,\pi_{|S|}$ such that

$w=R_{t}(s,a)+\sum_{j\in S}p_{t}(j|s,a)u_{t+1}^{\pi_{j}}(j)$ (17)

In principle, a policy of the form “if the state at time $t$ is $s$, take
action $a$; if the state at time $t+1$ is $j$, take the action prescribed by
$\pi_{j}$, and continue using $\pi_{j}$ over $t+2,...,N-1$” should accrue an
expected total reward of $w$ over $t,t+1,...,N$ assuming the state at time $t$
was $s$. Such a policy, however, cannot be formulated within the present
framework. Indeed, our definition of policy (more rigorously, of decision
rule) presupposes that the only information relevant to decision making at
time $t$ is the state at that time, whereas if we were to implement the policy
just described, we would also need to know, at all times $k>t+1$, the state
that was observed at time $t+1$. This leads naturally to a concept of policy
where decision rules are functions of histories rather than of states, where
we define “history at time $t$” as the random trajectory of states observed
prior to and including $t$, i.e

$Z_{t}=(X_{1},X_{2},...,X_{t})$ (18)

if $t>1$, and $Z_{1}=X_{1}$. As before, $X_{i}$ denotes the state of the
process at epoch $i$. For all $t\leq N$, let $H_{t}=S^{t}$ denote the set of
all histories at time $t$, and notice that $H_{1}=S$, so that we may use
histories and states interchangeably at $t=1$. For each epoch $t<N$, the
phrase “$t$-decision rule” shall refer to any mapping from $H_{t}$ to $A$. Let
$D_{t}$ be the set of $t$-decision rules for any $t<N$, and
$D=\cup_{t<N}D_{t}$ be the overall set of decision rules. Assume that each
$D_{t}$ is compact. A policy $\pi=(d_{1},...,d_{N-1})$ is a sequence of
decision rules where each $d_{t}$, $t<N$, is a $t$-decision rule. Let $P$
denote the set of all policies.

It should be made clear here that $t$-decision rules are distinct from the
decision rules which Puterman (2014), for example, calls history-dependent (HD
in short; “D” for “deterministic”). For Puterman, histories contain past
actions, so that an HD decision rule at epoch $t<N$ maps $S\times A\times
S\times...\times A\times S$ ($S$ $t$ times, $A$ ($t-1$) times) to $A$, while a
$t$-decision rule maps $S^{t}$ to $A$. It is possible, however, to construe
each $D_{t}$ as the subset of HD decision rules at epoch $t$ which ignore
actions taken up to $t$. Similarly, decision rules in White (1982) can be
viewed as the subset of $D$ for which past states are irrelevant; that is, if
$h_{t}=(s_{1},...,s_{t})$ is any history at time $t$, and $d_{t}$ is a
$t$-decision rule such that $d_{t}(h_{t})$ depends on $h_{t}$ only through
$s_{t}$, then $d_{t}$ is in fact a decision rule in White’s sense. It follows
that $P_{W}\subset P\subset P_{HD}$, where $P_{HD}$ is the set of all policies
containing HD decision rules.

######  Proposition 3.

$P_{W}\subset P$.

Now that we have refined our concepts of decision rule and policy, we may
define the expected total reward accrued for using a policy
$\pi=(d_{1},...,d_{N-1})\in P$ from time $t<N$ onward if the history at $t$ is
$h_{t}=(s_{1},...,s_{t})$ as

$u_{t}^{\pi}(h_{t}):=\mathbb{E}_{\pi}^{h_{t}}[\sum_{i=t}^{N-1}R_{i}(X_{i},d_{i}(Z_{i}))+R_{N}(X_{N})].$
(19)

Since $Z_{t}=h_{t}$, we obtain a recursion analogous to Equation (1):

$u_{t}^{\pi}(h_{t})=R_{t}(s_{t},d_{t}(h_{t}))+\sum_{j\in
S}p_{t}(j|s_{t},d_{t}(h_{t}))u_{t+1}^{\pi}(h_{t},j)$ (20)

where we let $(h_{t},j):=(s_{1},...,s_{t},j)$ for all $j\in S$, and

$u_{N}^{\pi}(h_{N})=R_{N}(s)$ (21)

for all histories at time $N$, $h_{N}=(s_{1},...,s_{N})$, with $s_{N}=s$. Let
$V^{\prime}_{t}(h_{t})=\bigcup_{\pi\in P}\\{u_{t}^{\pi}(h_{t})\\}$ for all
$t\leq N$.

Given this new framework, we are now in a position to construct policies of
the form described earlier in this section, that is, policies which prescribe
some action at time $t$, then, depending on the resulting state $j$ at $t+1$,
pursue from that moment on a policy associated with $j$. As mentioned earlier,
the importance of such policies is their ability to achieve expected total
rewards of the form

$w=R_{t}(s_{t},a)+\sum_{j\in S}p_{t}(j|s_{t},a)u_{t+1}^{\pi_{j}}(h_{t},j)$
(22)

where $\pi_{1},...,\pi_{|S|}\in P$ are arbitrary policies, $t<N$ is some
decision epoch, $h_{t}=(s_{1},...,s_{t})\in H_{t}$, and $a\in A_{s_{t}}$ some
action (see Proposition 4 below). This enables us to prove a particular
restatement of property (P), namely

$\forall t<N,\ \forall h_{t}\in H_{t},\ F^{\prime}_{t}(h_{t})\subseteq
V^{\prime}_{t}(h_{t})$ (23)

where for all $t<N$, for all $h_{t}=(s_{1},...,s_{t})\in H_{t}$,

$F^{\prime}_{t}(h_{t})=\bigcup_{a\in
A_{s_{t}}}\biggl{(}\\{R_{t}(s_{t},a)\\}\bigoplus\sum_{j\in
S}p_{t}(j|s_{t},a)U^{\prime}_{t+1}(h_{t},j)\biggr{)}$ (24)

and

$\forall t<N,\ U^{\prime}_{t}(h_{t}):=e(F^{\prime}_{t}(h_{t}))$ (25)

with the boundary condition

$U^{\prime}_{N}(h_{N}):=\\{R_{N}(s)\\}$ (26)

for all $h_{N}=(s_{1},...,s_{N})$ with $s_{N}=s$. It is clear that this
revised property, which we shall refer to as (P’), is fundamentally no
different from (P); informally, we may say that it is (P), but enunciated in a
different framework. It shall later be proven that (P’) provides a sufficient
condition for the White equations to admit the $e(V^{\prime}_{t}(h_{t}))$,
$t\leq N$, $h_{t}\in H_{t}$, as their solutions, which means it plays the same
role as (P) in the original framework (Propositions 5 and 6). More
importantly, we shall see that (P’) is necessarily true (Theorem 3), and
therefore that the solutions to the White equations are the
$e(V^{\prime}_{t}(h_{t}))$, $t\leq N$, $h_{t}\in H_{t}$ (Theorem 5).

######  Proposition 4.

Let $t<N$ and $h_{t}=(s_{1},...,s_{t})\in H_{t}$. Let
$\pi_{1},...,\pi_{|S|}\in P$ be policies, and $a\in A_{s_{t}}$ be an action.
For each policy $\pi_{j}$, write $\pi_{j}=(d^{j}_{1},...,d^{j}_{N-1})$. Let

$w=R_{t}(s_{t},a)+\sum_{j\in S}p_{t}(j|s_{t},a)u_{t+1}^{\pi_{j}}(h_{t},j)$

Let

  1. (1)

$d_{t}:H_{t}\rightarrow A$ be any $t$-decision rule such that
$d_{t}(h_{t})=a$;

  2. (2)

$d_{t+1}:H_{t+1}\rightarrow A$ be any $(t+1)$-decision rule such that for all
$j\in S$, $d_{t+1}(h_{t},j)=d^{j}_{t+1}(h_{t},j)$;

  3. (3)

for each epoch $N-1\geq k>t+1$, $d_{k}:H_{k}\rightarrow A$ be any $k$-decision
rule such that for any $(k-t)$ states $j_{t+1},...,j_{k}\in S$,

$d_{k}(h_{t},j_{t+1},...,j_{k})=d^{j_{t+1}}_{k}(h_{t},j_{t+1},...,j_{k})$

Finally, let $\pi$ be any element in $D_{1}\times...\times D_{N-1}$ with
$(\pi)_{i}=d_{i}$ for all $i=t,t+1,...,N-1$.

Then:

  * (a)

$\pi$ is a policy, i.e $\pi\in P$;

  * (b)

$u_{t}^{\pi}(h_{t})=w$.

Proof.  Part (a) follows from the definition of $P=D_{1}\times...\times
D_{N-1}$ and the well-definedness of the $d_{i}$’s. We shall prove part (b).

$\displaystyle u_{t}^{\pi}(h_{t})$
$\displaystyle=R_{t}(s,d_{t}(h_{t}))+\sum_{j\in
S}p_{t}(j|s,d_{t}(h_{t}))u_{t+1}^{\pi}(h_{t},j)$
$\displaystyle=R_{t}(s,a)+\sum_{j\in
S}p_{t}(j|s,a)\biggl{(}R_{t+1}(j,d_{t+1}^{j}(h_{t},j))+\sum_{j^{\prime}\in
S}p_{t}(j^{\prime}|j,d_{t+1}^{j}(h_{t},j))u_{t+2}^{\pi}(h_{t},j,j^{\prime})\biggr{)}$
$\displaystyle=R_{t}(s,a)+\sum_{j\in
S}p_{t}(j|s,a)\biggl{(}R_{t+1}(j,d_{t+1}^{j}(h_{t},j))+\sum_{j^{\prime}\in
S}p_{t}(j^{\prime}|j,d_{t+1}^{j}(h_{t},j))u_{t+2}^{\pi_{j}}(h_{t},j,j^{\prime})\biggr{)}$
$\displaystyle=R_{t}(s,a)+\sum_{j\in S}p_{t}(j|s,a)u_{t+1}^{\pi_{j}}(h_{t},j)$
$\displaystyle=w.$

$\Box$

The same method which was used to prove that (P) yields $U_{t}(s)=e(V_{t}(s))$
for all $t\leq N$ and $s\in S$ (see Proposition 1, Sec. 3) can be applied here
to show that (P’) yields $U^{\prime}_{t}(h_{t})=e(V^{\prime}_{t}(h_{t}))$ for
all $t\leq N$ and $h_{t}\in H_{t}$. To do this, one will require the analogue
of Lemma 1 for the $V^{\prime}_{t}(h_{t})$’s, i.e

######  Lemma 3.

Let $t\leq N$ and $h_{t}\in H_{t}$. For each $u\in V^{\prime}_{t}(h_{t})$,
there is a $v\in e(V^{\prime}_{t}(h_{t}))$ such that $v\geq u$.

An essential component of our proof of Lemma 3 is a general theorem which
appears in White (1977), restated below in the vocabulary of the present
paper:

######  Theorem 2.

(White, 1977) Let $R$ be a relationship on a set $X$. Define the efficient
subset of $X$ as $e(X)=\\{x\in X\mid,\ yRx\implies y=x\\}$. If $X$ is compact
and $S(x)=\\{y\in X\mid\,yRx\\}$ is closed for all $x\in X$, then, for all
$x\in X$, there exists $y\in e(X)$ such that $yRx$.

This theorem implies that we need only show that $V^{\prime}_{t}(h_{t})$ is
compact and that $S(u)=\\{v\in V^{\prime}_{t}(h_{t})\mid\,v\geq u\\}$ is
closed for all $t\leq N$, $h_{t}\in H_{t}$, $u\in V^{\prime}_{t}(h_{t})$. For
all $t\leq N$, $h_{t}\in H_{t}$, $V^{\prime}_{t}(h_{t})$, being a subset of
$\mathbb{R}^{m}$, is compact if and only if it is bounded and closed, as per
the Bolzano-Weierstrass theorem. In this connection, it is necessary to
introduce a topology on the $V^{\prime}_{t}(h_{t})$’s with respect to which
convergence is defined. Accordingly, we equip these sets with the topology of
pointwise convergence. Convergence in the $D_{t}$’s is also with respect to
this topology.

Our proof is by induction on $t$. In particular, to demonstrate the closedness
of $V^{\prime}_{t}(h_{t})$ for some $t$ and $h_{t}\in H_{t}$, assuming that
$V^{\prime}_{t+1}(h_{t+1})$ is compact for all $h_{t+1}\in H_{t+1}$, we invoke
an important lemma concerning the weighted sum of $k$ sequences, $k\geq 1$,
where each sequence takes its values in a compact subset of $\mathbb{R}^{m}$:

######  Lemma 4.

Equip $\mathbb{R}^{m}$ with the topology of pointwise convergence. Let $k\geq
1$ and let $U_{1},...,U_{k}$ be $k$ nonempty compact subsets of
$\mathbb{R}^{m}$. If $(p_{1,n})_{n\geq 0}$, …, $(p_{k,n})_{n\geq 0}$ are $k$
sequences with values in $[0,1]$ and $(x_{1,n})_{n\geq 0}$, …,
$(x_{k,n})_{n\geq 0}$ sequences with values in $U_{1},...,U_{k}$ respectively,
then there exists a strictly increasing map
$\phi:\mathbb{N}\rightarrow\mathbb{N}$ such that

  * (a)

for all $i=1,...,k$, $p_{i,\phi(n)}\to p_{i}^{*}$ for some
$p_{i}^{*}\in[0,1]$;

  * (b)

for all $i=1,...,k$, $x_{i,\phi(n)}\to x_{i}^{*}$ for some $x_{i}^{*}\in
U_{i}$;

  * (c)

and
$\sum_{i=1}^{k}p_{i,\phi(n)}x_{i,\phi(n)}\to\sum_{i=1}^{k}p_{i}^{*}x_{i}^{*}$.

Proof.  Let us first verify parts (a) and (b) for $k=1$. Let $U_{1}$ be a
nonempty compact subset of $\mathbb{R}^{m}$, $(p_{1,n})_{n\geq 0}$ be a
sequence with values in $[0,1]$ and $(x_{1,n})_{n\geq 0}$ be a sequence with
values in $U_{1}$. Since $[0,1]$ is compact, there exist a strictly increasing
map $\alpha:\mathbb{N}\rightarrow\mathbb{N}$ and a $p_{1}^{*}\in[0,1]$ such
that $p_{1,\alpha(n)}\to p_{1}^{*}$. Consider now the subsequence of
$(x_{1,n})_{n\geq 0}$ indexed by $\alpha$, $(x_{1,\alpha(n)})_{n\geq 0}$.
Because this subsequence also takes values in a compact set, $U_{1}$, there
exist a strictly increasing map $\beta:\mathbb{N}\rightarrow\mathbb{N}$ and a
$x_{1}^{*}\in U_{1}$ such that $x_{1,\alpha(\beta(n))}\to x_{1}^{*}$. We also
have that $(p_{1,\alpha(\beta(n))})_{n\geq 0}$ is a subsequence of
$(p_{1,\alpha(n)})_{n\geq 0}$, and therefore $(p_{1,\alpha(\beta(n))})_{n\geq
0}\to p_{1}^{*}$. Let $\phi=\alpha\circ\beta$, which is a strictly increasing
map from $\mathbb{N}$ to $\mathbb{N}$. Then $p_{1,\phi(n))}\to p_{1}^{*}$ and
$x_{1,\phi(n)}\to x_{1}^{*}$, hence parts (a) and (b), from which part (c)
follows.

Let now $k\geq 1$, and assume that the lemma holds for any $k$ nonempty
compact subsets of $\mathbb{R}^{m}$. Let $U_{1},...,U_{k+1}$ be $(k+1)$
nonempty compact subsets of $\mathbb{R}^{m}$, $(p_{1,n})_{n\geq 0}$, …,
$(p_{k+1,n})_{n\geq 0}$ be sequences with values in $[0,1]$, and
$(x_{1,n})_{n\geq 0}$, …, $(x_{k+1,n})_{n\geq 0}$ be sequences with values in
$U_{1},...,U_{k+1}$ respectively. By the induction hypothesis, there exist
$p_{1}^{*}$, …, $p_{k}^{*}$ in $[0,1]$, $x_{1}^{*}$, …, $x_{k}^{*}$ in
$U_{1},...,U_{k}$ respectively, and a strictly increasing map
$\gamma:\mathbb{N}\rightarrow\mathbb{N}$ such that $p_{i,\gamma(n)}\to
p_{i}^{*}$ and $x_{i,\gamma(n)}\to x_{i}^{*}$ for every $i=1,...,k$. Focus now
on $(p_{k+1,\gamma(n)})_{n\geq 0}$. Due to the compactness of $[0,1]$,
$(p_{k+1,\gamma(n)})_{n\geq 0}$ admits a subsequence, say
$(p_{k+1,\gamma(\alpha(n)}))_{n\geq 0}$, where
$\alpha:\mathbb{N}\rightarrow\mathbb{N}$ is strictly increasing, such that
$p_{k+1,\gamma(\alpha(n))}\to p_{k+1}^{*}$ for some $p_{k+1}^{*}\in[0,1]$.
Also, we know that $p_{i,\gamma(\alpha(n))}\to p_{i}^{*}$ and
$x_{i,\gamma(\alpha(n))}\to x_{i}^{*}$ for every $i=1,...,k$. By letting
$\phi=\gamma\circ\alpha$, we can see that for every $i=1,...,k+1$,
$p_{i,\phi(n)}\to p_{i}^{*}$ and $x_{i,\phi(n)}\to x_{i}^{*}$. Thus
$\sum_{i=1}^{k+1}p_{i,\phi(n)}x_{i,\phi(n)}\to\sum_{i=1}^{k+1}p_{i}^{*}x_{i}^{*}$.
The lemma follows by induction. $\Box$

Theorem 2 and Lemma 4 supply enough background material for proving Lemma 3.
We shall now proceed to do so.

Proof. [Proof of Lemma 3] For notational convenience, let
$S=\\{j_{1},...,j_{|S|}\\}$. We begin by demonstrating the compactness of
$V^{\prime}_{t}(h_{t})$ for all $t\leq N$ and $h_{t}\in H_{t}$. The proof is
by induction on $t$. For $t=N$, let $h_{N}=(s_{1},...,s_{N})\in H_{N}$.
$V^{\prime}_{N}(h_{N})=\\{R_{N}(s_{N})\\}$ is closed because it is finite. For
any $\pi\in P$, we have $u_{N}^{\pi}(h_{N})=R_{N}(s_{N})$, and therefore
$\|u_{N}^{\pi}(h_{N})\|_{\infty}\leq\|R_{N}(s_{N})\|_{\infty}$. We then have
that for all $h_{N}\in H_{N}$, $V^{\prime}_{N}(h_{N})$ is closed and bounded,
and therefore compact. Suppose $V^{\prime}_{t+1}(h_{t+1})$ is compact for all
$h_{t+1}\in H_{t+1}$, for some $t<N$.

Let $h_{t}=(s_{1},...,s_{t})\in H_{t}$ and $v=u_{t}^{\pi}(h_{t})\in
V^{\prime}_{t}(h_{t})$ with $P=(d_{1},...,d_{N-1})$. Then
$v=R_{t}(s_{t},d_{t}(h_{t}))+\sum_{j\in
S}p_{t}(j|s_{t},d_{t}(h_{t}))u_{t+1}^{\pi}(h_{t},j)$. By the induction
hypothesis, there exists, for each $j\in S$, an $M_{j}\geq 0$ such that
$\|u_{t+1}^{\pi}(h_{t},j)\|_{\infty}\leq M_{j}$. Applying the triangle
inequality twice on $\|v\|_{\infty}$, we obtain
$\|v\|_{\infty}\leq\|R_{t}(s_{t},d_{t}(h_{t}))\|_{\infty}+\sum_{j\in S}M_{j}$,
whence

$\|v\|_{\infty}\leq\max_{1\leq i\leq m}\max_{a\in
A_{s_{t}}}|R_{t}(s_{t},a)_{i}|+\sum_{j\in S}M_{j}$

by noticing that for each $1\leq i\leq m$, $\max_{a\in
A_{s_{t}}}\,|R_{t}(s_{t},a)_{i}|$ exists because $A_{s_{t}}$ is compact and
$a\mapsto|R_{t}(s_{t},a)_{i}|$ is continuous on $A_{s_{t}}$.

Thus $V^{\prime}_{t}(h_{t})$ is bounded. In order to demonstrate its
closedness, let $(v^{n})_{n\geq 0}$ be a sequence of vectors in
$V^{\prime}_{t}(h_{t})$ that converges to a $v\in\mathbb{R}^{m}$. We may write

$v^{n}=u_{t}^{\pi_{n}}(h_{t})=R_{t}(s_{t},d_{t}^{\pi_{n}}(h_{t}))+\sum_{i=1}^{|S|}p_{t}(j_{i}|s_{t},d_{t}^{\pi_{n}}(h_{t}))u_{t+1}^{\pi_{n}}(h_{t},j_{i})$

for some $\pi_{n}=(d_{1}^{\pi_{n}},...,d_{N-1}^{\pi_{n}})\in P$, for all
$n\geq 0$. We endeavor to show that $v\in V^{\prime}_{t}(h_{t})$. By the
hypothesized compactness of the $V^{\prime}_{t+1}(h_{t},j_{i})$’s,
$i=1,...,|S|$, there exist, according to Lemma 4, a strictly increasing map
$\phi:\mathbb{N}\rightarrow\mathbb{N}$, and $p_{1}^{*}$, …,
$p_{|S|}^{*}\in[0,1]$, and $x_{1}^{*},...,x_{|S|}^{*}$ in
$V^{\prime}_{t+1}(h_{t},j_{1})$, …, $V^{\prime}_{t+1}(h_{t},j_{|S|})$
respectively, such that

$u_{t+1}^{\pi_{\phi(n)}}(h_{t},j_{i})\to x_{i}^{*}$
$p_{t}(j_{i}|s_{t},d_{t}^{\pi_{\phi(n)}}(h_{t}))\to p_{i}^{*}$

for all $i=1,...,|S|$, and therefore
$\sum_{i=1}^{|S|}p_{t}(j_{i}|s_{t},d_{t}^{\pi_{\phi(n)}}(h_{t}))u_{t+1}^{\pi_{\phi(n)}}(h_{t},j_{i})\to\sum_{i=1}^{|S|}p_{i}^{*}x_{i}^{*}$.

Focusing now on the $p_{i}^{*}$’s, observe that since $D_{t}$ is compact,
there exist a $d^{*}\in D_{t}$ and a strictly increasing
$\alpha:\mathbb{N}\rightarrow\mathbb{N}$ such that
$d_{t}^{\pi_{\phi(\alpha(n))}}\to d^{*}$ and, in particular, in view of the
adopted topology, $d_{t}^{\pi_{\phi(\alpha(n))}}(h_{t})\to d^{*}(h_{t})$. By
the assumed continuity of transition probabilities on $A_{s_{t}}$, it follows
that

$p_{t}(j_{i}|s_{t},d_{t}^{\pi_{\phi(\alpha(n))}}(h_{t}))\to
p_{t}(j_{i}|s_{t},d^{*}(h_{t}))$

for all $i=1,...,|S|$. Moreover, for all $i=1,...,|S|$,
$(p_{t}(j_{i}|s_{t},d_{t}^{\pi_{\phi(\alpha(n))}}(h_{t}))_{n\geq 0}$ is a
subsequence of $(p_{t}(j_{i}|s_{t},d_{t}^{\pi_{\phi(n)}}(h_{t})))_{n\geq 0}$,
from which it follows that $p_{i}^{*}=p_{t}(j_{i}|s_{t},d^{*}(h_{t}))$. To
recapitulate, then, we have established that

$\sum_{i=1}^{|S|}p_{t}(j_{i}|s_{t},d_{t}^{\pi_{\phi(\alpha(n))}}(h_{t}))u_{t+1}^{\pi_{\phi(\alpha(n))}}(h_{t},j_{i})\to\sum_{i=1}^{|S|}p_{t}(j_{i}|s_{t},d^{*}(h_{t}))x_{i}^{*}.$

By the assumed continuity of rewards on $A_{s_{t}}$, we also have that
$R_{t}(s_{t},d_{t}^{\pi_{\phi(\alpha(n))}}(h_{t}))\to
R_{t}(s_{t},d^{*}(h_{t}))$. This means that

$R_{t}(s_{t},d_{t}^{\pi_{\phi(\alpha(n))}}(h_{t}))+\sum_{i=1}^{|S|}p_{t}(j_{i}|s_{t},d_{t}^{\pi_{\phi(\alpha(n))}}(h_{t}))u_{t+1}^{\pi_{\phi(\alpha(n))}}(h_{t},j_{i})\\\
\to
R_{t}(s_{t},d^{*}(h_{t}))+\sum_{i=1}^{|S|}p_{t}(j_{i}|s_{t},d^{*}(h_{t}))x_{i}^{*}$

We thus have a subsequence of $(v^{n})_{n\geq 0}$ that converges to
$R_{t}(s_{t},d^{*}(h_{t}))+\sum_{i=1}^{|S|}p_{t}(j_{i}|s_{t},d^{*}(h_{t}))x_{i}^{*}$.
Hence
$v=R_{t}(s_{t},d^{*}(h_{t}))+\sum_{i=1}^{|S|}p_{t}(j_{i}|s_{t},d^{*}(h_{t}))x_{i}^{*}$.
Recalling that each $x_{i}^{*}$ is in $V^{\prime}_{t}(h_{t},j_{i})$, we know
from Proposition 4 that there is a $\pi\in P$ such that
$v=u_{t}^{\pi}(h_{t})$. Thus $v\in V^{\prime}_{t}(h_{t})$. In conclusion,
$V^{\prime}_{t}(h_{t})$ is closed and bounded, and therefore compact.

Finally, for all $t\leq N$, $h_{t}\in H_{t}$ and $u\in V^{\prime}_{t}(h_{t})$,
that $S(u)=\\{v\in V^{\prime}_{t}(h_{t})\mid\,v\geq u\\}$ is closed follows
immediately from the closedness of $V^{\prime}_{t}(h_{t})$ and the fact that
if a convergent sequence $(v^{n})_{n\geq 0}$ in $\mathbb{R}^{m}$ satisfies
$v^{n}\geq u$ for all $n\geq 0$, then its limit $v$ also satisfies $v\geq u$
by the definition of $\geq$.

By Theorem 4, Lemma 3 is true. $\Box$

######  Proposition 5.

(P’) implies $U^{\prime}_{t}(h_{t})=e(V^{\prime}_{t}(h_{t}))$ for all $t\leq
N$ and $h_{t}\in H_{t}$.

Proof.  Suppose (P’) is true. For $t=N$, for all $h_{N}=(s_{1},...,s_{N})\in
H_{N}$, $U^{\prime}_{N}(h_{N})=\\{R_{N}(s_{N})\\}$ and
$V^{\prime}_{N}(h_{N})=\\{R_{N}(s_{N})\\}$; thus,
$U^{\prime}_{N}(h_{N})=e(V^{\prime}_{N}(h_{N}))$. Let $t<N-1$ and assume
$U^{\prime}_{t+1}(h_{t+1})=e(V^{\prime}_{t+1}(h_{t+1})$ for all $h_{t+1}\in
H_{t+1}$.

Let $h_{t}=(s_{1},...,s_{t})\in H_{t}$ and $v\in e(V^{\prime}_{t}(h_{t}))$.
There exists a $\pi=(d_{1},...,d_{N-1})\in P$ such that
$v=R_{t}(s_{t},d_{t}(h_{t}))+\sum_{j\in
S}p_{t}(j|s_{t},d_{t}(h_{t}))u_{t+1}^{\pi}(h_{t},j)$. For all $j\in S$,
$(h_{t},j)\in H_{t+1}$, and by Lemma 3 there exists a $v_{j}\in
e(V^{\prime}_{t+1}(h_{t},j))$ such that $v_{j}\geq u_{t+1}^{\pi}(h_{t},j)$.
Let $w=R_{t}(s_{t},d_{t}(h_{t}))+\sum_{j\in
S}p_{t}(j|s_{t},d_{t}(h_{t}))v_{j}$. By Lemma 2, $w\geq v$, and by the
induction hypothesis together with (P’) we have that $w\in
V^{\prime}_{t}(h_{t})$. However, $v$ being efficient in
$V^{\prime}_{t}(h_{t})$, $v=w$. Hence, again by the induction hypothesis,
$v\in F^{\prime}_{t}(h_{t})$. By (P’), $F^{\prime}_{t}(h_{t})\subseteq
V^{\prime}_{t}(h_{t})$, and thus $v$ is also efficient in
$F^{\prime}_{t}(h_{t})$, i.e $v\in U^{\prime}_{t}(h_{t})$. From this it
follows that $e(V^{\prime}_{t}(h_{t}))\subseteq U^{\prime}_{t}(h_{t})$.

Now we shall demonstrate the converse inclusion. Let $u\in
U^{\prime}_{t}(h_{t})$. There exists an $a\in A_{s_{t}}$ such that
$u=R_{t}(s_{t},a)+\sum_{j\in S}p_{t}(j|s_{t},a)v_{j}$ for some $v_{j}\in
U^{\prime}_{t+1}(h_{t},j)$ for all $j\in S$. By (P’), $u\in
V^{\prime}_{t}(h_{t})$. Assuming towards a contradiction that $u\notin
e(V^{\prime}_{t}(h_{t}))$, there exists, applying Lemma 1, $v\in
e(V^{\prime}_{t}(h_{t}))\subseteq U^{\prime}_{t}(h_{t})$ such that $v\geq u$
and $v\neq u$. This contradicts the fact that $u\in U^{\prime}_{t}(h_{t})$,
because $U^{\prime}_{t}(h_{t})$ is an efficient set, and shows that $u\in
e(V^{\prime}_{t}(h_{t}))$. Consequently, $U^{\prime}_{t}(h_{t})\subseteq
e(V^{\prime}_{t}(h_{t}))$.

Finally, for all $t\leq N$, for all $h_{t}\in H_{t}$,
$U^{\prime}_{t}(h_{t})=e(V^{\prime}_{t}(h_{t}))$.

$\Box$

We are now able to substantiate (P’).

######  Theorem 3.

(P’) is true, i.e

$\forall t<N,\ \forall h_{t}\in H_{t},\ F^{\prime}_{t}(h_{t})\subseteq
V^{\prime}_{t}(h_{t})$

Proof.  We proceed by induction on $t$. Let $h_{N-1}=(s_{1},...,s_{N-1})\in
H_{N-1}$, and let $f=R_{N-1}(s_{N-1},a)+\sum_{j\in
S}p_{N-1}(j|s_{N-1},a)R_{N}(j)\in F^{\prime}_{N-1}(h_{N-1})$, for some $a\in
A_{s_{N-1}}$. Then $f=u_{N-1}^{\pi}(h_{N-1})\in V^{\prime}_{N-1}(h_{N-1})$ for
any policy $\pi\in P$ that prescribes $a$ at time $N-1$ when the history at
that time is $h_{N-1}$. Consequently, $F^{\prime}_{N-1}(h_{N-1})\subseteq
V^{\prime}_{N-1}(h_{N-1})$ for all $h_{N-1}\in H_{N-1}$.

Let us assume now that for some $t<N-1$, $F^{\prime}_{t+1}(h_{t+1})\subseteq
V^{\prime}_{t+1}(h_{t+1})$ for all $h_{t+1}\in H_{t+1}$. Let
$h_{t}=(s_{1},...,s_{t})\in H_{t}$, and let $f\in F^{\prime}_{t}(h_{t})$.
There exist an $a\in A_{s_{t}}$ and, for each $j\in S$, a $v_{j}\in
U^{\prime}_{t+1}(h_{t},j)$ such that $f=R_{t}(s_{t},a)+\sum_{j\in
S}p_{t}(j|s_{t},a)v_{j}$. By our induction hypothesis,
$U^{\prime}_{t+1}(h_{t},j)=e(F^{\prime}_{t+1}(h_{t},j))\subseteq
V^{\prime}_{t+1}(h_{t},j)$ for all $j\in S$, so that each $v_{j}$ can be
written $v_{j}=u_{t+1}^{\pi_{j}}(h_{t},j)$ for some policy $\pi_{j}\in P$.
Thus,

$f=R_{t}(s_{t},a)+\sum_{j\in S}p_{t}(j|s_{t},a)u_{t+1}^{\pi_{j}}(h_{t},j)$
(27)

By virtue of Proposition 4, there exists a policy $\pi\in P$ such that
$f=u_{t}^{\pi}(h_{t})$. Thus, $f\in V^{\prime}_{t}(h_{t})$. As a result,
$F^{\prime}_{t}(h_{t})\subseteq V^{\prime}_{t}(h_{t})$. In sum, we have shown
by induction that for all $t<N$, $F^{\prime}_{t}(h_{t})\subseteq
V^{\prime}_{t}(h_{t})$ for all $h_{t}\in H_{t}$. $\Box$

Combining Theorem 3 with Proposition 5, we obtain the following relation
between the solutions to Equations (23) and (24) and the efficient sets of
policy returns over $P$, the $e(V^{\prime}_{t}(h_{t}))$’s:

######  Theorem 4.

For all $t\leq N$ and $h_{t}=(s_{1},...,s_{t})\in H_{t}$,
$e(V^{\prime}_{t}(h_{t}))$ is the unique solution $U^{\prime}_{t}(h_{t})$ to
either of the following equations:

$U^{\prime}_{t}(h_{t})=e\Biggl{(}\bigcup_{a\in
A_{s_{t}}}\biggl{(}\\{R_{t}(s_{t},a)\\}\bigoplus\sum_{j\in
S}p_{t}(j|s_{t},a)U^{\prime}_{t+1}(h_{t},j)\biggr{)}\Biggr{)};\begin{array}[]{l}t<N\\\
\end{array}$
$U^{\prime}_{t}(h_{t})=\\{R_{N}(s_{t})\\};\begin{array}[]{l}t=N\\\
\end{array}$

The equations can be simplified by noticing that $U^{\prime}_{t}(h_{t})$
depends on $h_{t}$ only through $s_{t}$. Because these and White’s equations
share the same boundary condition at $t=N$, this has the important implication
that for all $t\leq N$ and $h_{t}=(s_{1},...,s_{t})\in H_{t}$,
$U^{\prime}_{t}(h_{t})$ is none other than $U_{t}(s_{t})$.

######  Proposition 6.

For all $t\leq N$, for all $h_{t}=(s_{1},...,s_{t})\in H_{t}$,
$U^{\prime}_{t}(h_{t})=U_{t}(s_{t})$.

Proof.  For $t=N$, we have that for all $h_{N}=(s_{1},...,s_{N})\in H_{N}$,
$U^{\prime}_{N}(h_{N})=\\{R_{N}(s_{N})\\}=U_{N}(s_{N})$. The property holds
for $t=N$. Assume that for some $t<N$,
$U^{\prime}_{t+1}(h_{t+1})=U_{t+1}(s_{t+1})$ for all
$h_{t+1}=(s_{1},...,s_{t+1})\in H_{t+1}$. For all $h_{t}=(s_{1},...,s_{t})\in
H_{t}$, we have by definition,

$U^{\prime}_{t}(h_{t})=e\Biggl{(}\bigcup_{a\in
A_{s_{t}}}\biggl{(}\\{R_{t}(s_{t},a)\\}\bigoplus\sum_{j\in
S}p_{t}(j|s_{t},a)U^{\prime}_{t+1}(h_{t},j)\biggr{)}\Biggr{)}$ (28)

hence

$U^{\prime}_{t}(h_{t})=e\Biggl{(}\bigcup_{a\in
A_{s_{t}}}\biggl{(}\\{R_{t}(s_{t},a)\\}\bigoplus\sum_{j\in
S}p_{t}(j|s_{t},a)U_{t+1}(j)\biggr{)}\Biggr{)}$ (29)

by the induction hypothesis. Thus $U^{\prime}_{t}(h_{t})=U_{t}(s_{t})$. The
proposition follows. $\Box$

Applying Proposition 6 and Theorem 4, we discover that the solutions to the
White equations at $t\leq N$ are the $e(V^{\prime}_{t}(h_{t}))$’s, $h_{t}\in
H_{t}$.

######  Theorem 5.

For all $t\leq N$, for all $h_{t}=(s_{1},...,s_{t})\in H_{t}$,
$U_{t}(s_{t})=e(V^{\prime}_{t}(h_{t}))$.

An interesting byproduct of Theorem 5 and Corollary 2 is that under the
determinism assumption defined in Section 3, all efficient policy returns over
$P$ are attained by policies in $P_{W}\subset P$. Hence, given the same
initial state, an optimal policy in $P_{W}$ can accrue as “large” an expected
reward as an optimal policy in the whole of $P$. Rather than consider the full
range of policies in $P$, the decision maker is therefore justified in
focusing only on Markovian policies, i.e $P_{W}$, which are easier to
implement and evaluate (Puterman, 2014).

######  Corollary 3.

Suppose Assumption 1 is satisfied. Then, for all $s\in S$,

$e\Biggl{(}\bigcup_{\pi\in
P_{W}}\\{u_{1}^{\pi}(s)\\}\Biggr{)}=e\Biggl{(}\bigcup_{\pi\in
P}\\{u_{1}^{\pi}(s)\\}\Biggr{)}$

##  6\. An Example

In this section we report the results of experimental tests of Corollary 2
(Sec. 4), Theorem 5 (Sec. 5) and Corollary 3 (Sec. 5). To check Theorem 5, we
compared $U_{1}(s_{1})$ of the model in Section 2 with
$e(V^{\prime}_{1}(h_{1}))=e(V^{\prime}_{1}(s_{1}))$. Recall that this model
furnished a counterexample to White’s “theorem”, since

$U_{1}(s_{1})=\\{(30.3,-9.0),(30.0,-7.8),(29.0,-3.3),(28.7,-2),(27.6,0.4),(27.3,1.6),(26.8,4.2),\\\
(26.5,5.5),(25.8,6.6),(25.6,7.9),(25.0,10.5),(24.1,12.9),(23.5,15.5)\\}$ (30)

yet $e(V_{1}(s_{1}))\neq U_{1}(s_{1})$.

A full search that was performed over the 16 384 policies in $P$ yielded

$e(V^{\prime}_{1}(s_{1}))=\\{(30.3,-9.0),(30.0,-7.8),(29.0,-3.3),(28.7,-2),(27.6,0.4),(27.3,1.6),(26.8,4.2),\\\
(26.5,5.5),(25.8,6.6),(25.6,7.9),(25.0,10.5),(24.1,12.9),(23.5,15.5)\\}$ (31)

Thus $U_{1}(s_{1})=e(V^{\prime}_{1}(s_{1}))$, a fact in accord with Theorem 5.

As a test of Corollary 2, we next imposed deterministic state transitions on
this model, letting
$p_{t}(s_{1}|s_{1},a_{1})=p_{t}(s_{2}|s_{1},a_{2})=p_{t}(s_{1}|s_{2},a_{1})=p_{t}(s_{2}|s_{2},a_{2})=1$
for all $t<N=4$. The rewards were unchanged from Section 2. By evaluating
Equations (4) and (5) backward in time, we obtained

$U_{1}(s_{1})=\\{(34,-15),(26,5),(31,-4),(23,16)\\}$ (32)

and a full search of the 64 policies in $P_{W}$ confirmed
$e(V_{1}(s_{1}))=U_{1}(s_{1})$.

To support Corollary 3, we calculated $e(V^{\prime}_{1}(s_{1}))$ in this
deterministic setting with a view to comparing it with $e(V_{1}(s_{1}))$.
Through a comprehensive search of $P$, we found

$e(V^{\prime}_{1}(s_{1}))=\\{(34,-15),(26,5),(31,-4),(23,16)\\}=e(V_{1}(s_{1}))$
(33)

which corroborates Corollary 3.

##  7\. Conclusion

The aims of this paper were (a) to show that the hypotheses underlying the
vector extension of the Bellman equations of a Markov decision process do not
ensure the extension’s validity, and (b) to propose alternative hypotheses
that do. A counterexample to the “theorem” on which this extension is
predicated was provided, and an explanation as to why the “theorem” failed was
advanced. It was found that the “theorem” holds when (1) the decision making
horizon, $N$, spans two or three time steps, or when (2) only deterministic
state transitions are permitted, or when (3) the policy space is enlarged from
just Markovian policies to include non-Markovian ones.

Not covered in this paper was a fourth area in which the extension is valid,
namely a combination of determinism (Assumption 1) and that $\geq$ be any
relationship on $\mathbb{R}^{m}$ that meets either of the following sets of
conditions:

  1. (1)

$\geq$ is transitive;

  2. (2)

for all $t\leq N$, $s\in S$, and $u\in V_{t}(s)$, the set $S(u)=\\{v\in
V_{t}(s)\mid,\ v\geq u\\}$ is closed;

  3. (3)

for all $x,y,z\in\mathbb{R}^{m}$, $x\geq y\implies(x+z)\geq(y+z)$;

  4. (4)

for all $x\in\mathbb{R}^{m}$, for all nonnegative reals $a$, $x\geq y\implies
ax\geq ay$;

or

  1. (1)

$\geq$ is a partial order;

  2. (2)

for all $t\leq N$, $s\in S$, every totally ordered subset (chain) of
$V_{t}(s)$ admits an upper bound in $V_{t}(s)$ with respect to $\geq$;

  3. (3)

for all $x,y,z\in\mathbb{R}^{m}$, $x\geq y\implies(x+z)\geq(y+z)$;

  4. (4)

and for all $x\in\mathbb{R}^{m}$, for all nonnegative reals $a$, $x\geq
y\implies ax\geq ay$.

In the remainder of the discussion, we shall refer to the first set of
conditions as (C1), and to the second as (C2). Some motivation for (C1) and
(C2) follows. In our proof of the proposition that (P) implies
$U_{t}(s)=e(V_{t}(s))$ for all $t$ and $s$, we appealed principally to two
facts concerning $\geq$: Lemma 1 and Lemma 2. Here Lemma 2 follows from
conditions (3) and (4) in both of (C1) and (C2). Lemma 1 originally appeared
in White (1982), and is an application of a general theorem published years
earlier in White (1977). The theorem states that if $R$ is a transitive
relationship on a compact set $X$, and $S(x)=\\{y\in X\mid,\ yRx\\}$ is closed
for all $x\in X$, then for all $x\in X$, there exists $y\in e(X)$ with $yRx$,
where $e(X)$ is defined with respect to $R$. From this follows Lemma 1 under
(C1), because the compactness of $V_{t}(s)$ for all $t$ and $s$ is a fact
independent of $\geq$ (White, 1982). As to why it follows under (C2) as well,
recall that by Zorn’s lemma (Zorn, 1935), a partially ordered set $X$ in which
every chain is upper bounded in $X$ has at least a maximal element, i.e
$e(X)\neq\emptyset$. Under (C2), it is straightforward to show that every
chain in $V_{t}(s)\cap S(u)$ is upper bounded in $V_{t}(s)\cap S(u)$, for all
$t$, $s$ and $u\in V_{t}(s)$. Thus $e(V_{t}(s)\cap S(u))\neq\emptyset$.
Furthermore, as can easily be checked, $e(V_{t}(s)\cap S(u))\subseteq
e(V_{t}(s))\cap S(u)$, and thus $e(V_{t}(s))\cap S(u)\neq\emptyset$, hence
Lemma 1. From this we conclude that Proposition 1 holds. At this stage we need
only prove that (P) is true, but this is a direct consequence of Assumption 1.
Therefore, the extension is valid under Assumption 1 coupled with (C1) or
(C2).

## Acknowledgment

The author is indebted to Dominikus Noll for stimulating conversations that
gave impetus to the section pertaining to the deterministic case. The author
also thanks Eilon Solan for comments on an early version of this paper, and
Slim Kammoun for assistance with certain mathematical aspects of the final
section.

## Statements and Declarations

The author states that he has no conflict of interest.

## References

  * Geoffrion (1968) geoffrion1968properGeoffrion, AM.  1968\.  Proper efficiency and the theory of vector maximization Proper efficiency and the theory of vector maximization.  Journal of mathematical analysis and applications223618–630.
  * Hayes . (2022) 4Hayes, CF., Rădulescu, R., Bargiacchi, E., Källström, J., Macfarlane, M., Reymond, M.others  2022\.  A practical guide to multi-objective reinforcement learning and planning A practical guide to multi-objective reinforcement learning and planning.  Autonomous Agents and Multi-Agent Systems36126.
  * Mandow . (2022) 9Mandow, L., Pérez-de-la Cruz, JL. Pozas, N.  2022\.  Multi-objective dynamic programming with limited precision Multi-objective dynamic programming with limited precision.  Journal of Global Optimization823595–614.
  * Mannor Shimkin (2004) 5Mannor, S. Shimkin, N.  2004\.  A geometric approach to multi-criterion reinforcement learning A geometric approach to multi-criterion reinforcement learning.  The Journal of Machine Learning Research5325–360.
  * Puterman (2014) puterman1994Puterman, ML.  2014\.  Markov decision processes: discrete stochastic dynamic programming Markov decision processes: discrete stochastic dynamic programming.  John Wiley & Sons.
  * Roijers . (2021) 6Roijers, DM., Röpke, W., Nowé, A. Rădulescu, R.  2021\.  On following pareto-optimal policies in multi-objective planning and reinforcement learning On following pareto-optimal policies in multi-objective planning and reinforcement learning.  Proceedings of the Multi-Objective Decision Making (MODeM) Workshop. Proceedings of the multi-objective decision making (modem) workshop.
  * Ruiz-Montiel . (2017) 8Ruiz-Montiel, M., Mandow, L. Pérez-de-la Cruz, JL.  2017\.  A temporal difference method for multi-objective reinforcement learning A temporal difference method for multi-objective reinforcement learning.  Neurocomputing26315–25.
  * Van Moffaert Nowé (2014) 7Van Moffaert, K. Nowé, A.  2014\.  Multi-objective reinforcement learning using sets of pareto dominating policies Multi-objective reinforcement learning using sets of pareto dominating policies.  The Journal of Machine Learning Research1513483–3512.
  * White (1977) white1977kernelsWhite, D.  1977\.  Kernels of preference structures Kernels of preference structures.  Econometrica: Journal of the Econometric Society91–100.
  * White (1982) white1982White, D.  1982\.  Multi-objective infinite-horizon discounted Markov decision processes Multi-objective infinite-horizon discounted markov decision processes.  Journal of mathematical analysis and applications892639–647.
  * Wiering De Jong (2007) 3Wiering, MA. De Jong, ED.  2007\.  Computing optimal stationary policies for multi-objective markov decision processes Computing optimal stationary policies for multi-objective markov decision processes.  2007 IEEE International Symposium on Approximate Dynamic Programming and Reinforcement Learning 2007 ieee international symposium on approximate dynamic programming and reinforcement learning ( 158–165).
  * Zorn (1935) zorn1935remarkZorn, M.  1935\.  A remark on method in transfinite algebra A remark on method in transfinite algebra.  Bulletin of the American Mathematical Society4110667–670.


# Maxwell relation between entropy and atom-atom pair correlation

Raymon S. Watson  Caleb Coleman  Karen V. Kheruntsyan  School of Mathematics
and Physics, University of Queensland, Brisbane, Queensland 4072, Australia

###### Abstract

For many-particle systems with short range interactions the local (same point)
particle-particle pair correlation function represents a thermodynamic
quantity that can be calculated using the Hellmann-Feynman theorem. Here we
exploit this property to derive a thermodynamic Maxwell relation between the
local pair correlation and the entropy of an ultracold Bose gas in one
dimension (1D). To demonstrate the utility of this Maxwell relation, we apply
it to the computational formalism of the stochastic projected Gross-Pitaevski
equation (SPGPE) to determine the entropy of a finite-temperature 1D Bose gas
from its atom-atom pair correlation function. Such a correlation function is
easy to compute numerically within the SPGPE and other formalisms, which is
unlike computing the entropy itself. Our calculations can be viewed as a
numerical experiment that serves as a proof-of-principle demonstration of an
experimental method to deduce the entropy of a quantum gas from the measured
atom-atom correlations.

_Introduction._ —Entropy plays a fundamental role in thermodynamics,
statistical mechanics, and quantum information theory. However, measuring it
directly or calculating it from the defining multiplicity function or the
density matrix of an interacting many-body system often represents a
formidable challenge. Instead, the entropy is often deduced from other
thermodynamic quantities (such as the heat capacity or the free energy) using
the relevant thermodynamic relations [1, 2]. Here, we derive and discuss a
thermodynamic Maxwell relation by which the entropy of a quantum many-body
system with short-range interactions can instead be related to, and hence
deduced from, the local particle-particle correlation function. Such a pair
correlation function characterizes the probability of two particles to be
found in the same position compared to uncorrelated particles and can often be
computed using methods of many-body and quantum field theory either
analytically or numerically [3, 4]. It can also be measured experimentally in,
e.g., ultracold quantum gas experiments using photoassociation [5].

The surprising aspect of the Maxwell relation between the pair correlation and
the entropy that we discuss here is that the pair correlation function is
usually viewed and treated as a typical two-body observable, whereas the
entropy is a thermodynamic quantity. However, what promotes the pair
correlation into a thermodynamic quantity as well is the fact that we are only
considering many-body systems with short-range interactions that can be
characterized by the $s$-wave scattering length [6, 7]. In this case, the
inter-particle interactions can be approximated by a simple contact
interaction, meaning that the two-body correlation function at zero inter-
particle separation indeed becomes a thermodynamic quantity. This was first
demonstrated by Lieb and Liniger in their seminal work on the exact Bethe
ansatz treatment of a uniform one-dimensional (1D) Bose gas with repulsive
contact (delta-function) interactions [8, *Lieb-Liniger-II]. By using the
Hellmann-Feynman theorem and differentiating the total ground state (zero-
temperature, $T\\!=\\!0$) energy of the gas with respect to the interaction
strength, Lieb and Liniger were able to calculate the mean interaction energy
component, which itself is proportional to the unnormalized pair correlation
function (see below).

The extension of the Hellmann-Feynman theorem to finite temperature systems
[4, 10], together with the exact Yang-Yang thermodynamic Bethe ansatz (TBA)
solution for the 1D Bose at finite temperature [11], was later utilized to
calculate the local pair correlation at any temperature and interaction
strength. In this case, the pair correlation function is related to the
partial derivative of the Helmholtz free energy with respect to the
interaction strength [4, 10, 12]. In this work, we take this relationship a
step further by combining it with the fact that the partial derivative of the
same Helmholtz free energy with respect to the temperature, on the other hand,
gives the entropy of the system according to the canonical ensemble formalism
of statistical mechanics. Therefore, by using the commutative property of
mixed second derivatives of the Helmholtz free energy (with respect to the
interaction strength and temperature) one obtains the Maxwell relation between
the pair correlation and the entropy that we discuss here.

As a practical application of this Maxwell relation, we utilize it for
computing the entropy of a weakly interacting 1D Bose gas in the
quasicondensate regime in the context of the classical $c$-field field
approach of the stochastic projected Gross-Pitaevskii equation (SPGPE) [13,
14, 15, 16]. The SPGPE is a well established and widely used numerical
approach for computing thermal equilibrium and dynamical properties of finite
temperature Bose gases, such as partially condensed Bose-Einstein condensates
in 2D and 3D , or phase-fluctuating quasicondensates in 1D [17]. Despite its
wide applicability to ultracold quantum gas systems, computing the entropy of
such systems within the SPGPE has not been accomplished prior to this work.
Here, we compute the entropy of a 1D quasicondensate within the SPGPE
approach; we restrict ourselves to the 1D Bose gas because of the availability
of the exact TBA solution for both the entropy and the pair correlation
function, to which we compare, and hence validate, our numerical SPGPE
results. However, we point out that the Maxwell relation derived and discussed
here is equally applicable to 2D and 3D systems, as well as to Fermi gas
systems with similar contact interactions.

_Lieb-Liniger model and two-particle correlation._ —We start by considering
the Lieb-Liniger model describing a uniform 1D gas of $N$ bosons of mass $m$
interacting via a pair-wise delta-function potential on a line of length $L$
with periodic boundary conditions and of linear density of $n=N/L$. In second-
quantized form, the Hamiltonian of such a system is given by

$\displaystyle\hat{H}=$ $\displaystyle-\frac{\hbar^{2}}{2m}\int
dx\,\hat{\Psi}^{\dagger}\frac{\partial^{2}\hat{\Psi}}{\partial
x^{2}}+\frac{\chi}{2}\int
dx\,\hat{\Psi}^{\dagger}\hat{\Psi}^{\dagger}\hat{\Psi}\hat{\Psi}.$ (1)

Here, $\hat{\Psi}^{\dagger}(x)$ and $\hat{\Psi}(x)$ are the bosonic field
creation and annihilation operators, whereas $\chi$ quantifies the strength of
boson-boson interactions, assumed to be repulsive ($\chi>0$). This interaction
strength can be expressed in terms of the 3D $s$-wave scattering length $a$
via $\chi\approx 2\hbar\omega_{\perp}a$ [18], away from a confinement induced
resonance, where $\omega_{\perp}$ is the frequency of the harmonic potential
in the transverse (tightly confined) dimension.

The normalized two-point particle-particle correlation is defined in terms of
the field operators as the expectation value of a normally-ordered product of
two density operators, $\hat{n}(x)=\hat{\Psi}^{\dagger}(x)\hat{\Psi}(x)$ and
$\hat{n}(x^{\prime})=\hat{\Psi}^{\dagger}(x^{\prime})\hat{\Psi}(x^{\prime})$:

$g^{(2)}(x,x^{\prime})=\frac{\langle\hat{\Psi}^{\dagger}(x)\hat{\Psi}^{\dagger}(x^{\prime})\hat{\Psi}(x^{\prime})\hat{\Psi}(x)\rangle}{n(x)n(x^{\prime})}.$
(2)

In other words, the pair correlation $g^{(2)}(x,x^{\prime})$ is a normalized
and normally-ordered density-density correlation function. It is normalized to
the product of mean densities $n(x)=\langle\hat{n}(x)\rangle$ and
$n(x^{\prime})=\langle\hat{n}(x^{\prime})\rangle$ at points $x$ and
$x^{\prime}$ so that for uncorrelated particles (with
$\langle\hat{\Psi}^{\dagger}(x)\hat{\Psi}^{\dagger}(x^{\prime})\hat{\Psi}(x^{\prime})\hat{\Psi}(x)\rangle=\langle\hat{\Psi}^{\dagger}(x)\hat{\Psi}(x)\rangle\langle\hat{\Psi}^{\dagger}(x^{\prime})\hat{\Psi}(x^{\prime})\rangle$),
one has $g^{(2)}(x,x^{\prime})=1$. For values of $g^{(2)}(x,x^{\prime})\neq
1$, the pair correlation characterizes an enhanced ($g^{(2)}(x,x^{\prime})>1$)
or suppressed ($g^{(2)}(x,x^{\prime})<1$) probability of finding two particles
at positions $x$ and $x^{\prime}$, respectively, compared to uncorrelated
particles.

Due to the translational invariance of the uniform system that we are
considering, where $n(x^{\prime})\\!=\\!n(x)\\!=\\!n$, the above pair
correlation $g^{(2)}(x,x^{\prime})$ can only depend on the relative distance
$|x-x^{\prime}|$ between the two particles, i.e.,
$g^{(2)}(x,x^{\prime})\\!=\\!g^{(2)}(|x-x^{\prime}|)$. The local or the same-
point ($x\\!=\\!x^{\prime}$) correlation then corresponds to

$g^{(2)}\equiv
g^{(2)}(0)=\frac{\langle\hat{\Psi}^{\dagger}(x)\hat{\Psi}^{\dagger}(x)\hat{\Psi}(x)\hat{\Psi}(x)\rangle}{n^{2}}.$
(3)

In the canonical formalism, the partition function $Z(T,N,L,\chi)$ can be
written in terms of either the Helmholtz free energy $F$ or the Hamiltonian
$\hat{H}$ via $Z\\!=\\!\exp(-F/k_{B}T)=\text{Tr}\exp(-\hat{H}/k_{B}T)$. By
differentiating the Helmholtz free energy $F(T,N,L,\chi)\\!=\\!-k_{B}T\ln Z$
with respect to the interaction strength $\chi$, at constant $N$, $L$, and
$T$, one finds that [4]

$\left(\frac{\partial
F}{\partial\chi}\right)_{T,N,L}\\!\\!=\frac{1}{Z}\text{Tr}\left(e^{-\hat{H}/k_{B}T}\frac{\partial\hat{H}}{\partial\chi}\right)=\frac{L}{2}\braket{\hat{\Psi}^{\dagger}\hat{\Psi}^{\dagger}\hat{\Psi}\hat{\Psi}},$
(4)

and hence

$g^{(2)}=\frac{2}{Ln^{2}}\left(\frac{\partial
F}{\partial\chi}\right)_{T,N,L}.$ (5)

This relationship between the local pair correlation and the Helmholtz free
energy is what was used in Ref. [4] to calculate the $g^{(2)}$ function using
the exact Yang-Yang TBA [11] solution for $F$, as a function of the
dimensionless interaction strength $\gamma$ and the dimensionless temperature
$\tau$, defined via

$\gamma=\frac{m\chi}{\hbar^{2}n},\qquad\tau=\frac{2mk_{B}T}{\hbar^{2}n^{2}}.$
(6)

We note here that these two dimensionless parameters completely characterize
the thermodynamic properties of a uniform 1D Bose gas [11, 4].

_Maxwell relation._ —We now recall that the partial derivative of the same
Helmholtz free energy with respect to temperature $T$ gives the entropy $S$ of
the system:

$S=-\left(\frac{\partial F}{\partial T}\right)_{\chi,L,N}.$ (7)

Combining Eqs. (5) and (7) with the the commutative property of mixed second
derivatives of $F$, i.e. $\frac{\partial}{\partial\chi}\left(\frac{\partial
F}{\partial T}\right)_{L,N}=\frac{\partial}{\partial T}\left(\frac{\partial
F}{\partial\chi}\right)_{L,N}$, leads to the following Maxwell relation:

$\boxed{\left(\frac{\partial
S}{\partial\chi}\right)_{T,L,N}=-\frac{Ln^{2}}{2}\left(\frac{\partial
g^{(2)}}{\partial T}\right)_{\chi,L,N}.}$ (8)

Equation (8) is one of this paper’s key results and implies that the entropy
of the gas can be calculated by integrating the partial derivative of the pair
correlation function $g^{(2)}$ with respect to $T$ over the interaction
strength $\chi$. More specifically, the entropy of the uniform 1D Bose at a
specific value of $\chi$ (and some fixed values of $T$, $L$, and $N$) can be
evaluated via

$\displaystyle S(\chi,$ $\displaystyle T,L,N)=S(\chi_{0},T,L,N)$
$\displaystyle-\frac{Ln^{2}}{2}\int_{\chi_{0}}^{\chi}\left(\frac{\partial
g^{(2)}(\chi^{\prime},T,L,N)}{\partial
T}\right)_{\chi^{\prime},L,N}d\chi^{\prime}.$ (9)

where $S(\chi_{0},T,L,N)$ serves the role of the integration constant and is
assumed to be known for the method to work. In practice, $S(\chi_{0},T,L,N)$
can be chosen to correspond to the entropy of an ideal ($\chi_{0}=0$) 1D Bose
gas, $S(0,T,L,N)$, which can indeed be calculated for any $T$ using standard
methods of statistical mechanics [1, 19].

As a simple analytic illustration of the utility of Eq. (9), we calculate the
entropy of a 1D Bose gas in highly degenerate, nearly ideal Bose gas regime
that can be treated using perturbation theory with respect to $\gamma$ (see
the results for the so-called decoherent quantum regime in Ref. [4, 19], valid
in the region $2\sqrt{\gamma}\ll\tau\ll 1$). In this regime, the pair
correlation function $g^{(2)}$, which was calculated in Ref. [4] without
resorting to the Helmholtz free energy, is given by

$g^{(2)}=2-4\gamma/\tau^{2}.$ (10)

Therefore, Eq. (9) yields the following result for the corresponding entropy:

$S=S_{\text{IBG}}-4k_{B}N\gamma^{2}/\tau^{3}.$ (11)

where $S_{\text{IBG}}=S(0,T,L,N)$ is entropy of the ideal 1D Bose gas at the
same temperature [19].

_Application to the SPGPE approach._ —We now illustrate the utility of Eq. (9)
using a numerically computed pair correlation function within the SPGPE
approach. This itself can be viewed as a numerical experiment demonstrating
how one can deduce the entropy of a quantum gas from the measured atom-atom
correlations.

The SPGPE approach (see Appendix) is a classical or $c$-field method for
computing thermal equilibrium and dynamical properties of degenerate Bose
gases at finite temperatures [20, 21, 13, 22, 14, 23, 24, 25, 17, 26, 27, 28,
29, 30]. Evolving the SPGPE from an arbitrary initial state, for sufficiently
long time (such that the memory of the initial state is lost), samples thermal
equilibrium configurations of the system from the grand-canonical ensemble.
These configurations are represented by stochastic realizations of the complex
$c$-fields $\Psi_{\mathbf{C}}(x,t)$, which we will denote as
$\Psi_{\mathbf{C}}(x)$ for thermal equilibrium states. In the SPGPE approach,
the pair correlation function $g^{(2)}$ is computed according to:

$g^{(2)}=\frac{\langle\Psi_{\mathbf{C}}^{*}(x)\Psi_{\mathbf{C}}^{*}(x)\Psi_{\mathbf{C}}(x)\Psi_{\mathbf{C}}(x)\rangle}{\langle\Psi_{\mathbf{C}}^{*}(x)\Psi_{\mathbf{C}}(x)\rangle^{2}},$
(12)

where the expectation values are over a large number of stochastic
realisations.

Figure 1: Local pair correlation $g^{(2)}$ for a 1D quasicondensate as a
function of the dimensionless interaction strength $\gamma$, for a fixed
dimensionless temperature $\tau=0.2$. The numerically computed data from the
SPGPE simulations are shown as circles and are compared to the exact TBA
result (squares), and the analytic approximation of Eq. (10) (dashes).

In this work, we are interested in the pair correlation function, $g^{(2)}$,
of a 1D quasicondensate at thermal equilibrium, in the parameter range
$\sqrt{\gamma}\ll\tau\ll 1$, where the $c$-field approach is valid [20, 30].
In Fig. 1 we show the dependence of this correlation function over a range of
the dimensionless interaction strength $\gamma\in[10^{-4},10^{-2}]$, for a
fixed value of the dimensionless temperature $\tau=0.2$, obtained from the
SPGPE approach. For comparison, we also show the exact TBA result (squares)
and the approximate analytic result of Eq. (10) (dashed line).

As we see, in the limit of an ideal Bose gas ($\gamma\to 0$) at finite
temperature, the pair correlation approaches the value of $g^{(2)}=2$, which
is the Hanbury Brown–Twiss effect of bosonic bunching ($g^{(2)}>1$) first
observed for photons from a chaotic (thermal) light source [31,
*HBT_1956_two_coherent, *HBT_1956_question] and more recently for an ultracold
atomic gas above the transition to a Bose-Einstein condensate [34, 35, 36]. It
corresponds to large density fluctuations and an enhanced probability of
detecting two indistinguishable bosons in the same position due to the
constructive interference of the respective probability amplitudes. As the
strength of the repulsive interaction increases, the said probability
decreases and manifests itself in the reduction of the value of $g^{(2)}$
below $2$ [4, 5]. At some finite, but still weak ($\gamma\\!\ll\\!1$)
interaction strength, the pair correlation crosses the coherent level of
$g^{(2)}\\!=\\!1$ characteristic of a phase-fluctuating quasicondensate with
suppressed density fluctuations, which itself shares the properties of a
weakly interacting Bose-Einstein condensate in the mean-field description [34,
35].

As the interaction strength increases further and approaches the regime of
very strong or hard-core repulsion ($\gamma\to\infty$), also known as the
Tonks-Girardeau limit of fermionization, the pair correlation reduces further
down to $g^{(2)}\to 0$ (see Ref. [4, 5]). This reduction reflects the fact
that the bosons are now strongly (anti)correlated and behave effectively as
fermions, wherein the bosonic hard-core repulsion mimics the fermionic Pauli
blocking. In the pair correlation function, such repulsion manifests itself as
antibunching ($g^{(2)}<1$), which itself is due to the destructive
interference of probability amplitudes for detecting two indistinguishable
fermions in the same position [36]. This regime, however, is beyond the
applicability of the SPGPE approximation ($\gamma\ll\\!1$,
$2\gamma\\!\ll\\!\tau\\!\ll\\!1$; see, e.g., Ref. [30, 19], and references
therein), and this is why in Fig. 1 we do not show the behaviour of the
$g^{(2)}$ beyond the weakly interacting regime of $\gamma\\!\ll\\!1$. Because
of the same approximate nature of the SPGPE approach, we see that the SPGPE
data for $g^{(2)}$, while agreeing well with the exact TBA results at small
$\gamma$, starts to deviate from the TBA results as $\gamma$ increases and
approaches its upper bound of $\gamma=0.01$, where the condition
$2\gamma\ll\tau$ is not well satisfied. Similarly, the analytic result of Eq.
(10) deviates from TBA to a larger extend as $\gamma$ is increased, because it
is applicable in an even more restricted region of
$2\sqrt{\gamma}\\!\ll\\!\tau\ll\\!1$ [4, 19].

Figure 2: Entropy of a 1D quasicondensate as a function of the dimensionless
interaction strength $\gamma$, relative to that of an ideal Bose gas at the
same temperature, $S(\gamma,\tau)-S_{\text{IBG}}(\tau)$, for $\tau=0.2$. The
SPGPE data computed using Eq. (9) is shown as circles and is compared to the
exact TBA data (squares), and the analytic approximation of Eq. (11) (dashes).

We next deduce the entropy of the 1D quasicondensate using Eq. (9) and the
SPGPE data for $g^{(2)}$, except that now the integration in Eq. (9) is done
numerically. To obtain the dependence of $S(\chi,T,L,N)$ on $\chi$ at a fixed
$T$, or rather on the dimensionless $\gamma$ at a fixed $\tau$, we convert Eq.
(9) to the dimensionless units and first evaluate the derivative
$\left(\partial
g^{(2)}(\gamma^{\prime},\tau)/\partial\tau\right)_{\gamma^{\prime}}$ using the
central difference scheme, for a range of values of $\gamma^{\prime}$. We next
evaluate the integral over $\gamma^{\prime}$ numerically, as a function of the
upper bound. The upper bound is scanned within $\gamma\in[10^{-4},10^{-2}]$,
while fixing the lower bound at $\gamma_{0}=10^{-6}$, which is sufficiently
low for the SPGPE results to be nearly identical to the IBG results at finite
$T$, for which $g^{(2)}=2$ and $S(\gamma_{0},T,L,N)\simeq
S_{\text{IBG}}(T,L,N)$. In Fig. 2 we show the SPGPE result for the entropy
difference per particle, $(S-S_{\text{IBG}})/k_{B}N$ obtained from the SPGPE
approach as a function of $\gamma$, for a fixed value of the dimensionless
temperature $\tau$. We again compare these data with the exact TBA result
(squares) and the analytic result of Eq. (11) (dashed line). As we see, the
entropy is maximal in the ideal Bose gas limit ($\gamma\to 0$), where
$g^{(2)}=2$ is also maximal, reflecting the large density fluctuations and
excess randomness (bunching) in the probability of finding two
indistinguishable bosons in the same position. As the strength of repulsive
interactions increases, the random density fluctuations become more and more
suppressed, which is also evident in the decrease of the entropy of the gas,
as expected. Overall, we see a good agreement between the SPGPE and TBA
results, particularly at small values of $\gamma$, where the condition of
validity of the SPGPE approximation is better satisfied; the agreement becomes
worse as $\gamma$ is increased, for the same reason as the discrepancy in the
behaviour of $g^{(2)}$ discussed earlier.

_Summary and outlook._ —We have derived and discussed a new Maxwell relation
by which the entropy of a quantum many-body system with contact two-body
interactions can be related to, and deduced from, the local two-particle
correlation function. We have validated this method though a numerical
experiment based on the $c$-field SPGPE simulations and computed—for the first
time (to the best of our knowledge) within the SPGPE formalism—the
thermodynamic entropy of a weakly interacting 1D Bose gas in the
quasicondensate regime.

The Maxwell relation derived here may find immediate applications, such as
measuring the entropy and deducing the thermodynamic equation of state, in
quantum gas experiments that take advantage of tuneable interparticle
interactions and measurements of atom-atom correlations using photoassociation
or in-situ imaging techniques in quantum gas microscope setups. It can also be
applied to other computational approaches, such as DMRG and phase space
stochastic gauge methods [37, 38], that are capable of computing particle-
particle correlations from the many-body wave-function or density matrix
formalisms, but struggle to compute the entropy from, e.g., the multiplicity
or the free energy.

Beyond quantum gas systems, the main results discussed here, Eqs. (8) and (9),
can aid the study of traditional condensed matter systems that are often
characterized through the static structure factor that describes scattering
experiments. Indeed, the static structure factor $S(\mathbf{k})$ is related to
the nonlocal pair correlation $g^{(2)}(\mathbf{r})$ via a Fourier transform,
$S(\mathbf{k})\\!=\\!1\\!+\\!n\int\\!d\mathbf{r}g^{(2)}(\mathbf{r})e^{-i\mathbf{k}\cdot\mathbf{r}}$.
Therefore, measurements or theoretical knowledge of $S(\mathbf{k})$ can be
used to deduce the local pair correlation $g^{(2)}(0)\equiv g^{(2)}$ by an
inverse Fourier transform, which can then be used for determining the
thermodynamic entropy from Eq. (9). Finally, one can envisage derivation of
related Maxwell relations for a large class of spin Hamiltonians in which: (a)
the spin-spin interaction term can be similarly calculated using the Hellmann-
Feynman theorem; and (b) the relevant spin-spin correlation function can be
experimentally measured.

###### Acknowledgements.

This work was supported through Australian Research Council Discovery Project
Grant No. DP190101515.

_Appendix: The Stochastic Projected Gross-Pitaevskii approach._ —In the SPGPE
approach [20, 22, 14], the quantum field operator $\hat{\Psi}(x,t)$ is
decomposed into two regions, a $c$-field region and an incoherent thermal
region. The $c$-field region contains highly occupied low-energy modes and is
described by a single complex-valued classical field $\Psi_{\mathbf{C}}(x,t)$.
The incoherent region, on the other hand, contains sparsely occupied high-
energy modes that act as an effective thermal bath, treated as static, with
temperature $T$ and chemical potential $\mu$ that governs the thermal average
number of particles in the system (in the $c$-field region). The boundary
between these two regions is defined by an appropriately chosen energy cutoff
$\epsilon_{\text{cut}}$ [39].

In this approach, the thermal equilibrium state of the system is prepared by
evolving the simple growth stochastic projected Gross-Pitaevskii equation
(SPGPE) for the complex $c$-field $\Psi_{\mathbf{C}}(x,t)$ [22, 14],

$\displaystyle\mathrm{d}\Psi_{\mathbf{C}}$
$\displaystyle(x,t)=\mathcal{P}^{(\mathbf{C})}\\!\left\\{-\frac{i}{\hbar}\mathcal{L}_{0}^{(\mathbf{C})}\Psi_{\mathbf{C}}(x,t)\,\mathrm{d}t\right.$
$\displaystyle\left.+\frac{\Gamma}{k_{B}T}(\mu-\mathcal{L}_{0}^{(\mathbf{C})})\Psi_{\mathbf{C}}(x,t)\,\mathrm{d}t+dW_{\Gamma}(x,t)\\!\right\\}.$
(13)

Here, the projection operator $\mathcal{P}^{(\mathbf{C})}\\{\cdot\\}$ sets up
the high-energy cutoff $\epsilon_{\mathrm{cut}}$, whereas $\Gamma$ is the so-
called growth rate responsible for the coupling between the $c$-field and the
effective reservoir (served by the incoherent region). In addition,
$\mathcal{L}_{0}^{(\mathbf{C})}$ is the Gross-Pitaevskii operator defined by

$\mathcal{L}_{0}^{(\mathbf{C})}=-\frac{\hbar^{2}}{2m}\frac{\partial^{2}}{\partial
x^{2}}+V(x,t)+\chi|\Psi_{\mathbf{C}}(x,t)|^{2},$ (14)

where $V(x,t)$ is the external trapping potential, if any. The last term,
$dW_{\Gamma}(x,t)$, in Eq. (Maxwell relation between entropy and atom-atom
pair correlation) is a complex-valued stochastic white noise term with the
following nonzero correlation:

$\langle
dW_{\Gamma}^{*}(x,t)dW_{\Gamma}(x^{\prime},t)\rangle=2\Gamma\delta(x-x^{\prime})dt.$
(15)

As we mentioned in the main text, the stochastic realisations of the $c$-field
$\Psi_{\mathbf{C}}(x,t)$ prepared via the SPGPE after a sufficiently long
evolution time sample the grand-canonical ensemble of thermal equilibrium
states of the system. These stochastic realisations can then be evolved in
real time according to the mean-field projected Gross-Pitaevskii equation
[22], following a certain out-of-equilibrium protocol. This would then
represent real-time dynamical evolution of the system starting from an initial
thermal equilibrium state. In this work, however, we do not simulate any real-
time dynamics; instead, we are interested in the pair correlation function,
$g^{(2)}$, of a 1D quasicondensate at thermal equilibrium. Accordingly, our
simulations involve only the SPGPE stage.

Denoting the SPGPE realizations of the complex $c$-field
$\Psi_{\mathbf{C}}(x,t)$ after a sufficiently long evolution time via
$\Psi_{\mathbf{C}}(x)$, the thermal equilibrium values of physical observables
are then calculated in terms expectation values of products of
$\Psi_{\mathbf{C}}(x)$ and its complex conjugate $\Psi_{\mathbf{C}}^{*}(x)$
over a large number of stochastic realizations. This is much in the same way
as calculating the same observables in terms of expectation values over
normally-ordered products of quantum field operators $\hat{\Psi}(x)$ and
$\hat{\Psi}^{\dagger}(x)$, except that their non-commuting nature is ignored.
As an example, the particle number density
$n(x)=\langle\hat{\Psi}^{\dagger}(x)\hat{\Psi}(x)\rangle$ in the SPGPE
approach is calculated as
$n(x)=\langle\Psi_{\mathbf{C}}^{*}(x)\Psi_{\mathbf{C}}(x)\rangle$, where the
brackets $\langle{...}\rangle$ refer to ensemble averaging over a large number
of stochastic trajectories; similarly the pair correlation function $g^{(2)}$
can be computed via Eq. (12) of the main text.

## References

  * Huang [1987] K. Huang,  _Statistical Mechanics, 2nd Ed._ (John Wiley & Sons, New York, 1987).
  * Callen [1985] H. B. Callen,  _Thermodynamics and an Introduction to Thermostatistics_ (John Wiley & Sons, New York, 1985).
  * Gangardt and Shlyapnikov [2003] D. M. Gangardt and G. V. Shlyapnikov, Stability and phase coherence of trapped 1D Bose gases, Phys. Rev. Lett. 90, 010401 (2003).
  * Kheruntsyan  _et al._ [2003] K. V. Kheruntsyan, D. M. Gangardt, P. D. Drummond, and G. V. Shlyapnikov, Pair correlations in a finite-temperature 1D Bose gas, Phys. Rev. Lett. 91, 040403 (2003).
  * Kinoshita  _et al._ [2005] T. Kinoshita, T. Wenger, and D. S. Weiss, Local pair correlations in one-dimensional Bose gases, Phys. Rev. Lett. 95, 190406 (2005).
  * Pethick and Smith [2008] C. Pethick and H. Smith,  _Bose-Einstein condensation in dilute gases_ , 2nd ed. (Cambridge University Press, Cambridge, UK ; New York, 2008).
  * Pitaevskii and Stringari [2016] L. P. Pitaevskii and S. Stringari,  _Bose-Einstein condensation and superfluidity_ , International series of monographs on physics, V. 164 (Oxford University Press, Oxford, 2016).
  * Lieb and Liniger [1963] E. H. Lieb and W. Liniger, Exact analysis of an interacting Bose gas. I. The general solution and the ground state, Phys. Rev. 130, 1605 (1963).
  * Lieb [1963] E. H. Lieb, Exact analysis of an interacting Bose gas. II. The excitation spectrum, Phys. Rev. 130, 1616 (1963).
  * Kheruntsyan  _et al._ [2005] K. V. Kheruntsyan, D. M. Gangardt, P. D. Drummond, and G. V. Shlyapnikov, Finite-temperature correlations and density profiles of an inhomogeneous interacting one-dimensional Bose gas, Phys. Rev. A 71, 053615 (2005).
  * Yang and Yang [1969] C.-N. Yang and C. P. Yang, Thermodynamics of a one-dimensional system of bosons with repulsive delta-function interaction, Journal of Mathematical Physics 10, 1115 (1969).
  * Kerr and Kheruntsyan [2024] M. L. Kerr and K. V. Kheruntsyan, How to measure the free energy and partition function from atom-atom correlations, Phys. Rev. A 109, 033308 (2024).
  * Bradley  _et al._ [2005] A. S. Bradley, P. B. Blakie, and C. W. Gardiner, Properties of the stochastic Gross–Pitaevskii equation: finite temperature Ehrenfest relations and the optimal plane wave representation, Journal of Physics B: Atomic, Molecular and Optical Physics 38, 4259 (2005).
  * Rooney  _et al._ [2012] S. J. Rooney, P. B. Blakie, and A. S. Bradley, Stochastic projected Gross-Pitaevskii equation, Phys. Rev. A 86, 053634 (2012).
  * Gardiner  _et al._ [2002] C. Gardiner, J. Anglin, and T. Fudge, The stochastic Gross-Pitaevskii equation, Journal of Physics B: Atomic, Molecular and Optical Physics 35, 1555 (2002).
  * Gardiner and Davis [2003] C. Gardiner and M. Davis, The stochastic Gross–Pitaevskii equation: II, Journal of Physics B: Atomic, Molecular and Optical Physics 36, 4731 (2003).
  * Bradley  _et al._ [2015] A. S. Bradley, S. J. Rooney, and R. G. McDonald, Low-dimensional stochastic projected Gross-Pitaevskii equation, Phys. Rev. A 92, 033631 (2015).
  * Olshanii [1998] M. Olshanii, Atomic scattering in the presence of an external confinement and a gas of impenetrable bosons, Phys. Rev. Lett. 81, 938 (1998).
  * Kerr  _et al._ [2024] M. Kerr, G. De Rosi, and K. Kheruntsyan, Analytic thermodynamic properties of the Lieb-Liniger gas, arXiv:2404.06092 10.48550/arXiv.2404.06092 (2024).
  * Castin  _et al._ [2000] Y. Castin, R. Dum, E. Mandonnet, A. Minguzzi, and I. Carusotto, Coherence properties of a continuous atom laser, Journal of Modern Optics 47, 2671 (2000).
  * Sinatra  _et al._ [2001] A. Sinatra, C. Lobo, and Y. Castin, Classical-Field Method for Time Dependent Bose-Einstein Condensed Gases, Phys. Rev. Lett. 87, 210404 (2001).
  * Blakie  _et al._ [2008] P. B. Blakie, A. Bradley, M. Davis, R. Ballagh, and C. Gardiner, Dynamics and statistical mechanics of ultra-cold Bose gases using c-field techniques, Advances in Physics 57, 363 (2008).
  * Stimming  _et al._ [2010] H.-P. Stimming, N. J. Mauser, J. Schmiedmayer, and I. E. Mazets, Fluctuations and Stochastic Processes in One-Dimensional Many-Body Quantum Systems, Phys. Rev. Lett. 105, 015301 (2010).
  * Grisins and Mazets [2011] P. Grisins and I. E. Mazets, Thermalization in a one-dimensional integrable system, Phys. Rev. A 84, 053635 (2011).
  * Stimming  _et al._ [2011] H.-P. Stimming, N. J. Mauser, J. Schmiedmayer, and I. E. Mazets, Dephasing in coherently split quasicondensates, Phys. Rev. A 83, 023618 (2011).
  * Bouchoule  _et al._ [2016] I. Bouchoule, S. S. Szigeti, M. J. Davis, and K. V. Kheruntsyan, Finite-temperature hydrodynamics for one-dimensional Bose gases: Breathing-mode oscillations as a case study, Phys. Rev. A 94, 051602 (2016).
  * Pietraszewicz and Deuar [2018] J. Pietraszewicz and P. Deuar, Classical fields in the one-dimensional Bose gas: Applicability and determination of the optimal cutoff, Phys. Rev. A 98, 023622 (2018).
  * Thomas  _et al._ [2021] K. F. Thomas, M. J. Davis, and K. V. Kheruntsyan, Thermalization of a quantum Newton’s cradle in a one-dimensional quasicondensate, Phys. Rev. A 103, 023315 (2021).
  * Bayocboc  _et al._ [2022] F. A. Bayocboc, M. J. Davis, and K. V. Kheruntsyan, Dynamics of thermalization of two tunnel-coupled one-dimensional quasicondensates, Phys. Rev. A 106, 023320 (2022).
  * Bayocboc and Kheruntsyan [2023] F. A. Bayocboc and K. V. Kheruntsyan, Frequency beating and damping of breathing oscillations of a harmonically trapped one-dimensional quasicondensate, Comptes Rendus. Physique 10.5802/crphys.131 (2023).
  * Hanbury Brown and Twiss [1956a] R. Hanbury Brown and R. Q. Twiss, A Test of a New Type of Stellar Interferometer on Sirius, Nature 178, 1046 (1956a).
  * Hanbury Brown and Twiss [1956b] R. Hanbury Brown and R. Q. Twiss, Correlation between Photons in two Coherent Beams of Light, Nature 177, 27 (1956b).
  * Hanbury Brown and Twiss [1956c] R. Hanbury Brown and R. Q. Twiss, The question of correlation between photons in coherent light rays, Nature 178, 1447 (1956c).
  * Öttl  _et al._ [2005] A. Öttl, S. Ritter, M. Köhl, and T. Esslinger, Correlations and counting statistics of an atom laser, Phys. Rev. Lett. 95, 090404 (2005).
  * Schellekens  _et al._ [2005] M. Schellekens, R. Hoppeler, A. Perrin, J. V. Gomes, D. Boiron, A. Aspect, and C. I. Westbrook, Hanbury brown twiss effect for ultracold quantum gases, Science 310, 648 (2005).
  * Jeltes  _et al._ [2007] T. Jeltes, J. M. McNamara, W. Hogervorst, W. Vassen, V. Krachmalnicoff, M. Schellekens, A. Perrin, H. Chang, D. Boiron, A. Aspect, and C. I. Westbrook, Comparison of the Hanbury Brown–Twiss effect for bosons and fermions, Nature 445, 402 (2007).
  * Drummond  _et al._ [2004] P. D. Drummond, P. Deuar, and K. V. Kheruntsyan, Canonical bose gas simulations with stochastic gauges, Phys. Rev. Lett. 92, 040405 (2004).
  * Deuar  _et al._ [2009] P. Deuar, A. G. Sykes, D. M. Gangardt, M. J. Davis, P. D. Drummond, and K. V. Kheruntsyan, Nonlocal pair correlations in the one-dimensional bose gas at finite temperature, Phys. Rev. A 79, 043619 (2009).
  * [39] For the results presented in Figs. 1 and 2 of the main text, the energy cut-off, $\epsilon_{cut}$, was chosen such that the occupancy of the highest energy modes in plane wave basis was approximately one.