Sleeping experts and bandits approach to constrained Markov decision processes

DOI10.1016/J.AUTOMATICA.2015.10.015zbMATH Open1329.93154arXiv1412.4898OpenAlexW2132036095MaRDI QIDQ901196FDOQ901196

Authors: Hyeong Soo Chang 

Publication date: 23 December 2015

Published in: Automatica (Search for Journal in Brave)

Abstract: This brief paper presents simple simulation-based algorithms for obtaining an approximately optimal policy in a given finite set in large finite constrained Markov decision processes. The algorithms are adapted from playing strategies for "sleeping experts and bandits" problem and their computational complexities are independent of state and action space sizes if the given policy set is relatively small. We establish convergence of their expected performances to the value of an optimal policy and convergence rates, and also almost-sure convergence to an optimal policy with an exponential rate for the algorithm adapted within the context of sleeping experts.

Full work available at URL: https://arxiv.org/abs/1412.4898

Recommendations

• Learning algorithms for finite horizon constrained Markov decision processes
• scientific article; zbMATH DE number 4088775
• scientific article; zbMATH DE number 3852821
• Constrained Discounted Dynamic Programming
• Constrained Undiscounted Stochastic Dynamic Programming

zbMATH Keywords

constrained optimizationMarkov decision processeslearning algorithmsleeping experts and bandits

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Markov and semi-Markov decision processes (90C40) Optimal stochastic control (93E20)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• The sample average approximation method for stochastic discrete optimization
• Approximate dynamic programming. Solving the curses of dimensionality
• Sample average approximation of expected value constrained stochastic programs
• Constrained discounted Markov decision processes and Hamiltonian cycles.
• Stochastic approximation algorithms for constrained optimization via simulation
• Simulation-based algorithms for Markov decision processes.
• Non-randomized policies for constrained Markov decision processes
• ${Q}$-Learning Algorithms for Constrained Markov Decision Processes With Randomized Monotone Policies: Application to MIMO Transmission Control
• Regret bounds for sleeping experts and bandits
• An exact iterative search algorithm for constrained Markov decision processes
• Stochastically Constrained Ranking and Selection via SCORE
• Simulation-Based Discrete Optimization of Stochastic Discrete Event Systems Subject to Non Closed-Form Constraints

This page was built for publication: Sleeping experts and bandits approach to constrained Markov decision processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q901196)