aiqbench analysis
This paper proposes a scalable framework for decision-focused learning in Markov decision processes by reformulating the problem as an occupancy measure-based linear program. By introducing soft state aggregation and random row sketching, the authors effectively address scalability issues associated with large or continuous state spaces while reducing computational costs compared to KKT-based baselines. The work advances reinforcement learning optimization techniques, making complex sequential decision-making more tractable for practical applications.
Decision-Focused Learning in MDPs: An Occupancy Measure Approach
arXiv:2610.08384v1 Announce Type: new Abstract: In this work, we consider decision-focused learning (DFL) for a Markov decision process (MDP), where existing methods differentiate through the KKT conditions of the Bellman equation and require solving a linear system over all state-action pairs, limiting its scalability. We address this by reformulating the MDP as an occupancy measure-based linear program (LP), whose feasible region is induced by predicted dynamics, and we derive a closed-form gradient by identifying the active constraints in the feasible polyhedron via the pivoting algorithm. This occupancy measure-based LP layer raises two challenges: (1) LP's solution gradient is discontinuous when active constraints change, and (2) the LP backward cost still scales with the state size, which is costly for large or continuous state spaces. We address the challenges with an augmented Lagrangian surrogate and smooth the boundary jumps by random row sketching of the constraints, and a learnable soft state-aggregation layer and its function-approximation generalization that scales the LP to large finite and continuous-state MDPs. Across multiple tasks, our methods reach lower regret than KKT-based DFL and two-stage baselines with significantly lower computation cost. The source code for all experiments is available at https://github.com/A-Eshragh/State_Aggregation_Project.
Abstract:In this work, we consider decision-focused learning (DFL) for a Markov decision process (MDP), where existing methods differentiate through the KKT conditions of the Bellman equation and require solving a linear system over all state-action pairs, limiting its scalability. We address this by reformulating the MDP as an occupancy measure-based linear program (LP), whose feasible region is induced by predicted dynamics, and we derive a closed-form gradient by identifying the active constraints in the feasible polyhedron via the pivoting algorithm. This occupancy measure-based LP layer raises two challenges: (1) LP's solution gradient is discontinuous when active constraints change, and (2) the LP backward cost still scales with the state size, which is costly for large or continuous state spaces. We address the challenges with an augmented Lagrangian surrogate and smooth the boundary jumps by random row sketching of the constraints, and a learnable soft state-aggregation layer and its function-approximation generalization that scales the LP to large finite and continuous-state MDPs. Across multiple tasks, our methods reach lower regret than KKT-based DFL and two-stage baselines with significantly lower computation cost. The source code for all experiments is available at this https URL.
Machine Learning (cs.LG)
arXiv:2610.08384 [cs.LG]
(or arXiv:2610.08384v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.08384 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 285 words
Related coverage
Concrete Evaluations to Investigate the OpenAI Model That Hacked Hugging Face
AI Alignment Forum · Aug 3, 2026
BRICS Draws a New Global Line: Full Text of New Delhi Declaration
slguardian.org · Sep 12, 2026
Online Policy Evaluation for MDPs with Dynamic UBSR Measures
arXiv · Jul 28, 2026
Closing the Horizon Gap in Policy Optimization for Adversarial MDPs
arXiv · Oct 9, 2026