価値反復は、強化学習や動的計画法において、マルコフ決定過程（MDP）における最適な状態価値関数および最適方策を算出するための基本的なアルゴリズムです。環境の遷移確率や報酬関数といったモデルが既知である場合に、ベルマン最適方程式に基づく更新式を反復計算することで、各状態における期待報酬の最大値を収束させて求めます。
価値反復とは
価値反復とは、環境のモデル（状態遷移確率や報酬）があらかじめ分かっている状態で、各状態の価値を反復計算によって更新し、最終的に最適方策（最適な行動計画）を求める動的計画法のアルゴリズムです。
詳しく解説
価値反復は、強化学習の基礎となるマルコフ決定過程（MDP）を解決するための手法の一つです。この手法では、各状態における将来得られる累積報酬の期待値を表す「状態価値関数」を管理します。初期状態からスタートし、ベルマン最適方程式を利用して価値関数を繰り返し更新します。具体的には、すべての状態で可能な行動の中から得られる最大の価値を選択して更新を行い、価値関数の変化が一定の閾値以下になるまで処理を反復します。価値関数が最適値に収束した後に、各状態で最も価値が高くなる行動を選択することで、最適方策が得られます。このアプローチにより、明示的に方策を繰り返し改善・評価することなく、価値の計算だけに集中して解を導出できる点が特徴です。
具体例・使われ方
価値反復の具体的なイメージとして、迷路を解くロボットの制御が挙げられます。迷路全体の構造（どのマスからどのマスへ移動できるかという確率や、ゴールに到達した際の報酬）があらかじめ完璧に分かっている場合、各マス（状態）の価値をあらかじめ価値反復によって計算しておきます。計算完了後、ロボットは自分のいるマスから最も価値の高い隣接マスへ移動し続けるだけで、最短経路でゴールを目指すことができます。
似た用語との違い
価値反復と混同されやすい概念に「方策反復」があります。どちらも動的計画法を用いてマルコフ決定過程を解く手法ですが、更新手順が異なります。方策反復では「方策評価」と「方策改善」という2つのステップを交互に繰り返して最適な行動計画を直接改善していきます。一方、価値反復では価値関数の更新時に常に最大の期待価値を選択することで、方策の明示的な評価ステップを省略し、価値関数が完全に収束した段階で初めて最適方策を抽出します。
注意点
価値反復を適用するには、環境の遷移確率や報酬構造が事前に完全に判明している必要があります。そのため、環境のモデルが未知である現実世界の複雑な課題には直接適用できません。また、状態数や行動数が非常に多い「次元の呪い」に直面した場合、すべての状態に対して反復計算を行うため、計算量が爆発的に増加して実行が困難になるという限界があります。