Latest / Strachey Lectures / Lovelace Lecture: Learning and Efficiency of Outcomes in Games

Transcript

Lovelace Lecture: Learning and Efficiency of Outcomes in Games · Strachey Lectures

0:01
Okay. Okay.
0:16
So I'm delighted to introduce Ava TARDIS, who's going to give this year's Lovelace Lecture.
0:22
Actually, I know that Ava is really well known to many people, and also she has so many contributions,
0:29
in her words, that if I read them all, it would take all of her time.
0:33
So I've made a small selection.
0:36
So Ava as well, she received the Fulkerson Prize in 1980, 1988 for funding minimum course circulations in strongly polynomial time.
0:48
And then in 2006, won the George Dancing Prize for for deep and wide ranging contributions to mathematical programming,
0:58
including the first strongly polynomial time algorithm for minimum cost flows.
1:03
Several other variants network flows, linear programming, sub modularity, circuit complexity, scheduling.
1:10
The list goes on.
1:12
She moved on from there to laying the foundations of algorithmic game theory, for which she was a recipient of the Journal Prize in 2012.
1:23
For her contribution was her paper with Tim Ruff Garden.
1:26
How about unselfish rooting?
1:28
And then there's a string of awards, a National Academy of Science fellow of the AMS, member of the Academy American Academy of Arts and Sciences.
1:38
And I noticed just today that it's this award upcoming in 2017.
1:44
So it's a real honour for us to hear about her contributions to game theory.
1:50
And I think she has a really unique take and combining that with learning.
1:54
So we're really looking forward to the lecture. Thanks. So. So thank you very much and thank you for the nice introduction.
2:09
And indeed, what I want to do today is thank you something about actually not just regular games, but games,
2:16
repeated games and then thinking about combining that is learning where I'm thinking of learning as a way to model some of the agents in these games.
2:27
So I guess the previous lecture where one where we heard a lot about how irrational human players are in games was an interesting introduction.
2:37
I'm proposing a more mathematical model of how people behave, not quite the classical model.
2:44
And I'll tell you a little bit more and maybe it's a good moment to try to defend that.
2:50
My rational model is applicable in many situations.
2:54
So for this talk my favourite application is writing, which apparently I pronounce differently than Leslie.
3:04
You can think of it as traffic, as in cars.
3:07
That is, people choosing a path to go to work in a car.
3:12
Or if you want, you can think about package writing that is internet package.
3:16
In most cases, the basic setup is that cars are driving and congestion slows down like the more cars are random,
3:27
more packets are around, the slower it gets to get to the destination.
3:31
From the decision makers perspective,
3:33
these two are actually a little bit different in the sense that in the packet case the decision makers are the writers.
3:41
So there is an algorithm behind decision making and maybe we can believe that algorithms are actually rational.
3:47
Someone quoted them up and presumably they coded them up to do the right thing,
3:52
whereas humans driving there might be other decision making processes and they might not be fully driving on the shortest path.
4:02
We'll come back to this in a little bit, but for now, you can think of it either way.
4:07
So traffic writing is a place where congestion causes delays, so therefore it's a game.
4:12
My driving going to pass might help me get someplace, but at the same time slow as everyone has done on the same bus.
4:20
As a stream or an idea in my research that I will potentially touch on at least one to mention it,
4:27
even if that's not going to be a full focus of the of the talk that sometimes in this situation,
4:35
Internet traffic, I think for sure, and even car traffic to some extent situation actually does change.
4:41
And these players in the game will repeatedly play the same game and not really facing the same situation, but something changes.
4:49
So in the Internet case, you know, something becomes popular.
4:52
Everyone's due to the website to download that content. It's hard for the Internet traffic people to know this ahead of time.
4:59
They don't. So they're going to have to adjust to the changing traffic and the same thing on traffic streams.
5:05
If you're very smart and you know where the football game is happening around the football game tends to end.
5:10
So therefore the traffic will be bad because people are coming out of the football game,
5:15
say maybe you can avoid it, but other people do not and they get stuck in the bad traffic and have to adjust.
5:22
So sometimes the situation changes and I'll come back to this in a little bit that how our Siri adjusts to this.
5:29
So here is our model of what I think of as a repeated game.
5:33
So there are a bunch of agents, maybe their end of them in every step and I'm going to think of discrete steps.
5:39
So in the morning, every morning you wake up and maybe drive to work.
5:43
I'm going to generally think of you take action i they t and you do this every day and then some something happens in everyday.
5:51
You figure out how many minutes it took to get to work. You might, you know, go around and every day something happens.
5:58
And but I'm going to assume that when you're rational,
6:02
you try to minimise the average time it takes to get your package to the right destination, which again assumes that they're somewhat rational.
6:11
And what players are doing is trying to learn from data.
6:15
So this is maybe a more clearly a model of of what the what the writers are trying to do.
6:21
They're trying to get the packets, the destination, and where is the information coming from that good data,
6:27
whereas they know how much the previous packets take over the peak time right now is,
6:32
or they know something about previous data and that's what they're trying to use as the information.
6:39
And what I'm going to ask, I guess in some way the talk will consist of two parts.
6:46
In the beginning I'm going to ask about the research direction I and many of us have been pursuing for
6:51
a number of years ask what can we say about the outcome of these games when the players are learners?
6:58
I'm going to make the assumption that the read assumption here that every player is trying to learn from past data.
7:04
And I'm going to ask, what can I say about what will happen in the game if everyone's trying to learn?
7:11
This led me to think about learning and led me to realise that in some way this online learning that I'm going to use is very well developed.
7:21
Siri But there are some other ways game theory gets me motivated to think about online learning questions or think
7:27
about understanding or like learning behaviour in a little bit differently than the online learning community will do.
7:34
And I'm going to give you a little bit of test on some recent work where we try to ask what what does not natural learning
7:43
behaviour tell you or what kind of algorithms can you say that that assured us that players are actually learning online?
7:53
The speed at which you're learning is, I'm sure, important for online learning.
7:57
This is a topic that gets started online learning,
8:00
but in particular it's very important for game theory because if I want to have a system where there's some transient behaviour,
8:08
where people stay in the system for a little bit and then vanish, if they're very,
8:12
very slow at learning, then, you know, for a little while they were in a system, they'd learned enough.
8:17
I can't say anything about their behaviour. In order to be able to say something,
8:21
I have to know they stayed in the system long enough to learn and in particular I have to know how long does it take to learn?
8:27
So I have to know some balance on how fast they learn to be able to say anything meaningful.
8:33
So that's what I would like to tell you a little bit about. So two very related are very intertwined parts.
8:41
So games probably I should start with maybe this is a computer science audience so I think or large part.
8:50
So I'm assuming that trying to tell you that learning is a reasonable behaviour
8:55
of what happens in an online setting maybe doesn't need so much defence,
9:00
but maybe it's still good to say that. Of course, if I go back to what classical game theory always did,
9:07
then the classical thing we all studied me included this Nash equilibrium and not learning outcomes.
9:13
So maybe the natural thing would be to say that a light on the study Nash equilibrium.
9:18
And I guess there are many good reasons not to, but one of them is that Nash equilibrium is hard to find.
9:25
And there are many reasons, many variations on the sense of what I mean by hard to find.
9:32
One of them is in order to find the Nash equilibrium,
9:37
I have to be very well informed of who else is in the system and what on earth might they wanna do,
9:42
which is an information, lack of information kind of argument.
9:46
And of course there is also the famous does go Clarke is a very powerful attribute to resolve that is computationally hard to find,
9:55
give others a sort of alternate pulse sort of leading the same conclusion.
9:59
NASH Equilibrium is a problematic model. To get the Nash equilibrium, you simply have to know too much.
10:05
And even if you knew a lot, it would be computationally hard.
10:09
But then I can also offer you a very empirical evidence.
10:14
Hey, I can look. That's not what's happening. And here is my empirical evidence.
10:19
If I want to have a repeat of game and the simplest model of what does it mean to be at Nash Equilibrium?
10:25
And indeed the very first studies understanding this kind of games was to assume that, you know,
10:32
the players might like try to do stuff and then they going to settle into a Nash equilibrium and then going to repeat the
10:39
very same action every single day because they figured out what's an equilibrium if they could ever figure out such a state.
10:47
Indeed, that state should be stable because if they ever were in a state.
10:51
But. Nash equilibrium means exactly this equation right down here in equality right here,
10:56
it says that they're doing something which has lower cost than anything else they could try to do.
11:02
So if they try something else, it's only going to be worse. The next day they're going to go back to the right thing.
11:07
So now it's actually very stable because it has this quality of it's usually referred to as a no regret inequality.
11:14
It's NASH because you're not regretting that you're not doing something else and it's stable because they find this Nash equilibrium.
11:23
But you look at any data and sure, life isn't this stable.
11:26
I can tell you whatever data you look at, the data that's easy to show you is actually not the main subject of this talk is action data.
11:34
And I guess I've been working this different kind of action data.
11:38
This one is coming from being or Microsoft advertisment data.
11:43
They're just not this stable. That's not what's happening. So there is a complex of the problem with Nash equilibrium.
11:50
There's an information theoretic problem, there's not enough information, and then there's an empirical problem.
11:55
It's just not happening. Now one way to look at what the Microsoft advertiser's doing and again,
12:03
these are people these are actually high advertisers that change their bid very, very frequently.
12:09
So frequently that they virtually certainly know they're not humans like they were just too often they just they just change all the time.
12:17
This has to be an algorithm that does this, not a human, I'm guessing.
12:23
With this kind of changes. I think what best models this behaviour is some sort of online optimisation algorithms.
12:30
This is what online optimal optimisation does. It does some form of gradient descent.
12:35
And this totally looks to me as a just first eyeballing it as a gradient descent algorithm.
12:41
So that's another evidence that maybe learning is a better model of what really happening in real life.
12:48
So here is what I'm going to do. I'm going to assume as a behavioural model that people are learning.
12:55
And what does it mean that they're learning?
12:57
So but the ones that really show up in the system say this is the beginning of this picture is day one for some user.
13:05
And maybe he's clueless. He's trying other stuff. He's doing wrong things.
13:09
But as time goes on, he gets better and maybe does something reasonable.
13:15
And then I guess I want to use an assumption that's very, very similar to the Nash equilibrium,
13:20
except it does not you use the stability that is they like to do every day something different.
13:28
No regret would mean that for every fixed action, whatever they did is lower cost than having done that fixed action with hindsight.
13:36
Okay. This is the no regrets condition.
13:38
What I really mean, of course, is not no regret because there was the initial experimentation where you could have easily made a few mistakes.
13:46
I mean, small regret. And it's usually referred to as no regret, as long as this error doesn't go linearly with time.
13:55
So for example, if having normalised the cost between zero and one, the biggest error you can accumulate is to at 90.
14:04
If regret grows roughly a zero to or something not quite linearly, then it's called no regret, which is your gut vanishes as time goes on.
14:14
This is a pretty standard sort of no regret algorithm.
14:21
So I'm going to actually spend at least one slide in.
14:25
I'm going to defend to you the no regrets assumption,
14:29
but maybe I should admit that actually like using a little bit different no regret the assumption which I actually
14:37
think at least the data shows matches human behaviour much better than the actual no regret the assumption.
14:43
Is an approximate version, so this must, in all regret, remember the cost.
14:49
That you experience for any version of youth or any player, II is less than the cost of anything sexual besides site plus some sort of error instead.
14:59
In a somewhat recent paper from last year at NIPS, we try to introduce that a better notion for game theory is this thing called approximate regret.
15:09
And what I'm doing is allowing you instead of a purely additive error and on something that algorithms,
15:16
people often like doing, especially since I for example came from approximation algorithm is an area is approximate error.
15:23
And what I'm doing is mixing that too. I'm giving you a even plus epsilon error that I'm allowing you to have a multiplicative error,
15:32
one plus Epsilon saying that most humans and even the systems missing some low bit of noise something like and for looking at empirical data say five,
15:42
10%. They're not very sensitive. They not optimised the last digit.
15:47
So this is modelling this would be an epsilon equals 1/10 120 has something like
15:52
that and the benefit is which going to really really pay off for us that if you
15:59
shooting for this sort of approximate regret to those things it models data better
16:04
so it seems like a better model of human behaviour and as you might notice,
16:09
the error went way down. So instead of something that grows this time, I have an error that doesn't grow this time so much, much faster.
16:19
This amount, this quality of learning is achievable much, much faster than the ultimate quality of learning that the classical learning algorithms do.
16:29
If you have studied online learning that you might realise this band that actually
16:34
what's new here is its use of using game theory rather than the band itself.
16:38
And I'll come back to this in the second half of the talk.
16:43
So my point is that this sort of rote regret algorithms actually achieved by the classical algorithms you might all know or many of you might know,
16:52
such as music without evade hedge regret matching almost all of the algorithms you might be aware of actually have this band.
17:00
So there is nothing new here. It just more. Maybe more suited for game theory.
17:05
So why do I say it's more suited for game theory? Again, two points.
17:09
One, I think it matches human behaviour better than the actual regatta algorithms.
17:14
But here is another one. I like game theory.
17:18
Thinking of game theory, I got into interested in learning because I wanted to study what I said in the title.
17:24
The Quality of outcomes in games. So what do I mean by quality of outcomes in games?
17:30
So the classical notion by. Elias and Christos Papadimitriou is that of price of energy.
17:39
And what price of energy does is defines the cost divided by some sort of magical, optimal cost of an equilibrium.
17:48
Elias, like all of us, was studying. Nash Equilibrium and not learning outcomes.
17:53
But this is the price of energy. You look at the cost of inertia, equilibrium divided by optimal cost, and that's called the price of energy.
18:03
Now, since I want to study learning outcomes, I wanna change this to a related concept sometimes called the price of total energy.
18:12
But I'm not so sure. I kind of like calling the war price of energy.
18:15
Sorry. Very sad. No, no, no. They were Nash equilibrium.
18:19
They were learning. So what does it mean that they're learning?
18:22
I make the assumption that everyone is a learner.
18:26
They are all running some sort of intricate algorithm. And what I'm measuring is the average cost divided by the optimum.
18:34
This equation I wrote assumes a stable population, so there are six fixed populations.
18:40
So the optimum is fixed. They're three durations, they're three times the optimum that could happen.
18:45
Or if I want to be more generous and this is a topic I slightly mentioned the beginning, but as I said, I will barely touch on it.
18:52
I can tell you dynamic population when I change the population over time and then I
18:57
have to make an even more sort of generous average the population of these learners.
19:03
That's the top and the bottom and the optimal, which of course also not changes because I change the population.
19:10
This is the natural analogue of the price of energy.
19:13
This is the kind of thing, some interest that they might want to prove that if everyone is a learner, that in many games these ratios stay very small.
19:22
Now, as you may or may not know, and I hope you have seen some of this, there are beautiful results out there that prove price of energy bans.
19:32
And. They often come with a framework championed by Team Wrap Garden, which is in some way a very natural, simple framework.
19:46
Here is what it, roughly speaking, does.
19:49
It says that if the game has this natural that he called smoothness property, then you can prove good price offender events.
19:57
Now let the smoothness properties stay.
19:59
I wrote the inequality technically down on the slide and I'll show you in a second that it actually shows something.
20:06
But let me say it in English first. So if you imagine any solution, any kind of outcome that is fair,
20:13
so is the vector of different actions that have horrendously high cost, you know, 100 times above the optimum.
20:22
Then what this was to say that a lot of these guys have a good action to take that improves the situation, and that's what the inequality says.
20:31
If the cost of the solution is incredibly high, you is a multiplier less than one.
20:37
Then the right hand side is now not quite this high.
20:43
Because move was less than one in the afternoon is noisier. Then one of the guys on average, someone has a good option to take.
20:51
This is very natural that this condition should obviously imply a price of energy.
20:57
But if the cost is very high, that's not much because someone wants to improve.
21:01
And indeed the proof is just as easy. If you are a Nash equilibrium, then everyone doesn't regret this other action.
21:08
They instead want to do. Whatever they were doing is in inequality.
21:12
All you do is rearrange the inequality and you get the cost is some bad.
21:17
So this is a for all you know, is very straight forward proof.
21:22
What's interesting about it is that almost all with very, very, very few exceptions, all the price of energy bands follow this framework.
21:33
For example, the original paper I had this team that got mentioned in the introduction about price of
21:41
energy and traffic writing had this framework or the extension for atomic or bigger traffic.
21:49
Writing also has this framework. And in many, many others, I guess these are the two that most relevant in in the kids.
21:56
They all follow this very, very simplistic framework.
21:59
One thing to keep in mind is the numbers we are getting here, we are proving price of energy, balance of a factor of two, factor of four.
22:08
So it's if you want to be generous, factor of two and a half even worse.
22:16
When I'm interested in this kind of puns, I don't much care.
22:20
But there's 2.5 or 2.6. That's noise.
22:24
Like, if either you're not at all interested in this because because these factors are not relevant.
22:30
Or if you are, if you give that, if I give you one more digit, you'll say, sure, whatever.
22:36
And if this is interesting at all, then the last digit doesn't matter anymore or else it's not interesting.
22:42
So this is the attitude I want to take to learning. I'm not interested in that precise optimisation because this is what I'm shooting for.
22:49
And here you either are not interested in this at all or you're not interested in the last digit of precision.
22:56
So that's the attitude I'm going to take. This framework has the beautiful advantage that it works very, very nicely.
23:03
Also, a learning outcomes almost identically. You don't have to change anything.
23:07
I never used in the proof back here, the stability.
23:11
What I'm using instead is the no regrets condition, which is exactly what learning outcome has.
23:18
If you want to adjust the proof of learning, that would say that if you learned, then you don't regret very much not having done something else.
23:27
You have a bit of regret or not horrible amount of regret that all.
23:31
If the game was smoothest, you can still finish the same inequality and you get a same sort of band.
23:37
One important thing to note is that the regret there are, of course, came into the band, entered the band.
23:43
Like if you have large regret that or then you actually not very big, very close to the optimum.
23:48
If you don't have logic at that or then if have no regret at all, then we can carry over the proof if you have logic later or you lost something.
23:56
So the regulator really matters. This is maybe the point.
24:00
They should come back to this speed of convergence resolved.
24:03
Remember, I wanted to use approximate regret. So I want to put in this epsilon as an extra bond.
24:10
If I do this and they do the same machinery, which I didn't put the algebra out on the slide, but I hope you believe me.
24:16
Exact same manipulation. I lost the epsilon and here is how I lose it.
24:21
I lose it. It's a multiplier.
24:24
We used to have a lambda over one minus fuel as our bond, and it's now one plus one plus epsilon times lambda and one minus something we do again.
24:34
A little bit of different, but not much. If I kept epsilon small enough.
24:38
This is noise. Very small change. But at the expense that I can push the additive very significantly that.
24:48
Okay. So this is sort of my basic introduction of what I wanted to tell you on, on, on games.
25:01
Before I go and talk about learning, there is a little segment I wanted to.
25:06
I'm sure it's many of your minds, even though no one is speaking up.
25:09
But I'm sure many of you were thinking, so how good a model is this learning?
25:13
Are people actually learning? So I want to show you two slides.
25:16
In asking whether this error is a is a good model of learning.
25:22
So I promise that a little bit of a discussion and I want to show you some data.
25:26
So. Again, the main assumption here is everyone's learning.
25:31
I.M. Cave is almost everyone's learning, of course.
25:34
That's almost as good. But are people learning at all?
25:38
Anyone learning? Is any people learning at all? And there are two couple of things that I can offer.
25:44
Learning is utterly doable. So it's both doable information only.
25:49
So no need for everyone to know who else is in the game.
25:53
You're learning from data. Data is available. You can learn it's doable.
25:59
And what's better if your opponent's doing badly?
26:03
You learn even better outcomes. You take advantage of badly playing.
26:06
Opponents learn. That's what learning does. I feels to me like people should be learning.
26:16
That is. All I'm asking them if there's a single strategy that's consistently really good, please make it up to it.
26:24
I don't know where, whether Oxford people live far enough for this to make sense, but if you take, for example, California,
26:30
where people drive long distances, if there is a highway on which in the morning there never is congestion, that's what I'm asking you to notice.
26:38
Please know this isn't driving it. It's a pretty reasonable assumption in many, many algorithms that actually capable of implementing this.
26:49
And the ideas of these algorithms are very, very natural try stuff.
26:53
You know, if something was very bad in the past, don't try it with very high probability that it's a bad idea.
26:58
Try stuff that has higher you know usually do the things that the natural probabilities.
27:05
Nonetheless, if I look at data, it's so-so.
27:08
So again, back to the Microsoft data and this paper is from Denison.
27:12
I can follow them wisely. Saucony is with Denison.
27:15
I can follow in Westchester Counties from S.E. 15. We again, we looked at Microsoft Azure data.
27:22
Microsoft editor has the problem that unlike Traffic,
27:25
I think I don't actually know what this guy's value is because that's not in the data, the behaviour is in the data.
27:31
But I have to do and that's the content of this paper is try to guess the value given their behaviour.
27:39
They're proposing that the best guess we can make is the value on which they regret would be as small as possible.
27:47
So when I show you slides of how much regret you have, this is a very optimistic slide.
27:53
If I guess they value wrong, they have regrets. Bigger than what I'm showing.
27:58
This is a smaller regret as they physically can get. So it says 30% of the participants have zero or negative regret.
28:07
So there is a value on which they're doing better than any single bit with hindsight.
28:12
So maybe they varying the bid in a clever way and they doing better than what I could have done.
28:18
Another about ten, ten, 10% or 20% of people have less than 10%.
28:24
Less than 10% regret the law and 50% of the participants have.
28:29
We have 10% or more regret that or in fact, these guys up here have an incredible amount of regret that are doing something really wrong.
28:39
And again, I don't guarantee to you that they have the value, right?
28:43
Especially not those guys, but I guarantee they have this much regret that or I am giving you an optimistic estimate of they regret that.
28:51
So this is a an assumption and may be interesting mathematically,
28:55
but I think there's a lot of research to be done in the direction of understanding better of what's really going on here.
29:01
And I guess for some of you, for when humans are making decisions,
29:05
then I talked to some of you about some ideas I have of the actually acquiring and understanding the data is a cost that's not in this models.
29:15
So the human work involved in figuring out the right thing to do.
29:20
Anyway. The models we are using. Maybe I'm going to skip this. So I have enough.
29:24
Sorry, I have enough for a little bit of talking about the second half I was hoping to talk about.
29:32
So what I try to tell you so far and again,
29:35
I admit I skipped one important segment is I try to talk to you that that that this learning is a human behaviour is a behaviour model.
29:45
It's mathematically very very nice.
29:47
It has exactly the Nash like inequality without the Nash stability assumption it matches data better than than than Nash equilibrium.
29:58
But I admit not at all perfectly. And it there very nice balance which I certainly didn't show it to you except for the framework.
30:09
Sometime you can put 2000 bands of the find that if everyone does or most people satisfied there's no regret learning properties.
30:16
Then the average delays in a network are pretty good, like within some small, constant times the optimum.
30:27
And again, it can be supported by a broad set of learning algorithms.
30:31
So maybe works as a behavioural assumption. So hopefully I convinced you that despite.
30:38
Interesting to study other behavioural assumptions. It's this learning is an interesting and good assumption.
30:44
But I would like to spend the second half of the talk on his recent work actually trying to understand the aspect of learning that I hid
30:52
under the rug till now and I want to recover it from the rug and tell you that this is an important issue and I should talk about it.
31:02
And that's upcoming joint work with Cactus Shootaround and Todos Liquors.
31:11
Feedback. So when I think of learning algorithms and most of the online learning literature,
31:17
much of it, especially the early online literature, was that way too.
31:21
I made the very unnatural and very uncalled for assumption that whenever you're
31:26
choosing a path to travel and God gives you feedback on all other facets.
31:32
Good luck. That is an alter ego of yours.
31:35
Also went on the other pass and you know you go and you took an hour to drive to work.
31:40
But you're actually aware that on this other pass it would have taken 35 minutes and the third pass it would have taken 10 minutes.
31:47
That's called the full information feedback. And in fact, much, much of the results I had on my slide were all full information, feedback.
31:55
You were choosing a strategy. You experienced the outcome of the strategy, but I fed you full information on everything else you could have done.
32:04
Now I'm not aware of many full information feedback setups.
32:08
So, for example, the traffic packets out there certainly don't know what happens on other parts that they're not trying.
32:14
That's not how it works.
32:16
When you're driving, maybe you get some information listening to news coverage of traffic delays, but not as good as the one you actually drove on.
32:23
So you're getting some partial information, not full information.
32:27
So one thing would be important to have, especially information feedback models.
32:32
That is, if I don't give you full information, can you recover some of the same things?
32:38
So for this segment of the talk, I'm going to hide the other people's behaviour in notation and instead of saying cost of your action acts,
32:47
it will be just cost the time t of x.
32:51
Those things are getting hidden. I hide person I because I'm focusing on one person's learning and I'm hiding the other people's behaviour
32:59
by simply allowing the cost to vary this time going very this time because of the other guy's behaviour.
33:04
But maybe this is a more compact notation and like a learning theorist, I would like to actually have costs normalise to zero and one.
33:14
And so you have to take the, you know how long it maximum take and normalise them and I assume you did this.
33:21
There are two parts to. I'm going to start by talking about what the classical not full information model, which is certainly simple.
33:32
You simply only get the information about the the action you selected.
33:36
But I also want to mention an extension, more technically difficult extension of what you're doing in a very,
33:43
very beautiful partial information feedback model that I really like.
33:46
Here is what it looks like. Every action here is a choice as a node.
33:51
So, for example, if you choose action X, that's in red. But actions are some are connected by your visibility.
33:57
If you choose an action X, then you also get feedback on its neighbours.
34:02
So there's a graph on the action space and you get partial information, which means you get information on some stuff and not on some other stuff.
34:10
So in this case you get information on the neighbours of know that it's a very,
34:15
very clean and I think elegant partial information feedback model that we are studying.
34:21
This is a current state of this line of research and I have many, many good questions to ask and I'm sure you will.
34:29
You'll do a good job asking me questions of, you know, other extension of partial information, not exactly your neighbours, but some other things.
34:38
There are many, many interesting questions here whether what we're doing extends to other forms of personal information, feedback.
34:46
So let's first tell you what's known.
34:48
And again, I know some of you know a lot about online learning and might the first slide or two here might be a little well-known territory.
34:56
But let me just remind you, in case and in case you don't remember, it's the fact that you don't get full information, feedback.
35:04
That's not news to the learning community. Here is the standard algorithm.
35:09
So the standard algorithm goes as follows. So remember, you're choosing an action.
35:13
You find its cost, but there's all these other actions and you have no idea what their costs are.
35:19
You didn't get feedback. So here is the proposed way of dealing with it.
35:24
It's called important sampling, and it's a very, very simple idea.
35:28
If you haven't seen it, this is not at all my result. But this should be your take home message because it's so simple.
35:34
What you should do is pretend that everything you haven't seen is as good as it can be.
35:40
Zero cost. It was ideal. You could have gotten there in no time.
35:45
But everything you did see. I will scale the cost up by dividing by the probability that I chose that action.
35:54
So I had that probability distribution of choosing things. This one, maybe I chose this probability 10%.
36:00
This one is probably the 1%. And what I'm going to do is if I don't see it, I pretend pretend it has zero.
36:07
But if I do see it, a scale of the cost is the probability.
36:11
Now. What's good in this? Well, it's good in this that for if I take any fixed action, it's expected cost is precisely right.
36:21
Nike, probably tippy it will have this ginormous cost computing contributing to the exact expectation.
36:28
Exactly the cost and probably three rested zero and doesn't contribute anything.
36:33
They expect that cost is precisely right. Yes, it increased the variance by an awful lot, but the expectation is exactly right.
36:43
Similarly, if I now imagine that I use these imagined cost, not my real cost, but the scale up costs, and I run a full information.
36:54
Learning algorithms and thinking these were this field of things were the real cost.
36:59
Then the cost of this full information algorithm will also be exactly right in expectation.
37:06
And this is a bit more complicated computation. If I choose the probability distribution P to choose among these this filter costs, then,
37:17
you know, you get this using linearity of expectation, you get that it's the expected.
37:23
Of course there are the expectation. The cost is exactly right.
37:26
Again, I increase the variance by a lot, but the expectation is exactly right.
37:33
So what I could do is run my full information algorithm on this apps and this is what the proposed method is.
37:39
Just run your full information on the apps. Well, almost.
37:43
There is a slide back here, which I referred to a bunch of times over.
37:47
Do they increase the variance? Remember in costs we liked normalising the cost to zero and one.
37:56
So we have to normalise because this dividing by the probability increases the numbers.
38:01
But what should I re normalise to? The probabilities could be as low as zero, and if they divide by zero, the number will get pretty damn big.
38:11
So at the moment I should be normalise them to be between zero and infinity.
38:15
Which isn't going to work for me. So here is what I view as a dirty trick of the trade.
38:21
Maybe not dirty a trick of the trade that learning theory used for years and years.
38:25
And I want to say, no, no, no, don't do that. And here is what they do.
38:29
Just put in a little bit of random noise.
38:32
Don't let the probabilities go down to zero, because then you are running things up to infinity and that's really painful.
38:40
Instead, put in a little bit of random noise, say don't let any probability go below gamma.
38:45
Gamma is a random noise. The rest, you're running this algorithm.
38:50
This works okay from the classical regress perspective.
38:54
And for some reason, I put the slide in the middle here.
38:57
But it doesn't work for my goal because that small probability that gamma that you put in the random noise you're choosing horrible pass.
39:06
Why are you doing that? Again.
39:10
I don't know if I know proper right numbers here. I know California thinks.
39:14
Well, if you know that one alone, it's horrendous. It's horrendous.
39:18
Every day, even with probably three gamma launchers, one on one, that seems stupid.
39:23
It guarantees that you have got that much a get because it's probably got you're choosing a horrendously bad bus.
39:30
Don't do that. It works for the regret, but it works for the cerebellum.
39:35
But it's obviously a bad idea. Probably people are not doing this and they shouldn't be doing this.
39:40
It looks like an altogether bad idea. So one question one should ask Is there a better model of learning that avoids this trick?
39:50
Ken I'm still going to use important sampling, but I want to avoid this trick.
39:56
They want to not put in random noise.
40:00
And what I'm proposing instead, I think, is an equally simple and much more realistic alternative of what I propose you should do instead.
40:11
So here is a very simple idea. What I should do is if something goes down below probability, gamma, whatever the parameter is, just don't do it.
40:24
Don't like small probabilities because I don't like dividing. Is that number.
40:27
Just don't do it. So that's called freezing. And what I do is temporarily freeze those options.
40:34
I discovered that driving on California Road one on one is really bad.
40:39
Just don't do it. Don't do it. Is probably the one in 100.
40:43
Don't do it with one in a thousand. Just don't do it.
40:47
Now what happens if it's called freezing and this is what technically I mean,
40:50
I'm going to change the probably to zero if it went below a cut-off I'm slightly
40:55
cheating and that cheating is that wiggle sign over there because once I did this,
41:00
the numbers don't seem to run anymore, so I have to scale them up a bit.
41:04
That's the wiggle. Not by much like I'm sure I.
41:07
This is one plus epsilon. This is where my one plus epsilon will come in.
41:12
I'm giving myself one plus epsilon error. So scaling probability is a little bit.
41:16
One third me. So I do this. That's called freezing.
41:20
And here is what I would like to do with this freezing.
41:24
So what does it mean? So let's go back to what the what we study, the important sampling.
41:30
So the first thing I see that, like I said in English, I forgot to show it to you.
41:35
I want to make sure that the total probability that I froze is not too much.
41:40
So when I scale up, I don't have to scale up by a lot. So first of all, if you look at any fixed action, what am I doing?
41:49
I used to have that the expected cost is exactly right and I don't have that anymore because I did this artificial freezing action.
41:57
So maybe it has a very high cost and I artificially never tried it.
42:02
And in those cases the cost is zero for sure, even though it should have been something big in expectation.
42:09
But this estimate of the cost, which is not not right, is what's called negatively biased.
42:16
It's guaranteed to be less than it should be because sometimes I zero it out when I
42:20
shouldn't zero it that so my cost that I estimate is lower than the actual cost.
42:26
That's good news because if I do well compared to this, I surely did well compared to the real thing.
42:33
So a benefit number so far. Second, and maybe that's the important part, the algorithm is not suffering.
42:41
The expected cost of the algorithm is exactly right.
42:46
Modulo that slight to the little over there, which is again the scaling up of one plus epsilon,
42:51
because I'm not playing the answer in which I'm cheating.
42:55
I'm only playing the relapse, the real arm.
42:58
So I'm not having an estimation problem. The real arms have the right probability and right scaling up.
43:03
There's nothing wrong there. So my expense of the operating expense I have.
43:08
Exactly right. Modulo one plus epsilon are various.
43:12
My estimate is what's called negatively biased. It's too low.
43:16
So if the algorithm does well against the estimate there, I'm all set.
43:20
So again, but I want is I can run the full information algorithm.
43:24
I now know that no costs will go above one over Gamma because I zeroed out any gamma probability.
43:30
So I solved the variance problem, I limited my variance.
43:33
These come up and I can run the algorithm. It's a very, very simple idea and indeed it carries these bands.
43:44
You get bands that I'm going to maybe show you in a minute,
43:47
but I think I want more you to take on the technique or the idea than the actual arithmetic of how much the bands come out for.
43:54
So all I wanna propose take the classical method, but instead of injecting noise,
43:58
just take it that take the opposite action, not play it rather than stop playing it.
44:06
Exact same cut off as they were you using with the noise.
44:09
Anything goes below the noise level. I just don't play it. That causes an error in my estimate, but error goes in the right direction.
44:16
It's a lower band, not an upper band. Good enough. Very simple idea.
44:21
Many, many benefits. Maybe. One is that I even like it as a sort of behavioural assumption.
44:28
If something is so unlikely to be good, people that tend not to be, do it, not to do it.
44:33
So I think this improves the behavioural match to this assumption.
44:37
It's a black box reduction. I didn't tell you what the algorithm underlying algorithm was.
44:42
You can take your favourite learning algorithm of which there are many, many of them and do this to it.
44:47
And it becomes a learning algorithm in the in the not so full information set up.
44:53
It recovers the smaller response and it has these benefits that it doesn't that it recovers these bands which have a no dependence on time
45:04
in the in the error band because the full information version had the property and I'm not doing anything that has information loss.
45:13
And the last one, which I guess is sort of would have been relevant from the slides I skipped,
45:18
but maybe worth mentioning if you're going to have to change your behaviour,
45:22
if in the middle of driving for many,
45:24
many months it discovers that something changed and this monologue used to be really bad, but now it's actually pretty good.
45:33
Your algorithm will recover because it's not driving any probability below gamma.
45:38
If you've ever been, you might stop there. You'd never go slower than that.
45:41
So it is actually good in a very V humanly since learning is good, but not all learning algorithms are good that it it adjusts to changing situation.
45:50
And this is the part of the slides I skipped so I won't spend so much time on it instead.
45:55
And the last thing I want to tell you is that it also works on partial information.
46:01
That's actually a more sophisticated version of feedback.
46:05
So let's go back to this partial feedback graph that I showed you a little bit before.
46:11
So remember the model here is that you not only get feedback on what you did, but you get some feedback on some of the other ones.
46:19
So a subset of the other ones like the neighbours. Now just to get you.
46:27
Clear or spaced on very small is if the graph is complete like every edge is in.
46:34
That's the full information feedback. Every time you do anything you see all the neighbours and that's all the notes.
46:39
The graph is empty, there's no edges. That's what's usually called the bandit or no or partial information or no information.
46:46
Feedback. You only get feedback on the action you chose.
46:48
No neighbours and this offers you something in between that there are some other kind of graphs.
46:56
What we are going to prove. And I'm going to give you a very, very short hint that this freezing technique is good for this tool.
47:03
Is that what I can do with this is replace the number of options, which is the size of the independent set of this guy.
47:14
And that I think is the relevant parameter here in the full information feedback built environment that has size one.
47:21
And indeed you see everything all the time. If there's no edges there, then you have not feedback.
47:27
And indeed the number of number of options, you kind of have to try them.
47:31
There's no way you can get the information without trying them all. But here, the independent set is a very, very natural model.
47:38
It's very natural band and in fact easy to see that the lower bands of this form,
47:43
because if there is an independent set where the good things are happening, those you kind of have to try.
47:49
They don't give feedback about each other, but it offers you a smooth trade-off between the full information and the partial information.
47:58
So what happens in a graph?
48:02
Again, I have to quickly remind you that the important thing, this important sampling, is that every time you see something,
48:11
you should update the cause dividing down with the probability that you saw it to correct for the fact that you don't always see this.
48:18
So what matters here is not how often you play who we are.
48:21
And what matters is how much you sit. That's the divider that you have to correct with the probability that I saw the arm.
48:29
So I'm going to care about how often I see the arm.
48:32
If I see it because of the is fine with me. Doesn't matter.
48:36
Oh, sorry. Wrong direction.
48:39
So what I want to do in my estimated cost is when I see no change, estimated cost as the cost, I see divided by the probability that I saw the item.
48:51
So in this estimation, I would like to freeze items that have low probability of being seen.
48:57
Very natural. Instead of low probability of being paid.
49:01
So I'm hoping that I can keep it.
49:04
Keep a cut-off for a low probability of being seen higher than one over the number of notes or epsilon over the number of notes.
49:12
Oh, sorry. I guess this is just saying that had I be able to do this, I can recover all the all the learning algorithms that we had before.
49:26
All I have to make sure that if I if I want to freeze all of the items that are not seen by sufficiently high probability,
49:34
they're not going to, you know, clean up the whole graph. So how large can I keep this cut of?
49:40
So I claim that I can use a band that's Epsilon over the number of independent said,
49:45
and the third probability I freeze is actually constant times epsilon.
49:52
So it comes in two parts, and maybe I'll give you a hint of what the parts are.
49:57
So first thing I'm going to do,
49:59
I look at my network and look at all the notes that are not seen with sufficiently big probabilities, say, these are the nodes here.
50:06
And I want to argue that the amount of probability I froze is less than epsilon.
50:12
If I use this epsilon over the independent set as my cut-off, this is a simple and maybe nice argument.
50:20
Say the black notes here, an independent set.
50:24
If I take a maximally independent said, then of course every note is visible from one of the independent set notes.
50:30
That's what was maximal about the independent set. So every note is connected to one of them and therefore it's seen from one of them.
50:38
And therefore the probability of just associated with being seeing the black notes is covers everything.
50:44
And that's the number of independence times, whatever the cut-off was oftentimes gamma, as I said.
50:51
This is nice, but unfortunately there is a technical difficulty, which I'm going to.
50:58
Admit that. Unfortunately, once I write these notes, some other notes will become not seen high enough.
51:04
So here is the picture.
51:06
I find that despite of notes, which is the bubble and now standing on its head less than probably the epsilon as we just agreed.
51:12
And fortunately, there are some new nodes that have not seen enough because they neighbours got frozen.
51:18
So I have to do this iteratively and as best as I understand,
51:21
if I do this iteratively with the same cut-off, I might unfortunately wipe out the whole graph.
51:26
But if I do it with a decreased cut-off and I'm proposing sort of the previous probability, then I can try to convince you that it will stop.
51:36
It will stop not doing anything worse than doubling my probability.
51:41
And here is a very sketchy long line argument for this.
51:45
So look at the next step here. Is this no day or this other notice that gets five that.
51:53
These nodes, these angels have the probability that a second ago they were seen by more than a gamma probability,
52:00
and now they're seen by less than two or more of our three. Oh.
52:05
How did that happen? That means two thirds Gamma is going towards the previous notes and only one third is going out.
52:14
So a large majority of every scene from I just like that.
52:18
This is sort of like a three structure, vibratory structure.
52:23
Twice as much done is up. And as you all know, binary trees have more notes on the site, on the on the leaves than in the centre.
52:30
That is my argument and I slightly cheated on the details, but that's basically the argument of why this is happening.
52:38
So at most, I bought another gum affection.
52:42
So I'm going to stop here and maybe give you a sort of high level picture of what I'm hoping you to come from the talk.
52:50
I in some way, I did two different things that I think are supporting each other and related to each other, but a little bit different.
53:00
So first of all, I hope I convinced you that learning is a reasonable model of games erratic behaviour, even though it's not 100% matching data.
53:08
And probably, you know, having just came after the previous talk where the main message was that behaviour, human behaviour is so irrational.
53:19
I'm not claiming that this is a, this is a better rational model of human behaviour.
53:24
It's not perfect. And I showed you even data where half, half of the participants don't even match this.
53:30
So one can do more in studying what's a good behaviour model?
53:34
But it has many advantages. It allows the players to adopt to opponents.
53:38
They don't need common prior. They take advantage of the commons by playing badly and the very,
53:44
very simple strategies and pretty natural straight strategies guarantee this any sort of certainly better matches
53:51
better than than Nash equilibrium assumption and one that's not on the slide but probably should have been.
53:57
It's beautifully usable in mathematical proofs it's such a nice condition you know and an narrower almost like the Nash condition,
54:06
it makes the error very explicit and it's very nicely usable in mathematical conditions.
54:12
But the second part I wanted to also talk about.
54:16
It even works on dynamic environment. Oops.
54:22
I don't know the second part. Okay, the second part, I still need to talk about that.
54:26
The which is the blue line here that when I started to do this,
54:33
I went find my colleagues who then more research on online algorithms and try to ask them for okay, okay, give me algorithms that do this.
54:41
But at some point I realised that my game theory perspective is a little bit different than the classical perspective,
54:48
and I think there is a lot more that can be done to understand how this all works or whether it works on partial information feedback.
54:56
So passion, information, feedback, there's a very nice and very developed theory of online learning.
55:02
But the attitude, the game, the the game series to take, take, take to this,
55:07
there was the form of personal information that I think is natural and might not be the same as what they think is natural.
55:13
And my absolute interest in not additive, but this sort of mix of multiplicative and additive error, that is the last digit optimisation.
55:23
Humans don't do a little bit of error review stay in, but the speed of learning really,
55:29
really matters both in how fast changing environments can be tolerate and also in, you know, how fast they they achieve reasonable social welfare.
55:41
So the price of energy kind of bends and for some reason these but called approximate no regret conditions or not,
55:50
that algorithms are much, much less developed in in the partial information setting than I wish it was.
55:57
And I tried to contribute myself to improve the situation.
56:01
So I'm going to stop here and thank you very much.