Kursinnhold

Introduction to Reinforcement Learning

1. RL Core Theory

What is RL?RL vs Other Learning Paradigms Markov Decision Process Episodes and Returns Model, Policy, and Values Exploration vs Exploitation Gymnasium Basics Challenge: Setting Up an Environment

2. Multi-Armed Bandit Problem

Problem Introduction Action Values Epsilon-Greedy Algorithm Upper Confidence Bound Algorithm Gradient Bandits Algorithm Challenge: Multi-Armed Bandits

3. Dynamic Programming

What is Dynamic Programming?Bellman Equations Optimality Conditions Policy Evaluation Policy Improvement Generalized Policy Iteration Policy Iteration Value Iteration Challenge: Dynamic Programming

4. Monte Carlo Methods

What are Monte Carlo Methods?Value Function Estimation Monte Carlo Control Exploration Approaches On-Policy Monte Carlo Control Off-Policy Monte Carlo Control Incremental Implementations Challenge: Monte Carlo Methods

5. Temporal Difference Learning

What is Temporal Difference Learning?TD(0): Value Function Estimation SARSA: On-Policy TD Learning Q-Learning: Off-Policy TD Learning Generalization of TD Learning Challenge: Temporal Difference Learning

On-Policy Monte Carlo Control

The idea behind on-policy methods is intuitive: an agent learns by following its current policy and improves that policy based on the outcomes it experiences. To discover better actions and avoid getting stuck in suboptimal behavior, the agent incorporates a degree of randomness — occasionally trying alternative actions to encourage exploration.

Analogy

Imagine you're at an ice cream shop and there are three flavors available: chocolate, vanilla, and strawberry. You love chocolate, so that's what you usually pick. But one day, out of curiosity, you decide to try strawberry instead. Turns out, the strawberry ice cream at this shop is incredibly tasty, and you decide to pick it whenever you visit this shop.

Trying new flavor wasn't necessarily the most logical choice based on past experience, but it gave you a chance to discover something new. And this kind of exploration lies at the core of on-policy methods.

Stochastic Policies

Formally, adopting this idea means replacing the deterministic (hard) policies used in dynamic programming with stochastic (soft) policies, denoted as $\pi(a | s)$ , where:

\pi(a | s) > 0 \qquad \forall s \in S, a \in A(s)

In other words, every action in every state has a non-zero probability of being selected. This ensures that all parts of the environment can eventually be explored, which is essential when learning from experience.

$\Large\varepsilon$ -greedy Policies

To incorporate exploration into the policy, let's borrow the concept of $\varepsilon$ -greedy exploration from the multi-armed bandit problem. This allows us to define a stochastic policy that balances exploiting the best-known action with exploring alternatives:

\pi(a | s) \gets \begin{dcases} 1 - \varepsilon + \frac{\varepsilon}{|A(s)|} & \text{if } a = \argmax_{a'} q_\pi(s, a') \\ \frac{\varepsilon}{|A(s)|} & \text{otherwise} \end{dcases}

This policy behaves greedily most of the time — choosing the action with the highest estimated value — but with probability $\varepsilon$ , it selects a random action, ensuring that all actions have a non-zero chance of being taken (even the greedy one again, via uniform sampling).

At first glance, this approach seems problematic: since the policy never becomes purely greedy, it will never converge to the exact optimal policy. As such, it doesn't strictly satisfy the conditions for GPI if we expect the exact optimality in the limit.

However, GPI doesn't require the policy to become optimal immediately — it only requires that each policy improves (or stays the same) compared to the last, progressively moving toward optimality. The $\varepsilon$ -greedy policy satisfies this condition: it improves the policy on average, and ensures ongoing exploration to support better estimates.

To address the issue of convergence to the truly optimal policy, we can gradually reduce $\varepsilon$ over time. This strategy lets the policy become increasingly greedy as learning progresses. In the early stages, exploration helps gather diverse experience, while in later stages, the agent exploits its improved knowledge. With a properly decaying $\varepsilon$ , the method does converge to an optimal policy in the limit.

Pseudocode

Alt var klart?

Takk for tilbakemeldingene dine!

Seksjon 4. Kapittel 5

Spør AI

Spør om hva du vil, eller prøv ett av de foreslåtte spørsmålene for å starte chatten vår

Kursinnhold

Introduction to Reinforcement Learning

1. RL Core Theory

What is RL?RL vs Other Learning Paradigms Markov Decision Process Episodes and Returns Model, Policy, and Values Exploration vs Exploitation Gymnasium Basics Challenge: Setting Up an Environment

2. Multi-Armed Bandit Problem

Problem Introduction Action Values Epsilon-Greedy Algorithm Upper Confidence Bound Algorithm Gradient Bandits Algorithm Challenge: Multi-Armed Bandits

3. Dynamic Programming

What is Dynamic Programming?Bellman Equations Optimality Conditions Policy Evaluation Policy Improvement Generalized Policy Iteration Policy Iteration Value Iteration Challenge: Dynamic Programming

4. Monte Carlo Methods

5. Temporal Difference Learning

On-Policy Monte Carlo Control

Analogy

Stochastic Policies

Formally, adopting this idea means replacing the deterministic (hard) policies used in dynamic programming with stochastic (soft) policies, denoted as $\pi(a | s)$ , where:

\pi(a | s) > 0 \qquad \forall s \in S, a \in A(s)

$\Large\varepsilon$ -greedy Policies

\pi(a | s) \gets \begin{dcases} 1 - \varepsilon + \frac{\varepsilon}{|A(s)|} & \text{if } a = \argmax_{a'} q_\pi(s, a') \\ \frac{\varepsilon}{|A(s)|} & \text{otherwise} \end{dcases}

Pseudocode

Alt var klart?

Takk for tilbakemeldingene dine!

Seksjon 4. Kapittel 5

Introduction to Reinforcement Learning

On-Policy Monte Carlo Control

Analogy

Stochastic Policies

ε\Large\varepsilonε-greedy Policies

Pseudocode

Introduction to Reinforcement Learning

On-Policy Monte Carlo Control

Analogy

Stochastic Policies

ε\Large\varepsilonε-greedy Policies

Pseudocode

$\Large\varepsilon$ -greedy Policies

$\Large\varepsilon$ -greedy Policies