Types of Policies in Decision-Making Systems

What is a Policy?

At its core, a policy, typically denoted by the Greek letter $\pi$ (pi), is the agent's strategy or "behavioral blueprint." It dictates what action the agent will take in any given state. For any state the agent finds itself in, the policy provides the answer to the question, "What should I do now?"

In the context of an MDP, where the future is governed by probabilities, it is natural to define a policy in probabilistic terms. A policy $\pi (a|s)$ is a function that specifies the probability of taking action $a$ while in state $s$:

This formalizes the agent's behavior. Given an MDP, if we also have a policy, the entire system's evolution becomes a stochastic process that we can analyze.

Let's watch a segment from David Silver's lecture that introduces the policy and its role in turning a Markov Reward Process (which lacks agency) into a full Markov Decision Process.

As you saw, a policy completely defines the agent's behavior. However, policies can have different characteristics. They can be classified along two primary axes:

1. Deterministic vs. Stochastic: Does the policy always choose the same action in a state, or does it choose actions according to a probability distribution?
2. Stationary vs. Time-Dependent: Does the policy's rule change over time, or does it remain the same?

Let's break down these distinctions. For a precise and formal overview, we'll turn to a concise reference.

Dimension 1: Deterministic vs. Stochastic

The first distinction concerns the nature of the choice itself.

• A deterministic policy maps each state to a single, specific action. For any state $s$, there is one action $a=\pi (s)$ that the agent will always take. In this case, the probability $\pi (a|s)$ is 1 for that specific action and 0 for all others. Think of it as a fixed lookup table: "If in state $s$, do action $a$".

• A stochastic (or randomized) policy maps each state to a probability distribution over the set of available actions. In a state $s$, the agent might choose action $a_1$ with probability $p_1$, action $a_2$ with probability $p_2$, and so on. The policy $\pi (a|s)$ can take values between 0 and 1, as long as ${\sum }_{a\in A}\pi (a|s)=1$ for every state $s$.

You might wonder why we would ever want a policy to be stochastic. Wouldn't the agent want to be decisive? One of the most important reasons is to balance exploration and exploitation. An agent might need to take actions it doesn't currently believe are the best, just to "explore" and see if they lead to unexpectedly high rewards.

Andrew Ng's lecture on MDPs provides a fantastic explanation of this trade-off and introduces the $ϵ$-greedy policy, a classic example of a simple stochastic policy used in reinforcement learning.

Dimension 2: Stationary vs. Time-Dependent

The second distinction concerns whether the policy changes over time.

• A stationary policy is time-independent. The rule for choosing actions is the same regardless of the time step $t$. If the agent encounters state $s$ at time $t=5$ and again at $t=50$, it will use the exact same logic (the same $\pi (a|s)$) to choose an action. As David Silver mentioned in the first video, the Markov property of the state often makes it sufficient to consider only stationary policies.

• A time-dependent (or non-stationary) policy changes with time. The policy is represented as a sequence $\pi =({\pi }_0,{\pi }_1,{\pi }_2,\dots )$, where ${\pi }_t(a|s)$ is the rule used at time step $t$. An agent following such a policy might act differently in the same state depending on whether it's early or late in the process. This is particularly relevant in problems with a finite, known horizon. For example, a strategy for the last minute of a basketball game is very different from the strategy in the first quarter.

To solidify these ideas, let's return to the UMN paper and its robot example.

The Four Policy Types and Their Importance

By combining these two dimensions, we get four general categories of policies:

1. Stationary Deterministic: $\pi (s)$ — A fixed rule mapping each state to one action.
2. Stationary Stochastic: $\pi (a|s)$ — A fixed probability distribution over actions for each state.
3. Time-Dependent Deterministic: ${\pi }_t(s)$ — A rule mapping each state to one action, where the rule can change with time $t$.
4. Time-Dependent Stochastic: ${\pi }_t(a|s)$ — A probability distribution over actions for each state, where the distribution can change with time $t$.

A remarkable result in the theory of MDPs, which greatly simplifies the search for a solution in many common scenarios, is that for an infinite-horizon discounted MDP, an optimal policy exists and it can be found within the class of stationary deterministic policies. This means we don't have to search through the vastly more complex space of time-dependent or stochastic policies to find the best possible long-term strategy.

The following reading from a Stanford course makes this crucial point.

Conclusion

In this lesson, we have moved from the environment's dynamics to the agent's decision-making process. You have learned to define and differentiate the key types of policies that an agent can follow.

Here are the key takeaways:

• A policy $\pi$ is a mapping from states to actions (or distributions over actions), representing the agent's strategy.
• Deterministic policies specify a single action for each state, while stochastic policies specify a probability distribution over actions. Stochastic policies are particularly useful for encouraging exploration.
• Stationary policies are time-independent, applying the same rule at every time step. Time-dependent policies can change their rules over time.
• For the important class of infinite-horizon discounted MDPs, there is guaranteed to be an optimal policy that is both stationary and deterministic. This result dramatically simplifies the problem of finding the best way to act.

Now that we have defined both the environment (the MDP) and the agent's behavior (the policy), we can start to analyze what happens when they interact. In the next lesson, we will learn how to compute the probability of a specific sequence of states and actions—a trajectory—that results from an agent following a particular policy in an MDP.