Overview

Q-learning studies how an agent can estimate the long-term value of each action from rewards and transitions, then choose actions with high estimated value without first learning a full environment model. Methods range from tabular Bellman updates and fitted Q-iteration to deep critics, multi-step and entropy-regularized updates, and offline methods that constrain actions to those supported by data. Theory addresses convergence, finite-sample error, regret, and extensions to robust, risk-sensitive, continuous-time, and multi-agent settings; experiments use benchmarks including Atari, D4RL, and robotic manipulation. A central tension is that bootstrapping and greedy action selection can make learning efficient but amplify estimation errors and instability, particularly with function approximation, off-policy data, sparse coverage, or changing dynamics.

Latest papers

114 papers18 papers in the last four weeks, up 50% on the four weeks before. 0.1% of all new papers.

Nov 12, 2026

Support-Constrained Offline Policy Improvement for Pediatric ECMO from Limited Clinical Data

Managing children on ECMO (Extracorporeal Membrane Oxygenation) requires balancing short-term physiological stability with the long-term goal of preventing neurological injury. Standard reinforcement learning can propose risky, out-of-distribution actions, while imitation learning is limited to reproducing clinician behavior. We introduce Support-Constrained Fitted Q-Iteration (FQI-SC), an offline reinforcement learning framework that cautiously improves upon expert behavior by restricting optimization to empirically supported state-action pairs and defaulting to the clinician baseline in low-data regions. On 78 pediatric trajectories totaling over 6,000 hours of clinical data, we evaluate our framework using Fitted Q-Evaluation (FQE) and a behavioral disagreement. Additionally, we formalize the performance-safety trade-off by introducing a unified Balance Score (S(π)S(π)). Our empirical evaluation shows that support-constrained policy improves the Balance Score by 38% relative to FQI, improves estimated value by 1.28 FQE units over imitation learning, and reduces disagreement with clinician actions by 71% relative to FQI.
Nov 11, 2026

Understanding the Asymptotic Transience of Q-Learning via Distributional Expansion

Q-learning has been empirically observed to exhibit substantial transient error. This transient remains uncaptured by the leading Gaussian limit because the central-limit normalization removes the smaller-scale displacement generated by the initial nonlinear evolution. On the other hand, worst-case finite-sample guarantees, while accounting for transient effects, can obscure the mechanisms responsible for the error on a particular problem instance. We develop a finer asymptotic analysis that gives an asymptotically exact characterization of this transient for a fixed instance. Specifically, for synchronous Q-learning in finite discounted Markov decision processes, we separate the last-iterate error into an optimal-policy temporal-difference (TD) component and a nonnegative displacement caused by maximization. The centered TD component has Gaussian fluctuations at scale n−1/2n^{-1/2}, whereas the maximization transient is of order n−1n^{-1} and converges almost surely, after rescaling by nn, to a random limit. This limit represents the propagated effect of maximization errors generated before the greedy policy stabilizes. We combine this characterization with an Edgeworth expansion of the TD component to identify the corrections to its Gaussian approximation, separating the effects of initialization, non-Gaussian TD fluctuations, and maximization. The results reveal how transient errors arise for individual Q-learning instances and how their effects persist below the central-limit scale.
Nov 7, 2026

Horizon-Scalable Q-Learning

Learning accurate off-policy state-action value functions (Q-functions) from offline datasets becomes harder as the task horizon grows. One-step temporal-difference (TD) learning bootstraps after every transition, so small per-step errors accumulate along the horizon, and early states can be badly misvalued even when the TD loss is small. Multi-step TD shortens this chain by following the dataset trajectory for several steps; however, since the behavior policy is often suboptimal, every followed action adds a bias, and no fixed number of steps suits a whole trajectory. In this paper, we propose Horizon-Scalable Q-Learning (HQL), a simple method that enables accurate long-horizon value learning by automatically balancing between one-step and multi-step returns. HQL extends a target through a dataset action only when the critic values it at least as highly as the best-of-N actions sampled from the BC policy, and otherwise falls back to a one-step target. We show that this rule is a principled off-policy correction that needs no action densities, which makes HQL compatible with expressive flow and diffusion policies. Experiments show that HQL avoids the failures of both one-step and multi-step TD on a combination-lock task across horizons, and outperforms prior horizon-reduction methods on long-horizon OGBench and OCBench tasks.
Nov 7, 2026

An Analysis of Reinforcement Learning with Function Approximation

