Algoritmo Exato de Avaliação de uma Política Estacionária para CVaR MDP
Resumo
Processos de decisão Markovianos (Markov Decision Processes -- MDPs) são amplamente utilizados para resolver problemas de tomada de decisão sequencial. O critério de desempenho mais utilizado em MDPs é a minimização do custo total esperado. Porém, esta abordagem não leva em consideração flutuações em torno da média, o que pode afetar significativamente o desempenho geral do processo. MDPs que lidam com esse tipo de problema são chamados de MDPs sensíveis a risco. Um tipo especial de MDP sensível a risco é o CVaR MDP, que inclui a métrica CVaR (Conditional-Value-at-Risk) comumente utilizada na área financeira. Um algoritmo que encontra a política ótima para CVaR MDPs é o algoritmo de Iteração de Valor com Interpolação Linear chamado CVaRVILI. O algoritmo CVaRVILI precisa resolver problemas de programação linear várias vezes, o que faz com que o algoritmo tenha um alto custo computacional. Neste trabalho, é proposto um algoritmo que avalia uma política estacionário para CVaR MDPs de custo constante e que não precisa resolver problemas de programação linear, esse algoritmo é chamado de PECVaR. Além disso, foram realizados experimentos usando o custo total esperado e o custo usando o algoritmo PECVaR de uma política neutra para inicializar o algoritmo CVaRVILI. Os resultados mostram que utilizando essas inicializações é possível diminuir o tempo de convergência do CVaRVILI na maioria dos casos.
Referências
Carpin, S., Chow, Y.-L., & Pavone, M. (2016). Risk aversion in finite Markov decision processes using total cost criteria and average value at risk. In 2016 ieee international conference on robotics and automation (icra) (pp. 335–342).
Chow, Y. (2017). Risk-sensitive and data-driven sequential decision making (Unpublished doctoral dissertation). Stanford University.
Chow, Y., Tamar, A., Mannor, S., & Pavone, M. (2015). Risk-sensitive and robust decision-making: a CVaR optimization approach. Advances in Neural Information Systems, 1522–1530.
Iyengar, G., & Ma, A. K. C. (2013). Fast gradient descent method for mean-CVaR optimization. Annals of Operations Research, 205(1), 203–212.
Pflug, G. C., & Pichler, A. (2016). Time-consistent decisions and temporal decomposition of coherent risk functionals. Mathematics of Operations Research, 41(2), 682–699.
Puterman., M. L. (1994). Markov decision processes: Discrete stochastic dynamic programming. New York, NY: Wiley-Interscience.
Uryasev, S., & Rockafellar, R. T. (2001). Conditional value-at-risk: Optimization approach. Stochastic Optimization: Algorithms and Applications, 411–435.
