Answers.Body: <p>Yes, it is. <a href="http://papers.nips.cc/paper/1664-approximate-planning-in-large-pomdps-via-reusable-trajectories.pdf" rel="nofollow noreferrer">This article</a> (Approximate Planning in Large POMDPs via Reusable Trajectories) explain about it by means of the trajectory tree:</p>
  <blockquote>
  <p>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 <span class="math-container">$H_\epsilon$</span>, so it will have about <span class="math-container">$2^{H_\epsilon}$</span> nodes. The root is labeled by <span class="math-container">$s_0$</span> and the observation there, <span class="math-container">$o_0$</span>.</p>
  </blockquote>
  <p>Now a policy <span class="math-container">$\pi$</span> will be defined like the following base on the trajectory tree:</p>
  <blockquote>
  <p>For any deterministic strategy <span class="math-container">$\pi$</span> and any trajectory tree <span class="math-container">$T$</span>, <span class="math-container">$\pi$</span> defines a path through
  <span class="math-container">$T$</span>: <span class="math-container">$\pi$</span> starts at the root, and inductively, if <span class="math-container">$\pi$</span> is at some internal node in <span class="math-container">$T$</span>, then we feed to <span class="math-container">$\pi$</span> the observable history along the path from the root to that node, and <span class="math-container">$\pi$</span> selects and moves to a child of the current node. This continues until a leaf node is reached, and we define <span class="math-container">$R(\pi, T)$</span> to be the discounted sum of returns along the path taken. In the case that <span class="math-container">$\pi$</span> is stochastic, <span class="math-container">$\pi$</span> defines a distribution on paths in <span class="math-container">$T$</span>, and <span class="math-container">$R(\pi, T)$</span> is the expected return according to this distribution.  Hence, given <span class="math-container">$m$</span> trajectory trees <span class="math-container">$T_1 , \ldots , T_m$</span>, a natural estimate for <span class="math-container">$V^\pi(s_0)$</span> is <span class="math-container">$V^\pi(s_0) = \frac{1}{m}\sum_{i=1}^mR(\pi, T_i)$</span>. *Note that each tree can be used to evaluate any
  strategy, much the way a single labeled example <span class="math-container">$\langle x, f(x)\rangle$</span> can be used to evaluate any hypothesis <span class="math-container">$h(x)$</span> in supervised learning. Thus in this sense, trajectory trees are reusable.</p>
  </blockquote>
  <p>Now similar to definition of VC theory for classification methods:</p>
  <blockquote>
  <p>Our goal now is to establish uniform convergence results that bound the error of the estimates <span class="math-container">$V^\pi(s_0)$</span> as a function of the &quot;sample size&quot; (number of trees) <span class="math-container">$m$</span>.</p>
  </blockquote>
  <p>And finally, we have the following theorem:</p>
  <blockquote>
  <p>Let <span class="math-container">$\Pi$</span> be any finite class of deterministic strategies for an arbitrary two-action <strong>POMDP</strong> <span class="math-container">$M$</span>. Let <span class="math-container">$m$</span> trajectory trees be created using a generative model for <span class="math-container">$M$</span>, and
  <span class="math-container">$\widehat{V}^\pi(s_0)$</span> be the resulting estimates. If <span class="math-container">$m = O((V_{\max}/\epsilon)^2(\log(|\Pi|) + \log(1/\delta)))$</span>, then with probability <span class="math-container">$1 - \delta$</span>, <span class="math-container">$|V^\pi(s_0) - \widehat{V}^\pi(s_0)|\leqslant \epsilon$</span> holds simultaneously for all <span class="math-container">$\pi \in \Pi$</span>.</p>
  </blockquote>
  <p>About the VC dimension of <span class="math-container">$\Pi$</span>, if we suppose we have two actions <span class="math-container">$\{a_1, a_2\}$</span> (it can be generalized to more actions), we can say:</p>
  <blockquote>
  <p>If <span class="math-container">$\Pi$</span> is a (possibly infinite) set of deterministic strategies, then each strategy <span class="math-container">$\pi \in \Pi$</span> is simply a deterministic function mapping from the set of observable histories to the set <span class="math-container">$\{a_1, a_2\}$</span>,
  and is thus a boolean function on observable histories. We can, therefore, write <span class="math-container">$\mathcal{VC}(\Pi)$</span> to
  denote the familiar VC dimension of the set of binary functions <span class="math-container">$\Pi$</span>. For example, if <span class="math-container">$\Pi$</span> is
  the set of all thresholded linear functions of the current vector of observations (a particular
  type of memoryless strategy), then <span class="math-container">$\mathcal{VC}(\Pi)$</span> simply equals the number of parameters.</p>
  </blockquote>
  <p>and the following theorem:</p>
  <blockquote>
  <p>Let <span class="math-container">$\Pi$</span> be any class of deterministic strategies for an arbitrary two-action
  POMDP <span class="math-container">$M$</span>, and let <span class="math-container">$\mathcal{VC}(\Pi)$</span> denote its VC dimension. Let <span class="math-container">$m$</span> trajectory trees be created using a generative model for <span class="math-container">$M$</span>, and <span class="math-container">$\widehat{V}^\pi(s_0)$</span> be the resulting estimates. If:
  <span class="math-container">$$
  m = O((V_{\max}/\epsilon)^2(H_\epsilon\mathcal{VC}(\Pi)\log(V_{\max}/\epsilon) + \log(1/\delta)))
  $$</span>
  then with probability <span class="math-container">$1 - \delta$</span>, <span class="math-container">$|V^\pi(s_0) - \widehat{V}^\pi(s_0)|\leqslant \epsilon$</span> holds simultaneously for all <span class="math-container">$\pi \in \Pi$</span>.</p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-19T12:00:12.957Z
Answers.LastActivityDate: 2020-06-19T13:26:04.673Z
Answers.LastEditDate: 2020-06-19T13:26:04.673Z
Answers.UserDisplayName: OmG
Body: <p>Is the VC dimension meaningful for reinforcement learning (RL), as a machine learning (ML) method? How?</p>
  
Tags: <machine-learning><reinforcement-learning><computational-learning-theory><vc-dimension><vc-theory>
Title: Is the VC Dimension meaningful in the context of Reinforcement Learning?
UserDisplayName: OmG
ThreadText: # Is the VC Dimension meaningful in the context of Reinforcement Learning?
  
  (Asked by: username_0 on 2020-06-19)
  
  Is the VC dimension meaningful for reinforcement learning (RL), as a machine learning (ML) method? How?
  
  **Tags:** machine-learning, reinforcement-learning, computational-learning-theory, vc-dimension, vc-theory
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2020-06-19. Score: 2 | Accepted answer
  
  Yes, it is. [This article](http://papers.nips.cc/paper/1664-approximate-planning-in-large-pomdps-via-reusable-trajectories.pdf) (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$.
  
  
  ---
  
  