Overviewの最後に動的計画法と強化学習の手法（価値反復，方策反復）の関連性が示唆されているが（動的計画法のアルゴリズムを、遷移確率に関する情報がないのでサンプルから学習させるものという形で理解できる）本書だけでは動的計画法に関する記述が短いので理解するのが難しいので、下記資料をザッと眺めると良いかもしれない。
Bertsekas and Tsitsklis (1996)には average cost per stage problem についての記述がある。
割引報酬和（or コストの和）の期待値を指標として最適化するのとは別の指標（基準）を用いた問題。
具体的には割引報酬和の期待値のときには
- 1より小さいの割引率を使う。
- 吸収状態がありそれ以降報酬（コスト）が与えられない。
のいずれかによって値が有限であることが保証されているが、適切な吸収状態がなかったり、割引をするのが適切でない問題もある。 そのため、各状態におけるコストの平均（の期待値）を指標とした問題が平均コスト問題である。
この本ではたびたび適応サンプリングという言葉が登場するが、具体的な説明はないが、 下記のThompsonによるスライドは分かりやすい。 どの値をサンプリングするかを、過去のサンプリングの履歴に依存する形で依存して決定するアプローチ全体を指すという理解。 探索と活用のトレードオフを考えるアルゴリズムはこの枠組に入ると思われる。
- Thompson (2011) Adaptive sampling
情報源の発生情報量を見積もるためには、背後にある情報を生成する確率モデルを推定する必要があり、どのようにデータが生成されているかの一つの仮定としてMDPが使われる。
- マルコフ情報源とかで検索すると沢山関連資料がでてくる
- 強化学習による定式化をした日本語での関連資料: 強化学習における収益の情報源符号化とその行動選択への応用
ある基地局から別の基地局まで、他の基地局を経由しながら情報を適切に（短い距離で、失敗せずなど）送るためには動的計画法のような問題を解く必要がある、という理解。
- 関連がありそうなサーベイ: Alsheikh et al. (2015) Markov Decision Processes with Applications in Wireless Sensor Networks: A Survey
下記リンクでは、実際にギャンブラーが毎回の賭けに勝つ確率を既知（つまりモデルが既知）とした上で動的計画法（価値反復）によって最適方策を求めている。