Overview

Markov decision processes describe how an agent chooses actions as a system changes state probabilistically and rewards accumulate over time. Dynamic programming methods such as value iteration and policy iteration use Bellman equations to plan, while reinforcement learning methods such as Q-learning, policy gradients, and posterior sampling learn when transition models are unknown. Current work extends these tools to settings with constraints, risk, partial observability, non-stationarity, and large or structured state spaces, using methods such as robust optimization, state abstraction, and function approximation. A central tension is obtaining reliable safety and performance guarantees while keeping learning and planning computationally and statistically efficient beyond small tabular problems.

Latest papers

177 papers15 papers in the last four weeks, down 53% on the four weeks before. 0.1% of all new papers.

Nov 18, 2026

Bayesian κκ-Explorer for Minimax Model Estimation in MDPs

We study active exploration for minimax transition estimation in unknown Markov decision processes (MDPs). Frequentist κκ-Explorer~\citep{gu2026kappa} addresses this problem through a parameterized family of exploration objectives, but requires confidence-bound constructions and joint optimization over plausible transition kernels and occupancy measures, introducing a computational burden that limits its practical applicability. We develop Bayesian κκ-Explorer, which simplifies this procedure by placing Dirichlet priors on the transition distributions. Under the posterior mean estimator, the posterior expected squared ℓ2\ell_2 error equals the total posterior variance, providing a closed-form exploration signal. The algorithm plans under the posterior mean model, eliminating confidence-set optimization. Under the stated assumptions, this simpler planning procedure retains the O~(T−1/3)\widetilde{O}(T^{-1/3}) surrogate convergence rate of frequentist κκ-Explorer. We further bound the maximum posterior variance relative to the optimal asymptotic minimax allocation benchmark. Experiments on Pendulum, Mountain Car, and Taxi demonstrate lower worst-case transition-estimation errors than the tested baselines.
Nov 18, 2026

Approximate Dynamic Programming with Basis Function Learning

This work presents a novel approach for approximating the value function in Markov decision processes (MDPs). Our approach is grounded in the approximate linear programming (ALP) framework, wherein basis functions (BFs) play an important role. Traditionally, BFs have been pre-defined, randomly generated, or restricted to specific structures, which both limits the accuracy that can be achieved and leaves no mechanism for improving a given approximation. We instead learn BFs from the model itself, by repeatedly applying the Bellman operator to the current value estimate. We introduce the Bellman operator basis function (BOBF) learning method, and prove that each learned BF improves the approximation by a quantifiable amount and that the method converges to the optimal value function. Its shrunken counterpart (SBOBF) retains this guarantee while capping the number of BFs, and therefore the computational effort per iteration. For large-scale problems, where the number of constraints is prohibitive, we develop hybrid variants (HBOBF and SHBOBF) that combine constraint sampling with BF learning, and we show that the improvement and finite-termination guarantees are preserved under explicitly stated conditions. Numerical experiments on (continuous) perishable inventory and queueing control problems demonstrate that our BF learning techniques significantly outperform existing methods in the literature.
Nov 17, 2026

GP--RL--MPC: Uncertainty-Aware Reinforcement Learning-Augmented Model Predictive Control with Gaussian Process Postdecision State-Value Functions

We propose Gaussian Process Reinforcement Learning-Augmented Model Predictive Control (GP--RL--MPC), which uses a learned critic as the MPC terminal penalty to account for costs beyond the prediction horizon. Gaussian process regression (GPR) enables data-efficient critic learning from limited, noisy rollouts within optimistic approximate policy iteration (OAPI), with soft updates mitigating policy chattering. A tunable risk coefficient weights GP epistemic uncertainty in the terminal cost, regulating sensitivity to uncertain critic predictions. The postdecision state formulation shifts disturbance averaging offline to account for aleatoric uncertainty from the terminal transition onward. Under matching objectives and admissible actions, a one-step horizon recovers greedy value-space RL. After fitting GP hyperparameters by exact marginal likelihood, we construct a sparse deterministic training conditional (DTC) posterior using inducing points selected by pivoted Cholesky (PC), reducing online evaluation costs as the training dataset grows. In a continuous stirred-tank reactor (CSTR) subject to exogenous disturbances, GP--RL--MPC with an appropriately selected risk coefficient and policy screening reduces the sum of squared errors (SSE) by an average of 80.52% relative to an otherwise matched baseline MPC across five random seeds (sample standard deviation: 3.48%).
Nov 16, 2026

