1
00:00:23,250 --> 00:00:26,060
Alright. Hello, everyone.

2
00:00:29,890 --> 00:00:32,930
So, just to remind you,

3
00:00:33,800 --> 00:00:37,119
The Programming Assignment 3 is due this weekend.

4
00:00:38,430 --> 00:00:46,550
So, PA4… I, I adjusted a little bit.

5
00:00:46,770 --> 00:00:53,959
So… it had required you to call, like, make tens of thousands of API
calls.

6
00:00:54,260 --> 00:00:56,070
Which was gonna be difficult.

7
00:00:56,930 --> 00:00:59,120
Within, your budget?

8
00:01:00,470 --> 00:01:06,620
So, I mean, you could have done it over, like, 10 or 12 days.

9
00:01:07,570 --> 00:01:13,290
But… it would have required you to be quite efficient with how you used
it, so…

10
00:01:13,680 --> 00:01:19,199
So I reduced it, so, from 50 questions to 25,

11
00:01:19,660 --> 00:01:23,460
10 debates per profile to 5.

12
00:01:24,700 --> 00:01:29,170
So now, it should be something more like 21,000 calls.

13
00:01:29,320 --> 00:01:32,840
Which still is going to require you to plan ahead a little bit.

14
00:01:33,340 --> 00:01:37,309
Right? So don't wait until the last day on this one.

15
00:01:38,080 --> 00:01:39,770
For PA4.

16
00:01:40,170 --> 00:01:43,309
So it's still due November 21st.

17
00:01:44,960 --> 00:01:51,189
So hopefully that makes it a little bit easier to, to complete it, so
you…

18
00:01:51,520 --> 00:01:54,390
You have a few weeks,

19
00:01:55,700 --> 00:01:58,219
You should be able to make this amount of calls.

20
00:01:58,760 --> 00:02:03,170
Spread out over, like, 5 to 6 days, of budget.

21
00:02:05,090 --> 00:02:05,940
Alright.

22
00:02:07,900 --> 00:02:16,429
Right, and then, the progress report is due tomorrow for the project.

23
00:02:17,510 --> 00:02:21,500
Okay, alright.

24
00:02:24,260 --> 00:02:26,880
So let me know if there are any questions.

25
00:02:33,490 --> 00:02:37,849
Okay, so we're still on monitoring agents.

26
00:02:39,260 --> 00:02:48,679
Right? So last time, we looked at submodularity as a framework for
monitoring.

27
00:02:49,280 --> 00:02:56,560
Which, you know, it's very, it's very relevant for, so that concept,
right?

28
00:02:57,800 --> 00:03:00,949
We talked a little bit about doing it as a game.

29
00:03:01,130 --> 00:03:04,880
Which we're going to continue with, today.

30
00:03:06,990 --> 00:03:11,240
So first, maybe it's just useful…

31
00:03:11,920 --> 00:03:14,920
This was in the slides last time, but,

32
00:03:18,070 --> 00:03:20,159
We should probably go over it again.

33
00:03:20,970 --> 00:03:23,010
Right, so submodularity.

34
00:03:25,750 --> 00:03:32,519
So, submodularity is just a property of a function that you might have,
you know, like…

35
00:03:32,860 --> 00:03:40,620
like, convexity. It's like the discrete analog of convexity, right?
Which is very relevant to optimization.

36
00:03:42,060 --> 00:03:46,750
So there's a whole theory of optimizing submodular functions.

37
00:03:50,710 --> 00:03:54,929
And so why is it relevant to us? Well,

38
00:03:55,640 --> 00:04:00,440
Any sort of monitoring objective is usually going to be submodular.

39
00:04:00,810 --> 00:04:05,579
Right? Because… Submodularity is just diminishing returns.

40
00:04:06,400 --> 00:04:11,420
So if I have, like, if I have a… graph.

41
00:04:11,790 --> 00:04:15,860
Or if I have some ground set that I'm trying to monitor.

42
00:04:16,620 --> 00:04:20,920
If I place a monitor at different, say, vertices.

43
00:04:21,800 --> 00:04:28,720
Right? As my set grows, there's just gonna be a natural sort of
diminishing returns on that.

44
00:04:29,290 --> 00:04:37,610
Right? Which is, what submodularity, is formulated to… encapsulate,
right?

45
00:04:38,360 --> 00:04:43,330
So that's, item 1 here is the diminishing returns.

46
00:04:43,480 --> 00:04:49,690
Right? And 2 and 3 here are equivalent.

47
00:04:50,270 --> 00:04:56,230
Right? So, you could take any one of these three to be… to define
submodularity.

48
00:04:58,870 --> 00:05:05,299
But, so, just very simply, if we have an X, a Y, Is X contained in Y?

49
00:05:06,230 --> 00:05:11,969
And then we add a new element, so, like, picking a new place to monitor.

50
00:05:12,680 --> 00:05:16,690
Right? If we add it to X, and we compare that to adding it to Y.

51
00:05:17,780 --> 00:05:22,210
Right, then the diminishing return says we should get a bigger gain.

52
00:05:22,400 --> 00:05:25,449
for adding it to X, which is the left-hand side here.

53
00:05:25,980 --> 00:05:28,210
Okay, so that's just submodularity.

54
00:05:31,480 --> 00:05:38,199
Item 2 here is another way that people commonly define it, which is just
saying that, like, the whole

55
00:05:40,570 --> 00:05:42,859
Is bounded by the sum of the parts.

56
00:05:43,540 --> 00:05:48,339
Right? So, like, you can't add parts together and get something greater
than the whole.

57
00:05:48,840 --> 00:06:02,400
Okay, and then… If you remember, we also talked about monotonicity, so
that's a separate… function property.

58
00:06:03,290 --> 00:06:05,760
You can combine it with submodularity.

59
00:06:06,680 --> 00:06:14,140
All it's saying is that the function grows, right, as we add more
elements, then it would be amount.

60
00:06:16,190 --> 00:06:17,730
Okay.

61
00:06:18,420 --> 00:06:22,610
Right, so examples… coverage functions.

62
00:06:23,120 --> 00:06:28,750
And monitoring is going to be very similar to, like, a coverage sort of,
function.

63
00:06:31,130 --> 00:06:34,650
But you can also have submodular functions that are not monotone.

64
00:06:35,030 --> 00:06:35,750
Okay.

65
00:06:37,470 --> 00:06:39,430
So here's some examples.

66
00:06:39,740 --> 00:06:41,999
Of that, so, like, a graph cut.

67
00:06:43,570 --> 00:06:46,250
There's a classical example.

68
00:06:46,820 --> 00:06:49,410
Okay.

69
00:06:50,970 --> 00:06:52,760
Alright.

70
00:07:01,510 --> 00:07:02,400
Great.

