Value Function

The value function is defined by a recursive relationship formalized in the Bellman Equation. It decomposes the value of a state into the immediate reward plus the discounted value of the successor state. This property enables dynamic programming solutions by bootstrapping from future estimates. The equation exists in two forms: the Bellman Expectation Equation for a given policy and the Bellman Optimality Equation for the optimal policy.

Value functions bifurcate into two distinct but related concepts. The State-Value Function V(s) estimates expected return starting from state s and following a policy thereafter. The Action-Value Function Q(s,a) estimates expected return starting from state s, taking action a, and then following the policy. The relationship is defined by: V(s) = Σ π(a|s)Q(s,a). In model-free control, Q-functions are preferred because they allow action selection without a transition model.

The discount factor γ ∈ [0,1] is a critical hyperparameter that determines the present value of future rewards. A γ close to 0 makes the agent myopic, prioritizing immediate gratification. A γ close to 1 makes the agent farsighted, valuing distant rewards nearly as much as immediate ones. Mathematically, γ ensures the infinite sum of rewards converges to a finite value in continuing tasks. It also controls the effective horizon of planning.

A value function is always defined with respect to a specific policy π. The value V^π(s) represents the expected return if the agent starts in state s and follows policy π forever. Changing the policy changes the value function. The goal of policy iteration is to find the policy π* that maximizes the value for all states, yielding the optimal value function V*. This dependency makes value functions tools for both evaluation and improvement.

The value function is learned incrementally through the TD Error, which measures the difference between the current value estimate and a better, bootstrapped estimate. The error signal is: δ_t = R_{t+1} + γ V(S_{t+1}) - V(S_t). This scalar drives all weight updates in methods like TD(0) and Q-Learning. Unlike Monte Carlo methods, TD learning updates estimates based on other learned estimates without waiting for the episode's final outcome, enabling online, incremental learning.

Under specific conditions, value function learning algorithms are guaranteed to converge to the true optimal values. Tabular Q-Learning converges to Q* with probability 1 if all state-action pairs are visited infinitely often and the learning rate satisfies the Robbins-Monro conditions. Linear function approximation with on-policy TD learning converges to a fixed point near the true value. However, non-linear function approximators like deep neural networks in DQN have no theoretical convergence guarantees, relying instead on empirical stability tricks like experience replay and target networks.