How does policy evaluation work for continuous state space model-free approaches? ... Let's say you use a DQN to find another policy, how does model-free policy evaluation work then?
Policy evaluation is the process of determining state-value $v_{\pi}(s)$ or action-value $q_{\pi}(s, a)$ functions for the current policy. In the context of continuous state and action spaces without a model of the environment, policy evaluation must incorporate the agent's past experience instead of the model dynamics and will generally use a function approximator such as a neural network to estimate the action-values. Many popular approaches apply online updates to the function approximator; e.g., DQN combines Temporal-Difference targets and gradient descent to change the weights of the neural network and the resultant action-value estimates. Since
- we gradually change the weights of the neural network at each gradient descent step,
- the estimated action-values are solely dependent on the weights of the neural network,
- the current policy is solely dependent on the estimated action-values (e.g. DQN takes the action with largest action-value),
then policy evaluation (updating the estimated action-value function to better match the true action-value function under the current policy) and policy improvement (greedily changing the current policy based on the new estimated action-value function) occur simultaneously at each gradient descent step. In DQN, a gradient descent step occurs at each time step.
I am thinking of Monte Carlo simulation, but that would require many many episodes.
After changing the action-value function, we may get a new policy. We assume that the action-value function of the old policy is similar to that of the new policy (although it is not guaranteed) because the change in weights of the neural network was small. Therefore, we use the estimated action-value function of the old policy as an initial estimate of the action-value function of the new policy. Specifically, we use the same neural network with the same weights as the initial approximation. This is computationally convenient, as it prevents the need to start the next policy evaluation update from scratch (e.g. with a Monte Carlo simulation over a painfully large number of episodes).
Theoretically, a model-based approach for the discrete state and action space can be computed via dynamic programming and solving the Bellman equation.
This same technique of using the estimated action-values of the old policy as the initial estimates for the action-values of the new policy is employed by some Dynamic Programming methods such as value iteration, albeit with known dynamics. Generalized Policy Iteration (GPI) is the notion of letting policy evaluation and policy iteration interact on whatever granularity deemed necessary for the problem at hand. A consequence of adopting the GPI paradigm is the choice to halt policy evaluation before convergence of the action-value function. Many deep reinforcement learning algorithms take this to an extreme and perform policy evaluation and policy improvement simultaneously during a single gradient descent step. For reference, Chapter 4 of Sutton and Barto provides a brief summary of these ideas.