71
00:07:02,730 --> 00:07:09,780
So last time, you know, If you just have… You know, like, a single…
Agent.

72
00:07:10,510 --> 00:07:14,399
Optimization problem, where you're… you're trying to monitor

73
00:07:14,900 --> 00:07:17,889
Submodularity is going to be good to model that.

74
00:07:18,920 --> 00:07:22,930
And, and there's a lot of guarantees.

75
00:07:23,150 --> 00:07:25,960
You know, for different formulations of…

76
00:07:26,100 --> 00:07:30,640
submodular optimization that you can then use, right? So, like, the
greedy guarantee.

77
00:07:31,210 --> 00:07:35,460
Which is 1 minus 1 over E, if the function is also monotone.

78
00:07:35,880 --> 00:07:42,989
But of course, all of that changes once, once we have an adversary.

79
00:07:43,310 --> 00:07:44,770
Right,

80
00:07:48,070 --> 00:07:48,930
Right?

81
00:07:49,120 --> 00:07:53,190
So, so last time, we looked at greedy with a guarantee.

82
00:07:54,110 --> 00:08:01,700
It's actually really easy to prove this. We didn't really go through the
proof, but…

83
00:08:02,560 --> 00:08:04,810
Yeah, so it's 1 minus 1 over E…

84
00:08:05,140 --> 00:08:10,269
is a non-negative monotone submodular F with a budget K.

85
00:08:10,810 --> 00:08:14,150
And, you know, you can generalize the budget quite a bit.

86
00:08:14,700 --> 00:08:17,039
And still have the same guarantee.

87
00:08:17,480 --> 00:08:22,609
But, in the simplest case, if you just have a size constraint.

88
00:08:24,000 --> 00:08:26,319
It's quite easy to prove this.

89
00:08:26,450 --> 00:08:27,130
Okay.

90
00:08:28,070 --> 00:08:39,589
So we talked about, like, The reliability angle… as a regime, adaptive
angle,

91
00:08:40,110 --> 00:08:44,829
So both of those should still… we should still be able to use this
model.

92
00:08:44,940 --> 00:08:51,089
Right, and we even… so we even formulated a specific objective F, right,
where we had

93
00:08:51,190 --> 00:09:00,290
Like, independent failure probabilities, and then, with the monitoring,
detection probability.

94
00:09:00,550 --> 00:09:05,670
So we formulated that function, right, and that was, submodular.

95
00:09:06,940 --> 00:09:14,200
But but yeah, so the third regime… Where the agent is evading.

96
00:09:14,670 --> 00:09:18,180
Right, so that's where the independence is gonna break down.

97
00:09:18,670 --> 00:09:23,029
Right, so it's not just independent failures anymore.

98
00:09:23,220 --> 00:09:27,210
The adversary is going to concentrate attacks where monitoring is weak.

99
00:09:29,330 --> 00:09:33,789
So today, we're going to look at different ways that we could try to
model that.

100
00:09:34,040 --> 00:09:37,949
And handle that, and, like, what already exists in the literature.

101
00:09:39,600 --> 00:09:40,460
Oh, no.

102
00:09:40,970 --> 00:09:42,730
Okay,

103
00:09:46,740 --> 00:09:52,599
So first, we'll look at the literature at something called robust
submodular optimization.

104
00:09:53,070 --> 00:10:01,979
Where people have, I've tried to handle this and make it like a… like a
min-max, setting.

105
00:10:02,770 --> 00:10:09,770
and so we'll see what's, what already exists?

106
00:10:10,540 --> 00:10:11,530
There.

107
00:10:12,980 --> 00:10:19,929
We'll formulate it more explicitly as, like, this interventionist greedy
game.

108
00:10:20,380 --> 00:10:27,119
We will get some ratios for monotone objectives.

109
00:10:28,290 --> 00:10:31,890
We'll look at different, variants of the model.

110
00:10:32,600 --> 00:10:36,360
And then we'll talk about Programming Assignment 5.

111
00:10:38,230 --> 00:10:41,500
Which has you implement some of these.

112
00:10:42,320 --> 00:10:43,160
Okay.

113
00:10:44,160 --> 00:10:48,490
So first, robust submodular maximization.

114
00:10:49,260 --> 00:10:59,290
Okay, so… We have M, intrusion… intrusion scenarios.

115
00:11:00,180 --> 00:11:07,120
Right? So that's where the agent either inserts a backdoor, or there's
some kind of contamination.

116
00:11:07,650 --> 00:11:08,625
Right?

117
00:11:10,490 --> 00:11:15,289
So, like, so maybe these are… these could be M different policies.

118
00:11:15,500 --> 00:11:19,840
That the… that the agent tries to pick for their… for their back door.

119
00:11:20,280 --> 00:11:27,099
Right? And they get to pick one of those after…

120
00:11:27,670 --> 00:11:31,050
After we commit to the monitoring in this model.

121
00:11:31,330 --> 00:11:32,100
Okay.

122
00:11:32,280 --> 00:11:38,679
So we pick set S… And then the adversary picks set FI.

123
00:11:39,400 --> 00:11:40,270
Great.

124
00:11:42,630 --> 00:11:49,550
So… If we write down that objective formulation, what we want to do is
we want to maximize

125
00:11:50,020 --> 00:11:57,009
over the minimum of the choice, right? So this is a max-min formulation,
you know, like we've seen.

126
00:11:57,210 --> 00:12:11,010
the difference is, here, you know, in our, in our game, Theoretic,

127
00:12:11,670 --> 00:12:13,959
Examples that we've seen, mostly.

128
00:12:14,260 --> 00:12:21,999
Right? We just had the payoffs given to us, right? And so we were maxing
and minning

129
00:12:22,320 --> 00:12:25,449
Over the payoff matrix itself.

130
00:12:25,780 --> 00:12:31,920
Right? In this case, the function itself…

131
00:12:32,790 --> 00:12:40,329
So the… so the action space is very large, right? So even just doing
this maximum, if we have a set F,

132
00:12:40,710 --> 00:12:48,439
It's no longer just… you know, a trivial max, right? If we want to do it
efficiently.

133
00:12:48,700 --> 00:12:51,690
Okay.

134
00:12:52,290 --> 00:12:58,200
So if we look at this function, so the minimum over I of the Fi.

135
00:12:58,640 --> 00:13:00,409
Right, as a function of S.

136
00:13:01,250 --> 00:13:07,080
Unfortunately, that's… that's not submodular, even if all of the little
FIs are.

137
00:13:07,910 --> 00:13:12,180
Okay, and so we can come up with examples where

138
00:13:12,380 --> 00:13:15,249
A greedy algorithm would do arbitrarily badly.

139
00:13:16,580 --> 00:13:24,400
And in fact, we can show that unless P equals NP, No efficient
algorithm.

