Fast Algorithms for L∞-Constrained S-Rectangular Robust MDPs

Bahram Behzadian; Marek Petrik; Chin Pang Ho

Fast Algorithms for L_∞-Constrained S-Rectangular Robust MDPs

Bahram Behzadian
, Marek Petrik
, Chin Pang Ho

Department of Data Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

21 Citations (Scopus)

Abstract

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_∞-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.

Original language	English
Title of host publication	Advances in Neural Information Processing Systems 34
Subtitle of host publication	35th Conference on Neural Information Processing Systems (NeurIPS 2021)
Editors	M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, J. Wortman Vaughan
Publisher	Neural Information Processing Systems (NeurIPS)
Pages	25982-25992
Volume	31
ISBN (Print)	9781713845393
Publication status	Published - Dec 2021
Event	35th Conference on Neural Information Processing Systems (NeurIPS 2021) - Virtual, Los Angeles, United States Duration: 6 Dec 2021 → 14 Dec 2021 https://nips.cc/virtual/2021/index.html https://papers.nips.cc/paper/2021 https://media.neurips.cc/Conferences/NeurIPS2021/NeurIPS_2021_poster.pdf https://www.proceedings.com/63069.html

Publication series

Name	Advances in Neural Information Processing Systems
Volume	34
ISSN (Print)	1049-5258

Conference

Conference	35th Conference on Neural Information Processing Systems (NeurIPS 2021)
Place	United States
City	Los Angeles
Period	6/12/21 → 14/12/21
Internet address	https://nips.cc/virtual/2021/index.html https://papers.nips.cc/paper/2021 https://media.neurips.cc/Conferences/NeurIPS2021/NeurIPS_2021_poster.pdf https://www.proceedings.com/63069.html

Bibliographical note

Research Unit(s) information for this publication is provided by the author(s) concerned.

Research Keywords

MARKOV DECISION-PROCESSES

Access Output

https://papers.nips.cc/paper/2021/hash/da4fb5c6e93e74d3df8527599fa62642-Abstract.html

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Behzadian, B., Petrik, M., & Ho, C. P. (2021). Fast Algorithms for L_∞-Constrained S-Rectangular Robust MDPs. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. S. Liang, & J. W. Vaughan (Eds.), Advances in Neural Information Processing Systems 34: 35th Conference on Neural Information Processing Systems (NeurIPS 2021) (Vol. 31, pp. 25982-25992). (Advances in Neural Information Processing Systems; Vol. 34). Neural Information Processing Systems (NeurIPS). https://papers.nips.cc/paper/2021/hash/da4fb5c6e93e74d3df8527599fa62642-Abstract.html

Behzadian, Bahram ; Petrik, Marek ; Ho, Chin Pang. / Fast Algorithms for L_∞-Constrained S-Rectangular Robust MDPs. Advances in Neural Information Processing Systems 34: 35th Conference on Neural Information Processing Systems (NeurIPS 2021). editor / M. Ranzato ; A. Beygelzimer ; Y. Dauphin ; P.S. Liang ; J. Wortman Vaughan. Vol. 31 Neural Information Processing Systems (NeurIPS), 2021. pp. 25982-25992 (Advances in Neural Information Processing Systems).

@inproceedings{c30e379a67294877a0ebfc25ead5ecb0,

title = "Fast Algorithms for L∞-Constrained S-Rectangular Robust MDPs",

abstract = "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∞-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.",

keywords = "MARKOV DECISION-PROCESSES",

author = "Bahram Behzadian and Marek Petrik and Ho, \{Chin Pang\}",

note = "Research Unit(s) information for this publication is provided by the author(s) concerned.; 35th Conference on Neural Information Processing Systems (NeurIPS 2021) ; Conference date: 06-12-2021 Through 14-12-2021",

year = "2021",

month = dec,

language = "English",

isbn = "9781713845393",

volume = "31",

series = "Advances in Neural Information Processing Systems",

publisher = "Neural Information Processing Systems (NeurIPS)",

pages = "25982--25992",

editor = "M. Ranzato and A. Beygelzimer and Y. Dauphin and P.S. Liang and Vaughan, \{J. Wortman\}",

booktitle = "Advances in Neural Information Processing Systems 34",

address = "United States",

url = "https://nips.cc/virtual/2021/index.html, https://papers.nips.cc/paper/2021, https://media.neurips.cc/Conferences/NeurIPS2021/NeurIPS\_2021\_poster.pdf, https://www.proceedings.com/63069.html",

}

Behzadian, B, Petrik, M & Ho, CP 2021, Fast Algorithms for L_∞-Constrained S-Rectangular Robust MDPs. in M Ranzato, A Beygelzimer, Y Dauphin, PS Liang & JW Vaughan (eds), Advances in Neural Information Processing Systems 34: 35th Conference on Neural Information Processing Systems (NeurIPS 2021). vol. 31, Advances in Neural Information Processing Systems, vol. 34, Neural Information Processing Systems (NeurIPS), pp. 25982-25992, 35th Conference on Neural Information Processing Systems (NeurIPS 2021), Los Angeles, United States, 6/12/21. <https://papers.nips.cc/paper/2021/hash/da4fb5c6e93e74d3df8527599fa62642-Abstract.html>

Fast Algorithms for L_∞-Constrained S-Rectangular Robust MDPs. / Behzadian, Bahram; Petrik, Marek; Ho, Chin Pang.
Advances in Neural Information Processing Systems 34: 35th Conference on Neural Information Processing Systems (NeurIPS 2021). ed. / M. Ranzato; A. Beygelzimer; Y. Dauphin; P.S. Liang; J. Wortman Vaughan. Vol. 31 Neural Information Processing Systems (NeurIPS), 2021. p. 25982-25992 (Advances in Neural Information Processing Systems; Vol. 34).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Fast Algorithms for L∞-Constrained S-Rectangular Robust MDPs

AU - Behzadian, Bahram

AU - Petrik, Marek

AU - Ho, Chin Pang

N1 - Research Unit(s) information for this publication is provided by the author(s) concerned.

PY - 2021/12

Y1 - 2021/12

N2 - 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∞-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.

AB - 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∞-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.

KW - MARKOV DECISION-PROCESSES

UR - https://www.scopus.com/pages/publications/85131963203

UR - http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=LinksAMR&SrcApp=PARTNER_APP&DestLinkType=FullRecord&DestApp=WOS&KeyUT=000922928201006

UR - https://www.scopus.com/pages/publications/85131963203#tab=impact

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9781713845393

VL - 31

T3 - Advances in Neural Information Processing Systems

SP - 25982

EP - 25992

BT - Advances in Neural Information Processing Systems 34

A2 - Ranzato, M.

A2 - Beygelzimer, A.

A2 - Dauphin, Y.

A2 - Liang, P.S.

A2 - Vaughan, J. Wortman

PB - Neural Information Processing Systems (NeurIPS)

T2 - 35th Conference on Neural Information Processing Systems (NeurIPS 2021)

Y2 - 6 December 2021 through 14 December 2021

ER -

Behzadian B, Petrik M, Ho CP. Fast Algorithms for L_∞-Constrained S-Rectangular Robust MDPs. In Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Vaughan JW, editors, Advances in Neural Information Processing Systems 34: 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Vol. 31. Neural Information Processing Systems (NeurIPS). 2021. p. 25982-25992. (Advances in Neural Information Processing Systems).