#  On the Limited Representational Power of Value Functions and its Links to
Statistical (In)Efficiency

David Cheikhi
<EMAIL_ADDRESS>
Graduate School of Business
Columbia University &Daniel Russo
Graduate School of Business
Columbia University

###### Abstract

Identifying the trade-offs between model-based and model-free methods is a
central question in reinforcement learning. Value-based methods offer
substantial computational advantages and are sometimes just as statistically
efficient as model-based methods. However, focusing on the core problem of
policy evaluation, we show information about the transition dynamics may be
impossible to represent in the space of value functions. We explore this
through a series of case studies focused on structures that arises in many
important problems. In several, there is no information loss and value-based
methods are as statistically efficient as model based ones. In other closely-
related examples, information loss is severe and value-based methods are
severely outperformed. A deeper investigation points to the limitations of the
representational power as the driver of the inefficiency, as opposed to
failure in algorithm design.

##  1 Introduction

Policy evaluation is central to sequential decision making. Two main
frameworks compete to tackle this problem. Model based methods start by
learning the underlying dynamics of the problem (the model) and output a
value-to-go estimate consistent with this learned model. While this approach
enjoys nice theoretical properties (see e.g. Chapter 7 of Moerland et al.
(2023)), computing the value-to-go at a single state typically requires
computationally expensive forward simulation of the model. At the other end of
the spectrum, model-free methods (or value-based) methods directly estimate
the value function that fits data best, skipping the need for the difficult
step of computing the value function corresponding to a model. As a result,
direct model-free estimation of value functions is ubiquitous in reinforcement
learning.

When they work well, model-free approaches to value function estimation can be
statistically and computationally efficient while sidestepping the need to
estimate details of an underlying model. Unfortunately, model-free algorithms
are sometimes sample inefficient.

#### Puzzling case-studies on the statistical efficiency of model-free
methods.

In studying this sample efficiency tradeoff in simple examples, we encounter
puzzling competing evidence. Consider Figure 1. It compares the error of
least-squares temporal difference learning (Bradtke & Barto, 1996) against
simple model-based least-squares baseline in three cases. Section 5 provides
further details. Subfigure 1(a) looks at a linear quadratic control. As in Tu
& Recht (2018), we see LSTD is severely outperformed by model-based. Recht
(2019) conjectures that the issue is that model-based algorithms leverage
vector state observations, whereas LSTD collapses these into scalar
observations (of reward plus value-to-go). Subfigure 1(b) raises doubt about
this interpretation. LSTD is efficient again if we adjust the linear-quadratic
setting so that rewards are linear, rather than quadratic, functions of state.
Why is the sample-efficiency so impacted by this change to the problem?

In Subfigure 1(c), we restrict the model dynamics to be diagonal. This
structure is motivated by problems with decoupled structure — which we study
in detail in Section 4 and we explain is a very important feature of many
practical problems. We see that model-based are again far superior.

$0$$5$$10$$15$$20$$0$$1{,}000$$2{,}000$Dimension $d$MSE
$\mathbb{E}\left[\|\hat{\beta}-\beta\|^{2}\right]$LSTDModel Based (a) General
dynamics
Quadratic rewards

$0$$20$$40$$0$$100$$200$$300$Dimension $d$LSTDModel Based (b) General dynamics
Linear rewards

$0$$20$$40$$0$$100$$200$$300$Dimension $d$LSTDModel Based (c) Diagonal
dynamics
Linear rewards

Figure 1: Mean-squared error of LSTD and model based estimators when dynamics
are linear and rewards are quadratic (1(a)), when rewards are simplified to be
linear (1(b)) and when dynamics are further simplified to be diagonal (1(c)).

All scenarios may initially seem quite favorable to model-free methods, since
the structure of the model implies a simple structure to the true value
function. Yet (batch) LSTD is grossly sample inefficient in two cases; in one
other, it is just as efficient as model-based methods.

#### Limited representational power of value functions.

We offer an explanation of the puzzling scenarios plotted above. The issue is
not with LSTD itself, but with a loss of information when translating a
simplifying structure of the model dynamics to an associated (simplifying)
structure of the value-function representation.

> _Model free estimation algorithms suffer inherent information loss when
> information about the transition dynamics cannot be encoded in a value
> function representation._

To understand this precisely, it is helpful to abstract away from the details
of LSTD. We view it as some rule for estimating value functions based on data.
When specific problem structures are known, its behavior can be improved by
supplying a specialized value function representation, e.g. by taking
$\mathbb{V}$ below to consist of quadratic value functions.

######  Definition 1.1.

A model-free value function estimation algorithm (e.g. LSTD) is a function
that maps a class of value functions $\mathbb{V}$ and a dataset
$D=\\{(s_{i},r_{i},s^{\prime}_{i}):i=1,\ldots,n\\}$ consisting of state,
reward, next-state tuples, to an estimated value function
$\hat{V}\in\mathbb{V}$.

The next definition considers the conversion from a class of MRP models
$\mathbb{M}$ to the induced class of value functions
$\mathbb{V}=\\{V_{M}:M\in\mathbb{M}\\}$ where $V_{M}$ is the value function
associated with model $M$. We say that the value function representations lose
information about the model structure if $\mathbb{V}$ is also induced by a
larger class of models $\mathfrak{M}$. Roughly, a generic algorithm like LSTD
cannot ‘know’ or exploit a structure of the class of models $\mathbb{M}$ that
is not present in $\mathfrak{M}$ .

######  Definition 1.2 (Loss of information).

For a class of models $\mathbb{M}$, we say there is a loss of information in
the space of value functions if there exists a larger set of models
$\mathfrak{M}$, that is $\mathbb{M}\subsetneq\mathfrak{M}$, such that
$\mathbb{M}$ and $\mathfrak{M}$ have the same class of value functions:

$\\{V_{M};M\in\mathbb{M}\\}=\\{V_{M};M\in\mathfrak{M}\\}.$

A deeper look into the examples in Figure 1 seems to confirm that information-
loss is the true driver of LSTD’s poor performance. In fact, in both the
diagonal dynamics case in Figure 1(c) and the linear-quadratic example in
Figure 1(a), we explain that LSTD is _equivalent_ to a model-based least-
squares estimation procedure that operates in a much larger space of models
that shares the same value-function representation, like $\mathfrak{M}$ in
Definition 1.2. Therefore, our theory offers an alternative explanation to the
findings of Tu & Recht (2019).

As depicted in Table 1, the presence of severe information loss predicts the
relative statistical efficiency or inefficiency of model-free methods in five
important examples. In addition to the linear problems in Figure 1, we also
study policy evaluation in problems with many state components that evolve
independently. This structure is ubiquitous in operations research, see e.g.
Chapter 6.2 of Bertsekas (2005), and also appears naturally in other domains
like recommender systems (Maystre et al., 2023). The very poor performance of
generic model-free algorithms on simple variants of such problems is
disconcerting.

Model class |  Value functions consistent with model class |  Models consistent with value function class |  No info. loss |  LSTD is data efficient
---|---|---|---|---
All MRPs |  All functions |  All MRPs |  ✓ |  ✓
Decoupled transitions; additive rewards |  Linearly separable functions |  MRPs with arbitrary transition structure |  ✗ |  ✗
_Decoupled_ linear dynamics; linear rewards |  Linear functions |  MRPs with _general_ linear dynamics and rewards |  ✗ |  ✗
General linear dynamics; linear rewards |  Linear functions |  (essentially) MRPs with general linear transition structure |  ✓ |  ✓
LQR: general linear dynamics; _quadratic_ rewards |  Quadratic functions |  A class of MRPs with $\Theta(n^{4})$ free parameters (instead of $\Theta(n^{2})$). |  ✗ |  ✗
Table 1: In the settings studied throughout this paper, there is a perfect
correlation between LSTD’s relative statistical inefficiency and whether there
is los of information in the space of value functions.

