An Efficient Solution to s-Rectangular Robust Markov Decision Processes

2023/01/31 by Navdeep Kumar, Kumar, Navdeep, Kfir Y. Levy +5 · 5 citations
Computer Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2301.13642

openalex publication_date 2023/01/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present an efficient robust value iteration for s-rectangular robust Markov Decision Processes (MDPs) with a time complexity comparable to standard (non-robust) MDPs which is significantly faster than any existing method. We do so by deriving the optimal robust Bellman operator in concrete forms using our L_p water filling lemma. We unveil the exact form of the optimal policies, which turn out to be novel threshold policies with the probability of playing an action proportional to its advantage.

Cited by

• Robust Reinforcement Learning in Finance: Modeling Market Impact with Elliptic Uncertainty Sets
• ADARL: Adaptive Low-Rank Structures for Robust Policy Learning under Uncertainty
• Distributionally Robust Deep Q-Learning
• Pessimism Principle Can Be Effective: Towards a Framework for Zero-Shot Transfer Reinforcement Learning
• Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis

Related

• Efficient Policy Iteration for Robust Markov Decision Processes via Regularization
• Partial Policy Iteration for L1-Robust Markov Decision Processes
• First-order Policy Optimization for Robust Markov Decision Process
• Scalable First-Order Methods for Robust MDPs
• Best-Effort Policies for Robust Markov Decision Processes