Answers.Body: <p>The <strong>sample complexity</strong> is defined precisely in <a href="https://ai.stackexchange.com/q/20355/2444">computational learning theory</a>, which studies learning from a theoretical standpoint (like theoretical physics for physics).</p>
  <p>Here's a definition taken from the book <a href="https://www.cs.huji.ac.il/%7Eshais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf" rel="nofollow noreferrer">Understanding Machine Learning: From Theory to Algorithms</a>.</p>
  <blockquote>
  <p>The function <span class="math-container">$m_\mathcal{H} : (0, 1)^2 \rightarrow N$</span> determines the sample complexity of learning <span class="math-container">$\mathcal{H}$</span>: that is, <strong>how many examples are required to guarantee a <em>probably approximately correct</em> solution</strong>. The sample complexity is a function of the accuracy (<span class="math-container">$\epsilon$</span>) and
  confidence (<span class="math-container">$\delta$</span>) parameters. It also depends on properties of the hypothesis class <span class="math-container">$\mathcal{H}$</span> – for example, for a finite class we showed that the sample complexity depends on log the size of <span class="math-container">$\mathcal{H}$</span>.</p>
  </blockquote>
  <p>The intuitive definition of the sample complexity is <strong>in bold</strong>.</p>
  <p>To understand why <span class="math-container">$m_\mathcal{H}$</span> determines the sample complexity, you should learn about the PAC learning model, where PAC stands for <em>probably approximately correct</em>, which is defined in the same book - see definition 3.1.</p>
  <p>Once you are familiar with the concepts of hypothesis class, accuracy <span class="math-container">$\epsilon$</span> (not the accuracy you may be used to), confidence <span class="math-container">$\delta$</span> (not the confidence you may be used to), and other ideas described in the same book, then, for example, the equation in <em>corollary 3.2</em> of the same book will make sense to you. Here's corollary 3.2 for completeness.</p>
  <blockquote>
  <p>Every finite hypothesis class is PAC learnable with sample
  complexity</p>
  <p><span class="math-container">$m_\mathcal{H}(\epsilon, \delta) \leq  \left \lceil \frac{\log (|\mathcal{H}|/\delta)}{\epsilon} \right \rceil$</span></p>
  </blockquote>
  <p>In this equation, <span class="math-container">$|\mathcal{H}|$</span> (the size of the hypothesis class <span class="math-container">$\mathcal{H}$</span>), <span class="math-container">$\epsilon$</span> and <span class="math-container">$\delta$</span> are numbers, so <span class="math-container">$m_\mathcal{H}(\epsilon, \delta)$</span> is also number. So, <span class="math-container">$m_\mathcal{H}(\epsilon, \delta)$</span>, the sample complexity of <span class="math-container">$\mathcal{H}$</span>, is bounded from above by that expression <span class="math-container">$\left \lceil \frac{\log (|\mathcal{H}|/\delta)}{\epsilon} \right \rceil$</span>.</p>
  <p>The <strong>sample efficiency</strong> is a similar notion, which is, as far as I know, more commonly used in reinforcement learning. <a href="https://ai.stackexchange.com/a/21996/2444">This answer</a> describes it well.</p>
  <p>It's possible that, in the context of RL, people use these 2 terms interchangeably, i.e. when they use the term <em>sample complexity</em>, they refer to the <em>sample efficiency</em> described in <a href="https://ai.stackexchange.com/a/21996/2444">this</a> or <a href="https://ai.stackexchange.com/a/5295/2444">this</a> answers.</p>
  <p><a href="http://www.incompleteideas.net/book/RLbook2020.pdf" rel="nofollow noreferrer">The famous RL book</a> also defines the concept of the sample complexity to measure the exploration efficiency of an RL algorithm</p>
  <blockquote>
  <p>A definition of the sample complexity of exploration for a reinforcement learning algorithm is the <strong>number of time steps in which the algorithm does not select near-optimal actions</strong></p>
  </blockquote>
  <p>So, the ideas of sample complexity or efficiency are similar, both in RL and learning theory, but the precise definitions may differ. You should take context into account.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-17T04:40:40.997Z
Answers.Text: Very comprehensive answer. Thank you so much
Answers.UserDisplayName: Sam
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-16T23:13:51.680Z
Answers.LastActivityDate: 2023-01-17T10:35:40.950Z
Answers.LastEditDate: 2023-01-17T10:35:40.950Z
Answers.UserDisplayName: nbro
Body: <p>For example, the the paper <a href="https://arxiv.org/pdf/1801.01290.pdf" rel="nofollow noreferrer">Soft Actor-Critic:Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor</a>, both terms are mentioned but without explaining. I have seen them in other places as well but in different contexts. So I am confused because in this paper they are seemingly used in an interchangeable manner.</p>
  
Tags: <reinforcement-learning><comparison><terminology><sample-efficiency><sample-complexity>
Title: Do the terms 'sample complexity' and 'sample efficiency' mean the same thing in RL context
UserDisplayName: Sam
ThreadText: # Do the terms 'sample complexity' and 'sample efficiency' mean the same thing in RL context
  
  (Asked by: username_0 on 2023-01-16)
  
  For example, the the paper [Soft Actor-Critic:Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://arxiv.org/pdf/1801.01290.pdf), both terms are mentioned but without explaining. I have seen them in other places as well but in different contexts. So I am confused because in this paper they are seemingly used in an interchangeable manner.
  
  **Tags:** reinforcement-learning, comparison, terminology, sample-efficiency, sample-complexity
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-01-16. Score: 4 | Accepted answer
  
  The **sample complexity** is defined precisely in [computational learning theory](https://ai.stackexchange.com/q/20355/2444), which studies learning from a theoretical standpoint (like theoretical physics for physics).
  
  Here's a definition taken from the book [Understanding Machine Learning: From Theory to Algorithms](https://www.cs.huji.ac.il/%7Eshais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf).
  
  > The function $m\_\mathcal{H} : (0, 1)^2 \rightarrow N$ determines the sample complexity of learning $\mathcal{H}$: that is, **how many examples are required to guarantee a *probably approximately correct* solution**. The sample complexity is a function of the accuracy ($\epsilon$) and
  > confidence ($\delta$) parameters. It also depends on properties of the hypothesis class $\mathcal{H}$ – for example, for a finite class we showed that the sample complexity depends on log the size of $\mathcal{H}$.
  
  The intuitive definition of the sample complexity is **in bold**.
  
  To understand why $m\_\mathcal{H}$ determines the sample complexity, you should learn about the PAC learning model, where PAC stands for *probably approximately correct*, which is defined in the same book - see definition 3.1.
  
  Once you are familiar with the concepts of hypothesis class, accuracy $\epsilon$ (not the accuracy you may be used to), confidence $\delta$ (not the confidence you may be used to), and other ideas described in the same book, then, for example, the equation in *corollary 3.2* of the same book will make sense to you. Here's corollary 3.2 for completeness.
  
  > Every finite hypothesis class is PAC learnable with sample
  > complexity
  >
  > $m\_\mathcal{H}(\epsilon, \delta) \leq \left \lceil \frac{\log (|\mathcal{H}|/\delta)}{\epsilon} \right \rceil$
  
  In this equation, $|\mathcal{H}|$ (the size of the hypothesis class $\mathcal{H}$), $\epsilon$ and $\delta$ are numbers, so $m\_\mathcal{H}(\epsilon, \delta)$ is also number. So, $m\_\mathcal{H}(\epsilon, \delta)$, the sample complexity of $\mathcal{H}$, is bounded from above by that expression $\left \lceil \frac{\log (|\mathcal{H}|/\delta)}{\epsilon} \right \rceil$.
  
  The **sample efficiency** is a similar notion, which is, as far as I know, more commonly used in reinforcement learning. [This answer](https://ai.stackexchange.com/a/21996/2444) describes it well.
  
  It's possible that, in the context of RL, people use these 2 terms interchangeably, i.e. when they use the term *sample complexity*, they refer to the *sample efficiency* described in [this](https://ai.stackexchange.com/a/21996/2444) or [this](https://ai.stackexchange.com/a/5295/2444) answers.
  
  [The famous RL book](http://www.incompleteideas.net/book/RLbook2020.pdf) also defines the concept of the sample complexity to measure the exploration efficiency of an RL algorithm
  
  > A definition of the sample complexity of exploration for a reinforcement learning algorithm is the **number of time steps in which the algorithm does not select near-optimal actions**
  
  So, the ideas of sample complexity or efficiency are similar, both in RL and learning theory, but the precise definitions may differ. You should take context into account.
  
  > **Comments:**
  > **username_0**: Very comprehensive answer. Thank you so much  
  
  ---
  
  