Por que uma única estratégia não basta: portfólios adaptativos de políticas para MDPs robustos
Processos de decisão de Markov (MDPs) clássicos assumem que a dinâmica do ambiente é conhecida com precisão. Na prática, isso quase nunca é verdade: só podemos delinear um conjunto de cenários plausíveis. MDPs robustos (robust MDP) abordam isso de forma radical — buscam uma única política que funcione bem o suficiente sob a pior das transições possíveis. Mas essa abordagem tem um custo oculto: ela é ajustada para o pior caso e, por isso, muitas vezes acaba sendo excessivamente conservadora.
Isso fica especialmente evidente em situações em que a incerteza diminui com o tempo. O ambiente se desenrola diante do agente, e parte de sua dinâmica se torna observável e parcialmente identificável. A política ótima, calculada antes do desenrolar, não utiliza essa nova informação. Em essência, continuamos jogando contra o pior caso mesmo onde já sabemos que ele não se concretizou. Pesquisadores da Universidade de Twente e de Antuérpia — Kasper Engelen, Sebastian Junges, Guillermo A. Pérez e Marnix Suilen — em seu trabalho «Adaptive Policy Portfolios for Robust Markov Decision Processes» (arXiv:2608.17929, cs.AI/cs.LO) propõem uma abordagem mais flexível.
Portfólios adaptativos: um conjunto de políticas em vez de uma única
Em vez de uma única política robusta, os autores consideram um portfólio de políticas — um conjunto finito de políticas randomizadas sem memória, sintetizadas antecipadamente, offline. Além delas, utiliza-se um seletor online leve, que durante a execução escolhe a política mais adequada do portfólio. Isso lembra um ensemble de modelos em aprendizado de máquina, mas com uma formulação teórica clara.
A métrica-chave de qualidade desse portfólio é o arrependimento robusto (robust regret). Para cada ambiente específico dentro do conjunto de cenários plausíveis, ele mede o quanto a política escolhida pelo seletor online fica aquém daquela política ideal que construiríamos se conhecêssemos esse ambiente antecipadamente. Em outras palavras, o portfólio é considerado bom se seu melhor membro está suficientemente próximo do ótimo para qualquer ambiente. Essa visão desloca o foco das garantias de pior caso para o preço da adaptação.
Ideias semelhantes foram desenvolvidas anteriormente por Ghavamzadeh et al. (2016), mas com foco em métodos aproximados e relaxações para melhoria segura de políticas. O novo trabalho avança significativamente os fundamentos teóricos dessa área.
Complexidade de certificação e síntese
O portfólio não é apenas uma heurística de engenharia. Os autores fornecem uma análise teórico-complexidade cuidadosa dos problemas que surgem ao trabalhar com portfólios.
O primeiro problema é a certificação de um portfólio dado: é possível garantir que, para todos os ambientes plausíveis, exista uma política com arrependimento aceitável? Acontece que esse problema é ∀R-completo já para portfólios determinísticos em RMDPs acíclicos (s,a)-retangulares. Isso significa que verificar a qualidade mesmo de um pequeno conjunto de políticas é uma tarefa computacionalmente pesada, comparável em complexidade à resolução de sistemas de desigualdades reais.
Ainda mais difícil é o problema de síntese de um portfólio de tamanho limitado (unary-bounded). Para politopos racionais gerais, ele se mostra ∃∀R-completo — mesmo com coeficiente de desconto fixo e dinâmica acíclica. Essa complexidade indica que não existem algoritmos combinatórios simples aqui: o problema combina tanto busca discreta quanto complexidade algébrica. Notavelmente, até o caso de uma única política é não trivial e "caro" em ambos os eixos.
Como aproximar isso da prática?
Os resultados de complexidade obtidos podem assustar, mas os autores não param nas conclusões negativas. Eles propõem uma construção offline concreta de portfólio que permite especialização em tempo de execução (runtime specialization). A ideia é preparar antecipadamente um conjunto de políticas e, já durante a interação com o ambiente, ajustar rapidamente a escolha conforme a observação atual. Essa abordagem permite combinar garantias rigorosas com flexibilidade prática.
A conclusão é simples: em tarefas em que a incerteza é parcialmente revelada com o tempo, uma única estratégia fixa é comprovadamente mais fraca do que um conjunto adaptativo. O portfólio de políticas paga com maior complexidade computacional, mas em troca oferece margem para erro e capacidade de alternar à medida que os dados chegam. É um passo importante no caminho de métodos puramente conservadores para sistemas inteligentes de tomada de decisão sob incerteza.
