I'm unable to find online, or understand from context - the difference between estimation error and approximation error in the context of machine learning (and, specifically, reinforcement learning).
Could someone please explain with the help of examples and/or references?
Section 5.2 Error Decomposition of the book Understanding Machine Learning: From Theory to Algorithms (2014) gives a description of the approximation error and estimation error in the context of empirical risk minimization (ERM) and, in particular, in the context of the bias-complexity tradeoff (which is strictly related to the bias-variance tradeoff).
The expected risk (error) of a hypothesis $h_S \in \mathcal{H}$ selected based on the training dataset $S$ from a hypothesis class $\mathcal{H}$ can be decomposed into the approximation error, $\epsilon_{\mathrm{app}}$, and the estimation error, $\epsilon_{\mathrm{est}}$, as follows
\begin{align} L_{\mathcal{D}}\left(h_{S}\right) &= \epsilon_{\mathrm{app}}+\epsilon_{\mathrm{est}} \\ &= \epsilon_{\mathrm{app}}+ \left( L_{\mathcal{D}}\left(h_{S}\right)-\epsilon_{\mathrm{app}} \right) \\ &= \left( \min _{h \in \mathcal{H}} L_{\mathcal{D}}(h)\right) + \left( L_{\mathcal{D}}\left(h_{S}\right)-\epsilon_{\mathrm{app}} \right) \label{1}\tag{1} \end{align}
The approximation error (AE), aka inductive bias, defined as
$$\epsilon_{\mathrm{app}} = \min _{h \in \mathcal{H}} L_{\mathcal{D}}(h) $$
is the error due to the specific choice of hypothesis class (or set) $\mathcal{H}$. So, $\min _{h \in \mathcal{H}} L_{\mathcal{D}}(h)$ is minimal risk/error that can be achieved with a hypothesis class $\mathcal{H}$. In other words, if you limit yourself to $\mathcal{H}$ and you select the "best" hypothesis in $\mathcal{H}$, then $\min _{h \in \mathcal{H}} L_{\mathcal{D}}(h)$ is the expected risk of that hypothesis.
Here are some properties.
The larger $\mathcal{H}$ is, the smaller this error is (because it's more likely that a larger hypothesis class contains the actual hypothesis we are looking for). So, if $\mathcal{H}$ does not contain the actual hypothesis we are searching for, then this error could not be zero.
This error does not depend on the training data. You can see in the formula above that there's no $S$ (the training dataset), but only on $D$ (the distribution over the space of inputs and labels from which $S$ was assumed to have been sampled)
The estimation error (EE) is the difference between the approximation error $\epsilon_{\mathrm{app}}$ and the error achieved by the ERM predictor $L_{\mathcal{D}}\left(h_{S}\right)$, i.e.
\begin{align} \epsilon_{\mathrm{est}} &=L_{\mathcal{D}}\left(h_{S}\right)-\epsilon_{\mathrm{app}} \\ &= L_{\mathcal{D}}\left(h_{S}\right) - \min _{h \in \mathcal{H}} L_{\mathcal{D}}(h) \end{align}
Here are some properties.
The estimation error depends on the training dataset $S$. You can see $S$ in the formula above.
$\epsilon_{\mathrm{est}}$ also depends on the choice of the hypothesis class (given that it is defined as a function of $\epsilon_{\mathrm{app}}$).
If we increase the size and complexity of the hypothesis class, the approximation error decreases, but the estimation error may increase (i.e. we may have over-fitting). On the other hand, if we decrease the size and complexity of the hypothesis class, the estimation error may decrease, but the bias may increase (i.e. we may have under-fitting). So, we have a bias-complexity trade-off (where the bias refers to the approximation error or inductive bias) and the complexity refers to the complexity of the hypothesis class.
In section 4.1 of this book also describes a similar (but equivalent) error decomposition, which is called error excess because it's a difference between the expected risk and the Bayes error (which is sometimes called inherent error or irreducible error), which they denote by $R^{*}$, while the other book above, which also points out that there's this equivalent error excess decomposition, denote it by $\epsilon_{\mathrm{Bayes}}$. So, here's the error excess
$$R(h)-R^{*}=\underbrace{\left(\inf _{h \in \mathcal{H}} R(h)-R^{*}\right)}_{\text {approximation excess}} + \underbrace{\left(R(h)-\inf _{h \in \mathcal{H}} R(h)\right)}_{\text {estimation error}}$$
So, if you take $R^{*} = \epsilon_{\mathrm{Bayes}}$ from both sides of the equation, you end up with
$$R(h)=\underbrace{\left(\inf _{h \in \mathcal{H}} R(h) \right)}_{\epsilon_{\mathrm{app}}} + \underbrace{\left(R(h)-\inf _{h \in \mathcal{H}} R(h)\right)}_{\epsilon_{\mathrm{est}}} \label{2}\tag{2}$$
which is equivalent to equation \ref{1}, where
A nice picture that illustrates the relationship between these terms can be found in figure 4.1 of this book (p. 62).
Here, the red points are specific hypotheses. In this illustration, we can see that the best hypothesis (the Bayes hypothesis) lies outside our chosen hypothesis class $\mathcal{H}$. The distance between the risk of $h \in \mathcal{H}$ and the risk of $h^* = \operatorname{arg inf} _{h \in \mathcal{H}} R(h)$ is the estimation error, while the distance between $h^*$ and the Bayes hypothesis (i.e. the hypothesis that achieves the Bayes error) is the approximation excess in equation \ref{2}.
I think this is best explained by pictures. Please note that $h_{S}$ is the output of the ERM learner (under the hypothesis class $\mathcal{H}$) is denoted by $ERM_{\mathcal{H}}$, $f$ is the target hypothesis or the true labeling function. Also:
A small hypothesis class (or space) $\mathcal{H}$ not containing the target hypothesis $f$, the hypothesis $h_{S} \in \mathcal{H}$ found by the $ERM_{\mathcal{H}}$ learner via training, by some chance - say - small training set size, is not $h^{\star}$. Increasing the training set size may often help (i.e. make $h_{S}$ move closer or even equal to $h^{\star}$):
Another relatively small but slightly better hypothesis space $\mathcal{H}^{'}$: The approximation error (generalization error comes from the best hypothesis) is smaller than that one, i.e. $h^{\star}$ closely approximates the target function:
A good hypothesis space $\mathcal{H^{''}}$, of course the best hypothesis class is $\mathcal{H^{'''}}=\{f\}$ but most of the time we don't know what the (class of the) target hypothesis function $f$ is (if we know the function $f$ then learning is redundant), and especially under the assumption of agnostic PAC learning, it's often not a labeling function but rather a data generating distribution:
