1
$\begingroup$

Is the VC dimension meaningful for reinforcement learning (RL), as a machine learning (ML) method? How?

$\endgroup$
2
$\begingroup$

Yes, it is. This article (Approximate Planning in Large POMDPs via Reusable Trajectories) explain about it by means of the trajectory tree:

A trajectory tree is a binary tree in which each node is labeled by a state and observation pair, and has a child for each of the two actions. Additionally, each link to a child is labeled by a reward, and the tree's depth will be $H_\epsilon$, so it will have about $2^{H_\epsilon}$ nodes. The root is labeled by $s_0$ and the observation there, $o_0$.

Now a policy $\pi$ will be defined like the following base on the trajectory tree:

For any deterministic strategy $\pi$ and any trajectory tree $T$, $\pi$ defines a path through $T$: $\pi$ starts at the root, and inductively, if $\pi$ is at some internal node in $T$, then we feed to $\pi$ the observable history along the path from the root to that node, and $\pi$ selects and moves to a child of the current node. This continues until a leaf node is reached, and we define $R(\pi, T)$ to be the discounted sum of returns along the path taken. In the case that $\pi$ is stochastic, $\pi$ defines a distribution on paths in $T$, and $R(\pi, T)$ is the expected return according to this distribution. Hence, given $m$ trajectory trees $T_1 , \ldots , T_m$, a natural estimate for $V^\pi(s_0)$ is $V^\pi(s_0) = \frac{1}{m}\sum_{i=1}^mR(\pi, T_i)$. *Note that each tree can be used to evaluate any strategy, much the way a single labeled example $\langle x, f(x)\rangle$ can be used to evaluate any hypothesis $h(x)$ in supervised learning. Thus in this sense, trajectory trees are reusable.

Now similar to definition of VC theory for classification methods:

Our goal now is to establish uniform convergence results that bound the error of the estimates $V^\pi(s_0)$ as a function of the "sample size" (number of trees) $m$.

And finally, we have the following theorem:

Let $\Pi$ be any finite class of deterministic strategies for an arbitrary two-action POMDP $M$. Let $m$ trajectory trees be created using a generative model for $M$, and $\widehat{V}^\pi(s_0)$ be the resulting estimates. If $m = O((V_{\max}/\epsilon)^2(\log(|\Pi|) + \log(1/\delta)))$, then with probability $1 - \delta$, $|V^\pi(s_0) - \widehat{V}^\pi(s_0)|\leqslant \epsilon$ holds simultaneously for all $\pi \in \Pi$.

About the VC dimension of $\Pi$, if we suppose we have two actions $\{a_1, a_2\}$ (it can be generalized to more actions), we can say:

If $\Pi$ is a (possibly infinite) set of deterministic strategies, then each strategy $\pi \in \Pi$ is simply a deterministic function mapping from the set of observable histories to the set $\{a_1, a_2\}$, and is thus a boolean function on observable histories. We can, therefore, write $\mathcal{VC}(\Pi)$ to denote the familiar VC dimension of the set of binary functions $\Pi$. For example, if $\Pi$ is the set of all thresholded linear functions of the current vector of observations (a particular type of memoryless strategy), then $\mathcal{VC}(\Pi)$ simply equals the number of parameters.

and the following theorem:

Let $\Pi$ be any class of deterministic strategies for an arbitrary two-action POMDP $M$, and let $\mathcal{VC}(\Pi)$ denote its VC dimension. Let $m$ trajectory trees be created using a generative model for $M$, and $\widehat{V}^\pi(s_0)$ be the resulting estimates. If: $$ m = O((V_{\max}/\epsilon)^2(H_\epsilon\mathcal{VC}(\Pi)\log(V_{\max}/\epsilon) + \log(1/\delta))) $$ then with probability $1 - \delta$, $|V^\pi(s_0) - \widehat{V}^\pi(s_0)|\leqslant \epsilon$ holds simultaneously for all $\pi \in \Pi$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.