📘

Normalize a Transition Row

EasyReinforcement Learning 📚 RL 1: Foundations

Problem Statement

A transition function P(s' | s, a) must be a valid probability distribution over next states. Given a list of non-negative unnormalized counts, return the normalized distribution. If the counts sum to 0, return a uniform distribution.

Implement normalize_transition(counts).

Example:

Input:

normalize_transition([1, 3])

Output:

[0.25, 0.75]

Reasoning:

Compute the sum of the input counts to determine the normalization factor: $total = 1 + 3 = 4$ .
Check if the total is zero to decide between a uniform distribution and standard normalization; since $4 \neq 0$ , proceed with dividing each count by the total.
Normalize the first count by dividing it by the total: $1 / 4 = 0.25$ .
Normalize the second count by dividing it by the total: $3 / 4 = 0.75$ .
The final output is [0.25, 0.75]

Constraints:

1 <= len(counts) <= 1000, all counts >= 0.
Output sums to 1.
All-zero input returns uniform 1/n each.

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 a Markov Decision Process (MDP), the environment dynamics are fully described by a transition function $P(s' \mid s, a)$ , which gives the probability of reaching next state $s'$ given current state $s$ and action $a$ . For any fixed $(s, a)$ pair, the values $P(s' \mid s, a)$ across all possible next states $s'$ must form a valid probability distribution: every entry is non-negative, and the entries sum to exactly 1. This normalization constraint is fundamental because it ensures that the agent's belief about the next state is a proper categorical distribution.

In practice, transition probabilities are often estimated from data as raw counts or frequencies. For example, if an agent took action $a$ in state $s$ one hundred times and transitioned to state $s_1$ forty times, the raw count for $s_1$ is 40. To convert these counts into probabilities, you divide each count by the total sum of all counts. This is the standard maximum likelihood estimate of a categorical distribution.

A special edge case arises when the total count is zero, meaning the transition was never observed. In that situation, dividing by zero is undefined. The conventional fallback is to return a uniform distribution over all next states, which encodes maximum uncertainty (maximum entropy) and avoids biasing the policy toward any particular state.

2. Algorithm Approach

The core operation is L1 normalization of a non-negative vector. The algorithm follows a simple two-pass pattern:

Compute the sum of all elements in the input list.
If the sum is zero, return a uniform distribution (each element equals $1/n$ where $n$ is the length of the list).
Otherwise, divide each element by the sum.

This is a direct application of the definition of a probability distribution derived from counts. No iterative or recursive structure is needed; a single linear scan suffices.

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.