Improved Algorithms for Misspecified Linear Markov Decision Processes

Daniel Vial, Advait Parulekar, Sanjay Shakkottai, R Srikant
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:4723-4746, 2022.

Abstract

For the misspecified linear Markov decision process (MLMDP) model of Jin et al. [2020], we propose an algorithm with three desirable properties. (P1) Its regret after K episodes scales as Kmax{\ensuremath{\varepsilon}mis,\ensuremath{\varepsilon}tol}, where \ensuremath{\varepsilon}mis is the degree of misspecification and \ensuremath{\varepsilon}tol is a user-specified error tolerance. (P2) Its space and per-episode time complexities remain bounded as $K\rightarrow\infty$. (P3) It does not require \ensuremath{\varepsilon}mis as input. To our knowledge, this is the first algorithm satisfying all three properties. For concrete choices of \ensuremath{\varepsilon}tol, we also improve existing regret bounds (up to log factors) while achieving either (P2) or (P3) (existing algorithms satisfy neither). At a high level, our algorithm generalizes (to MLMDPs) and refines the Sup-Lin-UCB algorithm, which Takemura et al. [2021] recently showed satisfies (P3) in the contextual bandit setting. We also provide an intuitive interpretation of their result, which informs the design of our algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-vial22a, title = { Improved Algorithms for Misspecified Linear Markov Decision Processes }, author = {Vial, Daniel and Parulekar, Advait and Shakkottai, Sanjay and Srikant, R}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {4723--4746}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/vial22a/vial22a.pdf}, url = {https://proceedings.mlr.press/v151/vial22a.html}, abstract = { For the misspecified linear Markov decision process (MLMDP) model of Jin et al. [2020], we propose an algorithm with three desirable properties. (P1) Its regret after K episodes scales as Kmax{\ensuremath{\varepsilon}mis,\ensuremath{\varepsilon}tol}, where \ensuremath{\varepsilon}mis is the degree of misspecification and \ensuremath{\varepsilon}tol is a user-specified error tolerance. (P2) Its space and per-episode time complexities remain bounded as $K\rightarrow\infty$. (P3) It does not require \ensuremath{\varepsilon}mis as input. To our knowledge, this is the first algorithm satisfying all three properties. For concrete choices of \ensuremath{\varepsilon}tol, we also improve existing regret bounds (up to log factors) while achieving either (P2) or (P3) (existing algorithms satisfy neither). At a high level, our algorithm generalizes (to MLMDPs) and refines the Sup-Lin-UCB algorithm, which Takemura et al. [2021] recently showed satisfies (P3) in the contextual bandit setting. We also provide an intuitive interpretation of their result, which informs the design of our algorithm. } }
Endnote
%0 Conference Paper %T Improved Algorithms for Misspecified Linear Markov Decision Processes %A Daniel Vial %A Advait Parulekar %A Sanjay Shakkottai %A R Srikant %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-vial22a %I PMLR %P 4723--4746 %U https://proceedings.mlr.press/v151/vial22a.html %V 151 %X For the misspecified linear Markov decision process (MLMDP) model of Jin et al. [2020], we propose an algorithm with three desirable properties. (P1) Its regret after K episodes scales as Kmax{\ensuremath{\varepsilon}mis,\ensuremath{\varepsilon}tol}, where \ensuremath{\varepsilon}mis is the degree of misspecification and \ensuremath{\varepsilon}tol is a user-specified error tolerance. (P2) Its space and per-episode time complexities remain bounded as $K\rightarrow\infty$. (P3) It does not require \ensuremath{\varepsilon}mis as input. To our knowledge, this is the first algorithm satisfying all three properties. For concrete choices of \ensuremath{\varepsilon}tol, we also improve existing regret bounds (up to log factors) while achieving either (P2) or (P3) (existing algorithms satisfy neither). At a high level, our algorithm generalizes (to MLMDPs) and refines the Sup-Lin-UCB algorithm, which Takemura et al. [2021] recently showed satisfies (P3) in the contextual bandit setting. We also provide an intuitive interpretation of their result, which informs the design of our algorithm.
APA
Vial, D., Parulekar, A., Shakkottai, S. & Srikant, R.. (2022). Improved Algorithms for Misspecified Linear Markov Decision Processes . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:4723-4746 Available from https://proceedings.mlr.press/v151/vial22a.html.

Related Material