Subprocess-Constrained Markov Decision Processes

Constrained Markov decision processes (CMDPs) typically bound expected cumulative cost from an initial state. Such a guarantee can be insufficient when a policy must remain feasible after every history it may encounter. We introduce subprocess-constrained MDPs (S-CMDPs), which require the expected discounted cost of each continuation, conditional on any reachable history, to satisfy a bound determined by the current state. This stronger requirement changes the structure and complexity of the problem: we show that stationary policies can be strictly suboptimal, and finding even an approximately optimal stationary policy is NP-hard. We adapt a recently introduced value-set iteration framework to show that history-dependent policies surprisingly overcome both obstacles. Our polynomial-time algorithm represents such a policy implicitly: its expected reward is within εε of the optimal feasible value, it violates each subprocess cost bound by at most δδ, and its action distribution can be computed in polynomial time for any given history.
Nov 15, 2026

Lossless First-Action Menus for Linear-Reward Planning

We study sequential decision making where an agent reserves a minimum menu of initial actions before multi-objective trade-offs are revealed, followed by unrestricted continuation planning once linear reward weights arrive. We prove that a menu preserves the unrestricted optimal return across all linear scalarizations if and only if its reachable continuations cover all vertices of the full feature polytope. This geometric equivalence yields an output-sensitive algorithm that is fixed-parameter tractable in the vertex count, combining scalar backward induction with oracle-based facet identification. On explicitly layered graphs with unit feature increments, menu verification is coNP-complete and synthesis is complete for the second existential level of the polynomial hierarchy, even under additive loss strictly below one. In fixed dimensions two and higher, verification is polynomial whereas synthesis remains NP-complete, while one-dimensional instances admit polynomial-time solutions.
Nov 12, 2026

Improved Regret via Variance-Aware Policy Optimization in Adversarial MDPs

We study episodic adversarial MDPs with unknown dynamics and full-information rewards and achieve regret with leading term O~(H3SAK)\widetilde O(\sqrt{H^3SAK}). Here HH is the horizon, SS the total number of states across decision layers, AA the number of actions, and KK the number of episodes. This improves the two incomparable prior leading terms by factors S/H\sqrt{S/H} and H3\sqrt{H^3}, leaving a factor H\sqrt H to the lower-bound scale. We give a reduction from unknown to known dynamics for downstream-dependent algorithms, whose policy at step hh is computed only from information at steps h+1h+1 and onward. This reduces the remaining leading-order gap to finding a downstream-dependent known-dynamics algorithm with O~(HK)\widetilde O(H\sqrt K) regret, which would yield the tight O~(HSAK)\widetilde O(H\sqrt{SAK}) leading term for unknown dynamics. We instantiate the reduction with VOPO, a policy optimization (PO) algorithm. Its improved guarantees follow from a variance-aware analysis enabled by a novel bonus, which we call the Stability-Matching Bonus (SMB). VOPO achieves O~(H3K)\widetilde O(\sqrt{H^3K}) regret under known dynamics with full information; its H\sqrt H gap to the target HKH\sqrt K rate is inherited by our unknown-dynamics guarantee. We also show that with known dynamics and trajectory bandit feedback, VOPO achieves O~(H2SAK)\widetilde O(\sqrt{H^2SAK}) regret. Both known-dynamics guarantees improve the corresponding state-of-the-art PO bounds by a factor H\sqrt H. A matching lower bound establishes that the full-information rate is tight in one parameter regime.
Nov 12, 2026

Introducing Feedback Delays to Non-Delayed Adversarial MDPs: Optimal S\sqrt S and K\sqrt K Dependencies in Tabular and Linear AMDPs

