最大スコアを持つシーケンス？

Question

私は、n状態S = {s1、s2、s3、... sn}を持ち、すべての遷移、すなわちT行列f.e. s1→s5 = 0.3、s4→s3 = 0.7、...等となる。

state-x（s_x）から始まるスコアリングされたシーケンス/パスを選択するために使用するアルゴリズムまたはプロシージャは何ですか？

つの質問：無限に長いパスで、私は平均的に可能な状態として最高として選ぶように

1. は、最高の次の状態を選びますか？
2. パス長Lを指定すると、最高スコアを生成する状態のシーケンスを選択しますか？

私は現在、強化学習を研究していますが、アクションやポリシーはないので、過剰なようです。私はバリュー関数のような何かを使うことができますか？

何を使用しますか？

PS>シナリオの中には、T行列が時間とともに変化するものがあります。

---

http://mnemstudio.org/path-finding-q-learning-tutorial.htm

Q-学習は良い賭けであると思われます。私が見る唯一の違いは、時間の経過とともにQ値を保存する場合、T行列の変更に対応する方法を考えなければならないということです。

もう一つの難しいのは、最終的な目標はなく、仲介点の変更だけです。私はアルゴリズムを変更する必要はないかもしれませんが、それは単に変化するスコアに向かって収束することになります。これは大丈夫です。

私の最初の考えは、Lステップの最善のパス（つまり、毎回Qをゼロから再計算する）を実行するたびに行われましたが、もしできれば、着信データに応じてQテーブルを変更したくなります。

Answer 1

あなたのオプション1は、欲望というと呼ばれます。これは、一般に、すぐに「ベスト」オプションを選択する方法を指しています。その問題は、欲張りの選択が将来、最適な選択肢を制限する可能性があることです。

パスの長さに制限を設定しない場合、明らかに最大スコアは無限になります。

ここで、問題は次のとおりです。与えられたパスの長さにはどのような順序が最適ですか？これは、動的プログラミングのようなもので多項式時間に解くことができます。

再帰的なの式は、次のようになります。状態xから始まる長さLの最良パスを求めるには、他のすべての状態yを見てください。これらのそれぞれについて、T_xy +「状態yから始まる長さL-1の最良経路」を計算する。

明らかに、ある状態xから始まる長さ1の最適経路は「次善状態」になるので、再帰は簡単な基本ケースを持つ。