%0 Journal Article %1 LaBhSze18 %A Lakshminarayanan, C. %A Bhatnagar, S. %A Szepesvári, Cs. %D 2018 %J IEEE Transactions on Automatic Control %K Decision Markov Processes, control planning, %N 4 %P 1185--1191 %T A Linearly Relaxed Approximate Linear Program for Markov Decision Processes %U http://ieeexplore.ieee.org/document/8014469/ %V 63 %X Approximate linear programming (ALP) and its variants have been widely applied to Markov Decision Processes (MDPs) with a large number of states. A serious limitation of ALP is that it has an intractable number of constraints, as a result of which constraint approximations are of interest. In this paper, we define a linearly relaxed approximation linear program (LRALP) that has a tractable number of constraints, obtained as positive linear combinations of the original constraints of the ALP. The main contribution is a novel performance bound for LRALP.

@article{LaBhSze18, abstract = {Approximate linear programming (ALP) and its variants have been widely applied to Markov Decision Processes (MDPs) with a large number of states. A serious limitation of ALP is that it has an intractable number of constraints, as a result of which constraint approximations are of interest. In this paper, we define a linearly relaxed approximation linear program (LRALP) that has a tractable number of constraints, obtained as positive linear combinations of the original constraints of the ALP. The main contribution is a novel performance bound for LRALP. }, added-at = {2020-03-17T03:03:01.000+0100}, author = {Lakshminarayanan, C. and Bhatnagar, S. and {Sz}epesv{\'a}ri, {Cs}.}, bdsk-file-1 = {YnBsaXN0MDDSAQIDBFxyZWxhdGl2ZVBhdGhZYWxpYXNEYXRhXxBNLi4vLi4vLi4vLi4vTGlicmFyeS5wYXBlcnMzL0ZpbGVzL0Q5L0Q5QkEzMkVGLTMyQ0QtNERBRS04MkQzLTgyNjY2QTgyOUY0Ri5wZGZPEQHaAAAAAAHaAAIAAAxNYWNpbnRvc2ggSEQAAAAAAAAAAAAAAAAAAAAAAAAAQkQAAf////8fRDlCQTMyRUYtMzJDRC00REFFI0ZGRkZGRkZGLnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA/////wAAAAAAAAAAAAAAAAAEAAQAAAogY3UAAAAAAAAAAAAAAAAAAkQ5AAIAWS86VXNlcnM6Y3NhYmE6RG9jdW1lbnRzOkxpYnJhcnkucGFwZXJzMzpGaWxlczpEOTpEOUJBMzJFRi0zMkNELTREQUUtODJEMy04MjY2NkE4MjlGNEYucGRmAAAOAFIAKABEADkAQgBBADMAMgBFAEYALQAzADIAQwBEAC0ANABEAEEARQAtADgAMgBEADMALQA4ADIANgA2ADYAQQA4ADIAOQBGADQARgAuAHAAZABmAA8AGgAMAE0AYQBjAGkAbgB0AG8AcwBoACAASABEABIAV1VzZXJzL2NzYWJhL0RvY3VtZW50cy9MaWJyYXJ5LnBhcGVyczMvRmlsZXMvRDkvRDlCQTMyRUYtMzJDRC00REFFLTgyRDMtODI2NjZBODI5RjRGLnBkZgAAEwABLwAAFQACAAz//wAAAAgADQAaACQAdAAAAAAAAAIBAAAAAAAAAAUAAAAAAAAAAAAAAAAAAAJS}, bdsk-url-1 = {http://ieeexplore.ieee.org/document/8014469/}, bdsk-url-2 = {https://dx.doi.org/10.1109/TAC.2017.2743163}, biburl = {https://www.bibsonomy.org/bibtex/2d6a47da8bd7fee8f0864b1f525cf72ee/csaba}, date-added = {2018-03-11 16:50:30 +0000}, date-modified = {2019-07-20 10:14:41 -0600}, interhash = {990f60a2832c6bdb1cb941d1941dc8ba}, intrahash = {d6a47da8bd7fee8f0864b1f525cf72ee}, journal = {IEEE Transactions on Automatic Control}, keywords = {Decision Markov Processes, control planning,}, number = 4, pages = {1185--1191}, pdf = {papers/2018-lralp-ieee-tac.pdf}, rating = {0}, read = {Yes}, timestamp = {2020-03-17T03:03:01.000+0100}, title = {A Linearly Relaxed Approximate Linear Program for {M}arkov Decision Processes}, url = {http://ieeexplore.ieee.org/document/8014469/}, volume = 63, year = 2018 }