📘

Epsilon-Greedy Action Distribution

EasyReinforcement Learning 📚 RL 1: Foundations

Problem Statement

Given action-value estimates for one state, compute the probability distribution that an epsilon-greedy policy induces over the actions. Do not sample — return the exact probabilities.

Background

Epsilon-greedy is the standard answer to the exploration/exploitation dilemma: with probability 1 - epsilon take the action that currently looks best, and with probability epsilon pick uniformly at random among all actions (the greedy action included). So for a state with n actions:

$\pi(a \mid s) = \begin{cases} 1-\varepsilon + \dfrac{\varepsilon}{n} & a = \arg\max_{a'} Q(s,a') \$6pt] \dfrac{\varepsilon}{n} & \text{otherwise} \end{cases}$

The detail that trips people up is ties. If k actions share the maximum value, the greedy mass 1 - epsilon is split evenly among all k of them, so each tied action gets (1 - epsilon)/k + epsilon/n. Handing the whole greedy mass to argmax (which returns only the first index) silently biases the policy — and later, when you write Expected SARSA, that same distribution appears inside the update target, so the bug becomes a wrong learning signal rather than just an odd action choice.

Your Task

Implement:

def epsilon_greedy_probs(q, epsilon):
    ...

q — a list of floats, the action values Q(s, a) for the current state.
epsilon — a float in [0.0, 1.0].

Return a list of floats of the same length as q, summing to 1.

Input / Output Format

Input is a list of floats and a float. Output is a list of floats; the grader rounds each entry to 4 decimals.

Sample

print([round(p, 4) for p in epsilon_greedy_probs([1.0, 5.0, 3.0], 0.3)])

Output:

[0.1, 0.8, 0.1]

Every action gets 0.3/3 = 0.1, and the greedy action (index 1) additionally gets 1 - 0.3 = 0.7.

Example:

Input:

epsilon_greedy_probs([1.0, 5.0, 3.0], 0.3)

Output:

[0.1, 0.8, 0.1]

Reasoning:

Uniform exploration gives every action epsilon/n = 0.1. Action 1 is the unique greedy action, so it additionally receives 1 - epsilon = 0.7, giving 0.8.

Constraints:

1 <= len(q) <= 100
0.0 <= epsilon <= 1.0
Ties for the maximum value must split the greedy probability 1 - epsilon evenly among all tied actions.
The returned probabilities must sum to 1 (up to floating point error).

More from RL 1: Foundations

GAE Over a Full TrajectoryHard PPO Clipped Objective (Single Sample)Medium TD Residuals for GAEMedium Return Standardization BaselineMedium REINFORCE Loss TermMedium

1. Background Knowledge

In Reinforcement Learning (RL), an agent must balance exploitation (choosing the best known action) and exploration (trying other actions to gather more information). The epsilon-greedy policy is a standard strategy for this trade-off. With probability $1 - \epsilon$ , the agent selects the action with the highest estimated value (the greedy action). With probability $\epsilon$ , it selects an action uniformly at random from all available actions. This ensures that every action has a non-zero probability of being selected, which is crucial for convergence in many RL algorithms.

The core concept here is translating a deterministic greedy choice into a stochastic probability distribution. While sampling an action is common, many algorithms (like Expected SARSA) require the exact probability distribution $\pi(a \mid s)$ to compute expected values. The distribution is defined such that the "greedy mass" ( $1 - \epsilon$ ) is assigned to the optimal action(s), and the "exploration mass" ( $\epsilon$ ) is spread evenly across all actions.

A critical nuance is handling ties in the action-value estimates. If multiple actions share the maximum $Q$ -value, the greedy mass must be split evenly among them. Failing to do so biases the policy, leading to incorrect expected value calculations in downstream algorithms. Understanding how to identify these ties and distribute probability mass correctly is the key to solving this problem.

2. Algorithm Approach

The approach involves two main phases: identifying the optimal actions and calculating the probabilities.

Find the Maximum Value: Determine the highest $Q$ -value in the input list.
Count Ties: Identify how many actions share this maximum value. Let this count be $k$ .
Calculate Base Probability: Every action receives a base probability from the exploration component: $\frac{\epsilon}{n}$ , where $n$ is the total number of actions.
Add Greedy Probability: For each action that is tied for the maximum, add the shared greedy mass: $\frac{1 - \epsilon}{k}$ .

This results in a piecewise function for the probability of action $a$ :

\pi(a \mid s) = \begin{cases} \frac{1 - \epsilon}{k} + \frac{\epsilon}{n} & \text{if } Q(s, a) = \max_{a'} Q(s, a') \\ \frac{\epsilon}{n} & \text{otherwise} \end{cases}

3. Step-by-Step Strategy

👑

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

🔒

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.