Amostragem Posterior Otimista para Aprendizado por Reforço: Limites de Arrependimento no Pior Caso

Apresentamos um algoritmo baseado em amostragem posterior (também conhecido como amostragem de Thompson) que alcança limites de arrependimento no pior caso quase ótimos quando o processo de decisão de Markov (MDP) subjacente está se comunicando com um diâmetro finito, embora desconhecido. Nosso resultado principal é um limite superior de arrependimento com alta probabilidade da Fórmula: veja o texto para qualquer MDP comunicante com S estados, A ações e diâmetro D. Aqui, o arrependimento compara a recompensa total alcançada pelo algoritmo com a recompensa esperada total de uma política ótima de recompensa média não descontada em horizonte infinito no horizonte de tempo T. Este resultado corresponde de perto ao limite inferior conhecido da Fórmula: veja o texto. Nossas técnicas envolvem a prova de alguns resultados novos sobre a anticoncentração da distribuição de Dirichlet, que pode ser de interesse independente. Financiamento: Este trabalho foi apoiado em parte por um prêmio CAREER da NSF CMMI 1846792 concedido ao autor S. Agrawal.