Answers.Body: <p>If I understand your question correctly, the significance of this is due to the fact that <span class="math-container">$s'$</span> is random. In the RHS of the equation it is assumed that <span class="math-container">$V(\cdot)$</span> is known for each state, but the quantity is measuring the expected value of the next state given the current state and action.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-21T17:07:16.500Z
Answers.Text: I think i understand. This would mean that $s'$ means different things on the left and the right in a sense.
Answers.UserDisplayName: ijuneja
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-21T17:20:10.740Z
Answers.Text: Yeah, exactly. Note that s' is the index in the sum
Answers.UserDisplayName: harwiltz
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-21T14:53:24.033Z
Answers.LastActivityDate: 2020-07-21T14:53:24.033Z
Answers.UserDisplayName: harwiltz
Body: <p>In <a href="http://jmlr.csail.mit.edu/papers/volume7/evendar06a/evendar06a.pdf" rel="nofollow noreferrer">the paper</a> - &quot;Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems&quot;, on page 1083, on the 6th line from the bottom, the authors define expectation of the empirical model as
  <span class="math-container">$$\hat{\mathbb{E}}_{s,s',a}[V(s')] = \sum_{s' \in S} \hat{P}^{a}_{s, s'}V(s').$$</span>
  I didn't understand the significance of this quantity since it puts <span class="math-container">$V(s')$</span> inside an expectation while assuming the knowledge of <span class="math-container">$V(s')$</span> in the definition on the right.</p>
  <p>A clarification in this regard would be appreciated.</p>
  <p>EDIT:
  The paper defines <span class="math-container">$\hat{P}^{a}_{s, s'}$</span> as,
  <span class="math-container">$$\hat{P}^{a}_{s, s'} = \frac{|(s, a, s', t)|}{|(s, a, t)|}.$$</span>
  Where <span class="math-container">$|(s, a, t)|$</span> is the number of times state <span class="math-container">$s$</span> was visited and action <span class="math-container">$a$</span> was taken and <span class="math-container">$|(s, a, s', t)|$</span> as the number of times among the <span class="math-container">$|(s, a, t)|$</span> times <span class="math-container">$(s, a)$</span> was visited when the next state landed in was <span class="math-container">$s'$</span> during model learning.</p>
  <p>No explicit definition for <span class="math-container">$V$</span> is provided however, <span class="math-container">$V^{\pi}$</span> is defined as the usual expected discounted return, using the same definition as Sutton and Barto or other sources.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-21T13:20:26.547Z
Comments.Text: I think I can interpret this if the LHS was $\mathbb{\hat{E}}_{s,a}[V(s')]$ . . . does the paper definitely show $\mathbb{\hat{E}}_{s,s', a}$? Does the paper define $V$ in this context?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-21T13:39:52.477Z
Comments.Text: @NeilSlater the paper does use $s, s', a$ in the notation. have edited to add details
Comments.UserDisplayName: ijuneja
Tags: <model-based-methods><pac-learning>
Title: What is the expectation of an empirical model in model based RL?
UserDisplayName: ijuneja
ThreadText: # What is the expectation of an empirical model in model based RL?
  
  (Asked by: username_0 on 2020-07-21)
  
  In [the paper](http://jmlr.csail.mit.edu/papers/volume7/evendar06a/evendar06a.pdf) - "Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems", on page 1083, on the 6th line from the bottom, the authors define expectation of the empirical model as
  $$\hat{\mathbb{E}}\_{s,s',a}[V(s')] = \sum\_{s' \in S} \hat{P}^{a}\_{s, s'}V(s').$$
  I didn't understand the significance of this quantity since it puts $V(s')$ inside an expectation while assuming the knowledge of $V(s')$ in the definition on the right.
  
  A clarification in this regard would be appreciated.
  
  EDIT:
  The paper defines $\hat{P}^{a}\_{s, s'}$ as,
  $$\hat{P}^{a}\_{s, s'} = \frac{|(s, a, s', t)|}{|(s, a, t)|}.$$
  Where $|(s, a, t)|$ is the number of times state $s$ was visited and action $a$ was taken and $|(s, a, s', t)|$ as the number of times among the $|(s, a, t)|$ times $(s, a)$ was visited when the next state landed in was $s'$ during model learning.
  
  No explicit definition for $V$ is provided however, $V^{\pi}$ is defined as the usual expected discounted return, using the same definition as Sutton and Barto or other sources.
  
  **Tags:** model-based-methods, pac-learning
  > **Comments:**
  > **username_1**: I think I can interpret this if the LHS was $\mathbb{\hat{E}}_{s,a}[V(s')]$ . . . does the paper definitely show $\mathbb{\hat{E}}_{s,s', a}$? Does the paper define $V$ in this context?  
  > **username_0**: @NeilSlater the paper does use $s, s', a$ in the notation. have edited to add details  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-07-21. Score: 1 | Accepted answer
  
  If I understand your question correctly, the significance of this is due to the fact that $s'$ is random. In the RHS of the equation it is assumed that $V(\cdot)$ is known for each state, but the quantity is measuring the expected value of the next state given the current state and action.
  
  > **Comments:**
  > **username_0**: I think i understand. This would mean that $s'$ means different things on the left and the right in a sense.  
  > **username_2**: Yeah, exactly. Note that s' is the index in the sum  
  
  ---
  
  