We study regret minimization in episodic Adversarial Markov Decision Processes (AMDPs) with unknown transitions and bandit feedback. In tabular AMDPs with SS states, AA actions, and horizon HH, the best known KK-episode regret is O~(HSAK)\tilde O(HS\sqrt{AK}), whose S\sqrt S gap to the Ω(HSAK)Ω(H\sqrt{SAK}) lower bound has long remained open. In linear AMDPs with dd-dimensional features, after a five-year line of improvements starting from K14/15K^{14/15}, computationally efficient algorithms without a simulator or exploratory assumptions still only attain O~(K3/4)\tilde O(K^{3/4}) regret. A common challenge in both settings is to estimate the Q-function of a changing policy: past data comes from earlier policies that differ from (and are correlated with) the current one, while freezing the policy for future episodes worsens the dependency on KK. We instead propose a general technique called introduced feedback delays: we estimate the Q-function of the policy using future episodes while still updating the policy, as if the feedback were delayed. While feedback delays are usually an obstacle imposed by the environment, here they are introduced voluntarily and, perhaps surprisingly, come at no extra cost. We develop Geometric Resampling with Rejection (GRR) to account for policy changes during the delay, and threshold the visitation probabilities to avoid long delays on rarely visited state-action pairs. With this unified technique, our policy optimization algorithms achieve, with high probability, O~(poly(H)SAK)\tilde O(\text{poly}(H)\sqrt{SAK}) regret in tabular AMDPs, resolving the open problem; and O~(poly(d,H)K)\tilde O(\text{poly}(d,H)\sqrt K) regret in linear AMDPs, giving the first efficient algorithm optimal in KK. They also naturally extend to delayed AMDPs with a total feedback delay D\mathfrak D, yielding the first bounds optimal in SS and D\mathfrak D (tabular) and in KK and D\mathfrak D (linear).
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

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 5, 2026

Provably Efficient Representation Learning for Low-Rank CMDPs

We study representation learning in low-rank Constrained Markov Decision Processes (CMDPs), where both value and reward functions are approximated by a set of unknown representation vectors, and the transition dynamics admit a low-rank factorization. The objective is to maximize expected cumulative rewards while complying with constraints on the expected cumulative utility. To achieve this, we propose MFRLC (Model-Free Representation Learning for Low-Rank CMDP), a model-free algorithm that uses a primal-dual scheme to effectively balance reward regret and constraint violations. To the best of our knowledge, MFRLC is the first representation-learning method for low-rank CMDPs that combines the Least-Squares Value Iteration with Upper Confidence Bound (LSVI-UCB) and primal-dual techniques. MFRLC further enhances value function estimation with bonuses for function approximation and learns the mapping from representations to value functions directly, avoiding explicit estimation of the transition kernel. We prove that, with high probability, MFRLC achieves O~(K3/4)\widetilde O(K^{3/4}) reward regret and cumulative constraint violation over KK deployment rounds, independent of the size of the state space. To our knowledge, these are the first sublinear regret and violation guarantees for CMDPs with unknown features.
Nov 3, 2026

Regret Equals Integrated Covariance: Exact Identities for the Value of Information in Stochastic Optimization

For a stochastic program min⁡z∈ZcTz+h(z)\min_{z\in Z} c^T z + h(z) with a random cost vector cc, regret, or the expected value of perfect information, is usually computed by re-solving the problem scenario by scenario. We show that regret is determined by the covariance between the cost vector and the optimal decision πs(c)π^s(c). The identity is exact and holds without regularity assumptions once the covariance is integrated along the path from the mean to each scenario. With cs=E[c]+s(c−E[c])c_s=E[c]+s(c-E[c]), Reg=−∫01s−1Cov(cs,πs(cs)) dsReg=-\int_0^1 s^{-1} Cov(c_s,π^s(c_s))\,ds. Three consequences follow. First, the plain covariance is always an upper bound: 0≤Reg≤−Cov(c,πs(c))0\le Reg\le-Cov(c,π^s(c)). Second, when the optimal decision rule is affine, as in unconstrained and equality-constrained (e.g., budget-constrained Markowitz) quadratic programs, regret equals exactly one half of the covariance. For purely linear objectives, an affine rule forces zero regret. Third, the ratio of regret to covariance lies in [0,1][0,1] and is governed by the shape of the covariance profile along the path. The noise level at which this profile first becomes positive is a decision-stability margin that tightens the bound. The identity also holds scenario by scenario for any predicted cost, so it applies to linear and combinatorial programs with discontinuous decision rules. We give dimension-free concentration bounds and a central limit theorem for the plug-in estimator. Across 7 problem classes, 8 cost distributions, and the shortest-path benchmark of Elmachtoub and Grigas (2022) with 10610^6 draws per configuration, the identities hold to within quadrature error, and the covariance bound holds in every scenario.
Nov 3, 2026

LLMs as MDP Designers: A Dependency-Aware Agentic Framework for Automated Robot Policy Generation