We address the problem of computing the optimal Q-function in Markov decision problems with infinite state-space. We analyze the convergence properties of several variations of Q-learning when combined with function approximation, extending the analysis of TD-learning in Tsitsiklis and Van Roy (1996) to stochastic control settings. We identify conditions under which such approximate methods converge with probability 1. We conclude with a brief discussion on the general applicability of our results and compare them with several related works.
Nov 7, 2026

Bayesian transfer for offline Q-learning with multi-task Gaussian processes

Offline reinforcement learning can benefit from data collected in related tasks, yet indiscriminate knowledge transfer may lead to negative transfer under task mismatch and limited target-data coverage. We propose a target-aware Bayesian transfer framework for offline Q-learning based on multi-task Gaussian processes that jointly model task-specific Q-functions. Source tasks are assessed using target predictive evidence and maximum mean discrepancy (MMD), while posterior uncertainty and behavior-supported action sets guide conservative Bellman updates and policy extraction. To account for the dependence induced by Bellman bootstrapping, we distinguish Bellman innovations from bootstrap errors and establish stability and predictive source-selection results under explicit regularity conditions. We further derive selection-adaptive posterior contraction and offline policy-performance bounds, identifying the structural conditions under which source information can be pooled to achieve minimax-optimal rates in a shared-function Gaussian sequence experiment. Simulation studies with heterogeneous source tasks demonstrate improved target Q-function estimation and reduced material negative transfer compared with indiscriminate source pooling. An application to human decision-making data further shows higher average expected immediate payoff than both target-only learning and matched-size random source selection. These results highlight the benefits of combining target-aware source selection with uncertainty-aware conservative learning for reliable and sample-efficient offline reinforcement learning.
Nov 5, 2026

O(1/n)O(1/n) Convergence Rate for RVI QQ-Learning

We establish finite-time convergence guarantee for synchronous relative value iteration (RVI) QQ-learning for finite weakly communicating Markov decision processes (MDPs). For stochastic Krasnosel'skiĭ--Mann iterations driven by a non-expansive, linearly regular map on a finite-dimensional normed space, we establish last-iterate mean-squared residual bounds under martingale-difference noise whose conditional second moment grows at most linearly with the squared residual. Suitable polynomial stepsizes of order n−an^{-a} yield an O(n−a)O(n^{-a}) rate for 0<a≤10<a\leq1. We verify linear regularity and the noise condition for the centered Bellman operator for finite weakly communicating MDPs. Applying the general result gives an O(n−1)O(n^{-1}) bound on the mean-squared Bellman span residual of RVI QQ-learning iterates when a suitable stepsize sequence is used. The positive gap between optimal and suboptimal stationary deterministic policies then yields an O(n−1)O(n^{-1}) bound on the expected suboptimality of the greedy policy. Consequently, O(ε−1)O(ε^{-1}) synchronous iterations suffice for an εε-optimal policy in expectation. These guarantees are instance-dependent, with constants that depend on the hitting-time parameters and the suboptimality gap of the second-best policy.
Nov 1, 2026

Direct Knowledge Transfer for Offline Q-Learning

Data-driven sequential decision making in marketing and healthcare can benefit from observations collected in related environments, particularly when data in the environment of interest are limited. Transferring such information requires accounting for differences in rewards and transition dynamics across environments. We study knowledge transfer for offline reinforcement learning through a joint estimation framework that directly integrates source information into target value-function learning. We propose Direct Transfer Fitted Q-Iteration (DFQI), which updates the target Q-function while simultaneously borrowing the source information through an L1 penalty that links the target coefficients to a weighted aggregate of source coefficients, with both determined jointly within each Bellman update. Using sieve approximation, we establish statistical guarantees for target estimation and policy learning in stationary discounted environments with common or heterogeneous transition kernels. Empirical studies further demonstrate the effectiveness of the proposed DFQI framework in transferring source information to improve policy learning with limited target data.
Oct 31, 2026

Entropy-Regularized Reinforcement Learning for the Regime-Switching Consumption-Investment Problem

