JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Optimality and Improvement: Climbing Toward the Best Policy

Greedy improvement never makes a policy worse — loop it with evaluation and you reach the optimal policy. The skeleton of every RL method.

What 'optimal' means

We can finally say precisely what RL is trying to find. A policy is optimal when no other policy achieves a higher expected return from any state. Remarkably, in a finite MDP such a policy always exists, and there is a single optimal value function V* (and Q*) that every optimal policy shares. The optimal policy is then easy to read off: in each state, take the action that maximizes Q* — a greedy choice with respect to the optimal values.

V^*(s) = \max_{a}\sum_{s',r} p(s',r \mid s,a)\bigl[r + \gamma\, V^*(s')\bigr]

The Bellman optimality equation defines V*: solving an MDP means finding this value, and the optimal policy falls out for free.

Greedy improvement: acting on a value function

Suppose you have the value function of some current policy π — not optimal, just whatever you have now. Here is the key move: build a new policy that acts greedily with respect to Q_π, choosing the best action according to your current estimates. Intuitively, you are saying 'for one step, do the best thing my current knowledge suggests, then continue as before.' This new greedy policy is the raw material of improvement.

\pi'(s) = \operatorname*{arg\,max}_{a} Q_\pi(s,a) = \operatorname*{arg\,max}_{a}\sum_{s',r} p(s',r \mid s,a)\bigl[r + \gamma\, V_\pi(s')\bigr]

Acting greedily: the improved policy picks, in each state, the action with the highest Q_pi value.

The policy improvement theorem

Does acting greedily actually help, or could it backfire? The policy improvement theorem gives the guarantee: the greedy policy with respect to V_π is never worse than π, and is strictly better unless π was already optimal. This is the theoretical bedrock of RL — it promises that 'evaluate, then act greedily' is a staircase that only goes up. The advantage makes the reason vivid: greedy improvement picks actions with positive advantage, which by definition beat the policy's current baseline.

Generalized policy iteration

Put the two pieces in a loop and you get the master pattern of RL. Evaluate the current policy to get its value, then improve the policy by acting greedily on that value; repeat. This dance — value chasing the policy, policy chasing the value — is generalized policy iteration (GPI), and almost every algorithm is a special case of it.

  1. Start with any policy π.
  2. Evaluation: compute (or estimate) V_π / Q_π for the current π.
  3. Improvement: set π to be greedy with respect to those values.
  4. Repeat. Evaluation and improvement pull toward the same fixed point — the optimal policy.
Watch generalized policy iteration in action: evaluation and improvement loop on a gridworld until the policy climbs to optimal.

Interactive gridworld where repeated evaluation and greedy improvement steps converge to the optimal policy.

How algorithms instantiate GPI

The variants differ only in how completely they evaluate before improving. Policy iteration evaluates fully, then improves. Value iteration takes a single Bellman-optimality sweep between improvements — collapsing the two steps into one. Dynamic programming does this with a known model; Monte Carlo and temporal-difference methods do it from sampled experience when the model is unknown; and policy-gradient methods do a 'soft' version, nudging the policy toward high-advantage actions a little at a time.

Seeing the pattern is the payoff of this whole track. Returns define the goal, value functions measure progress, Bellman equations make value computable, and GPI turns measurement into a steadily improving policy. Every algorithm you meet later — from DQN to PPO — is a particular way of running this same loop.

Recap