We investigate the automated generation of executable robot reinforcement learning (RL) policies from natural-language task descriptions. Rather than using large language models (LLMs) as execution-time decision makers, we use them as designers that construct RL pipelines before deployment, including Markov decision process (MDP) formulation and simulator implementation. We identify a phase-wise structure in this problem: MDP formulation is dependency-structured and sequential, whereas simulator implementation becomes modular once the formulation is fixed. Based on this structure, we propose ARPG, a dependency-aware agentic framework that performs sequential MDP modeling, localized verification and correction, and simulator-structured implementation while externalizing intermediate artifacts. ARPG targets a key failure mode of automated policy generation: executable code may still yield non-learnable policies when state, action, reward, and termination artifacts are not semantically aligned. Experiments in Isaac Sim show that ARPG improves modeling correctness, environment executability, and policy-generation success compared with monolithic LLM baselines and off-the-shelf agentic systems. Additional demonstrations on custom robotics, standard RL, and engineering-domain MDPs further suggest that the same modeling pipeline can be reused beyond the main benchmark suite.
Oct 30, 2026

Instance-dependent sequential limits as an exact information ledger

Instance-dependent limits for bandit regret, sequential tests, best-arm identification and Markov decision processes are proved by one chain. It runs from a divergence decomposition through data processing to a statistic, a testing step that turns a class guarantee into a requirement on the history, and optimization over alternatives and allocations. Only the first step is an identity. This work writes the chain as an exact ledger. By the chain rule, data processing loses exactly a conditional divergence, which vanishes for arms in natural exponential families at the per-arm counts and reward sums. A one-parameter family of martingale identities extends the decomposition to every tilt between two instances. The classical limits follow by relaxations with named defects. All defects but the asymptotic step's can be computed from an algorithm's own runs, the uniform quantification's only when the class guarantee is a number. On seven published sources, from movie ratings to engine replacement, the ledger locates the difference between standard algorithms and the classical limits. For identification among trained models and for Wald's test the largest term is usually the uniform quantification's.
Oct 30, 2026

When Is a Game a Markov Decision Process? Correspondences Between Game Theory and Reinforcement Learning

Reinforcement learning and game theory describe the same object from two sides. Game theory says what a rational outcome of a strategic interaction is; reinforcement learning says how an agent could reach one through experience. The two literatures nevertheless keep separate vocabularies for identical structures, and the treatments that bridge them present the correspondence as analogy rather than theorem. This monograph supplies the theorems. A game is a Markov decision process in three distinct senses, and every table entry is labelled with the one that applies: a definitional identity, an exact reduction carried by a value- and solution-preserving map, or a structural analogy that fails under identifiable conditions. We take every standard class of game, from normal-form through repeated, stochastic, partially observable, extensive-form with imperfect information, Bayesian, graphical, Stackelberg, potential, coalitional, mean-field and evolutionary games, and identify for each the decision-theoretic model that reinforcement learning already studies under another name. The same treatment is applied to solution concepts: Nash equilibrium and the fixed point of the Bellman optimality operator, quantal response equilibrium and the soft Bellman operator, the Shapley value and credit assignment, Blackwell approachability and no-regret learning. We map each model class onto the training procedures sound for it and record the complexity of the associated solution problems. A final part collects the correspondences that do not hold: the non-stationarity that invalidates the independent-learner reduction, the impossibility results that forbid uncoupled convergence to Nash equilibrium, and the gap between the coarse correlated equilibria that no-regret self-play reaches and the correlated equilibria it is credited with.
Oct 29, 2026

FB-MOAC: A Reinforcement Learning Algorithm for Forward-Backward Markov Decision Processes

Reinforcement learning (RL) algorithms are effective in solving problems that can be modeled as Markov decision processes (MDPs). These algorithms primarily target forward MDPs whose dynamics evolve over time from an initial state. However, several important problems in different scenarios including stochastic control and network systems exhibit both a forward and a backward dynamics. As a consequence, they cannot be expressed as a standard MDP, thereby calling for a novel theory for RL in this context. Accordingly, this work introduces the concept of Forward-Backward Markov Decision Processes (FB-MDPs) for multi-objective problems, develops a novel theoretical framework to characterize their optimal solutions, and proposes a general forward-backward step-wise template that allows to adapt RL algorithms for FB-MDP problems. A Forward Backward Multi Objective Actor Critic (FB-MOAC) algorithm is introduced accordingly to obtain optimal policies with guaranteed convergence and a competitive rate with respect to standard approaches in RL. FB-MOAC is evaluated on diverse use cases in the context of mathematical finance and mobile resource management. The obtained results show that FB-MOAC outperforms the state of the art across different metrics, highlighting its ability to learn and maximize rewards.
Oct 28, 2026

Game-Theoretic Foundations for Undiscounted Bisimulation Metrics