This paper establishes an entropy-regularized reinforcement learning (ERRL) framework for the continuous-time consumption-investment problem under a regime-switching market model with general utility functions. By incorporating randomized exploratory policies and Shannon entropy regularization into the stochastic optimal control formulation, we derive closed-form representations for the optimal exploratory consumption and investment strategies. Specifically, the optimal investment strategy follows a multivariate Gaussian distribution, whereas the optimal consumption strategy takes the form of a Gibbs measure---which specializes to a Gamma distribution under logarithmic utility and a non-standard exponential distribution under power utility. Crucially, our theoretical analysis reveals that the classical deterministic optimal decisions correspond to the mode---rather than the mean---of these exploratory distributions. Furthermore, we establish the convergence of the exploratory value function to its classical unregularized counterpart as the temperature parameter vanishes. For algorithmic design, we develop a continuous-time q-learning framework grounded in a novel continuous-time q-function, prove the policy improvement theorem, and establish martingale characterizations for both on-policy and off-policy learning. We find that parameterizing the actor network based on theoretical distribution families can help accelerate convergence and enhance numerical stability. Furthermore, numerical experiments across regime-switching environments provide empirical support for our theoretical findings, demonstrating stable loss convergence as well as the monotonicity and concavity of the learned value functions.
Oct 27, 2026

Cooperative EV Charging Assignment Using Multi-Agent Reinforcement Learning: A Comparison of QMIX and Independent Q-Learning Under Urban Traffic Uncertainty

The allocation of electric vehicles to public charging stations is increasingly constrained by the fact that several heterogeneous facilities often serve the same stream of requests while observing only partial local information. An accept/reject decision that is defensible for one station may nevertheless reduce the efficiency of the charging district as a whole. We formulate this operational problem as a Decentralized Partially Observable Markov Decision Process (Dec-POMDP) and examine whether Centralized Training with Decentralized Execution (CTDE), instantiated through QMIX, improves assignment performance relative to a cooperative Independent Q-Learning baseline (IQL). The evaluation uses a six-station urban network simulated with SUMO, five independent random seeds, 200 training episodes, and four traffic flux scenarios ranging from 100 to 250 vehicles/hour. Under this protocol, QMIX reaches a mean reward per evaluated decision of +0.776, versus +0.578 for IQL (delta = +0.198, seed-paired Cohens dz = 2.98, exact two-sided Wilcoxon p = 0.0625, the minimum attainable value at this sample size), and raises the acceptance rate from 72.4% to 94.0% (delta = +21.6 pp, dz = 5.24, Wilcoxon p = 0.0625). A five-variant ablation suggests this gain is primarily attributable to the CTDE architecture when holding cooperative reward terms fixed, though not formally isolated with a single seed. By contrast, cooperative reward shaping and experience sharing show no clear descriptive benefit and may slightly reduce performance. These findings support the view that, for multi-station charging assignment, coordination should be embedded in the learning architecture rather than added only through heuristic cooperation terms.
Oct 27, 2026

Frequency-Uniform Log-Regret Reinforcement Learning for Diffusions

High-frequency control problems are often studied through time discretization, but refining the timestep δδ increases the discrete horizon H=T/δH=T/δ and can make standard finite-horizon regret guarantees deteriorate even when the physical horizon TT is fixed. We study episodic value-based reinforcement learning for Euler discretizations of controlled diffusions. The performance is measured as the cumulative regret over KK episodes relative to the optimal policy of the corresponding Euler model. Under stability and regularity conditions on value function gradients, Bellman residual derivatives, and fitted critics, we prove an O(log⁡K)\mathcal{O}(\log K) regret bound with constants uniform in δδ. For dynamics with drift linear in unknown parameters and unknown constant diffusion covariance, we verify localized versions of these conditions for a constrained, model-based controlled-diffusion fitted-QQ algorithm (CD-FQ) and obtain high-probability O(log⁡Klog⁡log⁡K)\mathcal{O}(\log K\log\log K) regret for fixed and finite TT, again with constants uniform in δδ.
Oct 26, 2026

Provably Efficient Q-learning for Robust Reinforcement Learning

