Unit 9 19 Value Iteration 3 knowitvideos English Japanese

Unit 9 19 Value Iteration 3YouTube↗ IA↗(long shot)
Howto & Style 48.2K views 89 likes 90 dislikes 01 Nov 2011

knowitvideos 11.8K subscribers N/A YouTube↗

Click to Play Video

Let me tell you about a truly magical algorithm called value iteration.

価値反復法と呼ばれる魔法のようなアルゴリズムについて説明します

In value iteration, we recursively calculate the value function

価値反復法では価値関数の値を再帰的に計算し

so that in the end, we get what's called the optimal value function.

終了時に最適価値関数が得られるようにします

And from that, we can derive, look up, the optimal policy.

これを見ると最適なポリシーが得られます

Here's how it goes.

動きを説明しましょう

Suppose we start with a value function of 0 everywhere

吸収状態以外の価値関数の値が 0の状態から始めます

except for the 2 absorbing states, whose value is +100 and -100.

吸収状態はそれぞれ＋100と－100です

Then we can ask ourselves the question is, for example,

例えばa3について現在の価値関数0が

for the field A3, 0 a good value.

真の評価値に近いかどうかを検討します

And the answer is no, it isn't. It is somewhat inconsistent.

答えはノーです

We can compute a better value.

よりよい評価値を計算できます

In particular, we can understand that if we're in A3 and we choose to go east,

具体的にはもしa3にいて東に行く行為をするなら

then with 0.8 chance we should expect a value of 100.

0．8の確率で100の値が期待できます

With 0.1 chance, we'll stay in the same state, in which case the value is -3.

そしてその場にとどまる確率が0．1で下に行く確率が0．1になります

And with 0.1 chance, we're going to stay down here for -3.

それぞれ－3の報酬です

With the appropriate definition of value, we would get the following formula, which is 77.

適切な値の定義に従い次の式を立てると77という値が得られます

So, 77 is a better estimate of value for the state over here.

77はこの状態に対する価値の推定としてより適切な値です

And now that we've done it, we can ask ourselves the question

このマスはこれで終わりです

is this a good value, or this a good value, or this a good value?

次は他のマスに対してもこの評価値が適切かどうかを見ます

And we can propagate value backwards in reverse order of action execution from the positive absorbing state through this grid world

これによって価値を正の吸収状態から逆方向に伝播させてこのグリッド全体に広げていき

and fill every single state with a better value estimate then the one we assumed initially.

すべての状態について評価値を適切な値に更新していきます

If we do this for the grid over here and run value iteration

これをグリッド全体について繰り返し収束するまで行うと

through convergence, then we get the following value function.

次のような価値関数を得られます

We get 93 over here. We're very close to the goal.

目標に極めて近いので93になっています

89, 85, 81, 77, 73, 70, over here.

他はそれぞれ89、85、81、77、73、70です

This state will be worth 68, and this state is worth 47,

ここは68でこちらは47です

and the reason why these are not so good is because

これらが低い価直となったのは

we might stay quite a while in those before we'll be able to execute an action that gets us outside the state.

このマスを脱出するまでに長くかかるからです

Let me give you an algorithm that defines value iteration.

価直反復法のアルゴリズムを説明します

We wish to estimate recursively the value of state S.

目的は状態sの価値を再帰的に推定することです

And we do this based on a possible successor state

これをあり得る後続状態s´として

as prime that we look up in the existing table.

現在の価値関数のテーブルから参照します

Now, actions A are non-deterministic. Therefore, we have to go through all possible as primes

行為aは非決定的ですのですべての可能性をs´として検討する必要があり

and weigh each outcome with the associated probability.

実現確率によって重みづけされます

The probability of reaching S prime given that we started state S and apply action A.

sから始めて行為aでs´に到達する確率を用いましょう

This expression is usually discounted by gamma,

この式は割引率γで割り引かれ

and we also add the reward or the costs of the state.

現在の状態の報酬もここに加わります

And because there's multiple actions and it's up to us

行為の候補は複数あり正しい行為を選ぶのは私たちですので

to choose the right action, we will maximize over all possible actions.

可能な行為に対する最大のものを選ぶようにしましょう

See, we look at this equation, and it looks really complicated, but it's actually really simple.

この式を見るととても複雑なように見えますが実は非常に単純です

We compute a value recursively based on successor values plus the reward and minus the cost that it takes us to get us there.

後続状態の価値とこの状態での報酬を足して再帰的に価値を計算しているだけです

Because Mother Nature picks a successor state for us for any given action,

大いなる自然が私たちの選んだ行為に対して後続状態を選びます

if you compute an expectation over the value of the successor state weighted by the corresponding probabilities which is happening over here,

後続状態については対応する確率で重みづけして期待値を求め

and because we can choose our action,

行為は私たち自身が選ぶので

we maximize over all possible actions.

行為に対しては最大となるものを選びました

Therefore, the max as opposed to the expectation on the left side over here.

ですのでここに示すようにmaxを取ったのです

This is an equation that's called backup.

これは“バックアップ”と呼ばれる式です

In terminal states, we just assign R(s),

吸収状態では単にその状態の報酬を割り当てます

and obviously, in the beginning of value iteration,

明らかに価直反復の開始時には等式は成立しないので

these expressions are different, and we have to update.

更新する必要があります

But as Bellman has shown a while ago,

しかし昔ベルマンが証明したように

this process of updates converges.

この更新手続きは収束します

After convergence, this assignment over here is replaced by the equality sign,

収束後この代入記号は等号に書き換えることができます

and when this equality holds true,

そしてこの等式が成り立っている時

we have what is called a Bellman equality or Bellman equation.

これを“ベルマン方程式”と呼びます

And that's all there is to know to compute values.

以上が価値の計算に必要な事項です

If you assign this specific equation over and over again to each state,

この等式による代入をそれぞれの状態に何回も行えば

eventually you get a value function that looks just like this,

いずれこのような価値関数を得ることができます

where the value really corresponds to what's the optimal future cost reward trade off that you can achieve

価値は最適な行為によって将来達成できるの報酬と費用のトレードオフと

if you act optimally in any given state over here.

密接な関係があるのです

Similar videos:

0 views 0 likes 0 dislikes 07 Jun 2026100% match

Gundarr (Ep 18): Pistol Passing (subtitulado al castellano)
daniborr
14.7K views 63 likes 2 dislikes 10 Aug 2012100% match

Unit 3 9c Answer

11.4K views 20 likes 9 dislikes 08 Oct 2011100% match

Shift Happens 6.0
ctumini
21.6K views 38 likes 8 dislikes 31 Jul 2012100% match

Unit 2, Topic 29, State Spaces

16.9K views 4 likes 1 dislikes 05 Oct 2011100% match

Unit 9 18 Value Iteration 2

13.4K views 16 likes 1 dislikes 01 Nov 2011100% match

OSHO: Aastik Kaun - आस्तिक कौन?
OSHO Hindi
106.1K views 1.1K likes 48 dislikes 22 Jul 2010100% match

CEOS Chatter
Fernando Garcia
1.3K views 2 likes 1 dislikes 14 Mar 2012100% match

Unit 2, Topic 30, State Space Diagram and More Complexity ANSWER

12.6K views 16 likes 3 dislikes 05 Oct 2011100% match

Mr. Peabody & Sherman
TheCaptionedInternet
43.6K views 74 likes 9 dislikes 03 Mar 2014100% match

Instrucciones para llorar, de Julio Cortázar
Inés Andrés
5.9K views 10 likes 0 dislikes 10 Jan 2012100% match

Unit 11 24.mp4 Particle Filters.mp4

21.5K views 94 likes 1 dislikes 11 Nov 2011100% match

Unit 3 8 More Complex Bayes Networks

13K views 26 likes 3 dislikes 08 Oct 2011100% match

محمد باسندوه و توكل كرمان في حوار خاص و هام جدا
عين اليمن
22.6K views 43 likes 13 dislikes 12 May 2012100% match

Unit 2, Topic 9, More Graph Search

20K views 11 likes 1 dislikes 05 Oct 2011100% match

Transformer la peur, l'angoisse, la colère, la haine - 5'
Selim Aïssel
11.5K views 83 likes 4 dislikes 31 Jan 2013100% match

Recomendación kuentalibros - pizarra digital y niños con discapacidad auditiva
anitamc20
933 views 1 likes 0 dislikes 21 Dec 2012100% match

(ENG/CHI SUB) 140216 SM True Thailand Facebook EXO
Baby Xiumin
783 views 10 likes 0 dislikes 16 Feb 2014100% match

Unit 9 17 Value Iteration 1

24.8K views 27 likes 24 dislikes 01 Nov 2011100% match

Unit 4, 9 Gibbs Sampling

41K views 107 likes 26 dislikes 06 Oct 2011100% match

Unit 5 12 Maximum Likelihood

33.3K views 61 likes 19 dislikes 17 Oct 2011100% match

Unit 2, Topic 25, A-Star Third Question

26.6K views 9 likes 17 dislikes 05 Oct 2011100% match

¿Cuál es la función de los Bancos de Inversión?
canaloie24
17.4K views 97 likes 5 dislikes 22 Nov 2011100% match

Unit 1w, 13 Chinese Translation Answer 2

24.6K views 18 likes 2 dislikes 05 Oct 2011100% match

Winnie the Witch 5
Pilar Moure
28.7K views 59 likes 10 dislikes 31 May 2013100% match

TED & TEDx explained
Kyo young Chu
1.1K views 7 likes 0 dislikes 02 Apr 2012100% match

Unit 11 02.mp4 Hidden Markov Models.mp4

13.2K views 19 likes 1 dislikes 11 Nov 2011100% match

Gundarr (Ep 23): Meet Moody Sue (Subtitulado al castellano)
daniborr
21.8K views 98 likes 10 dislikes 22 Sep 2012100% match

Unit 1w, 10 AI and Uncertainty

26.3K views 42 likes 2 dislikes 05 Oct 2011100% match

Papa,please, get the moon for me
Ana María
15K views 24 likes 0 dislikes 23 Nov 2014100% match

Settings Privacy About Contact Donate