х 1 (a 0 (x 0 ))... Px n-1 x n (a n-1 (x 0 , x 1 ,..., x n-1 ))
Пусть: 
где функция f (d, х ) ³ 0 и f (d, 0) = 0 (если точка {0} является поглощающим состоянием и f (d, x ) = I, d Î D, x = 1,..., N, то V a (x ) есть матем. ожидание времени попадания из точки х в точку 0). Функцию
называется ценой, а стратегию а * – оптимальной, если 
= V (x ) для всех х Î Е.
При довольно общих предположениях о множестве D устанавливается, что цена V (x ) удовлетворяет следующему уравнению оптимальности (уравнению Беллмана):
,
где
.
В классе всех стратегий наибольший интерес представляют т. н. однородные марковские стратегии, характеризуемые одной функцией а (х ) такой, что a n (x 0 ,..., x n ) = a (x n ) при всех n = 0, 1,...
Следовательно, критерий оптимальности (или достаточное условие оптимальности) может быть использован для проверки того, что данная однородная марковская стратегия является оптимальной: пусть существуют функции a * = а* (х ) и V* = V* (x ) такие, что для любого d Î D
0 = f (x, a* (x )) + L a *V* £ f (x, d ) + L d V* (x
