Ny algoritm löser beslutsoptimering under osäkerhet i polynomisk tid

arXiv cs.AI

Forskare har tagit fram en algoritm som i polynomisk tid (det vill säga effektivt skalbar beräkning) löser kvantitativa problem i så kallade robusta Markov-beslutsprocesser – en modell för att fatta optimala beslut när omgivningens beteende är okänt. Det intressanta är att de bevisar att både agent och motståndare alltid kan nöja sig med enkla, minneslösa strategier, vilket förenklar problemet avsevärt. Resultaten jämförs experimentellt med befintliga metoder baserade på stokastiska spel.