4
$\begingroup$

How does policy evaluation work for continuous state space model-free approaches?

Theoretically, a model-based approach for the discrete state and action space can be computed via dynamic programming and solving the Bellman equation.

Let's say you use a DQN to find another policy, how does model-free policy evaluation work then? I am thinking of Monte Carlo simulation, but that would require many many episodes.

$\endgroup$
3
  • $\begingroup$ Hi calveeen. Great question! To clarify - by policy evaluation, do you mean finding the true action-value function $q_{\pi}(s, a)$ of the current policy $\pi$ during training? Do you mean gauging the performance of the agent after constructing a final, trained policy? Or something else? $\endgroup$
    – DeepQZero
    Jun 11, 2020 at 14:18
  • $\begingroup$ Hi @DeepQZero, thank you for replying. This question seems rather silly as policy evaluation for DQN can be simply done by observing average reward returns. In my case I was not able to work with running the policy in real life. Hence, the way I found to estimate the value of a learnt policy would be through off policy value evaluation, which is the importance sampling and it's variant. $\endgroup$
    – calveeen
    Jun 11, 2020 at 14:30
  • $\begingroup$ Ok I see. For future reference, policy evaluation has a very specific definition in the context of reinforcement learning. It is the process of determining the true state-value $v_{\pi}(s)$ function or action-value function $q_{\pi}(s,a)$ under the current policy $\pi$ for every state and action. It seems that you are interested in gauging the agent's performance in the environment - that is equivalent to determining the state-value of only the start state(s) and separate from the policy evaluation problem. Both are good questions though. $\endgroup$
    – DeepQZero
    Jun 11, 2020 at 14:45

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ I think OP has a fixed policy to evaluate (indirectly asked here by calling out evaluation only, and implied from other questions by same OP), so the parts of the answer referring to deriving policy from Q or GPI need to be adjusted - either separated out to make it clearer which part is which, or could even be removed entirely. $\endgroup$ Jun 11, 2020 at 7:06
  • $\begingroup$ Hi @NeilSlater, and thank you very much for the good advice. It looks like I answered a different question than OP meant to ask - OP was wondering about agent performance (like you pointed out), while I provided an answer about policy eval in the context of GPI for continuous, model-free DRL. Since my answer was accepted, how should I proceed? Should I edit my response to provide more context for my particular answer? I'm very new here and just need some guidance. $\endgroup$
    – DeepQZero
    Jun 11, 2020 at 14:56
  • $\begingroup$ If it has been accepted, probably better to leave as-is. The OP is clearly able to extract the information that they want from the answer, and there's a risk you remove something important to them if you make a major edit as I suggested. $\endgroup$ Jun 11, 2020 at 15:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .