1
00:00:18,780 --> 00:00:20,179
Let's get started.

2
00:00:21,030 --> 00:00:25,360
So, the grades for PA2 were posted.

3
00:00:25,710 --> 00:00:29,770
So you should see those now.

4
00:00:29,930 --> 00:00:30,890
Oh.

5
00:00:31,610 --> 00:00:36,210
So, PA3… It is being graded.

6
00:00:37,240 --> 00:00:41,239
I will try to get the TA to grade a little bit.

7
00:00:41,570 --> 00:00:47,199
More quickly, so that you get those grades, before PA4 is due.

8
00:00:48,300 --> 00:00:56,129
Okay, but… You should have PA1, PA2 graded, now.

9
00:00:56,810 --> 00:01:04,310
The progress reports, I'm still going through. So, don't have those
quite yet.

10
00:01:06,400 --> 00:01:07,310
Okay.

11
00:01:13,680 --> 00:01:19,909
The last time… We started Module 9.

12
00:01:23,900 --> 00:01:26,689
Which is Applications Case Studies.

13
00:01:27,410 --> 00:01:34,480
And so we focused mostly on, different game-playing AIs.

14
00:01:34,870 --> 00:01:38,750
Right, and we didn't quite finish this set of slides.

15
00:01:39,150 --> 00:01:51,690
Here… But… So we talked about… Imperfect information… Like,
strategy-type games.

16
00:01:51,860 --> 00:01:55,920
And we looked at beyond two-player Zero Sum as well.

17
00:01:56,170 --> 00:02:04,439
So some of the systems… Maybe it's worth it if I just actually show
that, that timeline, right?

18
00:02:04,920 --> 00:02:11,289
So… 1992 Backgammon was one of the first early successes.

19
00:02:12,410 --> 00:02:17,009
With getting superhuman performance in the game.

20
00:02:17,920 --> 00:02:21,490
Right? And then here's some of the other milestones.

21
00:02:22,200 --> 00:02:29,820
That we talked about. Great, and so, you know.

22
00:02:30,570 --> 00:02:33,890
There are a lot of challenges.

23
00:02:34,610 --> 00:02:41,289
in all of these different settings, right? Just from the… Size of the
game…

24
00:02:42,050 --> 00:02:50,520
you know, the action space, especially with things like StarCraft II, or
Dota 2, where, like.

25
00:02:50,640 --> 00:02:56,550
It's a… it's a, real time. Real time, and…

26
00:02:56,750 --> 00:03:04,560
the action space is continuous, right? Okay,

27
00:03:07,790 --> 00:03:17,220
So… We made it… Most of the way through those slides, we didn't quite
finish the last part.

28
00:03:21,070 --> 00:03:33,299
But, so the last part of those slides was on, like.

29
00:03:33,410 --> 00:03:41,169
this Brood War, Starcraft Brood War, bot, So we'll pick up there.

30
00:03:43,120 --> 00:03:46,500
And we also noticed that most of the,

31
00:03:47,230 --> 00:03:58,140
Most of the algorithms, or most of the instantiations that we were
seeing, We're prioritized fictitious self-play.

32
00:03:58,780 --> 00:04:03,210
Right? And so… We talked about that a little bit.

33
00:04:03,710 --> 00:04:08,139
But that connects back to, you know, our Module 3.

34
00:04:08,350 --> 00:04:15,020
Where we looked at… Self-play, and we talked about convergence with
iterates.

35
00:04:15,580 --> 00:04:17,990
So in this set of slides.

36
00:04:18,829 --> 00:04:21,889
We are going to go into that a little bit deeper.

37
00:04:23,510 --> 00:04:26,610
So…

38
00:04:29,610 --> 00:04:35,019
But let's pick up with, with Pluto from the Lecture 20.

39
00:04:37,270 --> 00:04:42,480
Which is a very recent… Brood War bot.

40
00:04:42,890 --> 00:04:48,969
So there isn't really a full technical report for it, but… yet.

41
00:04:49,120 --> 00:04:53,809
The author is planning to release something at some point.

42
00:04:54,330 --> 00:05:01,980
But, what's interesting about this System is that it's,

43
00:05:02,320 --> 00:05:07,220
just totally… it's totally self-play, right? So not even,

44
00:05:07,970 --> 00:05:12,980
Fictitious self-play, or, prioritized versions of that.

45
00:05:13,220 --> 00:05:18,759
Right? So, it's just using… According to the author.

46
00:05:18,930 --> 00:05:23,349
just, like, PPO style, actor-critic reinforcement learning.

47
00:05:24,550 --> 00:05:29,979
At every time versus the current rate… the current weights, right,
against each other.

48
00:05:30,390 --> 00:05:36,479
Right? And so that's interesting, because,

49
00:05:40,300 --> 00:05:46,850
Because, the AlphaStar, if you remember from last time.

50
00:05:47,620 --> 00:05:54,369
kind of showed that that didn't work for them, right? For their agents,
right?

51
00:05:54,680 --> 00:05:56,630
So they actually ablated.

52
00:05:57,290 --> 00:06:08,490
Versus self-play… different PFSP variants, right? OpenAI Five.

53
00:06:09,020 --> 00:06:13,150
Same thing, they were using, like a PF…

54
00:06:13,570 --> 00:06:19,220
a PFSP where they sampled 20% from past variants.

55
00:06:19,620 --> 00:06:21,669
And 80% the latest.

56
00:06:22,240 --> 00:06:29,060
Right? So… And…

57
00:06:30,150 --> 00:06:34,110
And then there's also the question of, like, do you initialize from
human data or not?

58
00:06:34,350 --> 00:06:43,790
Right? So… if you remember AlphaGo, the Go version, from Google
DeepMind.

59
00:06:44,570 --> 00:06:51,200
That… the initial version of that did do imitation learning, with human
data.

60
00:06:51,640 --> 00:07:00,000
Right? So what does that mean? That just means, train like a model in a
supervised Fashion?

61
00:07:00,120 --> 00:07:08,220
To produce the human, you know, the human strategy as best as possible,
right?

62
00:07:08,920 --> 00:07:19,060
So… and then improving that further with reinforcement learning, right?
And then… The subsequent variants… you know, like, AlphaZero…

63
00:07:19,510 --> 00:07:23,119
And then we talked about MuZero, where they dropped that part.

64
00:07:24,180 --> 00:07:28,690
so, you know, it's,

65
00:07:29,180 --> 00:07:36,939
It's relevant, like, do we need to initialize it from human data to kind
of, like, constrain the search, or, like, start from a reasonable point,
or not?

66
00:07:37,230 --> 00:07:46,630
Right? And so these two systems, the OpenAI Five and the Pluto, have no
human initialization point.

67
00:07:47,320 --> 00:07:55,510
And then… AlphaStar really needed, you know, the league of agents, as we
talked about.

68
00:07:55,780 --> 00:07:57,570
To make it more robust.

69
00:07:58,200 --> 00:08:05,989
As their variant of, like, policy response oracles, right?

70
00:08:06,780 --> 00:08:11,570
And but Pluto is apparently just using just the latest

71
00:08:11,760 --> 00:08:16,900
just pure self-play, right? Pure, self-play.

72
00:08:17,220 --> 00:08:24,880
So… So yeah, we can…

73
00:08:25,500 --> 00:08:32,490
we can speculate as to… as to why that is, right? But…

74
00:08:33,169 --> 00:08:37,079
You know, we don't actually have a full report from the author.

75
00:08:37,280 --> 00:08:40,419
On that one yet, to actually inspect.

76
00:08:41,080 --> 00:08:48,669
You know, it does do some sort of, like, opening bandit selection of
strategies, which might sort of…

77
00:08:49,390 --> 00:08:55,940
put the… something like the PFSP, like, one level down, right?

78
00:08:56,310 --> 00:08:59,950
So, that's an interesting sort of connection there.

79
00:09:00,720 --> 00:09:03,509
It's like a bandit… It's just, like…

80
00:09:04,000 --> 00:09:10,770
A reinforcement learning setup where you just have one action to pull,
basically one state.

81
00:09:11,260 --> 00:09:17,650
Right? And so there's… A whole theory, like a literature on bandits.

82
00:09:19,400 --> 00:09:21,580
It's like pulling an arm of a slot machine.

83
00:09:21,880 --> 00:09:29,000
Right? And so Pluto apparently does that for its opening strategy
selection.

84
00:09:29,440 --> 00:09:32,120
Right? And so that might…

85
00:09:32,800 --> 00:09:35,080
That might sort of remove the need.

86
00:09:35,400 --> 00:09:40,390
for the prioritized self-play, right? Because you're sort of choosing
among strategies

87
00:09:40,580 --> 00:09:43,880
In a regular try… in a regularized way.

88
00:09:44,140 --> 00:09:47,509
As a built-in part of the strategy.

89
00:09:47,960 --> 00:09:50,649
Right, so, whole host of questions.

90
00:09:51,770 --> 00:09:56,660
Okay.

91
00:09:57,190 --> 00:10:03,199
But, so we see, you know, we see the wide variety of techniques here on
the different,

92
00:10:03,560 --> 00:10:07,980
on the different… systems, right? So with poker.

93
00:10:08,780 --> 00:10:13,229
CFR, Blueprint strategy, plus a sub-game solving.

94
00:10:13,760 --> 00:10:18,399
AlphaZero… Monte Carlo Tree Search with Self Play.

95
00:10:19,610 --> 00:10:29,160
Alf… but again, in this case, right, so in AlphaZero's case, We're
looking at deterministic games.

96
00:10:30,360 --> 00:10:35,150
Which makes, self-play… Much more robust.

97
00:10:36,130 --> 00:10:40,809
AlphaStar Imitation Learning.

98
00:10:40,970 --> 00:10:43,489
than the league with the PFSP.

99
00:10:44,140 --> 00:10:52,850
OpenAI Five… just, a simpler, a much simpler sort of, PFSP.

100
00:10:53,070 --> 00:10:56,380
But… But, right,

101
00:10:57,090 --> 00:11:07,510
you know, then we still have the question of, like, how exploitable? How
exploitable are these things, you know? So that was one of our main
ideas from last time, is…

102
00:11:08,820 --> 00:11:12,249
If you sort of measure the strength of your algorithm.

103
00:11:12,400 --> 00:11:17,939
With some sort of match… matchmaking rating type, score.

104
00:11:18,360 --> 00:11:24,189
That's totally dependent, right, on the population that you… that you're
playing against.

105
00:11:24,740 --> 00:11:32,429
Right? So… OpenAI Five might have a very high competitive strength.

106
00:11:33,100 --> 00:11:39,849
But that doesn't mean that it's not easy to exploit, right? So we have
that,

107
00:11:40,340 --> 00:11:42,420
We had that distinction last time.

108
00:11:42,810 --> 00:11:50,140
And we even saw, with, like, AlphaGo, or AlphaZero.

109
00:11:51,800 --> 00:11:54,320
Which is a deterministic setting.

110
00:11:55,030 --> 00:12:00,200
Right? It was relatively easy to exploit, and not only exploit.

111
00:12:00,410 --> 00:12:07,739
But a human was able to learn that strategy, and exploit the AlphaZero
and win 14 out of 15 games.

112
00:12:08,150 --> 00:12:14,119
Right? So this robustness is a very, a very…

113
00:12:14,460 --> 00:12:23,379
Important concept, and not just measurable by, you know, the strength
versus some population, right?

114
00:12:23,540 --> 00:12:26,169
OpenAI Five, same thing.

115
00:12:26,990 --> 00:12:29,609
They put it on, like, the open ladder.

116
00:12:30,150 --> 00:12:34,689
And humans figure out… figured out how to exploit it, right?

117
00:12:35,690 --> 00:12:38,820
okay.

118
00:12:41,890 --> 00:12:48,069
But one thing that I wanted to talk about today, was,

119
00:12:48,690 --> 00:12:55,520
Why use fictitious self-play or prioritized fictitious self-play at all?

120
00:12:56,260 --> 00:13:01,660
Because if you remember, we did a whole module.

121
00:13:01,890 --> 00:13:06,599
on online learning at the beginning of the class, so that was Module 3.

122
00:13:07,500 --> 00:13:12,000
And we had several algorithms in there.

123
00:13:12,380 --> 00:13:18,600
the… For one thing, we could kind of interpret as different
instantiations.

124
00:13:18,720 --> 00:13:22,500
Of the same algorithm, but they were, like, multiplicative weights
update.

125
00:13:22,870 --> 00:13:26,449
Online mirror descent and follow the regularized leader. Those were…

126
00:13:27,120 --> 00:13:31,369
The names that we had of very similar approaches.

127
00:13:32,140 --> 00:13:33,879
Right, and those had…

128
00:13:34,780 --> 00:13:44,759
an optimal theoretical rate, right, in terms of the regret, if you
remember, which gave us, directly for two-player zero-sum, a convergence
to Nash equilibrium.

129
00:13:45,810 --> 00:13:56,800
Right? Now, fictitious self-play… We, you know…

130
00:13:57,440 --> 00:14:01,920
I think… I think I talked about this algorithm in Module 3.

131
00:14:02,690 --> 00:14:07,340
But we didn't… and it does converge.

132
00:14:08,070 --> 00:14:15,489
But it does… it doesn't even have a convergence rate, necessarily,
right? So that's not known.

133
00:14:16,520 --> 00:14:19,940
We have upper bounds on it that are very weak.

134
00:14:21,140 --> 00:14:34,069
Right? So… So why use this algorithm, you know, if it's theoretically
theoretically, not that great.

135
00:14:34,210 --> 00:14:36,920
You know, when we were looking at,

136
00:14:38,110 --> 00:14:44,045
when we were looking at poker and CFR and all that, Right?

137
00:14:44,870 --> 00:14:47,399
Part of CFR is plugging in.

138
00:14:47,650 --> 00:14:50,420
A no-regret learning algorithm.

139
00:14:51,150 --> 00:14:59,759
And we did not plug in, like, fictitious play, right? We plugged in
stronger things for, like, the multiplicative weights update or
whatever.

140
00:14:59,900 --> 00:15:05,340
Or regret, just, regret minimization, right? Regret matching.

141
00:15:05,500 --> 00:15:07,270
And regret matching plus.

142
00:15:07,960 --> 00:15:11,810
Which had similar rates to, like, MWU and all that.

143
00:15:12,280 --> 00:15:15,840
Right, so why use fictitious play here?

144
00:15:16,610 --> 00:15:19,590
Or prioritized fictitious self-play.

145
00:15:20,450 --> 00:15:25,979
And so, we're gonna ask that question.

146
00:15:29,670 --> 00:15:32,380
And we're gonna talk about, like, the fact

147
00:15:32,750 --> 00:15:34,850
We're… so we're gonna talk about…

148
00:15:35,140 --> 00:15:45,330
Distinguishing last iterate convergence versus average convergence,
right? Which we talked about earlier in the course as well.

149
00:15:46,130 --> 00:15:52,110
But when you're doing, like, these deep learning methods, Right?

150
00:15:55,580 --> 00:16:02,079
that becomes… you know, not a totally trivial question to answer. It's
like, how do we…

151
00:16:02,260 --> 00:16:06,859
How do we learn the average strategy as opposed to just, like, a last
iterate?

152
00:16:07,090 --> 00:16:21,490
And… Since 2020, there have been… Variants of these stronger algorithms.

153
00:16:22,480 --> 00:16:28,090
Partly trying to get last iterate convergence for them.

154
00:16:28,270 --> 00:16:32,990
In certain contexts, right? And,

155
00:16:33,760 --> 00:16:43,680
And yeah, actually be able to apply them, as opposed to things like
fictitious play. And,

156
00:16:44,920 --> 00:16:50,349
There's also a recent paper, which we're gonna talk about last year,

157
00:16:51,260 --> 00:16:55,960
That actually just looked at regularized policy gradient itself.

158
00:16:56,650 --> 00:17:02,590
and actually, it's interesting, so there's actually a connection here.

159
00:17:03,120 --> 00:17:10,290
So, you can connect this reinforcement learning algorithm Policy
gradient.

160
00:17:11,050 --> 00:17:13,169
You can connect it to…

161
00:17:13,579 --> 00:17:24,200
actually something like CFR, or regret minimization. So there's, like, a
normalization term that's missing. If you actually go through the
derivation.

162
00:17:24,819 --> 00:17:27,019
But it's very similar.

163
00:17:27,230 --> 00:17:38,720
Okay, actually… And so this study found that actually just running that
algorithm itself regularized policy gradient.

164
00:17:39,300 --> 00:17:44,099
was at least as good as fictitious play.

165
00:17:44,690 --> 00:17:55,820
policy space response oracles, which was AlphaStar, right? For CFR-based
deep methods, Okay, so…

166
00:17:56,490 --> 00:17:58,979
That's interesting, because it kind of tells us

167
00:17:59,420 --> 00:18:04,149
We can maybe just use more standard reinforcement learning tools.

168
00:18:04,510 --> 00:18:05,770
In practice.

169
00:18:06,140 --> 00:18:08,319
Not have to worry so much.

170
00:18:08,660 --> 00:18:13,680
About which online learning algorithm that we, that we select.

171
00:18:14,830 --> 00:18:21,310
Okay, but so let's, let's just recall what Fictitious play actually was.

172
00:18:22,250 --> 00:18:28,209
And the hedge algorithm, or the multiplicative weights update algorithm
itself.

173
00:18:28,390 --> 00:18:30,329
Right, so fictitious play.

174
00:18:31,640 --> 00:18:37,880
Was just pick, in each round, A best response…

175
00:18:39,870 --> 00:18:44,439
which we might as well take as a pure one. Okay, so pure best response.

176
00:18:44,810 --> 00:18:47,899
To the opponent's empirical average of play.

177
00:18:49,160 --> 00:18:57,980
Okay, that was a… So… So, we take the average strategy of the opponent.

178
00:18:59,610 --> 00:19:03,900
Right, so in normal form, that's just picking strategy for each round.

179
00:19:06,250 --> 00:19:08,639
Whatever they picked, we average it.

180
00:19:08,780 --> 00:19:10,810
That gives me my Y bar.

181
00:19:11,960 --> 00:19:14,009
And then I just best respond to that.

182
00:19:17,470 --> 00:19:22,180
Then, if we want to look at the convergence.

183
00:19:22,920 --> 00:19:29,540
we're looking at the convergence of the X bar and Y bar. Okay, so we
look at X bar, Y bar.

184
00:19:31,040 --> 00:19:38,790
We define this duality gap, G, which is just if both players best
respond, so if player 2 best responds to X bar.

185
00:19:39,200 --> 00:19:41,870
And player 1, best response to Y bar.

186
00:19:42,240 --> 00:19:50,060
How much do they gain in total? So if I add those two up… If that's
zero…

187
00:19:50,430 --> 00:19:55,350
then we're at a Nash equilibrium. There's nothing to gain for either
player.

188
00:19:55,660 --> 00:20:05,350
By deviating. Okay. So Robinson, in one of the very first papers showing
any sort of convergence, like iterative-style convergence.

189
00:20:05,990 --> 00:20:09,240
Showed that fictitious play does converge.

190
00:20:09,640 --> 00:20:11,669
So GT goes to 0.

191
00:20:12,680 --> 00:20:15,990
For two-player zero-sum… Games.

192
00:20:16,400 --> 00:20:20,699
But he doesn't give any convergence rate there.

193
00:20:21,110 --> 00:20:24,370
Right? So, like, how fast? How fast does it go to zero?

194
00:20:24,880 --> 00:20:31,790
If you remember from Module 3, that was where we looked at MWU.

195
00:20:33,000 --> 00:20:34,760
Right? And we had…

196
00:20:35,160 --> 00:20:43,459
So we had a specific way, you know, MW has a specific way of setting the
probability distribution for the next action in terms of…

197
00:20:43,610 --> 00:20:47,859
the losses, right? It also had a step size there.

198
00:20:48,620 --> 00:20:54,330
So, if you remember, you had to set that step size eta.

199
00:20:54,660 --> 00:20:56,710
To this specific value.

200
00:20:57,280 --> 00:21:05,230
And then… the average pair was a Nash equilibrium, up to epsilon here.

201
00:21:06,020 --> 00:21:10,630
Okay, so as t goes to infinity… Epsilon goes to zero.

202
00:21:11,710 --> 00:21:14,090
And we converged to a Nash equilibrium.

203
00:21:15,310 --> 00:21:21,340
But not only that, we get, that Nash equilibrium, Error.

204
00:21:22,040 --> 00:21:25,020
as a function of T, big T.

205
00:21:25,490 --> 00:21:27,510
Right, which is the number of rounds.

206
00:21:28,440 --> 00:21:31,000
Right, so this tells me precisely

207
00:21:31,740 --> 00:21:33,949
how many rounds I need to do.

208
00:21:34,410 --> 00:21:38,350
I want to guarantee… epsilon-Nash.

209
00:21:38,460 --> 00:21:41,340
Right? So that's a lot stronger.

210
00:21:41,790 --> 00:21:43,990
Than not having any rate.

211
00:21:44,150 --> 00:21:46,080
For my convergence, right?

212
00:21:48,680 --> 00:21:59,790
But in both cases, the last iterate is going to cycle, and we saw… we
saw an example of that in Module 3 for MWU, right?

213
00:22:00,090 --> 00:22:02,769
Just in the matching pennies game itself.

214
00:22:03,680 --> 00:22:05,060
Okay.

215
00:22:05,880 --> 00:22:07,970
Right, that was something we talked about.

216
00:22:08,480 --> 00:22:14,680
quite a bit, is that the convergence is just for X bar, Y bar, not
whatever we're currently playing.

217
00:22:15,060 --> 00:22:15,980
Okay.

218
00:22:16,830 --> 00:22:23,420
So then… so the original Robinson paper didn't show convergence rates,
so what has happened since then?

219
00:22:24,290 --> 00:22:25,650
In this table.

220
00:22:25,790 --> 00:22:34,289
Right? So, here T is the number of iterations we've done of FP.

221
00:22:34,900 --> 00:22:42,029
Okay, so, 1958, Shapiro showed an upper bound.

222
00:22:42,940 --> 00:22:48,819
But there's, like, a hidden factor, so there's a big O here.

223
00:22:49,010 --> 00:22:54,499
And there's a hidden factor of, like, this exponential, so A times…

224
00:22:54,610 --> 00:22:56,849
2 to the R plus S here.

225
00:22:57,490 --> 00:23:03,620
Karlin conjectured that it should be O of T to the negative 1 half.

226
00:23:04,100 --> 00:23:07,630
Which is the same rate as, like, MWU.

227
00:23:07,950 --> 00:23:11,490
is… right, so 1 over square root t.

228
00:23:12,170 --> 00:23:15,129
Right? That's exactly what we have here.

229
00:23:17,200 --> 00:23:26,580
But, but… So, 2014.

230
00:23:26,990 --> 00:23:30,040
People show that this conjecture doesn't hold.

231
00:23:30,930 --> 00:23:35,030
Okay, at least if you let ties be broken arbitrarily.

232
00:23:35,750 --> 00:23:37,480
Right, so what does that mean?

233
00:23:38,340 --> 00:23:41,350
So, that means,

234
00:23:48,160 --> 00:23:48,880
Great.

235
00:23:52,590 --> 00:23:53,370
Okay.

236
00:23:54,420 --> 00:23:57,899
So that means, you know, when I have a best response here.

237
00:23:58,140 --> 00:24:00,710
Like, I best respond to Y bar.

238
00:24:01,560 --> 00:24:04,559
But there could be many best responses.

239
00:24:05,930 --> 00:24:10,230
So… how do I pick one? I need a tie-breaking rule.

240
00:24:11,410 --> 00:24:16,489
If, if I let the ties be broken arbitrarily.

241
00:24:16,940 --> 00:24:21,530
Right? Which means I can pick whichever best response I want.

242
00:24:22,960 --> 00:24:30,109
then… FP… Does not converge very quickly, right?

243
00:24:30,230 --> 00:24:32,900
So on the N by N identity.

244
00:24:33,050 --> 00:24:38,170
FP needs big theta of T to the negative 1 over n.

245
00:24:38,830 --> 00:24:39,510
Okay.

246
00:24:44,590 --> 00:24:50,500
But, you know, there's been some results since then, so, like, if the
matrix M, right, so M…

247
00:24:50,820 --> 00:24:53,020
Is my payoff matrix, right?

248
00:24:55,100 --> 00:24:57,110
R rows, S columns.

249
00:24:57,940 --> 00:25:02,520
Right, so if I have a diagonal M,

250
00:25:03,770 --> 00:25:07,719
This paper showed O of T to the negative 1 half.

251
00:25:08,260 --> 00:25:10,859
Using lexicographic ties.

252
00:25:11,570 --> 00:25:12,970
Okay, tie-breaking.

253
00:25:13,590 --> 00:25:18,769
Okay, so those are some results.

254
00:25:19,520 --> 00:25:21,399
Both upper and lower there.

255
00:25:25,680 --> 00:25:26,550
Okay.

256
00:25:29,380 --> 00:25:30,280
Right.

257
00:25:30,970 --> 00:25:33,660
So…

258
00:25:38,830 --> 00:25:40,699
Okay, so…

259
00:25:41,970 --> 00:25:49,349
So the weak form is still open for a general two-player zero-sum, so we
don't really know how fast fictitious play converges.

260
00:25:49,840 --> 00:25:53,710
But here's a plot of how it looks.

261
00:25:53,940 --> 00:25:56,790
In practice, Typically.

262
00:25:57,700 --> 00:26:01,209
So here is, the duality gap.

263
00:26:01,540 --> 00:26:06,979
Right? On, on the… on the left.

264
00:26:07,600 --> 00:26:11,899
Right, so the cum… Cumulative duality gap.

265
00:26:12,490 --> 00:26:16,470
And then just the red line is Y equals 5 times root t.

266
00:26:16,940 --> 00:26:25,259
And, Right, and then the blue line is what we actually get with,

267
00:26:25,480 --> 00:26:35,300
fictitious play for this game. Okay, so this game and this paper
Abernethy, Lai… Wibisono 2021.

268
00:26:36,400 --> 00:26:41,030
Right? So if we were to divide by T,

269
00:26:41,570 --> 00:26:46,169
Right? That's what converges to zero, right?

270
00:26:46,920 --> 00:26:51,670
So this is just random 10x10 Gaussian games.

271
00:26:52,430 --> 00:27:00,650
But, of course, you know, this is just… this is just some empirical
evidence.

272
00:27:06,340 --> 00:27:12,730
Yeah, so… So, the tie-breaking actually is relevant here, which is…

273
00:27:12,880 --> 00:27:15,750
You know, we can try to think about why that would be.

274
00:27:16,300 --> 00:27:21,500
Okay, so, that's fictitious play.

275
00:27:22,260 --> 00:27:24,649
Or, sorry, yeah, that's fictitious play.

276
00:27:25,300 --> 00:27:33,440
what about the prioritized version? Okay, so fictitious self-play.

277
00:27:34,330 --> 00:27:36,510
So what do we mean here?

278
00:27:37,350 --> 00:27:39,289
Well, typically what we're doing…

279
00:27:39,610 --> 00:27:44,139
It's… we're taking fictitious play, and we're trying to do it with
extensive form now.

280
00:27:44,360 --> 00:27:45,889
Okay, extensive form.

281
00:27:46,400 --> 00:27:51,980
Which means we don't even… we're not even actually really doing
fictitious play anymore.

282
00:27:52,280 --> 00:27:57,369
Because we're not really computing best responses anymore, we've got to
approximate that.

283
00:27:57,700 --> 00:28:02,100
And that's typically what we mean when we say fictitious self-play.

284
00:28:02,820 --> 00:28:07,410
We're doing that approximation on the game tree.

285
00:28:07,930 --> 00:28:12,330
so that means we need to average the strategies.

286
00:28:12,470 --> 00:28:18,189
in an approximate way, because we don't really have a full
representation of that. If we do.

287
00:28:18,510 --> 00:28:20,480
Then that's, XFP.

288
00:28:21,320 --> 00:28:28,510
Right, if we just… if we can write down the whole game tree, Do our… do
our behavioral…

289
00:28:28,820 --> 00:28:34,650
strategies, you know, the sequence form and all that through the LP,
computer best response.

290
00:28:35,880 --> 00:28:41,099
If we can do that, then that is exactly just doing FP.

291
00:28:41,430 --> 00:28:43,219
On the extensive form game.

292
00:28:43,490 --> 00:28:46,419
Okay, so… No problems there.

293
00:28:47,110 --> 00:28:53,430
But once we… the game tree is too large for that, we can't even actually
do F… P anymore.

294
00:28:53,820 --> 00:28:57,450
Right, so we have some sort of weakened, fictitious play.

295
00:28:58,140 --> 00:29:03,649
With a best response error, And a step size,

296
00:29:04,980 --> 00:29:08,000
So, if we make some assumptions on that.

297
00:29:08,200 --> 00:29:13,219
Right, that the step size is well-behaved, the errors go to zero.

298
00:29:13,550 --> 00:29:22,720
So… The actual convergence there,

299
00:29:23,800 --> 00:29:33,430
is still an open question, right? If we have a finite computational
budget per iteration, Right,

300
00:29:33,990 --> 00:29:38,520
So once you make things approximate, things get even harder, right?

301
00:29:40,460 --> 00:29:45,930
But… How can we even… how can we even approximate it in a sensible way?

302
00:29:46,260 --> 00:29:53,609
So, neural fictitious self-play, Is this from this paper, Heinrich and
Silver, 2016?

303
00:29:54,960 --> 00:29:55,750
Okay.

304
00:29:56,190 --> 00:30:03,740
And this is how we can actually implement this idea, or something like
this idea.

305
00:30:04,110 --> 00:30:08,340
with, with neural networks, right? Deep neural networks.

306
00:30:08,770 --> 00:30:17,730
Right, so, David Silver, was the main author who sort of got DeepQ
learning.

307
00:30:18,080 --> 00:30:22,159
To exist in the first place, or to be… to be practical?

308
00:30:22,440 --> 00:30:25,269
Right, with the Atari… the Atari games.

309
00:30:25,440 --> 00:30:26,839
Great,

310
00:30:27,510 --> 00:30:31,290
I'm not sure if that was on the timeline that I showed earlier or not, I
think it was.

311
00:30:33,230 --> 00:30:38,000
But for that, you know, you need, essentially, You need the…

312
00:30:38,260 --> 00:30:41,559
the DeepQ network to average over…

313
00:30:41,670 --> 00:30:46,599
you know, a lot of transitions, right? So what they have is what they
call, like, a replay buffer.

314
00:30:47,070 --> 00:30:56,070
Right? So we need… we need those buffers to be adapted here, To actually
implement the self-play.

315
00:30:56,610 --> 00:30:57,430
Okay.

316
00:30:57,910 --> 00:31:03,940
So, we have a circular buffer of beam transitions.

317
00:31:04,770 --> 00:31:10,209
That we can use to try to best respond to… so that's our best response
cue learning.

318
00:31:10,970 --> 00:31:18,070
to actually get the average policy,

319
00:31:19,060 --> 00:31:21,650
What we can do is we can just…

320
00:31:22,180 --> 00:31:25,630
Put our own best response samples.

321
00:31:26,520 --> 00:31:27,970
Into that buffer.

322
00:31:28,530 --> 00:31:31,239
You know, so some of them will be some from…

323
00:31:31,410 --> 00:31:35,619
This current iteration, some will be from previous iterations.

324
00:31:36,120 --> 00:31:37,000
Right.

325
00:31:37,130 --> 00:31:38,489
And so…

326
00:31:39,550 --> 00:31:45,269
what we want is to get the average policy out, right? We want to get the
actual X bar.

327
00:31:46,730 --> 00:31:47,580
Right.

328
00:31:49,280 --> 00:31:56,759
So we do that by putting in samples from all of the best responses, and
then we can train a supervised network

329
00:31:59,190 --> 00:32:03,170
To actually learn that, average policy.

330
00:32:03,940 --> 00:32:04,780
Okay.

331
00:32:05,430 --> 00:32:09,020
Okay.

332
00:32:09,940 --> 00:32:18,889
So, does this converge? You know, and under what assumptions?

333
00:32:19,310 --> 00:32:25,060
Definitely not shown, so no convergence theorem in this paper.

334
00:32:26,490 --> 00:32:31,180
They did show an exploitability of, like.06 on Leduc Poker.

335
00:32:31,560 --> 00:32:35,779
Right? But that's just… You know, an empirical result.

336
00:32:38,490 --> 00:32:39,590
Okay.

337
00:32:39,810 --> 00:32:43,709
But then, prioritized fictitious self-play.

338
00:32:44,090 --> 00:32:46,130
Is what was actually used.

339
00:32:46,340 --> 00:32:48,610
And let's say, like, AlphaStar.

340
00:32:49,260 --> 00:32:55,520
Right? Where they sampled opponents, According to how strong they were.

341
00:32:55,800 --> 00:32:59,139
Right? Or how likely they were to beat our current agent.

342
00:32:59,920 --> 00:33:02,080
Right, if you remember from the last time.

343
00:33:04,070 --> 00:33:10,079
So, we can just assign a probability to B, Based on a function F.

344
00:33:11,070 --> 00:33:13,940
And we can choose F to be different things.

345
00:33:15,160 --> 00:33:17,690
Right, if we just make it 1?

346
00:33:18,250 --> 00:33:20,610
Then it's just fictitious self-play.

347
00:33:21,220 --> 00:33:22,600
It's just uniform.

348
00:33:24,290 --> 00:33:31,160
If we let it adapt to… the probability, omega B here.

349
00:33:31,970 --> 00:33:33,600
The strength of the agent.

350
00:33:34,470 --> 00:33:41,119
Right, then… Opponents that we always beat get weight 0.

351
00:33:41,790 --> 00:33:46,320
So we're not sampling opponents that we can always beat.

352
00:33:48,280 --> 00:33:51,480
And then the stronger it is, the more likely we are to sample it.

353
00:33:51,760 --> 00:33:56,320
Right, and…

354
00:33:59,510 --> 00:34:06,800
We can also try to customize it to sample opponents that are close to
the level of this agent as well.

355
00:34:07,380 --> 00:34:17,600
So in this, in this paper, right, Vinyals et al. 2019, the AlphaStar
paper, They actually used…

356
00:34:17,850 --> 00:34:21,059
So they use both these, versions of F.

357
00:34:21,219 --> 00:34:29,190
for different agents at different times, right? So for main exploiter
agents, if you remember, we had the exploiter agents.

358
00:34:29,500 --> 00:34:30,740
Use this one.

359
00:34:31,590 --> 00:34:38,020
So yeah, so there's a lot of, A lot of choices here.

360
00:34:38,570 --> 00:34:43,899
So, actually, one thing that they claimed in this paper

361
00:34:44,940 --> 00:34:47,760
is that if you let P go to infinity.

362
00:34:50,699 --> 00:34:53,609
This is, like, a, a max min.

363
00:34:54,060 --> 00:34:59,130
Computation here.

364
00:34:59,750 --> 00:35:08,969
Right, so… So… It's pretty easy to see we have a derivation of that in
our… in our notes.

365
00:35:09,440 --> 00:35:11,749
On the website?

366
00:35:12,630 --> 00:35:16,489
But, so, like, as P goes to infinity.

367
00:35:16,980 --> 00:35:23,990
Right, if you look at W, Omega Min, right, Omega Min, So that's gonna
be,

368
00:35:24,790 --> 00:35:33,760
the hardest agent, right? The hardest agent that we have in the, should
have… Omega…

369
00:35:34,990 --> 00:35:37,989
to be the smallest, right?

370
00:35:38,840 --> 00:35:42,759
Then, for any agent, B, that's better than that.

371
00:35:43,450 --> 00:35:48,679
The probability that we sample it… Should go to zero.

372
00:35:48,900 --> 00:35:49,630
Okay.

373
00:35:49,790 --> 00:35:52,490
So all the weight goes to the hardest opponents.

374
00:35:52,850 --> 00:35:57,029
As P… as P increases.

375
00:35:57,540 --> 00:35:59,699
Okay, so P is just a parameter.

376
00:35:59,820 --> 00:36:02,480
That we can pick for this, function.

377
00:36:04,400 --> 00:36:05,140
Great.

378
00:36:05,610 --> 00:36:10,700
So the claim is that this function kind of interpolates between

379
00:36:14,480 --> 00:36:17,390
fictitious self-play and, like, a max-min.

380
00:36:17,690 --> 00:36:19,159
Selection here.

381
00:36:20,400 --> 00:36:30,300
Okay, so… Right, so it's p goes to infinity.

382
00:36:31,380 --> 00:36:38,650
What this, what we're trying to do here as an objective for our
gradient.

383
00:36:38,760 --> 00:36:45,809
Right, Is maximize the worst win rate.

384
00:36:46,030 --> 00:36:49,170
Worst win rate as p goes to infinity.

385
00:36:49,700 --> 00:36:54,030
Right? So at p equals 0…

386
00:36:54,820 --> 00:36:57,399
It's trying to maximize the average.

387
00:36:57,710 --> 00:37:03,920
win rate. Okay.

388
00:37:06,350 --> 00:37:08,150
So, how well does this work?

389
00:37:08,410 --> 00:37:13,639
Right, in practice, so in… in the Vinyals et al. paper, they did a bunch
of ablations.

390
00:37:14,060 --> 00:37:19,489
Right, so they compared… Their version of PFSP.

391
00:37:19,880 --> 00:37:24,219
Versus… Just self-play, fictitious self-play.

392
00:37:25,100 --> 00:37:29,830
you know, so just self-play itself, just playing against the last agent,
right?

393
00:37:30,950 --> 00:37:34,040
Or the best, or the current iteration.

394
00:37:34,750 --> 00:37:36,910
FSP, the uniform weighting.

395
00:37:37,870 --> 00:37:44,359
Right, and so, PFSP beats, FSP.

396
00:37:45,150 --> 00:37:48,560
Under all the measures that they, considered.

397
00:37:49,290 --> 00:38:06,029
Here, so, relative population, performance, min-max, But… But there's
actually no, no published convergence theory,

398
00:38:06,300 --> 00:38:07,509
For this algorithm.

399
00:38:08,010 --> 00:38:08,760
Okay.

400
00:38:09,230 --> 00:38:18,190
So… You know, whenever there's a gap between theory and practice, that
means… You know, empirically.

401
00:38:19,840 --> 00:38:23,710
People are inventing new techniques that then

402
00:38:24,460 --> 00:38:30,130
we can go back and try to understand, right? Okay.

403
00:38:32,040 --> 00:38:40,070
So… One thing you can try to say, or one thing you can try to ask is.

404
00:38:40,370 --> 00:38:47,019
How difficult is it for us to use deep methods to get, like, an average,
strategy?