140
00:13:24,990 --> 00:13:29,140
It's going to get any approximation factor on this at all.

141
00:13:29,360 --> 00:13:34,170
Okay, so this is quite a negative… Result.

142
00:13:35,190 --> 00:13:44,559
Okay, so what this is telling us in the monitoring, setting… Is that,

143
00:13:45,370 --> 00:13:50,280
Essentially, you know, if the agent gets to pick its policy.

144
00:13:50,740 --> 00:13:53,109
After we've picked our set S…

145
00:13:53,430 --> 00:13:59,070
then the problem is very hard, right? So…

146
00:13:59,400 --> 00:14:01,500
The agent is getting to react.

147
00:14:01,610 --> 00:14:03,750
To S, in this case.

148
00:14:04,780 --> 00:14:05,500
Great.

149
00:14:09,760 --> 00:14:13,060
So, we can relax just a little bit.

150
00:14:13,410 --> 00:14:23,699
So… Instead of just looking at the worst case, what if we just look at
the average

151
00:14:24,060 --> 00:14:30,130
At the average case, So, we average over all the FI.

152
00:14:31,630 --> 00:14:37,080
And we also, truncate at some C.

153
00:14:37,580 --> 00:14:42,829
Okay, so… Maybe it's helpful to draw a picture here.

154
00:14:44,140 --> 00:14:45,620
Hey,

155
00:14:49,700 --> 00:14:52,309
So, right, so a submodular function…

156
00:14:53,580 --> 00:14:56,489
Like, intuitively, it's gonna look like this, right?

157
00:14:57,900 --> 00:15:00,150
So that's the diminishing returns part.

158
00:15:00,890 --> 00:15:04,320
Right, so X, maybe, here's, like, the size.

159
00:15:05,000 --> 00:15:06,910
On the x-axis.

160
00:15:07,110 --> 00:15:15,950
the F value on the Y. Of course, this is just like a projection. The
function is a lot more complicated to just draw it like this.

161
00:15:16,950 --> 00:15:24,219
You know, you can have functions that are independent of the elements
and just depend on the size, but that's a very special case.

162
00:15:24,920 --> 00:15:27,920
But this is just sort of the picture.

163
00:15:28,690 --> 00:15:30,649
That you would… that you would have.

164
00:15:30,920 --> 00:15:33,219
Like, some sort of diminishing returns.

165
00:15:33,760 --> 00:15:37,809
And then, if we want to chop it off at C.

166
00:15:38,740 --> 00:15:42,730
Great, that would just be…

167
00:15:56,410 --> 00:15:57,930
I don't know why it's not drawing.

168
00:16:00,330 --> 00:16:01,269
There we go.

169
00:16:03,780 --> 00:16:04,610
Great.

170
00:16:05,140 --> 00:16:06,509
The min of those.

171
00:16:06,990 --> 00:16:10,930
The min of those two would be this, this line here.

172
00:16:12,180 --> 00:16:16,930
Right? So, that's still submodular.

173
00:16:17,040 --> 00:16:18,330
Okay, if I do that.

174
00:16:20,940 --> 00:16:24,960
Right, because the diminishing returns should still be there.

175
00:16:25,660 --> 00:16:33,880
Right, so, and then it turns out, if you average submodular functions
together with any weights.

176
00:16:34,120 --> 00:16:37,039
Like a convex combination.

177
00:16:37,600 --> 00:16:40,949
Submodular functions, that's also submodular.

178
00:16:42,090 --> 00:16:45,059
So this thing is submodular.

179
00:16:47,070 --> 00:16:54,420
And so then we can have an algorithm that binary searches c.

180
00:16:57,010 --> 00:17:01,040
And… We can then accept a C.

181
00:17:02,850 --> 00:17:08,659
If we're within some bound, on our original K budget.

182
00:17:09,170 --> 00:17:10,390
That we have.

183
00:17:11,130 --> 00:17:15,230
And the bound here is actually this, this alpha.

184
00:17:16,390 --> 00:17:17,930
Which is logarithmic.

185
00:17:19,170 --> 00:17:29,360
And then… This Krause et al. paper in 2008 showed But this algorithm
actually… Matches or exceeds opt.

186
00:17:33,540 --> 00:17:36,490
In terms of the FMIN, okay?

187
00:17:37,970 --> 00:17:43,269
Right? Which is a lot better. Like, you know, so this, this average
function.

188
00:17:43,920 --> 00:17:46,840
It's not what we wanted to optimize, right?

189
00:17:48,570 --> 00:17:51,130
We wanted to optimize Fmin here.

190
00:17:53,840 --> 00:17:58,739
And on this slide, we said that was basically impossible, right, unless
P equals NP.

191
00:18:02,870 --> 00:18:05,740
To do in polynomial time, right?

192
00:18:05,870 --> 00:18:12,690
Here, though, what we're saying is actually if we relax the budget,
Okay.

193
00:18:13,230 --> 00:18:17,209
So we're not requiring that we're less than K.

194
00:18:17,390 --> 00:18:19,610
Like, we have this alpha term here.

195
00:18:22,660 --> 00:18:28,410
If we relax the budget, then we can actually get, something that's…

196
00:18:28,840 --> 00:18:32,130
better than the optimal solution. Okay, so…

197
00:18:32,310 --> 00:18:36,069
We might not be feasible, so we're violating the feasibility.

198
00:18:37,180 --> 00:18:47,750
And the impossibility result… Needed us to stay feasible, right? But, so
we relax that.

199
00:18:48,240 --> 00:18:53,329
And we can do… as good as the best case set, right?

200
00:18:53,970 --> 00:18:54,750
Okay.

201
00:18:56,870 --> 00:18:57,730
Okay.

202
00:18:57,840 --> 00:19:00,689
Yeah, so buy the guarantee with budget, not value.

203
00:19:02,640 --> 00:19:05,909
So we're not compromising anything on the value here.

204
00:19:06,140 --> 00:19:12,389
But we do need to spend more budget than we… than the problem actually
asked us for.

205
00:19:12,710 --> 00:19:18,889
Right, so these are all kind of trade-offs, you know, that you can, they
can get into.

206
00:19:19,760 --> 00:19:27,039
when you start looking at optimization problems, right? You could also
sacrifice some of the value.

207
00:19:27,760 --> 00:19:32,600
And the budget. If you do that, that's called a bi-criteria algorithm.

208
00:19:33,220 --> 00:19:37,820
So you're kind of approximating two factors there.

209
00:19:39,550 --> 00:19:45,919
But in this case… We just… we're actually exceeding the optimal value.

210
00:19:46,070 --> 00:19:49,129
And just sacrificing on the… on the budget.

211
00:19:49,830 --> 00:19:50,610
Okay.

212
00:19:51,660 --> 00:19:58,720
So, let's look at some different models we could have.

