Bellman-Taylor Score Decoding for Markov Decision Processes with State-Dependent Feasible Action Sets

• URL: http://arxiv.org/abs/2606.10979v1
• Date: Tue, 09 Jun 2026 15:15:21 GMT
• Title: Bellman-Taylor Score Decoding for Markov Decision Processes with State-Dependent Feasible Action Sets
• Abstract summary: We propose a framework that moves policy learning to a Euclidean score space while enforcing feasibility through an action decoder.<n>We apply this framework to a queueing network control problem, where the policy essentially learns a state-dependent index-based dispatching rule.<n> Numerical experiments show near-optimal performance in small instances and considerable improvements over benchmarks in larger systems.
• Score: 14.165642103539632
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many Markov decision processes (MDPs) in operations research have feasible actions that are state dependent and defined implicitly by various operational constraints. These features make it difficult to use standard deep reinforcement learning (DRL) algorithms, whose action interfaces typically assume either a fixed finite action catalog or a simple Euclidean space. Motivated by a Taylor expansion of the optimal action-value function, we propose Bellman--Taylor score decoding, a framework that moves policy learning to a Euclidean score space while enforcing feasibility through an action decoder. The induced latent-score MDP then can be optimized by standard DRL algorithms without differentiating through the decoder. We provide a performance guarantee showing that the optimality gap of this approach decomposes into a structural approximation error and an algorithmic learning error. Lastly, we apply this framework to a queueing network control problem, where the policy essentially learns a state-dependent index-based dispatching rule. Numerical experiments show near-optimal performance in small instances and considerable improvements over benchmarks in larger systems.

Related papers

• Breaking the Computational Barrier: Provably Efficient Actor-Critic for Low-Rank MDPs [53.412166189410904]
  We use supervised learning as a computational proxy to establish a hierarchy of commonly adopted RL oracles under low-rank Markov Decision Processes (MDPs)<n>Motivated by this observation, we propose a novel optimistic actor-critic algorithm that relies solely on the policy evaluation oracle.<n>We prove that our algorithm outperforms the existing sample complexity guarantees for low-rank MDPs while avoiding computationally expensive planning or optimization oracles commonly assumed in prior works.
  arXiv  Detail & Related papers  (2026-05-02T04:46:54Z)
• DynaAct: Large Language Model Reasoning with Dynamic Action Spaces [58.298135359318024]
  We propose a novel framework named textscDynaAct for automatically constructing a compact action space.<n>Our approach significantly improves overall performance, while maintaining efficient inference without introducing substantial latency.
  arXiv  Detail & Related papers  (2025-11-11T09:47:13Z)
• Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions [10.225358400539719]
  We present an efficient reinforcement algorithm for Decision (MDPs) where a linear-action-action generalizes in a feature map. Specifically, we introduce a new algorithm that efficiently finds a near-optimal policy in this setting.
  arXiv  Detail & Related papers  (2024-09-07T14:38:05Z)
• Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
  We present a new algorithm for a policy gradient in TMDPs by a simple extension of the proximal policy optimization (PPO) algorithm. We demonstrate this on a real-world multiple-objective navigation problem with an arbitrary ordering of objectives both in simulation and on a real robot.
  arXiv  Detail & Related papers  (2022-09-15T07:22:58Z)
• Offline Policy Optimization with Eligible Actions [34.4530766779594]
  offline policy optimization could have a large impact on many real-world decision-making problems. Importance sampling and its variants are a commonly used type of estimator in offline policy evaluation. We propose an algorithm to avoid this overfitting through a new per-state-neighborhood normalization constraint.
  arXiv  Detail & Related papers  (2022-07-01T19:18:15Z)
• Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning [85.50033812217254]
  Actor-critic methods are widely used in offline reinforcement learning practice, but are not so well-understood theoretically. We propose a new offline actor-critic algorithm that naturally incorporates the pessimism principle.
  arXiv  Detail & Related papers  (2021-08-19T17:27:29Z)
• Logistic Q-Learning [87.00813469969167]
  We propose a new reinforcement learning algorithm derived from a regularized linear-programming formulation of optimal control in MDPs. The main feature of our algorithm is a convex loss function for policy evaluation that serves as a theoretically sound alternative to the widely used squared Bellman error.
  arXiv  Detail & Related papers  (2020-10-21T17:14:31Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• CertRL: Formalizing Convergence Proofs for Value and Policy Iteration in Coq [1.154957229836278]
  Reinforcement learning algorithms solve sequential decision-making problems in probabilistic environments by optimizing for long-term reward. This paper develops a formalization of two canonical reinforcement learning algorithms: value and policy iteration for finite state Markov decision processes. The CertRL library provides a general framework for proving properties about Markov decision processes and reinforcement learning algorithms.
  arXiv  Detail & Related papers  (2020-09-23T22:28:17Z)
• Zeroth-Order Supervised Policy Improvement [94.0748002906652]
  Policy gradient (PG) algorithms have been widely used in reinforcement learning (RL) We propose Zeroth-Order Supervised Policy Improvement (ZOSPI) ZOSPI exploits the estimated value function $Q$ globally while preserving the local exploitation of the PG methods.
  arXiv  Detail & Related papers  (2020-06-11T16:49:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.