Must every starting pair be equally likely?

No; positive probability is the essential coverage condition in the usual finite setting.

Is a random state enough?

No; initial actions also need coverage.

AI Glossary / Reinforcement learning and robotics / Advanced

Exploring starts

Definition

Exploring starts is an assumption or sampling arrangement in episodic reinforcement learning under which every relevant state-action pair has a nonzero chance of being selected as an episode's initial pair. It provides a way to obtain experience with actions that a subsequent policy might never choose. The idea is especially associated with Monte Carlo estimation and control.

What it means

Learning the value of an action requires evidence about what follows taking it. A deterministic policy may repeatedly choose one action and leave its alternatives unobserved. Exploring starts addresses this coverage problem by randomizing both the initial state and the first action.
It is stronger than merely starting in a random state. If the first action is always chosen by a deterministic policy, other actions at that state can still receive no starting visits.

How it works

Choose an initial pair from a distribution that assigns positive probability to each relevant state-action pair. Execute that action, then follow the specified policy for the rest of the episode. Monte Carlo prediction uses the resulting returns to estimate action values. In a control procedure, those estimates can also support policy improvement.
With independent draws from a fixed full-support distribution over a finite set, every pair is selected infinitely often with probability one as the number of episodes grows without bound. This is an asymptotic coverage statement. It does not imply complete coverage after a particular finite number of episodes or guarantee accurate estimates after one visit.
The assumption can be convenient in a controllable simulator and unrealistic in a physical process. When it is unavailable, learning methods need another exploration arrangement appropriate to the environment.

Three practical examples

Small simulated games: training episodes begin from different valid configurations and first moves to obtain returns for alternatives that a greedy policy would overlook.
Tabular learning demonstrations: a teacher deliberately samples initial state-action pairs to separate exploration coverage from the details of value estimation.
Simulator testing: researchers inspect the start distribution and recorded pair counts before claiming that every relevant action has had an opportunity to be evaluated.

Think of it this way

Imagine reviewing several routes by being allowed to start at any listed junction and take any listed first turn. After that first turn, you follow a fixed travel rule.

Worked example

Consider an original episodic simulator with two nonterminal states, A and B. Each has actions left and right. There are therefore four possible initial pairs: A-left, A-right, B-left and B-right. Suppose each episode independently selects one of the four with probability 1/4, and then follows a fixed policy after its initial action.
For any specified pair, the probability of not selecting it on one episode is 3/4. After eight independent episodes, the probability it has never been selected as the start is (3/4) to the eighth power, approximately 0.1001. Thus even a full-support start distribution leaves about a ten percent chance of missing that particular pair in eight starts.
Complete coverage is a different event. The probability all four pairs have appeared among eight starts is 1 - 4(3/4)^8 + 6(1/2)^8 - 4(1/4)^8, approximately 0.6229. Eight starts therefore provide only about a 62.3 percent chance of complete initial-pair coverage in this example.
The expected number of distinct initial pairs observed is 4[1 - (3/4)^8], approximately 3.5995. This expected count is neither a guarantee of four observed pairs nor the probability of complete coverage. Later visits within an episode could add experience, but these calculations deliberately count only initial selections.
Now change the procedure so that A and B are each selected with probability one-half, but the first action is always left. Both right-action pairs then have zero probability of being selected initially. The procedure randomizes states but does not satisfy exploring starts over the four pairs.
Finally, suppose a fixed-policy evaluation produces returns 2, 4 and 3 from three episodes beginning at A-right. Their sample mean is 3. This calculation estimates the value of taking right at A and then following that policy. Three observations do not establish the exact expected return; more evidence may change the estimate. The start distribution supplies opportunities to collect returns, while the return estimator uses those observations to learn values.
These are exact sampling calculations with rounded decimal displays and an illustrative return sequence. They do not describe a measured training run or prove convergence of a changing-policy control algorithm.

Illustrative case study

Fictional company Maple Learning develops a small simulated decision task. Its team defines which configurations are valid, checks that each permitted initial pair can be generated and logs the pair selected for every episode.
The analysts discover that a supposedly random start procedure randomizes states but retains a default first action. They correct the initialization logic and verify pair counts across repeated trials. They also distinguish the training start distribution from the starting conditions used for final evaluation. This fictional workflow reports no performance improvement or deployment outcome.

Common misconceptions and mistakes

Exploring starts does not require a uniform distribution, although uniform sampling is convenient in small examples. Every relevant pair needs positive probability under the stated arrangement. Positive probability alone should also not be used casually to justify repeated coverage under an arbitrary time-varying schedule; the sampling assumptions matter.
Another mistake is treating one visit per pair as sufficient for accurate Monte Carlo values. Stochastic returns require estimation. Random starts also do not guarantee that episodes terminate, which the episodic return procedure needs to address. Finally, coverage assumptions and convergence claims about a full control algorithm are separate issues.

Business use

Exploring starts helps teams recognize the difference between a learning algorithm's assumptions and the experiences their system can actually generate. Simulator-based studies should document valid resets, first-action selection and coverage counts. Evaluation should use the intended operating start distribution rather than silently inheriting an artificial training distribution.

Check your understanding

Why did the always-left procedure fail?

Answer: Both right-action pairs had zero starting probability.

Why was complete coverage less likely than observing a particular pair?

Answer: It required all four pairs to appear.

What did the mean return of 3 estimate?

Answer: Taking A-right first and then following the fixed policy.

Related terms

Policy evaluation
Exploration
Monte Carlo control
State-action coverage
Episode initialization
First-visit Monte Carlo
Epsilon-soft policy

Learn next

Replace the uniform start distribution with unequal probabilities and calculate which pairs are most likely to remain unobserved.

Sources

Sutton and Barto, Reinforcement Learning: An Introduction, second edition, Sections 5.2–5.4: https://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf . The four-pair sampling calculations and company scenario are original illustrations.

Previous: Explore-then-commit algorithm Next: Exponential dispersion family