Policy

Policies are often represented by a parameterized function approximator.

• Tabular: The policy is a direct lookup table for discrete state-action spaces.
• Linear Function: π(a|s) is based on a linear combination of state features (e.g., θ^T φ(s,a)).
• Deep Neural Network: A policy network with weights θ takes state s as input and outputs action probabilities or a deterministic action. This enables generalization to unseen states and is the foundation of Policy Gradient methods like REINFORCE and PPO.

An optimal policy π* is one that maximizes the expected cumulative reward (return). The fundamental theorem of dynamic programming guarantees that policies can be iteratively improved. Given a policy π and its value function V^π, a new policy π' can be derived that is greedy with respect to V^π. The Policy Improvement Theorem proves that π' is always equal to or better than π. This is the core principle behind algorithms like Policy Iteration.

This distinction defines how an agent learns and updates its policy.

• On-Policy: The agent learns the value of the policy it is currently executing. It must explore using this same policy (e.g., SARSA, PPO). The behavior policy and target policy are identical.
• Off-Policy: The agent learns about a target policy (often the optimal one) while following a different behavior policy for exploration (e.g., Q-Learning, DDPG). This allows learning from historical data or demonstrations.

Policies and value functions are dual concepts in RL. A value function (V(s) or Q(s,a)) evaluates the goodness of states or actions under a given policy π.

• Given a policy π, one can compute its value function.
• Given a value function Q(s,a), one can derive a greedy policy: π(s) = argmax_a Q(s,a).

Actor-Critic architectures explicitly separate these: an actor (the policy) selects actions, and a critic (the value function) evaluates them, providing a learning signal to improve the actor.

The fundamental dilemma a policy must manage: choosing between exploring new actions to gather information and exploiting known actions that yield high reward.

• ε-Greedy Policy: A simple strategy where the agent selects the greedy (best-known) action with probability 1-ε and a random action with probability ε.
• Softmax (Boltzmann) Policy: Actions are selected probabilistically based on their estimated values, favoring high-value actions but not excluding others.
• Upper Confidence Bound (UCB): Algorithms like Upper Confidence Bound for Trees (UCT) formalize this trade-off by adding an exploration bonus to the value estimate, encouraging visits to less-explored nodes.

A class of reinforcement learning algorithms that optimize a parameterized policy π(a|s; θ) directly by ascending the gradient of expected return with respect to the policy parameters θ.

• REINFORCE: A Monte Carlo policy gradient algorithm that uses complete episode returns.
• Actor-Critic Methods: Hybrid architectures where an actor (the policy) is updated using feedback from a critic (a value function), reducing variance in gradient estimates.
• Proximal Policy Optimization (PPO): A state-of-the-art policy gradient method that constrains policy updates to prevent destructively large changes, ensuring stable training.

An optimal policy π* is a policy that achieves the maximum possible expected return from all states. It is the solution to a sequential decision-making problem.

• Bellman Optimality Equation: Defines the optimal value functions: V*(s) = max_a Σ P(s'|s,a)[R(s,a,s') + γV*(s')]. The optimal policy is the greedy policy with respect to V* or Q*.
• Uniqueness: While the optimal value function is unique, there can be multiple optimal policies that achieve the same maximum return.
• Algorithms like Q-Learning and Policy Iteration are proven to converge to an optimal policy under standard conditions.

A key classification of policies based on whether their action selection rules change over time.

• Stationary Policy: A policy π(a|s) that does not change over time. It is a fixed mapping from states to action distributions. Most learned policies in RL converge to a stationary policy.
• Non-Stationary Policy: A policy π_t(a|s) that can select different actions for the same state at different time steps t. These are common in finite-horizon problems or during the learning process itself.
• In Monte Carlo Tree Search, the tree policy used during selection/expansion is non-stationary, as it updates based on simulation results, while the final recommendation is a deterministic policy derived from the search statistics.