Standard reinforcement learning (RL) algorithms based on Markov Decision Processes (MDPs) are vulnerable to sim-to-real gaps. To address this issue, distributionally robust RL algorithms based on robust MDPs (RMDPs) have been proposed, for ensuring that agents can perform reliably to unpredictable conditions in real-world environments. Despite of the rich literature, \revision{an efficient model-free method is still lacking} for robust RL, particularly for Markovian data, which is more relevant in practical applications. In this work, we take a step towards settling this problem by proposing a sample efficient (asynchronous Q-learning) algorithm for robust RL. In particular, consider a γγ-discounted infinite-horizon RMDP with state space S\mathcal{S} and action space A\mathcal{A}, where the uncertainty set is specified by the total variation (TV) distance with uncertainty level σσ. Assuming access to a single trajectory of Markovian samples induced by a behavior policy and the nominal transition kernel, the sample complexity of the proposed Q-learning algorithm --- to achieve an entrywise ε\varepsilon-approximation of the optimal Q-function --- is bounded by 1μminε2(1−γ)3max⁡{1−γ,σ}+tmixμmin(1−γ)\frac{1}{μ_{\mathsf{min}}\varepsilon^2(1-γ)^3\max\{1-γ,σ\}} + \frac{t_{\mathsf{mix}}}{μ_{\mathsf{min}}(1-γ)} up to logarithmic factors. Here, tmixt_{\mathsf{mix}} and μminμ_{\mathsf{min}} denote the mixing time and the minimum state-action occupancy probability of the sample trajectory, respectively. This result is nearly minimax optimal, with an additional factor of 11−γ\frac{1}{1-γ}. Moreover, it achieves a significant improvement over existing bounds.
Oct 15, 2026

Generative Value Classifier

Q-learning is premised on learning a function to predict the value of a state-action pair, with the goal of using such a function to guide policy improvement. Most approaches learn this function from scratch using scalar or distributional return targets. This discriminative approach leaves another source of supervision for learning representations unused: the actions themselves. Rather than directly predict the return of a state-action pair, we ask the reverse question: how likely is the action under each possible return? This perspective provides a critic whose generative component is a return-conditioned policy, which can share the actor's architecture. Training this policy supervises the critic with every action rather than with returns alone, and a squared-error loss anchors the critic's Q-value to the bootstrapped target. We evaluate our approach on both offline and online RL tasks and show gains over leading discriminative methods, including distributional RL methods.
Oct 15, 2026

Q(γHγ_H): Entropy-Guided Horizon Mixing in Multi-Discount Q-Learning

A fixed discount factor in Q-learning imposes a single planning horizon throughout training, despite the differing demands of early exploration and long-term credit assignment. We propose Q(γHγ_H), a multi-horizon Q-learning framework that maintains multiple discount-specific heads and adaptively combines them at control time using an entropy-derived confidence signal. The resulting state-dependent mixing weights shift control from shorter- to longer-horizon heads as policy confidence increases, enabling adaptive horizon mixing without modifying individual Bellman updates. Across classical control and deep reinforcement-learning benchmarks, Q(γHγ_H) shows its strongest improvements on delayed-credit tasks relative to strong fixed-discount baselines. By decoupling horizon adaptation from the underlying learning updates, Q(γHγ_H) provides a lightweight framework for adaptive planning-horizon control in reinforcement learning, avoiding the need for manual discount-factor selection while remaining compatible with standard value-learning methods.
Oct 14, 2026

Selective Growing Q-Networks (SGQN): An Analysis of Adaptive Action Grids in Decoupled Q-Learning

Value-based Q-learning for continuous control can discretise the action space, but the resolution of the discretisation trades early exploration against final precision. Growing Q-Networks (GQN) grow the resolution uniformly from coarse to fine. We introduce Selective Growing Q-Networks (SGQN), which keeps decoupled Q-learning and replaces uniform growth with an adaptive action grid: bins are added next to bins with high estimated Q-value, bins with low Q-value are pruned, and actions are chosen epsilon-greedily. On eight DeepMind Control Suite (DMControl) tasks with 2 to 12 action dimensions, SGQN has the highest mean final return among the compared methods on four, is within 1.1% of the best method on three more, and is 3.4% below Bang-Bang MPO on Walker Run, using on average 7.5 of 9 available bins per dimension. We then test whether the adaptive grid explains these results, and find that it does not. Growth activates every candidate bin and behaves like uniform growth, and removing pruning changes the return by at most 1.1%. Two other choices matter: starting from a coarse grid, since starting with all 9 bins produces collapsed seeds, and epsilon-greedy selection, since an annealed softmax lowers the return by 23% to 100%. SGQN is insensitive to its growth and pruning hyperparameters. It also differs from the GQN and DecQN baselines in other respects, notably one gradient update per environment step instead of one per eight, which we did not control for, so we do not attribute its advantage to a single component. We present SGQN as a competitive value-based method and as an analysis of which ingredients of a growing action grid matter.
Oct 14, 2026

Non-asymptotic Convergence of Average-reward Q-learning with Options