Bisimulation metrics offer a principled notion of task-relevant state similarity in reinforcement learning, but existing constructions and methods are largely confined to discounted MDPs, where contraction arguments ensure well-defined fixed points and downstream guarantees. We develop a unified foundation for bisimulation metrics in undiscounted settings, that is total- and average-reward problems, by replacing the standard operator-centric view with a game-centric one: we interpret prior metric operators as Bellman-Shapley operators of zero-sum turn-based games and define metrics as the corresponding game value functions, yielding unique definitions even when γ=1γ=1. This game-theoretic foundation facilitates transfer of dynamic-programming theory and algorithms. We also use this game-centric perspective to characterize how metric finiteness depends on structural properties of the underlying MDP and motivate certain directed metrics that remain finite in weakly communicating MDPs. We further introduce an abstract framework for modifying the games' action spaces, allowing general transition coupling sets, that recovers many existing metrics and guides new constructions. Finally, we prove that these metrics bound total-reward and, when the optimal gain is state-independent, optimal relative value differences. We also provide error and suboptimality guarantees for aggregation-based planning in total- and average-reward settings.
Oct 22, 2026

Primal-Dual Representation Learning for Low-Rank Constrained MDPs

Representation learning has substantially improved the efficiency of unconstrained continuous-state Markov Decision Processes (MDPs), but its extension to Constrained MDPs (CMDPs) is difficult because the transition representation must be learned while constraint violation is controlled. In this paper, we study representation learning for low-rank CMDPs with continuous state spaces, and propose REP-PD-TEG for the soft cumulative-violation setting. In the feature learning period, the algorithm interacts with the environment using a decaying-εε-greedy mixture execution policy, and uses the collected samples to learn transition features by maximum likelihood. Based on the learned features, it constructs uncertainty bonuses and plans with an optimistic Lagrangian objective to obtain the return policy. We prove regret and soft-violation guarantees for the return policies, and quantify the influence of the decaying-εε-greedy exploration. In particular, REP-PD-TEG achieves the optimal O~(K)\widetilde O(\sqrt K) return policy bound, and gives a O~(K3/4)\widetilde O(K^{3/4}) overall sample bound when exploratory actions are charged. For the stricter hard cumulative violation, where feasibility must be verified episode by episode, we propose REP-PD-H-TEG. It plans under a bonus-corrected lower-confidence utility certificate with the learned representation, and performs a stabilized dual search to obtain the return policy, yielding regret and hard-violation bounds. Together, these results give the first theoretically guaranteed representation-learning method for low-rank continuous-state CMDPs with both soft cumulative guarantees and certified hard-violation control.
Oct 21, 2026

Dissimilarity-Based Markov Decision Processes for Stabilizing State Distributions

Reinforcement learning for stochastic systems typically optimizes expected cumulative rewards, while reliable and repeatable behavior also depends on how the state distribution evolves over time. Optimizing expected return alone does not guarantee that this distribution converges to a desired target or remains stable. This paper develops a theoretical framework for learning policies that stabilize state distributions. We formulate the problem as a Dissimilarity-based Markov Decision Process (DMDP), in which the policy acts on the current state distribution and the objective measures its dissimilarity to a target distribution. We establish sufficient conditions under which the optimal policy makes the target distribution asymptotically stable. To support policy learning, we introduce a finite-dimensional representation of distributions and show how stability guarantees for its parameter dynamics extend to the underlying state distributions. We further develop certificates for the learned policies, including their deployment using estimated distribution parameters. These results quantify how learning and estimation errors affect the guarantees and identify conditions under which learned policies retain asymptotic stability. For practical implementation, we combine distribution estimates and target-dependent rewards with PPO and SAC. A computable example on a linear system illustrates the proposed theoretical certificates. Furthermore, experiments on a HalfCheetah task demonstrate the benefits of distribution feedback and explicit target matching for regulating the velocity distribution.
Oct 19, 2026

Towards instance-dependent regret optimality in Episodic MDPs with Posterior Sampling

We study regret minimization in finite-horizon episodic Markov Decision Processes (MDPs). While minimax-optimal algorithms are known, tractable approaches to instance-dependent optimality are still lacking. Motivated by this gap, we introduce π0π_0-PSRL, a variant of PSRL that uses posterior samples to decide when exploration is needed, while following a fixed reference policy π0π_0 during exploration episodes. This decouples the test for exploration, triggered when the sampled and empirical MDPs have different optimal policies, from the choice of the policy used to gather information. The resulting design addresses a limitation of standard PSRL, where the sampled optimal policy may not be the optimal choice for exploration. We prove instance-dependent regret bounds for π0π_0-PSRL, identifying the logarithmic exploration cost induced by π0π_0 and taking a step toward matching asymptotic lower bounds for episodic RL. Our proof techniques showcase a novel proof structure to derive problem-dependent regret bounds in episodic MDPs, and concentration results for Dirichlet random variables, that may be of independent interest.
Oct 17, 2026

