Policies: Mapping States to Actions

An agent interacts with an environment by observing states and taking actions to receive rewards. But how does the agent actually decide which action to take when it finds itself in a particular state? This decision-making logic is encapsulated in what we call the agent's policy. Think of the policy as the agent's strategy or its behavioral "brain."

Formally, a policy is a mapping from states to actions. It defines the agent's way of behaving at a given time. Policies can generally be categorized into two main types: deterministic and stochastic.

Deterministic Policies

A deterministic policy directly specifies the action the agent will take for each state. If the agent is in state $s$ , the policy $\pi$ provides a single action $a$ . We can write this as:

a = \pi(s)

For every state $s$ in the set of all possible states $\mathcal{S}$ , the policy $\pi$ outputs a specific action $a$ from the set of available actions $\mathcal{A}(s)$ . Imagine a simple robot navigating a maze. A deterministic policy might be: "If you are at position X and the path ahead is clear, move forward. If blocked, turn right." For a given state (position X, path clear), the action (move forward) is fixed.

Stochastic Policies

In contrast, a stochastic policy defines a probability distribution over actions for each state. Instead of outputting a single action, it tells us the probability of taking each possible action $a$ when in state $s$ . We denote this as $\pi(a|s)$ :

\pi(a|s) = P[A_t = a | S_t = s]

Here, $P[A_t = a | S_t = s]$ represents the probability that the action $A_t$ taken at time step $t$ is $a$ , given that the state $S_t$ at time $t$ is $s$ . The sum of probabilities for all possible actions in a given state must equal 1:

\sum_{a \in \mathcal{A}(s)} \pi(a|s) = 1 \quad \text{for all } s \in \mathcal{S}

Why use stochastic policies? They are particularly useful in several scenarios:

Exploration: During learning, agents often need to try different actions to discover which ones yield the best rewards. A stochastic policy naturally incorporates this exploration by allowing the agent to occasionally choose actions that aren't currently considered the best.
Uncertainty: Sometimes the environment itself has randomness, or the agent might not be able to perfectly distinguish between states (partially observable environments). A stochastic policy can sometimes be optimal in such cases.
Avoiding Deterministic Cycles: In certain situations, a deterministic policy might get stuck in suboptimal loops, which a stochastic policy might break out of.

Here's a simple illustration contrasting the two:

A visual comparison of a deterministic policy (always choosing action A1 from state S1) versus a stochastic policy (choosing action A1 with probability 0.7 and action A2 with probability 0.3 from state S1).

The Goal: Finding the Optimal Policy

The central objective in Reinforcement Learning is typically to find an optimal policy, denoted as $\pi^*$ . An optimal policy is one that maximizes the expected cumulative reward the agent receives over the long run, starting from any state. Much of this course will focus on algorithms designed to learn or approximate $\pi^*$ .

How policies are represented depends on the complexity of the problem. For simple environments with a small number of discrete states and actions, a policy might be stored in a lookup table. However, for problems with large or continuous state spaces (like controlling a robot based on sensor readings or playing video games from pixels), we often use function approximators, such as linear functions or neural networks, to represent the policy $\pi$ . These approximators take the state representation as input and output either the action (deterministic) or the probabilities of actions (stochastic). We will cover function approximation in detail in later chapters.

In summary, the policy is the core component dictating the agent's behavior. It's the strategy the agent follows to select actions based on states, and finding the best possible strategy, the optimal policy, is the fundamental goal of most RL algorithms. Understanding the difference between deterministic and stochastic policies is essential as we move towards exploring methods for learning these policies from experience.

Was this section helpful?

References

Reinforcement Learning: An Introduction, Richard S. Sutton and Andrew G. Barto, 2018 (MIT Press) - The definitive textbook on reinforcement learning, providing a comprehensive treatment of policies, their mathematical definitions, and the distinction between deterministic and stochastic types.
CS234: Reinforcement Learning | Lecture 2: Markov Decision Processes and Policies, Emma Brunskill, 2023 Stanford University Course (Stanford University) - Lecture slides from a prominent university course, offering a structured introduction to policies, their formal definitions, and their role within Markov Decision Processes.
RL Course by David Silver - Lecture 2: Markov Decision Processes, David Silver, 2015 UCL (University College London) Course (UCL (University College London)) - A widely recognized introductory lecture series that clearly explains policies, their types, and their significance in the context of Markov Decision Processes.