It is worth stressing that all of our examples are purposefully stylized and
meant to serve as a sanity check on the performance of model-free value
function estimation procedures. It is usually easy to modify algorithms to
perform well on a particular example, but it is unfortunate that these case-
by-case modifications are necessary.

##  2 Related work

Results about sample efficiency (or inefficiency) of both model-free (Jin et
al., 2020; Chen et al., 2021a) and model-based (Kearns & Singh, 2002; Auer et
al., 2008; Azar et al., 2017) are numerous in the literature. In specific
settings, the statistical efficiency of model-free and model-based methods
have been compared, showing there is nearly no gap between the two frameworks
in the tabular case (Zanette & Brunskill, 2019; Jin et al., 2018) but that
such a gap exists in the LQR setting (Tu & Recht, 2019). The results from
these works are setting-specific and provide little intuition on what
characteristic of the problem at hand drives the performance discrepancies in
Figure 1.

Sun et al. (2019) studies this issue in the full RL problem, where good
performance requires exploration and planning and not just policy evaluation.
They show there exist a setting in which any model-free method requires
exponentially more samples to match the performance of a model-based method.
While superficially similar, our paper offers insights that are very different
and complementary. Our definition of model-free policy evaluation methods (Def
1.1) restricts what problem structures are known apriori to the learner,
leading to our emphasis on information-loss due to value-based representation.
Roughly speaking, we’re worried that a sound value-function based
representation is necessarily “too flexible” to reflect structural constraints
on the transition dynamics. The definition in Sun et al. (2019) instead
restricts what model-free methods can observe about the dataset itself if the
value-function class is _insufficiently flexible_. In particular, their model-
free methods only have access to the image of states under value functions in
some class. Their counter-example constructs a setting where important
features of the data are lost as a result. This definition of model-free
methods is interesting, but is vacuous in the settings discussed in Table 1,
since for the data could be perfectly recovered from sufficiently many value
function evaluations.

Zhu et al. (2023a) and Dong et al. (2020) exhibit settings where value
functions require very complex representations even though the the transition
dynamics are simple. They argue this makes model-free methods inefficient.
This is orthogonal to the limitations in representation power described in
this work which refers to what information about the model space can be
inferred from the sole knowledge of the space of value functions. All of our
counter-examples stress the potential inefficiency of value-based methods even
when the value-function has known and simple representation.

Other works study benefits or shortcomings of both types of methods, such as
robustness to misspecification (Clavera et al., 2018; Jin et al., 2020; Wang
et al., 2020; Zhu et al., 2023b) or safety (Berkenkamp et al., 2017; Xu et
al., 2023).

Attempting to reconcile the benefits of model-free methods with the
statistical efficiency of model-based methods, multiple works have explored
using a learned model as a generator to enhance statistical efficiency of
model-free methods, both theoretically (Feinberg et al., 2018; Buckman et al.,
2018; Janner et al., 2019) and empirically (Lu et al., 2024; Young et al.,
2022).

##  3 Problem formulation

A _trajectory_ in a Markov Reward Process (MRP) is a Markovian sequence
$\tau=(S^{(0)},R^{(1)},S^{(1)},R^{(2)},S^{(2)},\dots),$ consisting of a
sequence of states $(S^{(t)})_{t}\subset\mathcal{S}$ and rewards
$(R^{(t)})_{t}\subset\mathbb{R}$. MRPs are the common framework for policy
evaluation: evaluating a fixed policy in a Markov Decision Process can be cast
as evaluating the value function of a MRP. The law of a Markov Reward Process
is specified by the tuple $\mathcal{M}=(\mathcal{S},P,R)$ consisting of a
state space, a transition kernel and a reward distribution. Here $P$ is a
transition kernel over the state space $\mathcal{S}$, specifying a probability
$P(s^{\prime}\mid s)$ of transitioning from $s$ to $s^{\prime}$. The object
$R$ specifies the distribution of rewards conditioned on a state transition as
$R(dr|s,s^{\prime})=\mathbb{P}(R^{(t)}=dr\mid
S^{(t)}=s,S^{(t+1)}=s^{\prime})$. Throughout we use the notation
$r(s,s^{\prime})$ for the mean of $R(\cdot|s,s^{\prime})$. For a given
discount factor $0<\gamma\leq 1$, the value function

$\displaystyle V(s)=\mathbb{E}\left[\sum_{t=1}^{\infty}\gamma^{t}R^{(t)}\mid
S^{(0)}=s\right]=\mathbb{E}\left[\sum_{t=1}^{\infty}\gamma^{t}r\left(S^{(t)},S^{(t+1)}\right)\mid
S^{(0)}=s\right]$