405
00:38:47,880 --> 00:38:49,320
Right? Because…

406
00:38:50,180 --> 00:38:57,220
You know, if I just… if I best respond each iteration, I get a different
deep Q-net… Q-network each iteration.

407
00:38:57,740 --> 00:39:03,290
How do I average those, right? How do I average those?

408
00:39:03,690 --> 00:39:11,139
I can't just average the weights, right? I don't actually have an
explicit representation of the probabilities.

409
00:39:11,430 --> 00:39:17,869
So, it's not really, it's not totally trivial to try to average those.

410
00:39:17,990 --> 00:39:24,849
But that's what we need, right? For all these different algorithms, we
need, we need an average.

411
00:39:25,210 --> 00:39:27,849
For the, the convergence.

412
00:39:28,350 --> 00:39:31,199
Which is what we want, right?

413
00:39:31,510 --> 00:39:33,939
So, as we saw with NFSP,

414
00:39:34,090 --> 00:39:35,719
That's one way to do it.

415
00:39:35,980 --> 00:39:38,419
So just do supervised learning.

416
00:39:38,540 --> 00:39:42,680
On a reservoir buffer of past best response actions.

417
00:39:43,010 --> 00:39:43,860
Okay.

418
00:39:44,280 --> 00:39:51,480
Another approach… So, deep CFR… Use this.

419
00:39:52,140 --> 00:39:58,839
Which is… Store each sampled strategy.

420
00:39:59,300 --> 00:40:02,500
at an infoset with Wei T.

421
00:40:03,060 --> 00:40:03,880
Okay.

422
00:40:04,240 --> 00:40:07,000
Train Strategy Network on that reservoir.

423
00:40:07,690 --> 00:40:15,020
Another thing is keep every iterations network

424
00:40:16,380 --> 00:40:23,220
you know, in… keep… keep those weights, then just sample one at random
during play, that's another thing.

425
00:40:23,380 --> 00:40:24,740
We could try to do.

426
00:40:25,460 --> 00:40:40,229
So… Another thing… or a third strategy is take, like, the population, or
take a population.

427
00:40:40,580 --> 00:40:42,810
Of agents.

428
00:40:43,170 --> 00:40:47,379
Right, so snapshots of the league with weights.

429
00:40:48,370 --> 00:40:49,670
are a mixture.

430
00:40:49,820 --> 00:40:53,040
Alright, so, like, the league in AlphaStar, for example.

431
00:40:53,580 --> 00:40:58,329
Sample one snapshot per game.

432
00:40:59,090 --> 00:41:12,099
So, with perfect recall, This should be… A behavioral strategy, That
approximates the average. Okay.

433
00:41:14,710 --> 00:41:19,299
But, yeah, so it's not, you know, it's not totally trivial how we can do
that.

434
00:41:20,180 --> 00:41:27,739
But, but, you know, there's gonna be an error associated with this
averaging as well.

435
00:41:28,030 --> 00:41:32,399
Right, so if we're trying to analyze things like convergence, right?

436
00:41:33,820 --> 00:41:46,580
you know… When we look at these guarantees, Right, these are all
assuming

437
00:41:46,850 --> 00:41:53,790
that we actually have X bar and Y bar, right? If we…

438
00:41:54,090 --> 00:42:00,120
If we are sampling an average of those, Right, and then best responding…

439
00:42:00,390 --> 00:42:04,989
Or sampling approximation and best responding to the approximation.

440
00:42:05,410 --> 00:42:08,679
Right, how is that going to impact the convergence?

441
00:42:08,860 --> 00:42:12,370
Right, so these are some of the difficult questions that come up.

442
00:42:13,770 --> 00:42:17,370
Okay.

443
00:42:17,550 --> 00:42:22,550
Right, so if we… if we're using a… if we're using a network, like, with
their,

444
00:42:22,800 --> 00:42:30,140
an average buffer that we're trying to do supervised learning on.
There's gonna be approximation error there.

445
00:42:30,900 --> 00:42:39,280
And there's also gonna be a lag, so we're not actually, computing the
right average there.

446
00:42:40,310 --> 00:42:49,469
Like, the bounds that we talked about do not cover that approximation,
right?

447
00:42:50,190 --> 00:42:52,979
So, average regret need not reach 0.

448
00:42:53,320 --> 00:43:00,150
AlphaStar was not actually running a no-regret learning algorithm.

449
00:43:00,370 --> 00:43:07,530
Right? Right, so, like, Actor Critic updates… Unsampled returns.

450
00:43:08,630 --> 00:43:12,760
is, it's not a no-regret learning algorithm.

451
00:43:12,920 --> 00:43:13,710
Okay.

452
00:43:17,540 --> 00:43:19,910
So what… what can we do instead?

453
00:43:20,680 --> 00:43:22,140
Right,

454
00:43:23,000 --> 00:43:29,910
We can try to get methods that do converge from the last iterate,
because that kind of gets rid of,

455
00:43:30,460 --> 00:43:33,720
That kind of gets rid of a lot of these problems.

456
00:43:33,940 --> 00:43:41,829
Right? So try to come up with a method where our last iterate actually
does converge.

457
00:43:41,950 --> 00:43:46,930
Right? Then, you know.

458
00:43:47,150 --> 00:43:49,600
We can just look at the current network.

459
00:43:50,550 --> 00:43:52,640
And not have to worry about…

460
00:43:52,900 --> 00:44:00,239
averaging, like, supervised learning, buffers, and the errors that, that
come up there, right?

461
00:44:02,030 --> 00:44:05,149
So here's, here's a paper from 2026.

462
00:44:05,590 --> 00:44:12,149
Trying to… trying to accomplish that, right? Okay.

463
00:44:19,340 --> 00:44:27,020
Right? So… Right,

464
00:44:27,590 --> 00:44:33,800
So, who do we actually play when we're doing the learner update? So,
opponent selection…

465
00:44:35,030 --> 00:44:38,260
Is, is one, one axis here.

466
00:44:38,830 --> 00:44:41,590
Right, that's what we've been talking about, mostly.

467
00:44:41,950 --> 00:44:48,539
But then also, how do we… how do we do the learner update itself, is
another axis that we get to pick.

468
00:44:48,940 --> 00:44:49,830
Right?

469
00:44:50,240 --> 00:44:56,089
So approximate best response is what we've been talking about mostly
thus far.

470
00:44:57,240 --> 00:45:04,739
Right? But as we mentioned, you know, there's different reinforcement
learning algorithms that exist that we can just try to use.

471
00:45:04,990 --> 00:45:07,760
And that people do use in practice.

472
00:45:08,400 --> 00:45:12,289
Right? Such as policy gradient itself.

473
00:45:13,010 --> 00:45:16,349
But there's different variants.

474
00:45:17,390 --> 00:45:21,869
That's not actually computing an approximate best response.

475
00:45:22,440 --> 00:45:25,030
So… do those converge?

476
00:45:25,140 --> 00:45:31,019
Great, and, of course, we can combine them with different opponent
selection methods.

477
00:45:31,590 --> 00:45:32,420
Great.

478
00:45:32,720 --> 00:45:33,750
Boom.

479
00:45:34,020 --> 00:45:40,060
So, so yeah, not… not well understood.

480
00:45:46,760 --> 00:45:49,950
So…

481
00:45:53,480 --> 00:45:59,640
Yeah, and so some of these actually don't fit very well in a single
column.

482
00:46:00,240 --> 00:46:04,720
Right, so… Okay.

483
00:46:05,000 --> 00:46:10,670
So the opponent axis is a pluggable, meta solver, right?

484
00:46:11,030 --> 00:46:16,630
So that's, if you remember our policy space response oracles discussion.

485
00:46:16,780 --> 00:46:24,470
right? So we can have a population, Right?

486
00:46:24,950 --> 00:46:27,710
We then play those agents against each other.

487
00:46:27,830 --> 00:46:30,040
That gives us a payoff table.

488
00:46:31,970 --> 00:46:34,829
We then pick some sort of…

489
00:46:34,980 --> 00:46:39,120
Distribution or mixture on those agents?

490
00:46:40,150 --> 00:46:43,050
And then, that's what we best respond to.

491
00:46:43,840 --> 00:46:44,600
Okay.

492
00:46:44,750 --> 00:46:48,879
And we can then add that new policy to our population.

493
00:46:49,640 --> 00:46:53,940
Right, so this was… AlphaStar implemented.

494
00:46:54,220 --> 00:46:58,389
some… Instantiation of this.

495
00:46:59,120 --> 00:47:00,060
Great.

496
00:47:00,730 --> 00:47:03,980
But we have… We have a lot of choices.

497
00:47:04,090 --> 00:47:10,860
Here, right? Which choice we make, you know, gives us different names of
different algorithms.

498
00:47:11,490 --> 00:47:16,540
Right? If we just always use the latest policy.

499
00:47:17,400 --> 00:47:21,179
for sigma minus I here, that's just self-play.

500
00:47:21,460 --> 00:47:22,320
Okay.

501
00:47:22,900 --> 00:47:26,909
If we do a uniform, Thus, fictitious pay… play?

502
00:47:27,870 --> 00:47:32,160
If we do a NASH, Equilibrium mixture here.

503
00:47:32,660 --> 00:47:37,879
That's called Double Oracle, Policy Space Response Oracles.

504
00:47:38,260 --> 00:47:43,400
We can try different things, like regret matching.

505
00:47:44,490 --> 00:47:51,130
we can do PFSP weights, like AlphaStar, just like the league-like thing.

506
00:47:51,990 --> 00:47:58,420
Right? But then… The other axis, so that's,

507
00:47:59,220 --> 00:48:04,429
So, the first axis is this, meta solver.

508
00:48:05,830 --> 00:48:13,750
The other axis is, how do we… how do we actually compute sigma NSI?

509
00:48:14,520 --> 00:48:19,890
Right? You know, if we're actually best responding.

510
00:48:20,320 --> 00:48:27,869
That's one thing, but we can use different learning rules, right? That's
what this x-axis is here.

511
00:48:28,590 --> 00:48:32,250
So that's the, the pink…

512
00:48:32,850 --> 00:48:36,099
Square here, pink rectangle, pink choice.

513
00:48:36,580 --> 00:48:40,860
Versus the, the, tan one here.

514
00:48:41,430 --> 00:48:42,860
Okay.

515
00:48:44,800 --> 00:48:54,349
And then we can ask, you know, what are the different guarantees? So we
can ask, what are the guarantees if we plug in different meta solvers?
That's mostly what we've been asking.

516
00:48:54,600 --> 00:48:58,719
But we can also ask, what if we plug in different algorithms?

517
00:48:59,140 --> 00:49:02,509
For the opponent selection there.

518
00:49:02,910 --> 00:49:09,730
Right? So…

519
00:49:11,240 --> 00:49:15,760
And some of these… some of these do have no regret options that we can
plug in.

520
00:49:16,460 --> 00:49:18,729
PFSP was not one of those.

521
00:49:19,180 --> 00:49:28,560
But… so here's a couple of papers, TMLR 2022, Online Double Oracle.

522
00:49:28,860 --> 00:49:30,810
So, no regret learning.

523
00:49:31,110 --> 00:49:36,910
Inside a double oracle algorithm. So what does that mean, right? So that
means…

524
00:49:38,310 --> 00:49:41,230
Double Oracle, use a Nash solver here.

525
00:49:42,360 --> 00:49:46,969
And no regret means use a no-regret algorithm here, right?

526
00:49:47,730 --> 00:49:50,180
And they actually got a regret bound for that.

527
00:49:50,710 --> 00:49:51,520
Okay.

528
00:49:54,300 --> 00:49:57,180
Okay, what are we doing on time?

529
00:50:01,720 --> 00:50:02,660
Okay.

530
00:50:04,210 --> 00:50:08,410
So there's a lot of open research questions here, I guess, is the
takeaway.

531
00:50:08,640 --> 00:50:17,070
And a lot of difficult ones as well, once we, you know, once we start
doing approximation, And…

532
00:50:17,190 --> 00:50:23,390
instantiating… Instantiating this sort of meta algorithm in many
different ways.

533
00:50:23,820 --> 00:50:28,360
Right. Okay.

534
00:50:28,910 --> 00:50:36,059
So… One thing we mentioned… Was, like, what if we just use…

535
00:50:36,790 --> 00:50:40,519
A sort of more standard reinforcement learning algorithm.

536
00:50:40,700 --> 00:50:44,380
Instead of one of our no-regret algorithms.

537
00:50:44,620 --> 00:50:48,400
So remember, hedge was another name for multiplicative weights update.

538
00:50:48,840 --> 00:50:49,640
Great.

539
00:50:50,060 --> 00:50:58,380
So what if we look at a single state, And we do the update.

540
00:50:58,800 --> 00:51:04,650
According to policy gradient, Versus hedge.

541
00:51:05,040 --> 00:51:09,070
And here's where,

542
00:51:09,810 --> 00:51:14,750
Here's where I was saying these are very similar. Like, if you remember
earlier in the slides, I mentioned.

543
00:51:14,960 --> 00:51:18,719
There's actually a strong sort of analogy here.

544
00:51:19,170 --> 00:51:27,570
If you actually go down and do the math, and you get the update, Right?
So, update…

545
00:51:27,790 --> 00:51:30,309
at, at State A.

546
00:51:30,500 --> 00:51:31,230
Okay.

547
00:51:31,450 --> 00:51:33,119
So we're at State A.

548
00:51:34,590 --> 00:51:39,510
We compute the update for YT.

549
00:51:40,000 --> 00:51:47,909
In terms of YT-1, Plus our, you know, our… the step that our… policy
gradient algorithm gives.

550
00:51:48,560 --> 00:51:52,340
We compare that to what we would get for multiplicative weights update.

551
00:51:53,330 --> 00:52:01,940
There's actually only a difference here of, pi_t of a.

552
00:52:02,740 --> 00:52:15,280
Okay, so PiT is this, term that comes from… the, the, policy,

553
00:52:15,490 --> 00:52:17,100
softmax of Y.

554
00:52:17,260 --> 00:52:17,960
Okay.

555
00:52:18,420 --> 00:52:25,720
So it's just sort of weighting… it's weighting the actions, differently.

556
00:52:26,040 --> 00:52:29,070
So, an action with low probability.

557
00:52:29,970 --> 00:52:38,910
learn slowly under SPG, even if it has become the best response, because
we're weighting it here by its probability of being selected. That's
what,

558
00:52:39,270 --> 00:52:41,319
This pi_t term here.

559
00:52:41,800 --> 00:52:45,460
But… You know, it's actually quite similar.

560
00:52:46,770 --> 00:52:53,700
as an update rule. So if we go back and look at our chart here… Or a
plot.

561
00:52:54,420 --> 00:52:59,489
This, we're looking at the second, the second column here.

562
00:53:00,470 --> 00:53:06,690
Second, spot on the axis, softmax policy gradient, and we're comparing
it

563
00:53:07,330 --> 00:53:12,529
To, like, a hedge in policy space, algorithm here.

564
00:53:13,500 --> 00:53:18,740
Okay, which is a no regret.

565
00:53:20,180 --> 00:53:20,880
Okay.

566
00:53:24,620 --> 00:53:27,929
So what does that factor cost in terms of the regret?

567
00:53:29,210 --> 00:53:31,250
So we have that extra factor.

568
00:53:32,080 --> 00:53:34,030
So we can now try to ask…

569
00:53:34,540 --> 00:53:36,870
Like, what are we giving up for that?

570
00:53:37,080 --> 00:53:40,560
If we wanted to just use softmax Policy Gradient.

571
00:53:41,590 --> 00:53:51,480
And, it turns out, you know, if you do matching pennies,

572
00:53:51,860 --> 00:53:54,190
Or a variant of matching pennies.

573
00:53:54,560 --> 00:54:03,329
You can actually get SPG's regret to grow linearly. Okay, so definitely
not a no regret.

574
00:54:03,550 --> 00:54:04,520
algorithm.

575
00:54:05,120 --> 00:54:08,769
Okay, so that's what this plot here is showing.

576
00:54:13,180 --> 00:54:16,669
And that's in the variant where they added this forfeit action.

577
00:54:16,860 --> 00:54:21,060
Into… Into the game.

578
00:54:24,410 --> 00:54:29,739
So… Why does adding the forfeit action

579
00:54:30,390 --> 00:54:36,200
You know, because without it, actually, SPGs regret Doesn't look like
linear growth.

580
00:54:36,620 --> 00:54:39,530
Okay, so this is a log-log plot.

581
00:54:41,220 --> 00:54:44,310
Linear growth would look like a straight line.

582
00:54:44,850 --> 00:54:46,900
This does not look like linear.

583
00:54:47,140 --> 00:54:48,610
Looks sublinear.

584
00:54:49,320 --> 00:54:54,730
So, without forfeit SPG… Doesn't look that bad.

585
00:54:56,370 --> 00:54:58,010
When we do add it in.

586
00:54:58,540 --> 00:55:01,480
It looks, you know, worst case, bad.

587
00:55:02,060 --> 00:55:04,089
Great, so why would that be?

588
00:55:05,380 --> 00:55:11,539
Well… This is a useless action.

589
00:55:12,360 --> 00:55:23,910
Right, so this is a useless action, so… It, it… It's probably… it's
always worse…

590
00:55:25,880 --> 00:55:28,790
It's always worse to choose forfeit.

591
00:55:29,790 --> 00:55:38,299
Matching pennies against an opponent that switches from H to T after 40%
of the rounds.

592
00:55:38,940 --> 00:55:45,849
Well… Okay, so let's go and look at the…

593
00:55:46,070 --> 00:55:48,779
The formula here, so we have this,

594
00:55:49,760 --> 00:55:53,950
the logit y, that's our,

595
00:55:54,670 --> 00:55:57,990
That's what we're plugging in, that we're doing our softmax over.

596
00:55:58,450 --> 00:56:00,569
Right, to get, pi.

597
00:56:01,440 --> 00:56:07,500
We've got our opponent switches from H to T after 40% of the rounds.

598
00:56:08,320 --> 00:56:09,050
Okay.

599
00:56:09,380 --> 00:56:16,139
That's the opponent that we're trying to do no regret against, right,
that we're trying to learn against.

600
00:56:16,840 --> 00:56:24,180
So… In this case…

601
00:56:24,930 --> 00:56:34,139
You know, it must be that the, the… the weight… being, distributed.

602
00:56:35,250 --> 00:56:41,710
On both the forfeit… You know, end the best response action.

603
00:56:42,180 --> 00:56:47,810
Right? We've… it must make the… the action probability smaller.

604
00:56:48,140 --> 00:56:50,890
Right? So it makes the learning slower.

605
00:56:51,480 --> 00:56:58,470
on the, on the best response action, even after it becomes the best
response.

606
00:56:59,320 --> 00:57:02,580
So… Okay.

607
00:57:05,930 --> 00:57:16,550
So, neural, NeuRD, right? So… That's,

608
00:57:17,410 --> 00:57:19,629
That's the algorithm on the right here.

609
00:57:20,580 --> 00:57:27,610
That's, that's hedge in spot… hedge in policy space.

610
00:57:28,130 --> 00:57:37,899
Right? So here… All we did is we deleted the pi_t(a)… Outta here.

611
00:57:38,510 --> 00:57:41,230
Okay, so one line change in the algorithm.

612
00:57:41,350 --> 00:57:42,230
Right?

613
00:57:42,840 --> 00:57:49,690
So, what does that actually, guarantee.

614
00:57:50,290 --> 00:57:55,380
Right, so…

615
00:57:57,860 --> 00:58:06,239
the difference, right, the difference is this… this pi term, right, in
the update, right? So, gradient theta pi versus

616
00:58:06,510 --> 00:58:08,319
Gradient theta without it.

617
00:58:08,460 --> 00:58:11,320
So if we look at the actual gradient.

618
00:58:11,500 --> 00:58:14,449
What are we doing? We're skipping…

619
00:58:14,770 --> 00:58:17,389
Doing the gradient through the softmax.

620
00:58:18,330 --> 00:58:20,629
So we're… so we're just dropping that term.

621
00:58:21,060 --> 00:58:30,400
And, you know, if we just look at the sequential tabular case,

622
00:58:32,060 --> 00:58:37,709
Then, we are actually just doing… The multiplicative weights update
algorithm.

623
00:58:38,490 --> 00:58:41,829
So, we actually do have our… our regret bound.

624
00:58:42,260 --> 00:58:47,410
Okay, so that fixes policy gradient.

625
00:58:48,320 --> 00:58:49,849
To be no regret?

626
00:58:50,300 --> 00:58:55,420
But we haven't really talked about the average question yet.

627
00:58:56,290 --> 00:59:01,249
Right, and then we still have that last iterate convergence problem, we
haven't talked about that at all.

628
00:59:01,360 --> 00:59:05,249
We've just fixed, the reinforcement learning algorithm.

629
00:59:06,010 --> 00:59:06,860
Okay.

630
00:59:09,020 --> 00:59:15,429
So… How can we get the last iterate to converge? So that's this last
section here.

631
00:59:15,680 --> 00:59:16,950
Part 6.

632
00:59:17,930 --> 00:59:24,839
So… Here are some plots.

633
00:59:25,330 --> 00:59:26,840
of cycles.

634
00:59:27,290 --> 00:59:30,250
Right? In the last iterate.

635
00:59:31,210 --> 00:59:37,260
So this is… this is like Matching Pennies, our favorite game, right?
Two-player zero-sum.

636
00:59:38,540 --> 00:59:41,620
And we're just plotting the last iterate.

637
00:59:42,130 --> 00:59:46,320
You know, as we, as we update. So…

638
00:59:46,670 --> 00:59:49,840
You know, we have a mixed strategy, heads, tails.

639
00:59:50,490 --> 00:59:54,710
That's a two-dimension… or that's a… That's an R2?

640
00:59:55,390 --> 00:59:56,760
We can plot it.

641
00:59:57,400 --> 01:00:02,430
Cycling would mean that it's just going around in a circle, like this,
right?

642
01:00:03,910 --> 01:00:08,910
So, if we use, follow the regularized, leader.

643
01:00:09,880 --> 01:00:14,749
And we do a continuous time variant of it.

644
01:00:15,340 --> 01:00:21,429
This is what… this is what we see. We see it cycling, right? As
expected.

645
01:00:22,270 --> 01:00:23,900
So that's A here.

646
01:00:25,500 --> 01:00:31,519
the actual equilibrium… is the red point.

647
01:00:32,790 --> 01:00:33,540
Okay.

648
01:00:34,980 --> 01:00:36,890
So this is Player 1.

649
01:00:37,110 --> 01:00:39,409
Probability for action 1.

650
01:00:39,850 --> 01:00:41,780
On the y-axis here.

651
01:00:43,160 --> 01:00:47,240
Equilibrium is going to be the red point, and we're not converging to
it.

652
01:00:48,440 --> 01:00:53,450
But what if we try to regularize it?

653
01:00:53,940 --> 01:00:58,290
to try to get it to converge. So that's what this paper does.

654
01:00:58,870 --> 01:01:01,879
Perolat et al. 2021.

655
01:01:03,180 --> 01:01:09,089
Then B to D are different strengths of the regularization.

656
01:01:11,090 --> 01:01:13,730
parameter… Okay.

657
01:01:15,210 --> 01:01:23,040
And we are starting to see convergence here, so as we increase the
regularization, so A no… A, no regularization.

658
01:01:23,180 --> 01:01:24,749
B, we increase it.

659
01:01:25,290 --> 01:01:27,400
C, increase, de-increase.

660
01:01:28,230 --> 01:01:31,720
And we do start to see convergence, right? So…

661
01:01:33,110 --> 01:01:37,249
We see that we start to get, like, a spiral here.

662
01:01:38,340 --> 01:01:40,920
Instead of just a circle.

663
01:01:42,070 --> 01:01:47,119
Right, and but it's actually not converging to the equilibrium.

664
01:01:48,130 --> 01:01:53,250
Because the red dot's here. Right. Red here. Conversions here.

665
01:01:53,950 --> 01:01:58,860
As we increase the convergence more, we get a much better cycling.

666
01:01:59,280 --> 01:02:05,180
But we get farther… As we increase the regularization, we get farther
from the actual equilibrium.

667
01:02:05,730 --> 01:02:07,800
But we're at least converging to something.

668
01:02:08,150 --> 01:02:09,250
That's nice.

669
01:02:10,490 --> 01:02:16,379
Maybe it's not what we wanted to converge to, but… Can't have
everything.

670
01:02:17,070 --> 01:02:21,160
So, I guess the argument here would be…

671
01:02:21,560 --> 01:02:28,360
If you can pick your regularization right, like, see here, maybe.

672
01:02:29,000 --> 01:02:34,380
We get last-iterate convergence that's fairly close to the equilibrium.

673
01:02:35,730 --> 01:02:40,989
And we don't have to worry about things like,

674
01:02:41,940 --> 01:02:49,509
time averaging, neural networks, stuff like that, right? We can just
simply keep our last iterate.

675
01:02:50,220 --> 01:02:52,160
And… and we're good.

676
01:02:52,390 --> 01:02:53,290
Great.

677
01:02:53,640 --> 01:03:05,680
Right, so… Same authors, follow-up paper, this is actually a science
paper, 2022.

678
01:03:06,880 --> 01:03:12,769
Where they do a transformation on the reward.

679
01:03:13,500 --> 01:03:14,400
Okay.

680
01:03:14,720 --> 01:03:24,200
So they essentially, they adjust the rewards of both the players, with
this transformation here.

681
01:03:24,830 --> 01:03:28,840
so they have some reference policy.

682
01:03:28,990 --> 01:03:33,040
pi_reg… They've got a parameter alpha.

683
01:03:33,920 --> 01:03:43,940
And so they sort of, normalized by the pi_reg Policy.

684
01:03:44,140 --> 01:03:45,040
Here.

685
01:03:46,000 --> 01:03:47,649
To adjust the reward.

686
01:03:48,060 --> 01:03:48,780
Okay.

687
01:03:49,330 --> 01:03:52,439
This is a little weird.

688
01:03:53,290 --> 01:04:02,520
If you… Run the dynamics on this game. You get a unique fixed point.

689
01:04:02,890 --> 01:04:12,360
And then what they do is they then iterate, okay? So then, set pi_reg,
To be our fixed point.

690
01:04:12,730 --> 01:04:14,379
And repeat this process.

691
01:04:15,430 --> 01:04:18,879
Okay, and then they actually were able to show…

692
01:04:19,710 --> 01:04:29,389
that the fixed points actually converge to a Nash equilibrium of the
original underlying game. Okay, so this is pretty cool.

693
01:04:29,800 --> 01:04:32,670
So let's see here… let's look at the plot.

694
01:04:36,230 --> 01:04:42,650
So, so yeah, so we're getting convergence.

695
01:04:43,610 --> 01:04:45,700
To our fixed point.

696
01:04:47,020 --> 01:04:48,840
That's the red dot here.

697
01:04:50,600 --> 01:04:54,299
We then set that to be our new pi_reg.

698
01:04:55,270 --> 01:04:57,760
So that's now our pi_1 reg.

699
01:04:58,980 --> 01:05:00,040
Do it again.

700
01:05:01,120 --> 01:05:02,560
Get a new fixed point.

701
01:05:03,410 --> 01:05:05,069
Do it again…

702
01:05:05,760 --> 01:05:15,000
At some point, these stop moving, and the claim is, that's actually the
equilibrium of the original game, and this is matching pennies.

703
01:05:15,800 --> 01:05:18,649
So the equilibrium should be 1 half, 1 half.

704
01:05:19,340 --> 01:05:24,210
And it looks like it is, right? And it looks like that's what we're
converging to.

705
01:05:25,000 --> 01:05:26,420
Okay, so that's good.

706
01:05:28,340 --> 01:05:34,730
Okay, so maybe… Of course, the downside now is we have to do multiple
rounds of convergence.

707
01:05:35,530 --> 01:05:36,560
But…

708
01:05:37,000 --> 01:05:44,929
at least, we don't have to do any averaging, right? We're just, last
iterate converging all the way.

709
01:05:46,040 --> 01:05:46,970
Okay.

710
01:05:47,240 --> 01:05:48,729
So that's kinda cool.

711
01:05:49,600 --> 01:05:52,700
Right.

712
01:05:53,660 --> 01:05:55,790
So here's the actual theorem statement.

713
01:05:56,640 --> 01:06:01,620
So, theorem 6.1… This 2021 version of the paper.

714
01:06:02,560 --> 01:06:09,079
In a monotone game whose Nash Equilibria are all interior.

715
01:06:09,850 --> 01:06:14,689
The sequence of reference policies converges to a Nash equilibrium.

716
01:06:15,360 --> 01:06:16,100
Okay.

717
01:06:16,600 --> 01:06:17,560
Alright.

718
01:06:18,370 --> 01:06:23,880
So, monotone… is a condition.

719
01:06:24,530 --> 01:06:28,870
On the games, the two-player zero sums, they can show satisfies that.

720
01:06:30,550 --> 01:06:31,890
Interior.

721
01:06:32,510 --> 01:06:36,080
That means the equilibrium, you know, is…

722
01:06:36,480 --> 01:06:41,840
Inside, somewhere. It's not on the boundary of the… of the simplex.