Anticipatory Gait Switching for Quadrupeds via Look-Ahead MDP Planning

Quadruped robots often switch gaits to traverse mixed terrain safely. Many practical supervisors enforce hardware constraints (e.g., dwell or guard intervals) using a transition handler. However, the switch decision itself is often driven by near-field thresholds, which can delay commitment when rough terrain is only detected shortly before contact in the local height map. We propose a lightweight height-map-only gait supervisor that unifies look-ahead and locomotion constraints in a single decision policy. A robot-centered height map is partitioned into near-, mid-, and far-field bands, each discretized into a terrain class, and band evolution is modeled as a Markov process. Gait selection is cast as a look-ahead Markov Decision Process whose transition model and cost explicitly encode platform-specific switching constraints. Indoor and outdoor experiments on a Unitree Go2 platform show reduced late switching, lower time spent using ineffective gaits on rough terrain, and improved roll stability compared to tuned reactive baselines. Overall, the MDP formulation yields anticipative constraint-aware gait switching that improves robustness without course-specific retuning.
Oct 16, 2026

Parametric Resonance in Primal-Dual Learning for Slowly Non-Stationary Constrained MDPs

Primal-dual methods for constrained Markov decision processes are analyzed under a two-timescale assumption, with non-stationarity entering through two channels. In the additive channel, where the constraint level oscillates, the dual oscillation saturates at a floor set by the moving optimum and is amplified linearly by the timescale ratio. In the parametric channel, where the constraint sensitivity oscillates, a coherent modulation carries no resonant forcing at any depth: the dual update's stiffness modulation cancels the primal update's damping modulation. Instability instead comes from a mismatch between the constraint estimate used by the primal update and the measurement used by the dual update, producing a parametric resonance at twice the pair's natural frequency. The tolerated mismatch grows with the square root of the forcing bandwidth and collapses with the square root of the dual-to-primal step-size ratio. These results hold on the tangent linear-quadratic reduction around an active saddle, for one constraint and for KK constraints under a common modulation and an isotropy condition. Driving both updates from the same estimate removes the resonant forcing but introduces a stationary offset equal to the estimator's bias. In a Lagrangian soft actor-critic agent, the multiplier locks onto the sub-harmonic at the timescale ratios its identified linear loop predicts and a coherent cost critic suppresses the lock-in, while a proportional (PID) term, predicted to leave the lock-in in place, suppresses most of it through the projection of the multiplier.
Oct 16, 2026

Contracting with an Agent under Model Mismatch

In the classical principal-agent setting, the principal delegates some task to the agent, who receives a payment conditioned on the outcome of the task, which in turn benefits the principal. To align their objectives, the principal designs a contract that incentivizes the agent to take actions beneficial to the principal. In practice, however, the agent may act under misspecified beliefs about the underlying environment, leading to systematically suboptimal decisions. In this work, we study this problem through a principal-agent Markov Decision Process (PAMDP), in which the principal repeatedly interacts with an agent whose transition model may differ from the true environment dynamics. The principal has access to the true transition model and designs contracts that account for the agent's belief and incentives. We characterize contract design under model mismatch and develop a framework that enables the principal to induce desirable long-term benefits even though the agent has a potentially inaccurate understanding of the environment.
Oct 14, 2026

Robust Counterfactuals for Markov Decision Processes under Statistical and Causal Uncertainties

Counterfactual reasoning (asking what would have happened, had a decision been different) is a powerful tool for identifying causes of failure and explaining the behaviour of AI systems in sequential decision-making tasks. In Markov Decision Processes (MDPs), two sources of uncertainty complicate counterfactual inference: statistical uncertainty in the MDP transitions when the MDP is estimated from trajectory data, and uncertainty about the unknown causal model, as there are multiple structural causal models (SCMs) compatible with each MDP. Existing work addresses these two challenges in isolation. We address both simultaneously by introducing a framework for partial counterfactual inference in MDPs that is robust to both statistical and causal uncertainty. Our approach provides: 1) closed-form analytical bounds for the counterfactual probabilities that are valid across all SCMs entailed by a given interval MDP (IMDP); 2) a method to compute minimal robust interventions to achieve a desired counterfactual outcome via pessimistic value iteration on the induced counterfactual IMDP. Since the latter is constructed using our analytical bounds, our approach remains efficient and scalable to realistic MDP environments. Experiments across multiple case studies demonstrate our method's robustness and practical utility for identifying minimal sets of actions that, if changed, would have led to improved outcomes.
Oct 13, 2026

