Policy

A deterministic policy maps a state to a single, specific action: π(s) = a. This is common in control systems and game-playing agents where a single optimal action is desired.

A stochastic policy maps a state to a probability distribution over actions: π(a|s). This is essential for exploration in RL and modeling real-world uncertainty. For example, a robot's navigation policy might assign a 70% probability to moving forward and 30% to scanning when in an unfamiliar corridor.

A stationary policy is time-invariant; its action selection depends only on the current state, not on the timestep. Most optimal policies for Markov Decision Processes are stationary.

A non-stationary policy can change over time, π_t(s) = a. This is used in finite-horizon problems or during training phases where an exploration schedule (like epsilon-greedy decay) is applied. The policy itself is a function of time.

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.

A value function estimates the long-term expected return from a given state or state-action pair, guiding policy improvement. It answers "how good" a state is.

• State-Value Function (V(s)): Estimates the expected return starting from state s and following policy π thereafter.
• Action-Value Function (Q(s,a)): Estimates the expected return after taking action a in state s and then following policy π.
• Bellman Equation: The recursive foundation for value functions: V(s) = Σ π(a|s) * Σ P(s'|s,a)[R(s,a,s') + γV(s')]. Policies are improved by acting greedily with respect to the value function.

The reward function R(s, a, s') provides the immediate, scalar feedback signal that defines the agent's goal. It is the primary driver for learning a policy.

• Sparse vs. Dense Rewards: Sparse rewards (e.g., +1 for winning, 0 otherwise) make policy learning difficult. Dense rewards provide incremental feedback.
• Reward Shaping: The practice of designing additional reward signals to guide the agent toward desired behaviors, which can inadvertently lead to unintended reward hacking if the agent exploits loopholes in the shaping.
• The policy's objective is to maximize the cumulative sum of these rewards (the return).

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.