213
00:19:59,010 --> 00:20:01,840
So we've just been talking about the first one so far.

214
00:20:02,550 --> 00:20:06,539
Right, so the adversary gets to pick the scenario after.

215
00:20:06,640 --> 00:20:09,580
seeing… S.

216
00:20:10,840 --> 00:20:15,050
So, surprisingly, we're still able to do quite well.

217
00:20:15,250 --> 00:20:17,300
By this 2008 result.

218
00:20:17,690 --> 00:20:21,550
If we go logarithmically over budget with that.

219
00:20:21,830 --> 00:20:22,550
Great.

220
00:20:22,740 --> 00:20:25,119
So that's actually quite strong, because…

221
00:20:25,620 --> 00:20:28,819
We're giving the adversary, like, full power.

222
00:20:29,670 --> 00:20:33,639
to see what we did and try to counter it, right?

223
00:20:36,600 --> 00:20:47,349
But of course, there's many other scenarios we could have, so I mean,
maybe that's not very realistic. You know, maybe we can… we can keep
this… the S that we pick hidden.

224
00:20:47,730 --> 00:20:49,300
from the adversary.

225
00:20:49,650 --> 00:20:51,449
Or at least partially hidden.

226
00:20:52,360 --> 00:20:58,140
So… Another scenario, line 2 here.

227
00:20:58,880 --> 00:21:03,179
Is that the adversary actually gets to,

228
00:21:04,010 --> 00:21:06,380
To mess up our set a little bit.

229
00:21:06,560 --> 00:21:07,350
Okay?

230
00:21:07,820 --> 00:21:10,189
So, in this case, we pick S.

231
00:21:12,360 --> 00:21:15,769
And they no longer get to pick the function.

232
00:21:16,810 --> 00:21:18,939
Right, so now the function is fixed.

233
00:21:20,810 --> 00:21:24,119
But the adversary gets to corrupt our set.

234
00:21:24,250 --> 00:21:26,309
Up to some tau.

235
00:21:26,930 --> 00:21:29,689
Okay, so they get to delete elements.

236
00:21:30,330 --> 00:21:32,149
Out of the set that we picked.

237
00:21:33,060 --> 00:21:33,790
Okay.

238
00:21:34,260 --> 00:21:43,430
So now the maxmin changes, right? So now we're still trying to max… over
a min…

239
00:21:43,820 --> 00:21:51,780
But the min is over the ability for them to… mess up our set, right?

240
00:21:52,280 --> 00:21:53,010
Okay.

241
00:21:56,070 --> 00:21:58,100
Okay, so people have studied this.

242
00:21:58,290 --> 00:21:59,380
as well.

243
00:22:00,560 --> 00:22:05,080
And… If you get… if you have a small tau.

244
00:22:05,250 --> 00:22:08,379
So that, you know, the degree to which they get to

245
00:22:08,890 --> 00:22:12,879
Mess up our set is small, then there's constant factor guarantees.

246
00:22:14,490 --> 00:22:19,280
And this is also restricted to the monotone F, setting.

247
00:22:20,510 --> 00:22:21,210
Okay.

248
00:22:24,700 --> 00:22:29,760
So… We can also look at a third model.

249
00:22:30,130 --> 00:22:39,469
So, where, the agent gets to force additions… Into one shared set.

250
00:22:40,310 --> 00:22:43,240
Okay, so here's how we can… we can imagine this.

251
00:22:43,690 --> 00:22:48,000
So… The agent proposes an action.

252
00:22:49,430 --> 00:22:53,569
And the monitor gets to override that action.

253
00:22:54,030 --> 00:22:59,840
at most R time. So R is, like, your budget here, in this case, right?

254
00:23:00,200 --> 00:23:04,000
So this is what we're going to call our interventionist.

255
00:23:04,280 --> 00:23:05,550
Greedy game.

256
00:23:06,060 --> 00:23:09,119
That we're gonna analyze, in these slides.

257
00:23:10,480 --> 00:23:16,360
Okay, so… so if we try to interpret…

258
00:23:19,930 --> 00:23:31,690
If we try to interpret, these in the context of monitoring, Right? If we
evade the monitor.

259
00:23:32,110 --> 00:23:34,729
that sort of deletes its F value.

260
00:23:34,880 --> 00:23:35,630
Okay.

261
00:23:35,830 --> 00:23:38,449
So we can interpret that in,

262
00:23:39,260 --> 00:23:43,940
In sort of, this, this row 2 here.

263
00:23:44,110 --> 00:23:54,470
Great, but… If you get a harmful action that you didn't stop,

264
00:23:55,290 --> 00:23:59,429
That just adds an element to our realized set, okay?

265
00:23:59,810 --> 00:24:05,319
So what we can do, then, is we can relax the, the condition of
monotonicity.

266
00:24:05,980 --> 00:24:06,750
Great.

267
00:24:08,490 --> 00:24:13,229
But remember, monotonicity is just increasing, right? So…

268
00:24:13,630 --> 00:24:16,149
A monotone function would look like this.

269
00:24:16,480 --> 00:24:17,330
You know?

270
00:24:22,070 --> 00:24:28,019
But if it's non-monotone, Like, let's say, you know.

271
00:24:28,560 --> 00:24:34,210
Let's say we're willing to accept… we're willing to accept not catching
everything.

272
00:24:34,840 --> 00:24:38,539
So we're willing to just sort of add that into our objective function.

273
00:24:38,690 --> 00:24:44,630
Okay? So, like, if the agent gets away with something, Then our function
decreases.

274
00:24:44,980 --> 00:24:45,850
Great.

275
00:24:46,490 --> 00:24:50,600
So that's how it could be non-monotone, right?

276
00:24:51,690 --> 00:24:56,419
And then we still want to optimize this function, right? So we're sort
of,

277
00:24:56,720 --> 00:25:01,010
Adopting a more general model, Here.

278
00:25:02,210 --> 00:25:04,370
Okay,

279
00:25:04,880 --> 00:25:10,450
Then that's, you know, we can kind of… we can use this third row of the
table to try to model that.

280
00:25:11,170 --> 00:25:16,470
Okay, so the agent proposes actions, and the monitor can override.

281
00:25:16,580 --> 00:25:19,410
R times.

282
00:25:19,650 --> 00:25:23,890
out of the total number of actions. So there's going to be K actions
total.

283
00:25:24,830 --> 00:25:27,980
The monitor gets to override R times.

284
00:25:28,110 --> 00:25:28,830
Great.

285
00:25:29,570 --> 00:25:30,790
Okay.

286
00:25:30,930 --> 00:25:34,390
So let's… So let's formalize this.

287
00:25:35,370 --> 00:25:41,000
So we have a ground set V of actions.

288
00:25:41,810 --> 00:25:43,950
So there's N total actions.

289
00:25:44,490 --> 00:25:53,370
We have… A non-negative submodular objective function F, Okay.

290
00:25:56,020 --> 00:26:01,880
Right, so, we have a selected set S,

291
00:26:02,410 --> 00:26:05,360
I'm sure these are the actions that have been picked so far.

292
00:26:05,940 --> 00:26:07,939
So we're gonna do this in rounds.

293
00:26:08,350 --> 00:26:12,640
Okay, so this is kind of like an online… Setting here.

294
00:26:13,760 --> 00:26:22,190
Once the monitor blocks an action, That stays off-limits.

295
00:26:22,380 --> 00:26:23,160
Okay.

296
00:26:23,680 --> 00:26:29,560
And then we have a remaining budget Q less than R, so, like, in an
online fashion, right?

297
00:26:29,820 --> 00:26:35,289
So let's… so let's have this model. So, an agent proposes the action A,

298
00:26:36,350 --> 00:26:38,930
in V minus S union B.

299
00:26:39,650 --> 00:26:40,420
P.

300
00:26:41,020 --> 00:26:43,109
So they're proposing an action.

301
00:26:43,990 --> 00:26:47,290
if the monitor accepts it.

302
00:26:48,250 --> 00:26:49,830
Then we add it to S.

303
00:26:51,260 --> 00:26:54,060
Right, or the monitor can override.

304
00:26:54,700 --> 00:26:58,060
Only if they've got budget left for that.

305
00:26:58,840 --> 00:27:07,449
In which case… The monitor itself picks… A different action.

306
00:27:07,910 --> 00:27:10,459
Okay, not equal to the original one.

307
00:27:11,120 --> 00:27:18,679
And we add A to a blocked set B, right? So now the agent is no longer
allowed to pick that.

308
00:27:19,000 --> 00:27:19,690
Good.

309
00:27:20,020 --> 00:27:26,980
And we've spent, in that case, if we override, we spent one of the
budget q.

310
00:27:27,150 --> 00:27:32,270
Okay, so that starts equal to… et cetera.

311
00:27:33,290 --> 00:27:37,989
Okay, so, in this case.

312
00:27:38,540 --> 00:27:42,259
Then the payoff is SK, just F of SK at the end.

313
00:27:42,570 --> 00:27:45,079
Right? After K rounds.

314
00:27:50,690 --> 00:27:54,639
The monitor is trying to maximize F, the agent is trying to minimize F.

315
00:27:55,080 --> 00:27:55,910
Okay.

316
00:27:57,140 --> 00:28:10,300
Alright, so… Yeah, so… Blocking needs to be permanent.

317
00:28:10,920 --> 00:28:15,349
Right? In this model, because otherwise the agent could just keep
proposing a…

318
00:28:15,640 --> 00:28:18,919
Over and over again, right? Until it gets through.

319
00:28:21,070 --> 00:28:28,269
But of course, you know, there's many different ways you could try to
take this basic model and extend it, right? For one thing.

320
00:28:28,950 --> 00:28:36,199
you know… being able to query F… You know, that might…

321
00:28:36,340 --> 00:28:39,379
Just offline with a value oracle.

322
00:28:40,180 --> 00:28:44,069
you know, that's a pretty strong assumption right there.

323
00:28:44,270 --> 00:28:46,440
So that might want to be relaxed, but…

324
00:28:46,820 --> 00:28:52,919
Let's, so let's look at it as, you know, A, a game tree.

325
00:28:54,210 --> 00:28:55,030
Okay.

326
00:28:55,480 --> 00:28:58,500
So we have a state like SBQ.

327
00:28:59,390 --> 00:29:04,660
Okay, so this is going to be a subtree that we plug into the SBQ spot.

328
00:29:04,980 --> 00:29:06,180
In the tree?

329
00:29:07,080 --> 00:29:09,240
Right, the agent picks an action.

330
00:29:11,220 --> 00:29:16,820
Monitor, then, for any of those, right? So this subtree is gonna be
everywhere.

331
00:29:17,150 --> 00:29:17,820
Oops.

332
00:29:23,660 --> 00:29:28,190
Right, so… There's an accept.

333
00:29:28,830 --> 00:29:32,520
Accept here, or… Override.

334
00:29:35,280 --> 00:29:41,699
Of course, once, once Q gets to zero, There's no override left.

335
00:29:43,490 --> 00:29:47,289
This is gonna be a pretty large tree.

336
00:29:47,800 --> 00:29:51,280
Right, great.

337
00:29:51,660 --> 00:29:57,560
If the agent accepts… I mean, if the monitor accepts, then we just
accept A2 in this case.

338
00:29:58,030 --> 00:30:01,100
B doesn't change, Q doesn't change.

339
00:30:01,970 --> 00:30:05,630
Or we can block A2 and override.

340
00:30:06,060 --> 00:30:07,549
Great, in that case.

341
00:30:07,660 --> 00:30:11,880
so then… The monitor picks I.

342
00:30:13,480 --> 00:30:14,970
A2 gets blocked.

343
00:30:15,790 --> 00:30:17,670
One budget is spent.

344
00:30:17,950 --> 00:30:18,650
Great.

345
00:30:19,110 --> 00:30:22,380
Then when we get to a leaf,

346
00:30:23,560 --> 00:30:25,689
our payoff is just F of SK.

347
00:30:25,820 --> 00:30:26,620
Great.

348
00:30:27,590 --> 00:30:28,530
Okay.

349
00:30:30,880 --> 00:30:34,610
So the monitor's move is a response to the proposal.

350
00:30:35,360 --> 00:30:40,080
The agent sees the whole history, including which overrides have been
spent.

351
00:30:41,170 --> 00:30:46,810
But we can… we can just go ahead and do backward induction on this,
right? So this is a finite tree.

352
00:30:53,140 --> 00:31:00,010
So And so here's the… here's the formula, right, for the, backward
induction.

353
00:31:00,880 --> 00:31:01,770
Great.

354
00:31:02,140 --> 00:31:08,140
So the agent is just gonna pick… The action.

355
00:31:08,810 --> 00:31:11,200
that over A, you know?

356
00:31:11,500 --> 00:31:12,979
Or pick an A.

357
00:31:13,560 --> 00:31:17,450
that minimizes… the max.

358
00:31:18,330 --> 00:31:21,820
Right, being… The value.

359
00:31:22,400 --> 00:31:29,930
if A is accepted versus, if the monitor, or the best block the monitor
can do.

360
00:31:30,680 --> 00:31:36,110
You know, relying on the value of the subtrees, Down here, right?

361
00:31:36,360 --> 00:31:37,080
Okay.

362
00:31:37,930 --> 00:31:41,550
Okay.

363
00:31:41,760 --> 00:31:50,500
So, you know, we can solve it with backward induction. There's no…
there's perfect information here, right?

364
00:31:51,370 --> 00:31:55,790
This is a perfect information, extensive form game.

365
00:31:56,780 --> 00:32:05,099
So backward induction solves it, and also the strategies… we have
optimal pure strategies, right? Pure optimal strategies.

366
00:32:05,380 --> 00:32:08,009
As we learned, right, in the past, right?

367
00:32:08,530 --> 00:32:11,870
So… We don't need randomization here.

368
00:32:12,090 --> 00:32:15,310
Okay.

369
00:32:15,730 --> 00:32:28,290
Okay. But, but how big is this game tree, right? Turns out it's very
big.

370
00:32:28,530 --> 00:32:30,620
exponential on N.

371
00:32:31,090 --> 00:32:44,479
Okay, so… We might want, more efficient algorithms for this.

372
00:32:47,150 --> 00:32:55,970
Okay, so… So we can have this theorem.

373
00:32:57,230 --> 00:33:03,529
So, fix… any T with T less than or equal to R.

374
00:33:06,300 --> 00:33:11,550
So, the monitor can always… Force this set T.

375
00:33:12,090 --> 00:33:16,030
Right? Because it has R budget.

376
00:33:16,410 --> 00:33:18,199
You can override.

377
00:33:19,160 --> 00:33:28,869
R times, so we can always get the monitor The monitor can always, force
a set T.

378
00:33:29,240 --> 00:33:30,110
Boom.

379
00:33:31,410 --> 00:33:37,760
However, well, so this gives us this theorem.

380
00:33:38,220 --> 00:33:39,520
A lower bound.

381
00:33:40,720 --> 00:33:43,520
Just… which follows just from submodularity.

382
00:33:44,170 --> 00:33:46,630
And the fact that we can,

383
00:33:47,490 --> 00:33:49,979
that we can force a T.

384
00:33:50,760 --> 00:33:52,200
of size R.

385
00:33:52,810 --> 00:33:57,140
And then, actually, we're assuming monotonicity for this, on this slide.

386
00:33:57,410 --> 00:33:59,340
So we're gonna relax that.

387
00:34:00,020 --> 00:34:07,729
But if we do assume monotonicity, then submodularity and monotonicity
just… Give you a simple…

388
00:34:08,000 --> 00:34:11,199
like, R over K bound there.

389
00:34:11,590 --> 00:34:12,420
Great.

390
00:34:13,170 --> 00:34:19,360
So, essentially, what that's saying is… The monitor can force…

391
00:34:20,580 --> 00:34:22,980
the best R set that exists.

392
00:34:23,830 --> 00:34:24,580
Great.

393
00:34:40,219 --> 00:34:43,249
Okay, so the monitor forces the best R-set.

394
00:34:48,050 --> 00:34:53,320
And then… The agent… well, we haven't shown this yet, but…

395
00:34:55,130 --> 00:35:06,020
Clearly, there exist objectives, right, where the agent then can just
force a zero, Beyond that… And so…

396
00:35:08,380 --> 00:35:11,679
This is gonna be a tight… this is gonna be a tight bound.

397
00:35:15,860 --> 00:35:20,020
But that still requires the monitor to actually find the best R-set.

398
00:35:20,560 --> 00:35:25,539
Which is also still gonna be… Not efficient, okay?

399
00:35:25,800 --> 00:35:27,559
But we can approximate that.

400
00:35:27,960 --> 00:35:31,760
Similar to, you know, how we do greedy approximations.

401
00:35:32,150 --> 00:35:37,829
In general here. And that'll give us this bound, 1 minus e to the
negative r over k.

402
00:35:38,870 --> 00:35:43,620
Okay, and yeah, and we can write down functions.

403
00:35:44,300 --> 00:35:53,369
even modular functions, so just, like, additive functions, not even the
submodular thing, right? So no, no diminishing returns, just exact.

404
00:35:53,610 --> 00:35:54,880
Modularity?

405
00:35:56,580 --> 00:35:59,909
Where the agent gets just com… at a zero.

406
00:36:01,300 --> 00:36:04,580
there's at most R goods, and we get R over K.

407
00:36:05,260 --> 00:36:06,020
Okay.

408
00:36:06,300 --> 00:36:10,859
So here's a worked example.

409
00:36:11,120 --> 00:36:26,349
So K equals 4, R equals 2, so… Let's see, so we have 4 zeros.

410
00:36:32,160 --> 00:36:33,620
Four good elements.

411
00:36:34,800 --> 00:36:35,540
Okay.

412
00:36:36,070 --> 00:36:39,290
Our function is just how many good elements did we pick?

413
00:36:39,810 --> 00:36:47,780
Right? So that is a modular function, so it's also submodular. It's also
monotone.

414
00:36:54,050 --> 00:36:56,669
Yeah, well, it's actually submodular.

415
00:36:57,070 --> 00:37:03,639
Because the zeros… Don't add anything.

416
00:37:04,130 --> 00:37:12,770
So… The monitor's budget is two… Overall budget is 4.

417
00:37:13,870 --> 00:37:17,600
So, of course, our optimum is 4 if we just pick all the good elements.

418
00:37:19,020 --> 00:37:22,440
But the monitor can only force two good elements, right?

419
00:37:23,060 --> 00:37:30,560
So… The monitor can accept two zeros, and it will have to at some point.

420
00:37:31,310 --> 00:37:37,230
Whether it does it initially, Or, or later.

421
00:37:38,010 --> 00:37:43,780
And then it can override and get to, two good elements.

422
00:37:45,640 --> 00:37:46,510
Alright.

423
00:37:48,660 --> 00:37:49,590
So…

424
00:37:55,650 --> 00:38:04,650
Right, so, we had mentioned, right, the blocking elements part, right?

425
00:38:04,980 --> 00:38:09,260
so, once the monitor overrides a proposal.

426
00:38:10,010 --> 00:38:13,780
That element is blocked. That action is blocked.

427
00:38:14,480 --> 00:38:18,929
So the action set shrinks, right, every time, it's caught.

428
00:38:19,800 --> 00:38:20,930
In this case.

429
00:38:24,800 --> 00:38:29,479
And, so this is especially important once we,

430
00:38:29,870 --> 00:38:32,430
Once we extend to non-monotone objectives.

431
00:38:32,830 --> 00:38:37,770
Right? You know, suppose,

432
00:38:38,880 --> 00:38:41,880
Suppose there's one element that always…

433
00:38:42,510 --> 00:38:45,710
negates down to zero. You know, like…

434
00:38:46,110 --> 00:38:52,410
a really bad case, you know? Like, I don't know, the agent hacks,
Hugging Face.

435
00:38:53,370 --> 00:38:56,499
So, like, that… we can call that, like, a poison.

436
00:38:57,370 --> 00:38:58,529
Poison pill.

437
00:38:59,210 --> 00:39:03,079
So, we need to be able to, to block those.

438
00:39:03,640 --> 00:39:05,909
Right? And then they don't…

439
00:39:06,150 --> 00:39:10,730
they don't continue to show up as possibilities, right?

440
00:39:11,210 --> 00:39:16,069
So, I don't know, the agent tries to put in a backdoor, Let me detect
it…

441
00:39:16,290 --> 00:39:21,360
So that's no longer a valid, action the agent can take.

442
00:39:23,470 --> 00:39:25,109
Right, we can just automate.

443
00:39:25,380 --> 00:39:29,190
At that point, we could just automate the, the detection there.

444
00:39:29,390 --> 00:39:30,060
Okay.

445
00:39:32,140 --> 00:39:36,180
Okay, so… So we can't have this sort of scenario.

446
00:39:36,430 --> 00:39:39,940
Where the agent just insists on P?

447
00:39:40,490 --> 00:39:44,710
And forces the monitor to override it R times.

448
00:39:44,940 --> 00:39:46,180
And then…

449
00:39:46,380 --> 00:39:51,350
You can just put P in and get a value of 0. But we… we rule out that
case.

450
00:39:52,780 --> 00:39:53,590
Okay.

451
00:39:58,370 --> 00:40:00,189
Yeah, so…

452
00:40:00,470 --> 00:40:06,289
So we definitely need that, you know, in the non-monotone case. In the
monotone case, it actually doesn't matter.

453
00:40:07,210 --> 00:40:10,679
Okay, because in the monotone case, elements can't actually hurt.

454
00:40:11,520 --> 00:40:18,089
they can at most be, like, zero value. So this is kind of the worst case
here, is these zero elements.

455
00:40:18,910 --> 00:40:22,410
Rather than… actively harmful.

456
00:40:23,140 --> 00:40:28,550
Right, in the non-monotone case, elements can be harmful.

457
00:40:30,890 --> 00:40:31,840
Okay.

458
00:40:32,780 --> 00:40:36,450
Yeah.

459
00:40:36,780 --> 00:40:46,299
So this makes the game also more interesting, right? Because the agent…
Has to either commit to…

460
00:40:47,440 --> 00:40:49,210
A poisonous element.

461
00:40:49,750 --> 00:40:51,200
Wish they could be blocked.

462
00:40:51,520 --> 00:40:55,329
And then it no longer has that opportunity going forward.

463
00:40:56,020 --> 00:41:04,110
Right, so… So… Any, any proposal…

464
00:41:04,500 --> 00:41:09,449
While the monitor still has budget, is… is a gamble.

465
00:41:09,800 --> 00:41:21,160
Right, so… If the… if the agent gets the element in, Then… succeeded.

466
00:41:21,430 --> 00:41:23,350
That element stays in S.

467
00:41:24,380 --> 00:41:29,369
The monitor can't go back and delete accepted items.

468
00:41:31,040 --> 00:41:35,490
If, however, the monitor does detect it and overrides it.

469
00:41:35,950 --> 00:41:42,870
the agent no longer gets to… gets to try that, right? So…

470
00:41:43,000 --> 00:41:46,590
there's a more interesting trade-off here, right?

471
00:41:46,760 --> 00:41:52,210
Let's say the agent has a lot of mildly harmful Elements?

472
00:41:53,380 --> 00:41:57,809
maybe… It needs… it tries to deploy those first.

473
00:41:57,920 --> 00:42:00,580
You know, use up the monitoring budget.

474
00:42:01,180 --> 00:42:03,749
Then go with something really harmful?

475
00:42:05,040 --> 00:42:13,630
Right? Or, of course, you know, if the mildly harmful elements aren't
harmful enough, then the monitor doesn't even commit there.

476
00:42:14,120 --> 00:42:21,190
Right? So, so the sync… the sequencing really matters here.

477
00:42:23,470 --> 00:42:24,410
Okay.

478
00:42:25,580 --> 00:42:29,809
So, and I actually haven't…

479
00:42:30,190 --> 00:42:34,199
I haven't fully analyzed this game. I have some partial results on it.

480
00:42:34,880 --> 00:42:39,010
I haven't really had time.

481
00:42:39,460 --> 00:42:40,669
To go through it.

482
00:42:41,730 --> 00:42:48,419
But… Let's look at, you know, let's look more specifically at AI
control.

483
00:42:48,770 --> 00:42:50,890
Game over a sequence of tasks.

484
00:42:51,900 --> 00:42:57,610
Right, so we have the blue as our protocol versus red, our untrusted
model.

485
00:42:57,810 --> 00:43:03,699
So remember, we had M programming problems, so we looked at this, in the
last set of slides.

486
00:43:04,400 --> 00:43:06,690
Right, so Blue has an audit budget.

487
00:43:07,480 --> 00:43:10,890
Red chooses when to insert a back door.

488
00:43:12,140 --> 00:43:15,769
Blue was memory full, red was memory-less.

489
00:43:16,220 --> 00:43:17,709
In this case.

490
00:43:18,140 --> 00:43:23,060
And we had a leader follower… Equilibrium…

491
00:43:26,200 --> 00:43:27,320
concept?

492
00:43:27,510 --> 00:43:32,740
right, so Greenblatt… Greenblatt had a…

493
00:43:33,110 --> 00:43:35,820
Several different protocols that they looked at.

494
00:43:35,940 --> 00:43:38,890
But that was the blue strategy.

495
00:43:39,740 --> 00:43:43,569
So, for example, Never audit anything.

496
00:43:45,190 --> 00:43:47,329
Just run the trusted model.

497
00:43:47,470 --> 00:43:49,710
Those were kind of the trivial cases.

498
00:43:50,730 --> 00:43:54,620
Upfront auditing, just spend all the budget right away.

499
00:43:54,980 --> 00:43:57,270
Obviously not a very good strategy.

500
00:43:59,800 --> 00:44:01,390
Trusted monitoring.

501
00:44:02,420 --> 00:44:12,450
New protocols, so… Raising the audit false positive rate.

502
00:44:12,550 --> 00:44:18,520
Where, that can give us a little bit of…

503
00:44:18,750 --> 00:44:21,569
An improvement in the weak monitor case.

504
00:44:22,040 --> 00:44:27,309
Right? We had quite a few assumptions.

505
00:44:27,640 --> 00:44:37,630
As far as the safety and usefulness, dangerous actions…

506
00:44:40,010 --> 00:44:46,969
So… so we can try to take all this and interpret it in our… our IGG
model.

507
00:44:47,610 --> 00:44:53,619
Right? And the mapping might not be totally perfect.

508
00:44:54,110 --> 00:44:59,040
But that's, you know, that's the beauty of modeling, is you get to
change the model.

