Reinforcement learning for stochastic shortest path with dead-ends (2025)
- Authors:
- Autor USP: PEREIRA, GUSTAVO DE MARI - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2025.tde-31082025-142940
- Subjects: APRENDIZADO COMPUTACIONAL; PROBABILIDADE; PROCESSOS ESTOCÁSTICOS
- Keywords: Aprendizado de máquina; Aprendizado por reforço; Becos sem saída; Caminho mais curto estocástico; Dead-ends; Goals; Machine learning; Meta; Planejamento probabilístico; Probabilistic planning; Reinforcement learning; Sequential decision making; Stochastic shortest path; Tomada de decisão sequencial
- Agências de fomento:
- Language: Inglês
- Abstract: Problemas em Aprendizado por Reforço (AR) são frequentemente modelados usando Processos de Decisão de Markov de Horizonte Infinito Descontado (do inglês, Infinite Horizon Discounted Markov Decision Processes - IHD-MDPs). No entanto, a comunidade de Planejamento Probabilístico argumenta que problemas de Caminho Mais Curto Estocástico (do inglês, Stochastic Shortest Path - SSP) oferecem uma estrutura mais natural para tarefas orientadas a meta. Em particular, ao lidar com SSPs envolvendo becos-sem-saída (estados a partir dos quais o agente não pode mais alcançar a meta), MDPs descontados requerem o ajuste cuidadoso do fator de desconto e nem sempre é possível encontrar soluções de interesse. Com base nos resultados de pesquisas em Planejamento Probabilístico, neste trabalho, propomos modificações em algoritmos clássicos de AR, como o algoritmo Q-learning, para resolver três classes de SSPs: (i) SSPs sem becos-sem-saída, (ii) SSPs com becos-sem-saída evitáveis e (iii) SSPs com becos-sem-saída inevitáveis. Com essas modificações, é possível aplicar algoritmos de AR em uma ampla gama de problemas de tomada de decisão sequencial orientados a meta
- Imprenta:
- Data da defesa: 03.07.2025
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
ABNT
PEREIRA, Gustavo de Mari. Reinforcement learning for stochastic shortest path with dead-ends. 2025. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2025. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-31082025-142940/. Acesso em: 07 abr. 2026. -
APA
Pereira, G. de M. (2025). Reinforcement learning for stochastic shortest path with dead-ends (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-31082025-142940/ -
NLM
Pereira G de M. Reinforcement learning for stochastic shortest path with dead-ends [Internet]. 2025 ;[citado 2026 abr. 07 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-31082025-142940/ -
Vancouver
Pereira G de M. Reinforcement learning for stochastic shortest path with dead-ends [Internet]. 2025 ;[citado 2026 abr. 07 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-31082025-142940/
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
