Algoritmo Exato de Avaliação de uma Política Estacionária para CVaR MDP

  • Denis Pais Universidade de São Paulo
  • Valdinei Freire Escola de Artes Ciências e Humanidades
  • Karina Valdivia-Delgado University of São Paulo

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.

Palavras-chave: MPD, Risco, CVaR, Decisão Sequencial

Referências

Bellman, R. E. (1957). Dynamic programming. Princeton University Press.

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.

Bellman, R. E. (1957). Dynamic programming. Princeton University Press.

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.
Publicado
15/10/2019
Como Citar

Selecione um Formato
PAIS, Denis; FREIRE, Valdinei; VALDIVIA-DELGADO, Karina. Algoritmo Exato de Avaliação de uma Política Estacionária para CVaR MDP. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 16. , 2019, Salvador. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2019 . p. 868-879. DOI: https://doi.org/10.5753/eniac.2019.9341.