[Narrator] So even for the simple grid world,
the optimal control policy assuming stochastic actions
and no costs of moving, except for the final absorbing costs,
is somewhat nontrivial.
Take a second to look at this.
Along here it seems pretty obvious, but
for the state over here, B3, and for the state over here, C4,
we choose an action that just avoids falling into the minus 100,
which is more important than trying to make progress towards the plus 100.
Now obviously this is not the general case of an MDP,
and it's somewhat frustrating they'd be willing to run through the wall,
just so as to avoid falling into the minus 100,
and the reason why this seems unintuitive is
because we're really forgetting the issue of costs.
In normal life, there is a cost associated with moving.
MDPs are gentle enough to have a cost factor,
and the way we're going to denote costs
is by defining our award function over any possible state.
We are reaching the state A4,
gives us plus 100, minus 100 for B4,
and perhaps minus 3 for every other state,
which reflects the fact that if you take a step somewhere
that we will pay minus 3.
So this gives an incentive to shorten the final action sequence.
So we're now ready to state the actual objective
of an MDP which is to minimize not
just the momentary costs, but the sum
of all future rewards,
but you're going to write RT to denote the fact that
this reward has received time T, and because
our reward itself is stochastic,
we have to complete the expectation over those,
and that we seek to maximize.
So we seek to find the policy that maximizes the expression over here.
Now another interesting caveat is a sentence people put
a so called discount factor into this equation
with an exponent of T, where a discount factor was going to be 0.9,
and what this does is it decays future reward
relative to more immediate rewards, and it's
kind of an alternative way to specify costs.
So we can make this explicit by a negative reward per state
or we can bring in a discount factor
that discounts the plus 100 by the
number of steps that it went by before it reached the plus 100.
This also gives an incentive to get to the goal as fast as possible.
The nice mathematical thing about discount factor is
it keeps this expectation bounded.
It easy to show that this expression over here
will always be smaller or equal to 1 over 1 minus gamma times the
absolute reward maximizing value and
which in this case would be plus 100.
単純なグリッドワールドでも
確率論な行為を仮定すると
吸収状態以外のコストがなくても
最適なポリシーは自明ではありません
詳しく見てみましょう
この辺りは明らかですが
このb3とc4の状態については
-100を避けるために行為を選んでいます
このことは+100へ進むことよりも重要です
これは明らかにマルコフ決定過程では
標準的ではありませんし
単に-100を避けるために壁に向かって
移動しようとするのは違和感があります
このように非直感的な結果となってしまう理由は
移動コストを考慮していないからです
日常生活では移動コストがかかります
マルコフ決定過程はコストを考慮し
報酬関数をすべての状態に対して設定することで
コストを表現できます
もしa4に行けば+100でb4に行けば-100です
他の状態には-3を割り当ててみましょう
これは他の状態に行くと
3のコストが必要であることを表しています
これは短い手順で吸収状態へ行く
インセンティブとなります
MDPの真の目的関数を定める準備ができました
単にある瞬間のコストではなく将来的な
すべての報酬の総和を最大化する関数です
これをRtと表記し時刻tに受け取る報酬を示します
この報酬は確率論的なので期待値を取る必要があり
これが私たちが最大化すべき関数となります
この式を最大化するポリシーを
見つけるのが問題です
もう1つ興味深い変形として
この式に割引率を加えることがあります
ここに割引率のt乗 例えば0.9を入れ
これによって未来の報酬を割引します
直近の報酬を重視するようにし
コストを定める方法もあります
他の状態に
マイナスの報酬を割り当てる方法もあります
他にも割引率を導入することで
+100からステップ数を引く方法もあります
これもまた早く吸収状態へ行く
インセンティブとなります
数学的に良い性質としてこの割引率によって
この期待値は上界を持つということがあります
この割引された期待値は
1/(1-γ)×|Rmax|です
この場合割引されない期待値は100です