1
$\begingroup$

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

$\endgroup$

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .