Policies and Value Functions (Vπ, Qπ)

We've established the Markov Decision Process (MDP) as our framework, defining the environment's states ($S$), the agent's possible actions ($A$), the rules of state transitions ($P$), immediate rewards ($R$), and the discount factor ($\gamma$). Now, how does an agent actually decide what to do in this environment? And how do we measure how good those decisions are in the long run? This is where policies and value functions come into play.

The Agent's Strategy: Policies

A policy, denoted by $\pi$, is the agent's strategy or behavior. It dictates which action the agent will choose when it finds itself in a particular state. Think of it as the agent's controller or decision-making function.

Policies can be categorized into two main types:

1. Deterministic Policies: For any given state $s$, a deterministic policy always specifies a single action $a$. We write this as:

   $$\pi(s) = a$$

   If the agent is in state $s$, it will take action $a$.

2. Stochastic Policies: In contrast, a stochastic policy specifies a probability distribution over actions for each state. We write this as:

   $$\pi(a|s) = P(A_t = a | S_t = s)$$

   This gives the probability that the agent selects action $a$ when in state $s$. The sum of probabilities over all possible actions in a state must equal 1: $\sum_{a \in A(s)} \pi(a|s) = 1$.

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

• Exploration: When learning, an agent might need to try different actions (even seemingly suboptimal ones) to discover better strategies. A stochastic policy allows for this exploration naturally.
• Uncertainty: Sometimes the optimal strategy itself involves randomization (e.g., in certain game theory scenarios).
• Partial Observability: In more advanced settings (Partially Observable MDPs, or POMDPs), the agent might not know the exact state, and a stochastic policy can represent the uncertainty in the best action.

The policy is fundamental because it defines how the agent interacts with the MDP. Given a policy $\pi$, the agent's sequence of states, actions, and rewards becomes a stochastic process determined by both the environment's dynamics ($P$) and the agent's choices ($\pi$).

Evaluating Policies: Value Functions

Knowing the agent's strategy ($\pi$) is one thing, but how do we know if it's a good strategy? We need a way to quantify the long-term value of following a policy. This is the role of value functions. Value functions estimate the expected cumulative future discounted reward, also known as the expected return, under a specific policy.

There are two primary types of value functions:

State-Value Function ($V^\pi$)

The state-value function, $V^\pi(s)$, measures the expected return if the agent starts in state $s$ and follows policy $\pi$ thereafter. It tells us "how good" it is to be in state $s$ under policy $\pi$.

Formally, $V^\pi(s)$ is defined as:

$$V^\pi(s) = \mathbb{E}_\pi [G_t | S_t = s] = \mathbb{E}_\pi \left[ \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} | S_t = s \right]$$

Let's break this down:

• $\mathbb{E}_\pi[\cdot]$ denotes the expected value, assuming the agent follows policy $\pi$.
• $G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$ is the total discounted return starting from time step $t$.
• $S_t = s$ is the condition that we are starting from state $s$ at time $t$.

So, $V^\pi(s)$ averages the total discounted rewards over all possible trajectories that could start from state $s$ when following policy $\pi$. A higher $V^\pi(s)$ indicates that state $s$ is more desirable under policy $\pi$.

Action-Value Function ($Q^\pi$)

The action-value function, $Q^\pi(s, a)$, measures the expected return if the agent starts in state $s$, takes a specific action $a$ (just for the first step), and then follows policy $\pi$ for all subsequent decisions. It tells us "how good" it is to take action $a$ from state $s$, and then continue with policy $\pi$.

Formally, $Q^\pi(s, a)$ is defined as:

$$Q^\pi(s, a) = \mathbb{E}_\pi [G_t | S_t = s, A_t = a] = \mathbb{E}_\pi \left[ \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} | S_t = s, A_t = a \right]$$

The main difference from $V^\pi(s)$ is the additional condition $A_t = a$. We are now evaluating the consequence of taking a specific first action $a$ before letting the policy $\pi$ take over.

The action-value function $Q^\pi(s, a)$ is often more directly useful for decision-making than $V^\pi(s)$. If the agent knows $Q^\pi(s, a)$ for all actions $a$ available in state $s$, it can simply choose the action with the highest Q-value to act greedily with respect to the current policy's valuation.

The Link Between Vπ and Qπ

The state-value and action-value functions are closely related.

The value of a state $s$ under a stochastic policy $\pi$ is the expected value of the Q-values for all actions possible in $s$, weighted by the policy's probability of choosing each action:

$$V^\pi(s) = \sum_{a \in A(s)} \pi(a|s) Q^\pi(s, a)$$

This makes intuitive sense: the value of being in a state is the average value of taking each possible action from that state, according to the policy's action probabilities.

Conversely, the value of taking action $a$ in state $s$ and then following policy $\pi$ depends on the immediate reward received and the discounted value of the next state $s'$ reached. We need to consider all possible next states $s'$ and rewards $r$ determined by the environment's transition dynamics $p(s', r | s, a)$.

$$Q^\pi(s, a) = \sum_{s', r} p(s', r | s, a) \left[ r + \gamma V^\pi(s') \right]$$

This equation states that the value of the state-action pair $(s, a)$ is the expected immediate reward ($r$) plus the expected discounted value of the next state ($\gamma V^\pi(s')$), averaged over all possible outcomes $(s', r)$ according to the environment dynamics $p(s', r | s, a)$.

The following diagram helps visualize the relationship between a policy and the value functions:

A simple MDP showing states (s1, s2, s3), actions (up, right, left), transition probabilities (p), rewards (R), and a policy ($\pi$). $V^\pi(s)$ estimates the long-term value starting from state $s$ under policy $\pi$. $Q^\pi(s, a)$ estimates the value of taking action $a$ first, then following $\pi$. For example, $Q^\pi(s1, \text{right})$ considers the immediate reward (+1) and the discounted value of the resulting state ($\gamma V^\pi(s2)$).

These relationships between $V^\pi$ and $Q^\pi$ are recursive and form the core of the Bellman equations, which we will explore in detail in the next chapter. They provide a way to break down the complex long-term value calculation into manageable, iterative steps.

Understanding policies and value functions is fundamental. Policies define what the agent does, and value functions evaluate how good those actions are in the context of achieving the overall goal: maximizing the expected cumulative reward. The ultimate objective in many RL problems is not just to evaluate a given policy, but to find an optimal policy ($\pi^*$), one that achieves the highest possible expected return from any starting state. This optimal policy will have corresponding optimal state-value ($V^*$) and action-value ($Q^*$) functions. Learning these optimal functions and policies is the central theme of the algorithms we will cover later in this course.