How is the fitted Q-iteration algorithm related to $Q^*(s, a)$, and how can we use function approximation with this algorithm?

Question

I hope to get some clarifications on Fitted Q-Iteration (FQI).

My Research So Far

I've read Sutton's book (specifically, ch 6 to 10), Ernst et al and this paper.

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.

Answer 1

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