LRL-3: Policies and Value Functions - Guiding the Agent

Okay, let's continue our journey into Reinforcement Learning! We're now at Chapter 3: Policies and Value Functions - Guiding the Agent. In the previous chapter, we formalized the RL problem by defining the environment, states, actions, and rewards. Now, we need to understand how an agent actually makes decisions and how we can evaluate the "goodness" of those decisions. This is where policies and value functions come into play.

Chapter 3: Policies and Value Functions - Guiding the Agent

In this chapter, we'll explore two central concepts in Reinforcement Learning: Policies and Value Functions. Policies are the strategies that agents use to choose actions, and value functions are used to estimate how good it is to be in a particular state or to take a particular action in a state. They are the key tools that enable agents to learn and make intelligent decisions in complex environments.

1. Policies: The Agent's Strategy for Choosing Actions

A policy is essentially the agent's brain! It's what dictates how the agent behaves in the environment. It's a mapping from states to actions, telling the agent what action to take when it's in a particular state.

• Definition: A policy, often denoted as π, is a function that maps states to probabilities of selecting each possible action. It defines the agent's way of behaving at a given time.

  • If the agent is in state s, the policy π(a|s) gives the probability of taking action a in state s.

(Diagram: Policy as a mapping from State to Action Probabilities)

State (s)  ----->  Policy (π)  ----->  Action Probabilities (P(a1|s), P(a2|s), ..., P(an|s))
                                        (Agent chooses action based on these probabilities)

Types of Policies:

• Deterministic Policy: A deterministic policy always chooses the same action for a given state. It's a straightforward mapping from states to actions.

  • a = π(s) (Policy directly outputs an action a for state s)

  • Example: In a simple game, a deterministic policy might be: "If you are in state S1, always choose action A, if in state S2, always choose action B, etc."

  (Table: Example Deterministic Policy) | State | Action | |-------|--------| | S1 | Action A | | S2 | Action B | | S3 | Action A | | ... | ... |

• Stochastic Policy: A stochastic policy outputs a probability distribution over actions for each state. For a given state, there's a probability associated with each possible action.

  • π(a|s) = P(A_t = a | S_t = s) (Policy gives the probability of choosing action a in state s)

  • Example: In a more complex game, a stochastic policy might be: "If in state S1, choose action A with 70% probability, action B with 20% probability, and action C with 10% probability."

  (Table: Example Stochastic Policy) | State | Action | Probability | |-------|--------|-------------| | S1 | Action A | 0.7 | | S1 | Action B | 0.2 | | S1 | Action C | 0.1 | | S2 | Action D | 0.4 | | S2 | Action E | 0.6 | | ... | ... | ... |

Why Stochastic Policies?

You might wonder why we need stochastic policies. Why not just always choose the "best" action in each state? There are several reasons why stochastic policies are important and sometimes necessary:

• Exploration: In early stages of learning, we often want the agent to explore different actions, even if they don't seem optimal at first. Stochastic policies naturally encourage exploration by assigning non-zero probabilities to less-explored actions. This is crucial for discovering better strategies in the long run (exploration vs. exploitation trade-off, which we'll discuss in detail later).
• Dealing with Uncertainty: In stochastic environments, the best action might not always be clear-cut. A stochastic policy can allow the agent to hedge its bets and choose actions probabilistically to account for environmental uncertainty.
• Optimality in Some Environments: In some games and environments (especially in game theory scenarios with multiple agents), the optimal strategy itself might be stochastic. Think about rock-paper-scissors – a deterministic strategy is easily exploitable, but a stochastic strategy (playing each option with equal probability) is unexploitable.

How Policies Guide the Agent:

At each time step, when the agent is in a state s_t, it uses its policy π to decide which action a_t to take.

• Deterministic Policy: The agent simply looks up the action a = π(s_t) and takes that action.
• Stochastic Policy: The agent samples an action from the probability distribution π(·|s_t). For example, if π(Action A|s_t) = 0.7, π(Action B|s_t) = 0.2, π(Action C|s_t) = 0.1, the agent might randomly choose Action A with 70% chance, Action B with 20% chance, and Action C with 10% chance.

The chosen action a_t is then executed in the environment, leading to a new state s_t+1 and a reward r_t+1. This process repeats as the agent interacts with the environment, guided by its policy.

2. Value Functions: Estimating "Goodness" of States and Actions

Value functions are used to estimate how "good" it is for an agent to be in a particular state or to take a particular action in a state. "Good" here is defined in terms of expected future rewards. Value functions are critical because they help the agent to make informed decisions by predicting the long-term consequences of its choices.

We have two main types of value functions:

