# 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 at 8:32

## 1 Answer

This is just a partial/general answer that addresses one of your doubts. I will let others address your question about the specific algorithms that you are mentioning.

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$$.

Note that time-steps in RL are not the same thing as time in time-complexity. Maybe this is where your confusion partially lies.

If the explanations above were confusing, then I think you should rigorously review the concepts of time/space complexity.

As a side note, computational learning theory is a branch of machine learning that studies learning algorithms from a theoretical/mathematical standpoint, i.e. the algorithms are analysed in terms of time complexity, space complexity and sample complexity, which is related to the sample efficiency, but not exactly the same thing.