Answers.Body: <p>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.</p>
  <p>Data efficiency refers to the number of <a href="https://www.investopedia.com/terms/s/sample.asp" rel="nofollow noreferrer">samples</a> or observations that you use during learning, as a function of the number of episodes, <a href="https://ai.stackexchange.com/a/11605/2444">time steps</a> or maybe time, to achieve a certain performance (e.g. <em>return</em>). I think that <a href="https://ai.stackexchange.com/q/1416/2444"><em>data efficiency</em></a> is a synonym for <a href="https://ai.stackexchange.com/q/21992/2444">sample efficiency</a>, at least, in reinforcement learning. In RL, a sample could e.g. be a tuple <span class="math-container">$\langle s_t, a_t, r_{t+1}, s_{t+1} \rangle$</span>.</p>
  <p>The time and space complexities of an algorithm indicate how much computation and memory the algorithm needs <a href="https://en.wikipedia.org/wiki/Asymptotic_analysis" rel="nofollow noreferrer"><em>asymptotically</em></a>. 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 <a href="https://en.wikipedia.org/wiki/Output-sensitive_algorithm" rel="nofollow noreferrer"><em>output-sensitive algorithm</em></a>, or maybe as a function of the <a href="https://ai.stackexchange.com/a/13626/2444">number of layers</a> in a neural network). In your case, it's expressed as a function of <span class="math-container">$d$</span>.</p>
  <p>Now, let's say that we have 2 learning algorithms, <span class="math-container">$A$</span> and <span class="math-container">$B$</span>, and that, on average, algorithm <span class="math-container">$A$</span> requires roughly <span class="math-container">$10^6$</span> samples to obtain the return <span class="math-container">$R$</span>, while algorithm <span class="math-container">$B$</span> requires only <span class="math-container">$10^3$</span> samples to obtain the same return <span class="math-container">$R$</span>. We can conclude that <span class="math-container">$B$</span> is more sample efficient than <span class="math-container">$A$</span>. However, let's say that, at every time step, <span class="math-container">$B$</span> does an expensive calculation (e.g. it performs an algorithm that has exponential time complexity), while <span class="math-container">$A$</span> does a constant-time computation. We can say that <span class="math-container">$A$</span> has a better time complexity. Later, maybe we can come up with a new algorithm <span class="math-container">$C$</span>, which has the same time complexity as <span class="math-container">$A$</span>, but better sample efficiency, so we would probably use <span class="math-container">$C$</span> rather than <span class="math-container">$A$</span>, but we could still choose <span class="math-container">$B$</span>, provided that its time complexity is acceptable (e.g. exponential time would not be acceptable). So, you could also have an algorithm <span class="math-container">$D$</span> that is as sample efficient as <span class="math-container">$B$</span>, 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 <span class="math-container">$R$</span>.</p>
  <p>Note that <a href="https://ai.stackexchange.com/a/11605/2444">time-steps</a> in RL are not the same thing as time in time-complexity. Maybe this is where your confusion partially lies.</p>
  <p>If the explanations above were confusing, then I think you should rigorously review the concepts of time/space complexity.</p>
  <p>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 <a href="https://en.wikipedia.org/wiki/Sample_complexity" rel="nofollow noreferrer">sample complexity</a>, which is related to the sample efficiency, but not exactly the same thing.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-12T23:01:02.687Z
Answers.LastActivityDate: 2022-04-12T23:01:02.687Z
Answers.UserDisplayName: nbro
Body: <p>In Sutton-Barto (Section: 9.8 Least-Squares TD, page 228):</p>
  <p>Authors say that  Least-Squares TD is the most &quot;data efficient&quot; form of linear TD(0). Later, in this section, they say the computational complexity of semi-gradient TD(0) is <span class="math-container">$O(d)$</span> and that of Least-Squares TD is <span class="math-container">$O(d^2)$</span>.</p>
  <p>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 &quot;data efficiency&quot;?</p>
  <p>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)?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-04-13T08:32:18.067Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><computational-learning-theory><temporal-difference-methods><computational-complexity><sample-efficiency>
Title: If Least-Squares TD is computationally more expensive, then why is it more data efficient than semi-gradient TD(0)?
UserDisplayName: user3489173
ThreadText: # If Least-Squares TD is computationally more expensive, then why is it more data efficient than semi-gradient TD(0)?
  
  (Asked by: username_0 on 2022-04-12)
  
  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)?
  
  **Tags:** reinforcement-learning, computational-learning-theory, temporal-difference-methods, computational-complexity, sample-efficiency
  > **Comments:**
  > **username_1**: 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.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-04-12. Score: 1 | Accepted 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](https://www.investopedia.com/terms/s/sample.asp) or observations that you use during learning, as a function of the number of episodes, [time steps](https://ai.stackexchange.com/a/11605/2444) or maybe time, to achieve a certain performance (e.g. *return*). I think that [*data efficiency*](https://ai.stackexchange.com/q/1416/2444) is a synonym for [sample efficiency](https://ai.stackexchange.com/q/21992/2444), 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*](https://en.wikipedia.org/wiki/Asymptotic_analysis). 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*](https://en.wikipedia.org/wiki/Output-sensitive_algorithm), or maybe as a function of the [number of layers](https://ai.stackexchange.com/a/13626/2444) 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](https://ai.stackexchange.com/a/11605/2444) 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](https://en.wikipedia.org/wiki/Sample_complexity), which is related to the sample efficiency, but not exactly the same thing.
  
  
  ---
  
  