Выше было указано, что процедура итерации по значениям в конечном итоге сходится к уникальному множеству решений уравнений Беллмана. В этом разделе показано, почему это происходит. В ходе этого будут представлены некоторые полезные математические идеи и получены определенные методы оценки ошибки в значении функции полезности, возвращаемом при преждевременном завершении работы алгоритма; это важно, поскольку означает, что количество применяемых итераций алгоритма не обязательно должно стремиться к бесконечности. Изложение в этом разделе является весьма формальным.

Основным понятием, используемым при доказательстве того, что процедура итерации по значениям сходится, является сжатие. Грубо говоря, функция сжатия — это функция от одного параметра, которая после ее последовательного применения к двум различным входным значениям вырабатывает два выходных значения, которые "ближе друг к другу" по меньшей мере на некоторую постоянную величину, чем первоначальные фактические параметры. Например, функция "деления на два" представляет собой функцию сжатия, поскольку после деления двух чисел на два разница между ними уменьшается наполовину. Обратите внимание на то, что функция "деления на два" имеет фиксированную точку, а именно нуль, которая остается неизменной в результате применения этой функции. На основании данного примера можно установить два важных свойства функций сжатия, описанных ниже.

•    Функция сжатия имеет только одну фиксированную точку; если бы были две фиксированные точки, они бы не приближались друг к другу после применения функции, поэтому такая функция не соответствовала бы определению функции сжатия.

•    После применения функции к любому параметру полученное значение должно стать ближе к фиксированной точке (поскольку фиксированная точка не движется), поэтому в пределе повторное применение функции сжатия всегда приводит к достижению фиксированной точки.

Теперь предположим, что обновление Беллмана (уравнение 17.6) рассматривается как оператор В, который используется для одновременного обновления значений полезности каждого состояния. Обозначим черезвектор полезностей для всех состояний в i-й итерации. В таком случае уравнение обновления Беллмана может быть записано следующим образом:

Затем нужно найти способ измерения расстояний между векторами полезностей. Мы будем использовать нормализованный максимум, который измеряет длину вектора по длине его максимального компонента, следующим образом: