Does infinite exploration mean every action has equal probability?

No. Probabilities can differ and decrease while still generating the required repeated visits.

Is GLIE required for Q-learning value convergence in exactly the same way as for SARSA?

No. Off-policy Q-learning and on-policy SARSA have different relationships between behavior and updates; their theorem assumptions must be stated separately.

Can a finite log prove GLIE?

No. It can show observed coverage and verify that the implemented schedule matches a theoretically analyzed design.

AI Glossary / Graphs and symbolic AI / Advanced

GLIE

Definition

GLIE stands for greedy in the limit with infinite exploration. It describes a reinforcement-learning exploration policy that keeps obtaining repeated experience of actions while increasingly choosing actions that are greedy with respect to its current value estimates.

What it means

The two requirements pull in different directions. Exploration must persist enough to avoid permanently neglecting an action because of an unlucky early estimate. At the same time, the probability of selecting a nongreedy action must approach zero as learning continues.

These requirements are compatible over an unlimited sequence of decisions: an event can become rarer while still occurring infinitely often. Infinite exploration does not mean maintaining a fixed exploration percentage forever.

GLIE is a property used in convergence analysis, not a complete learning algorithm. It does not specify the value-update rule, learning rates or environment assumptions. A finite training run cannot literally demonstrate infinitely many visits; it can implement a policy whose theoretical behavior has the required property under stated conditions.

How it works

Maintain action-value estimates and choose actions using a suitable exploration policy. In an epsilon-greedy policy, the agent usually selects an estimated best action and, with probability epsilon, selects randomly from the available actions.

To become greedy in the limit, epsilon can decrease toward zero. However, decreasing it too quickly can leave some actions insufficiently explored. A policy based on a state's visit count can preserve exploration opportunities in that state more appropriately than a global time counter alone.

The coverage conditions also matter. Classical convergence statements require sufficient visits to relevant state-action pairs and suitable update assumptions. GLIE does not make unreachable states reachable, nor does it automatically transfer a tabular convergence proof to a neural-network approximation or a changing environment.

Three practical examples

A small tabular control experiment uses a visit-based exploration schedule and records how often every state-action pair is sampled.
A teaching bandit simulator compares constant exploration, slowly decreasing exploration and exploration that shuts off too quickly.
A research review checks whether a claimed SARSA convergence result includes both exploration conditions and the required learning-rate assumptions.

Think of it this way

Think of returning to inspect alternative routes less often as you gain experience, while never declaring an alternative permanently off limits merely because of an early disappointing visit.

The analogy helps explain persistent but diminishing exploration. Real travel has finite time and practical constraints; GLIE is an asymptotic mathematical property, not an instruction to keep trying every physical route indefinitely.

Worked example

A probability that shrinks without eliminating exploration

Consider one repeatedly visited state with two actions. Assume one action is currently uniquely greedy. On the nth visit, set epsilon to 1/n and, during the exploration branch, choose uniformly between both actions using fresh random draws.

The nongreedy action is selected with probability epsilon/2 = 1/(2n). At visit 10 that probability is 0.05; at visit 100 it is 0.005; at visit 1,000 it is 0.0005. The greedy action's probability is 1 − 1/(2n), because it can also be chosen during random exploration.

Although 1/(2n) tends to zero, its sum over all visits diverges. The exploration mechanism therefore retains infinitely many opportunities to sample each action, with the usual independent randomization in this single-state example.

Contrast epsilon = 1/n². It also tends to zero, but its sum is finite, so it does not provide the same infinite-exploration guarantee. Merely stating that epsilon decays is insufficient. Extending this example to a multi-state environment requires checking state visitation, not simply copying the formula with global time.

Illustrative case study

The fictional Birch Learning team trains a small simulated controller. Its first exploration schedule decreases with the total number of interactions, even for states that have rarely been reached.

The team notices that a late-discovered state receives almost no exploration. Reviewers distinguish the global clock from that state's visit count and examine both action coverage and the assumptions of their learning method. They retain coverage reports alongside reward curves.

Birch also tests the final greedy policy separately from the exploratory training behavior. The case illustrates why an attractive learning curve does not by itself establish the hypotheses of a convergence theorem. It does not claim that a revised schedule guarantees good performance within a particular finite budget.

Common misconceptions and mistakes

Any decreasing epsilon schedule is GLIE. Exploration can decay too quickly to maintain the required coverage.
Constant positive epsilon is greedy in the limit. It normally retains a nonzero probability of nongreedy choices.
GLIE alone proves any learning system converges. Update rules, representation and environment assumptions remain essential.
Greedy means selecting the truly best action immediately. Here it means selecting an action with the highest current estimated value.

Business use

GLIE is useful for understanding the difference between eventual learning guarantees and finite-budget performance. A team can use it to question an exploration design, especially when rare states or early estimation errors matter.

For an applied project, report the actual schedule, visit counts, training budget and evaluation policy. Do not present an asymptotic theorem as a completion date or a bound on early mistakes. In nonstationary settings, continued exploration may be deliberately retained to track change, even though a fixed positive exploration rate is not greedy in the limit. The appropriate objective should determine that choice.

Check your understanding

Why is epsilon = 1/n² insufficient as a general GLIE justification in the worked setting?

Answer: Its exploration probabilities have a finite total sum. Going to zero establishes the greedy-limit direction but does not establish infinite exploration.

Related terms

Epsilon greedy policy
SARSA
Q-learning
Learning rate
Convergence
exploration and exploitation
action-value function
state visitation

Learn next

For four actions and one uniquely greedy action, derive each nongreedy action's probability under epsilon-greedy sampling. Then compare schedules based on global time and local visit count for a state first encountered late in training.

Sources

Singh, Jaakkola, Littman and Szepesvari define GLIE and prove qualified tabular on-policy convergence results: https://sites.ualberta.ca/~szepesva/papers/singh98convergence.pdf

Barto's author teaching notes discuss exploration in reinforcement learning: https://people.cs.umass.edu/~barto/courses/CS383-Fall11/383-Fall11-Lec23.pdf

The single-state probability exercise and Birch Learning case are original illustrations. Infinite-horizon properties are not presented as finite-run performance guarantees.

Previous: Glejser test Next: Glitch token