723
01:06:42,790 --> 01:06:46,880
Okay, so every action needs to be played.

724
01:06:47,020 --> 01:06:52,120
Right, so every action playing. They conjecture the non-interior case,
but they didn't show it.

725
01:06:52,660 --> 01:06:56,139
Then they did it with DeepNash.

726
01:06:56,880 --> 01:07:02,660
But, of course, they didn't prove anything about the convergence there,
because… You know.

727
01:07:02,800 --> 01:07:08,220
That's where the… The approximation starts… Showing up.

728
01:07:08,460 --> 01:07:11,270
Okay.

729
01:07:11,810 --> 01:07:17,090
Alright, right? So…

730
01:07:18,110 --> 01:07:28,140
You know, essentially trying to get this to actually work, actually
converge, last-iterate convergence, drop all the averaging complexity,
right, on some real examples.

731
01:07:30,140 --> 01:07:33,080
So… Alright.

732
01:07:36,000 --> 01:07:38,200
Okay, last, last set.

733
01:07:38,570 --> 01:07:39,670
Last part.

734
01:07:40,890 --> 01:07:42,720
Magnetic mirror descent.

735
01:07:43,670 --> 01:07:47,870
Okay, so… ICLR 2023.

736
01:07:48,590 --> 01:07:55,920
Mirror Descent, remember, was our online optimization algorithm.

737
01:07:56,180 --> 01:07:57,879
Online Mirror Descent.

738
01:07:58,380 --> 01:08:06,100
Which was… we could interpret as, you know, multiplicative weights of
updates in the online optimization context.

739
01:08:07,190 --> 01:08:14,130
Okay, and… So this paper… Is trying to do something.

740
01:08:15,600 --> 01:08:25,069
You know, so… Trying to, regularize the… Magnetic mirror descent.

741
01:08:26,180 --> 01:08:34,910
In the hopes that we can do something similar, right, as what's going on
over here, and get the last iterate to actually converge.

742
01:08:35,750 --> 01:08:36,620
Okay.

743
01:08:36,760 --> 01:08:39,660
End?

744
01:08:41,010 --> 01:08:46,289
So… What is the actual… Update here.

745
01:08:46,500 --> 01:08:49,089
So they add some regularization terms.

746
01:08:49,510 --> 01:08:53,039
And again… They've got, like,

747
01:08:53,810 --> 01:08:58,460
They've got a regularization versus, rho here.

748
01:08:58,990 --> 01:09:01,949
Which is what they're calling a magnet policy.

749
01:09:02,990 --> 01:09:09,810
So that seems kind of, like, analogous to our,

750
01:09:10,710 --> 01:09:13,560
our pi_reg here, the reference policy.

751
01:09:14,140 --> 01:09:16,439
We've got a magnet policy rho.

752
01:09:16,830 --> 01:09:21,149
And we're sort of penalizing for moving too far from it.

753
01:09:21,370 --> 01:09:25,569
with our KL divergence term, regularization term there.

754
01:09:26,109 --> 01:09:31,719
we've got a parameter alpha, we set it to 0.

755
01:09:32,479 --> 01:09:36,319
That's just, our no-regret hedge.

756
01:09:37,170 --> 01:09:43,840
MWU algorithm. Okay, so set it to zero, regularization term here goes
away.

757
01:09:44,399 --> 01:09:45,960
Set it non-zero.

758
01:09:46,109 --> 01:09:48,120
And we've added this new term.

759
01:09:50,300 --> 01:09:54,960
And, so they were able to show this theorem.

760
01:09:55,590 --> 01:10:00,359
Okay, so if we have… A smoothness constant L.

761
01:10:00,890 --> 01:10:06,379
Okay, which is something like, if we have a Matrix game, it's like the
max payoff or something.

762
01:10:06,850 --> 01:10:07,630
Good.

763
01:10:08,220 --> 01:10:20,250
If we choose our step size smaller… then alpha over L squared, Then, the
distance to the solution.

764
01:10:21,090 --> 01:10:22,350
Should shrink.

765
01:10:22,490 --> 01:10:28,460
by a factor… Of this factor per step.

766
01:10:29,050 --> 01:10:29,780
Okay.

767
01:10:33,950 --> 01:10:38,009
So what does that mean? It means our last iterate is actually
converging.

768
01:10:38,540 --> 01:10:41,700
Great.

769
01:10:43,060 --> 01:10:49,970
with this… with this, this rate here. So, eta, step size, Alpha
parameter.

770
01:10:50,660 --> 01:11:05,310
Okay, which means we have a linear… Last iterate convergence… 2… the
quantal response, equilibrium.

771
01:11:05,960 --> 01:11:06,850
Okay.

772
01:11:07,480 --> 01:11:13,370
so… So that's something.

773
01:11:14,530 --> 01:11:16,470
Okay, last iterate.

774
01:11:17,980 --> 01:11:21,840
So here's actually doing it on a rock, paper, scissors.

775
01:11:22,510 --> 01:11:27,650
Okay, so mag… MMD, magnetic mirror descent.

776
01:11:28,690 --> 01:11:29,440
Okay.

777
01:11:29,940 --> 01:11:37,100
And, so, linear convergence to the last iterate.

778
01:11:37,230 --> 01:11:39,440
We can look at these trajectories.

779
01:11:39,940 --> 01:11:47,320
Right, so… And then these are… these are different temperature values.

780
01:11:47,690 --> 01:11:50,230
Okay, so remember, temperature was our alpha.

781
01:11:50,480 --> 01:11:51,440
parameter.

782
01:11:52,500 --> 01:11:57,270
So, higher it is means more regularization.

783
01:11:57,380 --> 01:12:02,939
That we're doing, right? So, red here… Is the highest value.

784
01:12:04,120 --> 01:12:06,959
And if you notice, it converges to something…

785
01:12:07,150 --> 01:12:10,510
That's farther away from the Nash equilibrium.

786
01:12:11,040 --> 01:12:12,580
Okay, in this case.

787
01:12:13,540 --> 01:12:20,400
But actually, you know, we're actually magnifying This region here.

788
01:12:20,730 --> 01:12:25,720
So… The center, the blue here, is, you know.

789
01:12:25,960 --> 01:12:28,710
Are the equilibrium we're trying to converge to.

790
01:12:28,920 --> 01:12:35,740
Great, or the, yeah, I guess the, the black. The black.

791
01:12:36,370 --> 01:12:39,180
Great.

792
01:12:41,450 --> 01:12:46,860
And, as we… You know, as we… Decrease the temperature.

793
01:12:47,690 --> 01:12:49,979
We get a slower convergence.

794
01:12:50,530 --> 01:12:52,350
That's closer to the black.

795
01:12:52,610 --> 01:12:53,340
Great.

796
01:12:54,680 --> 01:12:57,889
And here's the actual perturbed version of the game that we have.

797
01:12:58,360 --> 01:12:59,420
Alright.

798
01:13:10,280 --> 01:13:14,319
So, oh, very recent, Nature 2026.

799
01:13:14,640 --> 01:13:16,260
Publication on this.

800
01:13:16,800 --> 01:13:26,780
Where, so, multi… er, magnetic mirror descent style self-play with
search.

801
01:13:29,330 --> 01:13:36,520
So, trying to search… Right? Because we need… right? We need several
things for this, right? We've got…

802
01:13:36,940 --> 01:13:41,549
We've got the temperature, alpha, and then the step size needs to depend
on that.

803
01:13:42,660 --> 01:13:46,829
We need, and then we have those two interacting here.

804
01:13:48,340 --> 01:13:54,709
So, if we try to search… On those, so coordinate…

805
01:13:54,820 --> 01:13:58,370
Between Regularization Strength and Policy Update.

806
01:13:59,070 --> 01:14:01,750
So let these vary.

807
01:14:02,040 --> 01:14:04,400
Like, lefties vary with each other.

808
01:14:05,090 --> 01:14:08,569
Right? So we can adapt… we can do adaptive step size.

809
01:14:09,160 --> 01:14:11,530
We can regularize strongly at first.

810
01:14:12,400 --> 01:14:20,420
So we get fast convergence early, and then when we need more accuracy,
Let it, let it vary.

811
01:14:21,280 --> 01:14:27,719
And, so this gives us this algorithm.

812
01:14:28,860 --> 01:14:32,080
Atarak… Ataraxos? Okay.

813
01:14:32,410 --> 01:14:37,079
Which is a damped self-play with a belief model.

814
01:14:37,880 --> 01:14:42,480
And a one-step search. Okay, I'm actually… I'm over time here. But,

815
01:14:42,840 --> 01:14:47,109
Here they're doing it versus the Stratego, so remember we talked about
Stratego last time?

816
01:14:48,020 --> 01:14:55,380
Right, and, you know, apparently the results here…

817
01:14:55,640 --> 01:14:58,810
You know, are, are quite good.

818
01:14:59,110 --> 01:15:01,699
So this is against a human, actually.

819
01:15:02,220 --> 01:15:10,440
Pim Niemeijer… Okay, and the 15 wins… One loss, four draws.

820
01:15:11,880 --> 01:15:12,660
Alright.

821
01:15:12,900 --> 01:15:13,800
Alright.

822
01:15:14,300 --> 01:15:18,600
So I have a few more slides here on, like, What's the current state?

823
01:15:18,720 --> 01:15:19,870
of these.

824
01:15:20,400 --> 01:15:24,699
Right? Which… I welcome you to look through.

825
01:15:25,570 --> 01:15:29,919
But I guess the takeaway is theorying is cut… theory is catching up.

826
01:15:30,350 --> 01:15:32,449
Right, we're getting algorithms.

827
01:15:33,050 --> 01:15:41,110
I can do last-iterate convergence, both theoretically and empirically,

828
01:15:41,630 --> 01:15:44,590
Okay, so I'll… I'll stop here.
