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

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

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