509
00:44:59,760 --> 00:45:03,470
To better correspond with reality.

510
00:45:04,910 --> 00:45:13,410
And if you remember, we also had in the Greenblatt, Formalism.

511
00:45:13,950 --> 00:45:19,420
We had the H… H, trusted labor.

512
00:45:20,600 --> 00:45:24,490
Which was… Ideally, human labor.

513
00:45:25,440 --> 00:45:29,169
But they actually used a GPT-4 for that.

514
00:45:30,770 --> 00:45:31,770
Right.

515
00:45:32,210 --> 00:45:36,810
okay,

516
00:45:38,770 --> 00:45:45,510
And again, in Programming Assignment 5, you're going to be asked to, to
implement one of these.

517
00:45:45,990 --> 00:45:49,279
Like, an audit-run version of this.

518
00:45:50,810 --> 00:45:55,420
with a single threshold, right? So, so remember how that works is,

519
00:45:56,250 --> 00:45:59,600
The monitor is the… the monitor's a weak model.

520
00:46:00,570 --> 00:46:07,449
The monitor, in this case, gives us… a… Suspicion score.

521
00:46:08,290 --> 00:46:10,559
If that's above a threshold tau.

522
00:46:10,960 --> 00:46:13,170
We actually do the full audit.

523
00:46:13,360 --> 00:46:14,819
You know, with H.

524
00:46:15,970 --> 00:46:21,209
If it's below just, let me just execute in this… in this version.

525
00:46:22,380 --> 00:46:27,120
But of course, there's different protocols that you can, you can come up
with.

526
00:46:29,710 --> 00:46:36,580
Right. So as far as, actually getting some results.

527
00:46:37,260 --> 00:46:39,289
In the non-monotone case.

528
00:46:41,940 --> 00:46:48,640
So… we, we have a construction here.

529
00:46:49,450 --> 00:46:59,630
a, so, a submodular function, Right? Where we have, we have…

530
00:47:00,450 --> 00:47:03,330
a set P of, poison…

531
00:47:03,610 --> 00:47:06,350
Poison elements, okay, that decrease the function.

532
00:47:06,700 --> 00:47:07,400
Okay.

533
00:47:07,790 --> 00:47:16,489
So… And the way we set it up is, if we put in all of the poisons.

534
00:47:18,240 --> 00:47:24,689
then we get the full removal of everything, okay? Right, so it looks
like,

535
00:47:25,330 --> 00:47:27,799
You know, if we've added in some good elements…

536
00:47:28,660 --> 00:47:31,520
Then as we add in poisons, they,

537
00:47:32,740 --> 00:47:34,350
If I get L of them…

538
00:47:35,090 --> 00:47:37,079
I decrease all the way down to zero.

539
00:47:38,220 --> 00:47:41,939
Great. And so the idea here is…

540
00:47:42,380 --> 00:47:45,939
You know, how poorly can we force the monitor?

541
00:47:46,710 --> 00:47:47,810
to respond.

542
00:47:48,980 --> 00:48:01,750
And so here's some results on that. So let's see… Yeah, so I think… the,

543
00:48:04,870 --> 00:48:11,570
So, with that construction, we can essentially show that we can get at
most R over K squared.

544
00:48:12,050 --> 00:48:13,919
The optimal value.

545
00:48:14,060 --> 00:48:15,990
With the monitor, okay.

546
00:48:16,870 --> 00:48:20,499
Which is worse than the monotone case.

547
00:48:21,940 --> 00:48:23,820
It's also just an upper bound.

548
00:48:24,290 --> 00:48:25,190
Okay.

549
00:48:25,420 --> 00:48:33,350
We haven't actually showed that we can get the R over K squared yet. So
that's still open here.

550
00:48:34,270 --> 00:48:38,220
So we do have an upper bound.

551
00:48:39,480 --> 00:48:43,200
So we know we can't get better than that.

552
00:48:43,690 --> 00:48:47,990
We still need the actual strategy to get the lower bound.

553
00:48:49,840 --> 00:48:50,620
Okay.

554
00:48:53,210 --> 00:48:57,230
Alright, I think, gonna go ahead and wrap it up here.

555
00:48:59,000 --> 00:49:01,520
So, Programming Assignment 5,

556
00:49:02,780 --> 00:49:09,640
if you recall, was, to reproduce the AI control monitoring, you know, so
a setup

557
00:49:10,440 --> 00:49:13,159
Reminiscent of the Greenblatt.

558
00:49:13,450 --> 00:49:15,700
Paper.

559
00:49:17,700 --> 00:49:24,969
Right, and so we threw in some submodular budget, tasks here as well.

560
00:49:25,600 --> 00:49:33,430
Right, so if we do have the independent setup, right, so, like, the
fallibility… Regime.

561
00:49:34,720 --> 00:49:38,789
Try to map the safety usefulness frontier, Task 3.

562
00:49:41,490 --> 00:49:47,390
Okay, so this is… but this one is actually pretty minimal in terms of
the API calls.

563
00:49:47,500 --> 00:49:51,710
Programming Assignment 4, as I mentioned,

564
00:49:52,420 --> 00:49:55,719
is quite more substantial on the API side.

565
00:49:57,790 --> 00:49:59,559
And here's just a mapping.

566
00:49:59,840 --> 00:50:05,680
of, of tasks of programming 5 to topics that we covered.

567
00:50:07,820 --> 00:50:15,580
Okay, so… Alright, I think I'm gonna go ahead and…

568
00:50:16,530 --> 00:50:25,760
stop for today. I will encourage you, so we have a few minutes left
here, to…

569
00:50:26,190 --> 00:50:30,170
Use this time to go ahead and do the course evaluation.

570
00:50:30,630 --> 00:50:36,850
So it's TAMU, I think APHIS, if you search… course evaluation…

571
00:50:37,650 --> 00:50:40,069
There might also be a link in Canvas.

572
00:50:41,150 --> 00:50:42,160
Say that again?

573
00:50:43,230 --> 00:50:47,369
Yeah, okay, so yeah, I think there's a link in Canvas that you can also
use.

574
00:50:47,710 --> 00:50:49,020
To pull it up.

575
00:50:49,620 --> 00:50:51,109
If you're having trouble.

576
00:50:52,130 --> 00:50:55,340
But, yeah.

577
00:50:55,550 --> 00:51:02,340
You know, this course has been evolving a lot. It started as an
algorithmic game theory course,

578
00:51:03,300 --> 00:51:08,130
So, definitely interested in your feedback on,

579
00:51:09,320 --> 00:51:14,080
The trajectory, where it should go, where… what would you like to see
more?

580
00:51:14,230 --> 00:51:17,840
of… How could I improve the course?

581
00:51:18,590 --> 00:51:23,970
Okay, so I will… I'll leave and give you the opportunity to do that.
