1
$\begingroup$

I'm studying reinforcement learning from Prof. Andrew Ng's lecture notes. Here I came across fitted value iteration algorithm for continuous state MDP. It's mentioned that in this algorithm, we are approximating the value function $V(s)$, over a finite number of states ($s^{(1)}, s^{(2)}... s^{(m)}$) using supervised learning algorithm like linear regression.

Why we need to sample a finite set of states from continuous states? If we are sampling the continuous states, doesn't it mean descretization of states?

Also what is the intuition behind the sampling of states and then using supervised learning algorithm to get value function? Why can't we simply use following equation for Value function $V(s)$?

$$V(s) = R(s) + {\gamma}\max_{a}\int_{s'}P_{sa}(s')V(s')ds'$$

$\endgroup$
1
$\begingroup$

Because you usually don't have access to $P_{sa}$, and even if you did the resulting equation hardly seems tractable.

$\endgroup$
1
$\begingroup$

If the state space is high-dimensional, then as explained earlier in the notes, it is not possible to estimate the value function at every discretized state due to the curse of dimensionality.

What we instead do is assume that the value function is given by a linear function of the (kernelized) state: $V(s) = \theta^T \phi(s)$, and then estimate $\theta$ using linear regression from a few state samples.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.