Min Max Generalization for Two-stage Deterministic Batch Mode Reinforcement Learning: Relaxation Schemes

2012/02/23 by Raphaël Fonteneau, Fonteneau, Raphael, Damien Ernst +5
Computer Science · Engineering · #Adaptive Dynamic Programming Control #Advanced Control Systems Optimization #FOS: Computer and information sciences #FOS: Electrical engineering #Machine Learning (cs.LG) #Reinforcement Learning in Robotics #Systems and Control (eess.SY) #electronic engineering #information engineering

paper · pdf · doi:10.48550/arxiv.1202.5298

openalex publication_date 2012/02/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the minmax optimization problem introduced in [22] for computing policies for batch mode reinforcement learning in a deterministic setting. First, we show that this problem is NP-hard. In the two-stage case, we provide two relaxation schemes. The first relaxation scheme works by dropping some constraints in order to obtain a problem that is solvable in polynomial time. The second relaxation scheme, based on a Lagrangian relaxation where all constraints are dualized, leads to a conic quadratic programming problem. We also theoretically prove and empirically illustrate that both relaxation schemes provide better results than those given in [22].

Citations

• A tutorial on partially observable Markov decision processes

Related

• The Max-Min Formulation of Multi-Objective Reinforcement Learning: From Theory to a Model-Free Algorithm
• Improving Optimization Bounds using Machine Learning: Decision Diagrams\n meet Deep Reinforcement Learning
• A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Setting
• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can\n be Exponentially Harder than Online RL
• BRPO: Batch Residual Policy Optimization