Q-learning
Algorithms AIMech:QLearning DRAFT
A model-free reinforcement-learning method that incrementally updates action-value estimates toward an observed reward plus the discounted maximum estimated value of the next state’s actions.
Identity Notes & Concept Scope
The record captures one-step Q-learning through the original finite tabular formulation and its explicitly conditional convergence statement. It is distinct from a learned Q table, a generic reinforcement-learning task, the complete deep Q-network procedure with replay and target networks, and Ant-Q’s edge-based constructive search. Maximizing the next-state estimate distinguishes its target from simply evaluating the next action chosen by the behavior policy. No normalized identity match was found across all 442 pinned AIO labels/scoped synonyms and 295 preceding native IDs/names/aliases. Full-checkout fixed-string searches included ignored and hidden files in worktree and main, returning 57 and 57 lines respectively. Text hits were prior candidate leads and neighboring-method mentions in maintained records, saved reviews and discovery reports; they did not identify an existing record for these candidates. Six exact AIO CLASS nodes with scoped synonyms/comments and outgoing edges and six native neighboring mechanisms were inspected. Absence is bounded to this snapshot and semantic neighborhood.
Claims & Grounded Evidence
1 Claim
Mechanism
#method
Maintain a finite table Q(x,a). On a sampled transition with current state x, action a, reward r and next state y, change only that entry to (1−alpha)*Q(x,a)+alpha*(r+gamma*max_b Q(y,b)), using the pre-update table for the target; leave other entries unchanged. Repeated samples supply rewards and next states without requiring an explicit estimated transition model. The maximum defines a greedy target even when behavior chooses an exploratory action; the update itself does not prescribe an exploration policy. In the paper’s discounted finite Markov setting, 0<gamma<1. Its theorem reports almost-sure convergence to optimal action values under bounded rewards, table representation, infinitely many samples of each state-action pair, and per-pair learning-rate sequences whose sum diverges while their squared sum converges, with 0<=alpha<1. This is an asymptotic, assumption-dependent statement, not a finite-sample stopping certificate.
⚠️ Curated Limitations & Negative Results
- The state representation and sampling process must support the controlled Markov assumptions. Partial observability, changing dynamics, biased sample reuse or unvisited actions prevent importing the stated theorem unchanged. Infinite visits alone are insufficient without the learning-rate conditions.
- A fixed positive learning rate violates the finite squared-sum condition; neural or other function approximation is not covered by the tabular theorem. The record does not claim all such variants fail, only that this particular guarantee does not establish their convergence.
- The action-replay process in the proof is an analytical construction, not a required replay-buffer implementation. Section 4 separately discusses reusing empirical samples and warns that repeated reuse can favor the observed empirical environment. DQN’s additional machinery is not silently included.
- The paper sketches undiscounted absorbing and multiple-entry extensions but does not establish every multi-step variant under the displayed theorem. Discounting, available actions, ties, terminal representation and initialization need a declared application. The proof’s full appendix was not independently audited; no benchmark claim is curated.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:ReinforcementLearning
Reinforcement Learning
|
related_match | The source explicitly defines Q-learning as a model-free reinforcement-learning algorithm. The pinned AIO target is a learning task; the relation records this direct connection without equating the algorithm to the task or asserting an algorithm-class hierarchy. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
Christopher J. C. H. Watkins, Peter Dayan
|
primary paper
full_text
|
ID: doi:10.1007/BF00992698
sha256:3f1938a60019…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T13:47:28Z
Updated: 2026-10-11T13:47:28Z
Source File:
data/curated/QLearning.yaml