specifies the expected sum of discounted rewards along a trajectory. We focus
on the problem of estimating the value function $V$ given a dataset of
transitions $\mathcal{D}=\left\\{\left((S^{(t)},R^{(t)},S^{(t)}_{\rm
next}\right)\right\\}_{t=1,\dots,n}$ where $S^{(t)}_{\rm next}\sim
P(\cdot|S^{(t)})$ and $R^{(t)}\sim R(\cdot|S^{(t)},S^{(t+1)})$. This allows
for the case where $S^{(t)}$ are generated from a single trajectory (in which
case $S^{(t+1)}=S^{(t)}_{\rm next}$), from multiple trajectories or drawn
i.i.d. from the occupancy measure.

##  4 Markov Reward Processes with Decoupled Transition Structure

###  4.1 On the importance of decoupled structures

The curse of dimensionality is a major barrier in Reinforcement Learning as
the number of parameters that need to be learned typically scales
exponentially with the dimension of the state space. Thankfully, it is common
that all parts of the state cannot interact arbitrarily in practical problems.
For instance, Maystre et al. (2023) model recommender systems where a
component of the user’s state represents their habitual engagement user with
specific audio items (e.g podcasts). The presence of hundreds of thousands of
items means state variables have hundreds of thousands of components.
Thanfuklly recommending a new podcast might primarily affect the few
components related to the user’s listening habit with that podcast.

Given the importance and omnipresence of these problems in practice, a large
literature has studied problems having some form of decoupling or weak
coupling. Factored Markov Decision Processes (Kearns & Koller, 1999) or weakly
coupled Markov Decision Processes (Hawkins, 2003) are two common frameworks
for capturing such structure. Examples of real-life problems cast in these
frameworks include inventory management (Turken et al., 2012; Chen et al.,
2021b), queuing (Chen et al., 2021b), resource allocation (Tesauro et al.,
2005), or restless bandits (Weber & Weiss, 1990), personalized health
interventions (Baek et al., 2023), and many others.

In what follows, we restrict our study to the most elementary version of this
structure where all components are perfectly independent and the rewards can
be linearly decomposed. Even though some weakly coupled problems can be
tackled by solving a series of fully decoupled problems as proposed by Le et
al. (2019), we do not claim to exactly capture practical problems through this
construction. Instead, we view decoupled MRPs as a minimal example capturing
the essence of those problems. That LSTD fails to be statistically efficient
even in this case is noteworthy. Given the simplicity of our example, we
expect that the exhibited failures will continue or be made worse in more
complex settings.

###  4.2 Definition

A $d$-decoupled MRP $\mathcal{M}$ is a system where the state and reward are
respectively the concatenation of the states and the sum of rewards of $d$
MRPs $\mathcal{M}_{i}=(\mathcal{S}_{i},P_{i},R_{i})$ evolving independently.

######  Definition 4.1 (Decoupled MRP).

A MRP $\mathcal{M}=(\mathcal{S},P,R)$ is said to be $d-decoupled$ if

  * •

There exists $\mathcal{S}_{1},\dots,\mathcal{S}_{d}$ such that
$\mathcal{S}=\mathcal{S}_{1}\times\dots\times\mathcal{S}_{d}$.

  * •

There exists transition kernels $P_{1},\dots P_{d}$ and reward kernels
$R_{1},\dots R_{d}$ such that for all states $s,s^{\prime}$,
$P(s^{\prime}|s)=\prod_{i=1}^{d}P_{i}(s_{i}^{\prime}|s_{i})$ and
$r(s,s^{\prime})=\sum_{i=1}^{d}r_{i}(s_{i},s_{i}^{\prime})$.

In the rest of this section, we restrict ourselves to the case of tabular
decoupled MRPs, that is each $\mathcal{S}_{i}$ is finite. The following
property of decoupled MRPs is central to the use of value-based methods in
this setting: the value function of a decoupled MRP is linearly separable,
that is there exists $V_{1},\dots,V_{d}$ such that

$V(s)=\sum_{i=1}^{d}V_{i}(s_{i})\quad\text{for all }s\in\mathcal{S}.$ (1)

Let $\mathbb{M}_{D}$ denote the set of decoupled MRPs and $\mathbb{V}_{D}$
denote the set of separable value functions, that is the value functions $V$
that verify (1) for some $V_{1},\dots,V_{d}$. Then $\mathbb{V}_{D}$ is exactly
the class of value functions induced by decoupled MRPs.

######  Proposition 4.2.

The class of value functions of decoupled MRPs is the set of separable value
functions: $\\{V_{M}|M\in\mathbb{M}_{D}\\}=\mathbb{V}_{D}$.

###### Proof.

$\\{V_{M}|M\in\mathbb{M}_{D}\\}\subset\mathbb{V}_{D}$ : Let $\mathcal{M}$ be a
decoupled MRP, concatenation of $\mathcal{M}_{1},\dots,\mathcal{M}_{d}$ with
value functions $V_{1}\dots,V_{d}$, respectively. Then
$V(s)=\sum_{i=1}^{d}V_{i}(s_{i})$ for all $s\in\mathcal{S}$.

$\mathbb{V}_{D}\subset\\{V_{M}|M\in\mathbb{M}_{D}\\}$: Let
$V\in\mathbb{V}_{D}$ and $V_{1},\dots,V_{d}$ be such that (1) is verified.
There exists MRPs
$\left(\mathcal{M}_{i}=(\mathcal{S}_{i},P_{i},R_{i})\right)_{i=1,\dots,d}$
with value function $V_{i}$. The decoupled MRP obtained by concatenating
$\left(\mathcal{M}_{i}\right)_{i=1,\dots,d}$ has value function $V$. ∎

###  4.3 Decoupled structure cannot be encoded in the value space

Proposition 4.2 shows that the class of separable value functions is exactly
the right class of value functions for decoupled MRPs. However, this is not
sufficient for the decoupled structure of the transitions to be encoded in the
space of value functions, as the following result shows.

######  Theorem 4.3 (Value representation loses information).

$\left(\mathbb{M}_{D}\subsetneq\\{M:V_{M}\in\mathbb{V}_{D}\\}\right)$
For any separable value function $V\in\mathbb{V}_{D}$ and any transition
kernel $P\in\mathbb{R}^{n^{d}\times n^{d}}$ over states $\mathcal{S}$, there
exists a vector of average rewards $r$ such that the value function of any MRP
with transition kernel $P$ and average rewards $r$ is separable.

###### Proof.

Let $V\in\mathbb{V}_{D}$ and let $P\in\mathbb{R}^{n^{d}\times n^{d}}$ be any
transition kernel. Setting $r=(I-\gamma P)V$ ensures that the value function
of the MRP with transition kernel $P$ and linear reward $r$ is exactly $V$. ∎

Theorem 4.3 shows that even if the set of value functions has been narrowed
down as much as possible, this same class of value function is shared by
another class of models whose dimension is exponentially larger.

###  4.4 Statistical inefficiency of LSTD

We empirically demonstrate the inefficiency of LSTD on this type of problem,
we consider $d$ tabular MRP $\mathcal{M}_{i}$ with
$\mathcal{S}_{i}=\\{1,\dots,N\\}$. We then create a sequence of decoupled MRPs
$(\tilde{\mathcal{M}}_{k})_{k}$ of increasing dimension $k=1,\dots,d$ by
having $\tilde{S}^{(t)}_{k}=(S_{1}^{(t)},\dots,S_{k}^{(t)})$ and
$\tilde{R}_{k}^{(t)}\sim\mathcal{N}\left(\sum_{i=1}^{k}r_{i}\left(S_{i}^{(t)}\right),1\right)$
where $S_{i}^{(t)}$ is the state at time $t$ in $\mathcal{M}_{i}$ and
$r_{i}(s)$ is the expected reward when at state $s$ in $\mathcal{M}_{i}$.

We consider the ratio between the Mean Squared Error (MSE)
$\mathbb{E}\left[\|\hat{V}(s)-V(s)\|^{2}\right]$ under model-free and model-
based estimates. Figure 2 shows the evolution of this ratio as the number of
components $k$ grows. Those experiments show that the gap in number of samples
required by model-based and LSTD grows rapidly with the number of components.
Subfigure 2(a) displays the ratio when the expectation is taken uniformly over
$\mathcal{S}$ to capture off-policy performance and Subfigure 2(b) when the
expectation is taken uniformly over the dataset to capture on-policy
performance.

$0$$50$$100$$150$$200$$0$$10$$20$$30$Dimension $d$Ratio of MSE
$\frac{\mathbb{E}\left[\|\hat{V}_{\rm
LSTD}(s)-V(s)\|^{2}\right]}{\mathbb{E}\left[\|\hat{V}_{\rm
MB}(s)-V(s)\|^{2}\right]}$Empirical ratio (a) $s$ is chosen uniformly at
random over $\mathcal{S}$

$0$$50$$100$$150$$200$$0$$5$$10$$15$Dimension $d$Empirical ratio (b) $s$ is
chosen uniformly at random in the dataset

Figure 2: Ratio of the mean-squared error estimation of LSTD and model based
for a randomly generated decoupled MRP, using $\gamma=0.9,N=5$. Here each
sample $\hat{\beta}$ was obtained using a trajectory of length $n=1000$ and
$80$ such samples were averaged to obtain an estimation of the MSE.

It is reasonable to think that the impossibility to represent the decoupled
structure in the value space, as described in Theorem 4.3, is the root of this
inefficiency. In the next section, we formalize this insight by considering a
setting where LSTD can be viewed as doing model-based estimation on an larger
than necessary class of models.

##  5 Linear dynamical systems

A linear dynamical system is one where there exists a stable matrix $A$ such
that the transition kernel is of the form $X^{(t+1)}=AX^{(t)}+\epsilon^{(t)}$
and rewards are of the form $R^{(t)}=f_{\theta}(X^{(t)})+\eta^{(t)}$, with
$\epsilon^{(t)}\sim\mathcal{N}(0,\sigma^{2}I_{d})$ and
$\eta^{(t)}\sim\mathcal{N}(0,\sigma^{2})$. A model is characterized by its
parameters $(A,\theta)$.

In what follows, we investigate three such systems which are variations of one
another:

  1. 1.

General linear dynamics, linear rewards: In this setting, the dynamic matrix
$A$ can be any stable matrix and the reward is linear
$f_{\theta}(x)=\theta^{\top}x$. We call this class of models
$\mathbb{M}_{G}=\\{(A,\theta|A\in\mathbb{R}^{d\times
d},\theta\in\mathbb{R}^{d}\\}$.

  2. 2.

Diagonal linear dynamics: The dynamic matrix $A$ is now constrained to be
diagonal and the reward is again linear $f_{\theta}(x)=\theta^{\top}x$. We
call this class of models $\mathbb{M}_{D}=\\{({\rm
Diag}\left(a\right),\theta|a\in\mathbb{R}^{d},\theta\in\mathbb{R}^{d}\\}$.

  3. 3.

Linear Quadratic Control (LQR): The dynamic matrix $A$ can be any stable
matrix and the reward is quadratic: $f_{Q}(x)=x^{\top}Qx$. We call this class
of models $\mathbb{M}_{Q}=\\{(A,Q|A\in\mathbb{R}^{d\times
d},Q\in\mathbb{R}^{d\times d}\\}$. Note that contrarily to the classic LQR,
$Q$ isn’t restricted to be SDP. While this hypothesis is important for
control, it is not for the policy evaluation problem where only the symmetric
structure is typically leveraged. While we don’t assume $Q$ to be symmetric,
our results easily extend to this case.

As observed in Figure 1, these subtle differences in the class of model
candidates can lead to large variations in the performance of LSTD. In what
follows, we show that in the first case (general linear dynamics and linear
rewards), LSTD is equivalent to model based. However, in the two other cases,
we show there is a significant loss of information in the value function space
and LSTD can be viewed as a model based procedure in a larger set of models.

The model-based estimators used in what follows are the plug-in estimator
where the dynamics and reward functions are the least-square estimate. Tu &
Recht (2018) provides a description of LSTD both in the general case and
specified to the LQR setting. The formal definition of all the estimators
mentioned thereafter can be found in Appendix A (linear rewards) and C
(quadratic rewards).

###  5.1 General linear dynamics, linear rewards

The class of value functions associated with models in $\mathbb{M}_{G}$ is the
set of all linear functions: for a model $\mathcal{M}=(A,\theta)$, the
associated value function is $V_{\mathcal{M}}(x)=\beta^{\top}x$ where
$\beta=\left(I_{d}-\gamma A^{\top}\right)^{-1}\theta$. When $A$ spans the set
of all stable matrices and $\theta$ the set of all vectors, then $\beta$ spans
the set of all vectors.

Hence,

$\\{V_{\mathcal{M}};\mathcal{M}\in\mathbb{M}_{G}\\}=\\{x\mapsto\beta^{\top}x;\beta\in\mathbb{R}^{d}\\}$

In this setting, running LSTD over this class of value functions does not
suffer any loss of statistical efficiency compared to model-based as we show
these two estimators are the same.

######  Theorem 5.1.

In the case of linear systems with linear costs, LSTD is equivalent to the
model based estimator with no assumptions on the dynamics, that is
$\hat{\beta}_{\rm LSTD}=\hat{\beta}_{\rm ModelBased}$

This result can be observed by simply considering the closed form expression
of both estimators. The detailed proof is defered to the Appendix A.2.

###  5.2 Diagonal linear dynamics, linear rewards

Restricting the dynamics to be diagonal drastically reduces the number of
candidate models. Intuitively, leveraging this added structure should be
necessary to reach statistical efficiency. However, the class of value
functions doesn’t shrink compared to the case where no restriction is imposed
on the dynamics:

$\\{V_{\mathcal{M}};\mathcal{M}\in\mathbb{M}_{D}\\}=\\{x\mapsto\beta^{\top}x;\beta\in\mathbb{R}^{d}\\}=\\{V_{\mathcal{M}};\mathcal{M}\in\mathbb{M}_{G}\\}$

Therefore, there is information loss when moving to the space of value
functions. Since LSTD only leverages the knowledge of the class of value
functions, it will output the same estimate whether it is known that the
dynamics are diagonal or not. That is, in this setting, LSTD is equivalent to
a model-based approach in the wrong class of models. It is, implicitly,
learning $\Theta(d^{2})$ free-parameters instead of $\Theta(d)$. The following
theorem shows that it indeed leads in a loss of statistical efficiency. We
also verify empirically this result, as shown in Figure 3.

######  Theorem 5.2.

Let’s consider the linear system with diagonal transitions $A=\lambda I_{d}$
and linear rewards $\theta=\boldsymbol{1}_{d}$. Then,

$\lim_{n\to\infty}\dfrac{\mathbb{E}\left[\|\hat{\beta}_{\rm
LSTD}-\beta\|^{2}\right]}{\mathbb{E}\left[\|\hat{\beta}_{\rm
diag}-\beta\|^{2}\right]}=\Theta(d)$

###### Proof.

Using the fact that $\hat{\beta}_{\rm LSTD}=\hat{\beta}_{\rm MB}$ and
Corollary A.4, we have

$\displaystyle\lim_{n\to\infty}n\mathbb{E}\left[\|\hat{\beta}_{\rm
LSTD}-\beta\|^{2}\right]$
$\displaystyle=\left(\frac{d\gamma^{2}}{(1-\gamma\lambda)^{2}}+1\right)\left(d\frac{1-\lambda^{2}}{(1-\lambda\gamma)^{2}}\right)=\Theta(d^{2})$

Similarly, from A.8, we have
$\lim_{n\to\infty}n\mathbb{E}\left[\|\hat{\beta}_{\rm
diag}-\beta\|^{2}\right]=d\left(\frac{\gamma^{2}}{(1-\gamma\lambda)^{2}}+1\right)\frac{1-\lambda^{2}}{(1-\gamma\lambda)^{2}}=\Theta(d)$.
Finally, taking the ratio gives the result.

∎

$0$$20$$40$$0$$20$$40$Dimension $d$Ratio in MSE
$\frac{\mathbb{E}\left[\|\hat{\beta}_{\rm
LSTD}-\beta\|^{2}\right]}{\mathbb{E}\left[\|\hat{\beta}_{\rm
diag}-\beta\|^{2}\right]}$EmpiricalAsymptotic Figure 3: Ratio of the mean-
squared error estimation of LSTD and diagonal model based as a functoin of the
dimension $d$. The system considered is the one with dynamics $A=0.9I_{d}$ and
rewards $\theta=\boldsymbol{1}_{d}$, using $\gamma=0.9$. Here
$\lambda=\gamma=0.9$. $100$ samples of each $\hat{\beta}$ were obtained using
$n=1000$ transitions.

###  5.3 Linear Quadratic Control

As already observed by Tu & Recht (2019), LSTD fails to be statistically
efficient in the LQR setting. We show that this setting also suffer a loss of
information and LSTD is again equivalent to a model-based algorithm that
optimizes over a larger class of models that induces this set of value
function. The value function of a system with linear dynamics $A$ and
quadratic rewards $Q$ is

$\displaystyle
V_{A,Q}(x)=x^{\top}Px+\frac{\gamma}{1-\gamma}\operatorname{Tr}\left(P\right)=\operatorname{Tr}\left((xx^{\top}+\frac{\gamma}{1-\gamma}I_{d})P\right)$

where $P$ verifies the discrete Lyapunov equation
$\left(\gamma^{1/2}A\right)^{\top}P\left(\gamma^{1/2}A\right)-P+Q=0$. Once
more, we show this the exactly the right class of value functions.

######  Proposition 5.3.

For any $P\in\mathbb{R}^{d\times d}$, there exists a stable matrix $A$ and a
reward matrix $Q$ such that

$V_{A,Q}(x)=\operatorname{Tr}\left((xx^{\top}+\frac{\gamma}{1-\gamma}I_{d})P\right)$

That is

$\\{V_{\mathcal{M}}|\mathcal{M}\in\mathbb{M}_{Q}\\}=\left\\{x\mapsto\operatorname{Tr}\left((xx^{\top}+\frac{\gamma}{1-\gamma}I_{d})P\right)|P\in\mathbb{R}^{d\times
d}\right\\}$ (2)

###### Proof.

For a matrix $P$, choose $A=.5I_{d}$ and $Q=\frac{4}{4-\gamma}P$. ∎

We now operate a change of variable, $Z^{(t)}={\rm
vec}\left(X^{(t)}(X^{(t)})^{\top}\right)$ where ${\rm vec}\left(M\right)$ is
the vector obtained by stacking the columns of $M$. Since the mapping
$x\mapsto xx^{\top}$ is injective, there is no loss of observability, that is
observing $X^{(t)}$ or $Z^{(t)}$ is equivalent.

In the space of $Z^{(t)}$, the system and rewards are affine:

$\displaystyle\mathbb{E}\left[Z^{(t+1)}|Z^{(t)}\right]$
$\displaystyle=MZ^{(t)}+{\rm vec}\left(I_{d}\right);\quad\quad\text{where
}M=A\otimes A$ $\displaystyle\mathbb{E}\left[R^{(t)}|Z^{(t)}\right]$
$\displaystyle={\rm vec}\left(Q\right)^{\top}Z^{(t)}$

where $\otimes$ is the Kronecker product.

Viewing the problem as one with state variable $Z^{(t)}$ lets us draw a
clarifying parallel to the setting where the rewards are linear and the
dynamics are known to be diagonal (Subsection 5.2): in both settings, the
class of possible transitions is a subset of all possible linear dynamics.
Instead of the diagonal structure, in this example we know the dynamics matrix
$M$ is of the form $A\otimes A$ instead of being any arbitrary matrix in
$\mathbb{R}^{d^{2}\times d^{2}}$. Working solely with value function
representations loses this structure on the dynamics matrix $M$; this is what
we call _information-loss_.

Given this discussion, it becomes unsurprising that LSTD is inefficient even
when applied with the right class of value functions. In fact, similar to the
setting with diagonal dynamics, LSTD is equivalent to a model-based method
that estimates the dynamics matrix $M$ without incorporating known
constraints. Information about those structural constraints has been “lost”
when working with a value-basted representation.

######  Theorem 5.4 (Informal).

LSTD applied with value functions in (2) is equivalent to a model-based plug-
in estimator where the matrix $M\in\mathbb{R}^{d^{2}\times d^{2}}$ is
estimated by unconstrained least-squares.

A precise description of this model-based procedure can be found in Appendix
C.

##  6 Conclusion

In this work, we show that some information about the model may not be
representable in the space of value functions. By exploring multiple closely
related settings where the efficiency of model-free methods varies
significantly, we are able to correlate the (in)efficiency of model-free
methods with whether there is loss of information in the space of value
functions. We are able to establish this loss of information as the driver of
statistical inefficiency in several of our examples by observing that LSTD
implicitly operates as model-based methods over an excessively large class.

Importantly, this work does not imply an impossibility of model-free methods
to be efficient but instead hints that any “generic” algorithm would only be
efficient for a few settings. When problem structure (e.g. decoupled
structure) is known or learned from auxiliary tasks, efficient learning
requires exploiting this structure. Information-loss suggests that value-based
estimation procedures cannot adapt to some problem structures based on the
value function representation alone, since the value function representation
is invariant to that structure. Proving a formal version of this statement is
left for future work.

It is worth emphasizing that if one had a specific structure in mind, like the
decoupled MRP structure, then it may be possible to design value-based
estimation procedures that are tailored to that structure and enhance
efficiency. In this case, the modeler is overcoming information loss by
reflecting problem structure in the estimation algorithm and not the value
function class.

## References

  * Auer et al. (2008) Peter Auer, Thomas Jaksch, and Ronald Ortner.  Near-optimal regret bounds for reinforcement learning.  _Advances in neural information processing systems_ , 21, 2008.
  * Azar et al. (2017) Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos.  Minimax regret bounds for reinforcement learning.  In _International Conference on Machine Learning_ , pp. 263–272. PMLR, 2017.
  * Baek et al. (2023) Jackie Baek, Justin J Boutilier, Vivek F Farias, Jonas Oddur Jonasson, and Erez Yoeli.  Policy optimization for personalized interventions in behavioral health.  _arXiv preprint arXiv:2303.12206_ , 2023.
  * Berkenkamp et al. (2017) Felix Berkenkamp, Matteo Turchetta, Angela Schoellig, and Andreas Krause.  Safe model-based reinforcement learning with stability guarantees.  _Advances in neural information processing systems_ , 30, 2017.
  * Bertsekas (2005) Dimitri P. Bertsekas.  _Dynamic Programming and Optimal Control_ , volume I.  Athena Scientific, Belmont, MA, USA, 3rd edition, 2005.
  * Bradtke & Barto (1996) Steven J Bradtke and Andrew G Barto.  Linear least-squares algorithms for temporal difference learning.  _Machine learning_ , 22:33–57, 1996.
  * Buckman et al. (2018) Jacob Buckman, Danijar Hafner, George Tucker, Eugene Brevdo, and Honglak Lee.  Sample-efficient reinforcement learning with stochastic ensemble value expansion.  _Advances in neural information processing systems_ , 31, 2018.
  * Chen et al. (2021a) Lin Chen, Bruno Scherrer, and Peter L Bartlett.  Infinite-horizon offline reinforcement learning with linear function approximation: Curse of dimensionality and algorithm.  _arXiv preprint arXiv:2103.09847_ , 2021a.
  * Chen et al. (2021b) Yi Chen, Jing Dong, and Zhaoran Wang.  A primal-dual approach to constrained markov decision processes.  _arXiv preprint arXiv:2101.10895_ , 2021b.
  * Clavera et al. (2018) Ignasi Clavera, Jonas Rothfuss, John Schulman, Yasuhiro Fujita, Tamim Asfour, and Pieter Abbeel.  Model-based reinforcement learning via meta-policy optimization.  In _Conference on Robot Learning_ , pp. 617–629. PMLR, 2018.
  * Dong et al. (2020) Kefan Dong, Yuping Luo, Tianhe Yu, Chelsea Finn, and Tengyu Ma.  On the expressivity of neural networks for deep reinforcement learning.  In _International conference on machine learning_ , pp. 2627–2637. PMLR, 2020.
  * Feinberg et al. (2018) Vladimir Feinberg, Alvin Wan, Ion Stoica, Michael I Jordan, Joseph E Gonzalez, and Sergey Levine.  Model-based value expansion for efficient model-free reinforcement learning.  In _Proceedings of the 35th International Conference on Machine Learning (ICML 2018)_ , 2018.
  * Hawkins (2003) Jeffrey Thomas Hawkins.  _A Langrangian decomposition approach to weakly coupled dynamic optimization problems and its applications_.  PhD thesis, Massachusetts Institute of Technology, 2003.
  * Janner et al. (2019) Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine.  When to trust your model: Model-based policy optimization.  _Advances in neural information processing systems_ , 32, 2019.
  * Jin et al. (2018) Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan.  Is q-learning provably efficient?  _Advances in neural information processing systems_ , 31, 2018.
  * Jin et al. (2020) Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan.  Provably efficient reinforcement learning with linear function approximation.  In _Conference on Learning Theory_ , pp. 2137–2143. PMLR, 2020.
  * Kearns & Koller (1999) Michael Kearns and Daphne Koller.  Efficient reinforcement learning in factored mdps.  In _IJCAI_ , volume 16, pp. 740–747, 1999.
  * Kearns & Singh (2002) Michael Kearns and Satinder Singh.  Near-optimal reinforcement learning in polynomial time.  _Machine learning_ , 49:209–232, 2002.
  * Le et al. (2019) Hoang Le, Cameron Voloshin, and Yisong Yue.  Batch policy learning under constraints.  In _International Conference on Machine Learning_ , pp. 3703–3712. PMLR, 2019.
  * Lu et al. (2024) Cong Lu, Philip Ball, Yee Whye Teh, and Jack Parker-Holder.  Synthetic experience replay.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Mann & Wald (1943) Henry B Mann and Abraham Wald.  On the statistical treatment of linear stochastic difference equations.  _Econometrica, Journal of the Econometric Society_ , pp. 173–220, 1943.
  * Maystre et al. (2023) Lucas Maystre, Daniel Russo, and Yu Zhao.  Optimizing audio recommendations for the long-term: A reinforcement learning perspective.  _arXiv preprint arXiv:2302.03561_ , 2023.
  * Moerland et al. (2023) Thomas M Moerland, Joost Broekens, Aske Plaat, Catholijn M Jonker, et al.  Model-based reinforcement learning: A survey.  _Foundations and Trends® in Machine Learning_ , 16(1):1–118, 2023.
  * Recht (2019) Benjamin Recht.  A tour of reinforcement learning: The view from continuous control.  _Annual Review of Control, Robotics, and Autonomous Systems_ , 2:253–279, 2019.
  * Sun et al. (2019) Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford.  Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches.  In _Conference on learning theory_ , pp. 2898–2933. PMLR, 2019.
  * Tesauro et al. (2005) Gerald Tesauro et al.  Online resource allocation using decompositional reinforcement learning.  In _AAAI_ , volume 5, pp. 886–891, 2005.
  * Tu & Recht (2018) Stephen Tu and Benjamin Recht.  Least-squares temporal difference learning for the linear quadratic regulator.  In _International Conference on Machine Learning_ , pp. 5005–5014. PMLR, 2018.
  * Tu & Recht (2019) Stephen Tu and Benjamin Recht.  The gap between model-based and model-free methods on the linear quadratic regulator: An asymptotic viewpoint.  In _Conference on Learning Theory_ , pp. 3036–3083. PMLR, 2019.
  * Turken et al. (2012) Nazli Turken, Yinliang Tan, Asoo J Vakharia, Lan Wang, Ruoxuan Wang, and Arda Yenipazarli.  The multi-product newsvendor problem: Review, extensions, and directions for future research.  _Handbook of Newsvendor Problems: Models, Extensions and Applications_ , pp. 3–39, 2012.
  * Wang et al. (2020) Ruosong Wang, Ruslan Salakhutdinov, and Lin F Yang.  Provably efficient reinforcement learning with general value function approximation.  _arXiv preprint arXiv:2005.10804_ , 2020.
  * Weber & Weiss (1990) Richard R Weber and Gideon Weiss.  On an index policy for restless bandits.  _Journal of applied probability_ , 27(3):637–648, 1990.
  * Xu et al. (2023) Wanqiao Xu, Yecheng Ma, Kan Xu, Hamsa Bastani, and Osbert Bastani.  Uniformly conservative exploration in reinforcement learning.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 10856–10870. PMLR, 2023.
  * Young et al. (2022) Kenny Young, Aditya Ramesh, Louis Kirsch, and Jürgen Schmidhuber.  The benefits of model-based generalization in reinforcement learning.  _arXiv preprint arXiv:2211.02222_ , 2022.
  * Zanette & Brunskill (2019) Andrea Zanette and Emma Brunskill.  Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds.  In _International Conference on Machine Learning_ , pp. 7304–7312. PMLR, 2019.
  * Zhu et al. (2023a) Hanlin Zhu, Baihe Huang, and Stuart Russell.  On representation complexity of model-based and model-free reinforcement learning.  _arXiv preprint arXiv:2310.01706_ , 2023a.
  * Zhu et al. (2023b) Hanlin Zhu, Ruosong Wang, and Jason Lee.  Provably efficient reinforcement learning via surprise bound.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 4006–4032. PMLR, 2023b.

##  Appendix A Proof of Theorem 5.2

Theorem 5.1 states that LSTD over the class of all linear functions is
equivalent to the plug-in estimator in the case where nothing is assumed about
the linear system. The proof will work by comparing the limiting variance of
the model based estimator when the dynamics are known to be linear versus when
nothing is known about the dynamics. We do so by stating a Central Limit
Theorem in both cases.

###  A.1 Notations and preliminaries

In what follows, $A\in\mathbb{R}^{d}$ is a stable matrix,
$\theta\in\mathbb{R}^{d}$ is a reward vector. $(\epsilon^{(t)})_{t}$ and
$(\eta^{(t)})_{t}$ are two independent i.i.d. sequences such that
$\epsilon^{(t)}\sim\mathcal{N}\left(0,\sigma^{2}I\right)$ and
$\eta^{(t)}\sim\mathcal{N}(0,\sigma^{2})$. The dataset accessed by any
algorithm is of the form $(X^{(t)},R^{(t)},X^{(t+1)})_{t=1,\dots,n}$ where

$\displaystyle X^{(t+1)}=AX^{(t)}+\epsilon^{(t)};\quad\quad
R^{(t)}=\theta^{\top}X^{(t)}+\eta^{(t)}$

$\beta$ is the parameter of the value function (that is $V(x)=\beta^{\top}x$)
and verifies $\beta=(I_{d}-\gamma A^{\top})^{-1}\theta$. The stationary
covariance matrix $P_{\infty}$ of the process $(X^{(t)})_{t}$ exists (Mann &
Wald, 1943) and verifies

$AP_{\infty}A^{\top}-P_{\infty}+\sigma^{2}I_{d}=0.$

Finally, $\otimes$ is the Kronecker product of two matrices and $\|\cdot\|$ is
the Frobenius norm. We now formally introduce the estimators we are comparing.

######  Definition A.1 (LSTD).

The LSTD estimator when the systems has linear dynamics and linear rewards is

$\hat{\beta}_{\rm LSTD}=\left(\sum_{t=1}^{n}X^{(t)}(X^{(t)}-\gamma
X^{(t+1)})^{\top}\right)^{-1}\sum_{t=1}^{n}R^{(t)}X^{(t)}$

######  Definition A.2 (Model Based estimator).

The model based estimator considered in this work are of the form

$\hat{\beta}_{\rm
ModelBased}(\mathcal{A})=\left(I-\gamma\hat{A}^{\top}\right)^{-1}\hat{\theta}$

where

$\displaystyle\hat{A}=\arg\min_{A\in\mathcal{A}}\sum_{t=1}^{n}\|X^{(t+1)}-AX^{(t)}\|^{2};\quad\quad\hat{\theta}=\arg\min_{\theta\in\mathbb{R}}\sum_{t=1}^{n}(R^{(t)}-\theta^{\top}X^{(t)})^{2}.$

When the class of models considered is not specified, it is understood there
is no restriction

$\hat{\beta}_{\rm ModelBased}=\hat{\beta}_{\rm ModelBased}(\mathbb{R}^{d\times
d}).$

In the case of diagonal transitions, we write

$\hat{\beta}_{\rm diag}=\hat{\beta}_{\rm ModelBased}({\rm
Diag}\left(\mathbb{R}^{d}\right)).$

###  A.2 Proof of Theorem 5.1

To facilitate the proof, we rewrite the estimators of interest in their closed
form in matrix notation. First LSTD is

$\hat{\beta}_{\rm LSTD}=\left(X(X-\gamma X^{\prime})^{\top}\right)^{-1}XR$

where $X\in\mathbb{R}^{d\times n}$ is the matrix where the $t$-th column is
$X^{(t)}$, $X^{\prime}\in\mathbb{R}^{d\times n}$ is the matrix where the
$t$-th column is $X^{(t+1)}$ and $R\in\mathbb{R}^{n}$ the vector where
$R_{t}=R^{(t)}$.

On the other hand, the least-square estimate of the dymaic matrix $A$ and of
the reward vector $\theta$ are

$\displaystyle\hat{A}^{\top}=(XX^{\top})^{-1}X(X^{\prime})^{\top};\quad\quad\hat{\theta}=(XX^{\top})^{-1}XR$

This allows to re-write the plug-in estimator as

$\displaystyle\hat{\beta}_{\rm ModelBased}(\mathbb{R}^{d\times d})$
$\displaystyle=\left(I_{d}-\gamma
A^{\top}\right)^{-1}\hat{\theta}=\left(I_{d}-\gamma(XX^{\top})^{-1}X(X^{\prime})^{\top}\right)^{-1}(XX^{\top})^{-1}XR$
$\displaystyle=\left(XX^{\top}-\gamma
X(X^{\prime})^{\top}\right)^{-1}XR=\left(X(X-\gamma
X^{\prime})^{\top}\right)^{-1}XR$ $\displaystyle=\hat{\beta}_{\rm LSTD}.$

###  A.3 Central Limit Theorem in the general linear dynamic setting

######  Proposition A.3.

The LSTD estimator $\hat{\beta}_{\rm LSTD}\to\beta$ a.s. and

$\displaystyle\sqrt{n}\left(\left(I_{d}-\gamma\hat{A}^{\top}\right)^{-1}-\left(I_{d}-\gamma
A^{\top}\right)^{-1}\right)\theta\Rightarrow\mathcal{N}\left(0,\sigma^{2}\left(\gamma^{2}\|\left(I_{d}-\gamma
A^{\top}\right)^{-1}\theta\|^{2}+1\right)\left(I_{d}-\gamma
A^{\top}\right)^{-1}P_{\infty}^{-1}\left(I_{d}-\gamma A\right)^{-1}\right)$

######  Corollary A.4.

As $n\to\infty$,

$n\mathbb{E}\left[\|\hat{\beta}_{\rm
LSTD}-\beta\|^{2}\right]\to\sigma^{2}\left(\gamma^{2}\|\left(I_{d}-\gamma
A^{\top}\right)^{-1}\theta\|^{2}+1\right)\left\|P_{\infty}^{-1/2}\left(I_{d}-\gamma
A\right)^{-1}\right\|^{2}$

###### Proof.

We define $M=\begin{bmatrix}A\\\ \theta^{\top}\end{bmatrix}$ and state an
asymptotic result on the least-square regressor of $M$ borrowed from Tu &
Recht (2019) (Lemma A.1).

######  Lemma A.5.

Let

$\hat{M}=\begin{bmatrix}\hat{A}\\\
\hat{\theta}^{\top}\end{bmatrix}=\arg\min_{M\in\mathbb{R}^{(d+1)\times
d}}\sum_{t=0}^{n-1}\left\|\begin{bmatrix}X^{(t+1)}\\\
R^{(t)}\end{bmatrix}-MX^{(t)}\right\|^{2}.$

Then $\hat{M}\xrightarrow{\text{a.s.}}M$ and $\sqrt{n}{\rm
vec}\left(\hat{M}-M\right)\Rightarrow\mathcal{N}\left(0,\sigma^{2}P_{\infty}^{-1}\otimes
I_{d+1}\right)$ In particular, $\hat{A}\xrightarrow{\text{a.s.}}A$,
$\hat{\theta}\xrightarrow{\text{a.s.}}\theta$ and

$\displaystyle\sqrt{n}{\rm
vec}\left(\hat{A}-A\right)\Rightarrow\mathcal{N}\left(0,\sigma^{2}P_{\infty}^{-1}\otimes
I_{d}\right);\quad\quad\sqrt{n}{\rm
vec}\left(\hat{\theta}-\theta\right)\Rightarrow\mathcal{N}\left(0,\sigma^{2}P_{\infty}^{-1}\right).$

Equipped with this lemma, we prove a central limit theorem on the matrix
$\left(I_{d}-\gamma\hat{A}^{\top}\right)^{-1}$.

######  Lemma A.6.

As $n\to\infty$,

$\displaystyle\sqrt{n}\left(\left(I_{d}-\gamma\hat{A}^{\top}\right)^{-1}-\left(I_{d}-\gamma
A^{\top}\right)^{-1}\right)\Rightarrow\gamma\left(I_{d}-\gamma
A^{\top}\right)^{-1}N\left(I_{d}-\gamma A^{\top}\right)^{-1}$

where ${\rm
vec}\left(N^{\top}\right)\sim\mathcal{N}\left(0,\sigma^{2}P_{\infty}^{-1}\otimes
I_{d}\right)$.

###### Proof.

This is an application of the delta method: we define the function
$f(X)=(I_{d}-\gamma X)^{-1}$. Its derivative at $X$ is
$df(X,H)=\gamma(I_{d}-\gamma X)^{-1}H(I_{d}-\gamma X)^{-1}$. Hence

$\displaystyle\sqrt{n}\left(\left(I_{d}-\gamma\hat{A}^{\top}\right)^{-1}-\left(I_{d}-\gamma
A^{\top}\right)^{-1}\right)\Rightarrow\gamma\left(I_{d}-\gamma
A^{\top}\right)^{-1}N\left(I_{d}-\gamma A^{\top}\right)^{-1}$

where Lemma A.5 ensures that ${\rm
vec}\left(N^{\top}\right)\sim\mathcal{N}\left(0,\sigma^{2}P_{\infty}^{-1}\otimes
I_{d}\right)$. ∎

To obtain the final result, we decompose the quantity of interest as follow.

$\displaystyle\sqrt{n}\left(\left(I_{d}-\gamma\hat{A}^{\top}\right)^{-1}\hat{\theta}-\left(I_{d}-\gamma
A\right)^{-1}\theta\right)=$
$\displaystyle\sqrt{n}\left(\left(I_{d}-\gamma\hat{A}^{\top}\right)^{-1}-\left(I-\gamma
A^{\top}\right)^{-1}\right)\left(\hat{\theta}-\theta\right)$
$\displaystyle+\sqrt{n}\left(\left(I_{d}-\gamma\hat{A}^{\top}\right)^{-1}-\left(I_{d}-\gamma
A^{\top}\right)^{-1}\right)\theta$ $\displaystyle+\sqrt{n}\left(I_{d}-\gamma
A^{\top}\right)^{-1}\left(\hat{\theta}-\theta\right).$

Assembling Lemma A.5 and A.6, we can analyse all three parts:

  1. 1.

The first part is a second order error term. From Slutsky’s theorem:

$\sqrt{n}\left(\left(I_{d}-\gamma\hat{A}^{\top}\right)^{-1}-\left(I-\gamma
A^{\top}\right)^{-1}\right)\left(\hat{\theta}-\theta\right)\Rightarrow 0$

  2. 2.

The second part converges to a normal distribution, as per Lemma A.6

$\sqrt{n}\left(\left(I_{d}-\gamma\hat{A}^{\top}\right)^{-1}-\left(I_{d}-\gamma
A^{\top}\right)^{-1}\right)\theta\Rightarrow\mathcal{N}\left(0,\gamma^{2}\sigma^{2}\|\left(I_{d}-\gamma
A^{\top}\right)^{-1}\theta\|^{2}\left(I_{d}-\gamma
A^{\top}\right)^{-1}P_{\infty}^{-1}\left(I_{d}-\gamma A\right)^{-1}\right)$

where we used the Lemma B.1 to simplify the covariance matrix.

  3. 3.

The third part converges to a normal distribution, as per Lemma A.5

$\sqrt{n}\left(I_{d}-\gamma
A^{\top}\right)^{-1}\left(\hat{\theta}-\theta\right)\Rightarrow\mathcal{N}\left(0,\sigma^{2}\left(I_{d}-\gamma
A^{\top}\right)^{-1}P_{\infty}^{-1}\left(I_{d}-\gamma A\right)^{-1}\right).$

Finally, Lemma A.5 implies that the 2. and 3. converge jointly to a normal
distribution. The sum also converges to a normal distribution where the
covariance is the sum of the variance (given the asymptotic independence of 2
and 3), concluding the proof.

∎

###  A.4 Central Limit Theorem in the diagonal linear dynamic setting

######  Proposition A.7.

The model based estimator when the dynamics are known to be diagonal verifies

$\sqrt{n}\left(\hat{\beta}_{\rm
diag}-\beta\right)\Rightarrow\mathcal{N}(0,\Sigma)$

where $\Sigma$ is diagonal and

$\Sigma_{i,i}=\left(\frac{\gamma^{2}\theta_{i}^{2}}{(1-\gamma
A_{i,i})^{2}}+1\right)\frac{1-A_{i,i}^{2}}{(1-\gamma A_{i,i})^{2}}$

######  Corollary A.8.

As $n\to\infty$,

$n\mathbb{E}\left[\|\hat{\beta}_{\rm
diag}-\beta\|^{2}\right]\to\sum_{i=1}^{d}\left(\frac{\gamma^{2}\theta_{i}^{2}}{(1-\gamma
A_{i,i})^{2}}+1\right)\frac{1-A_{i,i}^{2}}{(1-\gamma A_{i,i})^{2}}$

When $A$ is known to be diagonal, the model based estimator can be written
$\hat{\beta}_{{\rm diag},i}=\dfrac{\hat{\theta}_{i}}{1-\gamma\hat{A}_{i,i}}$.
Let $a=(A_{i,i})_{i=1,\dots,d}$. Similarly to Lemma A.5, we have in this case:

$\sqrt{n}\left(\begin{bmatrix}\hat{a}^{\top}\\\
\hat{\theta}^{\top}\end{bmatrix}-\begin{bmatrix}a^{\top}\\\
\theta^{\top}\end{bmatrix}\right)\Rightarrow\mathcal{N}\left(0,\begin{bmatrix}P_{\infty}^{-1}\quad
0\\\ \quad 0\quad P_{\infty}^{-1}\end{bmatrix}\right)$

Note that when $A$ is diagonal, so is $P_{\infty}$ and
$P_{\infty,i,i}=\dfrac{\sigma^{2}}{1-A_{i,i}^{2}}$. Hence, we can treat each
of the coordinate of $\hat{\beta}_{{\rm diag},i}$ separately. We then have

$\sqrt{n}\left(\hat{\beta}_{{\rm
diag},i}-\beta_{i}\right)\Rightarrow\mathcal{N}\left(0,\sigma^{2}\left(\frac{\gamma^{2}\theta_{i}^{2}}{(1-\gamma
A_{i,i})^{2}}+1\right)\frac{1-A_{i,i}^{2}}{\sigma^{2}(1-\gamma
A_{i,i})^{2}}\right)$

Using that each component of $\hat{\beta}_{\rm diag}$ is asymptotically
independent of the others, we get the result.

##  Appendix B Technical lemmas on random matrices

######  Lemma B.1.

Let $M$ be a random matrix such that $\mathrm{Cov}\left[{\rm
vec}\left(M^{\top}\right)\right]=B\otimes C$ and $\lambda\in\mathbb{R}^{d}$ be
a deterministic vector, then

$\mathrm{Cov}\left[M\theta\right]=(\theta^{\top}C\theta)B$

###### Proof.

Let $i,j\in\\{1,\dots,d\\}$,

$\displaystyle\mathrm{Cov}\left[(M\theta)_{i},(M\theta)_{j}\right]$
$\displaystyle=\mathrm{Cov}\left[\sum_{k=1}^{d}M_{i,k}\theta_{k},\sum_{l=1}^{d}M_{j,l}\theta_{l}\right]=\sum_{k=1}^{d}\sum_{l=1}^{d}\mathrm{Cov}\left[M_{i,k}\theta_{k},M_{j,l}\theta_{l}\right]$
$\displaystyle=\sum_{k=1}^{d}\sum_{l=1}^{d}\mathrm{Cov}\left[{\rm
vec}\left(M^{\top}\right)_{n(i-1)+k},{\rm
vec}\left(M^{\top}\right)_{n(j-1)+l}\right]\theta_{k}\theta_{l}$
$\displaystyle=\sum_{k=1}^{d}\sum_{l=1}^{d}B_{i,j}C_{k,l}\theta_{k}\theta_{l}=B_{i,j}\theta^{\top}C\theta.$

∎

##  Appendix C Equivalence between LSTD and a model-based method for LQR

As described in Section 5.3, we can consider without any loss of generality
that the state is $Z^{(t)}={\rm vec}\left(X^{(t)}(X^{(t)})^{\top}\right)$.
Doing this change of variable, the dynamics are

$\displaystyle\mathbb{E}\left[Z^{(t+1)}|Z^{(t)}\right]$
$\displaystyle=MZ^{(t)}+{\rm vec}\left(I_{d}\right);\quad\quad\text{where
}M=A\otimes A$ $\displaystyle\mathbb{E}\left[R^{(t)}|Z^{(t)}\right]$
$\displaystyle={\rm vec}\left(Q\right)^{\top}Z^{(t)}$

Let $\mathfrak{M}$ be the set of MRPs with state space
$\mathcal{S}=\mathbb{R}^{d^{2}}$ such that there exists
$M\in\mathbb{R}^{d^{2}\times d^{2}},\theta\in\mathbb{R}^{d^{2}}$ such that

$\displaystyle\mathbb{E}\left[X^{(t+1)}|X^{(t)}\right]=MX^{(t)}+{\rm
vec}\left(I_{d}\right);\quad\quad\mathbb{E}\left[R^{(t)}|X^{(t)}\right]=\theta^{\top}X^{(t)}.$

Let $\mathbb{M}_{\rm LQR}$ be the class of all LQR instances where the state
space is viewed in $\mathbb{R}^{d^{2}}$. It is clear that $\mathbb{M}_{\rm
LQR}\subset\mathfrak{M}$.

######  Proposition C.1 (Loss of information in LQR).

The class of models $\mathfrak{M}$ have the same class of value function as
$\mathbb{M}_{\rm LQR}$:

$\\{V_{\mathcal{M}}|\mathcal{M}\in\mathfrak{M}\\}=\\{V_{\mathcal{M}}|\mathcal{M}\in\mathbb{M}_{\rm
LQR}\\}$

The proof is immediate from Proposition 5.3 and verifying that
$V_{\mathcal{M}}$ lives in the same set for $\mathcal{M}\in\mathfrak{M}$.

We now describe the model-based procedure to which LSTD is equivalent in this
setting. First, we recall the LSTD estimator for LQR:

$\hat{P}_{\rm
LSTD}=\left(\Phi(\Phi-\gamma\Phi^{\prime})^{\top}\right)^{-1}\Phi R$

Where $\Phi\in\mathbb{R}^{d^{2}\times
n},\Phi^{\prime}\in\mathbb{R}^{d^{2}\times n}$ are the matrix where the $t$-th
column is respectively $Z^{(t)}+\frac{\gamma}{1-\gamma}{\rm
vec}\left(I_{d}\right)$ and $Z^{(t+1)}+\frac{\gamma}{1-\gamma}{\rm
vec}\left(I_{d}\right)$ and $R$ is the vector $(R^{(t)})_{t}$. Similarly to
the case with linear reward, this can be re-written as

$\displaystyle\hat{P}_{\rm LSTD}$
$\displaystyle=\left(\Phi\Phi^{\top}-\gamma\Phi(\Phi^{\prime})^{\top}\right)^{-1}\Phi
R$
$\displaystyle=\left(I_{d^{2}}-\gamma\left(\Phi\Phi^{\top}\right)^{-1}\Phi(\Phi^{\prime})^{\top}\right)^{-1}\left(\Phi\Phi^{\top}\right)^{-1}\Phi
R$
$\displaystyle=\left(I_{d^{2}}-\gamma\hat{M}^{\top}\right)^{-1}\hat{\theta}$

Where

$\displaystyle\hat{M}$ $\displaystyle=\arg\min_{M\in\mathbb{R}^{d^{2}\times
d^{2}}}\sum_{t=1}^{n}\left\|\left(Z^{(t+1)}+\frac{\gamma}{1-\gamma}{\rm
vec}\left(I_{d}\right)\right)-M\left(Z^{(t)}+\frac{\gamma}{1-\gamma}{\rm
vec}\left(I_{d}\right)\right)\right\|^{2}$ $\displaystyle\hat{\theta}$
$\displaystyle=\arg\min_{\theta\in\mathbb{R}^{d^{2}}}\sum_{t=1}^{n}\left\|R^{(t)}-\theta^{\top}\left(Z^{(t)}+\frac{\gamma}{1-\gamma}{\rm
vec}\left(I_{d}\right)\right)\right\|^{2}$

In words, $\hat{M}$ is the best linear approximation to the mapping from
$Z^{(t)}+\frac{\gamma}{1-\gamma}{\rm vec}\left(I_{d}\right)$ to
$Z^{(t+1)}+\frac{\gamma}{1-\gamma}{\rm vec}\left(I_{d}\right)$. While the true
mapping isn’t linear (it is affine), the best linear approximation to it,
under infinite data, is the mapping $z\mapsto Mz$ where $M$ is the dynamic
matrix. Therefore, this model estimation procedure asymptotically recovers the
true dynamics $M$. Similarly, it recovers the true reward parameter $\theta$.
However, the loss of information materializes in that the best linear
approximation $\hat{M}$ is learned over the set of all $d^{2}\times d^{2}$
matrices instead of only considering the ones of interest, that is those that
can be written $A\otimes A$ for some matrix $A\in\mathbb{R}^{d\times d}$.