We study the finite-sample convergence of Q-learning algorithms for the average-reward formulation of Reinforcement Learning (RL) with options. While options allow temporarily extended and hierarchical actions, the average-reward formulation incorporates continual tasks beyond discounted and episodic RL. We establish the first O~(1/iterations)\tilde{O}(1/\text{iterations}) convergence guarantees, in the mean-square sense, for average-reward option Q-learning algorithms in both the inter- and intra-option settings. First, we prove that both inter- and intra-option Bellman operators satisfy multi-step span contractions under unichain assumptions. Then, we propose synchronous estimators of these multi-step option Bellman operators leading to two variants of option Q-learning. Finally, we extend the stochastic approximation framework to prove convergence rates of these two algorithms under the minimal assumptions used in the literature.
Oct 14, 2026

Value-Guided Repulsion for Offline Reinforcement Learning

Drifting models have emerged as a highly efficient and stable paradigm for policy design in offline reinforcement learning (RL). However, standard drift policies determine repulsion solely from geometric relationships among generated actions and therefore cannot distinguish them by expected value. To address this limitation, we introduce Value-Guided Repulsion Q-Learning (VRQL) to integrate action value estimates into the particle interaction field. For each state, VRQL combines geometric kernel distance with a normalized Q value scaling. This mechanism assigns greater repulsive influence to particles with lower values while strictly retaining attraction toward behavior action. Consequently, this value-guided interaction field aligns behavior regularization with policy improvement without adding an auxiliary behavior model stage. On 50 OGBench task configurations and 6 D4RL AntMaze configurations, VRQL demonstrates highly competitive performance against established baselines, suggesting that value-guided particle interaction is an effective method for offline RL.
Oct 14, 2026

On the Convergence of Semi-Gradient TD: A Mean Field Perspective

Semi-gradient temporal-difference learning is a core algorithmic component of reinforcement learning, but bootstrapping with function approximation generally induces a non-conservative vector field and can lead to instability. We analyze this effect for two-layer neural networks in the mean-field regime and identify a simple stability mechanism in which entropy-induced relaxation dominates the sensitivity of the moving bootstrap target. Under this condition, we prove exponential convergence to a unique fixed point and quantify its bias relative to the unregularized Bellman solution. We also show that the same mechanism extends to entropy-regularized off-policy control through soft Q-learning.
Oct 13, 2026

Neural Supervised Clustering for Learning Individualized Treatment Rules with Many Treatments

Learning an individualized treatment rule (ITR) with many treatments requires estimating treatment-specific effects from limited observations per arm. Treatments with similar conditional responses can share information, but linear contrast models may miss nonlinear heterogeneity. We propose nonlinear supervised clustering fusion (NSCF), a neural Q-learning framework with a shared nonlinear covariate representation and low-dimensional treatment embeddings. Pairwise fusion groups treatments with similar learned contrasts, yielding an ITR and an interpretable partition. An alternating algorithm combines neural training, embedding fusion, validation-based partition selection, and unpenalized grouped refitting. NSCF lowers regret relative to a strong neural reference in nonlinear exact-sharing simulations; perturbations characterize the limits of hard sharing. In a melanoma xenograft application, NSCF improves average policy value over the neural reference. These results support nonlinear representation learning with supervised treatment fusion when treatment effects exhibit shared structure.
Oct 13, 2026

Fast Rates for Offline Q-Learning with KL Regularization

This paper investigates offline Q-learning for finite-horizon Markov decision processes with Kullback-Leibler (KL) regularization. Recent studies have shown that KL regularization can yield fast rates in offline decision-making problems. However, it remains unclear whether Q-learning, which adopts incremental stochastic approximation updates, can achieve such fast rates in the offline setting. We first propose KL-regularized Q-Learning (KLQ), a simple variant of classical Q-learning. By exploiting KL regularization, we prove that KLQ achieves a sample complexity of O~(1/ε)\widetilde{O}(1/ε) without explicit pessimism. This guarantee, however, has an exponential dependence on the KL regularization parameter and the horizon. To address this limitation, we further propose KL-regularized Pessimistic Q-Learning (KLPQ), which incorporates pessimism into KLQ. We prove that KLPQ retains the same O~(1/ε)\widetilde O(1/ε) rate while removing the explicit exponential dependence, thereby further improving the sample complexity. To the best of our knowledge, these results establish the first fast-rate guarantees for offline Q-learning in tabular finite-horizon KL-regularized MDPs.
Oct 13, 2026

