Policy Evaluation in Reinforcement Learning

Reinforcement learning agents must evaluate both situations and decisions. A state describes where the agent is, while an action describes what the agent does from that state. The optimal value functions organize these two perspectives: v*(s) evaluates a state, and q*(s, a) evaluates a particular action in a particular state.

The word maximum is important. A state may be evaluated under different policies, and those policies can produce different expected returns from that same starting state. v*(s) identifies the largest expected return achievable from the state. It therefore describes the best state-level outcome, rather than the outcome of one arbitrarily selected policy.

q*(s, a) contains more specific information about the initial decision than v*(s) does. v*(s) describes the best expected return associated with the state as a whole. q*(s, a) keeps the selected initial action visible, so it evaluates a state-action pair rather than only the starting state.

A useful mental sequence is to identify the state, identify a candidate action, evaluate that state-action pair with q*(s, a), and then relate the action-specific evaluation to the optimal state-level evaluation v*(s). The functions answer related questions, but they do not preserve the same amount of decision detail.

Reinforcement-learning environments may contain too many states for exact tabular storage. An agent may therefore be unable to store one exact entry for every state. The limitation is not only what the agent knows about the environment; it is also what the agent can store and compute.

Memory is needed for state information as well as for approximations of value functions, policies, and models. Computation can also be limiting: even with a complete and accurate environment model, an agent might not have enough time to perform all necessary computations at every time step.

Optimality is useful as a theoretical target even when an agent cannot reach an optimal solution exactly. The optimal value functions describe the best expected returns associated with states and state-action choices. They provide a reference point for understanding what an agent is trying to approximate.

In practice, limited memory and computation can prevent exact storage or complete calculation. The resulting value function, policy, or model may therefore be an approximation of the optimal one. Aiming for optimality and achieving an approximation are different claims: the first describes the objective, while the second describes the result that resource limits may permit.