Certifying Almost-Sure Reachability in Unknown MDPs

{\em Specification-Guided Reinforcement Learning (RL)} has largely concerned itself with learning an optimal policy against a formal specification in an unknown {\em Markov Decision Process (MDP)}. We take up the dual question. Given a policy already in hand, can one verify that it is correct against a formal specification in an unknown MDP, using sampling access alone? Such a question arises naturally in safety-critical systems. We investigate it for the {\em almost-sure reachability property}, whose correctness is witnessed by a {\em ranking supermartingale (RSM)} certificate. Our first finding is negative. In the absence of any further information about the MDP, one can neither learn such a certificate nor verify a candidate one with probabilistic guarantees. On the positive side, we show that, under a mild restriction, a known lower bound pmin⁡p_{\min} on nonzero transition probabilities, a correct certificate can be learned with PAC-style guarantees. To the best of our knowledge, this is the first study of learning and verifying certificates for almost-sure reachability in unknown MDPs from sampling access alone. Finally, our experiments show that the pmin⁡p_{\min}-based sufficient condition, while sound, is conservative: the learned certificate often remains valid on the true MDP even when the condition fails.
Oct 13, 2026

Convex-Analytic View of Query Selection for Safety Verification of Markov Decision Processes

Safety verification of a Markov decision process (MDP) asks whether the probabilities of reaching several failure states jointly lie in a convex safe region under every scheduler. Watanabe and Unno (2026) prove safety by refining an outer approximation of the failure probabilities, where each query bounds a nonnegative weighted sum of the probabilities. Their rule selects weights by the largest Euclidean violation. We present a unified framework to measure violation in an explicitly chosen error unit: directions are scored by the support-function gap between the outer approximation and the safe region, normalized by the support function of the unit. We show that the maximal score, when positive, equals the smallest enlargement of the safe region in multiples of that unit that contains the outer approximation. The Euclidean unit recovers the earlier rule; two new rules are generated by the unit cube and the safe region itself. We experimentally evaluate how the choice of measurement rule affects the performance of safety verification for MDPs.
Oct 8, 2026

Closing the Horizon Gap in Policy Optimization for Adversarial MDPs

We consider policy optimization for online episodic tabular Markov decision processes (MDPs) with adversarial losses and bandit feedback. Policy optimization updates the policy locally at each state and avoids optimization over the occupancy-measure polytope, but its existing regret bounds are larger by a factor of the horizon HH than those of occupancy-measure-based algorithms. We close this gap by using regularized QQ-functions, which allow us to control the stability of the local updates jointly over all state-action pairs rather than separately at each state. The resulting algorithm attains high-probability regret bounds of O~(HS(H+A)T)\widetilde O(\sqrt{HS(H+A)T}) for known transitions and O~(HSAT)\widetilde O(HS\sqrt{AT}) for unknown transitions, where SS is the number of states, AA the number of actions, and TT the number of episodes. Both bounds improve the horizon dependence of existing policy optimization bounds, and the latter matches the best-known bound. We further extend the algorithm to adversarial linear-mixture MDPs and obtain the same improvement in the horizon dependence.
Oct 8, 2026

Toward Optimal Regret in Adversarial MDPs with Stochastic Hard Constraints

We study episodic constrained Markov decision processes with adversarial losses under stochastic hard constraints. Specifically, starting from a known strictly feasible policy with margin dd, we seek to obtain optimal regret while satisfying the expected cost constraints in every episode. In this setting, Stradi et al. (2025) show that a carefully designed mixing rule attains regret of order O~(T/min⁡{d,d2})\widetilde{\mathcal{O}}(\sqrt{T}/\min\{d,d^2\}). Interestingly, they also provide a lower bound of order Ω(T/ρ)Ω(\sqrt{T}/ρ) for the same setting, where ρρ is the Slater margin of the offline problem and can be much larger than dd. In this work, we build on their approach to obtain optimal regret dependence on these margins. Specifically, we propose MA-OPS, an algorithm that combines an optimistic search for the Slater margin with a pessimistic evaluation of the selected policies to safely learn a policy with a large feasibility margin. This policy is then used to minimize regret while satisfying the constraints at every episode. In particular, we show that MA-OPS attains regret O~(T/ρ+1/(dρ))\widetilde{\mathcal{O}}(\sqrt{T}/ρ+ 1/(dρ)). Finally, we provide a matching lower bound, showing that the dependence on TT, dd, ρρ in the regret bound is optimal up to logarithmic factors.
Oct 8, 2026