From Policy Evaluation to Off-Policy Control: Provable Emergence of In-Context Q-Learning

Transformers can implement reinforcement-learning algorithms in context, yet how off-policy control emerges within Transformers remains poorly understood. We study Q-learning, a foundational model-free control algorithm that combines off-policy bootstrapping with greedy policy improvement. We prove that a two-layer attention-only Transformer can implement a finite-temperature form of Q-learning, where the temperature τ>0τ>0 controls the approximation to greedy action selection, recovering window Q-learning as τ→0τ\to0. We train the structured Transformer on randomly generated MDP tasks using output-only supervision. Experiments show that the theoretically predicted parameter structure emerges during training, including the internal greedy action-selection mechanism, and that the trained Transformer achieves performance comparable to Q-learning on unseen tasks. Our theoretical analysis further shows that the equivalent realizations form a solution manifold and that, under suitable task-diversity conditions, the training iterates converge locally to this manifold at an exponential rate. For the random-task model analyzed here, the local worst-case number of gradient steps needed to reduce the distance to the manifold by a factor εε is Θ(τ−5log⁡(1/ε))Θ\left(τ^{-5}\log(1/\varepsilon)\right), quantifying the increasing optimization cost as the learned update approaches window Q-learning.
Oct 11, 2026

Entropy-Regularized Mean-Field Games with Average-Reward Criterion: Span-Seminorm Contractions and Model-Free Learning

We study stationary discrete-time mean-field games with finite state and action spaces under the average-reward criterion, with an entropy-regularized objective and population-dependent dynamics and rewards. Under a minorization condition, the soft Q-operator is a span-seminorm contraction for the full transition kernel, so relative value iteration does not require the minorizing measure. When the Lipschitz constant of the kernel is below the minorization mass and the temperature exceeds an explicit threshold, the equilibrium fixed-point operator is a contraction: an equilibrium exists, its population distribution is unique, and a fixed-point iteration converges to it geometrically. We then learn the equilibrium model-free from a simulator, combining soft Q-learning at a fixed population distribution with an empirical transition kernel. We prove a finite-sample bound for soft Q-learning in the span seminorm, with temperature-independent constants, and derive convergence rates for the learned population distribution and policy. A congestion-aware routing game illustrates the results.
Oct 10, 2026

Mixing Regularization for Average-Reward QQ-Learning and QQ-Planning

The average-reward setting for reinforcement learning is challenging because its Bellman operator is known to contract in span only when the underlying Markov chain is mixing. Whereas existing work typically assumes a contraction property, e.g., through environment mixing, we consider the setting where we are given a reward-agnostic mm-step mixing policy, and we control the contraction and exploration properties of the learned policy by regularizing toward the mixing policy. We provide finite-time analysis of QQ-learning algorithms that can be instantiated with multiple choices of regularization, with guarantees measured with respect to the regularized fixed point. Our framework exposes novel regularizer-dependent objects that control contraction, exploration, and operator bias. In the one-step setting, our rates match the best known rates for QQ-iteration and synchronous QQ-learning, and for mm-step mixing we derive new rates. We also study QQ-planning variants, and show that planning acts as time-localized learning, where the planning horizon HH trades off the bias from the boundary value against the sample complexity. Finally, we present numerical studies validating the analysis: (i) knowledge of a strong mixing policy improves convergence and exploration, and its advantage increases with bottleneck severity and, (ii) our theory predicts the convergence and bias rankings of regularizers from the αα-divergence family.
Oct 9, 2026

Hitting-Time Bounds for Asynchronous Q-Learning

We study the last iterate of standard asynchronous Q-learning from a single trajectory of a finite Markov decision process. The trajectory follows a fixed behavior policy whose state--action chain is irreducible and may be periodic. For discount factor γγ, write H=(1−γ)−1H=(1-γ)^{-1}, and let μmin⁡μ_{\min} be the minimum stationary state--action probability and h⋆\mathfrak h_\star the largest expected hitting time of the reverse state--action chain. We prove that zero-initialized Q-learning with a constant step size achieves sup-norm error at most ε\varepsilon with high probability using O~(H4/(μmin⁡ε2)+h⋆)\widetilde{O}(H^4/(μ_{\min}\varepsilon^2)+\mathfrak h_\star) transitions, for 0<ε≤10<\varepsilon\le1. The statistical term retains the quartic effective-horizon dependence of standard Q-learning, while initialization cost is additive in h⋆\mathfrak h_\star. For aperiodic behavior chains, a comparison with mixing time yields a transient term O~(tmix/μmin⁡)\widetilde{O}(t_{\mathrm{mix}}/μ_{\min}). An empirical state--action count rule selects a constant step size for a subsequent training run and attains the same rate without prior knowledge of model parameters, target accuracy, or confidence level. The output is the last training iterate, with both stages included in the sample count. The proof uses two deterministic Bellman envelopes to separate statistical error from fixed-policy initialization error and adapts reverse-time hitting-cost compensation from TD learning to state--action propagation. An exploration lower bound holds for arbitrary predictable step sizes. Together with the existing statistical lower bound and its extension to pilot-selected constant steps, it yields matching mean-square rates up to logarithmic factors on the stated large-sample parameter classes.
Oct 7, 2026

