Sleeping experts and bandits approach to constrained Markov decision processes

DOI10.1016/J.AUTOMATICA.2015.10.015MaRDI QIDQ901196zbMATHOpenAlexFDO

Authors Hyeong Soo Chang

Publication date 23 December 2015

Published in Automatica (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

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)