Video
Đăng bởi Ban biên tập OpenER ·
Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
PROFESSOR
Today we're going to talk about Markov decision processes, which are a generalization of search problems where you're not entirely sure what your actions are going to do until you try them.
Hôm nay chúng ta sẽ nói về quá trình quyết định Markov, là sự tổng quát hóa của các bài toán tìm kiếm, trong đó bạn không hoàn toàn chắc chắn hành động của mình sẽ gây ra điều gì cho đến khi thử.
So why would we consider a kind of nondeterministic search? We had our search problems before. They had states, they had actions, they had costs, and we made plans.
Vậy tại sao ta lại xét một dạng tìm kiếm không tất định? Trước đây ta đã có các bài toán tìm kiếm. Chúng có trạng thái, hành động, chi phí, và ta lập kế hoạch.
We'd perhaps be moving a robot around the grid to accomplish some task or a Pac-Man around a board.
Có thể ta di chuyển một robot trên lưới để hoàn thành một nhiệm vụ, hoặc điều khiển Pac-Man trên bản đồ.
The reason why we need to have a nondeterministic search is because in the real world, often you know what actions are available to you, and you know what they might do but you're not entirely sure what outcome will occur.
Lý do ta cần tìm kiếm không tất định là vì trong thế giới thực, thường thì bạn biết mình có những hành động nào, và biết chúng có thể làm gì, nhưng không hoàn toàn chắc kết quả nào sẽ xảy ra.
So for example, if you're this robot here trying to cross this ledge, you know you can shimmy to the side and try to get that gem, and it might work, or you might fall into the pit.
Ví dụ, nếu bạn là con robot này đang băng qua gờ đá, bạn biết có thể nhích sang bên để lấy viên ngọc, và có thể thành công, hoặc bạn có thể rơi xuống hố.
And so when you take an action, you may know the possible outcomes, but you don't know which one is going to happen.
Vì vậy khi thực hiện một hành động, bạn có thể biết các kết quả khả dĩ, nhưng không biết kết quả nào sẽ xảy ra.
And so you have to make plans or more generally, compute policies that take into account all of the different outcomes that might occur in response to your actions.
Do đó bạn phải lập kế hoạch, hay tổng quát hơn là tính chính sách có tính đến tất cả các kết quả khác nhau có thể xảy ra để đáp lại hành động của bạn.
One example of not knowing what's going to happen is when you hit the spacebar, usually you get the next slide, but sometimes it all freezes up.
Một ví dụ về việc không biết điều gì sẽ xảy ra là khi tôi nhấn phím cách, thường thì sang slide kế tiếp, nhưng đôi khi mọi thứ bị treo.
Luckily, my policy knows what to do when that happens. So we're going to have a couple running examples. Just like when we talked about search, we had running examples of search.
May là chính sách của tôi biết phải làm gì khi chuyện đó xảy ra. Chúng ta sẽ có vài ví dụ xuyên suốt. Giống như khi nói về tìm kiếm, ta đã có các ví dụ xuyên suốt về tìm kiếm.
So we talked about the specific examples of search, or CSPs, or games. And then we talked about the whole class of search problems, or CSPs, or games.
Ta nói về các ví dụ cụ thể của tìm kiếm, CSP, hoặc trò chơi. Rồi sau đó nói về cả lớp bài toán tìm kiếm, CSP, hoặc trò chơi.
The running example we're going to use for MDPs, Markov decision processes, is Grid World. But just like in all those other cases, it's just a running example.
Ví dụ xuyên suốt ta dùng cho MDP, quá trình quyết định Markov, là Grid World. Nhưng cũng như những trường hợp khác, đó chỉ là một ví dụ xuyên suốt.
So in Grid World, we have a maze, we have a robot, we have north, south, east, and west, and we're going to have a bunch of Grid World concepts, which are really good for illustrating the kinds of things that happen in MDPs, but we're going to have to be really careful that we don't overfit — flash forward to the machine learning section at the end — we don't want to overfit to this particular example.
Trong Grid World, ta có một mê cung, một robot, có bắc, nam, đông, tây, và sẽ có nhiều khái niệm của Grid World, rất phù hợp để minh họa những gì xảy ra trong MDP, nhưng ta phải thật cẩn thận để không bị quá khớp — nhắc trước phần học máy ở cuối môn — ta không muốn quá khớp với ví dụ cụ thể này.
So in Grid World, which is just one of a whole rich world of possible MDPs, we have a problem that looks a little bit like a maze.
Grid World chỉ là một trong vô vàn MDP có thể có, với một bài toán trông hơi giống mê cung.
The agent is going to be on a grid, and they're going to be walls blocking the agents path. I love it when they install stuff for me. Let's go.
Tác tử nằm trên một lưới, và có các bức tường chặn đường của tác tử. Tôi thích khi họ cài đặt giúp tôi. Đi nào.
Get rid of you. There are going to be walls blocking the agent's path. This is a lot like moving Pac-Man around a maze except now there's going to be some nondeterminism.
Biến đi. Có các bức tường chặn đường của tác tử. Điều này khá giống việc di chuyển Pac-Man trong mê cung, ngoại trừ giờ sẽ có tính không tất định.
And in this case, in this particular MDP, that the nondeterminism is going to take the shape of noise.
Và trong MDP cụ thể này, tính không tất định có dạng nhiễu.
So in this Grid World, say 80% of the time, when you take an action, which might be called north, you'll actually move to the north.
Trong Grid World này, giả sử 80% số lần, khi bạn thực hiện hành động, chẳng hạn là bắc, bạn sẽ thực sự di chuyển lên phía bắc.
Remember, in search you would just decide where you want to go, and then you'd be there, but here you try to move north, but it might fail.
Nhớ rằng trong tìm kiếm, bạn chỉ cần quyết định muốn đi đâu, rồi bạn sẽ ở đó, nhưng ở đây bạn thử đi lên bắc, và có thể thất bại.
So in Grid World, your actions might succeed, and that means you're going to move in the direction you attempted to move, or they might fail, which means something else happens.
Trong Grid World, hành động có thể thành công, nghĩa là bạn di chuyển theo hướng đã định, hoặc có thể thất bại, nghĩa là có điều khác xảy ra.
And in this formulation of Grid World — and we could formulate Grid World a million different ways.
Và trong cách mô hình hóa Grid World này — ta có thể mô hình hóa Grid World theo cả triệu cách.
Formulating a problem so that it matches the real-world problem you're trying to solve is one of the challenges in using these techniques, but in this Grid World, 80% of the time you go where you're expected if there's no wall there.
Mô hình hóa bài toán sao cho khớp với bài toán thực tế cần giải là một trong những thách thức khi dùng các kỹ thuật này, nhưng trong Grid World này, 80% số lần bạn đi đúng hướng mong muốn nếu ở đó không có tường.
If there's a wall there, you'll just bounce off and stay put. The other 20% of the time you either go counterclockwise or clockwise direction.
Nếu có tường, bạn sẽ bị bật lại và đứng yên. 20% còn lại bạn sẽ đi theo hướng ngược chiều hoặc cùng chiều kim đồng hồ.
So 10% of the time, if you go to try to go north, you'll actually go west. 10% of the time, if you try to go north, you'll actually go east.
Vậy 10% số lần, nếu bạn định đi lên bắc, bạn sẽ thực sự đi sang tây. 10% số lần, nếu bạn định đi lên bắc, bạn sẽ thực sự đi sang đông.
In this Grid World, you're totally safe from going south. That's something that will never happen in this model if you try to go north. Is this is how the real robots work?
Trong Grid World này, bạn hoàn toàn an toàn khỏi việc đi xuống nam. Điều đó sẽ không bao giờ xảy ra trong mô hình này nếu bạn định đi lên bắc. Robot thật có hoạt động như vậy không?
Not really. This is how the Grid World we're going to use for this lecture and the next one works. If there is a wall in the direction you would have gone, you stay put.
Không hẳn. Đây là cách Grid World mà ta dùng cho bài giảng này và bài sau hoạt động. Nếu có tường ở hướng bạn định đi, bạn đứng yên.
All right. That's the rules about where you can move. You can move north, south, east, west, but it might fail, sending you in an unexpected direction.
Được rồi. Đó là các quy tắc về việc di chuyển. Bạn có thể đi bắc, nam, đông, tây, nhưng có thể thất bại, đưa bạn đến một hướng không mong đợi.
Now let's talk about the equivalent of costs from search. In MDPs, the costs are called rewards, and here we receive two kinds of rewards.
Giờ hãy nói về thứ tương đương với chi phí trong tìm kiếm. Trong MDP, chi phí được gọi là phần thưởng, và ở đây ta nhận hai loại phần thưởng.
They're sort of the primary Grid World reward, which is that you exit the game, and there's good exits and bad exits, and they're labeled with a value.
Loại chính của Grid World, đó là việc thoát khỏi trò chơi, có lối thoát tốt và xấu, được gắn nhãn bằng một giá trị.
So in this case the gem might be the good exit. If you can get to that square, you take the action exit, it ends the game.
Trong trường hợp này viên ngọc có thể là lối thoát tốt. Nếu bạn đến được ô đó, thực hiện hành động thoát, trò chơi kết thúc.
You get your plus 1 reward, and you're a happy robot.
Bạn nhận phần thưởng +1, và là một robot vui vẻ.
If you fall into the pit, you also take the action exit, you receive your minus 1 reward, the game still ends, but now you're a sad robot. Those are the big rewards.
Nếu rơi xuống hố, bạn cũng thực hiện hành động thoát, nhận phần thưởng -1, trò chơi vẫn kết thúc, nhưng giờ bạn là một robot buồn. Đó là những phần thưởng lớn.
They can be good or bad, positive or negative. And in Grid World, to illustrate some concepts, we sometimes also have a living reward, which happens every step that you don't exit the game.
Chúng có thể tốt hoặc xấu, dương hoặc âm. Và trong Grid World, để minh họa một số khái niệm, đôi khi ta còn có phần thưởng sống, nhận được ở mỗi bước mà bạn chưa thoát khỏi trò chơi.
So for example, in this position here, I might decide to take the action north.
Ví dụ, ở vị trí này, tôi có thể chọn hành động đi lên phía bắc.
Maybe it succeeds, and I actually move to the square to the north of the current robot, and I get a little reward.
Có thể nó thành công, và tôi thực sự di chuyển đến ô ở phía bắc của robot hiện tại, và tôi nhận được một phần thưởng nhỏ.
It could be a tiny little boost, a positive reward, or it could be a tiny little bit of pain or something like that as a negative reward, or it can be big or it can be zero.
Đó có thể là một chút lợi ích, tức phần thưởng dương, hoặc có thể là một chút đau đớn nào đó như một phần thưởng âm, hoặc có thể lớn hoặc bằng không.
That's something we can change, and that's something that you get every step of the game.
Đó là thứ chúng ta có thể thay đổi, và đó là thứ bạn nhận được ở mỗi bước của trò chơi.
This notion of a living reward and a big reward at the end and a gem and a fire pit, these are all Grid World concepts.
Khái niệm phần thưởng sống và phần thưởng lớn ở cuối, rồi viên ngọc và hố lửa, đều là các khái niệm của Grid World.
But the idea that when you take a transition from a state to another state, you receive a reward of some kind. That's an MDP notion.
Nhưng ý tưởng rằng khi bạn chuyển từ trạng thái này sang trạng thái khác, bạn nhận được một phần thưởng nào đó. Đó là khái niệm của MDP.
The goal, loosely, because we're going to revisit this later in this lecture, the goal, loosely, is to maximize the sum of the rewards So you would like to take action so that you get the gem, but you don't fall into the pit.
Mục tiêu, nói đại khái, vì ta sẽ xem lại điều này sau trong bài giảng, mục tiêu, nói đại khái, là cực đại hóa tổng các phần thưởng. Bạn muốn chọn hành động để lấy được viên ngọc, nhưng không rơi xuống hố.
That's a lot like search, when we we're trying to take actions which, in that case, minimize costs, now we're trying to maximize rewards.
Điều này giống tìm kiếm, khi ta chọn hành động để cực tiểu hóa chi phí, còn bây giờ ta cố cực đại hóa phần thưởng.
In a deterministic Grid World, we could have solved the problem with Search. We could have said, all right I'm in this state here, and what can I do?
Trong một Grid World tất định, ta có thể giải bài toán bằng tìm kiếm. Ta có thể nói, được rồi, tôi đang ở trạng thái này, và tôi có thể làm gì?
Well, I can move north. I can move west. North is a good move, west is a bad move, so I'll move north. And when I choose that action, I know what's going to happen.
Tôi có thể đi lên bắc. Tôi có thể đi sang tây. Bắc là nước đi tốt, tây là nước đi tệ, nên tôi đi bắc. Và khi chọn hành động đó, tôi biết điều gì sẽ xảy ra.
There is one outcome per action. That's what it means to say you have a deterministic search problem.
Mỗi hành động có một kết quả. Đó là ý nghĩa của việc nói bài toán tìm kiếm là tất định.
In a Markov decision problem, it's nondeterministic, which means when I'm in a certain state — like the robots right there to the right of the pit — and I choose to move north, there's multiple things that could happen.
Trong bài toán quyết định Markov thì không tất định, nghĩa là khi tôi ở một trạng thái nhất định, như robot ngay bên phải cái hố, và tôi chọn đi bắc, thì có nhiều điều có thể xảy ra.
Importantly, in an MDP, I know the set of possible outcomes, and it's actually going to turn out I know the probability that each one will occur.
Quan trọng là, trong MDP tôi biết tập các kết quả có thể, và thực ra sẽ thấy là tôi biết xác suất xảy ra của từng kết quả.
I just don't know which one will occur in a given run.
Tôi chỉ không biết kết quả nào sẽ xảy ra trong một lần chạy cụ thể.
So when I plan to go north here, I know I might go north or I might go to the east and have to replan from there, or I might go to the west and fall into the pit, and that will be bad.
Nên khi định đi bắc ở đây, tôi biết mình có thể đi bắc hoặc trượt sang đông và phải lập kế hoạch lại từ đó, hoặc trượt sang tây và rơi xuống hố, và điều đó sẽ tệ.
And as I plan, I need to take these things into account. So I might take, for example, a cautious behavior that takes into account all of the possible failures along the way.
Khi lập kế hoạch, tôi cần tính đến những điều này. Chẳng hạn tôi có thể chọn hành vi thận trọng, tính đến mọi thất bại có thể xảy ra trên đường đi.
So in general, an MDP, a Markov decision process, will be defined much in the way a search problem was by a set of quantities that defined the problem.
Nói chung, một MDP, một quá trình quyết định Markov, được định nghĩa giống như bài toán tìm kiếm, bằng một tập các đại lượng xác định bài toán.
There's a set of states. This is very much like in Search. These are the set of configurations of your problem. There is a set of actions, and we had these in Search too.
Có một tập các trạng thái. Điều này rất giống tìm kiếm. Đây là tập các cấu hình của bài toán. Có một tập các hành động, và tìm kiếm cũng có chúng.
Sometimes we didn't really talk about the actions having labels when we talked about, say, depth-first search, but there were neighbors. There was a successor function.
Đôi khi ta không thực sự nói các hành động có nhãn khi nói về, chẳng hạn, tìm kiếm theo chiều sâu, mà chỉ có các nút lân cận. Có một hàm kế tiếp.
And in your code, in project one, you did actually have to manage the labels of the actions. So this is something that's been there all along, their states and their actions.
Và trong code ở project một, bạn thực sự phải quản lý nhãn của các hành động. Vậy đây là thứ luôn có từ đầu, các trạng thái và các hành động.
The differences is that in search, when you're in a state and you take an action, there is a successor state and a cost.
Điểm khác là trong tìm kiếm, khi bạn ở một trạng thái và thực hiện một hành động, có một trạng thái kế tiếp và một chi phí.
And in MDP, there's not just one successor state, there are multiple. So we've got our states like before, we've got our actions like before.
Còn trong MDP, không chỉ có một trạng thái kế tiếp, mà có nhiều. Vậy ta có các trạng thái như trước, có các hành động như trước.
But now if I'm in state S, and I choose action A, there may be multiple states, s prime, that can occur as a result. And so what I will have is what's called a transition function, which describes from state S and action A, what S primes can happen and with what probability.
Nhưng giờ nếu tôi ở trạng thái S và chọn hành động A, có thể có nhiều trạng thái s phẩy xảy ra như một kết quả. Vì vậy ta sẽ có cái gọi là hàm chuyển, mô tả từ trạng thái S và hành động A, những S phẩy nào có thể xảy ra và với xác suất bao nhiêu.
So people write TSA S prime and call it a transition function, but what you should have in your head is this is for being in state S, choosing action A, and what I care about is the probability that every possible outcome, S prime, happens.
Người ta viết T(S, A, S') và gọi là hàm chuyển, nhưng điều bạn nên nghĩ trong đầu là: đang ở trạng thái S, chọn hành động A, và điều tôi quan tâm là xác suất mà mỗi kết quả có thể, S', xảy ra.
So TSA S prime, is in this sense a conditional probability that S prime will happen if you were in state S and chose action A.
Vậy T(S, A, S') theo nghĩa này là xác suất có điều kiện để S' xảy ra nếu bạn đang ở trạng thái S và chọn hành động A.
Another important quantity in an MDP is a reward function. So a reward function, in general, is going to be a positive or negative or a zero reward that you get.
Một đại lượng quan trọng khác trong MDP là hàm phần thưởng. Hàm phần thưởng, nói chung, cho ra phần thưởng dương, âm hoặc bằng không mà bạn nhận được.
If you're in state S, you choose action A, and you land in state S prime. Sometimes it will only depend on S. Sometimes it will only depend on S prime.
Nếu bạn ở trạng thái S, chọn hành động A, và đến trạng thái S'. Đôi khi nó chỉ phụ thuộc vào S. Đôi khi nó chỉ phụ thuộc vào S'.
Sometimes it will depend on the entire triple.
Đôi khi nó phụ thuộc vào cả bộ ba.
That triple is often called a transition, and in general, we'll write the reward function as being a function of where you started, what you did, and where you landed.
Bộ ba đó thường được gọi là một phép chuyển, và nói chung ta sẽ viết hàm phần thưởng như hàm của nơi bạn bắt đầu, điều bạn làm, và nơi bạn đến.
So if you're on the cliff trying to cross the cliff, there might be one reward for making it across and an entirely different award if you fall into the fire pit.
Vậy nếu bạn đang ở vách đá cố băng qua, có thể có một phần thưởng khi qua được và một phần thưởng hoàn toàn khác nếu rơi xuống hố lửa.
In general, there's maybe a start state. There might be a terminal state. This is where things start to differ. In Search, there was this really important notion of a goal test.
Nói chung, có thể có một trạng thái bắt đầu. Có thể có một trạng thái kết thúc. Đây là chỗ bắt đầu có sự khác biệt. Trong tìm kiếm, có một khái niệm rất quan trọng là kiểm tra đích.
These are the states where we stop. We've achieved our goal.
Đó là các trạng thái mà ta dừng lại. Ta đã đạt được mục tiêu.
And MDPs, in full generality, the game just keeps playing, and sometimes you get into a state where it stops, sometimes the game has gone forever, and we'll need to be very careful with our algorithms and our formulations that we understand what that means that a game may go on forever.
Còn MDP, ở dạng tổng quát, trò chơi cứ tiếp tục, đôi khi bạn vào một trạng thái làm nó dừng, đôi khi trò chơi diễn ra mãi mãi, và ta cần rất cẩn thận với các thuật toán và cách phát biểu để hiểu rõ điều đó có nghĩa gì khi một trò chơi có thể kéo dài vô tận.
So MDPs, like I said, are a class of nondeterministic search problems, and they will require a new class of algorithms to solve them. So A* search won't do it.
Vậy MDP, như tôi đã nói, là một lớp các bài toán tìm kiếm không tất định, và chúng cần một lớp thuật toán mới để giải. Nên tìm kiếm A* không làm được.
That's for deterministic search problem. So how are we going to solve MDPs?
Nó dành cho bài toán tìm kiếm tất định. Vậy ta sẽ giải MDP bằng cách nào?
We're going to talk about a bunch of algorithms today and next class, and then in some sense, the week after that as well, because it turns out that MDPs are the foundation for reinforcement learning as well.
Hôm nay ta sẽ nói về một loạt thuật toán, cả buổi sau nữa, và theo một nghĩa nào đó, cả tuần sau đó nữa, vì hóa ra MDP cũng là nền tảng của học tăng cường.
However, you actually already have an algorithm for solving MDPs. It's called expectimax search.
Tuy nhiên, thực ra các em đã có một thuật toán để giải MDP rồi. Đó là tìm kiếm expectimax.
When you learned about expectimax search, it might have felt like a weird variant of minimax, where the opponent was rolling dice or something like that.
Khi học expectimax, có thể các em thấy nó như một biến thể kỳ lạ của minimax, trong đó đối thủ đi tung xúc xắc hay gì đó tương tự.
But it's actually the more general algorithm, and here, we'll see that it's very tightly related to the algorithms we used to solve MDPs.
Nhưng thực ra nó là thuật toán tổng quát hơn, và ở đây ta sẽ thấy nó liên hệ rất chặt chẽ với các thuật toán dùng để giải MDP.
So MDPs are like search problems, but instead of knowing what your action will do, you have a distribution over possible outcomes represented by the transition function. Any questions?
Vậy MDP giống bài toán tìm kiếm, nhưng thay vì biết hành động sẽ gây ra điều gì, ta có một phân phối trên các kết quả có thể xảy ra, được biểu diễn bằng hàm chuyển. Có câu hỏi nào không?
All right. So there's this Markov guy, and what's he doing in my decision problem?
Được rồi. Vậy có ông Markov này, và ông ấy làm gì trong bài toán quyết định của tôi?
Markov in AI usually means something about the present state, and it means that given the present state, the future and the past are independent in an appropriate sense.
Trong AI, Markov thường nói về trạng thái hiện tại, và nghĩa là khi biết trạng thái hiện tại, tương lai và quá khứ độc lập theo một nghĩa phù hợp. độc lập với nhau theo một nghĩa thích hợp.
And in a Markov decision process, what Markov means is that the action outcomes — so those transition probabilities of what will happen if I take this action in this state, they can depend on the state, and they can depend on the action, but they can't depend on the past.
Còn trong quá trình quyết định Markov, Markov nghĩa là kết quả của hành động, tức các xác suất chuyển về điều sẽ xảy ra nếu tôi thực hiện hành động này ở trạng thái này, có thể phụ thuộc vào trạng thái, và vào hành động, nhưng không thể phụ thuộc vào quá khứ.
So if I'm the robot and I want to know what's going to happen if I try to cross this bridge, well, it depends on where I am and what I'm doing, but it doesn't depend on the route that I took to get there.
Nếu tôi là robot và muốn biết điều gì sẽ xảy ra khi tôi cố băng qua cây cầu này, thì nó phụ thuộc vào vị trí và việc tôi làm, nhưng không phụ thuộc vào đường tôi đã đi để tới đó.
So if you remember, this is just like what we had in search.
Các em nhớ đấy, điều này giống hệt trong tìm kiếm.
We had to be very careful to formulate our search problem so that the state had any information stuffed into it that was necessary to let the successor function fully describe the problem.
Ta phải rất cẩn thận khi xây dựng bài toán tìm kiếm để trạng thái chứa đủ mọi thông tin cần thiết để hàm kế tiếp mô tả đầy đủ bài toán.
And so with Search, we often formulated, all right, my state can't just be Pac-Man's position, it's also got to be which dots I've eaten or where the walls still are or whatever is appropriate for that variation.
Nên với tìm kiếm, ta thường phải xác định rằng trạng thái không thể chỉ là vị trí của Pac-Man, mà còn là những chấm nào đã ăn, hoặc tường còn ở đâu, hay bất cứ gì phù hợp với biến thể đó.
MDPs are the same way.
MDP cũng vậy.
We often have to be careful how we formulate our states so that they give us the Markov property, that if I know the state and I know the action, I can tell you the distribution over what happens next in a way that's independent of what's happened in the past.
Ta thường phải cẩn thận khi xây dựng các trạng thái để có tính chất Markov, tức là nếu biết trạng thái và biết hành động, tôi có thể cho em biết phân phối của điều xảy ra tiếp theo, mà không phụ thuộc vào những gì đã xảy ra trong quá khứ.
Thank you, Markov.
Cảm ơn ông Markov.
Here's another big difference from Search In Search, we had this model of the agent that looked at the search problem and did a bunch of offline computation and thought and thought and thought and came up with a plan.
Đây là một khác biệt lớn nữa so với tìm kiếm. Trong tìm kiếm, ta có mô hình tác tử nhìn vào bài toán tìm kiếm và tính toán offline cả một loạt nghĩ đi nghĩ lại mãi rồi đưa ra một kế hoạch.
What's a plan? A plan is a sequence of actions.
Kế hoạch là gì? Kế hoạch là một chuỗi hành động.
And then we would execute that plan step by step, and as we executed that plan, our master design would fall into place action by action, and we'd end up with the goal state exactly the way we planned.
Rồi ta thực thi kế hoạch đó từng bước, và khi thực thi, thiết kế tổng thể của ta sẽ vào đúng chỗ từng hành động một, và ta kết thúc ở trạng thái đích đúng như đã lên kế hoạch.
MDPs are for a noisier world. And so we can't really have a plan because it might work or it might not. So let me give you an example.
MDP dành cho một thế giới nhiều nhiễu hơn. Nên ta không thể có kế hoạch thực sự, vì nó có thể chạy đúng hoặc không. Để tôi lấy ví dụ.
I'm going to pull up Grid World here.
Tôi sẽ mở Grid World ở đây.
All right.
Được rồi.
Here is Grid World on the right, and here on the left, you can't really tell what I'm pressing, so you'll be able to see what happens for each transition as I pass.
Grid World ở bên phải, còn bên trái, các em không thấy rõ tôi bấm gì, nên các em sẽ thấy điều xảy ra ở mỗi lần chuyển khi tôi đi.
So here the robot is the blue dot, and you can see 1, that's the good exit with the gem, minus 1 is the bad exit with the fire pit, and I'm going to press north, south, east, or west, and the robot may or may not go the direction I press.
Robot là chấm xanh, số 1 là lối thoát tốt có viên ngọc, -1 là lối thoát xấu với hố lửa, tôi sẽ bấm bắc, nam, đông hoặc tây, và robot có thể đi hoặc không đi theo hướng tôi bấm.
So what direction should we go? Let's try north. I'm going to press the up key on my keyboard. What will happen?
Vậy ta nên đi hướng nào? Thử hướng bắc. Tôi bấm phím lên trên bàn phím. Chuyện gì sẽ xảy ra?
Who knows. So it worked, all that suspense. This said, started in state 0, 0. Took action north.
Ai biết được. Nó chạy đúng, hồi hộp ghê. Nó cho biết: bắt đầu ở trạng thái 0, 0. Thực hiện hành động bắc.
Ended in state 0, 1. That is a transition. S was 0, 0; A was north; S prime was 0, 1; and I got a little reward. My reward was negative 0.1.
Kết thúc ở trạng thái 0, 1. Đó là một lần chuyển. S là 0, 0; A là bắc; S phẩy là 0, 1; và tôi nhận được một chút phần thưởng. Phần thưởng là âm 0,1.
In this particular configuration of Grid World, you get a minus 0.1 each time, and that might affect your behavior.
Trong cấu hình Grid World này, mỗi lần đi bạn bị trừ 0,1, và điều đó có thể ảnh hưởng hành vi của bạn.
So as we change the living reward up and down, we'll get different Grid Worlds in which the optimal actions are going to be different behaviors. We'll see that in a second.
Khi ta tăng giảm phần thưởng sống, ta sẽ có những Grid World khác nhau mà hành động tối ưu sẽ là những hành vi khác nhau. Lát nữa ta sẽ thấy.
So I'm going to try to go north again. I'm going to press north again. OK, it worked. So far, it's acting pretty deterministic.
Tôi thử đi bắc lần nữa. Tôi bấm bắc lần nữa. Được, nó chạy đúng. Đến giờ nó hành xử khá tất định.
So we started in state 0, 1. We took action north, and we ended in state 0, 2. We might not have. We might have ended somewhere else, but that's what happened this time.
Ta bắt đầu ở trạng thái 0, 1. Ta thực hiện hành động bắc, và kết thúc ở trạng thái 0, 2. Có thể đã không như vậy. Có thể ta đã tới chỗ khác, nhưng lần này nó xảy ra như thế.
That's a transition, SA S prime, and we got an instantaneous reward, minus 1. So far, my rewards are minus 0.2. I'm going to try to go east. It worked.
Đó là một lần chuyển, S A S phẩy, và ta nhận phần thưởng tức thời, âm 1. Đến giờ tổng phần thưởng của tôi là âm 0,2. Tôi thử đi đông. Nó chạy đúng.
Do something random. I went east, and it worked. I'm going to try to go east again. Oh, look at this.
Làm gì đó ngẫu nhiên đi. Tôi đã đi sang phải, và nó thành công. Tôi sẽ thử đi sang phải một lần nữa. Ồ, nhìn này.
Started in state 1, 2. I took action in east, and I ended in state 1, 2. That wasn't the most likely outcome, but that's what happened here.
Bắt đầu ở trạng thái 1, 2. Tôi thực hiện hành động đi hướng đông, và kết thúc ở trạng thái 1, 2. Đó không phải kết quả có khả năng nhất, nhưng đó là điều đã xảy ra ở đây.
And so when I plan, I need to plan knowing that these things might not go the way I expected.
Vì vậy khi lập kế hoạch, tôi cần lập kế hoạch với ý thức rằng mọi thứ có thể không diễn ra như tôi mong đợi.
So if I had just blindly executed up, up, east, east, east, east, exit, I'd be in trouble because something didn't go according to plan. Something didn't have its most likely outcome here.
Nếu tôi cứ mù quáng thực hiện lên, lên, đông, đông, đông, đông, thoát, thì tôi sẽ gặp rắc rối vì có chuyện không đi theo kế hoạch. Có một bước không cho ra kết quả có khả năng nhất.
I'm going to go east again now because that's still a good idea. Whenever I'm in that state, that's a good idea. Now, I'm going to go east again.
Giờ tôi sẽ lại đi hướng đông vì đó vẫn là một ý hay. Bất cứ khi nào ở trạng thái đó, đó đều là ý hay. Giờ tôi lại đi hướng đông.
Now, here it starts to get a little bit suspenseful because I could successfully go into the good exit, or I could move perilously close to the fire pit.
Đến đây bắt đầu hơi hồi hộp một chút vì tôi có thể vào được lối thoát tốt, hoặc có thể đến gần hố lửa một cách nguy hiểm.
Let's try east.
Thử đi hướng đông.
Lucky. And then from this point, you'll notice I received only that living reward minus 0.1. I didn't receive the plus 1. That doesn't happen until I take the action exit from the square.
May quá. Và từ điểm này, bạn sẽ thấy tôi chỉ nhận được phần thưởng sống là trừ 0,1. Tôi chưa nhận được cộng 1. Điều đó chỉ xảy ra khi tôi thực hiện hành động thoát khỏi ô này.
And you think who cares about exactly when it happens?
Bạn có thể nghĩ ai quan tâm chính xác khi nào nó xảy ra?
Well, we're going to use this running example enough, and it's going to be in your project, but it's good to know exactly when it happens so you don't have off by 1 errors all the time.
Chúng ta sẽ dùng ví dụ này khá nhiều, và nó sẽ có trong project của các bạn, nên cần biết chính xác khi nào nó xảy ra để không bị lỗi lệch một đơn vị suốt.
All right. So here I go. I'm going to exit. Boom.
Được rồi. Nào, bắt đầu. Tôi sẽ thoát. Bùm.
And what happened here? Let's scroll up. I was in state 3, 2. I took the action exit.
Chuyện gì đã xảy ra ở đây? Cuộn lên xem. Tôi ở trạng thái 3, 2. Tôi thực hiện hành động thoát.
I ended in the special state, terminal state, and I got reward 1, so my total cumulative reward was like 0.7 or something like that. I'm going to do it again.
Tôi kết thúc ở trạng thái đặc biệt, trạng thái kết thúc, và nhận phần thưởng 1, nên tổng phần thưởng tích lũy khoảng 0,7 gì đó. Tôi sẽ làm lại.
All right.
Được rồi.
Let's make this a little more tense. I'm going the scary way. I'm going to go east, east. I'm going to go north.
Làm cho nó căng thẳng hơn một chút. Tôi đi đường đáng sợ. Tôi sẽ đi đông, đông. Rồi đi lên phía bắc.
I'm going to walk past the pit. North. All right, I'm going north. Anything could happen.
Tôi sẽ đi ngang qua hố lửa. Bắc. Được rồi, tôi đi lên phía bắc. Chuyện gì cũng có thể xảy ra.
All right.
Được rồi.
Some years, this is really intense, but not this year. All right. So you get the idea.
Có năm cái này rất căng thẳng, nhưng năm nay thì không. Được rồi. Vậy là các bạn hiểu ý rồi.
But even though nothing spectacular happened like falling into a fire pit, you did see a couple of times where I expected the most likely outcome would be I'd move east, but I stayed put.
Dù không có gì ngoạn mục như rơi xuống hố lửa, các bạn đã thấy vài lần mà tôi mong kết quả có khả năng nhất là đi sang phải, nhưng tôi lại đứng yên.
As a result, we can't have a plan, which is a sequence of actions because who knows what's going to happen when I take those actions.
Do đó, ta không thể có một kế hoạch, tức là một chuỗi hành động, vì ai biết được chuyện gì sẽ xảy ra khi ta thực hiện các hành động đó.
For MDPs, the analogous concept to a plan is something called a policy. A policy isn't a sequence of actions you take. It is a function which in a state tells you an action.
Với MDP, khái niệm tương tự kế hoạch là thứ gọi là chính sách. Chính sách không phải là chuỗi hành động bạn thực hiện. Nó là một hàm, tại một trạng thái cho bạn biết một hành động. Có thể xem nó như hàm đề xuất hành động.
So it's like a recommendation of an action function. Policy, you give it a state, it gives you an action back.
Chính sách: bạn đưa vào một trạng thái, nó trả về một hành động.
In general, when we say we solve an MDP, we're not just interested in any policy, we're interested in the optimal policy.
Nói chung, khi nói giải một MDP, ta không chỉ quan tâm đến một chính sách bất kỳ, mà quan tâm đến chính sách tối ưu.
The optimal policy — policies are pi — that little star throughout these lectures, and in general, in this class it's going to indicate optimality. So we want pi star, which is an optimal policy.
Chính sách tối ưu, chính sách ký hiệu là pi, và dấu sao nhỏ xuyên suốt các bài giảng này, nói chung trong lớp này, sẽ chỉ tính tối ưu. Vậy ta muốn pi sao, là một chính sách tối ưu. Có thể có nhiều chính sách tương đương.
There may be multiple equivalent policies. A policy gives an action for each state, and often a policy is one that maximizes the expected utility of followed.
Chính sách cho một hành động ở mỗi trạng thái, và thường chính sách là cái cực đại hóa độ hữu dụng kỳ vọng khi được tuân theo.
And an explicit policy is an actual explicit enumeration for each state of where you should go.
Chính sách tường minh là liệt kê cụ thể cho từng trạng thái nơi bạn nên đi.
And so for example, this map here that the robot is looking at for the Grid World, that is an explicit policy. It lists each state and what to do.
Ví dụ, bản đồ này mà robot đang nhìn trong Grid World là một chính sách tường minh. Nó liệt kê từng trạng thái và việc cần làm. Nghĩa là tuân theo chính sách này là một tác tử phản xạ.
That means following this policy is a reflex agent. You look up your state, you look up the action, you do it. No computation is required.
Bạn tra trạng thái, tra hành động, rồi thực hiện. Không cần tính toán gì.
All the computation went into building this policy in the first place. Once you've got it, you just do it. Sometimes that's realistic, sometimes it's not.
Mọi tính toán đã dồn vào việc xây dựng chính sách này ngay từ đầu. Có rồi thì bạn chỉ việc làm theo. Đôi khi điều đó thực tế, đôi khi không.
So for example, in something like Pac-Man with dots, the state space may be so large you could never compute or even write down the explicit policy, and so we would need different methods.
Chẳng hạn trong Pac-Man với các chấm, không gian trạng thái có thể lớn đến mức không bao giờ tính hay viết ra nổi chính sách tường minh, nên ta sẽ cần các phương pháp khác.
We're going to talk about today assumes that the MDP is small enough, the state space is small enough that we can actually enumerate the states and write down policies.
Hôm nay ta bàn đến giả định rằng MDP đủ nhỏ, không gian trạng thái đủ nhỏ để ta có thể liệt kê các trạng thái và viết ra các chính sách. Điều đó không phải lúc nào cũng đúng.
That's not always going to be true. If you remember expectimax, that didn't actually compute policies either.
Nếu nhớ expectimax, nó cũng không thực sự tính ra chính sách.
You just executed it as a computation in a state, it churned on the game tree for a while, and then it said take this action.
Bạn chỉ chạy nó như một phép tính tại một trạng thái, nó xử lý trên cây trò chơi một lúc, rồi bảo hãy thực hiện hành động này. Vậy expectimax có thể nằm trong một hàm pi, tính chính sách ngay khi có yêu cầu.
So expectimax might be living inside a function, pi, that computes the policy on the fly on demand.
Hôm nay ta không nói về cách đó, nhưng đó là một lớp cách khác để xây dựng chính sách.
That's not what we're going to talk about today, but that is another class of ways you can build policies.
Instead of being explicit policies, you could have an implicit policy that requires computation each time you try to access it. All right. Let's take a look at some optimal policies.
Thay vì chính sách tường minh, bạn có thể có chính sách ngầm cần tính toán mỗi lần bạn truy cập nó. Được rồi. Hãy xem một số chính sách tối ưu. Bạn có thể thấy chính sách tối ưu ngay đây.
So you can see the optimal policy right here.
So there's the gem, there's the fire pit, and there's this policy that says, all right, if you're here at the start state, you should go up and around and into the gem.
Đây là viên ngọc, đây là hố lửa, Đây là viên ngọc, đây là hố lửa, và có chính sách này nói rằng, nếu bạn đang ở trạng thái bắt đầu, bạn nên đi lên trên, vòng qua rồi vào viên ngọc.
OK. Fair enough. Where it gets more interesting is in some of the other squares. So for example, if you're in this square here, this policy says that you should take the short way.
OK. Cũng hợp lý. Chỗ thú vị hơn là ở một vài ô khác. Ví dụ, nếu bạn ở ô này, chính sách này bảo bạn nên đi đường ngắn.
You could just take the short way around and risk the pit. Why? Why don't you go the long way around?
Bạn cứ đi đường ngắn và chấp nhận rủi ro rơi xuống hố. Tại sao? Sao không đi đường vòng dài?
Well, this is going to be a function of exactly how the living reward, which here is a penalty balances against the risk you take by walking past that pit.
Điều này phụ thuộc chính xác vào việc phần thưởng sống, ở đây là một khoản phạt, cân bằng thế nào với rủi ro khi đi ngang qua cái hố.
And this is a general example of we feed in the specification of the model, and the behavior emerges through the computation.
Đây là ví dụ tổng quát: ta đưa vào đặc tả của mô hình, và hành vi xuất hiện từ quá trình tính toán.
So let's look at some examples of different kinds of behaviors all emerging from the same computation of solving an MDP to get an explicit policy for Grid World.
Hãy xem vài ví dụ về các hành vi khác nhau đều xuất hiện từ cùng một phép tính, tức là giải một MDP để có chính sách tường minh cho Grid World.
So here's an example. There's still a plus 1 and a minus 1, a good exit and bad exit. And remember, each time step that you don't exit, you get a little reward.
Đây là một ví dụ. Vẫn có ô +1 và ô -1, một lối thoát tốt và một lối thoát xấu. Và nhớ rằng, mỗi bước thời gian mà bạn chưa thoát, bạn nhận một chút phần thưởng.
In this case, it's negative, so you get hit with a tiny little tax minus 0.1 each time step. I guess it's more of a tool than a tax.
Ở đây nó âm, nên bạn bị đánh một khoản thuế nhỏ xíu -0.1 mỗi bước. Có lẽ gọi là phí qua cầu thì đúng hơn là thuế.
And if you look at this, you can see that as you'd expect, if you're at the start state, you might as well go the safe way.
Nhìn vào đây, bạn thấy rằng đúng như dự đoán, nếu ở trạng thái bắt đầu, thì bạn nên đi đường an toàn.
But if you're here, even though you're quite close to the shortcut, it's still going to send you around the long way.
Nhưng nếu bạn ở đây, dù khá gần lối tắt, chính sách vẫn gửi bạn đi đường vòng dài.
And that's because that living reward is so minor that it's not worth the risk of falling into the pit, which is a significant risk. So you just pay the extra price to go around.
Đó là vì phần thưởng sống quá nhỏ nên không đáng để liều rơi xuống hố, một rủi ro đáng kể. Nên bạn chịu trả thêm cái giá để đi vòng.
You might slip a little bit as you go, it might take a little longer, but you basically go around the long way. Here's the really interesting square right here.
Bạn có thể trượt một chút khi đi, có thể mất lâu hơn, nhưng về cơ bản bạn đi đường vòng dài. Đây là ô thật sự thú vị.
What the heck is that? The living reward is very small, and that means this agent has a lot of patience.
Cái quái gì thế này? Phần thưởng sống rất nhỏ, và điều đó nghĩa là tác tử này rất kiên nhẫn.
It can afford to take a lot of steps to get a large reward later. So it's doing this odd thing where it's moving into the wall.
Nó có thể đi rất nhiều bước để nhận phần thưởng lớn về sau. Nên nó làm một việc kỳ lạ: đi thẳng vào tường.
What's up with that? So we fed all the rules into the agent, and what did it do? It solved it, and it basically learned an exploit.
Chuyện gì vậy? Ta đưa mọi luật vào tác tử, và nó làm gì? Nó giải xong và về cơ bản học được một lỗ hổng.
Grid World has a bug, and this agent learned it. What is the bug? From this grid square here, if you go north, you might fall into the pit.
Grid World có một lỗi, và tác tử này đã học được nó. Lỗi đó là gì? Từ ô này, nếu đi lên phía bắc, bạn có thể rơi xuống hố.
If you go south, you might fall into the pit. If you go into the pit, you're probably going to fall into the pit.
Nếu đi xuống phía nam, bạn cũng có thể rơi xuống hố. Nếu đi vào hố, bạn gần như chắc chắn sẽ rơi xuống hố.
But if you head towards the wall, there's no chance of falling into the pit. What's probably going to happen? Nothing is probably going to happen.
Nhưng nếu hướng về phía tường, thì không có khả năng rơi xuống hố. Điều gì có khả năng xảy ra? Có lẽ chẳng có gì xảy ra cả.
You're probably going to end up where you are, but if you do it enough over and over and over again, eventually you'll slip to the left or the right, and you will have escaped the danger square without any risk of falling into the pit.
Bạn có lẽ vẫn ở nguyên chỗ cũ, nhưng nếu làm đi làm lại đủ nhiều lần, cuối cùng bạn sẽ trượt sang trái hoặc phải, và bạn đã thoát khỏi ô nguy hiểm mà không có rủi ro rơi xuống hố.
So if you remember back, you remember the little ibos playing soccer where the way they shoot is they put their stomach on the ball and then poop it out.
Nếu còn nhớ, các bạn nhớ mấy con ibo chơi bóng đá, cách chúng sút là úp bụng lên quả bóng rồi đẩy nó ra bằng đường hậu môn.
This is more or less a spontaneous discovery of a behavior which is optimal but maybe not what you would have predicted, and it's a consequence of the rules of the game.
Đây gần như là sự tự phát hiện ra một hành vi tối ưu nhưng có thể không như bạn dự đoán, và nó là hệ quả của luật chơi.
All right. We can turn up the temperature here, and charge the agent more per step so that taking your time is no longer going to be as appealing.
Được rồi. Ta có thể tăng nhiệt, phạt tác tử nhiều hơn mỗi bước để việc cứ thong thả không còn hấp dẫn nữa.
And so in this case, you still go straight.
Khi đó, bạn vẫn đi thẳng.
You prefer the good goal to the bad goal, but here you're going to risk falling in rather than taking 10 turns to shimmy your way out.
Bạn thích đích tốt hơn đích xấu, nhưng ở đây bạn sẽ liều rơi xuống hố thay vì mất 10 lượt để nhích ra.
But you'll still go the long way around if you're in one of these squares. Let's turn up the heat again. Here the reward is minus 0.4. Think about that.
Nhưng bạn vẫn đi đường vòng dài nếu đang ở một trong những ô này. Tăng nhiệt thêm lần nữa. Ở đây phần thưởng là -0.4. Hãy nghĩ xem.
It's like starting to be almost as big as the rewards at the end of the game. So now this agent is not going to mess around.
Nó bắt đầu gần bằng phần thưởng ở cuối trò chơi. Nên giờ tác tử này sẽ không lòng vòng nữa.
Given the choice, it would rather take the safe way than the dangerous way, but if you're in the square, you're just going to run for it.
Nếu được chọn, nó thích đường an toàn hơn đường nguy hiểm, nhưng nếu đã ở trong ô này, bạn cứ chạy liều.
Maybe you'll fall into the pit, but that's OK because if you go the long way around, you're going to accumulate so much negative living reward that that doesn't make sense.
Có thể bạn rơi xuống hố, nhưng không sao vì nếu đi đường vòng dài, bạn sẽ tích lũy quá nhiều phần thưởng sống âm nên điều đó không hợp lý.
What do you think is going to happen if I crank it all the way to negative 2? Think about that for a second.
Bạn nghĩ chuyện gì sẽ xảy ra nếu tôi đẩy nó xuống tận -2? Nghĩ một chút nhé.
That fire pit starts to look pretty good because it's better than the reward you get every step. And so what are you going to do? Straight to the closest exit.
Cái hố lửa bắt đầu trông khá ổn vì nó tốt hơn phần thưởng bạn nhận mỗi bước. Vậy bạn sẽ làm gì? Đi thẳng đến lối thoát gần nhất.
Get me out of this game. All of these different kinds of qualitative behaviors will emerge from the same kind of computation just as the differences in rewards and the balances of those shift.
Cho tôi ra khỏi trò chơi này. Tất cả những hành vi định tính khác nhau này đều xuất hiện từ cùng một phép tính chỉ khi sự khác biệt về phần thưởng và các cân bằng đó thay đổi.
Any questions on that? Now, we're going to see how to compute the stuff.
Có câu hỏi nào không? Giờ ta sẽ xem cách tính những thứ này.
That's Grid World.
Đó là Grid World.
It's really, really easy to think of search problems as happening on a grid, and by now you know that many search problems have nothing to do with the grid or any kind of spatial structure.
Rất dễ nghĩ các bài toán tìm kiếm là diễn ra trên lưới, và đến giờ bạn biết nhiều bài toán tìm kiếm chẳng liên quan gì đến lưới hay cấu trúc không gian nào.
I'm going to give you another example of an MDP that looks nothing like Grid World to give you a second running example that we're going to work a lot with today and next time.
Tôi sẽ cho bạn một ví dụ khác về MDP trông chẳng giống Grid World chút nào để cho các bạn một ví dụ chạy thứ hai mà chúng ta sẽ dùng rất nhiều trong buổi hôm nay và buổi sau.
So this is a super, super simple example of a robot car. It's a very, very simple example that has only three states.
Đây là một ví dụ cực kỳ đơn giản về một chiếc xe robot. Ví dụ rất đơn giản, chỉ có ba trạng thái.
And what you see here is a state transition diagram — I think like a finite automaton — that describes the states and how they interact in this MDP.
Cái các bạn thấy ở đây là sơ đồ chuyển trạng thái, giống như một automat hữu hạn, mô tả các trạng thái và cách chúng tương tác trong MDP này.
So we have a robot car. It would like to travel far and quickly. And it's going to have three states, obviously, a huge simplification. There's going to be cool, warm, and overheated.
Vậy ta có một chiếc xe robot. Nó muốn đi được xa và nhanh. Và nó sẽ có ba trạng thái, tất nhiên là đã đơn giản hóa rất nhiều. Đó là cool (mát), warm (ấm) và overheated (quá nhiệt).
And cool is the good state. The car would like to be cool. Warm is OK, but you start to risk overheating, and if you overheat, the game is over.
Và cool là trạng thái tốt. Chiếc xe muốn được ở trạng thái mát. Warm thì tạm được, nhưng bắt đầu có nguy cơ quá nhiệt, và nếu quá nhiệt thì trò chơi kết thúc.
It's not actually directly good or bad to be cool, warm, or overheated because the rewards happen on the transitions.
Thực ra bản thân việc ở trạng thái mát, ấm hay quá nhiệt không trực tiếp tốt hay xấu, vì phần thưởng nằm ở các bước chuyển.
And in this case, you've got action slow and fast, and the way the rewards happens on the transitions is that you get twice as many points for moving fast than from moving slow regardless of where you land.
Trong trường hợp này, ta có hành động slow và fast, và phần thưởng trên các bước chuyển được tính như sau: đi nhanh được gấp đôi điểm so với đi chậm, bất kể bạn kết thúc ở đâu.
The rewards can depend on where you land like they did and Grid World, here, they don't. They only depend, in this case, actually, on what state you're in and what action you take.
Phần thưởng có thể phụ thuộc vào nơi bạn đến, như trong Grid World, nhưng ở đây thì không. Trong trường hợp này, nó chỉ phụ thuộc vào trạng thái bạn đang ở và hành động bạn chọn.
So let's look and see if we can just wrap our heads around this example.
Giờ ta thử xem có hiểu rõ ví dụ này không.
So if the car is cool and you choose Slow, you will get your plus 1 reward because you went slow, and with probability 1, you'll stay cool. All right.
Nếu xe đang cool và bạn chọn Slow, bạn nhận phần thưởng +1 vì đi chậm, và với xác suất 1, bạn vẫn ở trạng thái cool. Được rồi.
What happens if you go fast? Well, if your car is cool and you go fast, you get the plus 2 for going fast, but what happens next is not deterministic.
Điều gì xảy ra nếu đi nhanh? Nếu xe đang cool và bạn đi nhanh, bạn được +2 vì đi nhanh, nhưng điều xảy ra tiếp theo không mang tính tất định.
Half the time, you stay cool, and half the time, you warm up. If you're warm and you go slow, you get the plus 1 reward for slow.
Một nửa số lần bạn vẫn cool, một nửa số lần xe nóng lên. Nếu xe đang warm và bạn đi chậm, bạn nhận +1 cho việc đi chậm.
Half the time you stay warm, but half the time you cool down.
Một nửa số lần vẫn warm, một nửa số lần nguội xuống.
If you're warm and you go fast, you get a minus 10, and you overheat, and if you overheat, the game is over. So what do you do? What do you do if it's cool?
Nếu xe đang warm và bạn đi nhanh, bạn bị -10, xe quá nhiệt, và nếu quá nhiệt thì trò chơi kết thúc. Vậy bạn làm gì? Khi xe đang cool thì làm gì?
Go fast. What do you do if it's warm? Don't go fast. Yeah, go slow.
Đi nhanh. Khi xe đang warm thì làm gì? Đừng đi nhanh. Đúng, đi chậm.
And if you're overheated, you should reflect back on the decisions that got you there. In this case, you do not have to end up there ever. So there you go.
Còn nếu đã quá nhiệt thì bạn nên nhìn lại những quyết định đã đưa bạn đến đó. Trong trường hợp này, bạn không bao giờ phải kết thúc ở đó. Vậy đấy.
This is a little MDP.
Đây là một MDP nhỏ.
It's got a very small number of states, but you can imagine the games can get very long because there's no real end to this game unless you make a mistake.
Nó có số trạng thái rất ít, nhưng bạn có thể hình dung ván chơi có thể kéo rất dài vì trò chơi này không thực sự có điểm kết thúc trừ khi bạn mắc sai lầm.
That's an example of another MDP. All right. So let's think if we wanted to figure out it's cool. I just ask you.
Đó là một ví dụ khác về MDP. Được rồi. Giả sử ta muốn tìm ra cần làm gì khi xe đang cool. Tôi vừa hỏi các bạn rồi.
So if I want to know what to do when the car is cool, apparently, you can just ask CS 188, but if I wanted to do that computationally, how would I figure out what the right action is?
Nếu tôi muốn biết phải làm gì khi xe đang cool, rõ ràng là bạn chỉ cần hỏi CS 188, nhưng nếu tôi muốn làm điều đó bằng tính toán, thì làm sao tìm ra hành động đúng?
You already got a tool.
Bạn đã có sẵn một công cụ.
You've got expectimax search, but I can think, all right, if I want to decide what to do from the state, cool, I can think out the possible futures just like we did with games last week.
Đó là tìm kiếm expectimax. Tôi có thể nghĩ thế này: nếu tôi muốn quyết định làm gì từ trạng thái cool, tôi có thể vạch ra các tương lai khả dĩ giống như ta đã làm với các trò chơi tuần trước.
And if I think out the possible futures, I'll think, well, I can go fast, or I can go slow. That's going to be under my control, but both are possible.
Và khi vạch ra các tương lai khả dĩ, tôi sẽ nghĩ: tôi có thể đi nhanh, hoặc đi chậm. Điều đó do tôi kiểm soát, và cả hai đều có thể xảy ra.
And if I go slow, only one outcome can happen from my taking that action, and that is I end up back in my state I started in.
Nếu tôi đi chậm, chỉ có một kết quả có thể xảy ra sau hành động đó, đó là tôi quay lại đúng trạng thái ban đầu.
If I go fast, there are two outcomes to that action. I'll either stay cool, or I'll heat up.
Nếu tôi đi nhanh, hành động đó có hai kết quả. Tôi sẽ vẫn cool, hoặc xe sẽ nóng lên.
I don't know which will happen, but I know they both can happen, and I know the probabilities associated with them. Now, you might wonder, what if I don't know the probabilities?
Tôi không biết cái nào sẽ xảy ra, nhưng tôi biết cả hai đều có thể xảy ra, và tôi biết các xác suất gắn với chúng. Bạn có thể thắc mắc: nếu tôi không biết các xác suất thì sao?
I would say come back next week for reinforcement learning where we'll learn the probabilities. For now, we know about them.
Tôi sẽ nói là hãy quay lại tuần sau để học về học tăng cường, nơi ta sẽ học cách tìm ra các xác suất. Còn bây giờ thì ta đã biết chúng.
And then I can just kind of keep extending this into the future, and I can see this tree, which will look exactly like an expectimax tree.
Rồi tôi cứ tiếp tục mở rộng như vậy vào tương lai, và ta thấy cái cây này trông hệt như một cây expectimax.
There will be an alternation between actions that I can choose amongst and then chance nodes which describe the possible outcomes, which I know a distribution over, but I can't force an outcome.
Nó xen kẽ giữa các hành động mà tôi có thể chọn và các nút ngẫu nhiên mô tả các kết quả có thể xảy ra, mà tôi biết phân phối của chúng nhưng không thể ép ra một kết quả.
It's not going to be as bad as worst case, there's just a distribution. So here's a search tree that describes that. One thing should already strike you about this search tree.
Nó sẽ không tệ như trường hợp xấu nhất, mà chỉ là một phân phối. Đây là cây tìm kiếm mô tả điều đó. Có một điều ở cây tìm kiếm này hẳn đã khiến bạn chú ý.
Anybody notice anything that didn't really happen in expectimax?
Có ai nhận ra điều gì mà trong expectimax không thực sự xảy ra không?
One thing is it's the same three states over and over and over and over again. So doing some exponential amount of computation over these three states just like can't be the right thing.
Một điều là cùng ba trạng thái đó lặp đi lặp lại mãi mãi. Vì vậy, tính toán một lượng theo hàm mũ trên ba trạng thái này chắc chắn không thể là cách đúng.
Because these same subtrees up here, this tree here, is exactly the same as this one here, so we're going to want to be careful of that.
Vì những cây con giống nhau ở trên này, cây này, giống hệt cây ở đây, nên ta cần cẩn thận với điều đó.
In general, whenever you have a Markov decision problem, you can think about there being a tree like this projected from each state.
Nói chung, bất cứ khi nào bạn có một bài toán quyết định Markov, bạn có thể hình dung có một cây như thế này được chiếu ra từ mỗi trạng thái.
So from each state, there is a tree of futures that has that state at the root and then the actions available to you branching out. When we talk about S, S is a state.
Tức là từ mỗi trạng thái có một cây các tương lai với trạng thái đó ở gốc, rồi các hành động khả dụng tỏa nhánh ra. Khi nói S, S là một trạng thái.
The actions are A — those are the actions available to you — and we've had those for a while.
Các hành động là A, đó là những hành động bạn có thể chọn, và ta đã có chúng từ lâu rồi.
Now, here's where we get to something that's new and a little bit counterintuitive but super useful. What are these chance nodes from expectimax? What do they represent?
Giờ ta đến một điều mới và hơi phản trực giác nhưng cực kỳ hữu ích. Vậy các nút chance trong expectimax này đại diện cho cái gì? Chúng biểu diễn điều gì?
Well, S is a state of the world, and A is an action you choose.
S là một trạng thái của thế giới, còn A là hành động mà bạn chọn.
And then after you choose an action, it's going to resolve to some state, S prime, and there's going to be multiple possible outcomes, which are governed by a probability distribution.
Và sau khi bạn chọn một hành động, nó sẽ dẫn đến một trạng thái nào đó, S phẩy, và có thể có nhiều kết quả khác nhau, được chi phối bởi một phân phối xác suất.
But what about this node right here? I was in a state. There could have been other states, I was in that state. I chose an action.
Nhưng còn nút ngay đây thì sao? Tôi đang ở một trạng thái. Có thể có những trạng thái khác, nhưng tôi đang ở trạng thái này. Tôi đã chọn một hành động.
It may or may not have been a smart action, but I've chosen it, but I don't yet know what happened as a result.
Có thể đó là hành động khôn ngoan, có thể không, nhưng tôi đã chọn rồi, và tôi vẫn chưa biết kết quả của nó là gì.
Being in this situation where you're in a state and you've committed to an action but it has not resolved is called a Q state.
Tình huống bạn đang ở một trạng thái và đã cam kết một hành động nhưng chưa có kết quả được gọi là một trạng thái Q.
And it represents having chosen an action but not seen its resolution.
Nó biểu diễn việc đã chọn một hành động nhưng chưa thấy kết quả của nó.
This whole sequence here, this little tree, SA S prime is called a transition, and on this arc right here, when your Q state SA resolves to a particular result, S prime, that's a transition.
Toàn bộ chuỗi này, cái cây nhỏ này, S A S phẩy, được gọi là một chuyển tiếp, và trên cung ngay đây, khi trạng thái Q SA dẫn đến một kết quả cụ thể, S phẩy, thì đó là một chuyển tiếp.
It's labeled with a probability from your MDP as well as a reward.
Nó được gắn nhãn bằng một xác suất từ MDP của bạn, cùng với một phần thưởng.
And here that reward is shown as a gem, but the reward can be negative, for example, both the fire pit and the cliff.
Ở đây phần thưởng được vẽ là viên ngọc, nhưng phần thưởng có thể âm, ví dụ như cả hố lửa và vách đá.
So both the fire pit and the living reward are both negative. So this little search tree, this is MDP is in this slide, is the search tree.
Cả hố lửa và phần thưởng sống đều âm. Vậy cái cây nhỏ này, MDP trong slide này, chính là cây tìm kiếm.
Everything we do, every algorithm, every quantity, it all comes back to this search tree where you have a state, a sequence of actions that you maximize over, and for each action, a sequence of outcomes, which you have a probability distribution over.
Mọi thứ chúng ta làm, mọi thuật toán, mọi đại lượng, đều quy về cây tìm kiếm này, nơi bạn có một trạng thái, một chuỗi hành động để bạn tối đa hóa, và với mỗi hành động là một chuỗi kết quả, mà bạn có một phân phối xác suất trên đó.
We'll talk about solution in a bit. Let's take a step back, and try to figure out how an agent should think about a sequence of utilities.
Lát nữa chúng ta sẽ bàn về lời giải. Hãy lùi lại một bước và xem tác tử nên nghĩ thế nào về một chuỗi độ hữu dụng.
Because another thing that happens in an MDP is that you saw when we were in Grid World, those rewards would be trickled in step by step.
Vì một điều nữa xảy ra trong MDP là, như bạn đã thấy ở Grid World, các phần thưởng đến từng bước một.
So we need to be able to think about our preferences over these sequences. So what preferences should an agent have over a sequence of rewards?
Nên chúng ta cần suy nghĩ về sự ưu tiên của mình đối với các chuỗi này. Vậy tác tử nên ưu tiên gì đối với một chuỗi phần thưởng?
First, should an agent like more rewards or less rewards?
Trước hết, tác tử nên thích nhiều phần thưởng hơn hay ít hơn?
So for example, if I give an agent a choice between a sequence of three rewards — 1, 2, and 2 — or three awards — 2, 3, and 4 — which one should it pick?
Ví dụ, nếu tôi cho tác tử chọn giữa một chuỗi ba phần thưởng: 1, 2 và 2, hoặc ba phần thưởng: 2, 3 và 4, nó nên chọn cái nào?
Well, I guess I have to like define whether positive is good or not.
Tôi đoán trước hết phải xác định dương là tốt hay không. .
In this case, we've been talking about them as rewards, so it seems pretty reasonable that the agent should prefer to get more rewards rather than less. Great.
Ở đây chúng ta gọi chúng là phần thưởng, nên khá hợp lý là tác tử nên thích nhận nhiều phần thưởng hơn là ít. Tốt.
If that's all I wanted to accomplish, I would just add up the rewards, and I would say, hey, agent, go act in such a way as to maximize the sum of rewards.
Nếu chỉ cần vậy thôi, tôi sẽ cộng các phần thưởng lại và nói: này tác tử, hãy hành động sao cho tối đa hóa tổng phần thưởng.
But there's one other thing that turns out to be really important in MDPs, and it has to do with a choice between now or later. So for example, here's two sequences of rewards.
Nhưng còn một điều nữa hóa ra rất quan trọng trong MDP, đó là lựa chọn giữa bây giờ và sau này. Ví dụ, đây là hai chuỗi phần thưởng.
One is 0 rewards followed by 0 reward, followed by a reward of 1. Or another sequence where it's a reward of 1, followed by 0, followed by 0.
Một chuỗi là phần thưởng 0, rồi 0, rồi phần thưởng 1. Chuỗi kia là phần thưởng 1, rồi 0, rồi 0.
Same sum of rewards. What should the agent prefer, the reward now or the reward later? Or should it be indifferent? How many people say reward now?
Tổng phần thưởng bằng nhau. Tác tử nên thích phần thưởng ngay bây giờ hay phần thưởng sau này? Hay nó nên thấy như nhau? Ai chọn phần thưởng ngay bây giờ?
Give me rewards. How many people want their reward later? How many people are indifferent? So it is totally reasonable to be indifferent.
Đưa phần thưởng đây. Ai muốn nhận phần thưởng sau? Ai thấy như nhau? Thấy như nhau là hoàn toàn hợp lý.
Sometimes that's an appropriate formulation. But in most cases — and most people raised their hand for rewards now — it is also reasonable to prefer rewards sooner.
Đôi khi đó là cách mô hình hóa phù hợp. Nhưng trong hầu hết trường hợp, và phần lớn các bạn giơ tay chọn phần thưởng ngay bây giờ, thì ưu tiên phần thưởng sớm hơn cũng hợp lý.
And so how are we going to handle that? Adding up the rewards doesn't actually capture the fact that rewards soon are more useful than rewards later.
Vậy ta xử lý điều đó thế nào? Cộng các phần thưởng lại thực ra không phản ánh được việc phần thưởng đến sớm có ích hơn phần thưởng đến muộn.
For example, if somebody comes up to you and says, hey, would you like $100 now or in 20 years? Will you be indifferent?
Ví dụ, nếu có ai đến hỏi bạn: bạn muốn 100 đô bây giờ hay 20 năm nữa? Bạn có thấy như nhau không?
What if they say, and of course, it's easy to see that you might say, well, I'd rather that reward now.
Còn nếu họ hỏi, và dĩ nhiên dễ hiểu là bạn sẽ nói, tôi thích nhận ngay bây giờ.
But what if they say, would you like $100 now or $110 in 20 years? You probably still want the reward now.
Nhưng nếu họ hỏi: bạn muốn 100 đô bây giờ hay 110 đô sau 20 năm? Có lẽ bạn vẫn muốn nhận ngay bây giờ.
And so that means there's going to be an implicit tradeoff between having things soon and having things be big.
Điều đó có nghĩa là có một sự đánh đổi ngầm giữa việc có thứ gì đó sớm và việc có thứ gì đó lớn.
So it's reasonable to maximize the sum of your rewards. In fact, that's what we've been doing so far with Grid World. It's also reasonable to prefer rewards now to rewards later.
Vì vậy tối đa hóa tổng phần thưởng là hợp lý. Thực tế đó là điều chúng ta đã làm với Grid World cho đến giờ. Ưu tiên phần thưởng bây giờ hơn phần thưởng sau cũng hợp lý.
One solution to capturing these different reasonable utility functions is to say that the values of rewards are going to decay in an exponential way.
Một cách để biểu diễn các hàm độ hữu dụng hợp lý khác nhau này là nói rằng giá trị của phần thưởng sẽ giảm dần theo hàm mũ.
So for example, here's a reward, and if you get it now, it might actually be worth 1 right now.
Ví dụ, đây là một phần thưởng, và nếu nhận ngay bây giờ, nó có thể đáng giá 1.
But if you think about that reward, that same reward being in the future, it could be worth the same, then you would just be summing rewards, or we can penalize it.
Nhưng nếu nghĩ về phần thưởng đó, cũng phần thưởng đó nhưng ở tương lai, nó có thể đáng giá như nhau, khi đó ta chỉ cộng các phần thưởng, hoặc ta có thể phạt nó.
A way that's very convenient formally and mathematically to penalize things is to say that in the next time step, it won't be worth 1 any more. It will be worth less.
Một cách rất tiện về mặt hình thức và toán học để phạt là nói rằng ở bước thời gian kế tiếp, nó sẽ không còn đáng giá 1 nữa. Nó sẽ đáng giá ít hơn.
It will be discounted. It will be worth some amount, gamma, which we can pick.
Nó sẽ bị chiết khấu. Nó sẽ đáng giá một lượng gamma nào đó mà ta có thể chọn.
Gamma has to be greater than 0 to make sense, and it has to be less than or equal to 1 if you want things to be worth less later, but there are different points you could set in between.
Gamma phải lớn hơn 0 thì mới có nghĩa, và phải nhỏ hơn hoặc bằng 1 nếu bạn muốn những thứ về sau có giá trị thấp hơn, nhưng bạn cũng có thể chọn các mức ở giữa.
And then in two time steps, it will be worth gamma squared.
Và sau hai bước thời gian, nó sẽ có giá trị gamma bình phương.
And so the value of your reward will decay exponentially, or the rate of that decay is something that is actually an input to the problem rather than something you can derive.
Vậy giá trị phần thưởng của bạn sẽ suy giảm theo hàm mũ, còn tốc độ suy giảm đó thực ra là đầu vào của bài toán chứ không phải thứ bạn suy ra được.
So two questions. One is, how do we discount, and the second is, why do we discount. So how we discount is actually the easier of those questions.
Vậy có hai câu hỏi. Một là chiết khấu như thế nào, và hai là tại sao phải chiết khấu. Chiết khấu như thế nào thì dễ hơn.
So remember, if we think about there being this tree of possible futures where every time you take an action, the world responds with telling you what the outcome was.
Hãy nhớ, nếu ta hình dung có một cây các tương lai khả dĩ, trong đó mỗi lần bạn thực hiện một hành động, thế giới phản hồi cho bạn biết kết quả là gì.
So here you are at S. You took action A. You landed in S prime, and at that point, there's this little call which is, hey, I was at S, I took action A, I landed in S prime, so here you go.
Ở đây bạn đang ở S. Bạn thực hiện hành động A. Bạn đến S phẩy, và tại thời điểm đó, có một lời gọi kiểu: này, bạn đã ở S, đã làm hành động A, và đã đến S phẩy, nên đây là phần của bạn.
You can have your reward, R of SA S prime.
Bạn nhận phần thưởng R của S, A, S phẩy.
And then you get another award here. You get another reward and another reward here.
Rồi bạn nhận thêm một phần thưởng ở đây. Lại thêm một phần thưởng nữa ở đây.
And what you can do is conceptually you want each of those rewards to get hit with an extra factor of gamma and say if you are running and expectimax search, you could just set it up so that each time you recurse to the next level of the tree and you return a result, you hit it with a factor of gamma so that each level down picks up an extra factor of gamma.
Về mặt khái niệm, điều bạn có thể làm là nhân mỗi phần thưởng đó thêm một hệ số gamma, chẳng hạn nếu bạn đang chạy tìm kiếm expectimax, bạn chỉ cần thiết lập sao cho mỗi lần đệ quy xuống tầng tiếp theo của cây và trả về kết quả, bạn nhân kết quả đó với một hệ số gamma, để mỗi tầng đi xuống lại có thêm một hệ số gamma.
This has some really interesting properties like things way, way in the future eventually just don't matter very much because they've been hit with so many factors of gamma that they're just not worth very much to your computation.
Cách này có những tính chất rất thú vị, chẳng hạn những thứ ở rất, rất xa trong tương lai rốt cuộc không còn quan trọng mấy, vì chúng đã bị nhân với rất nhiều hệ số gamma nên giá trị trong phép tính của bạn rất nhỏ. Vậy tại sao nên chiết khấu? Thứ nhất, phần thưởng đến sớm có thể thật sự có độ hữu dụng cao hơn phần thưởng đến muộn.
So why should we discount? One is that sooner rewards probably really do have higher utility than later rewards.
Đôi khi điều này liên quan đến cơ chế của chính bài toán, chẳng hạn đây là tiền, bạn có thể đem đi đầu tư hay gì đó tương tự.
And sometimes this has to do with the mechanics of the problem itself, like maybe this is money you can invest it or something like that.
Và thực sự có một cách giải thích rằng cơ chế đó là thứ gì đó tăng theo hàm mũ hoặc giảm dần giá trị.
And there is actually a story where the mechanism is something exponential or something decaying in value.
Nhưng nó cũng giúp thuật toán hội tụ, và còn một lý do nữa khiến chúng rất tiện, lát nữa tôi sẽ nói.
But it also helps our algorithms converge, and there's another reason why these are very convenient, which I'll talk about in a second. So that's discounting.
Đó là chiết khấu.
In general, in MDPs, we say either we sum the rewards or we sum them up with a discount that hits each time step so that things farther out into the future are worth exponentially less.
Nói chung, trong MDP, ta hoặc cộng các phần thưởng hoặc cộng chúng với một hệ số chiết khấu áp vào mỗi bước thời gian, để những thứ càng xa trong tương lai thì giá trị giảm theo hàm mũ. Và nếu nghĩ kỹ, hai cách này thực ra hoàn toàn giống nhau, vì nếu dùng gamma bằng 1, bạn sẽ có trường hợp không chiết khấu.
And if you think about it, these are actually the exact same thing because if you use that gamma equal to 1, you'll end up with the undiscovered case.
Giả sử chiết khấu là 0,5, thì chuỗi 1, 2, 3 không có giá trị là 1 cộng 2 cộng 3.
So if you think about a discount of 0.5, that sequence 1, 2, 3 is not worth 1 plus 2 plus 3. So 1, 2, and 3 are the rewards.
Ở đây 1, 2 và 3 là các phần thưởng.
The utility of the sequence could be the sum of the rewards or it could be the sum of the discounted rewards, which is, in general, what we'll do, and here, that means that's 1 times 1 because it has discounted yet plus 2 at the second time step, but it gets hit with a discount, in this case 0.5.
Độ hữu dụng của chuỗi có thể là tổng các phần thưởng hoặc tổng các phần thưởng đã chiết khấu, và nói chung ta sẽ dùng cách này. Ở đây, đó là 1 nhân 1 vì chưa bị chiết khấu cộng 2 ở bước thời gian thứ hai, nhưng nó bị nhân với chiết khấu, ở đây là 0,5. Rồi ở bước thứ ba, bạn nhận được 3, nhưng nó đã bị chiết khấu hai lần, nên chỉ đáng một phần tư so với giá trị ở bước thời gian hiện tại.
And then on the third time step, you get a 3, but it's been hit with that discount twice, so it's only worth a quarter of what it would have been worth at the current time step.
Vì vậy tổng ở đây không phải 6, mà nhỏ hơn nhiều.
And so the sum here isn't 6, it's much less. And that 3, even though it's the largest number is actually worth less than the 1 at the next time step.
Và số 3, dù là số lớn nhất, lại có giá trị thấp hơn số 1 ở bước kế tiếp. Nhìn vào đây, ngoài ra còn có nghĩa là 1, 2, 3 có độ hữu dụng kém hơn 3, 2, 1.
So if you look at this, among other things, this means that 1, 2, 3 is not as good in utility as 3, 2, 1.
Vậy khi xác định một MDP, ta phải chỉ rõ một hệ số chiết khấu, cho biết cách biến chuỗi phần thưởng thành độ hữu dụng của chuỗi.
So when we specify an MDP, we have to specify a discount, which tells us how to turn the sequence of rewards into a utility over the sequence.
Hoặc là tổng, hoặc là tổng có chiết khấu. Được rồi.
It's either going to be the sum or the discounted sum.
All right.
Remember when we talked about utilities and we talked about there being even before you have utilities, which is going around and assigning numbers to outcomes, we talked about something more primitive, which is preferences.
Hãy nhớ khi nói về độ hữu dụng, ta đã nói rằng ngay cả trước khi có độ hữu dụng, tức là việc gán số cho các kết quả, còn có một khái niệm sơ khai hơn, đó là sở thích. Tôi thích hai viên kem hơn một viên kem.
I like two scoops of ice cream more than one scoop of ice cream. And then I can go around saying how many U tiles each scoop is or something like that.
Rồi sau đó tôi có thể gán xem mỗi viên đáng bao nhiêu đơn vị hay đại loại như vậy. Ta đã nói về một tập các sở thích hợp lý.
We talked about there being a set of rational preferences.
These are preferences that seemed like any reasonable set of utilities should respect them, and then we could derive things like if your preferences obey these rational constraints, then they can be formulated in a certain way as a utility function.
Đó là những sở thích mà bất kỳ tập độ hữu dụng hợp lý nào cũng phải tôn trọng, và từ đó ta suy ra được rằng nếu sở thích của bạn tuân theo các ràng buộc hợp lý này, thì chúng có thể được biểu diễn dưới dạng một hàm độ hữu dụng. Với chuỗi cũng có một khái niệm tương đương, đó là sở thích dừng (stationary preferences). Có một định lý nói rằng giả sử sở thích của bạn là dừng.
There's an equivalent notion here for sequences, and it's a notion of stationary preferences. So there is this theorem that says let's imagine that your preferences are stationary.
Nghĩa là nếu bạn thích chuỗi phần thưởng A1, A2, A3, A4, v.v. hơn chuỗi khác là B — B1, B2, B3.
That means if you prefer the sequence of rewards A1, A2, A3, A4, and so on, to this other sequence B — B1, B2, B3.
Tức là bạn thích chuỗi A hơn chuỗi B. Tốt. Không cần biết vì sao.
So you like the A sequence better than the B sequence. Great. Who cares why. You like A better than B.
Bạn thích A hơn B.
If I tell you, hey, how about for the first time step, I'll give you the same reward, R, and then I'm going to give you A and B. Well, if you liked A better than B now and your preferences are stationary, it means you will also like a better than be shifted one time step if that first time step has the same reward.
Nếu tôi nói: ở bước thời gian đầu tiên, tôi cho bạn cùng một phần thưởng R, rồi sau đó mới đến A và B. Nếu bạn thích A hơn B bây giờ và sở thích của bạn là dừng, thì bạn cũng sẽ thích A hơn B khi bị dịch đi một bước thời gian, miễn là bước đầu có cùng phần thưởng. Giả định sở thích là dừng có vẻ hợp lý. Nếu sở thích là dừng, thì chỉ có hai cách để định nghĩa độ hữu dụng, mà như ta đã nói về cơ bản là một, đó là hoặc cộng các phần thưởng tức thời ở mỗi bước thời gian, hoặc cộng chúng với chiết khấu.
It seems like it's reasonable to assume that preferences are stationary.
If preferences are stationary, it turns out there are only two ways to define utilities, which as we talked about are basically the same thing, which is you either sum the instantaneous rewards at each time step, or you sum them with a discount.
Và bạn có thể thấy hơi lạ. về cơ bản là như nhau, tức là bạn hoặc cộng tổng các phần thưởng tức thời ở mỗi bước thời gian, hoặc cộng chúng có áp dụng hệ số chiết khấu.
And you think that's a little weird. Maybe my preferences aren't stationary, and sometimes they're not.
Và bạn thấy điều đó hơi lạ. Có thể sở thích của tôi không bất biến theo thời gian, và đôi khi đúng là như vậy.
Because for example, if you are playing a game, like say, Life, where you don't have an infinite number of time steps, it could be that by pushing the rewards out something just comes too late, something falls off the edge, or something like that.
Ví dụ, nếu bạn chơi một trò chơi như Life chẳng hạn, nơi số bước thời gian không phải là vô hạn, thì việc đẩy phần thưởng ra xa có thể khiến thứ gì đó đến quá muộn, hoặc rơi mất khỏi rìa, hoặc đại loại như vậy.
And so when things have finite horizons, sometimes things get trickier and have to be handled in different ways.
Vì thế khi bài toán có chân trời hữu hạn, mọi thứ đôi khi trở nên rắc rối hơn và phải được xử lý theo những cách khác.
All right. Let's do a quick quiz. First, any questions before the quiz has gone? Any questions?
Được rồi. Ta làm một câu đố nhanh. Trước hết, có câu hỏi nào trước khi làm câu đố không? Có ai hỏi không?
Yep.
Mời bạn.
STUDENT
Is there a reason that are discounts are exponential rather than subtracting at each step?
Có lý do nào khiến hệ số chiết khấu là dạng mũ chứ không phải trừ đi một lượng ở mỗi bước không ạ?
PROFESSOR
It's a great question. The question is, why are we doing exponential rather than subtractive discounts. So let me separate two things. Very important.
Câu hỏi rất hay. Câu hỏi là: tại sao ta dùng chiết khấu dạng mũ thay vì chiết khấu bằng phép trừ. Để tôi tách hai việc ra. Rất quan trọng.
There's two things going on in a Grid World, not in MDP in general, a Grid World, robots, north, south, east, west, and so on.
Có hai việc đang diễn ra trong Grid World, không phải trong MDP nói chung, mà là Grid World, robot, bắc, nam, đông, tây, v.v.
There is a living reward which might be a penalty at each time. That is an R. That's a reward. That has nothing to do with a discount.
Có một phần thưởng sống còn, có thể là một hình phạt ở mỗi thời điểm. Đó là R. Đó là phần thưởng. Nó không liên quan gì đến hệ số chiết khấu.
Then there is a discount, which so far we have been talking about the Grid World is having a discount of 1. They were undiscounted so far.
Còn hệ số chiết khấu thì từ đầu đến giờ, khi nói về Grid World, ta coi hệ số chiết khấu bằng 1. Tức là từ trước đến giờ ta chưa chiết khấu.
So you can always penalize each time step as part of the reward structure. But mathematically, when you talk about sequences being converted into a single number, that's when we use the exponential formulation.
Nên bạn luôn có thể phạt mỗi bước thời gian như một phần của cấu trúc phần thưởng. Nhưng về mặt toán học, khi nói về việc chuyển một chuỗi thành một con số duy nhất, thì ta dùng công thức dạng mũ.
And the reason we do that is one, it's mathematically very convenient. It helps us prove that things converge.
Lý do là, thứ nhất, nó rất thuận tiện về mặt toán học. Nó giúp ta chứng minh được sự hội tụ.
It reflects a lot of real-world things, in many cases by pushing something out in time, for example, interest and so on on money. Things really are exponential.
Nó phản ánh nhiều hiện tượng thực tế, trong nhiều trường hợp khi đẩy thứ gì đó ra xa về thời gian, ví dụ lãi suất trên tiền. Mọi thứ thực sự là dạng mũ.
And then beyond that, there's also this theory about stationary preferences which only holds for the exponential case and not for the additive case.
Ngoài ra, còn có lý thuyết về sở thích bất biến, chỉ đúng cho trường hợp dạng mũ chứ không đúng cho trường hợp cộng.
But it's a great question, and sometimes we do actually, like in Grid World, want to have something additive going on where every time step costs the same. And we can do that too.
Nhưng đó là câu hỏi hay, và đôi khi như trong Grid World, ta thật sự muốn có thứ mang tính cộng, mỗi bước thời gian tốn như nhau. Và ta cũng làm được điều đó.
OK. Yep.
OK. Mời bạn.
STUDENT
So this is depictions of reward in action, is the reward?
Vậy đây là mô tả phần thưởng khi hành động, có phải phần thưởng không ạ?
PROFESSOR
I'm sorry, could you ask it again?
Xin lỗi, bạn hỏi lại được không?
STUDENT
Is the sequence of reward. So how can I know the sequence if the future is undetermined?
Đó có phải là chuỗi phần thưởng không ạ? Làm sao em biết chuỗi đó nếu tương lai chưa xác định?
PROFESSOR
So the question is, how can I know the sequence of rewards when the future is undetermined.
Câu hỏi là làm sao biết chuỗi phần thưởng khi tương lai chưa xác định.
And before you act, you don't know what sequence or rewards you will get, but what these algorithms do is they plan — I could take this action, I could take that action.
Trước khi hành động, bạn không biết sẽ nhận chuỗi phần thưởng nào, nhưng các thuật toán này lập kế hoạch: tôi có thể làm hành động này, hoặc hành động kia.
And based on the actions I take and the actions I might then take later, I have to hedge with all of those possible outcomes and probabilities in the appropriate way.
Dựa trên hành động tôi chọn và những hành động tôi có thể chọn sau đó, tôi phải dự phòng cho mọi kết quả khả dĩ và xác suất của chúng một cách phù hợp. Nên ta cần tính được: nếu tôi có phần thưởng này, hoặc phần thưởng kia, thì kết hợp chúng thế nào và nghĩ về chúng ra sao.
So we need to be able to compute, OK, if I have this reward, or I have this reward, how would I combine them and how would I think about them.
Nhưng đúng là vậy. Bạn thực sự không biết mình sẽ gặp tương lai nào cho đến khi chơi thật.
But it's true. You don't actually know which future you're going to get until you actually play the game. So solving an MDP happens offline. You don't actually play it.
Nên việc giải một MDP diễn ra ngoại tuyến. Bạn không chơi thật. Bạn xét các xác suất và xây dựng chính sách.
You consider the probabilities, and you make your policy. You can then go actually execute the policy, and then you're going to get one particular experience.
Sau đó bạn có thể đi thực thi chính sách, và khi đó bạn sẽ có một trải nghiệm cụ thể. Điều đó tương tự với học tăng cường, nơi ta chơi trò chơi và có chuyện xảy ra, rồi lần sau chơi lại, có thể có chuyện khác xảy ra.
And that's going to be analogous to what we do in reinforcement learning where we just play the game and something happens, and the next time we play it, something else might happen.
Và khi đó ta sẽ phải học.
And then we'll be in a position of having to learn.
Right now we know the rules of the game, and so even without actually playing it, we can solve in a way that hedges all of those various probabilities appropriately.
Còn bây giờ ta biết luật chơi, nên dù không chơi thật, ta vẫn giải được theo cách dự phòng cho tất cả các xác suất đó một cách phù hợp. Câu hỏi rất hay. Ta làm câu đố về chiết khấu.
Great questions. Let's do a quiz on discounting. So this is a Grid World. You can go east, west, and exit.
Đây là một Grid World. Bạn có thể đi sang đông, tây, và thoát. Chỉ thoát được ở A và E. Môi trường tất định, nên nếu đi sang đông thì bạn thực sự đi sang đông.
You can only exit at A and E. It's deterministic so that if you go east, you'll actually go east. And if you exit a day, you get 10.
Nếu thoát ở A, bạn nhận 10. Nếu thoát ở E, bạn nhận 1. Nếu gamma bằng 1, chính sách tối ưu là gì?
If you exit at E, you get 1. If gamma is 1, what is the optimal policy? So what should I do, say at B here? You should go this way.
Vậy tôi nên làm gì, chẳng hạn ở B đây? Bạn nên đi hướng này. Giờ thì bắt đầu khó hơn. Ở giữa tôi nên làm gì?
Now, it starts to get tricky. What should I do in the center? I should go left. All right.
Tôi nên đi sang trái. Được rồi. Nếu gamma bằng 1, ở D đây tôi nên làm gì? Tôi nên đi sang trái, vì chuỗi phần thưởng tôi nhận là gì?
Now if gamma is 1, what should I do over here at D? I should go left because what sequence of rewards will I get? I'll get 0, 0, 0.
Tôi sẽ nhận 0, 0, 0. Và cuối cùng, nó bị đẩy ra xa hơn. Cuối cùng tôi vẫn nhận được 10, và không sao vì tôi không chiết khấu nó.
And then at the end, it's been pushed farther out. I'll eventually get that 10, but that's fine because I'm not actually discounting it. However, if gamma is 1, I'll give you the easy one.
Tuy nhiên, nếu gamma là 1, tôi cho bạn câu dễ. Tôi nên đi đến đây. Thêm một câu dễ nữa ở giữa.
I should go here. I'll give you another easy one in the center. It's going to be the same amount of time either way, but here's the interesting case, what happens here if it's 0.1?
Đi hướng nào thì thời gian cũng như nhau, nhưng trường hợp thú vị là, chuyện gì xảy ra ở đây nếu gamma là 0.1? Nếu tôi đi hướng này, tôi nhận được gì? Tôi sẽ không nhận được 1 vì nó bị đẩy ra một bước thời gian.
Well, if I go this way, what am I going to get? I'm not going to get 1 because it's going to be pushed out a time step.
Nếu đi hướng này, tôi nhận 0.1. Còn nếu đi hướng này thì sao?
If I go this way, I'll get 0.1. What if I go this way?
Nếu đi đường này, tôi sẽ được 0,1. Còn nếu đi đường này thì sao?
I'm pushed out one, two, three time steps, so I'm going to get 0.001, and that means it's better to just go right. Because I'd rather get that 1.
Nó bị đẩy lùi một, hai, ba bước thời gian, nên tôi chỉ nhận được 0.001, và điều đó có nghĩa là tốt hơn là cứ đi sang phải. Vì tôi thà nhận phần thưởng 1 đó.
By the time I get to the 10, it will be so decayed I don't even want it. So in this case, sooner is more important than more.
Đến lúc tôi tới được phần thưởng 10, nó đã bị chiết khấu nhiều đến mức tôi chẳng còn muốn nó nữa. Vậy trong trường hợp này, sớm quan trọng hơn nhiều.
And that tradeoff is encapsulated in gamma, which among other things, specifies in a soft way what's often informally called the horizon of the agent, how far out I'm thinking.
Và sự đánh đổi đó được gói gọn trong gamma, mà ngoài những thứ khác, còn xác định một cách mềm dẻo cái mà người ta thường gọi không chính thức là tầm nhìn (horizon) của tác tử, tức là tôi nghĩ xa đến đâu.
Now, in MDP, you're always thinking all the way out but in a way that tails off.
Trong MDP, bạn luôn nghĩ đến tận cùng nhưng theo kiểu giảm dần.
And the faster that discount tails off, the more greedy you are going to be, the more you'll pursue rewards sooner rather than larger rewards later. I think we'll just go from there.
Và hệ số chiết khấu giảm càng nhanh thì bạn càng tham lam, bạn sẽ càng theo đuổi phần thưởng sớm hơn là phần thưởng lớn hơn về sau. Tôi nghĩ ta dừng ở đây.
A couple more things, and we'll take a break and talk about algorithms for solving these MDPs. All right.
Còn vài điều nữa, rồi ta sẽ nghỉ giải lao và nói về các thuật toán giải các MDP này. Được rồi.
So let's say you're that race car and you can go fast or you can go slow.
Giả sử bạn là chiếc xe đua đó và bạn có thể đi nhanh hoặc đi chậm.
And if you play your cards right, you're never going to actually overheat, so the game will last forever. You go fast, fast, slow, slow, fast, fast, fast.
Và nếu bạn chơi khéo, bạn sẽ không bao giờ bị quá nhiệt, nên trò chơi sẽ kéo dài mãi mãi. Bạn đi nhanh, nhanh, chậm, chậm, nhanh, nhanh, nhanh.
And what's your total reward going to be? Infinite. If you go slow all the time, what's it going to be? Infinite.
Vậy tổng phần thưởng của bạn sẽ là bao nhiêu? Vô hạn. Nếu lúc nào cũng đi chậm thì sẽ là bao nhiêu? Vô hạn.
If you go fast when you can and then slow when you have to, infinite. And so that's not good.
Nếu đi nhanh khi có thể và chậm khi buộc phải chậm, vẫn vô hạn. Vậy thì không ổn.
I mean, it's good if you like rewards because they're infinite, but it's a problem for algorithms that are going to be trying to decide between different actions if all the quantities we're deciding between are just infinity.
Ý tôi là, cũng tốt nếu bạn thích phần thưởng vì chúng vô hạn, nhưng đó là vấn đề đối với các thuật toán đang cố quyết định giữa các hành động khác nhau nếu mọi đại lượng ta đang chọn giữa chúng đều là vô cùng.
So how do we handle the possibility the games could go on forever and make our algorithms difficult? Well, there's basically three solutions, and sometimes they're appropriate, and sometimes they're not.
Vậy ta xử lý thế nào khi có khả năng trò chơi kéo dài mãi và làm thuật toán của ta gặp khó? Về cơ bản có ba giải pháp, có lúc chúng phù hợp, có lúc thì không.
One solution is to talk about finite horizon. In this case, we terminate all our episodes after, say, something like t steps. Life is an example of this.
Một giải pháp là dùng tầm nhìn hữu hạn (finite horizon). Trong trường hợp này, ta kết thúc mọi episode sau, chẳng hạn, khoảng t bước. Cuộc sống là một ví dụ.
We don't know what t is, but it's not infinity. And so in this case, you say, OK, car, you've got 100 moves, go. Do your best.
Ta không biết t là bao nhiêu, nhưng nó không phải vô hạn. Và khi đó bạn nói: được rồi xe, bạn có 100 nước đi, bắt đầu. Hãy cố hết sức.
Having a finite horizon can give rise to non-stationary policies where the policy, the optimal action depends on the time left. First thought, that might be weird. You're in some state.
Tầm nhìn hữu hạn có thể dẫn đến chính sách không dừng (non-stationary) trong đó chính sách, tức hành động tối ưu, phụ thuộc vào thời gian còn lại. Thoạt nghe có thể thấy lạ. Bạn đang ở một trạng thái nào đó.
Why does what you should do depend on how much time is left? And the answer is, you've seen this in like every sports game you've ever seen.
Sao việc bạn nên làm lại phụ thuộc vào thời gian còn lại bao nhiêu? Câu trả lời là, bạn đã thấy điều này trong hầu như mọi trận thể thao bạn từng xem.
It's like some crazy stuff happens at the end right before the timer runs out. With these cars, you might risk overheating at the last second because who cares.
Những chuyện điên rồ xảy ra ở cuối trận ngay trước khi đồng hồ hết giờ. Với những chiếc xe này, bạn có thể liều bị quá nhiệt vào giây cuối vì ai quan tâm chứ.
The game is going to end anyway. And so especially as you get close to the end of a finite horizon game, sometimes the policies can change greatly.
Dù sao trò chơi cũng sắp kết thúc. Vì vậy, nhất là khi gần đến cuối của trò chơi tầm nhìn hữu hạn, đôi khi chính sách có thể thay đổi rất nhiều.
But that's one way to make things finite. You just declare the end.
Nhưng đó là một cách để làm cho mọi thứ hữu hạn. Bạn cứ tuyên bố kết thúc.
Another way is to just use discounting. The nice thing about discounting is even though the sequences of rewards can be infinite and their sums can be infinite, their discounted sums usually are not.
Một cách khác là dùng chiết khấu. Điểm hay của chiết khấu là dù chuỗi phần thưởng có thể vô hạn và tổng của chúng có thể vô hạn, thì tổng đã chiết khấu thường thì không.
So if gamma is between 0 and 1 and the rewards themselves are bounded, the sum through some infinite series, magic is going to be bound.
Nên nếu gamma nằm giữa 0 và 1 và bản thân các phần thưởng bị chặn, thì tổng của một chuỗi vô hạn nào đó, thật kỳ diệu, sẽ bị chặn.
And then the last thing is some games have what's called an absorbing state, which is that you look at it and you say, OK, I can actually see that the games can go on forever, but with probability 1, it's going to stop.
Và cuối cùng, một số trò chơi có cái gọi là trạng thái hấp thụ (absorbing state), tức là bạn nhìn vào và nói: được, thực ra trò chơi có thể kéo dài mãi, nhưng với xác suất 1, nó sẽ dừng.
So the probability that you keep lucking out and not having the game end tails off to 0. That's good enough in many cases. All right.
Nên xác suất bạn cứ may mắn mãi mà trò chơi không kết thúc sẽ giảm dần về 0. Trong nhiều trường hợp thế là đủ tốt. Được rồi.
We're going to recap, we're going to break, and then I'm going to give you some algorithms. So to recap, Markov decision processes. They're like nondeterministic search problems.
Ta sẽ tóm tắt, nghỉ giải lao, rồi tôi sẽ giới thiệu một số thuật toán. Tóm lại, các quá trình quyết định Markov. Chúng giống như các bài toán tìm kiếm không tất định.
They've got a set of states just like search, including a start state.
Chúng có một tập trạng thái giống như tìm kiếm, bao gồm một trạng thái bắt đầu.
They have a set of actions, just like search except now instead of the action taking you from an S to an S prime, it can take you to multiple S primes.
Chúng có một tập hành động, giống tìm kiếm, nhưng giờ thay vì hành động đưa bạn từ S sang một S phẩy, nó có thể đưa bạn đến nhiều S phẩy.
So we have a transition function, which tells you for each S prime how likely it is, possibly 0 if it's not going to happen.
Vì vậy ta có hàm chuyển, hàm này cho biết với mỗi S phẩy thì khả năng xảy ra là bao nhiêu, có thể bằng 0 nếu nó không xảy ra.
And for each transition, SA S prime, there's a reward that tells you how many points you get on that transition right then and then a discount, which tells you how to add up a sequence in the appropriate way by multiplying in a discount each time.
Và với mỗi bước chuyển, S A S phẩy, có một phần thưởng cho biết bạn nhận được bao nhiêu điểm ngay ở bước chuyển đó và một hệ số chiết khấu, cho biết cách cộng một chuỗi theo đúng cách bằng cách nhân thêm hệ số chiết khấu mỗi lần.
The quantities that we've talked about so far, we've talked about policies, which is a mapping of states to actions and utilities, which is a sum of discounted rewards across the entire game of the MDP.
Các đại lượng ta đã nói đến cho tới giờ, ta đã nói về chính sách, là ánh xạ từ trạng thái sang hành động, và độ hữu dụng, là tổng các phần thưởng đã chiết khấu trong toàn bộ trò chơi của MDP.
We're going to take a quick break, and then we're going to talk about how to solve them, which will lead into reinforcement learning after the next lecture.
Ta sẽ nghỉ giải lao nhanh, rồi sẽ nói về cách giải chúng, điều này sẽ dẫn tới học tăng cường sau bài giảng tiếp theo.
Two-minute break, quick break, and then we'll start again.
Nghỉ hai phút, giải lao nhanh, rồi ta bắt đầu lại.
All right. I don't know if that was actually two minutes. It felt like two minutes. It was about two minutes.
Được rồi. Không biết đó có thật là hai phút không. Cảm giác như hai phút. Khoảng hai phút.
All right. We're talking about solving MDPs. How do you solve an MDP?
Được rồi. Chúng ta đang nói về việc giải MDP. Làm sao để giải một MDP?
The way you solve an MDP, the input, this is really important because in reinforcement learning, it's going to look so similar, and it's going to be so different.
Cách giải một MDP, đầu vào là gì, điều này rất quan trọng vì trong học tăng cường, mọi thứ trông sẽ rất giống nhau, nhưng thực ra lại rất khác.
The input, when you solve an MDP is an MDP.
Đầu vào khi giải một MDP chính là một MDP.
That means somebody tells you, hey, here are the states, here the actions, here the transition probabilities, here are the awards, and then your output is a policy.
Nghĩa là ai đó đưa cho bạn: đây là các trạng thái, đây là các hành động, đây là xác suất chuyển, đây là các phần thưởng, và đầu ra của bạn là một chính sách.
It's a mapping from each state to the optimal action.
Đó là ánh xạ từ mỗi trạng thái sang hành động tối ưu.
In order to do that, we need to define a whole bunch of quantities that are going to be useful in this computation that actually are going to be very parallel to things that you computed with expectimax search.
Để làm được vậy, ta cần định nghĩa một loạt đại lượng sẽ hữu ích cho phép tính này, và chúng sẽ song song với những thứ bạn đã tính trong tìm kiếm expectimax.
We're going to have to define them, and then we're going to have to mathematically state how they relate to each other, which will then turn into algorithms for computing them.
Ta phải định nghĩa chúng, rồi phát biểu bằng toán học chúng liên hệ với nhau thế nào, và từ đó sẽ thành các thuật toán để tính chúng.
So here are some important quantities associated with an MDP. We'll show this for Grid World first.
Đây là vài đại lượng quan trọng gắn với một MDP. Ta sẽ minh họa trước với Grid World.
The first is the value of a state, and this is going to turn out to be both the utility of being in that state and acting optimally, and it's also going to correspond to what expectimax would have produced.
Đầu tiên là giá trị của một trạng thái, nó sẽ vừa là độ hữu dụng của việc ở trong trạng thái đó và hành động tối ưu, vừa tương ứng với kết quả mà expectimax sẽ cho ra.
So values, the written v, there is a value for each state. v as a value. v* is the optimal value.
Giá trị, ký hiệu v, mỗi trạng thái có một giá trị. v là value. v* là giá trị tối ưu.
That means the value you will achieve, on average, because it's going to be an expected value, if you act optimally starting from state S. Some states will have higher values than others because some states are better to be in than others.
Nghĩa là giá trị bạn đạt được, trung bình, vì đây là một giá trị kỳ vọng, nếu bạn hành động tối ưu bắt đầu từ trạng thái S. Một số trạng thái có giá trị cao hơn những trạng thái khác vì có trạng thái tốt hơn để đứng vào.
It's much better to be right next to the goal than right next to the fire pit. Remember, there are also Q states. S is a state.
Đứng ngay cạnh đích tốt hơn nhiều so với đứng ngay cạnh hố lửa. Nhớ rằng còn có các trạng thái Q. S là một trạng thái.
It corresponds to a max node and expectimax, and it has a value. That value is what you would do if you acted optimally from that point.
Nó tương ứng với nút max trong expectimax, và có một giá trị. Giá trị đó là kết quả nếu bạn hành động tối ưu từ thời điểm đó.
A Q state corresponds to a chance node in the same sense that there are good states and bad states and you just have to compute the value of each particular state.
Trạng thái Q tương ứng với nút may rủi, theo nghĩa có trạng thái tốt và trạng thái xấu, và bạn chỉ cần tính giá trị của từng trạng thái cụ thể.
Like you're in this state, you could wish you were in another state, but the state has whatever value it has. Q states have values. You're in the state, and you're performing this action.
Như khi bạn đang ở trạng thái này, có thể ước mình ở trạng thái khác, nhưng trạng thái vẫn có giá trị của nó. Các trạng thái Q cũng có giá trị. Bạn đang ở một trạng thái và thực hiện hành động này.
The value of that Q state is the expected utility of starting out having taken action A from state S and acting optimally thereafter.
Giá trị của trạng thái Q đó là độ hữu dụng kỳ vọng khi bắt đầu bằng hành động A từ trạng thái S rồi sau đó hành động tối ưu.
In the same way that there are some states that are good and some states that are bad, there are some Q states that are good, and there are some Q states that are bad.
Giống như có trạng thái tốt và trạng thái xấu, thì cũng có trạng thái Q tốt, và có trạng thái Q xấu.
Their values have to do with what will happen if from that state and Q state you act optimally in the future. There is then an optimal policy. Pi is a policy.
Giá trị của chúng liên quan đến việc điều gì xảy ra nếu từ trạng thái và trạng thái Q đó bạn hành động tối ưu trong tương lai. Sau đó là chính sách tối ưu. Pi là một chính sách.
Pi* is an optimal policy. Pi* of S is the action recommended by this optimum policy from state S. And it will be something like in the state, go north.
Pi* là chính sách tối ưu. Pi*(S) là hành động mà chính sách tối ưu này đề xuất tại trạng thái S. Ví dụ như ở trạng thái này, đi lên phía bắc.
So let's take a look at these in Grid World.
Giờ hãy xem những thứ này trong Grid World.
All right. So here is Grid World. This is a particular setting.
Được rồi. Đây là Grid World. Đây là một thiết lập cụ thể.
To know these particular values, you need to know what was the noise probability, what was the living reward, what was the discount, and so on.
Để biết các giá trị cụ thể này, bạn cần biết xác suất nhiễu là bao nhiêu, phần thưởng sống là bao nhiêu, hệ số chiết khấu là bao nhiêu, v.v.
But qualitatively here, you can see that if you are in this state, your value is 1 because you only have one possible future. You take exit, you exit, you get plus 1.
Nhưng về mặt định tính, bạn có thể thấy nếu ở trạng thái này thì giá trị là 1 vì bạn chỉ có một tương lai duy nhất. Bạn thoát ra, và nhận cộng 1.
If you're in the pit, the value is negative 1. You only have one future, exit minus 1.
Nếu ở trong hố, giá trị là âm 1. Cũng chỉ một tương lai, thoát ra với âm 1.
Everywhere else, these values represent optimal play from that point, and then all the possible outcomes have various probabilities. This is an average as an expectation.
Ở mọi chỗ khác, các giá trị này biểu diễn lối chơi tối ưu từ điểm đó, và mọi kết quả có thể xảy ra đều có những xác suất khác nhau. Đây là giá trị trung bình, tức kỳ vọng.
We'll figure out how to compute that expectation, but from here, this means that on average sometimes you'll accidentally slip and fall into from — this 0.85 includes both going straight into the good exit and exiting.
Ta sẽ tìm cách tính kỳ vọng đó, nhưng ở đây nghĩa là trung bình có lúc bạn vô tình trượt và rơi vào — con số 0.85 này gồm cả việc đi thẳng vào lối thoát tốt và thoát ra.
It also includes slipping here trying to get back, but slipping again and then falling into the fire and so on.
Nó cũng gồm cả việc trượt ở đây khi cố quay lại, rồi lại trượt lần nữa và rơi vào hố lửa, v.v.
And these arrows, you can see the numbers are the sum of discounted rewards, including the living award and the final reward, under the optimal policy. The optional policy is shown by the arrows.
Còn với các mũi tên này, các con số là tổng phần thưởng đã chiết khấu, gồm cả phần thưởng sống và phần thưởng cuối, theo chính sách tối ưu. Chính sách tối ưu được thể hiện bằng các mũi tên.
So those are the values of the states. And so you look. This state is really good because you're just going to get a good reward.
Đó là giá trị của các trạng thái. Bạn nhìn xem. Trạng thái này rất tốt vì bạn sắp nhận được phần thưởng tốt.
This state is pretty good because unless you get really unlucky, you're going to get a good reward pretty soon.
Trạng thái này khá tốt vì trừ khi quá xui, bạn sẽ sớm nhận được phần thưởng tốt.
The state down here in the lower left, the one we had sometimes been calling the start state, its value is only about 0.5. Why?
Trạng thái ở dưới góc trái này, cái mà đôi khi ta gọi là trạng thái bắt đầu, giá trị chỉ khoảng 0.5. Tại sao?
Well, by the time you make your way up, some combination of living reward and probability of falling into the pit and discount have whittled away that plus 1 and averaged in a whole bunch of other possible outcomes, and so your state's value is lower.
Vì khi bạn đi lên được tới đó, sự kết hợp của phần thưởng sống, xác suất rơi vào hố và hệ số chiết khấu đã làm hao mòn mức cộng 1 đó và lấy trung bình với hàng loạt kết quả khả dĩ khác, nên giá trị trạng thái này thấp hơn.
It is better to be in the state than the state.
Ở trạng thái này tốt hơn ở trạng thái kia.
But the whole point of computing these values is not to notice that this is a bad state, but rather to figure out what is the optimal thing to do if you're there.
Nhưng mục đích của việc tính các giá trị này không phải để nhận ra đây là trạng thái xấu, mà để tìm ra việc tối ưu cần làm khi bạn đang ở đó.
So those are values. Every state has a number, and the farther you are from the goal in Grid World, in general, the worse your value is going to be.
Đó là các giá trị. Mỗi trạng thái có một con số, và càng xa đích trong Grid World, nói chung giá trị càng tệ.
What is that? These are the Q values. So each square is a state, and in each square there are four actions north, south, east, and west.
Còn đây là gì? Đây là các giá trị Q. Mỗi ô vuông là một trạng thái, và trong mỗi ô có bốn hành động: bắc, nam, đông và tây.
So each of these little pie slices represents that action. The top pie slice is the north action.
Mỗi múi nhỏ hình quạt này biểu diễn một hành động. Múi trên cùng là hành động đi bắc.
And so for example, you can see that that 0.85 from the state up here corresponds to taking the action east.
Ví dụ, các em thấy số 0.85 ở trạng thái phía trên này ứng với hành động đi đông.
So the value of the Q state, 3, 3; action east is 0.85. There are other Q values for that state.
Vậy giá trị của trạng thái Q (3, 3), hành động đông là 0.85. Trạng thái đó còn có các giá trị Q khác.
In the same way that states can be good states or bad states and you'd rather, if you can control it, be in the good states, there's good actions and bad actions.
Cũng như có trạng thái tốt và trạng thái xấu, và nếu kiểm soát được thì ta muốn ở trạng thái tốt, thì cũng có hành động tốt và hành động xấu.
And if you can control it, you'd rather take the good actions.
Và nếu kiểm soát được, ta muốn chọn hành động tốt.
And so if you go south here, you're going to end up in a worse state, and then even if you act optimally thereafter, you're not going to get that same 0.85.
Nên nếu đi về phía nam ở đây, ta sẽ rơi vào trạng thái tệ hơn, và dù sau đó ta hành động tối ưu, ta cũng không đạt lại được 0.85 đó.
And so you can see the Q value here is lower than it is for the other actions branching out of that state.
Vì vậy các em thấy giá trị Q ở đây thấp hơn so với các hành động khác tỏa ra từ trạng thái đó.
And I just had a little episode.
Và tôi vừa lỡ lời một chút.
So those are the values. The fundamental operation in solving MDPs is to compute the value. And here we mean expectimax or expected value of a state.
Đó là các giá trị. Phép toán cơ bản khi giải MDP là tính giá trị. Ở đây ý là giá trị expectimax, tức giá trị kỳ vọng của một trạng thái.
So we need to know the expected utility under optimum actions, and that's going to be an average sum of discounted rewards.
Tức là cần biết độ hữu dụng kỳ vọng khi hành động tối ưu, và đó là trung bình của tổng các phần thưởng đã chiết khấu.
Expectimax computed that, but right now we're going to try to find another algorithm, and in order to do that, we're going to write down recursively some properties that hold between these values that will let us formulate an algorithm.
Expectimax tính được điều đó, nhưng bây giờ ta sẽ tìm một thuật toán khác, và để làm vậy, ta sẽ viết ra theo đệ quy một số tính chất giữa các giá trị này, giúp ta xây dựng được thuật toán.
So let's write this in blue. The value of a state. So let's talk about the optimal value of some state, S. We're always going to think about this little expectimax future.
Ta viết bằng màu xanh. Giá trị của một trạng thái. Hãy nói về giá trị tối ưu của một trạng thái S nào đó. Ta luôn nghĩ đến cây expectimax nhỏ của tương lai.
How good is it to be at some state S? Well, I don't know, but I can relate it to some other quantities.
Ở trạng thái S thì tốt đến mức nào? Tôi chưa biết, nhưng có thể liên hệ nó với các đại lượng khác.
I can relate it to how good other states and Q states are.
Tôi có thể liên hệ nó với độ tốt của các trạng thái và trạng thái Q khác.
So in particular, I could write down that the value of being in state S is just the maximum over all of the actions I can take from that state of the optimum Q value of S, A. That just says that the expectimax value of this max node is the max over these, of the Q values of those Q states.
Cụ thể, tôi có thể viết rằng giá trị của việc ở trạng thái S là giá trị lớn nhất trên mọi hành động có thể làm từ trạng thái đó của giá trị Q tối ưu của S, A. Nghĩa là giá trị expectimax của nút max này là max của các giá trị Q của những trạng thái Q đó. nút là giá trị lớn nhất (max) trong các giá trị Q của những trạng thái Q đó.
All right. Well, that doesn't really help because I don't know Q* either.
Được rồi. Nhưng thế chưa giúp được gì vì tôi cũng chưa biết Q*.
So what is the value, or you can think about it as what would I get if I ran expectimax from this chance node, S, A. I can write that down too.
Vậy giá trị đó là gì, hay có thể hiểu là tôi sẽ nhận được gì nếu chạy expectimax từ nút ngẫu nhiên S, A. Tôi cũng viết ra được.
So I can go, change colors for chance node here.
Tôi đổi màu cho nút ngẫu nhiên ở đây.
The expectimax value of being in state S and having chosen A, regardless of whether A was, in fact, a good action, you have to compute this for all of them.
Giá trị expectimax của việc ở trạng thái S và đã chọn A, bất kể A có thật sự là hành động tốt hay không, ta phải tính điều này cho tất cả.
Well, I don't know why I got into state S, and I don't know why I took it upon myself to choose A, but I do know what's going to happen next.
Tôi không biết vì sao mình vào trạng thái S, cũng không biết vì sao mình chọn A, nhưng tôi biết điều gì sẽ xảy ra tiếp theo.
The average outcome I'm going to get is always going to break down into, I'm going to get a reward from state S from action A.
Kết quả trung bình tôi nhận được luôn tách thành: tôi sẽ nhận một phần thưởng từ trạng thái S với hành động A.
That reward is going to depend on the S prime I land in. So I get a reward for the transition. Who knows which S prime it is, but I'm going to get a reward.
Phần thưởng đó phụ thuộc vào S' mà tôi rơi vào. Vậy tôi nhận phần thưởng cho bước chuyển. Chưa biết S' là gì, nhưng tôi sẽ nhận một phần thưởng.
And then when I land in S prime, that's down here, I'm going to then act optimally. So what is that?
Rồi khi tôi đến S', ở dưới này, tôi sẽ hành động tối ưu. Vậy nó là gì?
The optimal action from state S prime is going to give me a score of v* S prime in the future.
Hành động tối ưu từ trạng thái S' sẽ cho tôi điểm số v* của S' trong tương lai.
So my score from S, A is the instantaneous reward R of SA S prime plus the future after more reward v* of S prime. Two more things.
Vậy điểm của tôi từ S, A là phần thưởng tức thời R(S, A, S') cộng với phần thưởng tương lai v*(S'). Còn hai điều nữa.
One, that future is discounted, so I stick a gamma there. The second thing is I don't know which S prime is going to happen.
Một, tương lai bị chiết khấu, nên tôi thêm gamma vào. Hai, tôi không biết S' nào sẽ xảy ra.
I'm taking A, but I don't know what outcome S prime I'm going to get. I have to average over them. The way I average over them is I have to take an average.
Tôi chọn A, nhưng không biết mình sẽ nhận kết quả S' nào. Tôi phải lấy trung bình. Cách lấy trung bình là tính trung bình có trọng số.
I sum them all up, weighted by the transition probabilities T of AS prime, and this thing here is the probability of S prime given S, A.
Tôi cộng tất cả lại, có trọng số là xác suất chuyển T(S, A, S'), và đại lượng này là xác suất của S' khi biết S, A.
So here's a system of equations.
Đây là một hệ phương trình.
People often inline these things. So you will usually see these things inlined. When you see them inlined, it says, what is the expectimax value of a state?
Người ta thường viết gộp các thứ này lại. Nên các em thường sẽ thấy dạng viết gộp. Khi đó nó nói rằng, giá trị expectimax của một trạng thái là gì?
Well, it is the instantaneous reward that you will get in the next time step plus the future reward from the successor state. The future is discounted.
Đó là phần thưởng tức thời nhận được ở bước thời gian kế tiếp cộng phần thưởng tương lai từ trạng thái kế tiếp. Tương lai bị chiết khấu.
I have to average over all of the possible consequences of my action, so I have to sum over S primes.
Tôi phải lấy trung bình trên mọi hệ quả có thể của hành động, nên phải lấy tổng theo S'.
I have to take the weighted sum of them, and then, of course, A is under my control, so I take whichever action is best.
Tôi lấy tổng có trọng số của chúng, và dĩ nhiên A do tôi kiểm soát, nên tôi chọn hành động tốt nhất.
This defines a system of equations that relate v* of states to v* of other states.
Đây định nghĩa một hệ phương trình liên hệ v* của các trạng thái với v* của các trạng thái khác.
And you look at that and you say how does that help me, because now I've written something I don't know in terms of something else I don't know.
Nhìn vào đó các em sẽ hỏi nó giúp được gì, vì giờ tôi viết một đại lượng chưa biết theo một đại lượng chưa biết khác.
Moreover, because of that max, this is not a linear system of equations. So you can't just invert some matrix or something like that.
Hơn nữa, vì có phép max, nên đây không phải hệ phương trình tuyến tính. Nên không thể chỉ đảo một ma trận nào đó là xong.
So we're going to talk about how to solve these equations, but this is the core system of equations. These are called the Bellman equations.
Ta sẽ bàn cách giải các phương trình này, nhưng đây là hệ phương trình cốt lõi. Đây gọi là các phương trình Bellman.
These are the core recursive definitions of values and Q values of states.
Đây là các định nghĩa đệ quy cốt lõi của giá trị và giá trị Q của các trạng thái.
These are really, really good things to stare at until you are totally, totally sure you get what they're saying because you will see variations of these over and over and over again.
Đây thật sự là thứ rất đáng nhìn kỹ cho đến khi các em hoàn toàn chắc chắn đã hiểu chúng nói gì, vì các em sẽ gặp các biến thể của chúng hết lần này đến lần khác.
So you can stare at them. I'm going to erase them and replace them with beautiful latex so you can see on your slides because no one should have to read my handwriting.
Nên các em cứ nhìn kỹ chúng. Thầy sẽ xóa đi và thay bằng bản latex đẹp trên slide để các em dễ xem, vì không ai phải đọc chữ viết tay của thầy.
All right. So that was a recursive definition of these values in terms of other optimal quantities.
Được rồi. Đó là một định nghĩa đệ quy của các giá trị này theo các đại lượng tối ưu khác.
I can erase that. I can define the optimal value of a state in terms of the optimal values of Q states.
Thầy xóa cái này. Ta có thể định nghĩa giá trị tối ưu của một trạng thái theo các giá trị tối ưu của các trạng thái Q.
I can define the optimum value of Q states in terms of the optimal values of states using these lookahead equations that relate values of states to values of states one step ahead in time.
Ta cũng định nghĩa giá trị tối ưu của trạng thái Q theo các giá trị tối ưu của các trạng thái, dùng các phương trình nhìn trước này, liên hệ giá trị của trạng thái với giá trị của các trạng thái ở bước thời gian kế tiếp.
And again, these are called one-step lookahead equations or Bellman equations. Let's look at that racing search tree again.
Và những phương trình này gọi là phương trình nhìn trước một bước hay phương trình Bellman. Ta xem lại cây tìm kiếm của bài đua xe.
So if we look at this, well, I could run expectimax on this, but when I look at this, I think maybe there is a better algorithm because those same states seem to appear over and over again.
Nhìn vào đây, ta có thể chạy expectimax, nhưng thầy nghĩ có lẽ có thuật toán tốt hơn vì các trạng thái đó dường như xuất hiện lặp đi lặp lại.
And as we know, their optimal values are all interrelated by the system of equations.
Và như ta biết, các giá trị tối ưu của chúng đều liên hệ với nhau qua một hệ phương trình.
So this is the search tree to depth 1. If I continue it forward, that tree is going to grow. It's going to grow rapidly. It's going to grow exponentially fast.
Đây là cây tìm kiếm đến độ sâu 1. Nếu tiếp tục mở rộng, cây sẽ lớn dần. Nó sẽ lớn rất nhanh. Nó sẽ lớn nhanh theo hàm mũ.
And if you look at that, you think it can't possibly be right to run expectimax over this whole giant tree that's growing exponentially fast, but, in fact, only has three states occurring over and over again.
Nhìn vậy, ta thấy chắc chắn không thể đúng khi chạy expectimax trên cả cây khổng lồ này, vốn lớn theo hàm mũ, mà thật ra chỉ có ba trạng thái xuất hiện lặp đi lặp lại.
It's a tiny little system of equations. There should be a way to more efficiently just directly connect all these quantities and compute them.
Đó chỉ là một hệ phương trình nhỏ xíu. Phải có cách hiệu quả hơn để nối trực tiếp các đại lượng này và tính chúng.
And that's what we're going to talk about now is an algorithm for this. So why should we not just run expectimax? Well, problem one, we're doing way too much work.
Và đó là điều ta sẽ nói bây giờ, một thuật toán cho việc này. Vậy sao không chạy expectimax? Vấn đề một: ta làm việc quá nhiều.
Among other things, this whole subtree is exactly the same as this whole subtree. So there's at a minimum, there is duplicated work. And in fact, there's exponentially duplicated work.
Chẳng hạn, cả cây con này giống hệt cả cây con kia. Vậy ít nhất cũng có việc bị lặp. Thật ra, việc lặp này tăng theo hàm mũ.
That's one problem. And so that's the state's repeated problem. The second, this tree is actually infinite, so running expectimax on an infinite tree is a bad idea. And can you fix these problems?
Đó là một vấn đề. Đó là vấn đề lặp trạng thái. Thứ hai, cây này thực ra vô hạn, nên chạy expectimax trên cây vô hạn là ý tồi. Vậy ta có sửa được những vấn đề này không?
Right now, if I stop the lecture, you could fix all these problems. You could say, all right, well, look, why don't we catch this stuff. Once I compute something, why don't I cash that.
Ngay lúc này, nếu thầy dừng bài giảng, các em đã có thể sửa hết. Các em sẽ nói: thôi, sao ta không lưu lại những thứ này. Tính được gì thì sao không cache lại.
And actually, instead of doing an infinite tree, didn't we talk about how things deep in the tree if they're discounted don't matter. I'll just truncate this at depth 100.
Và thay vì dùng cây vô hạn, chẳng phải ta đã nói những gì nằm sâu trong cây, nếu bị chiết khấu, thì không quan trọng sao. Cứ cắt cây ở độ sâu 100.
Well, actually, if you put these ideas together, you will have more or less reinvented the algorithm we're going to talk about now, which is an algorithm called value iteration.
Thật ra, nếu ghép những ý này lại, các em đã gần như phát minh lại thuật toán ta sắp nói, đó là thuật toán gọi là lặp giá trị (value iteration).
But the algorithm we have works the other direction.
Nhưng thuật toán của ta chạy theo chiều ngược lại.
Rather than starting at the top, doing things recursively, caching as we go, and trying to depth limit as we go, the algorithm we're going to have is going to start at the bottom and work our way upward until we decide that the tree is deep enough.
Thay vì bắt đầu từ trên, làm đệ quy, vừa đi vừa cache và giới hạn độ sâu, thuật toán của ta sẽ bắt đầu từ đáy rồi đi ngược lên cho đến khi ta thấy cây đủ sâu.
The key idea we're going to need in order for us to have this algorithm value iteration is an idea of time limited values. And so what we're going to do is where v*.
Ý tưởng then chốt để có thuật toán lặp giá trị này là giá trị bị giới hạn thời gian. Ta sẽ làm như sau, với v*.
So v* was a very tricky quantity. It is the value of being in a state and acting optimally. That's very tricky because that could go on forever. It could be an infinite depth thing.
v* là một đại lượng rất khó. Đó là giá trị của việc ở một trạng thái và hành động tối ưu. Khó vì nó có thể kéo dài mãi mãi. Nó có thể có độ sâu vô hạn.
We're going to define something much more tractable, which is v sub k of a state.
Ta sẽ định nghĩa một đại lượng dễ xử lý hơn nhiều, là v chỉ số k của một trạng thái.
v sub k is the optimal value of if you start in that state and play optimally, it's the expected value of starting that state and playing optimally.
v chỉ số k là giá trị tối ưu nếu bắt đầu ở trạng thái đó và chơi tối ưu, tức là giá trị kỳ vọng khi bắt đầu từ trạng thái đó và chơi tối ưu, nếu trò chơi kết thúc sau k bước thời gian nữa.
If the game is going to end in k more time steps. Why is this useful? This is really useful.
Vì sao điều này hữu ích? Nó rất hữu ích.
Now, suddenly that tree is no longer infinite, and this quantity is exactly what a depth, K, expected max would give if you started at S, so we already have an algorithm.
Giờ cây đó đột nhiên không còn vô hạn, và đại lượng này chính xác là kết quả của expectimax độ sâu K nếu bắt đầu từ S, vậy là ta đã có một thuật toán.
And in fact, if we save repeated work, we'll have an even better algorithm in a second.
Và nếu ta tránh lặp việc, lát nữa ta sẽ có thuật toán còn tốt hơn.
So we take a look at this tree, and we say, well, looking at this, there is a computation from say, state blue of what can happen in two time steps.
Ta nhìn cây này và nói, ở đây có một phép tính, chẳng hạn từ trạng thái xanh, về những gì có thể xảy ra trong hai bước. từ, chẳng hạn, trạng thái màu xanh, trong hai bước thời gian.
This is that tree.
Đây là cây đó.
And if we run expectimax over that, it will compute the average rewards I will get if I act optimally, I do the right thing at all the max nodes, and the game ends after 2.
Nếu chạy expectimax trên đó, nó sẽ tính phần thưởng trung bình nhận được nếu hành động tối ưu, làm đúng ở mọi nút max, và trò chơi kết thúc sau 2 bước.
So I can just think of this little tree as v2. That the root is of depth 2, and it has some value.
Nên ta có thể xem cây nhỏ này là v2. Gốc có độ sâu 2 và có một giá trị nào đó.
And if I see this tree occur 100 times, I can just keep plugging that value in, and it represents the value of being in state blue, which was cool and acting optimally for two time steps.
Nếu thấy cây này xuất hiện 100 lần, ta cứ thế điền giá trị đó vào, và nó biểu diễn giá trị của việc ở trạng thái xanh, là trạng thái cool, và hành động tối ưu trong hai bước thời gian.
So let's take a look how this looks in Grid World.
Ta xem điều này trông thế nào trong Grid World.
All right. So here is our favorite example of the grid with a good and a bad exit. v0 is very important to understand, and it's also very simple.
Được rồi. Đây là ví dụ quen thuộc của ta, lưới có một lối thoát tốt và một lối thoát xấu. v0 rất quan trọng cần hiểu, và cũng rất đơn giản.
If I have 0 times steps, what's a time step? It's a reward. 0 means 0 more rewards. What value will I get under optimal play from the good exit?
Nếu có 0 bước thời gian, một bước thời gian là gì? Là một phần thưởng. 0 nghĩa là không còn phần thưởng nào nữa. Chơi tối ưu từ lối thoát tốt thì ta nhận được giá trị bao nhiêu?
0. No time to get a reward. Bad exit, 0. Lower left corner, 0.
0. Không còn thời gian để nhận phần thưởng. Lối thoát xấu, 0. Góc dưới bên trái, 0.
Everything is 0 because there is 0 or more rewards, so my future score from that state is 0. Easy but not helpful.
Mọi giá trị đều bằng 0 vì có 0 hoặc nhiều phần thưởng hơn, nên điểm tương lai của tôi từ trạng thái đó là 0. Dễ nhưng không hữu ích.
But now I can ask, what about if I allow myself one more reward before I end the game? Well, some of these states will no longer have 0 optimal value.
Nhưng giờ tôi có thể hỏi: nếu cho phép thêm một phần thưởng nữa trước khi kết thúc trò chơi thì sao? Một số trạng thái này sẽ không còn giá trị tối ưu bằng 0 nữa.
Like the upper right, what can I do in one time step? Well, there's only one thing I can do in one step, which is call exit, and I get plus 1.
Như ô phía trên bên phải, trong một bước thời gian tôi làm được gì? Chỉ có một việc tôi làm được trong một bước, đó là gọi exit, và tôi nhận cộng 1.
How about the firepit? What can I do in one time step? There's only one choice according to the rules of the game, take exit and get minus 1.
Còn hố lửa thì sao? Trong một bước thời gian tôi làm được gì? Chỉ có một lựa chọn theo luật chơi: thoát và nhận trừ 1.
Anywhere else, what can I do in one time step? I can move and get the living reward. If the living reward is 0, these are the values for one time step.
Ở những chỗ khác, trong một bước tôi làm được gì? Tôi có thể di chuyển và nhận phần thưởng sống. Nếu phần thưởng sống bằng 0, đây là các giá trị cho một bước thời gian.
So this is v sub 1. These are the values achievable under optimal play on average for one more time step. Now what if I had two time steps?
Đây là v chỉ số 1. Đây là các giá trị đạt được trung bình khi chơi tối ưu trong một bước thời gian nữa. Còn nếu tôi có hai bước thời gian thì sao?
Think about it.
Hãy nghĩ thử.
Some of these places like the lower left, there's just no where you can get in two time steps that's going to give you any reward other than 0, presuming the living reward is 0.
Một số ô như ô dưới bên trái, trong hai bước không có chỗ nào cho bạn phần thưởng nào khác ngoài 0, giả sử phần thưởng sống bằng 0.
But here's v sub 2. So there's two interesting things that happened. One, the upper right square here became 0.72. Why?
Đây là v chỉ số 2. Có hai điều thú vị đã xảy ra. Một, ô phía trên bên phải ở đây thành 0,72. Tại sao?
What does that represent? Well, what can happen in two time steps? I can move east, succeed, and take the exit and get plus 1. That has a certain probability.
Nó biểu diễn điều gì? Trong hai bước thời gian có thể xảy ra gì? Tôi có thể đi sang đông, thành công, thoát và nhận cộng 1. Việc đó có một xác suất nhất định.
I can also move east, fail, slip, go in the wrong direction, try to move back, and run out of time. That's going to have value 0.
Tôi cũng có thể đi sang đông nhưng thất bại, bị trượt, đi sai hướng, cố quay lại, rồi hết thời gian. Trường hợp đó có giá trị 0.
And so that 0.72 represents a mixture of things where I didn't quite make it to an exit and the one case where I just barely made it into the exit in time, and when you average all that all together you, get 0.72.
Vậy 0,72 biểu diễn một hỗn hợp, trong đó có những lần tôi không kịp tới lối thoát và một trường hợp tôi vừa kịp tới lối thoát đúng lúc, và khi lấy trung bình tất cả, bạn được 0,72.
The more interesting one is the 0 right below it, the one right next to the fire pit. Why is that 0? Because I can exit the game in two times steps.
Điều thú vị hơn là số 0 ngay bên dưới nó, ô nằm cạnh hố lửa. Tại sao nó bằng 0? Vì tôi có thể thoát trò chơi trong hai bước.
I could jump into the pit and get a minus 1, but that's not optimal play. So under optimal play, I will avoid that.
Tôi có thể nhảy vào hố và nhận trừ 1, nhưng đó không phải chơi tối ưu. Nên khi chơi tối ưu, tôi sẽ tránh việc đó.
I will take some other sequence of actions, which does not include that, and I can basically guarantee myself an average of 0, where I can make sure I don't actually fall in.
Tôi sẽ chọn một chuỗi hành động khác không gồm việc đó, và về cơ bản tôi đảm bảo được trung bình bằng 0, vì tôi có thể chắc chắn không rơi vào hố.
And then as I look farther into the future — four, five, six — you can see that eventually I'm looking far enough into the future that even from the lower left, I can start to see ways of eventually getting to a good reward.
Rồi khi nhìn xa hơn về tương lai, bốn, năm, sáu bước, bạn thấy cuối cùng tôi nhìn đủ xa đến mức ngay cả từ góc dưới bên trái, tôi bắt đầu thấy các cách để cuối cùng đạt được phần thưởng tốt.
Now, I can't see all of them because some of the ways of getting to that good reward are going to take more than six or more than seven or more than eight time steps because they involve slipping or some other thing that's going to slow me down.
Tôi chưa thấy hết các cách, vì một số cách đạt phần thưởng tốt đó sẽ mất hơn sáu, hơn bảy hay hơn tám bước vì có trượt hoặc chuyện gì khác làm tôi chậm lại.
But as I do this and I push this out, eventually, this will stop. And looking farther and farther into the future eventually will not contribute much if there's a discount.
Nhưng khi tôi cứ đẩy xa dần như vậy, cuối cùng nó sẽ dừng. Và nhìn càng xa về tương lai thì cuối cùng cũng đóng góp không nhiều nếu có hệ số chiết khấu.
I'm going to show you one more thing on this. I'll show that same thing again.
Tôi sẽ cho bạn xem thêm một điều nữa. Tôi chiếu lại đúng cái đó.
I want you to watch, not the values because the green will bleed outward, I want you to watch the arrows. So first they change a lot.
Tôi muốn bạn xem không phải các giá trị vì màu xanh sẽ lan ra ngoài, mà hãy xem các mũi tên. Lúc đầu chúng đổi nhiều.
But once I get to here, watch the arrows. The numbers are still fine tuning, but after a certain point, the arrows are done flipping.
Nhưng khi tới đây, hãy xem các mũi tên. Các con số vẫn còn tinh chỉnh, nhưng sau một thời điểm, các mũi tên không đổi chiều nữa.
And this is a common thing that as I look deeper and deeper, I have these residual rewards that I can keep accumulating forever. It's like computing the limit of a series.
Đây là điều thường gặp: khi tôi nhìn sâu hơn nữa, có những phần thưởng còn lại mà tôi có thể cứ tích lũy mãi. Giống như tính giới hạn của một chuỗi.
I keep accumulating, but the actual policies implied by that depth of search will eventually stabilize, and that often happens long before the values themselves do.
Tôi cứ tích lũy, nhưng các chính sách thực sự suy ra từ độ sâu tìm kiếm đó cuối cùng sẽ ổn định, và điều đó thường xảy ra lâu trước khi bản thân các giá trị ổn định.
So this actually gives us all we need to define the core algorithm here, which we'll define now and then we will extend and pick up next time.
Vậy điều này cho ta mọi thứ cần thiết để định nghĩa thuật toán cốt lõi, mà ta sẽ định nghĩa ngay bây giờ rồi sẽ mở rộng và tiếp tục vào buổi sau.
And that is, I look at this tree of all the possible futures in ways this game can play out, which includes the same repeating units over and over again.
Đó là: tôi nhìn cây của mọi tương lai có thể mà trò chơi này diễn ra, và cây gồm các đơn vị giống nhau lặp đi lặp lại.
And I look at the bottom, and I say, whats down there? What are these little expectimax fragments? Well, they're all depth 0 trees. They don't have any rewards in them.
Tôi nhìn xuống đáy và hỏi: dưới đó có gì? Những mảnh expectimax nhỏ này là gì? Chúng đều là các cây độ sâu 0. Trong đó không có phần thưởng nào.
So I know I can summarize this exponentially large number of leaves with just the terminal values, v0, which we know are all 0.
Nên tôi biết có thể tóm tắt số lượng lá lớn theo hàm mũ này chỉ bằng các giá trị kết thúc, v0, mà ta biết đều bằng 0.
And then if I look above that, there are a bunch of repeated subtrees. These are the v1 trees over and over and over and over again.
Rồi nếu nhìn lên trên đó, có một loạt cây con lặp lại. Đó là các cây v1 lặp đi lặp lại mãi.
So I can summarize that whole stripe across this tree by just the values of each state that I could then reuse and reuse and reuse.
Nên tôi có thể tóm tắt cả dải ngang cây này chỉ bằng giá trị của mỗi trạng thái, rồi dùng đi dùng lại.
And then if I go to v2, v3, and now at the top, there's not actually that much tree, but that value at the top is v4 if I consider this tree to truncate after four more rewards.
Rồi tới v2, v3, và giờ ở trên cùng, thực ra không còn nhiều cây, nhưng giá trị ở trên cùng là v4 nếu ta coi cây này bị cắt sau bốn phần thưởng nữa.
So this is basically how this algorithm is going to flow.
Về cơ bản thuật toán sẽ chạy như vậy.
I'm going to start with v0 which I know to be 0, and I'm going to go through, and I'm going to compute a new vector of values.
Tôi bắt đầu với v0, mà tôi biết bằng 0, rồi tôi duyệt qua và tính một vectơ giá trị mới.
Each pass through this, I will be computing a vector which correspond to a depth-limited expectimax computations.
Mỗi lượt duyệt, tôi sẽ tính một vectơ tương ứng với phép tính expectimax giới hạn độ sâu.
And each time this new vector that gets produced for k plus 1 will represent having done expectimax in a larger and larger tree without having to have done it explicitly.
Và mỗi lần, vectơ mới được tạo ra cho k cộng 1 biểu diễn việc đã chạy expectimax trên cây ngày càng lớn mà không cần phải làm điều đó một cách tường minh.
Eventually these vectors will stop changing very much, and this process will terminate. So value iteration is the algorithm.
Cuối cùng các vectơ này sẽ gần như thôi thay đổi, và quá trình này sẽ kết thúc. Vậy lặp giá trị chính là thuật toán này.
It's basically like building a big layer cake where first I decide what could I accomplish in zero time steps? If I know that, what can I accomplish and one?
Về cơ bản nó giống như làm một chiếc bánh nhiều tầng, đầu tiên tôi xác định xem mình có thể đạt được gì trong không bước thời gian nào? Biết điều đó rồi, tôi đạt được gì trong một bước?
If I know that, what can I accomplish in two? And I stop whenever it appears to have converged. All right. So here's value iteration, the algorithm.
Biết điều đó rồi, tôi đạt được gì trong hai bước? Và tôi dừng khi thấy nó có vẻ đã hội tụ. Được rồi. Đây là thuật toán lặp giá trị.
We're going to go through this now, and we will extend and improve this next time.
Bây giờ chúng ta sẽ đi qua nó, và buổi sau sẽ mở rộng và cải tiến nó.
In value iteration, you start with v0, that is for each state, you compute your average rewards under optimal play for zero or more time steps. So it's just a vector of zeros.
Trong lặp giá trị, bạn bắt đầu với v0, tức là với mỗi trạng thái, bạn tính phần thưởng trung bình khi chơi tối ưu trong không hoặc nhiều bước thời gian. Nên nó chỉ là một vectơ toàn số không.
Then you imagine you are given a vector of vk for each state. This only works when the number of states is manageable and can be enumerated. And so for each, you have vk.
Rồi giả sử bạn được cho một vectơ vk cho mỗi trạng thái. Cách này chỉ dùng được khi số trạng thái đủ nhỏ để liệt kê hết. Vậy với mỗi trạng thái, bạn có vk.
You know what happens if you compute k time step search from each state. And now using that as a building block, we're going to compute a vk plus 1 value for each.
Bạn biết kết quả nếu tìm kiếm k bước thời gian từ mỗi trạng thái. Và giờ dùng nó làm nền tảng, ta sẽ tính giá trị vk cộng 1 cho từng trạng thái.
And that means the value, the average rewards under optimal play for k plus 1 more time step. And that's just the same little expectimax tree fragment.
Nghĩa là giá trị, tức phần thưởng trung bình khi chơi tối ưu thêm k cộng 1 bước thời gian. Và đó chính là đoạn cây expectimax nhỏ ấy.
We say, well, if I want to know what I can achieve on average in k plus 1 steps from S, I'm going to say, well, what am I going to do?
Ta nói: nếu tôi muốn biết trung bình mình đạt được gì trong k cộng 1 bước từ S, thì tôi sẽ làm gì?
Well, I'm going to max over the actions available to me. I'm going to state I can choose an action.
Tôi sẽ lấy max trên các hành động có thể chọn. Ở trạng thái này tôi chọn một hành động.
When that happens, I'm going to be in a Q state SA, but I need to know what S prime is going to happen before I can compute rewards.
Khi đó tôi sẽ ở trạng thái Q (S, A), nhưng tôi cần biết S prime nào sẽ xảy ra trước khi tính được phần thưởng.
I don't know which S prime is going to happen, but I know a distribution over them. So I can take an average.
Tôi không biết S prime nào sẽ xảy ra, nhưng tôi biết phân phối của chúng. Nên tôi có thể lấy trung bình.
So I sum over all of them, I weigh each option, S prime, by its probability, and now for each outcome, S prime, I'm going to get an instantaneous reward, R of SA S prime.
Tôi lấy tổng trên tất cả, gán trọng số cho mỗi S prime bằng xác suất của nó, và với mỗi kết quả S prime, tôi nhận phần thưởng tức thời R của (S, A, S prime).
And then well, I'll have k time steps left. How much score will I accumulate over that k time step? Well, it depends where I land.
Rồi tôi còn k bước thời gian. Tôi sẽ tích lũy được bao nhiêu điểm trong k bước đó? Điều đó phụ thuộc vào nơi tôi đáp xuống.
I landed in S, and then I'm going to play optimally but with fewer time steps.
Tôi đáp xuống S prime, rồi tôi sẽ chơi tối ưu nhưng với ít bước hơn.
So it's going to be v sub k because that's all the time that's left for state S prime where I landed, and I can stick my discount in there.
Nên đó sẽ là v chỉ số k, vì đó là toàn bộ thời gian còn lại cho trạng thái S prime nơi tôi đáp xuống, và tôi nhân thêm hệ số chiết khấu vào.
This looks exactly like the Bellman equations that related optimal values to other optimal values except that wasn't an algorithm. This is an algorithm. It relates vk plus 1 to vk, but I know vk.
Cái này trông giống hệt các phương trình Bellman liên hệ các giá trị tối ưu với nhau, chỉ khác là đó không phải một thuật toán. Còn đây là một thuật toán. Nó liên hệ vk cộng 1 với vk, mà tôi biết vk.
If I have a vector of vk's, I can then visit each state compute it's vk plus 1 with a one step look ahead like a one-ply expectimax search using this update.
Nếu có vectơ các vk, tôi có thể duyệt từng trạng thái và tính vk cộng 1 của nó bằng nhìn trước một bước, như tìm kiếm expectimax một tầng, dùng phép cập nhật này.
So how expensive is this? Well, I have to visit each S, so I get a factor of S.
Vậy chi phí là bao nhiêu? Tôi phải duyệt từng S, nên có một thừa số S.
And then for each S, I'm going to do a little expected max, so I'm going to get a factor of A as I consider each action.
Rồi với mỗi S, tôi làm một expectimax nhỏ, nên có thừa số A khi xét từng hành động.
And then for each action, I need to consider every possible state that results. In the worst case, every state can result in every other state, so I'll get another factor of S.
Và với mỗi hành động, tôi cần xét mọi trạng thái có thể xảy ra. Trong trường hợp xấu nhất, mỗi trạng thái có thể dẫn đến mọi trạng thái khác, nên có thêm một thừa số S.
In practice, you don't usually get that second factor of S because actions have a limited amount of possible successors, S prime. But there is your complexity. Is that good?
Thực tế thường không có thừa số S thứ hai đó vì mỗi hành động chỉ có số trạng thái kế tiếp hữu hạn, S prime. Đó là độ phức tạp của nó. Vậy có tốt không?
It really, really depends on how many states you have.
Điều đó phụ thuộc rất nhiều vào số trạng thái.
So for now we're going to imagine our sets of states as small, which is exactly the opposite of what we did when we add the search.
Giờ ta tạm giả sử tập trạng thái là nhỏ, hoàn toàn ngược với những gì ta làm khi học tìm kiếm.
We imagined our set of states was so huge you could never enumerate it.
Khi đó ta giả sử tập trạng thái lớn đến mức không bao giờ liệt kê hết được.
Well, we will fix the distance between these two things when we get to a state function approximation about a week from today.
Ta sẽ thu hẹp khoảng cách giữa hai cách này khi học đến xấp xỉ hàm, khoảng một tuần nữa.
So this thing will converge towards optimal values, but I'll prove that next time. So should we do an example now?
Thuật toán này sẽ hội tụ về các giá trị tối ưu, nhưng tôi sẽ chứng minh buổi sau. Vậy giờ ta làm một ví dụ nhé?
You guys are all closing your books, so — who wants an example? Let's do it democratically. Who wants to just be free?
Các bạn đang đóng sách lại rồi, nên — ai muốn xem ví dụ? Ta biểu quyết dân chủ nhé. Ai muốn được tự do?
All right. Sounds like we're going to do a quick example. All right, v0. What's v0 from each state?
Được rồi. Có vẻ ta sẽ làm một ví dụ nhanh. Được, v0. v0 của mỗi trạng thái là bao nhiêu?
Remember the car MDP? It's 0. Because in zero time steps, you can get 0 awards. All right, v1.
Nhớ MDP chiếc xe không? Là 0. Vì trong không bước thời gian, bạn nhận được phần thưởng 0. Được, v1.
You don't even need to know the algorithm. You can just think, what will I accomplish on average if I play for one more time step? What if I'm overheated?
Bạn thậm chí không cần biết thuật toán. Chỉ cần nghĩ: trung bình tôi đạt được gì nếu chơi thêm một bước thời gian? Nếu tôi đang quá nhiệt thì sao?
0. No more rewards for you. You're overheated. Reflect on your life choices.
0. Hết phần thưởng cho bạn. Bạn quá nhiệt rồi. Hãy suy ngẫm lại các lựa chọn của đời mình.
All right. What if you're in the cool state? You have only one time left. Go for it.
Được rồi. Nếu bạn đang ở trạng thái mát thì sao? Bạn chỉ còn một bước thời gian. Cứ làm đi.
Go fast. You're going to get 2. Sometimes. All the time.
Chạy nhanh. Bạn sẽ được 2. Đôi khi. Lúc nào cũng vậy.
Who knows what state you'll end up in, but you'll always get the same reward. Yep.
Không biết bạn sẽ rơi vào trạng thái nào, nhưng phần thưởng luôn như nhau. Vâng.
STUDENT
Wouldn't you get a minus 10 from being overheated?
Chẳng phải bị quá nhiệt sẽ bị trừ 10 sao ạ?
PROFESSOR
Excellent question. If you are in the state overheated, no, you don't get a minus 10. You get a minus 10 as you transition into that state.
Câu hỏi rất hay. Nếu bạn đang ở trạng thái quá nhiệt, thì không, bạn không bị trừ 10. Bạn bị trừ 10 khi chuyển sang trạng thái đó.
In that state, you can imagine there's like a little — oh, that's unexpected. You can imagine there's a little loop here that says 0. Yeah, that's a great question.
Ở trạng thái đó, bạn có thể hình dung là như một vòng lặp nhỏ — ồ, bất ngờ thật. Các em có thể hình dung có một vòng lặp nhỏ ở đây ghi số 0. Vâng, câu hỏi rất hay.
So if you're on cool, you get 2. If you are in the red warm state, what can you accomplish in one time step? Well, you've only got two choices.
Nếu đang ở trạng thái cool, em nhận được 2. Nếu em đang ở trạng thái warm màu đỏ, em làm được gì trong một bước thời gian? Em chỉ có hai lựa chọn.
You're either going to go fast or you're going to go slow. And then you can compute. Well, if I went fast, I would be guaranteed a minus 10.
Hoặc đi nhanh, hoặc đi chậm. Rồi em có thể tính. Nếu đi nhanh, em chắc chắn nhận -10.
If I went slow, I would be guaranteed a 1. That sounds better, and so that represents optimal play. The other one doesn't hurt you because you're not going to do it.
Nếu đi chậm, em chắc chắn nhận 1. Cách sau tốt hơn, và đó là cách chơi tối ưu. Lựa chọn còn lại không hại em vì em sẽ không chọn nó.
Here's where things get interesting. From overheated, you still have 0. The game is over at that point.
Đây là chỗ thú vị. Từ trạng thái overheated, em vẫn nhận 0. Lúc đó trò chơi đã kết thúc.
So let's say you are in the cool state, and you think, OK, I've got two time steps left. I could try to enumerate all of the length 2 futures.
Giả sử em đang ở trạng thái cool, và em nghĩ, được rồi, mình còn hai bước thời gian. Em có thể thử liệt kê mọi tương lai có độ dài 2.
There are some number of them. I could try to enumerate them all, but that's not what this algorithm does. This algorithm says, what am I going to do?
Có một số lượng nhất định các tương lai đó. Em có thể thử liệt kê hết, nhưng thuật toán này không làm vậy. Thuật toán này hỏi: mình sẽ làm gì?
Well, I'm in this cool state, so I'm at cool, and I've got two choices. I can go slow, or I can go fast. What happens if from cool, I go slow?
Mình đang ở trạng thái cool, và có hai lựa chọn. Đi chậm hoặc đi nhanh. Điều gì xảy ra nếu từ cool mình đi chậm?
Well, cool, I go slow. If I go slow, I will receive 1 in the next step. I will be guaranteed to land at cool, and then I will do the optimal thing.
Từ cool, mình đi chậm. Đi chậm thì bước tiếp theo mình nhận 1. Chắc chắn mình sẽ đến cool, và sau đó mình làm điều tối ưu.
v1. I don't have to think about it. Once I only have one time step left, I've got a cache right here lower on the slide. And so what's that?
v1. Mình không cần nghĩ nữa. Khi chỉ còn một bước thời gian, mình đã có bảng lưu sẵn ở phần dưới của slide. Vậy giá trị đó là bao nhiêu?
I'll get 2 in the next step. Or I could go fast. If I go fast, what's going to happen? Well, remember I'm in cool right now.
Bước tiếp theo mình nhận 2. Hoặc mình có thể đi nhanh. Nếu đi nhanh thì chuyện gì xảy ra? Nhớ là bây giờ mình đang ở cool.
When I go fast, I am going to get two points for going fast, but what happens next depends on whether or not I heat up.
Đi nhanh thì mình được 2 điểm, nhưng bước sau còn tùy việc mình có nóng lên hay không.
If I heat up, which happens half the time, I will land in warm and thereafter receive 1.
Nếu nóng lên, xảy ra nửa số lần, mình sẽ đến warm và sau đó nhận 1.
If I don't heat up, I will land and cool and thereafter receive 2 looking at my cache.
Nếu không nóng lên, mình sẽ đến cool và sau đó nhận 2, nhìn vào bảng lưu của mình.
And so I'm either going to get 2 plus 2, or I'm going to get 2 plus 1, both equally likely. And therefore, on average, my score here will be 3.5 under optimal play.
Vậy mình sẽ nhận 2 cộng 2, hoặc 2 cộng 1, hai trường hợp có khả năng như nhau. Do đó, trung bình điểm của mình ở đây sẽ là 3,5 khi chơi tối ưu.
I don't have to worry about what happens if I go slow, because I'm not going to do that. I can control that.
Mình không cần lo chuyện gì xảy ra nếu đi chậm, vì mình sẽ không chọn vậy. Mình kiểm soát được điều đó.
But I do need to worry that when I go fast, I might heat up or I might not, and that's going to recurse into what I've already computed.
Nhưng mình cần lo rằng khi đi nhanh, mình có thể nóng lên hoặc không, và điều đó sẽ đệ quy vào những gì mình đã tính.
And then if you look at this value here, you'll undergo the same computation. You'll look at it and you say, well, I'm either going to go fast, or I'm going to go slow.
Rồi nhìn giá trị ở đây, em sẽ thực hiện phép tính tương tự. Em nhìn và nói, mình sẽ đi nhanh, hoặc đi chậm.
And in each case, you do the next ply of the expectimax. It grounds out in v1 that you've already computed, and you can try it on your own.
Và mỗi trường hợp, em làm tầng tiếp theo của expectimax. Nó dừng ở v1 mà em đã tính xong, và các em có thể tự thử.
You'll get 2.5. Now if I keep doing this, what are they going to converge to?
Em sẽ được 2,5. Nếu cứ tiếp tục thế này, chúng sẽ hội tụ về đâu?
They will not converge. This is without a discount. This is one of these defective cases where your rewards will go infinite. We'll talk about what that means next time.
Chúng sẽ không hội tụ. Đây là trường hợp không có hệ số chiết khấu. Đây là một trong những trường hợp khiếm khuyết mà phần thưởng sẽ tiến đến vô hạn. Lần sau ta sẽ nói điều đó nghĩa là gì.
So the answers are on the slide. Next time we'll talk about why this converges, and we'll talk about another class of algorithms. All right. Thanks, everyone.
Đáp án có trên slide. Lần sau ta sẽ nói vì sao nó hội tụ, và ta sẽ nói về một lớp thuật toán khác. Được rồi. Cảm ơn các em.
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.