§ 14.3. Марковские процессы решения с бесконечным числом шагов

В задачах, где нет естественного последнего шага, часто является уместным следующее построение марковского процесса решения с бесконечным числом шагов. Пространство состояний , пространство альтернатив А, функция выигрыша и переходная функция определяются так же, как и раньше. Фиксируем число , которое будет служить множителем, уменьшающим ценность будущих выигрышей по сравнению с настоящим. Предположим, что процесс начинается из некоторого данного состояния и продолжается неограниченно долго. На шаге статистик наблюдает состояние процесса, выбирает альтернативу и получает выигрыш после чего

процесс переходит в новое состояние согласно о. в.

Задача статистика состоит в определении бесконечной последовательности альтернатив максимизирующей среднее значение общего выигрыша, который с учетом уменьшения ценности будущих выигрышей имеет вид

Средний общий выигрыш составляется с учетом множителя уменьшающего ценность будущих выигрышей. На любом шаге процесса статистик считает единичный выигрыш после следующих шагов эквивалентным выигрышу на настоящем шаге. Такие множители часто используются в задачах экономического планирования и капиталовложений. Процесс с бесконечным числом шагов и уменьшающимися выигрышами обладает следующими двумя важными свойствами.

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

Второе важное свойство заключается в том, что задача решения статистика является стационарной во времени в следующем смысле. Пусть на шаге процесс находится в состоянии Поскольку выигрыши, полученные на предыдущих шагах, от нулевого до не влияют на будущие решения, то теперь статистик должен максимизировать средний общий выигрыш от оставшейся части процесса. Этот будущий выигрыш имеет вид

В нашем процессе переходная функция не меняется от шага к шагу. Следовательно, с точностью до множителя на шаге средний общий выигрыш (2) от оставшейся части процесса равен среднему общему выигрышу (1) от всего процесса, если рассматривать как начальное состояние. Поэтому на каждом шаге задача решения совпадает с исходной, но при другом начальном состоянии.

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

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

Пусть средний общий выигрыш оптимальной процедуры, в случае когда начальное состояние процесса есть Тогда этот выигрыш должен при всех удовлетворять следующему уравнению:

Предположим, что функция V ограничена на Следующие две теоремы, полученные Штраухом (1966) и Прескоттом (1967), показывают, что У является единственным ограниченным решением уравнения (3) и с помощью метода последовательных приближений можно получить последовательность функций, равномерно сходящуюся к

Теорема 1. Для любого заданного значения найдется не более одной ограниченной функции удовлетворяющей уравнению (3).

Доказательство. Предположим, что и две ограниченные функции, удовлетворяющие уравнению (3), и Тогда для Поэтому при всех состояниях

Аналогично для Поэтому . В силу определения числа отсюда следует, что т. е. для всех

Теорема 2. Пусть произвольная ограниченная функция на множестве Определим последовательность функций следующим рекуррентным соотношением:

Если функция V ограничена и удовлетворяет уравнению (3), то равномерно по всем

Доказательство. Так как функции и V ограничены, то найдется число для которого при всех Поэтому при всех

Аналогично Поэтому для всех состояний Повторяя эти рассуждения, видим, что при откуда и следует равномерная сходимость в (6).

Дальнейшие замечания и ссылки на литературу. Большое количество задач различной степени общности по тематике марковских процессов решения рассмотрено в книгах Беллмана (1957а, 1961), Ховарда (1960) и Мартина (1967). См. также: Карлин (1955а), Блекуэлл (1961, 1962, 1964, 1965, 1967), Майтра (1965, 1966), Штраух (1966), Дермэн (1962, 1963, 1964, 1966), Дермэн и Вейнотт (1967), Л. Фишер (1968), Росс (1968), Фишер и Росс (1968) и Маккин (1966).

Укажем еще ряд работ, которые посвящены главным образом приложениям к эконометрике и управлению производством, но представляют и значительный общий интерес: Эрроу (1962, 1964), Маршак (1963а), Маккин (1964а).

К другому классу задач последовательного решения относятся так называемые составные задачи решения и эмпирические байесовские процедуры, которые систематически впервые были изучены Роббинсом. Вот некоторые работы из этой области: Роббинс (1956b, 1964), Хеннан (1957), Хеннан и Роббинс (1955), Хеннан и Ван Рызин (1965), Джонс (1957, 1961), Сэмюэл (1963а, b; 1964; 1965а,b), Ван Рызин (1966а, b).