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
OK. Let's get started.
Được rồi. Chúng ta bắt đầu nhé.
Today, we're going to talk a little bit more about MDPs, Markov decision processes. But before we do that, I have a quick update on Mini-Contest 1.
Hôm nay chúng ta sẽ nói thêm một chút về MDP, quá trình quyết định Markov. Nhưng trước đó, tôi có một cập nhật nhanh về Mini-Contest 1.
How many of you here participated in Mini-Contest 1? OK. What? Was there a question?
Có bao nhiêu bạn ở đây đã tham gia Mini-Contest 1? Được rồi. Gì cơ? Có câu hỏi à?
Well, you're in good company. There are 200 participating teams of about 250 students, so thank you all for participating.
Ồ, các bạn không đơn độc đâu. Có 200 đội tham gia, trên khoảng 250 sinh viên, nên cảm ơn tất cả các bạn đã tham gia.
There will be a sequence of these culminating in a final contest, which I think is pretty awesome.
Sẽ có một chuỗi các cuộc thi như thế, đỉnh điểm là cuộc thi cuối cùng, tôi nghĩ là rất tuyệt.
And today, I'm going to give you just a little bit of a view into what some of the top scoring teams did in Mini-Contest 1.
Và hôm nay, tôi sẽ cho các bạn xem sơ qua một số đội điểm cao nhất đã làm gì trong Mini-Contest 1.
Before I do that, I always love to see what names people come up with.
Trước đó, tôi luôn thích xem mọi người nghĩ ra những cái tên nào.
So you guys just like type some random name, but like, we're actually there looking there to see all those cool names. So we've got a pretty good assortment of cool names.
Các bạn cứ gõ một cái tên ngẫu nhiên, nhưng thực ra chúng tôi có xem những cái tên hay ho đó. Chúng ta có khá nhiều tên thú vị.
Almost every year, there is a Waka Waka Waka, and as soon as I see that, I cannot then get that sound out of my head for the whole rest of the semester.
Gần như năm nào cũng có một đội Waka Waka Waka, và cứ thấy nó là tôi không thể thoát khỏi âm thanh đó trong đầu suốt phần còn lại của học kỳ.
So thanks, Waka Waka Waka for getting that in my head. MorePointsPlease, you'll have to report whether or not the name actually got you more points.
Cảm ơn Waka Waka Waka đã làm tôi bị ám ảnh. MorePointsPlease, bạn sẽ phải báo lại xem cái tên đó có thật sự giúp bạn có thêm điểm không.
There's this bully expression which reminds me a lot of the requirements for the course, except with professor names put in.
Có một câu bắt nạt này làm tôi nhớ nhiều đến các yêu cầu của môn học, chỉ khác là thay bằng tên các giáo sư.
And then, thank you whoever decided to stress test our string processing with this little emoji guy. Some bugs were discovered.
Và cảm ơn bạn nào đã quyết định kiểm tra giới hạn phần xử lý chuỗi của chúng tôi bằng anh chàng emoji nhỏ này. Một số lỗi đã bị phát hiện.
STUDENT
That one is actually written in [INAUDIBLE].. I recognize it.
Cái đó thực ra viết bằng [KHÔNG NGHE RÕ]. Em nhận ra nó.
PROFESSOR
Yeah, well thank you for stress testing our system in any case. On to the meat of it, which is, in third place, we have team Winnie the Pooh.
Vâng, dù sao cũng cảm ơn bạn đã kiểm tra hệ thống của chúng tôi. Vào phần chính, ở vị trí thứ ba là đội Winnie the Pooh.
Is Winnie the Pooh here? Are Winnie the Pooh here? OK. That is Phillip and Winnie, the Pooh, perhaps.
Winnie the Pooh có ở đây không? Có Winnie the Pooh nào ở đây không? Được rồi. Đó là Phillip và Winnie, có lẽ là Pooh.
Congratulations in third place with score 1,193. You'll notice these are all very tightly clustered in score. Their bot used BFS to find the nearest food, and re-planned whenever another agent ate the bot.
Chúc mừng hạng ba với số điểm 1,193. Các bạn sẽ thấy điểm số của họ rất sát nhau. Bot của họ dùng BFS để tìm thức ăn gần nhất, và lập kế hoạch lại mỗi khi tác tử khác ăn mất mục tiêu.
So I'm going to play this here, so probably, those of you doing the contest are used to seeing these in a much higher rate, but watch all of these Pac-Men collaborate.
Tôi sẽ chiếu cái này, có lẽ các bạn làm cuộc thi quen xem với tốc độ cao hơn nhiều, nhưng hãy xem các Pac-Man này phối hợp.
Notice they're not sort of like — sometimes there will be like one sad Pac-Man in some solutions, that follows another Pac-Man but never gets a dot. But these ones seem to coordinate pretty well.
Hãy xem, chúng không kiểu như — đôi khi trong một số lời giải có một Pac-Man đáng thương cứ đi theo Pac-Man khác mà không bao giờ ăn được chấm nào. Nhưng những con này phối hợp khá tốt. Làm tốt lắm.
Good job. [APPLAUSE] Good job, Winnie the Pooh.
[VỖ TAY] Làm tốt lắm, Winnie the Pooh. Hạng nhì là đội Jason L. Jason L có ở đây không?
In second place, we have team Jason L. Are you here, Jason L? Congratulations. Score of 1,200.
Chúc mừng. Điểm 1,200.
Bot description, lots of caching of pre-computed solutions to reduce redundant computation re-planning, as in the previous one.
Mô tả bot: lưu đệm nhiều lời giải đã tính trước để giảm tính toán lặp lại khi lập kế hoạch lại, giống đội trước.
But also, something that we saw a lot in many of the agent submissions on the leaderboard, which was a sort of prioritizing different directions, some kind of a diversity so that the Pac-Men would spread out.
Nhưng cũng có điều chúng tôi thấy ở nhiều tác tử trên bảng xếp hạng, đó là ưu tiên các hướng khác nhau, một kiểu đa dạng hóa để các Pac-Man tản ra. Cùng xem nhé.
So let's watch this go.
Chúng đi kìa.
There they go. Can you guys see this? Yes, you can. OK.
Các bạn thấy không? Có, thấy rồi. Được rồi. Mấy chấm tội nghiệp ở góc, lúc nào cũng bị ăn cuối.
Those poor dots in the corner, they're always last. OK. Congratulations, Jason L.
Được rồi. Chúc mừng Jason L.
[APPLAUSE] And in first place, team [? Yusheng. ?] Are you here, [? Yusheng? ?] All right.
[VỖ TAY] Và hạng nhất là đội [? Yusheng. ?] [? Yusheng ?] có ở đây không? Được rồi. Còn có Ryan.
There's also Ryan. Are you here, Ryan? Excellent. OK, well, I'm going to call you guys team [? Yusheng ?] Ryan.
Ryan có ở đây không? Tuyệt. Được rồi, tôi sẽ gọi hai bạn là đội [? Yusheng ?] Ryan.
You had a score of 1,201, barely edging out the second place team by one point. What did you do? I have no idea. What did you do?
Các bạn được 1,201 điểm, chỉ nhỉnh hơn đội hạng nhì đúng một điểm. Các bạn đã làm gì? Tôi không biết luôn. Các bạn đã làm gì? Bạn nói nhanh được không?
SINH VIÊN
Do you want to say really quickly?
Vâng.
STUDENT
Yeah. We modified the [INAUDIBLE] in three parts.
Chúng em sửa [KHÔNG NGHE RÕ] ở ba phần. Phần đầu là [KHÔNG NGHE RÕ].
GIÁO SƯ
The first part is [INAUDIBLE].
Tuyệt.
PROFESSOR
Cool. So again, this theme of reducing computation and also kind of giving the agents away to specialize, which is always important in multi-agent systems. So let's see it.
Lại là chủ đề giảm tính toán và giúp các tác tử chuyên biệt hóa, điều luôn quan trọng trong hệ đa tác tử. Cùng xem nhé. Xem có thấy được khác biệt một điểm không.
Let's see if you can see the difference of the one point.
Được rồi, chúng đi kìa.
All right, there they go.
In future contests, it's going to be team versus team, and then it gets intense. All right, those last dots. All the Pac-Men headed that way. All right.
Ở các cuộc thi sau, sẽ là đội đấu đội, và sẽ rất căng thẳng. Được rồi, mấy chấm cuối cùng. Tất cả Pac-Man đều đi về hướng đó. Được rồi. Chúc mừng [? Yusheng ?] và Ryan.
Congratulations, [? Yusheng ?] and Ryan. [APPLAUSE] Good job, everybody who participated, and here's our final leaderboard.
[VỖ TAY] Cảm ơn mọi người đã tham gia, và đây là bảng xếp hạng cuối cùng.
You can see those top three are really, really closely clustered, but really there's just a whole bunch of teams that had really strong submissions. So congratulations to everybody there.
Các bạn thấy ba đội đầu rất, rất sát nhau, nhưng thật ra có cả một loạt đội có bài nộp rất mạnh. Chúc mừng tất cả các bạn.
A couple others to eyeball so you can get a sense of the ideas that kept coming up in some of the top submissions, a lot of pre-caching to make computation fit in into the time.
Vài đội khác đáng xem để các bạn nắm được những ý tưởng lặp lại trong các bài nộp hàng đầu, rất nhiều là tính trước và lưu đệm để việc tính toán trong một số bài nộp xuất sắc nhất, người ta dùng rất nhiều kỹ thuật pre-caching để việc tính toán vừa với thời gian cho phép.
A lot of re-planning, a lot of prioritizing keeping agents apart. Some kind of diversity function, dividing food pellets up, kind of splitting goals, that kind of thing. So all of these ideas, very successful.
Nhiều bài lập kế hoạch lại liên tục, ưu tiên giữ các tác tử cách xa nhau. Một dạng hàm đa dạng hóa nào đó, chia các hạt thức ăn ra, chia nhỏ mục tiêu, đại loại vậy. Tất cả những ý tưởng này đều rất thành công.
So congratulations to everybody who participated, and I look forward to seeing Mini-Contest 2. So congratulations to everybody. [APPLAUSE] Any questions on Mini-Contest 1?
Xin chúc mừng tất cả các bạn đã tham gia, và tôi mong được xem Mini-Contest 2. Chúc mừng tất cả mọi người. [VỖ TAY] Có câu hỏi nào về Mini-Contest 1 không?
All right, MDPs for real this time. All right, we're going to keep talking about MDPs.
Được rồi, lần này là MDP thật sự. Chúng ta sẽ tiếp tục nói về MDP.
And today, we're going to talk about methods that focus on the policies that we generate in MDPs so that we can start to solve them a little bit more efficiently, and also understand a little bit what's going on inside algorithms like value iteration when we run them.
Hôm nay, chúng ta sẽ bàn về các phương pháp tập trung vào chính sách mà ta tạo ra trong MDP, để giải chúng hiệu quả hơn một chút, và cũng hiểu phần nào điều gì diễn ra bên trong các thuật toán như lặp giá trị khi ta chạy chúng.
So I can't say this enough.
Tôi có nói bao nhiêu lần cũng không đủ.
Grid world is both a really important running example because it's going to show up in your homework, it's going to show up in your projects, it's going to be all over lecture, it's probably going to show up in exams.
Grid world là một ví dụ xuyên suốt rất quan trọng vì nó sẽ xuất hiện trong bài tập về nhà, trong các project, xuất hiện khắp bài giảng, và có lẽ cũng sẽ có trong bài thi.
At the same time, it is just one MDP. Most MDPs do not involve robots in a grid. They do not involve walls, and they do not involve the actions north, south, east, and west.
Nhưng đồng thời, nó chỉ là một MDP. Hầu hết MDP không liên quan đến robot trên lưới. Chúng không có tường, và không có các hành động bắc, nam, đông, tây.
But this one does. It's basically a maze, the agents in a grid, and there are walls blocking the path and then there are various exits.
Nhưng cái này thì có. Về cơ bản nó là một mê cung, tác tử nằm trên lưới, có những bức tường chắn đường và có nhiều lối thoát khác nhau.
The actions are north, south, east, and west and there's noise. So usually, when you take an action, it does what you expect, and sometimes it does something different.
Các hành động là bắc, nam, đông, tây và có nhiễu. Thường thì khi bạn thực hiện một hành động, nó làm đúng như bạn mong đợi, và đôi khi nó làm một việc khác.
We talked last time about the details. 10% of the time, you sort of go 90 degrees to the left of what you expected.
Lần trước ta đã nói chi tiết. 10% số lần, bạn đi lệch 90 độ sang trái so với dự định.
10 percent of the time, you go 90 degrees to the right of what you expected. And if there's a wall in your way, you stay put.
10% số lần, bạn đi lệch 90 độ sang phải so với dự định. Và nếu có tường chắn đường, bạn đứng yên.
This MDP has rewards that we talk about as a living reward, which is possibly 0, tiny little reward that you get step by step every time even though the game hasn't ended, and then a large reward at the end when you take the exit action from a terminal square.
MDP này có phần thưởng mà ta gọi là phần thưởng sống (living reward), có thể bằng 0, một phần thưởng rất nhỏ bạn nhận được mỗi bước dù trò chơi chưa kết thúc, và một phần thưởng lớn ở cuối khi bạn thực hiện hành động thoát từ một ô kết thúc.
And here, the big rewards are the plus 1 and the minus 1, and the living reward is some value, maybe like minus 0.01. That terminology of a living reward, that's grid world terminology.
Ở đây, phần thưởng lớn là +1 và -1, còn phần thưởng sống là một giá trị nào đó, chẳng hạn -0,01. Thuật ngữ phần thưởng sống này là thuật ngữ riêng của grid world.
In a generic MDP, there's just a reward function, and every step, you get a reward. Maybe it's 0, maybe it's not.
Trong MDP tổng quát chỉ có một hàm phần thưởng, và mỗi bước bạn nhận một phần thưởng. Có thể bằng 0, có thể không.
It's just some reward, R. The goal, in general for MDPs, is to maximize the sum of rewards.
Chỉ là một phần thưởng R nào đó. Mục tiêu chung của MDP là cực đại hóa tổng các phần thưởng.
And last time, we talked about this idea that rewards further out in the future maybe should be discounted, either for algorithmic convenience or because it actually reflects that rewards further out in time are worth less to the agent.
Lần trước ta cũng nói về ý tưởng rằng phần thưởng càng xa trong tương lai thì có lẽ nên được chiết khấu, hoặc vì thuận tiện cho thuật toán, hoặc vì nó thực sự phản ánh rằng phần thưởng càng xa trong thời gian thì càng ít giá trị với tác tử.
To recap, MDPs in general, not just grid world — even though grid world will often be our running example — MDPs are nondeterministic search processes.
Tóm lại, MDP nói chung, không chỉ grid world, dù grid world thường là ví dụ xuyên suốt của ta, là các quá trình tìm kiếm không tất định.
So like search, there's a set of states, S, and it's fully observed so you know what state you're in. Later on in the course, you may not even know that.
Giống như tìm kiếm, có một tập trạng thái S, và nó quan sát được hoàn toàn nên bạn biết mình đang ở trạng thái nào. Về sau trong khóa học, có thể bạn còn không biết điều đó.
But right now, there's a set of states, S. You know what state you're in. There's a set of actions, and you know what actions are available to you.
Nhưng bây giờ, có một tập trạng thái S. Bạn biết mình đang ở trạng thái nào. Có một tập hành động, và bạn biết những hành động nào khả dụng.
What's different from search is there's now a transition function.
Điểm khác với tìm kiếm là bây giờ có một hàm chuyển.
Instead of actions having a successor, meaning you take this action and you end up in this state, there is now a distribution over successors given by the transition function.
Thay vì mỗi hành động có một trạng thái kế tiếp, nghĩa là làm hành động này thì ra trạng thái này, giờ có một phân phối trên các trạng thái kế tiếp do hàm chuyển cho.
So whenever you see [? T ?] of SAS prime, you think, that's the probability that if I'm in state S and I take action A, the result will be S prime.
Vậy khi thấy T(s, a, s'), bạn hiểu đó là xác suất để nếu tôi ở trạng thái s và thực hiện hành động a, kết quả sẽ là s'.
Now, it's nondeterministic in the sense that from SA, I don't know what S prime I'm going to land on.
Nó không tất định theo nghĩa từ (s, a), tôi không biết mình sẽ rơi vào s' nào.
But it is known in the sense that I know what probability each outcome has, and that's important. And that's going to become even more important towards the end of today, and especially next week.
Nhưng nó là đã biết theo nghĩa tôi biết mỗi kết quả có xác suất bao nhiêu, và điều đó quan trọng. Điều này sẽ còn quan trọng hơn vào cuối buổi hôm nay, và đặc biệt là tuần sau.
There's then a bunch of rewards, and for every SAS prime, you get a reward. So in a state S, taking action A, you'll get a reward.
Tiếp theo là các phần thưởng, và với mỗi (s, a, s') bạn nhận một phần thưởng. Tức là ở trạng thái s, thực hiện hành động a, bạn sẽ nhận phần thưởng.
That reward, in general, is going to depend not just on S and A, but also on what happens.
Phần thưởng đó, nói chung, sẽ phụ thuộc không chỉ vào s và a, mà còn vào điều xảy ra.
So if your action isn't successful, you may not get the same reward as if it is. And then there's a start state.
Nên nếu hành động không thành công, bạn có thể không nhận cùng phần thưởng như khi thành công. Và cuối cùng là trạng thái bắt đầu.
We also talked about certain quantities that are going to show up over and over again in formulating and solving MDPs.
Ta cũng đã nói về một số đại lượng sẽ xuất hiện đi xuất hiện lại khi xây dựng và giải MDP.
They're also going to show up over and over again when we talk about reinforcement learning, so it's good to get really clear on what they are today.
Chúng cũng sẽ xuất hiện lặp đi lặp lại khi ta nói về học tăng cường, nên hôm nay cần hiểu thật rõ chúng là gì.
So these are quantities that we can define mathematically, and then we can produce algorithms for computing them either incrementally or from each other, as we'll do today.
Đây là những đại lượng ta có thể định nghĩa bằng toán học, rồi ta có thể xây dựng thuật toán để tính chúng, hoặc theo kiểu tăng dần, hoặc từ đại lượng này suy ra đại lượng kia, như hôm nay ta sẽ làm.
So the important one that we talk about when we think about taking an action is the policy. A policy is a map of states to action.
Đại lượng quan trọng mà ta nhắc tới khi nghĩ về việc thực hiện một hành động là chính sách. Chính sách là một ánh xạ từ trạng thái sang hành động.
So I give you a state, you tell me what to do. That's the policy. Search had a plan, and you could have a plan because you knew what was going to happen.
Tôi đưa bạn một trạng thái, bạn cho tôi biết phải làm gì. Đó là chính sách. Tìm kiếm có một kế hoạch, và có kế hoạch được vì bạn biết điều gì sẽ xảy ra.
Everything was deterministic. Now we have policies. Whatever state you end up in, it tells you what to do. It might be an explicit policy that lists the actions like we've seen in grid world.
Mọi thứ đều tất định. Giờ ta có chính sách. Bất kể bạn rơi vào trạng thái nào, nó cho bạn biết phải làm gì. Nó có thể là một chính sách tường minh liệt kê các hành động như ta đã thấy trong grid world.
It might be an implicit policy that requires some computation like running expectimax. In addition to policies, which map from states to actions, we had a notion of utility.
Cũng có thể là chính sách ngầm, đòi hỏi phải tính toán như chạy expectimax. Ngoài chính sách, vốn ánh xạ từ trạng thái sang hành động, ta còn có khái niệm độ hữu dụng.
The MDP has a notion of reward, so that function R there is a reward. Every time step, you get a reward.
MDP có khái niệm phần thưởng, tức hàm R ở đây chính là phần thưởng. Mỗi bước thời gian, bạn nhận được một phần thưởng.
It might be big, it might be small, it might be 0, but every time step, you get what's called an instantaneous reward.
Có thể lớn, có thể nhỏ, có thể bằng 0, nhưng mỗi bước thời gian bạn đều nhận được cái gọi là phần thưởng tức thời.
A utility is the sum of all of those rewards, or the sum of a discounted series of those rewards. So it's a possibly discounted sum of rewards. That's the utility.
Độ hữu dụng là tổng của tất cả các phần thưởng đó, hoặc tổng của chuỗi các phần thưởng có chiết khấu. Tức là tổng phần thưởng, có thể có chiết khấu. Đó là độ hữu dụng.
All the agents we have are maximizing their expected utility, and utilities here are the sum of discounted rewards. We talked about values. This is important, and I'll expand this in the next slide.
Mọi tác tử của ta đều tối đa hóa độ hữu dụng kỳ vọng, và độ hữu dụng ở đây là tổng các phần thưởng có chiết khấu. Ta đã nói về các giá trị. Điều này quan trọng, và tôi sẽ nói rõ hơn ở slide sau.
Values are a function from states to numbers. So in that sense, they're a lot like a utility. What is a value of a state?
Giá trị là một hàm từ trạng thái sang các con số. Theo nghĩa đó, nó khá giống độ hữu dụng. Giá trị của một trạng thái là gì?
It is the expected utility that you will get from that state. And you say, well, doesn't the utility sort of depend on a bunch of things? Doesn't it depend on what I do?
Đó là độ hữu dụng kỳ vọng bạn sẽ nhận được từ trạng thái đó. Bạn sẽ hỏi: độ hữu dụng chẳng phải phụ thuộc vào nhiều thứ sao? Chẳng phải nó phụ thuộc vào việc tôi làm gì sao?
Yes, but when we talk about the value, it's the value under acting optimally. You might not know what that is, but that's the mathematical definition of value.
Đúng, nhưng khi nói về giá trị, đó là giá trị khi hành động tối ưu. Bạn có thể chưa biết hành động đó là gì, nhưng đó là định nghĩa toán học của giá trị.
But then you say, also, won't the rewards I get from a state depend not only on the policy I act according to, but also on what happens?
Rồi bạn lại hỏi: phần thưởng tôi nhận từ một trạng thái chẳng phải không chỉ phụ thuộc vào chính sách tôi theo, mà còn vào những gì xảy ra sao?
Yes, and the value will be an average over everything that might happen, where that averages the various outcomes of the actions, and we'll see that.
Đúng, và giá trị sẽ là trung bình trên mọi điều có thể xảy ra, tức trung bình các kết quả khác nhau của hành động, ta sẽ thấy điều đó.
And in an expectimax, that's what the chance nodes do. There's also Q values which, I think, are the least intuitive of these quantities.
Và trong expectimax, đó là việc của các nút ngẫu nhiên. Còn có các giá trị Q, mà tôi nghĩ là kém trực quan nhất trong các đại lượng này.
A Q value is the expected future utility, not from being in a state, but from being in a Q state, which is a chance node in an expectimax tree.
Giá trị Q là độ hữu dụng kỳ vọng trong tương lai, không phải từ việc ở trong một trạng thái, mà từ việc ở trong một trạng thái Q, tức là nút ngẫu nhiên trong cây expectimax.
So whenever you think about an MDP, I think this is just the most useful diagram you can have in your head.
Vì vậy, bất cứ khi nào nghĩ về một MDP, tôi cho rằng đây là sơ đồ hữu ích nhất mà bạn có thể ghi nhớ.
In general, you're at some state S, and that's where you are right now.
Nói chung, bạn đang ở một trạng thái S nào đó, và đó là nơi bạn đang đứng lúc này.
And when you're in a state S, you get to choose an action A. So any time you're thinking about these actions, you're never going to pick one at random.
Khi ở trạng thái S, bạn được chọn một hành động A. Vậy mỗi khi bạn nghĩ về các hành động này, bạn sẽ không bao giờ chọn ngẫu nhiên.
You're going to pick the best one. You're always going to be maximizing over A, unless you're told a specific A to evaluate. OK, so we max over A.
Bạn sẽ chọn hành động tốt nhất. Bạn luôn tối đa hóa theo A, trừ khi được cho một A cụ thể để đánh giá. Vậy ta lấy max theo A.
When I'm in a state in an action, I get to a chance node. This represents having committed to the action. I'm in the state. It's too late to wish I was in another state.
Khi ở một trạng thái và một hành động, ta đến một nút ngẫu nhiên. Nó biểu diễn việc đã cam kết với hành động. Tôi đang ở trạng thái đó. Quá muộn để ước mình ở trạng thái khác.
I've picked an action. It's too late to pick another action.
Tôi đã chọn một hành động. Quá muộn để chọn hành động khác.
But I'm not sure what S prime is going to happen yet, because I don't know which of the possible outcomes is going to obtain.
Nhưng tôi chưa chắc S' nào sẽ xảy ra, vì tôi không biết kết quả nào trong các kết quả khả dĩ sẽ xảy ra.
So there's this range of S primes you could end up with, and in general, we will average over those.
Vậy có một loạt các S' mà bạn có thể rơi vào, và nói chung, ta sẽ lấy trung bình trên chúng.
And so that basic kind of thought that you're in a state, you'll choose an action, and then some S prime will result according to the transition function and giving you a reward for that time step, that's the basic cycle of an MDP.
Và ý tưởng cơ bản đó, rằng bạn ở một trạng thái, chọn một hành động, rồi một S' nào đó xuất hiện theo hàm chuyển và cho bạn một phần thưởng ở bước thời gian đó, đó là chu trình cơ bản của một MDP.
And then once you get to S prime, there's going to be some future.
Và khi đến S', sẽ có một tương lai nào đó.
And in general in these algorithms, the future will plug in some quantity as a placeholder for the future, because if we expanded the whole thing out, it would be this like big nested equation that would be really difficult to handle.
Nói chung trong các thuật toán này, ta sẽ đưa vào một đại lượng làm chỗ giữ chỗ cho tương lai, vì nếu khai triển toàn bộ ra, nó sẽ là một phương trình lồng nhau khổng lồ rất khó xử lý.
So we have these optimal quantities that we are going to be writing down expressions that either define them in terms of each other or define procedures which compute them.
Ta có các đại lượng tối ưu này và sẽ viết các biểu thức hoặc định nghĩa chúng theo nhau hoặc định nghĩa các thủ tục để tính chúng. Các đại lượng này có thể bắt đầu lẫn vào nhau.
These quantities may all start to blur together. If they haven't blurred together already, they may blur together today when we start talking about variations of them.
Nếu chúng chưa lẫn vào nhau, thì hôm nay có thể sẽ lẫn, khi ta bắt đầu nói về các biến thể của chúng.
It's important to keep them — especially their definitions, it's important to keep them separate. So let's pull up the grid world, and we'll look and see what values, Q values, and policies look like.
Điều quan trọng là phải giữ chúng tách bạch, đặc biệt là các định nghĩa, phải giữ chúng riêng rẽ. Giờ ta mở grid world lên, xem giá trị, giá trị Q và chính sách trông như thế nào. Ở đây bạn thấy có các dấu sao.
And now here, you can see there are stars.
Whenever I talk about values, if I want to be extra clear that I'm talking about the value of the state, meaning the average utility, the expected utility from that state, if I want to be clear that I mean under optimal choice of action, I'll put a star.
Mỗi khi nói về giá trị, nếu tôi muốn nói rõ đó là giá trị của trạng thái, nghĩa là độ hữu dụng trung bình, độ hữu dụng kỳ vọng từ trạng thái đó, và muốn nói rõ là khi chọn hành động tối ưu, tôi sẽ thêm dấu sao. Vậy V sao là giá trị tối ưu, Q sao là giá trị Q tối ưu, còn pi sao, có nhiều chính sách pi.
So V star is the optimal values, Q star is the optimal Q values, and pi star — there are many policies pi.
Có chính sách bảo bạn làm điều khôn ngoan, có chính sách bảo bạn làm điều thiếu khôn ngoan.
Some tell you to do wise things, and some tell you to do unwise things. Pi star indicates an optimal policy. All right. Let's bring up the demo.
Pi sao chỉ một chính sách tối ưu. Được rồi. Ta mở demo lên. Vậy demo này làm gì? Demo này về cơ bản là project ba của các bạn.
All right, so what does this demo do? This demo is basically your project three.
Nó đã chạy lặp giá trị, thuật toán của buổi trước mà hôm nay tôi sẽ nhắc lại nhanh.
And what this has done is it has run value iteration, the algorithm from last time which I'll recap quickly today.
Nó chạy lặp giá trị 100 vòng, về cơ bản là đủ để hội tụ trên MDP này.
It's run value iteration for 100 iterations, which is basically enough to converge on this MDP.
Đây là một thể hiện grid world với phần thưởng +1 và -1 ở cuối, ở hai ô phía trên bên phải.
So what's going on, this is a grid world instance with a plus 1 and a minus 1 reward at the end in those two upper right squares.
Ngoài ra còn có hệ số chiết khấu. Để tôi dời cái này để các bạn thấy hết chi tiết.
And then in addition, there is a discount factor.
Được rồi, hệ số chiết khấu ở đây là 0.9.
Here, let me move this so you can see all the details. OK, so the discount here is 0.9.
Được rồi, hệ số chiết khấu ở đây là 0.9. Hệ số chiết khấu ở đây là 0.9.
That means every step the reward is pushed into the future, it's going to be worth 0.9 times as much.
Nghĩa là cứ mỗi bước phần thưởng bị đẩy lùi về tương lai, nó chỉ còn giá trị bằng 0,9 lần trước đó.
And so if it's going to take you 10 steps to get to that 1.0, it's going to be worth less to you. And then, there's also a noise here.
Nên nếu bạn mất 10 bước để tới phần thưởng 1.0 đó, thì nó sẽ có giá trị thấp hơn với bạn. Ngoài ra, ở đây còn có nhiễu.
And in this case, I think there's not a living reward. So there's a noise of 0.2 as before. So what are these numbers? These numbers represent values.
Và trong trường hợp này, tôi nghĩ là không có phần thưởng sống. Vậy nhiễu là 0,2 như trước. Vậy những con số này là gì? Những con số này biểu diễn các giá trị.
So here, that's easy. If you're in this square here, the only possible future you have is the one where you get a 1, and then the game ends.
Ở đây thì dễ. Nếu bạn ở ô này, tương lai duy nhất bạn có là nhận được 1, rồi trò chơi kết thúc.
What does this 8.5 mean? Well, there's a lot of things that can happen. So let's say the policy is the one that's indicated here with the arrows, which is the optimal policy.
Còn 8.5 này nghĩa là gì? Có rất nhiều điều có thể xảy ra. Giả sử chính sách là cái được chỉ bằng các mũi tên ở đây, tức là chính sách tối ưu.
If I act, most of the time, I go into the exit, and I get that discounted 1. Except, 20% of the time, something different happens.
Nếu tôi hành động, phần lớn thời gian tôi đi vào ô thoát, và nhận được phần thưởng 1 đã chiết khấu. Trừ 20% số lần, có điều khác xảy ra.
Sometimes I'm still in this square, and then I go into the exit. Sometimes I slip to the hazard square that says 0.57 here and so on.
Đôi khi tôi vẫn ở lại ô này, rồi sau đó mới đi vào ô thoát. Đôi khi tôi trượt vào ô nguy hiểm ghi 0,57 ở đây, và cứ thế.
And so all of those possible futures, each has a weight. Because I know what actions I'm going to take, I can figure out that average.
Mỗi tương lai khả dĩ đó đều có một trọng số. Vì tôi biết mình sẽ thực hiện hành động nào, tôi có thể tính ra giá trị trung bình đó.
That's what that value is, it's the average utility you will get under optimal play, which in that case, is the policy that's shown. Let me bring that back for a second.
Giá trị đó chính là độ hữu dụng trung bình bạn nhận được khi chơi tối ưu, mà trong trường hợp này là chính sách đang hiển thị. Để tôi chiếu lại cái đó một chút.
Those are the values of the states. And remember, states also had four actions for the states that aren't exits, and each of those actions corresponds to a Q state.
Đó là các giá trị của các trạng thái. Và nhớ rằng, mỗi trạng thái cũng có bốn hành động với các trạng thái không phải ô thoát, và mỗi hành động ứng với một trạng thái Q.
So these are the Q values for those states.
Đây là các giá trị Q của những trạng thái đó.
And if you remember from this — I don't know whether you can see my cursor well here, but this one that was 0.85 that's just to the left of the 1.0 square, you can now see that value 0.85 that came from optimal play from that, is associated with the action of going east.
Và nếu bạn còn nhớ từ đây — Tôi không biết các bạn có thấy rõ con trỏ của tôi không, nhưng ô có giá trị 0,85 này nằm ngay bên trái ô 1.0, giờ bạn thấy giá trị 0,85 đến từ chơi tối ưu gắn với hành động đi về phía đông.
There are other actions that belong to that state, so there are three other Q states from that state, and those all have lower values.
Còn các hành động khác thuộc trạng thái đó, tức là có ba trạng thái Q khác từ trạng thái ấy, và chúng đều có giá trị thấp hơn.
So Q values, some are going to be high, some are going to be low.
Vậy các giá trị Q, có cái cao, có cái thấp.
In the same way that some states are good, and some are bad, and you should probably avoid the bad ones, some Q states are good and some states are bad, and you should probably avoid the bad ones.
Cũng như có trạng thái tốt, có trạng thái xấu, và bạn nên tránh những trạng thái xấu, có trạng thái Q tốt và có trạng thái Q xấu, và bạn nên tránh những cái xấu.
OK. The difference is you have more direct control over what Q states you pick because you get to pick A directly.
OK. Điểm khác là bạn kiểm soát trực tiếp hơn việc chọn trạng thái Q nào, vì bạn chọn trực tiếp A.
You don't get to pick S except by arranging a sequence of actions to get into that state. OK. All right.
Bạn không chọn được S, trừ khi sắp xếp một chuỗi hành động để đi vào trạng thái đó. OK. Được rồi.
OK. Last time, we talked about the Bellman equations. Actually, there's a whole bunch of things that can be called Bellman equations.
OK. Lần trước, chúng ta đã nói về các phương trình Bellman. Thực ra có cả một loạt thứ có thể gọi là phương trình Bellman.
Bellman equations are basically any equations that write down these quantities from MDPs, values, Q values, policies in terms of others of those quantities, usually in one time step ahead look ahead.
Phương trình Bellman về cơ bản là bất kỳ phương trình nào viết các đại lượng của MDP, giá trị, giá trị Q, chính sách theo các đại lượng khác, thường là nhìn trước một bước thời gian.
And they usually look like a little tiny fragment of an expectimax calculation. It basically boils down to this.
Và chúng thường trông như một mảnh nhỏ của phép tính expectimax. Về cơ bản nó quy về thế này.
If you want to do optimal things — because we've been talking about V star, V star, V star, that's the optimal value from a state.
Nếu bạn muốn làm điều tối ưu, vì chúng ta cứ nói V sao, V sao, V sao, đó là giá trị tối ưu của một trạng thái.
How the heck am I supposed to calculate how many points I'm going to get playing optimally if I don't even know what the policy is?
Làm sao tính được tôi sẽ có bao nhiêu điểm khi chơi tối ưu nếu tôi còn chưa biết chính sách là gì?
The whole point of these algorithms is to find optimal policies in most cases.
Mục đích của các thuật toán này phần lớn là tìm ra chính sách tối ưu.
So what the Bellman equations do is they break down that notion of optimality, which is this nebulous thing, into a one step mutual recursion that lets you nail down a property that optimal values would have into a system of equations you can then solve.
Vậy các phương trình Bellman làm là phân rã khái niệm tối ưu vốn khá mơ hồ này thành một đệ quy tương hỗ một bước, giúp xác định một tính chất mà các giá trị tối ưu phải có thành một hệ phương trình mà bạn có thể giải.
And they look like this. They basically say, whatever the optimal value is, it's going to look like doing the right thing where I plug in for the future other optimal values.
Và chúng trông như thế này. Về cơ bản chúng nói rằng, giá trị tối ưu là bao nhiêu thì nó trông như làm điều đúng đắn, với việc thế vào tương lai những giá trị tối ưu khác.
Of course, I don't know them, but you know, that'll be a problem for the algorithm, not for the math.
Tất nhiên tôi chưa biết chúng, nhưng bạn biết đấy, đó là vấn đề của thuật toán, không phải của toán học.
So that definition of optimal utility that we have via sort of this expectimax computation gives a one step look ahead relationship.
Vậy định nghĩa độ hữu dụng tối ưu mà ta có qua phép tính expectimax cho ta một quan hệ nhìn trước một bước.
We talked about this last time, so I'll go through this relatively quickly, but I think it's good to have it fresh for today because you're going to see variations of these equations.
Lần trước ta đã nói về chuyện này, nên tôi sẽ đi qua khá nhanh, nhưng nên để nó còn mới trong đầu cho hôm nay vì bạn sẽ thấy các biến thể của những phương trình này.
So what is the value of being in state S? What's that? You think, what I really want to know is what action should I take? OK, we'll get to that.
Vậy giá trị của việc ở trạng thái S là gì? Là gì nhỉ? Bạn nghĩ, cái tôi thực sự muốn biết là nên thực hiện hành động nào? OK, ta sẽ tới đó.
I promise. What is the value for state S? So V star, the optimal value in state S, is what I will get from state S on average if I play optimally.
Tôi hứa. Giá trị của trạng thái S là gì? V sao, giá trị tối ưu tại trạng thái S, là điểm trung bình tôi nhận được từ trạng thái S nếu chơi tối ưu.
Well, we know what that is. That's a max over these chance nodes that are right underneath. Well, what's the value of those chance nodes? Well they have values.
Ta biết nó là gì rồi. Đó là max trên các nút ngẫu nhiên nằm ngay bên dưới. Vậy giá trị của các nút ngẫu nhiên đó là gì? Chúng có giá trị.
Their values are Q values. Q of S comma A. And so we get this relationship between values and Q values, which is really simple.
Giá trị của chúng là các giá trị Q. Q của S phẩy A. Và ta có quan hệ này giữa giá trị và giá trị Q, rất đơn giản.
It says the optimum score from a state is going to be the score of the best Q state leaving that state. What does that mean?
Nó nói rằng điểm tối ưu từ một trạng thái là điểm của trạng thái Q tốt nhất đi ra từ trạng thái đó. Điều đó nghĩa là gì?
That means you maximize over all the actions, and you pick the best Q underneath.
Nghĩa là bạn lấy max trên mọi hành động, và chọn Q tốt nhất bên dưới.
Now of course, that doesn't really help you identify what V star is because you don't know what Q star is either. So you need to define Q in terms of something.
Tất nhiên, điều đó thực ra chưa giúp xác định V sao là gì, vì ta cũng chưa biết Q sao là gì. Nên ta cần định nghĩa Q theo một thứ khác.
Well, you'll do that in terms of the next layer of the tree, because the next layer of the tree is, again, max nodes. These are values, but they're values of different states.
Ta sẽ định nghĩa theo tầng tiếp theo của cây, vì tầng tiếp theo của cây lại là các nút max. Đây là các giá trị, nhưng là giá trị của những trạng thái khác.
So we can get this relation of states up at the top to states at the bottom, and that relation of states at sort of some time step to states one layer deeper in the tree, that's what the Bellman equations say.
Vậy ta có được quan hệ giữa các trạng thái ở trên cùng với các trạng thái ở dưới, và quan hệ giữa các trạng thái ở một bước thời gian nào đó với các trạng thái sâu hơn một tầng trong cây, chính là điều các phương trình Bellman nói.
So what is Q star? Well, this one is probably worth writing out quickly.
Vậy Q sao là gì? Cái này chắc đáng để viết ra nhanh.
So Q star — so the value, the expectimax value of a chance node is going to be the average over all the possible outcomes of that action from that state.
Q sao, tức là giá trị expectimax của một nút ngẫu nhiên, sẽ là trung bình trên mọi kết quả có thể của hành động đó từ trạng thái đó.
So we're going to have to average over all the outcomes. Each outcome has a weight. That weight is T S A S prime. That's the conditional probability of S prime given S and A.
Vậy ta phải lấy trung bình trên mọi kết quả. Mỗi kết quả có một trọng số. Trọng số đó là T của S, A, S phẩy. Đó là xác suất có điều kiện của S phẩy khi biết S và A.
Now, for each S prime, I need to know what score I'm going to get if I land in that S prime.
Với mỗi S phẩy, tôi cần biết mình sẽ được điểm bao nhiêu nếu rơi vào S phẩy đó.
Well, right that instant, we're going to get a reward S A, R of SAS prime, and then I'm going to land in S prime. What's going to happen then?
Ngay lúc đó, ta sẽ nhận một phần thưởng, R của S, A, S phẩy, rồi tôi sẽ đáp xuống S phẩy. Sau đó chuyện gì xảy ra?
Well, of course, I will play optimally. What does that mean? I have no idea, but I have a symbol for it. And the symbol for it is V star of S prime.
Tất nhiên, tôi sẽ chơi tối ưu. Điều đó nghĩa là gì? Tôi không biết, nhưng tôi có một ký hiệu cho nó. Ký hiệu đó là V sao của S phẩy.
OK, and there's a gamma in there to discount things in the future.
Và có thêm gamma ở đó để chiết khấu phần tương lai.
So what this does, if you inline them — let me make my marginal handwriting go away and be replaced with beautiful [INAUDIBLE].. So we can define V in terms of Q.
Nên nếu thế các cái này vào nhau... để tôi xóa nét chữ xấu của mình đi và thay bằng chữ đẹp [KHÔNG NGHE RÕ]. Vậy ta có thể định nghĩa V theo Q.
That is the recursion where you write the value of a max node in terms of its child chance nodes.
Đó là đệ quy, trong đó ta viết giá trị của nút max theo các nút ngẫu nhiên con của nó.
You can write Q in terms V. That's where you say that a chance node is the average of its children in expectimax.
Ta có thể viết Q theo V. Đó là chỗ ta nói rằng một nút ngẫu nhiên là trung bình của các nút con trong expectimax.
And if you inline that, you get the standard form of the Bellman equation. You'll notice the Q's are gone. That's the variable that you inline. So this here is the standard form.
Và nếu thế vào nhau, ta được dạng chuẩn của phương trình Bellman. Các bạn để ý Q đã biến mất. Đó là biến mà ta đã thế vào. Vậy đây là dạng chuẩn.
What does it say? It says, if I want to compute optimal values, which like, a minute ago, I wasn't really even sure what they were. Now I have an expression for them.
Nó nói gì? Nó nói rằng, nếu muốn tính các giá trị tối ưu, mà cách đây một phút tôi còn chưa chắc chúng là gì, thì giờ ta đã có một biểu thức cho chúng.
It says the optimal value has the property that it's the best of the actions that you can take from that state where each action has a value that is an instantaneous reward plus optimal future discounted, blended together by your averaging function.
Giá trị tối ưu có tính chất là hành động tốt nhất trong các hành động có thể làm từ trạng thái đó, trong đó mỗi hành động có một giá trị là phần thưởng tức thời cộng với tương lai tối ưu đã chiết khấu, được trộn lại bằng hàm trung bình của bạn.
So that's the Bellman equation for optimal values. It relates V stars to V stars. And you say, does that help me?
Đó là phương trình Bellman cho các giá trị tối ưu. Nó liên hệ các V sao với các V sao. Bạn sẽ hỏi: thế có giúp được gì không?
Because I'm trying to find V stars, and if I need V stars to get V stars, how am I ahead? But this is just how systems of equations work.
Vì tôi đang tìm các V sao, mà cần V sao để có V sao thì tiến được gì? Nhưng hệ phương trình vốn hoạt động như vậy.
This characterizes the optimal values. It is not an algorithm for computing it. But we're a step ahead of where we were before.
Cái này mô tả đặc trưng của các giá trị tối ưu. Nó không phải thuật toán để tính chúng. Nhưng ta đã tiến thêm một bước so với trước.
We have a system of equations we're trying to solve, and that's a precise thing because now, I have techniques for solving systems of equations. OK. Any questions on that?
Ta có một hệ phương trình cần giải, và đó là thứ chính xác, vì giờ tôi có các kỹ thuật để giải hệ phương trình. Được rồi. Có câu hỏi nào về phần này không?
That's the core bit. OK, so we have this algorithm. Value iteration. I'm not going to go through an example, but I want to show how it relates to the equation I just showed.
Đó là phần cốt lõi. Vậy ta có thuật toán này. Lặp giá trị. Tôi sẽ không làm ví dụ, nhưng muốn cho thấy nó liên quan thế nào đến phương trình tôi vừa trình bày.
So Bellman equations characterize the optimal values. They say, V star has this property that it's sort of equal to this expectimax fragment with other V stars plugged in for the future.
Các phương trình Bellman mô tả đặc trưng của các giá trị tối ưu. Chúng nói V sao có tính chất là bằng đoạn expectimax này với các V sao khác được thế vào cho tương lai.
So we're defining V star in terms of V star, right? That is a system of equations. Can I solve this one? Well, it's not the easiest system of equations because of that max.
Vậy ta định nghĩa V sao theo V sao, đúng không? Đó là một hệ phương trình. Tôi có giải được nó không? Đây không phải hệ phương trình dễ nhất vì có phép max đó.
Without that max, it would be a linear system. But with that max, it's kind of hard.
Không có max thì nó là hệ tuyến tính. Nhưng có max thì khá khó.
Value iteration, which we talked about last time and ran an example of, computes these values, and it computes them using an update that looks exactly like the Bellman equation and is called a Bellman update.
Lặp giá trị, mà ta đã nói lần trước và chạy ví dụ, tính các giá trị này, và tính bằng một phép cập nhật trông giống hệt phương trình Bellman và được gọi là cập nhật Bellman.
So the equation has the same quantities on the left and right. The update does not.
Phương trình có cùng các đại lượng ở vế trái và vế phải. Phép cập nhật thì không.
So in the update, what we do is we say, well, I don't know how to solve that system of equations directly, but if I imagine I had an approximation V K to the values of all the states — maybe it's a bad approximation.
Trong phép cập nhật, ta nói rằng: tôi không biết giải trực tiếp hệ phương trình đó, nhưng nếu tôi có một xấp xỉ V K cho giá trị của mọi trạng thái, có thể đó là xấp xỉ tệ, có thể là 0.
Maybe it's 0. In fact, V 0 will be 0.
Thực ra V 0 sẽ bằng 0.
If I had an approximation to the values of all the states, I could get a better approximation, or at least a new approximation to the values of all the states, by running from each state, a one step, one ply expectimax search, plugging in my old approximation as the future cost.
Nếu tôi có một xấp xỉ giá trị của mọi trạng thái, tôi có thể có xấp xỉ tốt hơn, hay ít nhất là một xấp xỉ mới cho giá trị của mọi trạng thái, bằng cách từ mỗi trạng thái chạy tìm kiếm expectimax một bước, một ply, thế xấp xỉ cũ của tôi vào làm chi phí tương lai.
So here, what I would do is I would say, well, I want to know the value of this, so I'm going to run expectimax. I'm going to max over the children.
Ở đây, tôi sẽ nói rằng tôi muốn biết giá trị của cái này, nên tôi chạy expectimax. Tôi lấy max trên các nút con.
For each child, I'm going to average over the children. And then, when I have to put in something that represents the whole future, I'm going to plug in my old estimate.
Với mỗi nút con, tôi lấy trung bình trên các nút con của nó. Rồi khi phải đặt vào thứ gì đó đại diện cho toàn bộ tương lai, tôi thế ước lượng cũ vào.
Right?
Đúng không?
And we also had these subscripts K. K represented not just the iteration of the algorithm, but how many rewards were taken into account in that computation, so V 0 takes into account 0 rewards.
Và ta cũng có các chỉ số dưới K này. K không chỉ đại diện của thuật toán, mà còn là số phần thưởng được tính đến trong phép tính đó, nên V 0 tính đến 0 phần thưởng.
You produce V 1, which is equivalent to a depth 1 tree being computed over. Depth 2, depth 3, depth 4.
Bạn tạo ra V 1, tương đương với việc tính trên một cây có độ sâu 1. Độ sâu 2, độ sâu 3, độ sâu 4.
And as you run this iteration over and over again, you get successive approximations, and I told you but did not prove to you that they will converge. OK.
Và khi bạn chạy phép lặp này hết lần này đến lần khác, bạn có các xấp xỉ liên tiếp, và tôi đã nói nhưng chưa chứng minh là chúng sẽ hội tụ. OK.
Any questions on that? Yep.
Có câu hỏi nào không? Mời bạn.
STUDENT
So are we going depth one, depth two, and depth three, or [INAUDIBLE].
Vậy mình đi theo độ sâu một, độ sâu hai, rồi độ sâu ba, hay là [KHÔNG NGHE RÕ].
PROFESSOR
Yeah. So the question is, are you going sort of down the tree kind of like expectimax? This is sort of like a lot of dynamic programs, everything's been flipped around.
Vâng. Câu hỏi là, mình có đi xuống cây giống như expectimax không? Cái này giống nhiều bài quy hoạch động, mọi thứ bị đảo ngược lại.
We compute V 0 which represents all of the possible depth 0 trees. Right? V 0 of this state, V 0 of this state, and so on, and you compute all the V 0's.
Ta tính V 0, đại diện cho tất cả các cây có độ sâu 0 có thể có. Đúng không? V 0 của trạng thái này, V 0 của trạng thái này, và cứ thế, bạn tính tất cả các V 0.
And so now I know what any depth 0 expectimax will be, which is 0. Then I compute all the V 1's, which is all the depth 1 trees.
Vậy giờ tôi biết expectimax độ sâu 0 bất kỳ sẽ bằng bao nhiêu, đó là 0. Rồi tôi tính tất cả các V 1, tức là tất cả cây độ sâu 1.
And then I compute all the v 2's. Now, V 2 trees would start to get expensive, except I'm just going to plug in my V 1 answers after one layer.
Rồi tôi tính tất cả các V 2. Cây V 2 bắt đầu tốn kém, trừ việc tôi chỉ cần thay đáp án V 1 vào sau một tầng.
So each layer of this is like one ply of expectimax from every state, and it'll just be grabbing things from my cache from the previous approximation.
Vậy mỗi tầng giống như một ply của expectimax từ mọi trạng thái, và nó chỉ lấy các giá trị từ bộ nhớ đệm của xấp xỉ trước.
So as I go, I am getting the values from deeper and deeper trees. But it sort of feels like you start at the bottom and work your way up.
Khi đi tiếp, tôi nhận được giá trị từ những cây ngày càng sâu hơn. Nhưng cảm giác là bạn bắt đầu từ đáy và đi dần lên.
OK? Good question. All right. So value iteration.
OK? Câu hỏi hay. Được rồi. Vậy là lặp giá trị.
Last time, we talked about these time limited values. I'm not going to get into that again.
Lần trước ta đã nói về các giá trị giới hạn thời gian. Tôi sẽ không nhắc lại.
But from here, I can actually just look at this and say that was a system of equations, and I am solving it using a fixed point solution method.
Nhưng từ đây, tôi có thể nhìn vào đây và nói đó là một hệ phương trình, và tôi đang giải nó bằng phương pháp điểm bất động.
I take my values from my variables, I push them from one side of the equation to the other, and then I do it again and again and again, and if I find a fixed point, I'm solved.
Tôi lấy giá trị từ các biến, đẩy chúng từ vế này sang vế kia của phương trình, rồi làm lại hết lần này đến lần khác, và nếu tìm được điểm bất động thì coi như đã giải xong.
Now of course, with fixed point methods, we don't know it's going to converge, but this is a fixed point method and I'm claiming to you it will converge.
Tất nhiên, với các phương pháp điểm bất động, ta không biết nó có hội tụ không, nhưng đây là phương pháp điểm bất động và tôi khẳng định với bạn là nó sẽ hội tụ.
OK? How do we know it will converge? I just so happen to have a slide on it. OK, so I'm going to sketch a proof.
OK? Làm sao biết nó sẽ hội tụ? Tình cờ tôi có một slide về chuyện này. OK, tôi sẽ phác thảo một chứng minh.
All right. So if you're totally clear on value iteration, great.
Được rồi. Nếu bạn đã hiểu rõ lặp giá trị thì tốt.
If you're still trying to kind of figure out, what is this update, all you really need to know is that V K, a vector of values for each state, is a sequence of approximations to the values which may or may not converge.
Nếu bạn vẫn đang cố hiểu phép cập nhật này là gì, bạn chỉ cần biết V K, một vectơ giá trị cho mỗi trạng thái, là một dãy các xấp xỉ của các giá trị có thể hội tụ hoặc không.
OK, and the first one is going to be 0.
OK, và cái đầu tiên sẽ là 0.
Moreover, V K represents the result of running expectimax over a depth K tree or equivalently the expected utility for K steps starting in a given state.
Hơn nữa, V K biểu diễn kết quả của việc chạy expectimax trên cây độ sâu K, hay tương đương là độ hữu dụng kỳ vọng trong K bước bắt đầu từ một trạng thái cho trước.
OK. That's what you need to have in order to follow the sketch here.
OK. Đó là những gì bạn cần để theo dõi phần phác thảo này.
So how do we know that these vectors of V K are going to converge, provided they are indeed computing these depth K computations?
Vậy làm sao biết các vectơ V K này sẽ hội tụ, miễn là chúng thực sự tính các phép tính độ sâu K này?
Case one, the actual tree of the MDP has a maximum depth. Well then once I get to that depth, I actually have untruncated exact values, and I'm done.
Trường hợp một, cây thực sự của MDP có độ sâu tối đa. Khi đó, một khi tới độ sâu ấy, tôi có giá trị chính xác, không bị cắt cụt, và xong.
But that's a little weird. That only works for MDPs that actually, when you unroll them from every single state, they unroll into a tree that terminates within M steps every single time.
Nhưng cái đó hơi kỳ. Nó chỉ áp dụng cho các MDP mà khi bạn khai triển từ mỗi trạng thái, chúng triển khai thành cây kết thúc trong M bước, lần nào cũng vậy.
That usually only happens if you actually have a timer in your MDP and you have some time limited state space. Case two, this is the general case.
Điều đó thường chỉ xảy ra nếu MDP của bạn có bộ đếm thời gian và có một không gian trạng thái giới hạn thời gian. Trường hợp hai, đây là trường hợp tổng quát.
And in this case, in order to show that it's going to converge, we assume that the discount gamma is less than 1. And the argument goes something like this.
Và ở đây, để chứng minh nó hội tụ, ta giả sử hệ số chiết khấu gamma nhỏ hơn 1. Và lập luận như sau.
Well, what does V K compute? Well for any given state, V K computes the result of running expectimax to depth K. So K times steps in the future.
V K tính cái gì? Với một trạng thái bất kỳ, V K tính kết quả của việc chạy expectimax đến độ sâu K. Tức là K bước trong tương lai.
V K plus 1 from each state looks at K plus 1 steps into the future, so the tree is one layer deeper, but they're otherwise identical. OK.
V K cộng 1 từ mỗi trạng thái nhìn K cộng 1 bước vào tương lai, nên cây sâu hơn một tầng, nhưng ngoài ra thì giống hệt nhau. OK.
So we think, well, how different can it be if you take a tree of depth K and another tree of depth K plus 1 that's equivalent for the top K layers?
Vậy ta nghĩ, hai cây, một cây độ sâu K và một cây độ sâu K cộng 1, giống nhau ở K tầng trên cùng thì khác nhau được bao nhiêu?
How different can they possibly be? Well, we can think of this one on the left as actually being depth K plus 1, because we can pad out the bottom with what value?
Chúng có thể khác nhau nhiều nhất là bao nhiêu? Ta có thể coi cây bên trái cũng có độ sâu K cộng 1, vì ta có thể đệm thêm ở đáy với giá trị nào?
STUDENT
0.
0.
PROFESSOR
0. OK? So the trees are the same, except the bottom layers are different. On the left, there's the value 0 on the bottom layer.
0. OK? Vậy hai cây giống nhau, chỉ khác các tầng đáy. Bên trái, tầng đáy có giá trị 0. Bên phải thì giá trị là gì?
On the right, what's the value? Who knows?
Ai biết được?
It's whatever the rewards in the MDP are, but at worst, it's sort of R min, some lower bound on the rewards, and at most, it's R max. So there's a range, there's a bound.
Nó là phần thưởng nào đó trong MDP, nhưng tệ nhất là R min, một cận dưới của phần thưởng, và nhiều nhất là R max. Vậy có một khoảng, có một cận. OK?
OK? So at worst, it's one. At best, it's the other. Now, up here, things are undiscounted.
OK? Trường hợp xấu nhất thì nó là giá trị này. Trường hợp tốt nhất thì là giá trị kia. Ở phía trên này, mọi thứ không bị chiết khấu.
Down here, things are discounted pretty heavily. Down here, things are discounted by gamma to the K.
Còn ở dưới này, mọi thứ bị chiết khấu khá mạnh. Ở dưới này, mọi thứ bị chiết khấu bởi gamma mũ K.
So all those rewards down there, they're pretty small when you add them together with the stuff up above. OK. And so when I look and I say, what pops out of this calculation?
Nên tất cả các phần thưởng ở dưới đó khá nhỏ khi cộng lại với phần phía trên. OK. Và khi nhìn vào và hỏi, phép tính này cho ra kết quả gì?
Well there's this max and the average in the max, but all of those things that I'm maxing and averaging and maxing, in one case, have a 0 at the end, and in the other case, have one of these other terms at the end.
Có max và trung bình bên trong max, nhưng tất cả những thứ mà ta lấy max rồi trung bình rồi lại max, ở một trường hợp thì kết thúc bằng số 0, còn ở trường hợp kia thì kết thúc bằng một trong các số hạng khác ở cuối.
So the difference between them is that most, bounded by the difference between R min and R max here, discounted gamma to the K.
Vậy chênh lệch giữa chúng tối đa bị chặn bởi hiệu giữa R min và R max, nhân chiết khấu gamma mũ K.
So these two values of the root can't be that different, because they're the same until the bottom and that bottom is heavily discounted.
Nên hai giá trị tại gốc này không thể khác nhau nhiều, vì chúng giống nhau cho đến tận đáy, và phần đáy đó bị chiết khấu rất mạnh.
So as K increases, that difference between the values gets pushed further and further, which means it has more and more layers of gamma, and therefore, the difference between successive rounds of this algorithm's approximations are going to shrink in this way.
Khi K tăng, chênh lệch giữa các giá trị bị đẩy ngày càng xa, nghĩa là có ngày càng nhiều lớp gamma, và do đó, chênh lệch giữa các xấp xỉ của các vòng liên tiếp của thuật toán sẽ co lại theo cách này.
OK? That's a sketch. That's not all the details, but that's the basic idea. It's a contraction argument.
OK? Đó là một bản phác thảo. Chưa đủ chi tiết, nhưng đó là ý tưởng cơ bản. Đó là lập luận co (contraction).
OK. All right. That was louder than I expected. Sorry.
OK. Được rồi. To hơn tôi tưởng. Xin lỗi.
Policy methods. Let's talk about policy methods here. So what have we talked about so far? We talked about important quantities in MDPs.
Các phương pháp chính sách. Ta bàn về các phương pháp chính sách. Cho đến giờ ta đã nói về những gì? Ta đã nói về các đại lượng quan trọng trong MDP.
We talked a lot about what the value of a state is and how I can compute it in terms of values of other states, which then gave us the value iteration algorithm.
Ta nói nhiều về giá trị của một trạng thái và cách tính nó theo giá trị của các trạng thái khác, từ đó ra thuật toán lặp giá trị.
Except this is weird in a couple of ways. One, I don't think any of you woke up this morning thinking, I really want to know how to find the value of a state.
Nhưng điều này hơi lạ ở vài điểm. Một, tôi không nghĩ ai trong các bạn sáng nay thức dậy và nghĩ, mình thực sự muốn biết cách tìm giá trị của một trạng thái.
In the same way that when you run minimax, you don't really care the minimax value of the root.
Cũng như khi chạy minimax, bạn không thực sự quan tâm giá trị minimax của gốc.
You're running minimax to get the action at the root, so we've got to like anchor this back to policies, because we're trying to figure out how to act.
Bạn chạy minimax để lấy hành động tại gốc, nên ta phải neo nó lại với chính sách, vì ta đang tìm cách hành động.
The other thing is, value iteration, as we saw last time, can be pretty slow, and so we're going to talk about better methods to do that.
Điều còn lại là, lặp giá trị, như ta thấy lần trước, có thể khá chậm, nên ta sẽ bàn về các phương pháp tốt hơn.
So we're going to talk about methods that look at policies, evaluating policies, improving policies, and extracting policies. And then we'll be in a position to move on to reinforcement learning.
Ta sẽ nói về các phương pháp xem xét chính sách: đánh giá chính sách, cải thiện chính sách và trích xuất chính sách. Rồi ta sẽ sẵn sàng chuyển sang học tăng cường.
There's a question.
Có một câu hỏi.
STUDENT
Yeah. What's the proof if, like, when gamma's 1?
Vâng. Chứng minh sẽ thế nào khi gamma bằng 1?
PROFESSOR
What's the proof if gamma's 1? If gamma's 1, they may not converge, because you can easily have MDPs where the values diverge.
Chứng minh khi gamma bằng 1 ư? Nếu gamma bằng 1, chúng có thể không hội tụ, vì dễ có những MDP mà giá trị phân kỳ.
Even the values themselves may not be finite, so all kinds of things.
Thậm chí bản thân các giá trị có thể không hữu hạn, đủ thứ chuyện.
Now there are other cases that you can imagine, like if you can guarantee an absorbing state or something, it becomes analogous to the fixed depth. It's a great question.
Cũng có những trường hợp bạn có thể hình dung, như nếu đảm bảo có trạng thái hấp thụ chẳng hạn, thì nó tương tự trường hợp độ sâu cố định. Câu hỏi rất hay.
Yeah, it's a very important point. When gamma's 1, you don't really have these convergent guarantees.
Vâng, đó là một điểm rất quan trọng. Khi gamma bằng 1, bạn không thực sự có các đảm bảo hội tụ này.
All right, policy methods. First one is policy evaluation. So up until now, we've been talking about calculating quantities that are optimal quantities. What is the value of this state if I act optimally?
Được rồi, các phương pháp chính sách. Đầu tiên là đánh giá chính sách. Cho đến giờ, ta tính các đại lượng tối ưu. Giá trị của trạng thái này là bao nhiêu nếu tôi hành động tối ưu?
OK, policy evaluation's simpler. In policy evaluation, someone has given you a policy. It may be good, it may be bad, it may be optimal, it may be terrible.
OK, đánh giá chính sách thì đơn giản hơn. Trong đánh giá chính sách, ai đó đưa cho bạn một chính sách. Nó có thể tốt, có thể xấu, có thể tối ưu, có thể tệ hại.
All you want to know is, how good is this policy? Tell me for each state what my score will be if I do the thing written on this map.
Bạn chỉ muốn biết: chính sách này tốt đến mức nào? Hãy cho biết với mỗi trạng thái, điểm của tôi sẽ là bao nhiêu nếu tôi làm theo những gì ghi trên bản đồ này.
OK, and the answer might be, all right, it's bad, or it's really good. How are computations different if you have a fixed policy? Well it turns out they're much, much easier.
OK, và câu trả lời có thể là: nó tệ, hoặc nó thực sự tốt. Tính toán khác đi thế nào khi có chính sách cố định? Hóa ra nó dễ hơn nhiều.
And the short reason why they're easier is all those maxes go away. You don't have to think about what's the best action. Someone has told you the action.
Lý do ngắn gọn khiến nó dễ hơn là tất cả các phép max biến mất. Bạn không phải nghĩ hành động nào là tốt nhất. Người ta đã cho bạn biết hành động rồi.
All you have to think about is the different possible outcomes, and that just forms some big linear system that's a lot easier to work with.
Bạn chỉ cần nghĩ đến các kết quả có thể xảy ra, và nó tạo thành một hệ tuyến tính lớn dễ xử lý hơn nhiều.
So in expectimax, or a general MDP when you're computing an optimal quantity, which is what expectimax does, you form a computation tree that considers all the possible actions so that you can max over them and thereby choose the best one.
Trong expectimax, hay một MDP tổng quát khi bạn tính một đại lượng tối ưu, đúng như expectimax làm, bạn lập một cây tính toán xét mọi hành động có thể để lấy max trên chúng và nhờ đó chọn hành động tốt nhất.
OK. So what do you do?
OK. Vậy bạn làm gì?
Well you take your state, you max over all the actions, and then for each of those possible actions, you compute the value of that action, which is the Q value.
Bạn lấy trạng thái, lấy max trên mọi hành động, rồi với mỗi hành động có thể đó, bạn tính giá trị của hành động, tức là giá trị Q.
OK? That's what happens when you're trying to do optimal things. This is the computation of V star of S. That's what it looks like.
OK? Đó là điều xảy ra khi bạn cố làm những việc tối ưu. Đây là phép tính V sao của S. Nó trông như vậy.
And then, of course, it continues down. What if you had some fixed policy? Well, now you don't have to act optimally anymore. You just have to act the way pi tells you.
Và tất nhiên, nó tiếp tục đi xuống. Còn nếu bạn có một chính sách cố định thì sao? Giờ bạn không cần hành động tối ưu nữa. Bạn chỉ cần hành động theo những gì pi bảo.
You just have to follow pi.
Bạn chỉ cần theo pi.
So if pi were telling you what to do, we wouldn't be trying to compute V star of S, the score or utility under optimal action, which is hard because we don't know what optimal action.
Nên nếu pi cho bạn biết phải làm gì, ta sẽ không cố tính V sao của S, điểm số hay độ hữu dụng khi hành động tối ưu, điều rất khó vì ta không biết hành động tối ưu là gì.
Now we're in this much easier world where all we have to do is figure out what our average score will be if we do pi. We know what pi is.
Giờ ta ở trong một thế giới dễ hơn nhiều, nơi ta chỉ cần tính xem điểm trung bình sẽ là bao nhiêu nếu ta làm theo pi. Ta biết pi là gì.
It's given to us as input, so we only have to evaluate this one policy.
Nó được cho sẵn làm đầu vào, nên ta chỉ phải đánh giá một chính sách này thôi.
And that means that when you're at the equivalent of a max node here, and you're computing the value of a state, it's a value according to pi.
Và điều đó có nghĩa là khi bạn ở vị trí tương đương một nút max ở đây, và bạn đang tính giá trị của một trạng thái, thì đó là giá trị theo pi.
There's only one edge going out of it. There's only one action. Pi is telling you to do pi of S, so you do it.
Chỉ có một cạnh đi ra từ nó. Chỉ có một hành động. Pi bảo bạn làm pi của S, thì bạn làm thế.
Now of course, there's still the same — some you have to think about over all the possible outcomes. The policy won't tell you what will happen. It will just tell you what to do.
Dĩ nhiên vẫn còn như cũ... bạn vẫn phải cân nhắc tất cả các kết quả có thể xảy ra. Chính sách không cho bạn biết điều gì sẽ xảy ra. Nó chỉ cho bạn biết phải làm gì.
So it's the max nodes that get simpler. All right? So let's think about utilities for a fixed policy. In some ways, these, I think, are easier to think about than the optimal ones.
Vậy là các nút max được đơn giản đi. Rõ chưa? Giờ hãy nghĩ về độ hữu dụng với một chính sách cố định. Theo một cách nào đó, tôi nghĩ những cái này dễ hình dung hơn các cái tối ưu.
So another basic operation with MDPs is to compute the utility of a state, not under optimal play but under a fixed presumably non-optimal and general policy.
Một thao tác cơ bản khác với MDP là tính độ hữu dụng của một trạng thái, không phải khi chơi tối ưu mà theo một chính sách cố định, có thể không tối ưu và tổng quát.
So let's define the utility of a state under a fixed policy of pi. V pi of S is going to be the expected total discounted rewards starting in that state and following pie.
Vậy ta định nghĩa độ hữu dụng của một trạng thái theo một chính sách cố định pi. V pi của S là tổng phần thưởng chiết khấu kỳ vọng khi bắt đầu ở trạng thái đó và làm theo pi.
That's again, given by this tree, except now there's no max nodes anymore. There's just pi nodes and then chance nodes, so we can compute that out with the same kind of recursive relation.
Nó vẫn được cho bởi cây này, nhưng giờ không còn nút max nữa. Chỉ còn các nút pi rồi đến các nút ngẫu nhiên, nên ta có thể tính nó bằng cùng kiểu quan hệ đệ quy.
So I can say, well I don't know what V pi of a state S is, but I can look at my fragment and I can say, luckily, I don't have to max over A anymore, but I still need to average over what's going to happen when I do pi of S.
Tôi có thể nói: tôi không biết V pi của trạng thái S là bao nhiêu, nhưng tôi nhìn vào đoạn cây này và nói, may quá, tôi không phải lấy max theo A nữa, nhưng tôi vẫn cần lấy trung bình theo những gì sẽ xảy ra khi tôi làm pi của S.
So I whip out my trusty average. I average over the possible S primes that could happen if I did pi of S from state S, and I take an average.
Vậy tôi lôi phép lấy trung bình quen thuộc ra. Tôi lấy trung bình trên các S phẩy có thể xảy ra nếu tôi làm pi của S từ trạng thái S, và tôi lấy trung bình.
Well the probability that S prime will happen if I take pi of S as my action is that transition function. And then what score will I get? Well, I'll get a reward right then.
Xác suất S phẩy xảy ra nếu tôi chọn pi của S làm hành động chính là hàm chuyển. Và ta sẽ được điểm bao nhiêu? Ta nhận được phần thưởng ngay lúc đó.
It'll be the rewards corresponding to being in state S, taking pi of S, and then landing in this S prime, and I'm going to consider them all.
Đó là phần thưởng ứng với việc ở trạng thái S, làm pi của S, rồi đáp xuống S phẩy này, và tôi sẽ xét tất cả các trường hợp.
Plus, remember the utility is the current reward plus discounted future rewards. So I discount my future, and then I plug in my future rewards.
Cộng thêm, nhớ rằng độ hữu dụng là phần thưởng hiện tại cộng phần thưởng tương lai đã chiết khấu. Vậy tôi chiết khấu tương lai, rồi điền phần thưởng tương lai vào.
My future rewards are from state S prime, and the future value is not the optimal value from S prime, but presuming I continue to do what pi says, V pi of S prime.
Phần thưởng tương lai tính từ trạng thái S phẩy, và giá trị tương lai không phải giá trị tối ưu từ S phẩy, mà là giả sử tôi tiếp tục làm theo pi, tức V pi của S phẩy.
So this looks a lot like the equation before, except you'll notice the max over A has been replaced by A equals pi of S, so it's a little easier.
Nên phương trình này giống phương trình lúc trước, chỉ khác là max theo A được thay bằng A bằng pi của S, nên dễ hơn một chút.
There it is. And this is actually — if you look at this now, this is now a linear system of equations.
Đây rồi. Và thật ra, nếu nhìn vào đây, đây giờ là một hệ phương trình tuyến tính.
So in the back of your head, you just think, even if I totally space this algorithm I'm about to learn, I can always just solve linear equations by sticking them in MATLAB or something.
Nên trong đầu bạn cứ nghĩ, dù tôi có quên sạch thuật toán sắp học này đi nữa, tôi vẫn luôn giải được hệ tuyến tính bằng cách đưa vào MATLAB hay gì đó.
All right, so let's think of an example. Here is one of our robots in a grid world, and this robot has been handed the always go right policy.
Được rồi, xét một ví dụ. Đây là một robot của chúng ta trong thế giới lưới, và robot này được giao chính sách luôn đi sang phải.
This is a policy. Is it a good policy? It's a pretty bad policy. How likely are you to actually make it across the bridge?
Đây là một chính sách. Nó có tốt không? Nó khá tệ. Khả năng bạn qua được cây cầu là bao nhiêu?
Pretty unlikely. You have to like — the robot's going to continually try to throw itself off the bridge, and like, maybe it fails over and over again and gets to the other side.
Khá thấp. Bạn phải kiểu là... robot cứ liên tục cố lao mình xuống khỏi cầu, và có thể nó thất bại hết lần này đến lần khác rồi qua được bên kia.
This is a bad policy, OK? Here's another policy. This one's a presumably optimal one of always go forward. OK, so here are two policies under the same MDP.
Đây là chính sách tệ, được chứ? Đây là một chính sách khác. Cái này có lẽ là tối ưu: luôn đi thẳng. Vậy là có hai chính sách trong cùng một MDP.
Each state is going to have a value for the first policy and each state is going to have a value for the second policy.
Mỗi trạng thái sẽ có một giá trị cho chính sách đầu và một giá trị cho chính sách thứ hai.
In general, the values are going to be higher for the second policy because you accumulate more rewards. But every policy has a value function, the values are just sometimes bad.
Nói chung, giá trị sẽ cao hơn với chính sách thứ hai vì bạn tích lũy được nhiều phần thưởng hơn. Nhưng chính sách nào cũng có một hàm giá trị, chỉ là đôi khi các giá trị rất tệ.
OK.
OK.
From these scenarios that I showed you here with the different policies, here are the actual values of those policies.
Từ các tình huống tôi vừa cho xem với các chính sách khác nhau, đây là giá trị thực của các chính sách đó.
So of course, the exact numbers depend on what we associate with falling off the cliff. Here, it's minus 10. Getting to the edge is 100, and then what's the discount?
Dĩ nhiên các con số cụ thể phụ thuộc vào điểm ta gán cho việc rơi khỏi vách. Ở đây là trừ 10. Đến lối ra là 100, còn hệ số chiết khấu là bao nhiêu?
What's the living reward?
Phần thưởng sống là bao nhiêu?
So don't worry about the specific numbers, but for some reasonable setting of this MDP, you can see that always go right has a really, really bad — so V of always go right is really bad unless you happen to be in the exit square, because you have no choice but to get your reward.
Đừng lo về các con số cụ thể, nhưng với một thiết lập hợp lý của MDP này, bạn thấy luôn đi sang phải có giá trị rất, rất tệ... tức V của luôn đi sang phải rất tệ, trừ khi bạn tình cờ đang ở ô thoát, vì bạn không có lựa chọn nào ngoài việc nhận phần thưởng.
It's like, kind of not too bad from this state, because there's a decent enough chance that you'll fail to throw yourself off the cliff that you get a couple points.
Từ trạng thái này thì cũng không quá tệ, vì có khá nhiều khả năng bạn không lao được xuống vách nên bạn có được vài điểm.
OK? Always go forward, what's that V? It also has an identically shaped value function.
OK? Luôn đi thẳng thì V ra sao? Nó cũng có một hàm giá trị cùng hình dạng.
Each square has a value, except now the values are much better, because for most states, your expected discounted rewards will be higher. It's a better policy.
Mỗi ô có một giá trị, nhưng giờ các giá trị tốt hơn nhiều, vì với hầu hết trạng thái, phần thưởng chiết khấu kỳ vọng sẽ cao hơn. Đó là chính sách tốt hơn.
So one way to find a good policy is to enumerate all the policies, evaluate them all, and pick the one where the numbers are the highest.
Vậy một cách để tìm chính sách tốt là liệt kê mọi chính sách, đánh giá hết chúng, rồi chọn cái có các con số cao nhất.
It's not a good algorithm, but the point here is you can think of the policy as a thing you search over, and we're going to start doing that right now.
Đây không phải thuật toán tốt, nhưng điểm quan trọng ở đây là bạn có thể xem chính sách như thứ để tìm kiếm trên đó, và ngay bây giờ chúng ta sẽ bắt đầu làm điều đó.
Any questions? All right, policy evaluation.
Có câu hỏi nào không? Được rồi, đánh giá chính sách (policy evaluation).
One trick we do over and over again with these Bellman systems of equations, or should I say systems of Bellman equations, is we take these equality equations that we don't know how to solve, we turn the equalities into updates, and then, provided certain conditions hold, we know that those updates will converge to the right fixed points.
Có một mẹo ta dùng đi dùng lại với các hệ phương trình Bellman này, hay nói đúng hơn là hệ các phương trình Bellman, đó là ta lấy những phương trình đẳng thức mà ta không biết giải, rồi biến đẳng thức thành các bước cập nhật, và nếu một số điều kiện nhất định được thỏa, ta biết các bước cập nhật đó sẽ hội tụ về đúng các điểm bất động.
So how do we calculate V's? Well, one idea is we can turn these recursive equations into updates. It's just like value iteration, except it's easier.
Vậy ta tính các giá trị V như thế nào? Một ý tưởng là biến các phương trình đệ quy này thành các bước cập nhật. Nó giống lặp giá trị, nhưng dễ hơn.
We start off by saying, if you have 0 time steps left, my first approximation is every state gets 0 rewards. That's easy.
Ta bắt đầu bằng việc nói: nếu còn 0 bước thời gian, xấp xỉ đầu tiên của tôi là mọi trạng thái đều có phần thưởng 0. Dễ thôi.
But then I say, what will I get on average after K plus 1 steps of following pi from state S, and I'll do this for every state.
Rồi tôi hỏi: trung bình tôi sẽ nhận được bao nhiêu sau K cộng 1 bước làm theo pi từ trạng thái S, và tôi làm vậy cho mọi trạng thái.
I say well, I can figure out what happens next. The next thing is going to be I'm going to take action pi of S. And then, well, chance node kicks in.
Tôi có thể tính xem điều gì xảy ra tiếp theo. Việc tiếp theo là tôi sẽ thực hiện hành động pi của S. Và sau đó, nút ngẫu nhiên (chance node) bắt đầu hoạt động.
So S prime will be my next state. I don't know which one, so I have to average over all the states that can happen from state S and action pi of S.
Vậy S phẩy sẽ là trạng thái kế tiếp của tôi. Tôi không biết là trạng thái nào, nên phải lấy trung bình trên mọi trạng thái có thể xảy ra từ trạng thái S và hành động pi của S.
So I average over all the S primes. For each one of these, I will get a reward of S pi of S S prime, and then a discounted future.
Vậy tôi lấy trung bình trên tất cả các S phẩy. Với mỗi trạng thái đó, tôi nhận được phần thưởng R của S, pi của S, S phẩy, cộng với tương lai được chiết khấu.
Well what's the future look like? Well, I have K plus 1 steps. I just took a step. That means my future only has K steps.
Vậy tương lai trông thế nào? Tôi có K cộng 1 bước. Tôi vừa đi một bước. Nghĩa là tương lai của tôi chỉ còn K bước.
It's of state S prime, and it's a future from following pi, not a future of star which is optimal action for K steps. So here you go. Magic [INAUDIBLE] appear.
Đó là của trạng thái S phẩy, và là tương lai khi làm theo pi, chứ không phải tương lai của star, tức hành động tối ưu trong K bước. Đây rồi. Phép màu [KHÔNG NGHE RÕ] xuất hiện.
OK. So here, now, you have an update. If this arrow were an equation, and the K plus 1 and K were gone, this would be the Bellman equation.
Được. Vậy giờ bạn có một bước cập nhật. Nếu mũi tên này là dấu bằng, và K cộng 1 cùng K biến mất, đây sẽ là phương trình Bellman.
I take the equation, I turn it into an update. It's now a fixed point solution method that represents a dynamic program for solving this.
Tôi lấy phương trình, biến nó thành bước cập nhật. Giờ nó là phương pháp giải theo điểm bất động, đại diện cho một quy hoạch động để giải bài toán này.
You would look at this, and you say, that looks like value iteration, except instead of maxing, I just take the action I'm stuck with. That's right. It's got a name.
Bạn nhìn vào đây và nói, trông giống lặp giá trị, trừ việc thay vì lấy max, tôi chỉ lấy hành động mà tôi buộc phải làm. Đúng vậy. Nó có tên riêng.
It's called policy evaluation, but it is just value iteration where you don't do a max.
Gọi là đánh giá chính sách, nhưng thực chất là lặp giá trị mà không lấy max.
OK, so you run this, and you run this, and you run this, and you'll eventually get a vector where, for each state, you have a value that tells you your average score from that.
Bạn chạy đi chạy lại như vậy, và cuối cùng bạn sẽ có một vectơ mà với mỗi trạng thái, có một giá trị cho biết điểm trung bình bạn nhận được từ đó.
This only makes sense when the number of states is manageable, and the reason for that is your efficiency here is S squared per iteration.
Cách này chỉ hợp lý khi số trạng thái ở mức quản lý được, vì hiệu quả ở đây là S bình phương mỗi vòng lặp.
So I have to do this thing S times per iteration. I have to visit each state and compute its new approximation.
Tôi phải làm việc này S lần mỗi vòng lặp. Tôi phải duyệt từng trạng thái và tính xấp xỉ mới của nó.
And then for each state, I need to loop over all of the possible outcomes of the action I've been told to take. Right?
Rồi với mỗi trạng thái, tôi cần lặp qua tất cả kết quả có thể của hành động mà tôi được chỉ định phải làm. Đúng không?
So that's another factor of S. And you think, wait, but each state probably doesn't lead to every possible other state. That's right.
Vậy là thêm một thừa số S. Và bạn nghĩ, khoan, nhưng mỗi trạng thái chắc không dẫn tới mọi trạng thái khác. Đúng vậy.
Most MDPs are not fully connected, and so sometimes the branching factor here is much less than S. This is better than value iteration because value iteration also had a max in here, and that max gave rise to another factor of A, which is much more expensive.
Hầu hết các MDP không liên thông đầy đủ, nên đôi khi hệ số rẽ nhánh ở đây nhỏ hơn S nhiều. Cách này tốt hơn lặp giá trị vì lặp giá trị còn có một phép max ở đây, và phép max đó tạo thêm một thừa số A, tốn kém hơn nhiều.
OK. And again, as we talked about before, if you didn't — now that the maxes are gone, there's nothing nasty here. It's a system of linear equations and we know how to solve those.
Được. Và như đã nói trước đây, nếu bạn không — giờ phép max đã mất, không còn gì khó chịu ở đây. Đó là một hệ phương trình tuyến tính và ta biết cách giải chúng.
OK, so now we have — what was that? What just happened? Policy evaluation, input a policy, mapping from states to actions. Output a vector of values.
Được, vậy giờ ta có — vừa rồi là gì nhỉ? Điều gì vừa xảy ra? Đánh giá chính sách: đầu vào là một chính sách, ánh xạ từ trạng thái sang hành động. Đầu ra là một vectơ các giá trị.
Not optimal values, pi values. If pi happened to be optimal, they'd be optimal values. But in general, you've just evaluated some completely arbitrary policy pi. Now it's time for the opposite.
Không phải giá trị tối ưu, mà là giá trị pi. Nếu pi tình cờ tối ưu thì đó sẽ là giá trị tối ưu. Nhưng nói chung, bạn vừa đánh giá một chính sách pi hoàn toàn tùy ý. Giờ đến lúc làm ngược lại.
Policy evaluation takes a policy and produces values. Now we're going to take values and produce a policy.
Đánh giá chính sách nhận chính sách và tạo ra giá trị. Giờ ta sẽ nhận giá trị và tạo ra chính sách.
So this is like, you sit down, you're going to play the grand master at chess, and you have a secret.
Giống như bạn ngồi xuống để đấu với đại kiện tướng cờ vua, và bạn có một bí mật.
You, through some magical means, have access to the value of every configuration of the chessboard. Great. Does this help you? How do you turn values into knowing what action to take?
Bằng cách thần kỳ nào đó, bạn biết giá trị của mọi cấu hình của bàn cờ. Tuyệt. Điều này có giúp bạn không? Làm sao biến giá trị thành biết nên làm hành động nào?
Because you sit down, and you're like, checkmate. Right? That's not really how the game works, right? You need to actually look at the board and pick a move.
Vì bạn ngồi xuống và nói: chiếu hết. Đúng không? Trò chơi đâu có chơi như vậy, đúng không? Bạn phải nhìn bàn cờ và chọn một nước đi.
So how are we going to turn scores of states into moves? And so you think, well that's maybe not too hard.
Vậy làm sao biến điểm số của các trạng thái thành nước đi? Và bạn nghĩ, cái đó chắc không khó lắm.
I'll do a look ahead, I'll see what I can do, and then look at the values.
Tôi sẽ nhìn trước, xem mình làm được gì, rồi xem các giá trị.
That's basically the idea, but let's dig in a little more, and we'll see something that's actually very deep that will show up next week as well with reinforcement learning.
Về cơ bản là ý đó, nhưng ta hãy đào sâu thêm một chút, và ta sẽ thấy một điều thực sự sâu sắc, tuần sau cũng sẽ xuất hiện trong học tăng cường. học.
How are we going to compute actions from values? OK, let's imagine somebody gives you optimal values, which is a big deal, right? These optimal values may be intractable to compute.
Ta tính hành động từ các giá trị như thế nào? Được, giả sử ai đó đưa bạn các giá trị tối ưu, điều đó rất đáng giá, đúng không? Các giá trị tối ưu này có thể rất khó tính toán.
You have optimal values. How are you going to extract a policy for them? Or equivalently, what policy do these values imply? Well here's a little grid world.
Giả sử bạn đã có các giá trị tối ưu. Làm sao bạn rút ra chính sách từ chúng? Hay nói cách khác, các giá trị này ngụ ý chính sách nào? Đây là một grid world nhỏ.
And in this grid world, there are values on every state. And these are the optimal values that have been computed through value iteration. So let's think, how should we act?
Trong grid world này, mỗi trạng thái đều có một giá trị. Và đây là các giá trị tối ưu đã được tính bằng lặp giá trị. Vậy ta nên hành động thế nào?
Well, let's imagine you were in this interesting state here, the 0.89. OK? And shown on this slide is the actual optimal policy. So in this case, what are you supposed to do from here?
Hãy tưởng tượng bạn đang ở trạng thái thú vị này, ô 0.89. OK? Trên slide này là chính sách tối ưu thực sự. Vậy ở đây bạn phải làm gì?
You're supposed to go west and do the shimmy thing. So this is a setting of the grid world where the right thing is to do the shimmy thing.
Bạn phải đi về phía tây và làm động tác lách qua lách lại. Đây là một thiết lập của grid world mà việc đúng đắn là làm động tác lách đó.
But if you just looked at the values and you didn't see that arrow, what would you do? You'd look at it, you'd be like, 0.89. I guess that's OK.
Nhưng nếu bạn chỉ nhìn các giá trị và không thấy mũi tên, bạn sẽ làm gì? Bạn nhìn vào và nghĩ: 0.89. Chắc cũng ổn.
What should I do? Well I'd like that 0.98 please, except you don't have an action that gets you to that square.
Mình nên làm gì? Mình muốn ô 0.98 kia, nhưng bạn không có hành động nào đưa bạn thẳng tới ô đó.
You've got north, south, east, and west, and they do a variety of things with noise, right? And so, even though you might wish you were in a state, you don't get to do that.
Bạn chỉ có bắc, nam, đông, tây, và chúng cho ra nhiều kết quả khác nhau do nhiễu, đúng không? Vì vậy, dù bạn muốn ở một trạng thái nào đó, bạn không thể tự chọn như vậy.
You just need to decide what action is best. So you think, well, how good is north?
Bạn chỉ cần quyết định hành động nào tốt nhất. Bạn nghĩ: đi hướng bắc tốt đến đâu?
Like, is it going to get me to the 0.98, or is it going to drop me in the pit, or what?
Nó sẽ đưa mình tới ô 0.98, hay làm mình rơi xuống hố, hay sao?
And so in order to figure out how to act, you need to unroll all of your actions far enough in the expectimax tree that you can plug in these magical optimal values that you've been given.
Vì vậy, để biết cách hành động, bạn phải khai triển các hành động đủ sâu trong cây expectimax để có thể điền vào những giá trị tối ưu kỳ diệu mà bạn đã được cho.
So acting's actually sort of a pain in the butt, and it looks like this.
Vậy việc hành động thực ra khá phiền, và nó trông như thế này.
We need to say, all right, I need to know the optimal action for S. I have the optimal values, but unfortunately, I don't have the optimal actions yet.
Ta cần nói: tôi cần biết hành động tối ưu cho S. Tôi có giá trị tối ưu, nhưng tiếc là tôi chưa có hành động tối ưu.
So, let's start doing an expectimax until I find a place to put these optimal values that I've been so luckily given.
Vậy ta bắt đầu chạy expectimax cho tới khi tìm được chỗ để điền các giá trị tối ưu mà ta may mắn được cho.
So what I'll do is, I'm going to have to do some computation for every A, because I'm going to have to look at all my actions and see which one of these actions actually achieves this value that I know to be the value of this state.
Việc tôi sẽ làm là tính toán cho từng A, vì tôi phải xem xét tất cả các hành động và xem hành động nào thực sự đạt được giá trị mà tôi biết là giá trị của trạng thái này.
Right? And so what I'll do is, I'll look at all the actions A, and for each one, I'll say, well, OK, for that action, some S prime is going to happen.
Đúng không? Tôi sẽ xét tất cả các hành động A, và với mỗi hành động, tôi nói: OK, với hành động đó, sẽ xảy ra một S prime nào đó.
For that S prime, I'm going to get a reward.
Với S prime đó, tôi nhận được một phần thưởng.
The reward's going to correspond to the reward from state S to action A, landing in S prime, plus a future value, which luckily I know for every S prime.
Phần thưởng này ứng với phần thưởng khi từ trạng thái S thực hiện hành động A, rơi vào S prime, cộng với giá trị tương lai, mà may là tôi biết với mọi S prime.
Can't forget my discount. I can't forget the fact that S prime was not deterministic so I have to average over all the possible S primes. So I have to do this computation here.
Không được quên hệ số chiết khấu. Không được quên là S prime không mang tính tất định nên tôi phải lấy trung bình trên mọi S prime có thể. Vậy tôi phải làm phép tính này.
What is this computation here? That's a chance node. That's a Q value, right? I have to compute that again, but I'll plug in V star.
Phép tính này là gì? Đó là một nút ngẫu nhiên. Đó là một giá trị Q, đúng không? Tôi phải tính lại nó, nhưng sẽ thay V sao vào.
OK? Now what do I do with A? I'm going to compute each of these Q values, and I'm going to say, all right, north was the best. I'm going to do north.
OK? Giờ làm gì với A? Tôi sẽ tính từng giá trị Q này, và nói: được rồi, hướng bắc là tốt nhất. Tôi sẽ đi hướng bắc.
That's almost a max over A, but a max over A would be a number. It'd be like 7.6. I don't want to know that 7.6 is the answer.
Đó gần như là max trên A, nhưng max trên A chỉ là một con số. Chẳng hạn 7.6. Tôi không muốn biết đáp án là 7.6.
I want to know that north is the action which has the maximum value. The way we write that, which many of you have probably seen in some other context is arg max.
Tôi muốn biết hướng bắc là hành động có giá trị lớn nhất. Cách ta viết điều đó, mà nhiều bạn chắc đã thấy trong ngữ cảnh khác, là arg max.
So I say, I want the arg max over A, the A which gives you the maximum value of this unrolled chance node computation. So that's sort of a pain.
Tôi nói: tôi muốn arg max trên A, tức A cho giá trị lớn nhất của phép tính nút ngẫu nhiên đã khai triển này. Vậy là khá phiền.
Even though I have the optimal values, I still need to do a layer of expectimax to figure out what actions give rise to them. Choosing actions from values is annoying.
Dù đã có giá trị tối ưu, tôi vẫn cần thêm một lớp expectimax để biết hành động nào tạo ra chúng. Chọn hành động từ các giá trị thật khó chịu.
OK?
OK?
All right, there it is pretty. This thing where I give you values and you extract a policy from them, it is called policy extraction and it gets the policy that's implied by those values.
Được rồi, đây là nó, khá đẹp. Việc ta được cho các giá trị rồi rút ra chính sách từ chúng gọi là policy extraction, và nó cho ra chính sách được ngụ ý bởi các giá trị đó.
If those values are the optimal values, it will extract for you the optimal policy.
Nếu các giá trị đó là giá trị tối ưu, nó sẽ rút ra chính sách tối ưu.
If those values are some other values, it'll extract some other policy, but it'll extract a policy that's sort of driven by those values as a one step look ahead.
Nếu đó là các giá trị khác, nó sẽ rút ra một chính sách khác, nhưng đó là chính sách được dẫn dắt bởi các giá trị ấy qua phép nhìn trước một bước.
All right. On the other hand, these Q states, which are weird and that's why we don't have a name for them in common terminology, they're actually really nice for this purpose.
Được rồi. Ngược lại, các trạng thái Q này, vốn kỳ lạ và vì thế ta không có tên gọi cho chúng trong thuật ngữ thông dụng, thì thực ra rất tiện cho mục đích này.
Because if instead of giving you the values, somebody gave you the optimal Q values, it would be really, really, really easy to select actions.
Vì nếu thay vì cho bạn các giá trị, ai đó cho bạn các giá trị Q tối ưu, thì việc chọn hành động sẽ cực kỳ dễ.
Because if you were in this state here, where we were trying to figure out how do we get that 0.89, well it's really easy.
Vì nếu bạn đang ở trạng thái này đây, nơi ta đang cố tìm cách ra được 0.89, thì rất dễ.
That 0.89 lives on the Q state corresponding to that square and west. That square and north has a different value. It's 0.76.
Giá trị 0.89 nằm ở trạng thái Q ứng với ô đó và hướng tây. Ô đó và hướng bắc có giá trị khác. Là 0.76.
So if you have the Q values, you can just look around at all the actions, and you know their Q values have been computed for you already. So how should you react?
Nên nếu có các giá trị Q, bạn chỉ cần nhìn quanh tất cả các hành động, và giá trị Q của chúng đã được tính sẵn cho bạn. Vậy bạn nên phản ứng thế nào?
It's trivial. You take an arg max of the Q values surrounding you. The moral of the story is that actions are way easier to select from Q values than values.
Quá đơn giản. Bạn lấy arg max của các giá trị Q xung quanh. Bài học rút ra là chọn hành động từ các giá trị Q dễ hơn rất nhiều so với chọn từ các giá trị.
This observation is basically what unlocked modern reinforcement learning, and we'll talk about that next week. OK? OK, so, let's see.
Nhận xét này về cơ bản chính là điều đã mở đường cho học tăng cường hiện đại, và tuần sau chúng ta sẽ nói về nó. Được chứ? Được rồi, để xem.
We'll take a two minute break now, then we'll talk about an algorithm that combines these two ideas into something called policy iteration, and we'll get our first taste of reinforcement learning.
Giờ nghỉ hai phút, rồi chúng ta sẽ học một thuật toán kết hợp hai ý tưởng này, gọi là lặp chính sách, và chúng ta sẽ làm quen lần đầu với học tăng cường.
OK? So two minutes.
Được chứ? Vậy nghỉ hai phút.
There's a request to go back to the previous slide. I will do that.
Có bạn yêu cầu quay lại slide trước. Tôi sẽ làm vậy.
By the way, these slides are always up before lecture if you want them.
Nhân tiện, các slide luôn có sẵn trước buổi học nếu các bạn cần.
Actually, if you really click around, the lecture is up before lecture, because we have past lectures recorded.
Thật ra, nếu các bạn chịu khó bấm quanh, thì bài giảng cũng có sẵn trước buổi học, vì chúng tôi có ghi hình các bài giảng trước.
OK. All right. Policy iteration.
Được rồi. Nào. Lặp chính sách.
Once you have policy evaluation, which takes a policy and produces values, and you have policy extraction, which takes values and figures out what policy they imply, policy iteration's actually a really simple algorithm.
Khi đã có đánh giá chính sách, tức là nhận một chính sách và cho ra các giá trị, và có trích xuất chính sách, tức là nhận các giá trị và tìm ra chính sách mà chúng ngụ ý, thì lặp chính sách thực ra là một thuật toán rất đơn giản.
You just alternate those two. So why do we even do it? Well, there are some problems with value iteration.
Bạn chỉ việc luân phiên hai bước đó. Vậy tại sao ta lại làm vậy? Vì lặp giá trị có một số vấn đề.
Let's take a look. Let's take a look at value iteration happening here.
Hãy xem thử. Hãy xem lặp giá trị chạy ở đây.
All right, so this is going to be our favorite grid world, and every time I hit the button, I'm going to get a round of value iteration.
Đây là grid world quen thuộc của chúng ta, và mỗi lần tôi bấm nút, ta sẽ có thêm một vòng lặp giá trị.
And on this grid world, it's like super fast. OK? So what you'll remember is — you can think it in the back of your head, two things are happening.
Và với grid world này thì nó cực nhanh. Được chứ? Các bạn nhớ rằng — cứ ghi nhớ trong đầu, có hai việc đang diễn ra.
One is we are doing an iterative algorithm that will eventually converge to the true optimal values. Great.
Một là ta chạy một thuật toán lặp mà cuối cùng sẽ hội tụ về các giá trị tối ưu thật sự. Tuyệt.
It's also the case that if I run this for K iterations, say 7 iterations, I will have sort of the values that represent the MDP if it were truncated after 7 more rewards.
Hai là nếu chạy K lần lặp, chẳng hạn 7 lần, ta sẽ có các giá trị biểu diễn MDP như thể nó bị cắt cụt sau 7 phần thưởng.
So after 0 rewards, my approximation is 0. And then, I update. Some of them turned non-0. And I update and I update and I update and I update and I update.
Sau 0 phần thưởng, xấp xỉ của tôi bằng 0. Rồi tôi cập nhật. Một số giá trị khác 0. Tôi cập nhật, cập nhật, cập nhật, cập nhật và cập nhật nữa.
And then, for a while, things are changing. But you'll notice now that I'm up to iteration 19, and maybe some numbers will change, but the errors are pretty much done.
Một lúc thì các giá trị còn thay đổi. Nhưng giờ các bạn thấy tôi đã tới lần lặp 19, có thể vài con số còn đổi, nhưng sai số gần như hết rồi.
So if I do this for a long time, with enough degrees of precision, some numbers are still changing, some infinite series are still slowly accumulating, but there's just not that many futures from any given state that are that long.
Nếu chạy lâu với đủ độ chính xác, một số giá trị vẫn còn đổi, một số chuỗi vô hạn vẫn đang tích lũy chậm, nhưng từ một trạng thái bất kỳ thì không có nhiều tương lai dài đến thế.
So they add up to value, but they don't actually add up to a lot of change in the policy. This is a very common thing.
Chúng cộng vào giá trị, nhưng thật ra không làm chính sách thay đổi nhiều. Đây là chuyện rất thường gặp.
So a common thing with value iteration has basically got a major problem, which is S squared A is really slow.
Vậy lặp giá trị về cơ bản có một vấn đề lớn, đó là S bình phương nhân A rất chậm.
That means you have to visit every state, and sometimes that's just a deal breaker. We'll talk about approximate methods starting next week.
Nghĩa là bạn phải duyệt mọi trạng thái, và đôi khi điều đó là không thể chấp nhận. Từ tuần sau ta sẽ nói về các phương pháp xấp xỉ.
But even if you did that, you would then visit each state and each successor to that state, which we write as S squared, but usually it's not as bad as S squared.
Nhưng dù vậy, bạn vẫn phải duyệt từng trạng thái và từng trạng thái kế tiếp của nó, ta viết là S bình phương, nhưng thường không tệ đến mức S bình phương.
And then, for each one, you have to look at every possible action, so it's slow. However, the max of each state almost always doesn't change.
Rồi với mỗi cái, bạn phải xét mọi hành động có thể, nên nó chậm. Tuy nhiên, max của mỗi trạng thái hầu như không đổi.
So if you saw I went like 100 iterations into value iteration, and the numbers were changing.
Giả sử tôi chạy khoảng 100 lần lặp của lặp giá trị, và các con số vẫn thay đổi.
So those chance nodes that compute those sums were giving different results, but the max, the one that decides which child is the one that actually supports optimal behavior, they weren't changing.
Các nút ngẫu nhiên tính các tổng đó cho kết quả khác nhau, nhưng max, tức là cái quyết định nút con nào thực sự đem lại hành vi tối ưu, thì không đổi.
The policy was fixed. So for every action other than the one that we had already landed on, that computation was wasted.
Chính sách đã cố định. Vậy với mọi hành động khác ngoài hành động đã chọn, phép tính đó đều lãng phí.
Also something you saw, which is very related, is that the policy has often converged long before the values.
Một điều các bạn đã thấy, và rất liên quan, là chính sách thường hội tụ từ lâu trước các giá trị.
And once the policy converges, every branch of that expectimax tree that doesn't correspond to an optimal action is wasted computation, so you're doing a factor of A of wasted computation.
Và khi chính sách đã hội tụ, mọi nhánh của cây expectimax không ứng với hành động tối ưu đều là tính toán lãng phí, tức là bạn lãng phí một hệ số A khối lượng tính toán.
OK, so how can we fix that? These are in there so you can see it yourself. OK, let's do policy iteration as an alternative to this.
Vậy làm sao khắc phục? Những cái này có trong slide để các bạn tự xem. Được rồi, ta dùng lặp chính sách thay thế.
So an alternative approach for optimal values looks like this. Step one, you're going to do a policy evaluation.
Một cách tiếp cận khác để tìm giá trị tối ưu như sau. Bước một, bạn thực hiện đánh giá chính sách.
You will compute the utilities, the values, not for the optimal policy, but just for some policy.
Bạn tính các độ hữu dụng, các giá trị, không phải cho chính sách tối ưu, mà cho một chính sách nào đó.
On the plus side, this is going to be pretty fast, because policy evaluation is a factor of A faster than value iteration. The downside will be you have values for the wrong policy.
Ưu điểm là việc này khá nhanh, vì đánh giá chính sách nhanh hơn lặp giá trị một hệ số A. Nhược điểm là bạn có giá trị của chính sách sai.
Life's full of trade offs. Step two is you will improve your policy.
Cuộc đời đầy đánh đổi mà. Bước hai là cải thiện chính sách.
Now that you have values, not of the optimal policy but of random policy, you will do a one step look ahead improvement round where you actually consider all the actions again, and you extract a one step look ahead policy against those values.
Giờ bạn đã có giá trị, không phải của chính sách tối ưu mà của một chính sách ngẫu nhiên, bạn sẽ thực hiện một vòng cải thiện nhìn trước một bước, trong đó bạn xét lại tất cả các hành động, và trích xuất chính sách nhìn trước một bước dựa trên các giá trị đó.
OK, that is just as slow as value iteration, as an iteration of value iteration. It is an iteration of value iteration. You can repeat those until the policy converges.
Bước đó chậm y như lặp giá trị, như một lần lặp của lặp giá trị. Nó chính là một lần lặp của lặp giá trị. Bạn lặp lại cho đến khi chính sách hội tụ.
That's it. So it's policy iteration. It's still optimal, because step two alone repeated would be optimal. It would be value iteration, but it can be much faster.
Chỉ vậy thôi. Đó là lặp chính sách. Nó vẫn tối ưu, vì chỉ lặp riêng bước hai cũng sẽ cho kết quả tối ưu. Khi đó nó là lặp giá trị, nhưng cách này có thể nhanh hơn nhiều.
You evaluate the policy you've got for a while, and then every now and then, you go back in, and you consider the other actions, and then you start evaluating this policy for a while.
Bạn đánh giá chính sách hiện có một lúc, rồi thỉnh thoảng bạn quay lại, xem xét các hành động khác, rồi lại tiếp tục đánh giá chính sách mới này một lúc.
OK, so let's write that out in math.
Được rồi, giờ ta viết nó ra bằng toán.
But it really is just a synthesis of these others, so these are going to look exactly like the equations from before, that is a feature, not a bug.
Nhưng thực ra nó chỉ là tổng hợp của những cái trước, nên các công thức này sẽ trông y hệt các phương trình trước đó, đó là một đặc điểm chứ không phải lỗi.
So evaluation, we fix a policy pi, presumably a bad policy, and we find its values. And we iterate the following until it converges. OK, what is this equation?
Ở bước đánh giá, ta cố định một chính sách pi, có thể là chính sách tệ, và tìm các giá trị của nó. Ta lặp bước sau cho đến khi hội tụ. Phương trình này là gì?
This is the equation that says the values are an average of the results according to pi, where I plug in future pi values as my truncation function.
Nó nói rằng các giá trị là trung bình của các kết quả theo pi, trong đó tôi thay các giá trị pi ở tương lai làm hàm cắt cụt.
Great. I run this for a while, I don't have to max over actions. I'm just going to follow pi, and now I know the values of all the states for pi.
Tốt. Tôi chạy nó một lúc, không cần lấy max trên các hành động. Tôi chỉ đi theo pi, và bây giờ tôi biết giá trị của mọi trạng thái theo pi.
Now I do improvement, I do one step look ahead. This is the one that does all the work.
Tiếp theo là cải thiện, tôi nhìn trước một bước. Đây là bước làm hầu hết công việc.
I say, I want my new policy, I want policy I plus 1, pi I plus 1 of x. Well now, I take an arg max.
Tôi muốn chính sách mới, chính sách i cộng 1, pi i cộng 1 của x. Giờ tôi lấy arg max.
From S, I consider all the actions once again, just like in value iteration or expectimax.
Từ S, tôi lại xét tất cả các hành động, giống như trong lặp giá trị hay expectimax.
And for each action, well, I do that same thing where I average all the possible outcomes and plug in a truncation function.
Và với mỗi hành động, tôi làm cùng việc đó, lấy trung bình mọi kết quả có thể và thay vào một hàm cắt cụt.
The truncation function here came from the previous round of the policy I just evaluated. Now you think, am I going to get the same policy PI out? You're not, not in general.
Hàm cắt cụt ở đây lấy từ vòng trước, từ chính sách tôi vừa đánh giá. Bạn có thể nghĩ: liệu mình có nhận lại cùng chính sách pi không? Không, nói chung là không.
Because although you're plugging in values from V pi, you're plugging them in inside an admittedly small expectimax tree. And remember when we talked about minimax? We had these evaluation functions for a chess position.
Vì tuy bạn thay các giá trị từ V pi vào, nhưng bạn thay vào bên trong một cây expectimax tuy nhỏ nhưng vẫn là cây. Nhớ khi ta học minimax không? Ta có các hàm đánh giá cho một thế cờ vua.
We bury it deep into a minimax tree or an expectimax tree.
Ta chôn nó sâu trong cây minimax hoặc cây expectimax.
And even though that evaluation function isn't very good, if you bury it under enough layers of look ahead, it starts mattering less and less whether that approximation is correct.
Và dù hàm đánh giá đó không tốt lắm, nếu chôn nó dưới đủ nhiều tầng nhìn trước, thì việc xấp xỉ đó đúng hay không càng ít quan trọng.
And so this approximation V pi is being buried under a layer of look ahead and a gamma, so it's being discounted.
Và xấp xỉ V pi này bị chôn dưới một tầng nhìn trước và một gamma, tức là nó bị chiết khấu.
And so this process will improve your policy, and then you go back and forth. That's policy iteration.
Vì thế quá trình này sẽ cải thiện chính sách, rồi bạn cứ đi qua đi lại như vậy. Đó là lặp chính sách.
Any questions? Let me make the red go away. Any questions about this? OK.
Có câu hỏi nào không? Để tôi xóa nét đỏ này. Có câu hỏi nào về phần này không? Được rồi.
A very, very common state to be in right now is some mix of symbol shock — like so many V's, so many pi's so many Q's, and all possible configurations — and the feeling that you have just seen the same equation like 17 times with minor variations.
Trạng thái rất phổ biến lúc này là hơi choáng vì ký hiệu, nào là V, nào là pi, nào là Q, đủ mọi cấu hình, đủ mọi tổ hợp, và cảm giác là bạn vừa thấy cùng một phương trình khoảng 17 lần với những biến thể nhỏ.
You have just seen the same equation 17 times with minor variations.
Bạn vừa thấy cùng một phương trình 17 lần với những biến thể nhỏ.
It all comes down to just one layer of expectimax, either relating a max node to a chance node, a chance node to a max node, that's V's to Q's or Q's to V's, or maybe V's to V's.
Tất cả chỉ là một tầng expectimax, hoặc nối nút max với nút chance, nút chance với nút max, tức V sang Q hay Q sang V, hoặc có thể V sang V. Bạn thậm chí có thể viết phương trình Bellman từ Q sang Q nếu muốn.
You can write out a Bellman equation for Q to Q if you want. It's all the same thing with just kind of different starting points and ending points in that expectimax tree.
Tất cả đều như nhau, chỉ khác điểm bắt đầu và điểm kết thúc trong cây expectimax đó. Khác biệt còn lại là bạn lấy max trên các hành động, hay chỉ lấy hành động pi.
The other difference is whether you max over your actions, or you just take action pi. And that's the difference between computing pi values, the evaluation of policy pi, or optimal values.
Đó là khác biệt giữa việc tính các giá trị pi, tức đánh giá chính sách pi, và tính các giá trị tối ưu.
And so really, it is the same core of a one step look ahead expectimax, starting in different places, ending in different places, with different assumptions about optimality. So let's compare.
Vậy thực chất đó vẫn là cùng một lõi expectimax nhìn trước một bước, bắt đầu ở những chỗ khác nhau, kết thúc ở những chỗ khác nhau, với các giả định khác nhau về tính tối ưu. Giờ ta so sánh. Được rồi.
All right. We have value iteration, we have policy generation. They compute the exact same thing. They take an MDP.
Ta có lặp giá trị và lặp chính sách. Chúng tính đúng cùng một thứ. Chúng nhận một MDP. Rồi tính giá trị tối ưu cho mỗi trạng thái.
They then compute, for each state, the optimal value. That's what value iteration and policy iteration do.
Đó là việc của lặp giá trị và lặp chính sách.
In value iteration, each iteration you consider both all the values and also the policy, because that place where you maxed over the A's, if you remember which one was the biggest, that's the policy.
Trong lặp giá trị, mỗi vòng lặp bạn xét cả các giá trị lẫn chính sách, vì chỗ bạn lấy max trên các A, nếu nhớ hành động nào lớn nhất, đó chính là chính sách. Bạn không theo dõi chính sách đó, nhưng khi lấy max, bạn tính lại nó mỗi lần.
You don't track that policy, but when you take that max, you're recomputing it every time.
In policy iteration, in contrast, you usually keep your policy fixed and do a bunch of tracking of value changes under that policy, and every now and then, let the policy consider other actions.
Ngược lại, trong lặp chính sách, bạn thường giữ chính sách cố định và cập nhật giá trị nhiều lần theo chính sách đó, và thỉnh thoảng mới cho chính sách xét các hành động khác. Nếu chính sách đổi liên tục thì bạn phí thời gian.
If the policy's changing all the time, you're wasting your time. If the policy is changing rarely, you save a lot of time. And that's the trade off here.
Nếu chính sách ít khi đổi thì bạn tiết kiệm được nhiều thời gian. Đó là sự đánh đổi ở đây. Thường thì cách này nhanh hơn.
Usually this is faster.
Được rồi.
OK.
Here's the summary, and then we're going to branch into a little reinforcement learning. Actually, before I summarize, any questions?
Đây là phần tóm tắt, rồi sau đó ta sẽ chuyển sang một chút học tăng cường. Thật ra trước khi tóm tắt, có câu hỏi nào không? Mời bạn?
SINH VIÊN
Yep?
[KHÔNG NGHE RÕ].
STUDENT
[INAUDIBLE].
Về cập nhật chính sách, ta phải làm bao nhiêu vòng?
PROFESSOR
So for the policy update, how many rounds of that do we have to do? This is actually — it's a great question.
Đây thật ra là một câu hỏi rất hay. Khi cải thiện các giá trị cho một chính sách cố định, bạn có thể làm nhiều lần.
When you improve your values for a fixed policy, you might do this a lot. You might do this, you know, until convergence. You might do this 100x.
Bạn có thể làm đến khi hội tụ. Có thể làm 100 lần. Còn khi nhìn trước một bước, bạn chỉ làm một lần. Bạn nhìn trước một bước.
SINH VIÊN
When you do a one step look ahead, you do this once. You do a one step look ahead.
[KHÔNG NGHE RÕ].
STUDENT
[INAUDIBLE].
Rồi bạn quay lại và làm 100 lần SINH VIÊN: [KHÔNG NGHE RÕ].
PROFESSOR
And then you go back and you do 100 times with this new policy. So there's a cycle here, which is, take your policy, evaluate it. That means you run these faster updates until convergence.
Rồi bạn quay lại và làm 100 lần với chính sách mới này. Vậy có một chu trình ở đây: lấy chính sách của bạn, đánh giá nó. Nghĩa là bạn chạy các bước cập nhật nhanh hơn này cho đến khi hội tụ.
STUDENT
[INAUDIBLE].
[KHÔNG NGHE RÕ].
PROFESSOR
Yep, and then once you get a new policy, you go up and you evaluate it. And so you're spending most of your iterations evaluating policies, and every 100th iteration, you actually update the policy.
Đúng, và khi có chính sách mới, bạn quay lên và đánh giá nó. Như vậy phần lớn các vòng lặp bạn dành để đánh giá chính sách, và cứ mỗi 100 vòng, bạn mới thực sự cập nhật chính sách một lần.
STUDENT
[INAUDIBLE].
[KHÔNG NGHE RÕ].
PROFESSOR
So the question is, does this take a lot of time? It can. I can, but in general, this is a factor of A faster.
Câu hỏi là, cách này có tốn nhiều thời gian không? Có thể. Có thể, nhưng nhìn chung cách này nhanh hơn một hệ số A.
And you don't actually — one difference in reality, this is actually a great point.
Và thực ra bạn không — có một khác biệt trong thực tế, và đây là một điểm rất hay.
One difference is that when you do this in practice, you don't start the evaluation over at 0, you start it at your old values.
Khác biệt là khi làm trong thực tế, bạn không bắt đầu lại việc đánh giá từ 0, mà bắt đầu từ các giá trị cũ.
So if the policy hasn't changed much, you're pretty close to begin with. There are ways to speed this up. In general, it is faster.
Nếu chính sách không thay đổi nhiều, thì ngay từ đầu bạn đã khá gần đáp án rồi. Có nhiều cách để tăng tốc việc này. Nhìn chung, nó nhanh hơn.
You can think of it just as value iteration where sometimes you, instead of looping over the actions, you just recycle the last round's preferred action, and then it's easier to see why it would be faster.
Bạn có thể xem nó như lặp giá trị, trong đó đôi khi thay vì duyệt qua tất cả các hành động, bạn chỉ tái sử dụng hành động được ưu tiên ở vòng trước, và như vậy dễ thấy vì sao nó nhanh hơn.
It's a good question. Any others?
Câu hỏi hay. Còn câu nào khác không?
Yeah.
Vâng.
STUDENT
[INAUDIBLE] PROFESSOR: Yeah, it's a good question. In general, whether it's value iteration or policy iteration, when you iterate these things, when do you stop?
[KHÔNG NGHE RÕ] GIÁO SƯ: Vâng, câu hỏi hay. Nhìn chung, dù là lặp giá trị hay lặp chính sách, khi lặp những thứ này thì khi nào dừng?
You have to have some notion of convergence, and that's generally based on the size of the changes, and there's different criteria. You can also do fixed iterations.
Bạn cần một khái niệm nào đó về hội tụ, thường dựa trên độ lớn của các thay đổi, và có nhiều tiêu chí khác nhau. Bạn cũng có thể chạy số vòng lặp cố định.
But when you've got this view of an embedded optimization, the question is, how much polishing do you want to do of V pi if you're just going to change pi?
Nhưng khi nhìn nó như một bài tối ưu lồng nhau, câu hỏi là bạn muốn trau chuốt V pi đến mức nào nếu dù sao bạn cũng sắp thay đổi pi?
And so, in general with these methods, you don't want to over optimize intermediate quantities that are just going to be discarded and turned into other quantities.
Vì vậy, với các phương pháp này, bạn không nên tối ưu quá mức các đại lượng trung gian vốn sẽ bị bỏ đi và chuyển thành các đại lượng khác.
And so, in general, it is not the case that you start the evaluation step at 0, and it's also not the case that you have a strict convergence.
Nên nhìn chung, không nhất thiết bạn phải bắt đầu bước đánh giá từ 0, và cũng không nhất thiết phải hội tụ chặt chẽ.
You might just run it five times for every one improvement step. These are all questions for which the answer is, there are trade offs, and there's no hard and fast answer.
Bạn có thể chỉ chạy năm lần cho mỗi một bước cải thiện. Với những câu hỏi này, câu trả lời đều là có sự đánh đổi, và không có đáp án cứng nhắc.
Basically, as long as you — you don't even have to visit every state every time.
Về cơ bản, miễn là bạn — bạn thậm chí không cần duyệt mọi trạng thái ở mỗi lần.
As long as you visit every state and every action from that state infinitely often, you'll eventually converge to the right thing.
Miễn là bạn duyệt mọi trạng thái và mọi hành động từ trạng thái đó vô số lần, thì cuối cùng bạn sẽ hội tụ về kết quả đúng.
These methods are very robust to being sort of juggled around the orders in which you do a limited or complete, simplified or full Bellman updates. OK.
Các phương pháp này rất bền vững trước việc xáo trộn thứ tự thực hiện các bước cập nhật Bellman, dù hạn chế hay đầy đủ, đơn giản hóa hay nguyên bản. các lần cập nhật. OK.
All right. Summary, and then we're going to talk about reinforcement learning a little bit. What if you have an MDP and you would like to compute optimal values?
Được rồi. Tóm tắt, rồi chúng ta sẽ nói một chút về học tăng cường. Nếu bạn có một MDP và muốn tính các giá trị tối ưu thì sao?
Use value iteration or policy iteration. OK? If you want to compute values for a particular policy, you use policy evaluation. It's faster.
Dùng lặp giá trị hoặc lặp chính sách. OK? Nếu muốn tính giá trị cho một chính sách cụ thể, bạn dùng đánh giá chính sách. Cách này nhanh hơn.
If you have a policy that you wish to turn — if you have values and you wish to turn them into a policy, use policy extraction, which is just a one step look ahead where you plug those values in.
Nếu bạn có giá trị và muốn biến chúng thành một chính sách, hãy dùng trích xuất chính sách, tức chỉ là nhìn trước một bước và thay các giá trị đó vào.
If those values are really good, that one step ahead policy might be really good. If those values are 0, you just did a level one expectimax.
Nếu các giá trị đó thật sự tốt, chính sách nhìn trước một bước có thể rất tốt. Nếu các giá trị đều bằng 0, bạn chỉ vừa làm expectimax một tầng.
Don't expect much out of your policy, but maybe it's already better than moving randomly. OK. You look at these and you say, these are all the same.
Đừng kỳ vọng nhiều ở chính sách đó, nhưng có thể nó vẫn tốt hơn việc di chuyển ngẫu nhiên. OK. Nhìn những cái này, bạn sẽ thấy chúng đều giống nhau.
Like I said before, these are basically all variations of the Bellman updates, and they're all just one step ahead fragments.
Như tôi đã nói, về cơ bản chúng đều là biến thể của các cập nhật Bellman, và đều chỉ là các mảnh nhìn trước một bước.
That point where you realize they're actually all the same and there's sort of a core piece that you then pin down in various ways, that is both a point of high confusion conceptually and also a point where, once you get through that, everything starts to be a little easier to remember because the arbitrariness starts to be determined by the purpose.
Khoảnh khắc bạn nhận ra chúng thật ra đều giống nhau và có một lõi chung mà bạn cố định theo nhiều cách khác nhau, vừa là điểm rất dễ gây nhầm lẫn về mặt khái niệm, vừa là điểm mà một khi vượt qua, mọi thứ bắt đầu dễ nhớ hơn một chút vì sự tùy tiện bắt đầu được quyết định bởi mục đích.
All right, reinforcement learning. Let's play slots. OK, this is CS188 slots. Imagine you are a robot.
Được rồi, học tăng cường. Chơi máy đánh bạc nào. OK, đây là máy đánh bạc CS188. Hãy tưởng tượng bạn là một robot.
We will pick actions for this robot. And there are two slot machines, blue and red. The blue slot machine, every time you pull the lever, gives you a dollar.
Chúng ta sẽ chọn hành động cho robot này. Có hai máy đánh bạc, xanh và đỏ. Máy xanh, mỗi lần bạn kéo cần, cho bạn một đô la.
It's a pretty good slot machine. Real slot machines aren't like this. I would love this slot machine. OK.
Máy này khá tốt. Máy đánh bạc thật không như vậy. Tôi rất thích máy này. OK.
The other slot machine, when you pull the lever, it either gives you $0 or $2. OK? Now, what should we do? Well, of course, we're going to formulate it as an MDP.
Máy còn lại, khi bạn kéo cần, hoặc cho bạn $0 hoặc $2. OK? Vậy chúng ta nên làm gì? Tất nhiên, ta sẽ mô hình hóa nó thành một MDP.
OK, except it's a really, really simple MDP. It's even simpler than what's on the slide, so if anything, the thing on the slide over-complicates it.
OK, nhưng đây là một MDP cực kỳ đơn giản. Thậm chí còn đơn giản hơn cái trên slide, nên nếu có gì thì cái trên slide làm nó phức tạp thêm.
You have an MDP, in which your actions are you can pull the blue lever and get your dollar, or you can pull the red lever and have a little bit of excitement and get either $0 or $2.
Bạn có một MDP, trong đó các hành động là kéo cần xanh và nhận một đô la, hoặc kéo cần đỏ để có chút hồi hộp và nhận $0 hoặc $2.
In this particular formulation, I've split up two states. There's really only one state. There's really just — I'm in the state, what do I do next?
Trong cách mô hình này, tôi đã tách thành hai trạng thái. Thật ra chỉ có một trạng thái. Thực ra chỉ có — Tôi đang ở trạng thái này, tiếp theo làm gì?
But if you actually look at the MDP formalism, the reward I get depends on whether I win or lose, and so S prime needs to be different if I win or lose.
Nhưng nếu nhìn vào hình thức luận MDP, phần thưởng tôi nhận được phụ thuộc vào việc tôi thắng hay thua, nên S prime phải khác nhau giữa thắng và thua.
So here's, if anything, an over-complication of this MDP. And if you look at it, you see that from either state, the blue action takes you — you're a winner.
Vậy đây là một cách mô hình hóa MDP phức tạp hóa quá mức. Và nếu nhìn kỹ, từ trạng thái nào cũng vậy, hành động xanh đưa bạn đến chỗ thắng.
You are an instant winner for a dollar. And the red action, from either state, 75% chance of giving you $2, 25% chance of giving you $0. All right, let's avoid infinite rewards.
Bạn thắng ngay lập tức một đô la. Còn hành động đỏ, từ trạng thái nào cũng có 75% cơ hội nhận $2 và 25% cơ hội nhận $0.
So there will be no discount, because they'll just make this messy. There's 100 times steps, so the answers aren't all infinity, and we know the MDP.
Được rồi, để tránh phần thưởng vô hạn, ta sẽ không dùng hệ số chiết khấu, vì nó chỉ làm mọi thứ rối thêm. Có 100 bước thời gian, nên đáp án không phải vô cực, và ta biết MDP này.
We know both states are going to have the same value, so we can sort of collapse that notion. Let's look at this MDP and think really hard and decide what is the optimum policy.
Ta biết hai trạng thái có cùng giá trị, nên có thể gộp chúng lại. Hãy nhìn MDP này, suy nghĩ thật kỹ và quyết định chính sách tối ưu là gì.
OK, well what's going to happen if I choose the policy play blue? That's a policy. Let's evaluate it.
Được, chuyện gì xảy ra nếu tôi chọn chính sách chơi xanh? Đó là một chính sách. Hãy đánh giá nó.
The states are the same, so what is the value of the policy play blue, presuming that's going to be 100 times steps?
Các trạng thái giống nhau, vậy giá trị của chính sách chơi xanh là bao nhiêu, giả sử có 100 bước?
How much money will I make if I always play blue 100 times? STUDENT: $100. PROFESSOR: $100. OK, how about play red?
Tôi kiếm được bao nhiêu tiền nếu luôn chơi xanh 100 lần? SINH VIÊN: $100. GIÁO SƯ: $100. Còn chơi đỏ thì sao?
That's a policy. Let's evaluate that policy. What am I going to get? Well you look at it and you're like, I don't know what you're going to get because there's a slot machine.
Đó là một chính sách. Hãy đánh giá chính sách đó. Tôi sẽ nhận được bao nhiêu? Bạn nhìn và nghĩ, tôi không biết sẽ được bao nhiêu vì đây là máy đánh bạc.
Right? And remember the value is the expected discounted reward, so it's the expected reward. So I'm going to go 100 steps, and on an expectation, an average, what am I going to get?
Đúng không? Và nhớ rằng giá trị là phần thưởng chiết khấu kỳ vọng, tức là phần thưởng kỳ vọng. Tôi sẽ đi 100 bước, và theo kỳ vọng, tức trung bình, tôi sẽ nhận được bao nhiêu?
I don't know what I'll actually get, but on average, what am I going to get? STUDENT: $150. PROFESSOR: $150. OK.
Tôi không biết thực tế được bao nhiêu, nhưng trung bình tôi sẽ nhận được bao nhiêu? SINH VIÊN: $150. GIÁO SƯ: $150. Được.
Here we are. You just did offline planning. We did not play slots. You looked at the MDP.
Vậy đó. Các bạn vừa lập kế hoạch ngoại tuyến. Ta chưa hề chơi máy. Các bạn nhìn vào MDP.
You thought and you thought and you thought deep and profound thoughts, and you came to the realization that play red has value $150, play blue has value $100.
Các bạn nghĩ đi nghĩ lại, suy tư sâu sắc, và nhận ra chơi đỏ có giá trị $150, chơi xanh có giá trị $100.
What is the optimal policy for this MDP? Play red. All right, great. OK, you knew the quantities of the MDP.
Chính sách tối ưu của MDP này là gì? Chơi đỏ. Tuyệt. Các bạn biết các đại lượng của MDP.
You determined values and policies, all of that just thinking offline using math, and the input values from the MDP. Great. Let's play.
Các bạn xác định giá trị và chính sách, tất cả chỉ bằng suy nghĩ ngoại tuyến, dùng toán, và các giá trị đầu vào từ MDP. Tuyệt. Giờ ta chơi nhé.
OK. I hope you solved the MDP correctly, because it's real fake money now. OK? So we're going to actually play.
Được. Hy vọng các bạn giải MDP đúng, vì giờ là tiền giả thật đấy. Nhé? Giờ ta chơi thật.
What should I play? I want to be optimal.
Tôi nên chơi gì? Tôi muốn chơi tối ưu.
STUDENT
Red.
Đỏ.
PROFESSOR
Red. OK, cool. $2. OK, but I thought I was just going to get $1.50. OK, that's an expectation, the actual thing that happens is going to be a sample.
Đỏ. Tốt. $2. Nhưng tôi tưởng mình chỉ được $1,50. Đó là kỳ vọng, còn điều thực sự xảy ra là một mẫu.
OK? $2, now what? What [INAUDIBLE] should I play? Red, $2. Now what?
Nhé? $2, giờ sao? Tôi nên chơi gì [KHÔNG NGHE RÕ]? Đỏ, $2. Giờ sao?
Red. Now? Red. Red, red, red, red, red, red.
Đỏ. Giờ thì sao? Đỏ. Đỏ, đỏ, đỏ, đỏ, đỏ, đỏ.
I can't stop. OK, we just played 10 times. How'd we do? We got $12.
Tôi không dừng được. Ta vừa chơi 10 lần. Kết quả thế nào? Ta được $12.
On average, what will we get? On average, we would have gotten $15, so even like a little unlucky, but not catastrophically unlucky.
Trung bình sẽ được bao nhiêu? Trung bình lẽ ra được $15, nên hơi xui một chút, nhưng không xui thảm hại.
What we did offline when we thought about the averages and compared them and did math, that was solving an MDP. This is actually playing the real fake game.
Việc ta làm ngoại tuyến khi nghĩ về các giá trị trung bình, so sánh và tính toán, chính là giải một MDP. Còn đây là chơi trò chơi giả thật.
OK, we actually got samples back. They may or may not adhere to the average. The average is just an average. OK, and that was actually playing the game.
Ta thực sự nhận về các mẫu. Chúng có thể khớp hoặc không khớp với trung bình. Trung bình chỉ là trung bình. Và đó là chơi game thật sự.
Important distinction even though, yes, they were both just on PowerPoint. OK? Are you ready? Rules are going to change.
Đây là một sự phân biệt quan trọng, dù đúng là cả hai đều chỉ trên PowerPoint. Nhé? Sẵn sàng chưa? Luật sẽ thay đổi.
You walk in to the new and improved CS188 casino and the rules have changed. There is still the $1 slot machine.
Bạn bước vào sòng bạc CS188 mới và cải tiến và luật đã đổi. Vẫn có máy đánh bạc $1.
There is now the $0 or $2 slot machine just like before, except you don't know its payoff probability. You don't know how likely you are to win.
Giờ có máy $0 hoặc $2 như trước, nhưng bạn không biết xác suất trả thưởng. Bạn không biết khả năng thắng là bao nhiêu.
So it's the same MDP in structure, but I no longer know the probability that I'll get the $2. Maybe I'll always get the $2. Maybe I'll never get the $2.
Vậy cấu trúc MDP vẫn như cũ, nhưng tôi không còn biết xác suất nhận được $2 nữa. Có thể tôi luôn nhận được $2. Có thể tôi không bao giờ nhận được $2.
I don't know. OK, so I just took something away from you. You don't know the MDP anymore.
Tôi không biết. Tôi vừa lấy đi của các bạn một thứ. Các bạn không còn biết MDP nữa.
You know that there is an MDP, that is a useful formalism and a useful way to think about the world, but you don't know what the MDP is.
Bạn biết rằng có một MDP, đó là một hình thức luận hữu ích và một cách hữu ích về thế giới, nhưng các em không biết MDP đó là gì.
You don't know the parameters. OK. Everything is different. You are now in a totally different world.
Các em không biết các tham số. OK. Mọi thứ đều khác đi. Giờ các em ở trong một thế giới hoàn toàn khác.
Time to play, right? You cannot think deep thoughts now and figure out the value of the red policy. Right? You don't have the necessary information.
Đến lúc chơi rồi, đúng không? Giờ các em không thể ngồi suy nghĩ thật sâu để tính ra giá trị của chính sách màu đỏ. Đúng không? Các em không có đủ thông tin cần thiết.
How are you going to get the necessary information to figure out how to act optimally? We have to actually act. So let's play. Which lever should I pull?
Vậy làm sao có được thông tin cần thiết để biết cách hành động tối ưu? Ta phải thực sự hành động. Nào, chơi thôi. Tôi nên kéo cần nào?
STUDENT
Red.
Đỏ.
PROFESSOR
Red? Who wants red? Who wants blue? All right, we'll go with red.
Đỏ à? Ai muốn đỏ? Ai muốn xanh? Được, ta chọn đỏ.
OK, red. I got a $0. Must be a dud, right? It's just a sample.
OK, đỏ. Tôi nhận được $0. Chắc là máy hỏng, đúng không? Đây chỉ là một mẫu thôi.
OK, who wants red, who wants blue? Who wants red? Who wants blue? OK, $0.
OK, ai muốn đỏ, ai muốn xanh? Ai muốn đỏ? Ai muốn xanh? OK, $0.
Who wants red? Who wants blue?
Ai muốn đỏ? Ai muốn xanh?
Nobody is wanting blue, but there are fewer and fewer red hands. OK, red. Red. OK.
Chưa ai muốn xanh, nhưng số tay giơ chọn đỏ ngày càng ít. OK, đỏ. Đỏ. OK.
We played four times. Who wants red? All right, yeah. They're starting to come back.
Ta đã chơi bốn lần. Ai muốn đỏ? Được, vâng. Mọi người bắt đầu quay lại.
Red's seeming a little better because we finally got some money out of it. OK, we'll play red. Who wants red? Who wants blue?
Đỏ có vẻ khá hơn một chút vì cuối cùng ta cũng nhận được ít tiền. OK, ta chơi đỏ. Ai muốn đỏ? Ai muốn xanh?
OK, I'm going to play red a bunch. Red, red, red, red, red. OK.
OK, tôi sẽ chơi đỏ nhiều lần. Đỏ, đỏ, đỏ, đỏ, đỏ. OK.
All right. Now what should happen? We're going play again. Let's play 11.
Được rồi. Giờ chuyện gì sẽ xảy ra? Ta sẽ chơi tiếp. Chơi lần thứ 11.
Who wants red? OK, we've got some die hard red fans. Who wants blue? Everybody wants blue, so I'll play blue.
Ai muốn đỏ? OK, có vài fan cứng của đỏ. Ai muốn xanh? Mọi người muốn xanh, vậy tôi chơi xanh.
What's going to happen when I play blue? I'm going to get a dollar. What are you going to want after that? Like, more blue because nothing's really changed.
Chuyện gì sẽ xảy ra khi tôi chơi xanh? Tôi sẽ nhận được một đô la. Sau đó các em sẽ muốn gì? Chắc là xanh nữa, vì chẳng có gì thay đổi.
So one interesting thing is, once you switch to blue, there's really not a great reason to switch back on the surface here. OK, but what just happened? Let's take a step back.
Một điều thú vị là, một khi đã chuyển sang xanh, nhìn bề ngoài thì không có lý do gì mấy để chuyển lại cả. OK, nhưng vừa rồi chuyện gì đã xảy ra? Ta lùi lại một bước.
What just happened? You did not take an MDP and solve it, because I didn't give you the MDP. What did you do?
Chuyện gì vừa xảy ra? Các em đã không lấy một MDP rồi giải nó, vì tôi đâu có cho các em MDP. Vậy các em đã làm gì?
You interacted with the real fake world, and then you took those observations, and you used them to figure out a little bit more information about the MDP.
Các em tương tác với thế giới giả mà thật, rồi lấy các quan sát đó, và dùng chúng để biết thêm một chút thông tin về MDP.
And as you gathered information about the MDP, you started to have different opinions of what you should do. And eventually, you decided that red appears to be sort of a loser.
Và khi thu thập thêm thông tin về MDP, các em bắt đầu có ý kiến khác nhau về việc nên làm gì. Và cuối cùng, các em quyết định rằng đỏ có vẻ là một cái máy thua.
Although, in fact, it could be amazing and you were just unlucky. But from your experience, you know? All right. That was not planning.
Dù thực ra nó có thể rất tuyệt và các em chỉ xui thôi. Nhưng theo kinh nghiệm của các em thì vậy, đúng không? Được rồi. Đó không phải là lập kế hoạch.
That first time when you calculated averages and then you just went for it and you pulled the red lever forever, that was offline planning. This was learning. You did reinforcement learning.
Lần đầu, khi các em tính trung bình rồi cứ thế kéo cần đỏ mãi mãi, đó là lập kế hoạch ngoại tuyến. Còn đây là học. Các em đã làm học tăng cường.
There was an MDP, but you couldn't solve it with computation because you didn't know the parameters.
Có một MDP, nhưng các em không thể giải nó bằng tính toán vì không biết các tham số.
You needed to actually act to figure out the parameters by seeing samples of the behavior of the system.
Các em cần thực sự hành động để tìm ra các tham số, bằng cách xem các mẫu hành vi của hệ thống.
You also saw basically every idea that is kind of core to reinforcement learning right there, even with that simple case. So one important idea in reinforcement learning is exploration.
Các em cũng đã thấy gần như mọi ý tưởng cốt lõi của học tăng cường ngay tại đó, dù chỉ là trường hợp đơn giản. Một ý tưởng quan trọng trong học tăng cường là khám phá.
You have to try unknown things in order to get information. So red was, in fact, not a very good slot machine. But you didn't know that, and you had to try it.
Phải thử những điều chưa biết để có thông tin. Thực ra máy đỏ không phải máy đánh bạc tốt. Nhưng các em không biết, và phải thử nó.
And everything that's unknown, the only way to figure out what those parameters are is to actually try it. That's called exploration.
Với mọi thứ chưa biết, cách duy nhất để biết các tham số đó là gì là thực sự thử. Đó gọi là khám phá.
When you take an action and your payment is not like slot machine dollars coming in, what do you get paid in when you pull that red lever? You got paid in knowledge.
Khi các em hành động mà khoản thu không phải là tiền đô la từ máy đánh bạc, thì khi kéo cần đỏ, các em được trả bằng gì? Các em được trả bằng kiến thức.
You got paid in experience. And that experience helps you make better decisions in the future. So exploration is you have to sometimes do things for the experience rather than for the yield.
Được trả bằng kinh nghiệm. Và kinh nghiệm đó giúp các em quyết định tốt hơn trong tương lai. Vậy khám phá là đôi khi phải làm việc gì đó vì kinh nghiệm chứ không vì lợi nhuận.
Exploitation, on the other hand, is eventually, you have learned all you care to know about that red slot machine, and you're done. You're like, OK, enough exploration, it's time to pull the blue lever.
Còn khai thác thì, cuối cùng, các em đã biết đủ những gì cần biết về máy đánh bạc đỏ đó, và xong. Các em nghĩ: OK, khám phá đủ rồi, đến lúc kéo cần xanh.
It's time to exploit the knowledge I have in order to get return, right? You also discovered the concept of regret. OK, this does not mean exactly what it means informally.
Đến lúc khai thác kiến thức mình có để thu lợi, đúng không? Các em cũng đã khám phá ra khái niệm regret (sự hối tiếc). OK, nó không hoàn toàn có nghĩa như cách nói thông thường.
Regret is the idea that even if you learn intelligently and you do an optimal job given your uncertainty of trying things out, you will not do as well as if you had actually known the MDP to begin with.
Regret (sự hối tiếc) nghĩa là dù bạn học một cách thông minh và làm tối ưu nhất có thể với sự bất định khi thử các lựa chọn, bạn vẫn sẽ không làm tốt bằng việc biết trước MDP ngay từ đầu.
Regret is the difference between what you experience and the best that you could possibly have gotten sort of in retrospect. You also ran into the idea of sampling, because there's chance.
Regret là chênh lệch giữa những gì bạn nhận được và kết quả tốt nhất mà lẽ ra bạn có thể đạt được, nhìn lại sau này. Bạn cũng đã gặp ý tưởng về lấy mẫu, vì có yếu tố ngẫu nhiên.
You can't just try the red thing once and be like, oh, it's a $2, it's a 100% payoff. You have to do things over and over again, and that has consequences.
Bạn không thể thử cái màu đỏ một lần rồi nói: ồ, được 2 đô, vậy là 100% có thưởng. Bạn phải làm đi làm lại nhiều lần, và điều đó có hệ quả.
When you do reinforcement learning, you've got to keep trying things over and over and over again. And the more complicated they are, maybe the more times you have to try them.
Khi làm học tăng cường, bạn phải liên tục thử đi thử lại nhiều lần. Và càng phức tạp thì có lẽ càng phải thử nhiều lần hơn. Và càng phức tạp thì có lẽ càng phải thử nhiều lần hơn.
And trying things in the real world — this isn't simulation. It's like you actually like send that helicopter up in the air, it crashes, and you buy a new one.
Mà thử trong thế giới thực thì không phải mô phỏng. Tức là bạn thật sự cho chiếc trực thăng đó bay lên không trung, nó rơi, và bạn phải mua chiếc mới.
You might have to do that a lot. Right? Experience can cost. OK, and sampling means you have to try things repeatedly.
Có thể bạn phải làm vậy rất nhiều lần. Đúng không? Kinh nghiệm có thể tốn kém. Và lấy mẫu nghĩa là bạn phải thử lặp đi lặp lại.
Also difficulty. This is like the simplest MDP you could possibly imagine, and solving it in the case of the known MDP was trivial. You didn't need value iteration.
Còn có một khó khăn nữa. Đây là MDP đơn giản nhất mà bạn có thể tưởng tượng, và giải nó khi đã biết MDP thì quá dễ. Bạn không cần lặp giá trị.
You didn't need anything from the past few lectures. You just needed a description of the problem and your basic mathematical intuitions, and you were done.
Bạn không cần gì từ mấy bài giảng trước. Bạn chỉ cần mô tả bài toán và trực giác toán học cơ bản là xong.
As soon as I take away that probability, suddenly it's hard. How many times should I pull that lever? Should I switch back? Should I ever switch back?
Nhưng hễ tôi bỏ đi xác suất đó, đột nhiên nó trở nên khó. Tôi nên kéo cần đó bao nhiêu lần? Có nên chuyển lại không? Có bao giờ nên chuyển lại không?
Suddenly, these questions that were very easy are very hard, simply because learning is much harder. It's much harder to learn an MDP than it is to solve a known one.
Đột nhiên những câu hỏi vốn rất dễ lại rất khó, đơn giản vì việc học khó hơn nhiều. Học một MDP khó hơn nhiều so với giải một MDP đã biết.
Any questions on any of that? OK, next time, reinforcement learning.
Có câu hỏi nào về phần này không? Được rồi, lần sau là học tăng cường.
We will think about how you should act when there are MDPs, but you don't know any of the parameters, and the only way to learn what's going on is by interacting with the world.
Chúng ta sẽ xét cách hành động khi có các MDP, nhưng bạn không biết tham số nào cả, và cách duy nhất để biết chuyện gì đang xảy ra là tương tác với thế giới.
So we will start that next lecture.
Chúng ta sẽ bắt đầu ở bài giảng sau.
Đă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.