Programowanie dynamiczne: iteracja wartości i polityki

Dynamic programming for MDPs (value and policy iteration) · id dynamicprogramming · aliases: dynamic programming, value iteration, policy iteration, iteracja wartości, iteracja polityki

Obliczanie optymalnej polityki, gdy model przejść i nagród jest w pełni znany, przez wielokrotne stosowanie równań Bellmana. Punkt odniesienia dla metod uczących się z prób.

Computing an optimal policy when the transition and reward model is fully known, by repeatedly applying the Bellman equations. The reference point for methods that learn from trials.

In one sentence

To liczenie najlepszego sposobu działania, gdy dokładnie znasz reguły świata i skutki każdego ruchu.

This computes the best way to act when you know the world's rules and the result of every move exactly.

Problem it solves

Masz pełny opis zadania, ale sprawdzanie wszystkich możliwych planów po kolei trwałoby wieki.

You have a complete description of the task, but checking every possible plan one by one would take forever.

What it does

Jak liczenie drogi od mety wstecz: każde pole dostaje ocenę z ocen sąsiadów, aż oceny przestaną się zmieniać.

Like working backwards from the finish line: each square gets a score from its neighbours' scores until the scores stop changing.

Everyday example

Robot sprzątający zna plan mieszkania i dla każdego pokoju wylicza, którędy najszybciej dojedzie do stacji ładowania.

A cleaning robot knows the flat's floor plan and works out, for every room, the quickest way back to its charging dock.

This concerns you if you…

Examples

Sources