Timezone: »

Fast Algorithms for $L_\infty$-constrained S-rectangular Robust MDPs
Bahram Behzadian · Marek Petrik · Chin Pang Ho

Tue Dec 07 08:30 AM -- 10:00 AM (PST) @
Robust Markov decision processes (RMDPs) are a useful building block of robust reinforcement learning algorithms but can be hard to solve. This paper proposes a fast, exact algorithm for computing the Bellman operator for S-rectangular robust Markov decision processes with $L_\infty$-constrained rectangular ambiguity sets. The algorithm combines a novel homotopy continuation method with a bisection method to solve S-rectangular ambiguity in quasi-linear time in the number of states and actions. The algorithm improves on the cubic time required by leading general linear programming methods. Our experimental results confirm the practical viability of our method and show that it outperforms a leading commercial optimization package by several orders of magnitude.

Author Information

Bahram Behzadian (University of New Hampshire)

I am a research assistant in the Department of Computer Science at the University of New Hampshire and a member of the Reinforcement Learning and Robustness Lab led by Marek Petrik.

Marek Petrik (University of New Hampshire)
Chin Pang Ho (City University of Hong Kong)

More from the Same Authors