Answers.Body: <p>1): The intuition is based on the concept of <em>value iteration</em>, which the authors mention but don't explain on page 504. The basic idea is this: imagine you knew the value of starting in state x and executing an optimal policy for n timesteps, for every state x. If you wanted to know the optimal policy (and it's value) for running for n+1 timesteps in each location, this is now easy to compute. The optimal action from state x is whichever one maximizes the sum of the reward for this timestep (r) and the value of executing an optimal n-step policy from the state you'd end up in after (or expected value if the problem isn't deterministic). </p>
  
  <p>In the approach of the paper, you're not going to compute either the policy or the value explicitly (probably because it's too expensive), so you just approximate the Q function for the n+1 problem.</p>
  
  <p>IIRC, as long as your problem has a discounting factor and the error in your function approximation isn't too large, there are proofs (see <a href="https://rads.stackoverflow.com/amzn/click/0136042597" rel="nofollow noreferrer">Russell &amp; Norvig</a>'s chapter on RL (18?)) that your policy will eventually stop changing in-between updates, and will be consistent with the policy for an infinite number of steps. Intuitively, this is because the discounting factor causes a series for the rewards to be convergent.</p>
  
  <p>2): I <em>think</em> that's right. When you build the training set, use the actions suggested by the results for the $$Q_{n-1}$$ network. That's an approximation of the reward for starting in each state and running for n-1 steps with an optimal policy. Then you're learning an approximation of $Q_n$ from that, which looks right.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-08T00:07:08.443Z
Answers.LastActivityDate: 2018-08-08T00:07:08.443Z
Answers.UserDisplayName: John Doucette
Body: <p>I hope to get some clarifications on Fitted Q-Iteration (FQI).</p>
  <p><strong>My Research So Far</strong></p>
  <p>I've read <a href="http://incompleteideas.net/book/the-book-2nd.html" rel="nofollow noreferrer">Sutton's book</a> (specifically, ch 6 to 10), <a href="http://www.jmlr.org/papers/volume6/ernst05a/ernst05a.pdf" rel="nofollow noreferrer">Ernst et al</a> and <a href="https://pdfs.semanticscholar.org/5c65/d095600d6c647426fa3bc45031b208882d5f.pdf" rel="nofollow noreferrer">this paper</a>.</p>
  <p>I know that <span class="math-container">$Q^*(s, a)$</span> expresses the expected value of first taking action <span class="math-container">$a$</span> from state <span class="math-container">$s$</span> and then following optimal policy forever.</p>
  <p>I tried my best to understand function approximation in large state spaces and TD(<span class="math-container">$n$</span>).</p>
  <p><strong>My Questions</strong></p>
  <ol>
  <li><p>Concept - Can someone explain the intuition behind how iteratively extending N from 1 until stopping condition achieves optimality (Section 3.5 of Ernst et al.)? I have difficulty wrapping my mind around how this ties in with the basic definition of <span class="math-container">$Q^*(s, a)$</span> that I stated above.</p>
  </li>
  <li><p>Implementation - Ernst et al. gives the pseudo-code for the tabular form. But if I try to implement the <em>function approximation</em> form, is this correct:</p>
  </li>
  </ol>
  <pre><code>Repeat until stopping conditions are reached:
      - N ← N + 1
      - Build the training set TS based on the function Q^{N − 1} and on the full set of four-tuples F 
  
      - Train the algorithm on the TS
  
      - Use the trained model to predict on the TS itself
  
      - Create TS for the next N by updating the labels - new reward plus (gamma * predicted values )
  </code></pre>
  <p>I am just starting to learn RL as part of my course. Thus, there are many gaps in my understanding. Hope to get some kind guidance.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-07-18T18:48:36.470Z
Comments.Text: Hello. Please, next time, **ask only one question per post**. If you have multiple questions, create one post for each of them, even though they are related, so that people can focus on 1 question at time.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><q-learning><papers><value-iteration>
Title: How is the fitted Q-iteration algorithm related to $Q^*(s, a)$, and how can we use function approximation with this algorithm?
UserDisplayName: NoviceProg
ThreadText: # How is the fitted Q-iteration algorithm related to $Q^*(s, a)$, and how can we use function approximation with this algorithm?
  
  (Asked by: username_0 on 2018-08-07)
  
  I hope to get some clarifications on Fitted Q-Iteration (FQI).
  
  **My Research So Far**
  
  I've read [Sutton's book](http://incompleteideas.net/book/the-book-2nd.html) (specifically, ch 6 to 10), [Ernst et al](http://www.jmlr.org/papers/volume6/ernst05a/ernst05a.pdf) and [this paper](https://pdfs.semanticscholar.org/5c65/d095600d6c647426fa3bc45031b208882d5f.pdf).
  
  I know that $Q^\*(s, a)$ expresses the expected value of first taking action $a$ from state $s$ and then following optimal policy forever.
  
  I tried my best to understand function approximation in large state spaces and TD($n$).
  
  **My Questions**
  
  1. Concept - Can someone explain the intuition behind how iteratively extending N from 1 until stopping condition achieves optimality (Section 3.5 of Ernst et al.)? I have difficulty wrapping my mind around how this ties in with the basic definition of $Q^\*(s, a)$ that I stated above.
  2. Implementation - Ernst et al. gives the pseudo-code for the tabular form. But if I try to implement the *function approximation* form, is this correct:
  
  ```
  Repeat until stopping conditions are reached:
      - N ← N + 1
      - Build the training set TS based on the function Q^{N − 1} and on the full set of four-tuples F 
  
      - Train the algorithm on the TS
  
      - Use the trained model to predict on the TS itself
  
      - Create TS for the next N by updating the labels - new reward plus (gamma * predicted values )
  
  ```
  
  I am just starting to learn RL as part of my course. Thus, there are many gaps in my understanding. Hope to get some kind guidance.
  
  **Tags:** reinforcement-learning, q-learning, papers, value-iteration
  
  > **Comments:**
  > **username_1**: Hello. Please, next time, **ask only one question per post**. If you have multiple questions, create one post for each of them, even though they are related, so that people can focus on 1 question at time.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2018-08-08. Score: 3 | Accepted answer
  
  1): The intuition is based on the concept of *value iteration*, which the authors mention but don't explain on page 504. The basic idea is this: imagine you knew the value of starting in state x and executing an optimal policy for n timesteps, for every state x. If you wanted to know the optimal policy (and it's value) for running for n+1 timesteps in each location, this is now easy to compute. The optimal action from state x is whichever one maximizes the sum of the reward for this timestep (r) and the value of executing an optimal n-step policy from the state you'd end up in after (or expected value if the problem isn't deterministic).
  
  In the approach of the paper, you're not going to compute either the policy or the value explicitly (probably because it's too expensive), so you just approximate the Q function for the n+1 problem.
  
  IIRC, as long as your problem has a discounting factor and the error in your function approximation isn't too large, there are proofs (see [Russell & Norvig](https://rads.stackoverflow.com/amzn/click/0136042597)'s chapter on RL (18?)) that your policy will eventually stop changing in-between updates, and will be consistent with the policy for an infinite number of steps. Intuitively, this is because the discounting factor causes a series for the rewards to be convergent.
  
  2): I *think* that's right. When you build the training set, use the actions suggested by the results for the $$Q\_{n-1}$$ network. That's an approximation of the reward for starting in each state and running for n-1 steps with an optimal policy. Then you're learning an approximation of $Q\_n$ from that, which looks right.
  
  
  ---
  
  