# If Least-Squares TD is computationally more expensive, then why is it more data efficient than semi-gradient TD(0)?

In Sutton-Barto (Section: 9.8 Least-Squares TD, page 228):

Authors say that Least-Squares TD is the most "data efficient" form of linear TD(0). Later, in this section, they say the computational complexity of semi-gradient TD(0) is $$O(d)$$ and that of Least-Squares TD is $$O(d^2)$$.

If Least-Squares TD is computationally more expensive, then why is it more data efficient than semi-gradient TD(0)? In fact, what do authors mean by "data efficiency"?

I think authors mean by data efficiency to avoid from iterative nature of semi-gradient TD(0). However, the Least-Squares TD is also iterative (please see the box at page 230 of the book). I am confused. How do we know that convergence of Least-Squares TD takes less time steps compared to semi-gradient TD(0)?

• Can you also rephrase this sentence "I think authors mean by data efficiency to avoid from iterative nature of..." because it's not very understandable? It seems that some words are missing or there are typos.
– nbro
Apr 13, 2022 at 8:32

Data efficiency refers to the number of samples or observations that you use during learning, as a function of the number of episodes, time steps or maybe time, to achieve a certain performance (e.g. return). I think that data efficiency is a synonym for sample efficiency, at least, in reinforcement learning. In RL, a sample could e.g. be a tuple $$\langle s_t, a_t, r_{t+1}, s_{t+1} \rangle$$.
The time and space complexities of an algorithm indicate how much computation and memory the algorithm needs asymptotically. These are usually expressed as a function of the size of the input (which is measured in different ways, e.g. number of elements in a list or maybe the number of bits to represent a number), but this does not always have to be the case (e.g. you can also express the time complexity as a function of the output size, for a certain type of algorithm known as output-sensitive algorithm, or maybe as a function of the number of layers in a neural network). In your case, it's expressed as a function of $$d$$.
Now, let's say that we have 2 learning algorithms, $$A$$ and $$B$$, and that, on average, algorithm $$A$$ requires roughly $$10^6$$ samples to obtain the return $$R$$, while algorithm $$B$$ requires only $$10^3$$ samples to obtain the same return $$R$$. We can conclude that $$B$$ is more sample efficient than $$A$$. However, let's say that, at every time step, $$B$$ does an expensive calculation (e.g. it performs an algorithm that has exponential time complexity), while $$A$$ does a constant-time computation. We can say that $$A$$ has a better time complexity. Later, maybe we can come up with a new algorithm $$C$$, which has the same time complexity as $$A$$, but better sample efficiency, so we would probably use $$C$$ rather than $$A$$, but we could still choose $$B$$, provided that its time complexity is acceptable (e.g. exponential time would not be acceptable). So, you could also have an algorithm $$D$$ that is as sample efficient as $$B$$, but, at every step, it performs an update that requires exponential time, but it still requires the same number of time steps to get the same return $$R$$.