Прикладная математика
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

Оптимальные стратегии в марковских цепях

Для задания марковской цепи с вознаграждениями матрицу вознаграждений брали в сочетании с матрицей вероятностей переходов . Было показано, как вычисляются векторы , элементы которых описывают ожидаемое вознаграждение, выдаваемое системой за периодов, как функцию исходного состояния системы. Вплоть до этого момента в рассмотрение не включались никакие решения; модель просто описывала систему, которая не предоставляла никаких альтернатив. Предположим, что введены некоторые альтернативные решения, касающиеся поведения системы. В примере с компьютером рассмотрим правило, определяющее некоторое решение: всегда ремонтируйте машину, если она этого требует. Если в качестве матрицы вознаграждений по-прежнему взять матрицу, приведенную ранее, и если стоимость ремонта машины равна 0,90 ден. ед., то важно ответить на такой вопрос: этому ли правилу нужно следовать или целесообразнее предпочесть правило «ничего не делать» (напомним, что с вероятностью 0,6 машина регулируется сама).

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

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

(производится максимизация по множеству возможных решений).

В матричных обозначениях:

, (13)

где проводятся независимых максимизаций в уравнении (13) по одной для каждого из элементов , то есть по одной для каждого из возможных начальных состояний.

Решение проблемы выбора решений происходит следующим образом. Вначале решают все уравнения (13) при , находя для каждого начального состояния оптимальное решение, то есть то значение , которое максимизирует правую часть соответствующего из уравнений (13). Обозначим, вектор оптимальных решений для случая, когда должны пройти периодов:

.

Тогда есть оптимальное решение для случая, когда система находится в состоянии и должно пройти периодов. Решение уравнений (13) получается непосредственно, поскольку , и уравнения преобразуются к виду:

. (14)

Как только уравнения (13) решены для каждого элемента , оптимальные решения записываются в виде вектора , где –й элемент есть целое число в диапазоне от 1 до , которое максимизирует ожидаемое вознаграждение за один период при условии, что система начинает с состояния . Затем уравнения (13) решают при , записывая оптимальные решения и вектор . Далее переходят к и так далее до тех пор, пока не будет достигнуто желаемое число периодов. Затем рассматривают множество векторов оптимальных решений , задающее оптимальную стратегию. Оптимальная стратегия используется следующим образом: если должно пройти периодов и система находится в состоянии , то применяют решение . Затем после перехода система попадает в некоторое новое состояние . Теперь остался период, и оптимальное решение есть . Подобным образом векторы оптимальных решений позволяют нам принимать оптимальные решения безотносительно к тому, в какие состояния переходит система; для случая, когда система начинает с состояния , максимальное ожидаемое вознаграждение за периодов задается величиной .

Добавить комментарий


Защитный код
Обновить

По темам:

Google