An agent that always takes the action it currently rates highest will never discover a better one. Epsilon-greedy is the simplest fix: most of the time take the best known action, and with probability epsilon pick an action at random instead.
Written out as a probability for every action, that policy is:
The greedy action gets ε/n too, because "pick at random" includes the possibility of randomly picking the best one.
So you don't need a random number generator, the draw is handed to you: u is a number in [0, 1). Select the action by walking the probabilities and adding them up, stopping at the first action where the running total exceeds u.
Task: write epsilon_greedy(q_values, epsilon, u) returning the index of the selected action.
q_values[a] is the agent's current estimate for action a.0 upward.epsilon = 0 makes the policy purely greedy — the greedy action's probability is 1, so every u selects it. epsilon = 1 makes it uniform.The cumulative walk is a technique worth knowing in its own right: given a list of probabilities and one uniform draw, it samples from that distribution exactly. It's how you sample from any discrete distribution, from a softmax policy to a weighted replay buffer.