Q-Learning with Scalar Adjoint Matching

Flow policies capture rich and diverse action distributions, and fine-tuning them with off-policy RL to improve beyond the demonstrations has drawn growing interest. However, fine-tuning a flow policy against a learned value function is not trivial, because the policy generates its action over many flow steps. Adjoint matching offers a principled way to update the flow model itself by propagating value information from the final action back to each flow step, but it requires a vector--Jacobian product through the policy at every step, a cost that grows with the number of flow steps and the policy size. We observe that the batch-averaged velocity Jacobian of pretrained flow policies concentrates on its diagonal. Motivated by this finding, we derive a closed-form scalar adjoint that scales the value gradient at the final action by the flow time, eliminating the per-step vector--Jacobian products. We further find that controlling the critic's value at policy-generated actions is particularly important under the scalar adjoint. Based on these findings, we propose Q-learning with Scalar Adjoint Matching (SQAM), which combines the scalar adjoint with a value penalty at those actions. SQAM's gains concentrate on the four hardest OGBench domains, where its success rate exceeds that of the strongest baseline in each domain by 18 to 35 percentage points. To test whether SQAM extends to large pretrained policies, we also fine-tune a vision-language-action policy on a real bimanual robot. SQAM improves over supervised fine-tuning on all three tasks.
Oct 2, 2026

QQ Can Play That Game: Online Fitted QQ-Iteration for Continuous-Action Zero-Sum Markov Games with Convex-Concave Function Approximation

Zero-sum Markov games arise in a wide variety of sequential decision-making problems such as adversarial learning and planning against modeled uncertainties. However, prior work on finite-sample guarantees on the learned state-action value function (QQ-function) for zero-sum Markov games is largely restricted to finite-action settings, or to continuous-action games in which agents have linear dynamics and quadratic rewards (i.e. linear-quadratic, or LQ, games). A central challenge in extending such guarantees to more general continuous-action zero-sum Markov games is that the associated Bellman operator involves a minimax problem that need not admit a tractable saddle-point solution. To this end, we first introduce a class of neural network function approximators for the QQ-function that is convex-concave in the players' actions, which guarantees that this minimax problem admits a pure-strategy saddle point. We then study an online variant of fitted QQ-iteration employing this function class and establish, to the best of our knowledge, the first finite-sample guarantees for non-LQ zero-sum Markov games with continuous states and actions. Our code can be found at https://github.com/CLeARoboticsLab/QCanPlayThatGame.
Oct 1, 2026

Q-Learning for Reachability in MEC-Free MDPs

Reinforcement learning (RL) for reachability specifications is fundamental to sequential decision-making. Prior work establishes asymptotic convergence to optimal policies, but only through model-based methods that must explicitly estimate the transition probabilities of the underlying Markov Decision Process (MDP). We present Quasar, the first model-free algorithm with asymptotic guarantees for reachability on the fragment of MDPs free of non-terminal maximal end components (MECs), a building block to which every MDP reduces by the standard MEC quotient. Our algorithm follows the classical Q-learning approach, using temporal-difference updates to converge to an optimal policy without ever learning the transition probabilities. The resulting learner reduces the memory footprint from the O(|S|^2|A|) that model-based methods require to O(|S||A|). On the standardized Quantitative Verification Benchmark Set, our algorithm converges to the optimal policy with orders of magnitude fewer samples than the previous model-based state-of-the-art. Together these results are a concrete step toward the practical deployment of reachability learning and, with it, of specification-guided RL.
Sep 28, 2026

Finite-Sample Theory for Fitted Q-Iteration When Actions Are Functions