• State Value Function (V-function): The state value function, V^π(s), estimates how good it is to be in state s when following policy π. It's the expected return starting from state s and thereafter following policy π.

  • V^π(s) = E_π [G_t | S_t = s]

  (Equation: State Value Function Definition)

  • E_π denotes the expected value when following policy π.
  • G_t is the return (usually discounted return) starting from time step t.

  • S_t = s means we are starting in state s at time t.

  • Intuition: V^π(s) tells you, on average, how much cumulative reward you can expect to get if you start in state s and continue to act according to policy π for the rest of the episode (or indefinitely in a continuing task).

  (Analogy: Imagine states as locations on a map. V-function tells you how "valuable" each location is if you follow a certain route (policy) from that location onwards).

• Action Value Function (Q-function): The action value function, Q^π(s, a), estimates how good it is to take action a in state s and thereafter follow policy π. It's the expected return starting from state s, taking action a, and then following policy π for all subsequent steps.

  • Q^π(s, a) = E_π [G_t | S_t = s, A_t = a]

  (Equation: Action Value Function Definition)

  • E_π denotes the expected value when following policy π after the first action.
  • G_t is the return (usually discounted return) starting from time step t.

  • S_t = s, A_t = a means we are starting in state s at time t and taking action a at time t.

  • Intuition: Q^π(s, a) tells you, on average, how much cumulative reward you can expect to get if you start in state s, first take action a, and then continue to act according to policy π for the rest of the episode.

  (Analogy: Imagine you are at location 's' and have multiple roads (actions) to choose from. Q-function for each road (action 'a') tells you how "valuable" it is to take that road and then follow a certain route (policy) from there onwards).

Relationship Between V-function and Q-function:

The V-function and Q-function are closely related. For a given policy π, we can express the state value function in terms of the action value function:

• V^π(s) = ∑_a∈A π(a|s) Q^π(s, a)

  (Equation: V-function in terms of Q-function)

  • This equation says that the value of a state s under policy π is the average of the Q-values of all possible actions in state s, weighted by the probabilities of taking those actions according to policy π. Essentially, it's the expected Q-value in state s when following policy π.

Difference between V-function and Q-function:

• V-function (V^π(s)): Value of being in a state s, assuming you will follow policy π afterwards. State-centric.
• Q-function (Q^π(s, a)): Value of taking action a in state s, and then following policy π afterwards. State-action pair centric.

Why are Value Functions Important?

Value functions are crucial for Reinforcement Learning because they:

• Guide Policy Improvement: Value functions provide a way to evaluate policies and to improve them. If we know the value function for a policy, we can determine if the policy is good or bad in different states and identify actions that can lead to higher rewards.
• Enable Decision Making: In many RL algorithms, agents use value functions to choose actions. For example, in a state s, an agent might choose the action a that maximizes Q^π(s, a) (or an estimate of it) if it wants to act greedily with respect to the value function.
• Form the Basis of Learning Algorithms: Many RL algorithms are based on estimating and updating value functions. Algorithms like Q-Learning, SARSA, and others directly learn approximations of the Q-function or V-function.

Optimal Policy and Optimal Value Functions:

In Reinforcement Learning, our ultimate goal is often to find an optimal policy, denoted as π

*. An optimal policy is a policy that achieves the maximum possible expected return over all possible policies. There can be multiple optimal policies, but they will all achieve the same optimal value functions.

• Optimal State Value Function (V^*(s)): The maximum state value function over all policies:

  • V

(s) = max_π V^π(s)*

(Equation: Optimal State Value Function Definition)

• V

(s) gives the best possible value that can be achieved starting from state s*.

Optimal Action Value Function (Q^*(s, a)): The maximum action value function over all policies:

• Q

(s, a) = max_π Q^π(s, a)*

(Equation: Optimal Action Value Function Definition)

• Q

(s, a) gives the maximum possible value that can be achieved by taking action a in state s* and then following an optimal policy thereafter.

Relationship between Optimal V and Q

:

Similar to the relationship between V^π and Q^π, we have:

• V

(s) = max_a∈A Q(s, a)

(Equation: Optimal V-function in terms of Optimal Q-function)

• The optimal value of a state s is simply the maximum of the optimal Q-values for all actions available in state s. To achieve the optimal value in state s, you should choose the action that leads to the highest optimal Q-value.

Policies and Value Functions in Action (Summary):

• Policy (π): Answers the question: "What action should I take in this state?" (Strategy for action selection).
• Value Function (V^π or Q^π): Answers the question: "How good is it to be in this state (or to take this action in this state)?" (Prediction of future rewards).
• Optimal Policy (π_*): The best possible strategy to maximize cumulative reward.
• Optimal Value Functions (V, Q

): The best possible values achievable in each state or state-action pair.

In the next chapter, we'll delve into Markov Decision Processes (MDPs), which provide the mathematical framework for formally defining RL problems. We'll also introduce the Bellman Equations, which are fundamental equations that relate value functions between states and time steps, and which are at the heart of many RL algorithms. We will see how Bellman equations help us to calculate and understand value functions and ultimately find optimal policies.