Policy (in RL/Planning)

Policies can be represented in various forms, impacting their expressiveness and learnability:

• Tabular: A simple lookup table for discrete state and action spaces.
• Parametric (e.g., Neural Network): A function approximator like a deep neural network that can generalize to unseen states, essential for large or continuous spaces. The weights of the network are the policy parameters.
• Symbolic/Logic-based: A set of rules or conditions, common in classical planning domains. The choice of representation directly affects the policy search process during learning.

A stationary policy is one where the action choice depends only on the current state (or belief state), not on the time step. Most MDP formulations assume stationary policies. A non-stationary policy can select different actions for the same state at different time steps, which can be necessary for finite-horizon problems or when the environment's dynamics change over time. In planning, a contingent policy (a plan tree) is inherently non-stationary, as future actions depend on prior observations.

A policy is a more general concept than a simple plan (a linear sequence of actions). A plan is one possible rollout or trajectory generated by following a specific policy. Conversely, an optimal policy can be derived from an optimal value function (V*(s) or Q*(s,a)) by acting greedily with respect to it. In model-based RL and planning, policies are often evaluated and improved by simulating their outcomes using an internal world model.

A critical characteristic, especially during learning, is how the policy balances exploration (trying new actions to gather information) and exploitation (choosing the best-known action to maximize reward). Stochastic policies naturally facilitate exploration. Algorithms address this explicitly: ε-greedy policies exploit most of the time but explore randomly with probability ε, while policies optimized via the Upper Confidence Bound (UCB) principle, as used in Monte Carlo Tree Search (MCTS), quantify uncertainty to guide exploration intelligently.

A value function estimates the long-term desirability of being in a state (or of taking an action from a state) under a given policy. The two primary types are:

• State-Value Function Vπ(s): The expected return (cumulative reward) starting from state s and following policy π thereafter.
• Action-Value Function Qπ(s, a): The expected return starting from state s, taking action a, and thereafter following policy π. The Bellman equation provides a recursive definition for these functions. The optimal policy π* is intimately linked to the optimal value functions V* and Q*; it is defined by selecting actions that maximize Q*(s, a).

Policy gradient methods are a class of reinforcement learning algorithms that directly optimize the parameters θ of a parameterized policy π_θ(a|s). Instead of learning value functions and deriving a policy (as in Q-learning), they adjust θ to maximize the expected reward J(θ) using gradient ascent.

• REINFORCE: A Monte Carlo policy gradient algorithm.
• Actor-Critic: Combines a policy (actor) with a value function (critic) to reduce variance in gradient estimates. These methods are particularly effective for high-dimensional or continuous action spaces and are the foundation for many advanced algorithms like Proximal Policy Optimization (PPO) and Soft Actor-Critic (SAC).

Policies are categorized by how they select actions:

• Deterministic Policy: Maps a state (or belief state) directly to a single action, a = μ(s). This is simple and memory-efficient but may not explore the environment sufficiently during learning and can be brittle in stochastic environments.
• Stochastic Policy: Specifies a probability distribution over actions for a given state, π(a|s). This is essential for exploration during training and is often necessary for optimal behavior in adversarial or partially observable settings (e.g., mixed strategies in game theory). Most policy gradient methods learn stochastic policies, while algorithms like Deep Deterministic Policy Gradient (DDPG) learn deterministic ones.

This distinction is crucial in finite-horizon and time-dependent planning problems.

• Stationary Policy: The action choice depends only on the current state (or belief state), not on the time step. π_t(a|s) = π(a|s) for all t. Most infinite-horizon MDPs have optimal policies that are stationary.
• Non-Stationary Policy: The action choice can vary with both the state and the time step, π_t(a|s). These are common in finite-horizon problems where the time remaining influences the optimal decision (e.g., aggressive maneuvers are less desirable near a deadline). Contingent plans in temporal planning often result in non-stationary policies.