Policy Synthesis for Finite Populations of MDP Agents under Aggregate Reach-Avoid Chance Constraints

Consider a finite population of agents with decoupled Markov transition dynamics and empirical-density feedback, subject to the following constraints: with probability at least 1−δr1-δ_r, at least a fraction αrα_r of agents must reach a target region at some time t∗t^*, while, at each time up to t∗t^*, the unsafe population fraction must remain below βuβ_u with probability at least 1−δu1-δ_u. However, standard mean-field methods enforce these constraints only in expectation, which fails to account for stochastic fluctuations at finite fleet size NN. To address this control problem, we propagate the second-order moment (variance) of the empirical density alongside the mean-field trajectory via a discrete-time Lyapunov recursion, and apply the Cantelli inequality to convert chance constraints into tractable deterministic conditions on the moments of the empirical density. We then incorporate these moment-based surrogate constraints into a gradient-based sequential convex approximation procedure for density-feedback policy synthesis. We further introduce additional moment-error bounds to construct a rigorous finite-NN certificate. The method is evaluated on a gridworld environment and a power-system EV-charging aggregation problem and compared with a standard deterministic population-level LP baseline.
Oct 7, 2026

Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach

We study learning optimal policies in average-reward multichain Markov decision processes (MDPs), where the optimal gain may depend on the initial state and recurrence structures vary across policies, creating challenges for reinforcement learning (RL) methods. We propose an asynchronous value-iteration-based RL algorithm that requires no model knowledge beyond the MDP's transition graph and leverages Bather's decomposition to hierarchically partition the state space into communicating subsystems and transient states. This decomposition induces a recasting of the global decision problem into structured subproblems, which our algorithm exploits. We show that the algorithm converges to the optimal gain and produces gain-optimal policies after finite time. Building on this base algorithm, we develop two further algorithms: one approximately solves the multichain average optimality equations to obtain near gain-optimal policies, and another targets near bias-optimality by approximating the optimal bias function and solving an induced average-reward multichain MDP using the base algorithm. We provide almost-sure convergence guarantees for all three algorithms and empirically compare their tradeoffs, showing that the latter two also consistently improve transient performance relative to the base algorithm. To our knowledge, these are the first essentially model-free average-reward RL algorithms for general multichain MDPs without reductions to discounted problems.
Oct 7, 2026

Online Resource Allocation with an Endogenous Markov State: Fewer LP Solves Earn More

We study finite-horizon online resource allocation with i.i.d. requests and an endogenous Markov state on a finite state space: each action affects the transition of the state that governs future rewards and resource consumption. In this problem, a transient fluid LP benchmark upper bounds the expected reward of every nonanticipating policy, while a stationary LP supplies randomized state-dependent controls. We assume that the stationary LP has a unique optimum and identify primal nondegeneracy and irreducibility of the optimal induced kernel as important regularity conditions in this framework. With a known request prior, we show that, under nondegeneracy and irreducibility, both frequent and infrequent re-solving attain O(1)O(1) regret. However, under a degenerate optimum, irreducibility yields the sharp worst-case Θ(T)Θ(\sqrt{T}) rate for infrequent re-solving, while frequent re-solving can incur Ω(T)Ω(T) regret. Thus, more frequent optimization can perform asymptotically worse. With an unknown request prior, we develop a three-phase U-shaped infrequent re-solving policy that coordinates learning and inventory correction with O(log⁡log⁡T)O(\log\log T) LP solves. When the optimal induced kernel is irreducible and the algorithm is given the optimal target state class and a constant-cost entrance policy, it attains O(1)O(1) regret under nondegeneracy and O(T)O(\sqrt{T}) regret under degeneracy. Without the target-class information, linear minimax regret is unavoidable. Numerical experiments further illustrate the instability of round-by-round re-solving relative to epoch-wise infrequent re-solving, show that thresholding greatly mitigates its loss, and find that infrequent schemes remain dominant under both known and estimated priors.