Offline reinforcement learning seeks optimal decision rules from previously collected data. In some applications, a decision can be an entire function, such as a fluence map in radiation therapy or a smooth movement trajectory in robotics. In this paper, we study the finite-sample theory for fitted Q-iteration (FQI) with functional actions in a discounted infinite-horizon setting. Three major difficulties arise in this setting: first, the absence of a Lebesgue probability density for functional actions complicates coverage descriptions; second, conventional coverage requirements can be restrictive; and third, the large functional action space makes greedy optimization in FQI challenging. To address these difficulties, we study smoothness-regularized policy search under a critic-relative coverage condition. This condition measures how well logged data distinguish relevant action-value differences without requiring an action density. Our main theorem gives finite-sample guarantees for learned-policy regret relative to the best value within a fixed smooth class of functional-action policies. The results allow trajectory lengths to be either bounded or growing and Q-functions to be fitted by either functional-input kernel ridge regression or adaptive functional neural networks. For a few examples, we can obtain polynomially decaying regret bounds in the number of logged transitions, up to logarithmic factors, with logarithmically many FQI iterations. Numerical experiments show gains of learned functional-action policies over constant-action policies and support our adoption of a critic-relative coverage condition.
Sep 26, 2026

All On-Board: Fully On-Chip Neuromorphic Q-Learning with Embedded CartPole Simulation

As AI models grow in size and usage, their energy demands increase dramatically, raising sustainability and economic concerns. Neuromorphic hardware, inspired by the energy efficiency of the brain, seeks to address this challenge by offering low-power, fast-processing alternatives to conventional computing. Such hardware is particularly well-suited to control systems deployed in resource-constrained environments, which are best trained via reinforcement learning (RL). This contribution presents the design and implementation of a fully on-chip, closed-loop Loihi 2 RL agent. Our neuromorphic circuit consists of a fully embedded Q-learning algorithm and an on-chip simulation of the CartPole-v0 environment on Loihi 2. Our Q-learning algorithm trained the same number of successful agents as the CPU implementation in only half the execution time and with two orders of magnitude less dynamic power. These findings demonstrate the viability of RL on neuromorphic hardware and highlight its promise for building energy-efficient, real-time, embedded AI systems.
Sep 19, 2026

Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochs

Many real-world reinforcement learning (RL) problems evolve in continuous time, where decisions occur at irregular, event-driven intervals rather than at fixed discrete steps. We study episodic continuous-time Markov Decision Processes (MDPs) in which decision epochs are governed by a homogeneous Poisson process and the reward and transition dynamics vary smoothly over time. We consider both a fixed number of jumps per episode and a fixed time budget with a random number of Poisson decision epochs. Under a Lipschitz continuity assumption in time, we exploit local smoothness through discretization and extend both UCRL (Auer and Ortner 2006) and Q-learning (Jin et al. 2018) to this setting, proving O~(T2/3)\widetilde{O}(T^{2/3}) regret bounds for both model-based and model-free algorithms. Finally, we establish matching Ω~(T2/3)\widetildeΩ(T^{2/3}) minimax lower bounds, showing that the rate is optimal up to logarithmic factors. These results provide the first tight regret guarantees for Lipschitz-smooth continuous-time episodic MDPs with Poisson decision epochs.
Sep 17, 2026

Mitigating Retaliatory Algorithmic Collusion in Repeated Games

Reinforcement learning agents trained to maximize their own reward in repeated interactions can converge to supra-competitive outcomes resembling explicit collusion, without communication or shared design. Existing mitigation approaches are largely tied to specific economic settings, like two-sided platforms and auctions, leaving open how to design interventions for general repeated games. We address this gap by formalizing the connection between empirical observations from prior work on Q-learning collusion and classical theory of Simple Penal Codes (SPCs). We show any non-trivial SPC induces a quantifiable conditional dependence in agents' policies, detectable via the total variation distance between an agent's action distributions across cooperation and defection histories. Building on this connection, we propose CURB (Collusion Unwinding via Reward shaping and Belief injection), a reward-shaping framework that penalizes this Total Variation (TV) distance signal during Q-learning and is guaranteed to convert any SPC fixed point of the dynamics into a trivial one, thus precluding collusive equilibria sustained by punishment threats. Empirically, CURB substantially reduces collusion by Q-learning agents in both Bertrand and Cournot Competition Repeated Games. We further demonstrate that CURB extends to deep Q-network agents in Bertrand competition, suggesting the mechanism generalizes beyond tabular Q-learning.