PolicyEvaluation

PolicyEvaluation refers to the process of determining the value of a fixed policy in a Markov decision process (MDP). The goal is to compute the expected discounted return when following the given policy from each state, enabling assessment of policy quality without altering the policy itself. The action-value counterpart, Q^π(s, a), describes the expected return starting from state s, taking action a, and thereafter following π.

Formally, for a policy π and discount factor γ in [0, 1), the value function is V^π(s) = Eπ[ Σ_{t=0}^∞ γ^t R(S_t, A_t, S_{t+1}) | S_0 = s ]. The Bellman expectation equation for policy evaluation is V^π(s) = Σ_a π(a|s) Σ_{s'} P(s'|s, a) [ R(s, a, s') + γ V^π(s') ]. In finite MDPs this becomes a linear system V^π = R^π + γ P^π V^π, where P^π captures transitions under π and R^π the expected immediate rewards.

Algorithms vary from exact to approximate. Exact solutions solve the linear equations directly; iterative policy evaluation updates V_{k+1}(s) = Σ_a π(a|s) Σ_{s'} P(s'|s, a) [ R(s, a, s') + γ V_k(s') ] until convergence (guaranteed for γ < 1). Stochastic methods include Monte Carlo policy evaluation, which estimates V^π(s) from episodes, and temporal-difference methods (e.g., TD(0)), which bootstrap with V(S_t) ← V(S_t) + α [ R_{t+1} + γ V(S_{t+1}) − V(S_t) ].

Policy evaluation is a foundational step in policy iteration and many actor-critic algorithms, providing the value estimates used to improve or adjust policies. It faces challenges in large or continuous state spaces, often requiring function approximation.