# Is the VC Dimension meaningful in the context of Reinforcement Learning?

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

## 1 Answer

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$$.