For example, the the paper Soft Actor-Critic:Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor, 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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
The sample complexity is defined precisely in computational learning theory, 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.
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 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 or this answers.
The famous RL book 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.
-
2