Bandits in auctions (& more)
Perchet, Vianney
In this talk, I will introduce the classical theory of multi-armed bandits, a field at the junction of statistics, optimization, game theory and machine learning, discuss the possible applications, and highlights the new perspectives and open questions that they propose We consider competitive capacity investment for a duopoly of two distinct producers. The producers are exposed to stochastically fluctuating costs and interact through aggregate supply. Capacity expansion is irreversible and modeled in terms of timing strategies characterized through threshold rules. Because the impact of changing costs on the producers is asymmetric, we are led to a nonzero-sum timing game describing the transitions among the discrete investment stages. Working in a continuous-time diffusion framework, we characterize and analyze the resulting Nash equilibrium and game values. Our analysis quantifies the dynamic competition effects and yields insight into dynamic preemption and over-investment in a general asymmetric setting. A case-study considering the impact of fluctuating emission costs on power producers investing in nuclear and coal-fired plants is also presented.
 Thanks for the invitation. It's always a pleasure to be here. And I'm going to speak with my friend Philippe Régault. He's a student, John Whid from MIT. So the thing is, I'm going to speak about two things, two main topics today, which are, as you can see in the title, Bandit. Another one is auction. So Bandit is a subfield of learning theory. And more specifically of reinforcement learning, the talk we saw yesterday evening. And the main idea is that you have someone, particularly in algorithms, that are going to take decision and get rewarded for this sequence of decision. And auction, well, I guess all of you know what auction is. So I will motivate our problem. And then I will show you some theory behind the multi-term Bandit thing and how we can apply it in a real life auction, real life problem, motivated by some stuff we do at Criteo. So it's not the right button. OK. So what are multi-term Bandits? So the original motivation of multi-term Bandits goes back to the 30s, when we wanted, where Thompson wanted to study how to do clinical trials, sequential clinical trials, and with some objectives. So what was his idea? He says, OK, let's say you are a pharmacist company and you have two treatments, either the red one or the blue one. And you want to find which one is the best one. OK, so you will hire a bunch of patients. And you want to decide whether it's the red or the blue one, which has the highest efficiency. So simplify, let's just say, when you give a treatment to someone, it's either cured or dead. So there's just, of course, a simplifying assumption, but just to give you some intuition. So if you want to do some basic statistics, you will say, OK, let's say you have 1,000 patients. You want to compute to do some inference. You want to know which one has the highest efficiency. The basic stuff to do is, well, I'm going to give the red pill to 500 of my patients and the blue pill to 500 of my patients. Then I will compute. I will see how many patients survived. And I will claim that the best treatment is the one that saves most of the people. So that's a very good answer. It works. It works really well. But the thing is, if, let's say, the red pill kills everybody and the blue pill saves everybody, if you do that, if you do this in a statistical perspective, you're just going to kill half of your patients. So indeed, you will know at the end that the blue pill is the best one, but you will have killed 500 people. And this is something we want to avoid when we're doing the clinical trials. So the idea of Thompson says, well, I'm not going to do clinical trials as it is right. I mean, we're using these ideas, these techniques. What I want to do is get a patient, give him a treatment, see if he survives or not. Based on this information, I will give another treatment to another patient and so on and so forth. And my idea is to find which one is the best one between the two treatments, the red one or the blue one. But at the same time, I want to save as many patients as possible, which here, what we call sometimes ethical. So that was during the 30s. And so we had some, well, this guy got quite famous for this. And then we had some theoretical study of that problem during the 50s by Robins, like in Robins. And then it's, so again, in the 80s and 90s, some work on bandits. And then it kind of declined. Nobody really cared about bandits. Until the beginning in 2000, where this idea of multi-impeded had a new application. And the thing is, it's not really about clinical trials. And the application is from an online auction, an online advertisement displaying. The thing is, when you go to a website, sometimes you have some ads on these websites. And oh, sorry about that. How do you, is this the phone? Yes. So when you go to a website, you have a banner with an ad on it. And if you are the user, click on the ad, then the guy that put the ad gets rewarded. So if you go to Le Monde, for instance, that website, to lemonde.fr. And if it displays, like simplifying, but if they say display an ad for Trois-Huist, if you click on Trois-Huist, then Le Monde gets paid. So here, it's kind of a similar thing that having a clinical trial. Le Monde has two options, the red one or the blue one. And it can give the red treatment or the blue treatment to the next user that arrives. And it will get paid if the red treatment is efficient, which means that if the user click on the ad. So here, same thing. We have two different ads to display, the red one or the blue one. Le Monde wants to know which one is the best one. And he wants to do it as quickly as possible because he wants to have as many clicks as possible because clicks are money. And that's the idea. That's the motivating idea of this talk. And this problem here of displaying the right ad on websites, actually a huge problem. Lots and lots of companies are working on it. You see why? Omni, actually. Because there is billions and billions of ad displayed every day. And so there is billions of billions of dollars involved with that problem. So it's a really important one. So let's look at it, how it actually really works. And because where the options arrive. So when you arrive on a website, and so here, it's a picture from Le Monde. From yesterday, I went to Le Monde yesterday. And I went twice on Le Monde. So I just refreshed Le Monde. So the first time, I got this ad here. So for Microsoft. I know it's tiny, but it's for Microsoft. And then I just refreshed my browser. And I got another ad for Air France. So of course, I got these ads because in the past, I browsed on the website of the Microsoft and on the websites of Le Monde, of Air France. So anyway, so I got these two ads. And here, I don't know if you know that, but if you look at those ads, can we see here, yeah, on the top right, you have a blue arrow over here and the same here. And if you click on it, you can see who sent you that ad. And here for the purpose of that talk, I did that. And you can see that if you click this ad here, this was sent to me by Criteo, my own company. While that ad here was sent to me by Rocketfuel, another company, a concurrent. So the question is, who gets to decide which ad I'm going to see? Why this ad is shown to me by Criteo? While it's here, Rocketfuel, that's an exact ad. And the process of deciding which company that our advertising gets to put an ad on the website is, well, it's an auction. It follows, it's as follows. So actually Le Monde, that's on Le Monde, is not choosing by himself the ad he wants to display. He's not choosing between Office and Air France. I guess, yeah, Air France, anyway. So what Le Monde does is, well, he has a bunch of clients, Criteo, Rocketfuel, and all other companies, and he contacts them directly or not, it's not really relevant. And he say, well, I have the Année Perche that arrived on my website, so you know him very well because he is not deleting his cookies, so you know him very well, you know what is boarding, and he's on my website. And I have a slot for an ad, typically in the right part of the Le Monde, so I have a slot for this ad. Who wants to put an ad here? And he says, so I'm running an auction, a second price auction, and who wants to put an ad here? How much do you value the fact that you can display an ad here for him? Criteo and Rocketfuel answer and say, okay, well, I don't know, maybe Criteo says here, said I'm willing to pay two cents for this opportunity, while Rocketfuel say, well, I'm willing to pay one cent, so Criteo wants that auction. And the display an ad. And what Criteo paid is what we call, so the second price, Criteo won the opportunity to display an ad for Microsoft or anything else, but he paid only the bid of Rocketfuel. Okay, so when you bid two cents, if you're in an auction, if you're opponent bid one cent, then you will pay one cent. You're not paying your own bid, you're paying the second bid, the second highest bid. Therefore, for some reason for that, I will explain them later on. So then let's say that Criteo won, he paid to Le Monde one cent, which was the bid of Rocketfuel, then he display an ad to me, which was for Microsoft, and then it's Criteo that is going to get paid by Microsoft if I click on the ad. If I don't click on the ad, Criteo is not going to get paid, and so he just wasted money by displaying an ad to me. And actually that's what happened, I did not click on that ad, so Criteo learned that I was not willing to click on the ad for Office or for Microsoft, and then when I refreshed my browser, there was another auction, so Le Monde said, well, Yanné Perche is here again, do you, how much do you value the fact that you can display an ad and so on and so forth? Criteo said, well, probably they say, okay, I displayed an ad to him two seconds ago, he didn't click, so now he's worth like zero to me, so they bid zero, Rocketfuel probably bid one, and they got the one cent, they got the win the auction, and they got the opportunity to display an ad. And that's all things works. I have to say that I had lots and lots of auctions every day, there's billions of auctions every day. So just to give you an idea of how many auctions we have there is in the world every day, just imagine that all those data, the data that are just sending by Le Monde saying, Viané wants, so we have an auction for Viané, and all those data gathered around the world, they cannot be stored, and even Google don't manage, don't know how to store that many data, okay, so it's not like big data, it's even way more than big data, I mean it's so big, you cannot store them, so you have to throw away the data, so because there's billions and billions every day of structure auction. Anyway, so now the problem of we had that hand is, well, Criteo here, he wants to bid, so he wants to bid what he said, he wants to put an optimal bid to the auction, so their difficulty for Criteo or Ketru is the same thing, is to learn how much they should bid, and that's the first thing, because they know me, they know I'm, sorry, I'm a perche, I have this boring history, so they know basically what I'm buying, where, when, but the thing is how much should they build to optimize their revenue, and this is the thing that, based on your data, the question is how can you learn the optimal strategy in those auctions, and then when they win that auction, there's another issue that arrives, because when Criteo just say, okay, I'm going to bid two cents for putting in that for Viannée, for me, the thing is, they don't have just one client, they don't have only Microsoft as a client, they also have like a CDS-KUNT or booking, so they can put in that for CDS-KUNT or booking or whatever, so here from the point of view of Criteo, once they want the auction, everything is not done, they still have to decide which ad to display, and how they're going to construct that ad, and so on and so forth, so lots and lots of decisions that must be taken by Criteo or any of their companies to learn the optimal behavior to adopt in this repeated interaction, and this is where, I mean, there's clear connection with reinforcement learning, as we saw in last talk yesterday, because you have repeated interaction, you take decision, based on decision, you get some reward with the guide click on that on your ad, and then you try to update your strategy, your policy based on what you saw in the past. Okay, so here, just to give you an intuition, to give you some ideas, if you click, still on those things here, you have lots of options, you can control the cookies that you are willing to, they can control your cookies, and you can decide, companies by companies, which cookies you're going to allow or not, and this is just the list of companies that are betting when your ad is displayed. So see again, this is a really huge market, I don't know how many of them there are, but you just, I mean, it's like probably 100 or so. So see, those are all the companies, we don't see it, but here is Criteo, so Criteo is over here, where you have Facebook, I guess, which is over here, you have Yahoo here, so all those companies, Rocket Fuel of course is around here, so you have all those companies that are betting at the same time, and it's a huge, huge, huge market. So let's, so that's what's the motivation for Bandit, another motivation for the Bandit theory is motivated by this, what we call spam filtering. So it has nothing to do with auctions, with ad displaying, it's another motivating example. So first one was clinical trial, second one was auction for displaying ads, the second one is spam filtering. So as you all know, when you receive an email, your spam filters decide whether it's a spam or not a spam. So it's the same thing, each time you receive an email, it takes a decision, and it gets rewarded by one, if it makes the right decision, and it gets rewarded by zero, if it makes the wrong decision. The right decision being, well, you classify correctly, the wrong decision being you misclassify your mail. And here's just a message, if you're already bored with my talk, which I mean, I'm okay with that. The thing is, so what do we call it, sometimes we don't know about this, what do we call it, spam. So just a thing is, like a spam, as you can see here, is actually a fake ham, that is sold in the UK and US. It's like a recomposed ham. And you cannot tell by the look of it, whether it's good or bad for you, okay? But actually, well, the fake ham is not that good, while the good ham is better, hopefully. And so this spam filtering is to distinguish between the good and the bad ham, okay? And this has been, so it was, that was a brand, and you have this sketch from the multi-peaton, and I don't remember, I think it's 79, where they are going to this restaurant and they are ordering stuff, and the food and they're asking the waiter what is on the menu, and everything is based on spam, so it's just the spamming, actually, the spam, spam, spam, spam, spam, spam, during the whole sketch. And this is why we are motioning a spam. And the name, I mean, that's where the name of spam mail that came, okay? So this is, at least, something you can bring back to home if you don't understand about learning, learning theory. So let's go back to bandit theory, how does that work? So to simplify things, we just look at the original setup where you have the clinical trials, you are, oh, sorry. You have two treatments, the red one and the blue one, and you're a company and you want to know whether the best one is the red one or the blue one. Each time a patient arrives, you can give him the red or the blue one, and he will die or survive depending on the efficiency of your treatment. So how does that come? So here, let's say you have a bunch of patients that arrive one after the other one, okay, a line of time, each one is a patient. So you have the first patient that arrives. You don't know anything about your treatment, let's say you give him the blue treatment. And you wait for quite a long maybe, or let's say it's instantaneous, and you see that the guy died. So based on this information, you know that first guy, you got him the blue treatment and he died. You have to take another decision. So maybe you want to try the red one. So, but you only have this information. So let's say you try the red one. You wait a bit, and you see that that guy survived. So now you have the third patient that arrives. Based on this information, you say maybe the red one is better than the blue one. So you try again the red one. Patients survive again. Okay, fourth one, okay, maybe the red one, and here you see someone died. So now you have two options. Maybe, maybe indeed the red one is the best one, or maybe it's the blue one and you are not lucky. Maybe you killed the patient, but that was just bad luck. You know in statistics, it's hard to make a statistic based on one sample. So here based on this, you say okay, clearly sometimes the patient with the red treatment dies, and sometimes the patient with the blue treatment dies. So in order to know which one is the best, I might have to sample more the blue patient, the blue treatment. So for the next guy, you're going to take blue and see that he survived, and so on and so forth. But here's a message of that slide, here you have a sequential treatment, okay, sequential, you take sequential decision, and you can only base your decision based on what you saw. Here you can just, you don't know if the patient would have survived if you have given him the red treatment. You don't know that, you have no idea. Same thing here, you don't know if that patient would have survived if you have given him the blue treatment. So you are basing your decision only on the thing you saw. And this is the difficulty of the bandit literature, is you're basing all your decision on what you saw and not on what you didn't know. It seems trivial like this, but I mean, this is really important actually. And the objective is, as I said, is to save as many patients as possible. So typically here, if you put zero for people that died and one to people that live, then you want to maximize the number of success, the number of ones you received. So that thing here, you can easily see that this could be an ad, okay, that could be the blue ad and the red ad. And being dead means that you don't have a click. Surviving means that you get a click and you want to maximize the number of click because a click is money. So let's look at, there is a bunch of literature on this, a bunch of ideas, and let's look at how it works. I mean a way to solve that problem, to have an algorithm which makes sense. So let's look at what we call stochastic mutambenit, which are data IID. So let's say that, so this thing is following, you have, as we have saw in yesterday's talk, you have K actions, each time you have K actions, so you have K treatment you can sample from, okay, you have the treatment red, the blue one, but you have also, I don't know, the green one. So let's say you have K treatment. And you want to sample sequentially from those treatments. And at stage T, when you have the patient T that arrives, you can give him one of those treatments. And if you give the patient T the treatment I, you will get as a reward XT of I. So we, I mean, I used to assume that X of Y was either 0 and 1, but this is just a simplifying assumption. I can assume that they are sub-Gaussian, or actually Gauchan, that's irrelevant. Okay, so being 0 and 1 just simplifies the talk. So let's say that XT of OI, IID, so that's an IID process, of expectation mu high. So mu high is the probability that a patient survived, or the probability that someone clicked on your add. So of course, if you know those parameters, if you knew mu high in advance, so if you know that the treatment red is better than the treatment blue, you will give the red treatment to everybody, for sure. Unless you are, I mean, anyway. So if you knew mu high in advance, you will give to anyone the best treatment. Here, the thing is you don't know this mu high. The question is how can you learn which one is the best one without sacrificing, without killing too many people, or without losing too much money? So to do that, you're going to build a policy, as I show in the slide, a policy is just based on what I see either to choose the action red or the action blue. So you want to build such a policy that maximizes your reward, the expected reward, as we saw yesterday. So you want to maximize your expected reward. So that's the kind of stuff you want to do. And the maximum reward is, I mean, in expectation is the sum of mu Pt, where Pt is the treatment you give to patient T. So here is an issue with that formulation here, is that, as you can see, those mu can hold be arbitrarily big or arbitrarily small. There's no constraint on mu, there's no prior on mu. Okay, we are in a non-parametric world. We have no assumption on mu at all, it can be anything. So the thing is, if you have an algorithm that gets a lot of money, okay, let's say that's your expected money. And you say, well, after stage T, I got T rows. So I have a very good algorithm because I got one T rows every day. Maybe it does not mean that your algorithm is really good. You get T rows, it just means that all those parameters mu i are really big. And maybe the smallest mu i is actually one. All of them are bigger than one, they are all equal to two, except one, which are equal to one. And you are really happy of getting T rows where you could have got two T rows. So it's not because that number is big that you are found a good algorithm. It's not because you have a lot of money that your algorithm is good because you could have got even more money. And same thing, if you have, let's say at stage C, you have almost no money at all, okay, you just have epsilon T. It doesn't mean that your algorithm is bad. Maybe all the other options were even worse. So having lots of money or higher reward doesn't mean that your algorithm is good. And the same way around, if your total reward is bad, it doesn't mean that your algorithm is bad. So we have to normalize that number. And there is two ways to normalize that number, depending if you're from the learning theory or from the learning theory community or from the CS community. And so I'm from learning theory, so I'm going to use what we call the really great. The one is the competitive ratio. So the great is, well, you look at what you got. Okay, that's an expectation of your expected reward. And as I told you, if you knew in advance all those mu i's here, you would have given to all your patients the best treatment. And so this is the number of patients you would have solved. The expected highest number of highest expected reward you would have got, how do you know all those parameters? So this is what we call the regret is the difference between those two numbers. And this is just, I mean, why we call it regret is just because it's, I mean, the literal translation, literal sense, it's just the difference between what you could have got and what you got. Because just what I could have got, I had I known all those parameters, minus what I got. And now we are focusing on that notion of regret and we want to minimize this thing. We want to have a regret which is as small as possible. Yeah. Would you guess the other criterion? Yeah, sure. So let's, other criterion is instead of having this, this additive normalization, okay, where you're subscribed from your, from your, well, you're subscribed to the maximum your reward. The other one, which is the competitive ratio is just you divide, okay. And here, what you really want this to be as small as possible. And the other one, the competitive ratio is when you divide your, your, your, your cumulative pay reward by the optimal one, the maximum one. And you want this to be as close to one as possible. Okay. So this is called a competitive ratio. And yeah, I mean, there are some connections between them, but let's not enter into too many days. So this, this regret, as you can see, I can rewrite it using this formula, this formulation here. Well, I'm going to introduce a parameter delta i, which is just the cost of making a mistake. So the cost of making a mistake is, is just, oh, sorry. It's just the difference between the efficiency of the best treatment and the efficiency of treatment, if you, of the treatment i, okay. Delta i is the cost of prescribing treatment i instead of prescribing treatment star, the best one. So that thing, obviously, as you can see, can, the regret can only increase this time because that, that, that parameter here is positive. And those, those things are also positive. So you have the sum of positive numbers, we can only increase. In the worst case, of course, it will increase linearly. So the question is, can we find an algorithm which regrets we're going to increase because we have no choice. It has to increase. Okay, so increasing sum of positive numbers. But increase slowly, sublinearly, in the square root of t, or even in the log t, or even in constant. How can we do that? That's the question. And the answer is, well, the following. The most famous algorithm that does that. So here I'm going to say this is, I'm going to focus in non-athletic bounds. So I want precise, non-athletic, efficient bounds. There have been algorithms before that. But here, all those results are really precise in terms that you control everything. Okay, all those, all those, those inequality are really precise and are non-athletic. And while I'm here, this symbol here, smaller or equal than with a tilde below it, just means that I'm eating a constant. And a constant in my, in my community, a constant is a constant. A constant is two, okay? If you have like a k, k is not a constant, okay, it's a parameter. Or if you have, I don't know what do I have here. Delta, delta is not a constant. It doesn't change with time, but still it's not a constant. It's a parameter. Okay, a constant is two, it's pi, it's one million. Okay, I don't care. So maybe here, I've eaten one million or two. I'm not going to tell you. But that's what we call constant, universal constant. Okay, it's not a parameter. So there is this algorithm which is widely famous. It's called UCB for upper confidence bound. So the idea is the following. So I want to prescribe to my patient the best, the best treatment, the one which has the highest efficiency. Of course, so highest efficiency is the one with the highest mean. A very good proxy for finding, for computing the mean of a random process is to look at its empirical mean. But here there is something which is really interesting in online learning is that everything you know about statistics is incorrect. If you look at that thing here, the empirical average, and if you look at the expectation of that guy here, the expectation of the empirical average, well, you want to say that the expectation of the empirical average is equal to mu i. Okay, you want to say that. Because that's the first thing you learn in statistics. When you have a process, the expectation of that process is equal to its mean. By definition actually. But here it's incorrect. The expectation of the empirical average does not necessarily converge to the expectation, to its true expectation. Why, why is that? Why is that true? It's simply because, I mean, when you have the empirical average will converge to the true average, when the data you get are just received as is. So you say, okay, I have 1,000 data that are iid, and the expectation of those guys, of the empirical average on those 1,000 data are in, I mean, of course the expectation is mu i. But here those data are not iid. Because you choose to sample from the process i based on the previous data you received. So typically if in the past, the process i was really bad, bad behavior, when you're going to sample it less and less. So at the end, it might be the case that the expected empirical average does not converge to the true average. It's possible. So you have to be really careful. Stated otherwise, that guy here, the empirical average, is biased. It's a bias estimator of the true mean. So those are, so if you based your policy on a non-biased estimator, well of course your policy is going to diverge. You might not converge to the best one because you're looking at a bias estimator. So you want some hope to unbiased it, or to control the variance. And the way to do that is to add some error term, which is this one. So it's quite a lot of two log t divided by the number of samples you have. And this is called hyper-coffe-dazmone because it's linked to everything in the quality. I don't know if you know it. I mean, otherwise it's not really important. And the thing is that mu high is going to be really close to that guy of the empirical average plus the error term in the orange. But not necessarily close to the empirical average. So this guy here is a very good proxy for what the empirical mean could be. It's still biased, but it's less biased, yeah. So this correction is the limitless for x, the real one, and bounded by one. So here, this correction is indeed when x is bounded by one, or when there are sub-gauchan with a parameter one fourth, which is more or less equivalent to being bounded by one. Exactly. So if you know the variance of your parameter, sorry, this is one, but if you have a variance sigma square, you can have a bond here that involves sigma square. You're going to put sigma square over two. And if you don't know that variance, you can estimate it online and put here based on everything in equality. And if you're going to use an estimate of the variance, and you're going to use Bernstein inequality instead, and so you get sigma hat here. Okay? But here typically is just, this idea is just saying, well, with very high probability, actually with probability one over t to the fourth, new i is going to be smaller than that thing. Okay? Just to note, the fact that you have nothing, a thing bound is just because we made this assumption. If you have another type of process, you could make any per-competence bound here. As long as you have, all the results I'm going to say, are going to be true if you have exponential convergence. And so if you look, if you take this algorithm, if we call it UCB, well, you can show that your reglet is going to scale, is going to increase, of course, because it has to increase. But not that quickly. Actually, the reglet is not going to be linear, it's just going to be logarithmic. So your reglet is just going to increase as log t over the delta k, the sum of log t over delta k, which is, of course, much slower than t. So it means that if you compare, if you look at, let's say you are in a clinical field, if you could have saved all the patients, t, and you want to find out which one is the best one, you will just lose log t patients in the process, which is not that big. And if you look at this type of bond, here it depends on delta. So you might say, yeah, I want to have uniform guarantees over all the possible delta, all the possible cost of action, all the possible parameters. And if you take the maximum of that thing here, well, it more or less sums up to find this equation, and you can show that your reglet is bounded as a square root of kt log t. Of course, because here if delta goes to zero, this goes to infinity, but it's always going to be smaller than the square root of kt log t. So in any case, your reglet is going to increase as much as the square root of t, which is way smaller than t. And if your parameters are nice enough, then it will increase as log t. So that has been, so it's prepared, that's in 2002, so it's 15 years ago. And after that, there is lots and lots and dozens of different, even underwrites and thousands of papers and bandits following this trend, this trend of ideas. So the question I might ask is why, because it looks pretty simple. Actually, it is pretty simple. And you should just look at the proof. The proof is, I mean, it's two lines, so I'm just going to do it. Well, I'm going to lie in the middle, but still. So if you don't lie, it's like four lines. So let's look at the proof or just to give you some intuition. So we're going to look at our algorithm. The algorithm is going to sample, to prescribe the treatment i, which is not the best one. Under which condition? Well, based on this idea, it means that the score of our treatment i is bigger than the score of the best treatment. So it just means that the score of the treatment i, which is the empirical mean plus the error term, is bigger than the score of the best one plus its error term. I know if you just take that guy here and say, well, okay, here is where I'm lying, but actually I'm not lying. The empirical average is almost equal to mu star, and that guy is almost equal to mu high. So if I take that guy on the right part, I will get delta high. If I take that guy here, I'll get delta high. This one is bigger than one, so I can just remove it, and that one is going to be here. So I'm going to sample from i, more or less, when delta i is going to be smaller than that error from the error term. And just give me, if you invert this equation, the number of times you sample from process i increase as log t over delta i square. Okay, and this is the main idea of the proof. And then everything is like to line. And you can show that this is actually optimal. You cannot do better than this. In some sense, I'm not going to enter into this detail. But here's the idea of that algorithm and why I do like Bandit, because you can see the sitting is quite simple to explain. Okay, you have several processes for treatment. You want to give one to the other one. So you can make any other assumption, say, okay, what if we say, assume that this is possible, this is not possible, or whatever. And the proof are basically not that difficult. The most difficult thing is to find the right algorithm. Okay, to have the good idea. It's not like taking a mathematical hammer and hammering your equation until you, at the end, you get something which looks nice. Okay, it's just having a good intuition, which is, I mean, I think it's nice. So there are lots of algorithms that improve the right software, I've done some hope, I'm not going to enter into the detail. If you're interested, well, can you look at the slides that are going to be on mine. So here, I assume the data were IID. But in real life, for instance, if you look at your spam data, the mail you receive are not IID. Why is that? Because if you think again about the spam filter. So let's say you're building your spam filter. And there is an example about this. So you're building your spam filter. And what you're going to receive. So you receive an email. So the first, I guess the first spam was on Viagra. So you receive email saying Viagra. And it's quite easy to understand that when you have Viagra written in full letters in your mail, then this is spam. So the first spam filter say, well, if Viagra is here, then it's going to be a spam. But then the spam standard, people that are trying to sell Viagra, figure out that if they put Viagra in the, I should not say Viagra when I'm recorded. I should find a better example. And let's, anyway, it's too late now. So yeah, those guys figure out that you don't want to put Viagra in your mail. So just put v.ive.a.g.l.a. And then the spam filter say, well, this modified the distribution of data you receive. Because before you never saw this kind of string of letters with the point. And then, so it means that the data adapted itself to your own algorithm. Okay, so the data are not IID, they are adapting to your algorithm. You have, you make a decision and the data are adapt to that decision. And then same thing. So the spam filter say, well, v.i.etc is a spam. And it gets this spam. So it say, okay, I'm going to change my algorithm. Say this is not a spam. And then the spam standard say, okay, no, we have to change things. So just put lits, lits, lits, you know, you replace i by one and so on and so forth. And then you have this game between spam standard and spam filters where each one of them is adapting to their own strategy. So at the end we have, when you were looking at this multi-term bandit, you still have your action. So, okay, so you still have k action, one to k. But the thing is your process XIT are no longer IID. Because XT plus one, the law of XT plus one depends on how the past. So you cannot just say, you cannot use the last tool which are based on empirical process and only on the study of stochastic empirical processes. So you have to be more clever. The rate is defined as usual. You say, okay, I'm going to look at stage T. I'm going to look at what was the best decision, constant decision up to that stage. And you compare this, I mean, this is the amount of money of people you will have saved, how you were given to all of them with the treatment i. And you compare this to what you got. And this you want to minimize. This is closely related to convex optimization. So here you have, it's more or less convex optimization. So you can use tricks for convex optimization. I'm not going to enter into these details, but you have to mix, to use random strategy. As we saw before, you want to build unbiased estimator and so on and so forth. You can do that. So that's what we saw yesterday. We mentioned that estimator yesterday. It's important sampling estimator. So you have techniques to do that. But the main message is the last one. So if you're using this kind of algorithm, then you can show that no matter what the sequence of action is, okay? So the data you receive can be generated by an adversary, by another algorithm that is trying to screw you. Okay, so you're adding a spam filter. So you're trying to build a spam filter. And the spam standard are adapting to your algorithm, to your own algorithm. And no matter what your adversary is, no matter how strong it is, you regret is not going to increase linearly. You can find an algorithm so that you regret only increase a square root of t times K log k. So this is the very, actually, at first time when you think about it, it's kind of weird because you made no assumption at all on the process XTI, no assumption at all. And still you manage to learn which one is the best one without any assumption. And everything can change from one stage to another one. So it's kind of, it's not that easy to understand why it's working actually. If you think about it, you have no assumption on the data and you want to do as well as the best strategy, but still it's possible. And the idea, just in a few words, is actually just to compensate your losses. Okay, if at some time you have some losses compared to action one and you have some gains, so you perform better than action two, then you can compensate the surplus you get from action two to action one. So just a matter of compensating your loss and gains. But this is the idea, at the end, the thing is you regret only scale as square root of t. Which was the same, it was exactly, this was, except for the long part, but this was exactly the rates of the rate of error of the optimal rates of error in the stochastic case. So this means, actually, that if you look at it at this last line here, it means that the adversarial world, when you make no assumption at all on all the data you can receive and the data can even adapt to your own algorithm, this world is not more difficult than the worst stochastic case. Okay, so that was a 30 minutes course on Bandit. Okay, all you need to know about Bandit theory. So I'll just save you like 20 hours of my M2 courses. So let's go back to action. So remember, we have this problem here. How can we use this idea of Bandit in our auction problem? So we have, I mean, yeah, so we have this auction. So Le Monde is offering a slot to Creteau or Rocketfuel to put an ad on my webpage. And the question is from, the auction is second price. And the question is how can Creteau and Rocketfuel learn what they should be? So, the first question you might ask is, what is that second price auction? How come when you bid something, you're paying the second highest price? And the thing is, so there's this auction, we call it sometimes V-Cray auction, it has a really interesting mechanism, auction mechanism, because what we call it's truthful. And actually V-Cray, which in what you did, got a Nobel Prize for that. So let's say what the second price auction was. So you have a good, that is sell on auction. So it's either an ad like this, but it can also be, I don't know, like a boat or whatever. Or a painting. So each buyer is going to, so he has his price evaluation, so by your eye, things that for him, the good is worth V-high, that's his valuation, and he puts a bid V-high, okay? So that's a secret auction, closed auction, so he's only one, so just say, okay, I'm willing to pay, that's how much of money for, I'm willing to bid, that's how much of money for that ad or for that boat. And I think so, you gather all your bids, and the thing is, so you're going to look, the winner of the auction is going to be the guy with the highest bid, as I said before, which makes sense. Okay, because he's the one which wants the good the most. So the winner is B, so B-sharp, no, B-sharp is the one you're going to pay. So the winner is the guy with the highest bid, and he's going to pay the second highest bid. He's not going to pay his bid, he's going to pay the second highest bid, B-sharp. So why are we using this mechanism? It's because, as I said before, it's truthful. It means that your optimal strategy, no matter what your opponents are doing, no matter what you think they're doing, no matter what their valuation are, no matter what anything, your optimal action, you have nothing better to do than bidding your own valuation. Okay, if you think this boat is worth $100,000, then you bid $100,000. If you think that this auction is worth one cent, you bid one cent, and nothing more, nothing less. You cannot try to be a smarter, ever less and bid just a bit lower or a bit above to maximize your revenue, it makes no sense, for the following reason. So your utility, so what you gain, you're expecting gain is just, well, if you win the auction, if you don't win the auction, you get zero. Okay, you had zero before, you had zero at the end. So your utility is, if you win that auction, so if your bid is bigger than the second highest bid, you get V high minus the second highest bid. So now let's say you want to be a smart ass, and say, well, I'm going to bid more than my valuation. Okay, my bid is going to be bigger than my valuation. What might happen? Well, you might win the auction. Okay, V high might be bigger than V sharp. But if V sharp is bigger than V high, at the end you're going to pay more, you're going to pay something, you're going to pay more than the valuation of your good. So you're going to get a negative revenue. Well, if you had bid only V high, your revenue is always going to be, your revenue is always going to be positive. Okay, or equal to zero. Because V high is V high, so you're only going to pay something when V sharp is smaller than V high. So if you're trying to overbid, the only thing that could happen is, you will not have one detection with your bidding V high, your valuation, so you want the action, but you pay more than what is worth. So you don't want to overbid. And if you bid, oh, there should be a smaller, smaller than, if you bid smaller than your valuation, if you say, okay, I'm going to try to save some money, what might happen is just going to, you're going to lose that auction. And actually, if you think about it, since you pay the second highest price, the amount of money, if you win the auction, conditionally to the fact that you won the auction, the amount of money you're going to pay is independent of your bids. So the only thing that might happen is, instead of winning an auction and making a small surplus, you're going to lose that auction. So the optimal strategy is, it's always to bid your valuation. So in this, hard displaying, if you want to display an ad, the optimal strategy is, typically, to bid the probability that someone click on your ad. So you're trying to learn what is the probability that, so Crito is trying to learn what is the probability that I have on clicking on their ad. Okay, because if they knew that, if they knew that my probability is P, then they should bid P. So this, another guy got another, I mean, my son got another Nobel Prize because he improved the mechanism by allowing the seller to have a reserve price, which means that nothing is sold if there's no bid below the reserve price. And when it's sold, it's at least a reserve price, but that's a bit irrelevant. So let's look at our learning model. So, and we're going to place ourselves in the shoes of Crito or Rocketjoule. So we want to learn what is the probability that I have to click on the ad. Okay, they want to learn what is the probability that me or you, guys, is going to click on one ad. And to do that, well, they need some data. So they need to buy some data to learn what is the probability of clicking. So there's two ways to buy data. I thought you just say, okay, well, I'm going to buy 1,000 ad and look at what it is, as we said before, and then you just compute the array. Or you can do it in a more clever way. And let's look at the model. So we have several rounds, so that's all the actions. So we have action one because I arrive on Le Monde the first time, then the second time, the third time, so on and so forth, like T times. So they know that I'm going to be here for T times. Okay, I'm going to click on Le Monde, I don't know, like once a day, so like three times a day, so there is at least 1,000 options. Okay, so we know that, let's say we're going to fix T to be 1,000. So that's the number of ads that can be displayed and it's sequentially. Okay, so when ads T arrived, then each bidder, so each one of the companies we have seen before, so the Criteo, Rocketshul, Google, Yahoo, and many more, can place bid, BT, between zero and one. Okay, because that's typically the probability, they assume this is the probability of clicking. Okay? So if, so we are Criteo, okay, we are in a shoes on one of those companies, let's say we are Criteo. If BT, if our bid is bigger than the highest bid of our opponent, it means that we have the highest bid, then we win this auction. Okay? And what we paid is empty. And we get to observe, let's say a click. So you get to observe BT, the value, which is zero and one, can be even zero, it's either zero or one. Okay, let's say that BT is either zero or one, to simplify stuff. So at the end, our total utility that we got during this process is, well, we saw move all the action, so you look at all the action you have won, when our bid was the biggest one, our bid was bigger than the second highest one. And what we got is BT, so it's zero or one, depending if there has been a click, minus what we paid. That's our utility, and that's the thing we want to maximize. So I'm not going to do this pitch again, that this thing can be arbitrarily high or arbitrarily small, depending on your algorithm is good or bad, so we're just going to look at the regret to normalize that thing. So that in orange is the total amount of money we made. And in black here, it's the maximum amount of money we could have made had we always bid the same B. Okay, if we made a B, then we will have done that, that option if B is bigger than your second highest bid, and this is the money we will have made, BT minus empty. And we maximize this over B. And our regret is going to be the difference between those guys. So from here, I made no assumption on what's empty and BT are, whether they are stochastic, SIR or whatever, or those data are generated. So typically, BT is the value of a good, is the probability that I have to click on one ad. So typically, I mean, BT is whether it will click on the ad or not, and typically, these are stochastic. Okay, we can assume that the probability that I have on clicking on the ad won't change each day. Well, if I have, it's not true, but let's say it is. So that's the first option we can make. Okay, we can assume that the probability that I have to click on the ad is stationary, it's independent of time. And so the value of an ad for a criteria, which is BT, which is 0 and 1, whether I click or not, this is an idea process. Here comes the other part, empty, the second highest bid of my opponent. I can assume that this is stochastic, which means that my opponents are always going to bid the same thing. I mean, the bid is going to be constant with time. Actually, this is true. This is an assumption which makes sense, because when you look at it, when you look at data, it's almost true. So I have lots of anecdotes I want to share with you, but I don't have time, so if you are interested in this kind of stuff, go ask me at lunch. All you have to say is, well, I can assume that empty is not going to be stochastic, because our opponents are going to adapt to our behavior and so on and so forth. So empty can be anything, and I will be able to adapt to any sequence of bids. So that's a pretty cool adversarial. Okay, what's the second idea as in spam filtering. Anyway, in that case here, if you look at your, oops, if you look at the definition of regret, when you maximize that thing with b, and empty is independent on vt, which makes sense, the optimal is always attained when b is taken equal to v, your expected value. Okay, so the regret revised as this. Okay, that difference in black, you should have bet at each time v, and you bet inside bt, and this is your regret. The difference between what you could have got at most minus what you got. The other thing we could look at is the adversarial I'm not going to speak about it today, but you have slides so you can just look at it online, and it's when you make no assumption at all on vt either. So what are we going to do in a stochastic case? Well, as a algorithm we're going to use, it is based on UCB, it's a variant of UCB, that we call UCBid, because it's bidding on an upper confidence bond. And the thing is, our bid, we would like to bid the value v, but we know, so if you look at the empirical average of success, we know that that guy is biased. Okay, I told you that this is the bias estimate of v. So as before, we're going to add an error term, so that this is still biased, okay, but it's less biased. And so a negative, the number of auctions we want up to now, and this is what we're going to bid. And if we do more or less the same proof, where it's way more difficult because it's continuous, we have a continuous action and things are more difficult, we can prove using the same ideas that the regret is going to increase logarithmically in log t over delta. So the question is what is delta? Delta is the smallest interval between v and, so it's an interval between v and the smallest bid of open-end, which is above v. Okay, so it means that we have no bids between v and v plus delta. Of course, the thing, we don't know it. We don't know v and we don't know delta in advance. And if delta is, so if your open-end is nice enough, then your regret is going to scale on illogatmically. But delta can be as close to zero as it wants, if it doesn't want to be nice. And this thing can also prove that it's never going to be bigger than the square root of t. So we have an algorithm such that it behaves as so you can learn the optimal value of, you can learn the value of a, of a, and it can bid this value almost optimally. The only thing it's going to lose is square root of t, the factor of square root of t, which is, which is admissible. And if your open-end is nice, nice enough, then it's log t over delta. So I think delta, I said it can be small, but if our open-end is like playing stochastic, maybe the probability that that bid fall in that interval is going to be really small. And we can control this using some margin condition. So I'm going to spare you the details, but we can interpolate between, we can have some continuous interpolation depending on the strength or the badness or opponent between the slope t and the square root of t. Okay, there is this parameter, alpha, that interpolates between those two. How much time do we have? Like it's over? Okay, I only have one minute. Perfect. So that was the take-home message from the slide, is that we can interpolate between this fast rate of log delta and the rate of square root of t. Now, as I said, we also have another algorithm for when the data are, we made no assumption of the data in the adversarial case. I'm not going to describe it. And same thing, we get a rate of adjunct in square root of t. And all the results are, I see the constant are exact, here it's a four. And they are all more or less optimal up to log term because we can show that you cannot build an algorithm which is better than this. Okay, there are always a way to screw any other algorithm. That's the summary of our results. So let's remember we had a whole this multi-ambient theory that is 15 years old now. And we adapted it to these sequential auctions. And thing is, so our action space is no longer finite, but in finite, it continues between 0 and 1. And we still got to manage to get rates of adjuncts as scale as square root of log t, as log t or square root of log t, which was quite surprising actually. And even if you look more in detail into those bones, if you're used to them, you can see that there's some really, really interesting stuff going around. So I'm not going to speak about this because I don't have time. Same thing, it's online. But I would just to say that this is, I find this very interesting. Maybe for you it's just quite interesting. Anyway, all goes, all takes our nature. But can we use them, I mean, as it is in real life, so question, the answer is obviously no because there's many, many issues. Here we made lots of assumptions that are not satisfied in real life. So there's lots and lots of works to do before we can apply directly those ideas into the real life problem. And of course, if you are interested into doing that, well, please come see me and we can discuss all of these issues. And they are described after, I mean, there is a bunch of remaining slides here, but it's just for online. So I just want to finish that talk with two announcements. There is 10 hour lectures by Tim Hofgarden from Sanford on auction, data driven optimal auction. So this is going to be in pre-technic, so in late September. And at Crito, we're organizing what we call a machine learning and a reward workshop, probably on the 21st of November. And if you have any questions about any of those events, please come to, come ask me for answers. Thank you. Thank you. One or two short questions? I'm not any specialist in this, but I was wondering, in the auction case, can you take into account some kind of internal information or privileged information, like for example, some auctioners are being given information by the organizers. Is it possible to take these kind of things in account? So actually here, that's the question, oh, you heard it. So in this kind of, I mean, that's in a, I want to say in real life auctions, when you're trying to say, to buy a painting or a boat or a house or whatever, there is some private information that tells you what is the true value of this goods you're trying to buy. And here you want to leverage it and see, and if you see what is the other one that you're buying, then it, I mean, modifies your building strategies. But here actually, something which is really different, when you have a user that arrives, the value for Creteo is totally different from the value is independent of the value for Rocketfuel. For the simple reason that Creteo has some clients, so as I say, there was Microsoft, and Microsoft is going to booking, but here is the ad for Microsoft, and Rocketfuel has the ad for Air France. And of course, Air France is not going to ask two re-targeting companies, that's Creteo and Rocketfuel, to manage their company. So only one company is advertising for Air France, only one of them is advertising for Microsoft. So at the end, we have this ad for Microsoft and the ad for Air France, and the probability of clicking are totally independent. Well, almost independent. So the information that Rocketfuel has on me, whether I'm going to click on the ad for Air France, it is not going to be helpful for Creteo to determine which is the probability that I have on clicking on its ad. So the private information in that case makes less sense that if you have a common value of the good, which is typically when you buy a house, it has some price, which is the market value of that house, and everybody has a different signal about it. And you're trying to gather this signal and try to find the optimal price of that thing. But here, we are really in a case where the good that I sold has a different value for everyone. So having private information and trying to leverage it makes sense, but it's just using the data you have and trying to be, because here I just say that we don't gather any data on the user, just saying, well, it's always the same user with the same stochastic probability. But then actually, this is not true because my browsing history will depend on Creteo or Rocketfuel has some private information about my behavior, and of course, they are leveraging this to update their, the probability of clicking. But yeah. So I was wondering about the, so here you talk about the expected regret. So I was just wondering what is the behavior of the regret pathways? So do we have any, is there any control pathways on the regret like, well, to know if the scaling like square root t of log t is something just available in mean or also on the full distribution of the regret? No, you can, so this algorithm actually just working for expectations. So it just in mean you have this kind of regret. Sometimes it can be linear, sometimes it can be smaller. But you also have a variance of those algorithms that take that into account and you can show that you can put some probability and say, okay, I want to have this, I mean, some high probability version of those results. Okay, instead of having square root of t log t, you can replace some t by one over delta. Where delta is the probability you want to control. Typically, you can do that. But that's, you just have to modify a bit your algorithm. It seems very similar to the original truth just that the variance can be in one DOWNREST quantity. That's, that's a really small chance that the probability of thislied set of 3 is not a factor that people can use籌 because in real world,
 Thanks for the invitation.  It's always a pleasure to be here.  And I'm going to speak with my friend Philippe Régault.  He's a student, John Whid from MIT.  So the thing is, I'm going to speak about two things,  two main topics today, which are, as you can see in the title,  Bandit.  Another one is auction.  So Bandit is a subfield of learning theory.  And more specifically of reinforcement learning,  the talk we saw yesterday evening.  And the main idea is that you have someone,  particularly in algorithms, that are going to take decision  and get rewarded for this sequence of decision.  And auction, well, I guess all of you  know what auction is.  So I will motivate our problem.  And then I will show you some theory  behind the multi-term Bandit thing  and how we can apply it in a real life auction,  real life problem, motivated by some stuff we do at Criteo.  So it's not the right button.  OK.  So what are multi-term Bandits?  So the original motivation of multi-term Bandits  goes back to the 30s, when we wanted, where Thompson wanted  to study how to do clinical trials,  sequential clinical trials, and with some objectives.  So what was his idea?  He says, OK, let's say you are a pharmacist company  and you have two treatments, either the red one or the blue  one.  And you want to find which one is the best one.  OK, so you will hire a bunch of patients.  And you want to decide whether it's  the red or the blue one, which has the highest efficiency.  So simplify, let's just say, when you give a treatment to someone,  it's either cured or dead.  So there's just, of course, a simplifying assumption,  but just to give you some intuition.  So if you want to do some basic statistics,  you will say, OK, let's say you have 1,000 patients.  You want to compute to do some inference.  You want to know which one has the highest efficiency.  The basic stuff to do is, well, I'm  going to give the red pill to 500 of my patients  and the blue pill to 500 of my patients.  Then I will compute.  I will see how many patients survived.  And I will claim that the best treatment is the one  that saves most of the people.  So that's a very good answer.  It works.  It works really well.  But the thing is, if, let's say, the red pill kills everybody  and the blue pill saves everybody,  if you do that, if you do this in a statistical perspective,  you're just going to kill half of your patients.  So indeed, you will know at the end that the blue pill is  the best one, but you will have killed 500 people.  And this is something we want to avoid  when we're doing the clinical trials.  So the idea of Thompson says, well,  I'm not going to do clinical trials as it is right.  I mean, we're using these ideas, these techniques.  What I want to do is get a patient, give him a treatment,  see if he survives or not.  Based on this information, I will give another treatment  to another patient and so on and so forth.  And my idea is to find which one is the best one  between the two treatments, the red one or the blue one.  But at the same time, I want to save as many patients  as possible, which here, what we call sometimes ethical.  So that was during the 30s.  And so we had some, well, this guy got quite famous for this.  And then we had some theoretical study of that problem  during the 50s by Robins, like in Robins.  And then it's, so again, in the 80s and 90s,  some work on bandits.  And then it kind of declined.  Nobody really cared about bandits.  Until the beginning in 2000, where this idea of multi-impeded  had a new application.  And the thing is, it's not really about clinical trials.  And the application is from an online auction,  an online advertisement displaying.  The thing is, when you go to a website,  sometimes you have some ads on these websites.  And oh, sorry about that.  How do you, is this the phone?  Yes.  So when you go to a website, you have a banner with an ad on it.  And if you are the user, click on the ad,  then the guy that put the ad gets rewarded.  So if you go to Le Monde, for instance, that website,  to lemonde.fr.  And if it displays, like simplifying,  but if they say display an ad for Trois-Huist,  if you click on Trois-Huist, then Le Monde gets paid.  So here, it's kind of a similar thing  that having a clinical trial.  Le Monde has two options, the red one or the blue one.  And it can give the red treatment or the blue treatment  to the next user that arrives.  And it will get paid if the red treatment is efficient,  which means that if the user click on the ad.  So here, same thing.  We have two different ads to display, the red one  or the blue one.  Le Monde wants to know which one is the best one.  And he wants to do it as quickly as possible  because he wants to have as many clicks as possible  because clicks are money.  And that's the idea.  That's the motivating idea of this talk.  And this problem here of displaying the right ad  on websites, actually a huge problem.  Lots and lots of companies are working on it.  You see why?  Omni, actually.  Because there is billions and billions  of ad displayed every day.  And so there is billions of billions of dollars  involved with that problem.  So it's a really important one.  So let's look at it, how it actually really works.  And because where the options arrive.  So when you arrive on a website, and so here,  it's a picture from Le Monde.  From yesterday, I went to Le Monde yesterday.  And I went twice on Le Monde.  So I just refreshed Le Monde.  So the first time, I got this ad here.  So for Microsoft.  I know it's tiny, but it's for Microsoft.  And then I just refreshed my browser.  And I got another ad for Air France.  So of course, I got these ads because in the past,  I browsed on the website of the Microsoft  and on the websites of Le Monde, of Air France.  So anyway, so I got these two ads.  And here, I don't know if you know that,  but if you look at those ads, can we see here,  yeah, on the top right, you have a blue arrow over here  and the same here.  And if you click on it, you can see who sent you that ad.  And here for the purpose of that talk, I did that.  And you can see that if you click this ad here,  this was sent to me by Criteo, my own company.  While that ad here was sent to me by Rocketfuel,  another company, a concurrent.  So the question is, who gets to decide  which ad I'm going to see?  Why this ad is shown to me by Criteo?  While it's here, Rocketfuel, that's an exact ad.  And the process of deciding which company  that our advertising gets to put an ad on the website  is, well, it's an auction.  It follows, it's as follows.  So actually Le Monde, that's on Le Monde,  is not choosing by himself the ad he wants to display.  He's not choosing between Office and Air France.  I guess, yeah, Air France, anyway.  So what Le Monde does is, well, he has a bunch of clients,  Criteo, Rocketfuel, and all other companies,  and he contacts them directly or not,  it's not really relevant.  And he say, well, I have the Année Perche  that arrived on my website, so you know him very well  because he is not deleting his cookies,  so you know him very well, you know what is boarding,  and he's on my website.  And I have a slot for an ad,  typically in the right part of the Le Monde,  so I have a slot for this ad.  Who wants to put an ad here?  And he says, so I'm running an auction,  a second price auction, and who wants to put an ad here?  How much do you value the fact  that you can display an ad here for him?  Criteo and Rocketfuel answer and say, okay, well,  I don't know, maybe Criteo says here,  said I'm willing to pay two cents for this opportunity,  while Rocketfuel say, well, I'm willing to pay one cent,  so Criteo wants that auction.  And the display an ad.  And what Criteo paid is what we call,  so the second price, Criteo won the opportunity  to display an ad for Microsoft or anything else,  but he paid only the bid of Rocketfuel.  Okay, so when you bid two cents,  if you're in an auction, if you're opponent bid one cent,  then you will pay one cent.  You're not paying your own bid,  you're paying the second bid, the second highest bid.  Therefore, for some reason for that,  I will explain them later on.  So then let's say that Criteo won,  he paid to Le Monde one cent,  which was the bid of Rocketfuel,  then he display an ad to me,  which was for Microsoft,  and then it's Criteo that is going to get paid  by Microsoft if I click on the ad.  If I don't click on the ad,  Criteo is not going to get paid,  and so he just wasted money by displaying an ad to me.  And actually that's what happened,  I did not click on that ad,  so Criteo learned that I was not willing  to click on the ad for Office or for Microsoft,  and then when I refreshed my browser,  there was another auction,  so Le Monde said, well,  Yanné Perche is here again,  do you, how much do you value the fact  that you can display an ad and so on and so forth?  Criteo said, well, probably they say, okay,  I displayed an ad to him two seconds ago,  he didn't click, so now he's worth like zero to me,  so they bid zero, Rocketfuel probably bid one,  and they got the one cent,  they got the win the auction,  and they got the opportunity to display an ad.  And that's all things works.  I have to say that I had lots and lots of auctions every day,  there's billions of auctions every day.  So just to give you an idea of how many auctions  we have there is in the world every day,  just imagine that all those data,  the data that are just sending by Le Monde saying,  Viané wants, so we have an auction for Viané,  and all those data gathered around the world,  they cannot be stored,  and even Google don't manage,  don't know how to store that many data, okay,  so it's not like big data,  it's even way more than big data,  I mean it's so big, you cannot store them,  so you have to throw away the data,  so because there's billions and billions every day  of structure auction.  Anyway, so now the problem of we had that hand is,  well, Criteo here, he wants to bid,  so he wants to bid what he said,  he wants to put an optimal bid to the auction,  so their difficulty for Criteo or Ketru is the same thing,  is to learn how much they should bid,  and that's the first thing,  because they know me,  they know I'm, sorry, I'm a perche,  I have this boring history,  so they know basically what I'm buying,  where, when, but the thing is how much should they build  to optimize their revenue,  and this is the thing that, based on your data,  the question is how can you learn  the optimal strategy in those auctions,  and then when they win that auction,  there's another issue that arrives,  because when Criteo just say,  okay, I'm going to bid two cents  for putting in that for Viannée, for me,  the thing is, they don't have just one client,  they don't have only Microsoft as a client,  they also have like a CDS-KUNT or booking,  so they can put in that for CDS-KUNT or booking or whatever,  so here from the point of view of Criteo,  once they want the auction, everything is not done,  they still have to decide which ad to display,  and how they're going to construct that ad,  and so on and so forth,  so lots and lots of decisions  that must be taken by Criteo or any of their companies  to learn the optimal behavior to adopt  in this repeated interaction,  and this is where, I mean, there's clear connection  with reinforcement learning,  as we saw in last talk yesterday,  because you have repeated interaction,  you take decision, based on decision,  you get some reward with the guide click on that  on your ad, and then you try to update your strategy,  your policy based on what you saw in the past.  Okay, so here, just to give you an intuition,  to give you some ideas,  if you click, still on those things here,  you have lots of options,  you can control the cookies that you are willing to,  they can control your cookies,  and you can decide, companies by companies,  which cookies you're going to allow or not,  and this is just the list of companies that are betting  when your ad is displayed.  So see again, this is a really huge market,  I don't know how many of them there are,  but you just, I mean, it's like probably 100 or so.  So see, those are all the companies,  we don't see it, but here is Criteo,  so Criteo is over here,  where you have Facebook, I guess, which is over here,  you have Yahoo here, so all those companies,  Rocket Fuel of course is around here,  so you have all those companies  that are betting at the same time,  and it's a huge, huge, huge market.  So let's, so that's what's the motivation for Bandit,  another motivation for the Bandit theory  is motivated by this, what we call spam filtering.  So it has nothing to do with auctions,  with ad displaying, it's another motivating example.  So first one was clinical trial,  second one was auction for displaying ads,  the second one is spam filtering.  So as you all know, when you receive an email,  your spam filters decide whether it's a spam  or not a spam.  So it's the same thing, each time you receive an email,  it takes a decision, and it gets rewarded by one,  if it makes the right decision,  and it gets rewarded by zero, if it makes the wrong decision.  The right decision being, well, you classify correctly,  the wrong decision being you misclassify your mail.  And here's just a message, if you're already bored  with my talk, which I mean, I'm okay with that.  The thing is, so what do we call it,  sometimes we don't know about this,  what do we call it, spam.  So just a thing is, like a spam, as you can see here,  is actually a fake ham, that is sold in the UK and US.  It's like a recomposed ham.  And you cannot tell by the look of it,  whether it's good or bad for you, okay?  But actually, well, the fake ham is not that good,  while the good ham is better, hopefully.  And so this spam filtering is to distinguish  between the good and the bad ham, okay?  And this has been, so it was, that was a brand,  and you have this sketch from the multi-peaton,  and I don't remember, I think it's 79,  where they are going to this restaurant  and they are ordering stuff,  and the food and they're asking the waiter  what is on the menu, and everything is based on spam,  so it's just the spamming, actually,  the spam, spam, spam, spam, spam, spam,  during the whole sketch.  And this is why we are motioning a spam.  And the name, I mean, that's where the name of spam mail  that came, okay?  So this is, at least, something you can bring back to home  if you don't understand about learning, learning theory.  So let's go back to bandit theory, how does that work?  So to simplify things, we just look at the original setup  where you have the clinical trials, you are, oh, sorry.  You have two treatments, the red one and the blue one,  and you're a company and you want to know  whether the best one is the red one or the blue one.  Each time a patient arrives, you can give him  the red or the blue one, and he will die or survive  depending on the efficiency of your treatment.  So how does that come?  So here, let's say you have a bunch of patients  that arrive one after the other one, okay,  a line of time, each one is a patient.  So you have the first patient that arrives.  You don't know anything about your treatment,  let's say you give him the blue treatment.  And you wait for quite a long maybe,  or let's say it's instantaneous,  and you see that the guy died.  So based on this information, you know that first guy,  you got him the blue treatment and he died.  You have to take another decision.  So maybe you want to try the red one.  So, but you only have this information.  So let's say you try the red one.  You wait a bit, and you see that that guy survived.  So now you have the third patient that arrives.  Based on this information, you say maybe the red one  is better than the blue one.  So you try again the red one.  Patients survive again.  Okay, fourth one, okay, maybe the red one,  and here you see someone died.  So now you have two options.  Maybe, maybe indeed the red one is the best one,  or maybe it's the blue one and you are not lucky.  Maybe you killed the patient, but that was just bad luck.  You know in statistics, it's hard to make a statistic  based on one sample.  So here based on this, you say okay,  clearly sometimes the patient with the red treatment dies,  and sometimes the patient with the blue treatment dies.  So in order to know which one is the best,  I might have to sample more the blue patient,  the blue treatment.  So for the next guy, you're going to take blue  and see that he survived, and so on and so forth.  But here's a message of that slide,  here you have a sequential treatment,  okay, sequential, you take sequential decision,  and you can only base your decision based on what you saw.  Here you can just, you don't know if the patient  would have survived if you have given him  the red treatment.  You don't know that, you have no idea.  Same thing here, you don't know if that patient  would have survived if you have given him  the blue treatment.  So you are basing your decision only  on the thing you saw.  And this is the difficulty of the bandit literature,  is you're basing all your decision on what you saw  and not on what you didn't know.  It seems trivial like this, but I mean,  this is really important actually.  And the objective is, as I said,  is to save as many patients as possible.  So typically here, if you put zero for people that died  and one to people that live,  then you want to maximize the number of success,  the number of ones you received.  So that thing here, you can easily see  that this could be an ad, okay,  that could be the blue ad and the red ad.  And being dead means that you don't have a click.  Surviving means that you get a click  and you want to maximize the number of click  because a click is money.  So let's look at, there is a bunch of literature on this,  a bunch of ideas, and let's look at how it works.  I mean a way to solve that problem,  to have an algorithm which makes sense.  So let's look at what we call stochastic mutambenit,  which are data IID.  So let's say that, so this thing is following,  you have, as we have saw in yesterday's talk,  you have K actions, each time you have K actions,  so you have K treatment you can sample from,  okay, you have the treatment red, the blue one,  but you have also, I don't know, the green one.  So let's say you have K treatment.  And you want to sample sequentially from those treatments.  And at stage T, when you have the patient T that arrives,  you can give him one of those treatments.  And if you give the patient T the treatment I,  you will get as a reward XT of I.  So we, I mean, I used to assume that X of Y  was either 0 and 1, but this is just a simplifying assumption.  I can assume that they are sub-Gaussian, or actually  Gauchan, that's irrelevant.  Okay, so being 0 and 1 just simplifies the talk.  So let's say that XT of OI, IID,  so that's an IID process, of expectation mu high.  So mu high is the probability that a patient survived,  or the probability that someone clicked on your add.  So of course, if you know those parameters,  if you knew mu high in advance,  so if you know that the treatment red is better  than the treatment blue,  you will give the red treatment to everybody, for sure.  Unless you are, I mean, anyway.  So if you knew mu high in advance,  you will give to anyone the best treatment.  Here, the thing is you don't know this mu high.  The question is how can you learn  which one is the best one without sacrificing,  without killing too many people,  or without losing too much money?  So to do that, you're going to build a policy,  as I show in the slide,  a policy is just based on what I see  either to choose the action red or the action blue.  So you want to build such a policy  that maximizes your reward,  the expected reward, as we saw yesterday.  So you want to maximize your expected reward.  So that's the kind of stuff you want to do.  And the maximum reward is, I mean,  in expectation is the sum of mu Pt,  where Pt is the treatment you give to patient T.  So here is an issue with that formulation here,  is that, as you can see,  those mu can hold be arbitrarily big or arbitrarily small.  There's no constraint on mu,  there's no prior on mu.  Okay, we are in a non-parametric world.  We have no assumption on mu at all, it can be anything.  So the thing is, if you have an algorithm  that gets a lot of money,  okay, let's say that's your expected money.  And you say, well, after stage T, I got T rows.  So I have a very good algorithm  because I got one T rows every day.  Maybe it does not mean that your algorithm is really good.  You get T rows, it just means that all those parameters  mu i are really big.  And maybe the smallest mu i is actually one.  All of them are bigger than one,  they are all equal to two, except one,  which are equal to one.  And you are really happy of getting T rows  where you could have got two T rows.  So it's not because that number is big  that you are found a good algorithm.  It's not because you have a lot of money  that your algorithm is good  because you could have got even more money.  And same thing, if you have, let's say at stage C,  you have almost no money at all, okay,  you just have epsilon T.  It doesn't mean that your algorithm is bad.  Maybe all the other options were even worse.  So having lots of money or higher reward  doesn't mean that your algorithm is good.  And the same way around,  if your total reward is bad,  it doesn't mean that your algorithm is bad.  So we have to normalize that number.  And there is two ways to normalize that number,  depending if you're from the learning theory  or from the learning theory community  or from the CS community.  And so I'm from learning theory,  so I'm going to use what we call the really great.  The one is the competitive ratio.  So the great is, well, you look at what you got.  Okay, that's an expectation of your expected reward.  And as I told you, if you knew in advance  all those mu i's here,  you would have given to all your patients  the best treatment.  And so this is the number of patients you would have solved.  The expected highest number of highest expected reward  you would have got,  how do you know all those parameters?  So this is what we call the regret  is the difference between those two numbers.  And this is just, I mean, why we call it regret  is just because it's, I mean,  the literal translation, literal sense,  it's just the difference between what you could have got  and what you got.  Because just what I could have got,  I had I known all those parameters,  minus what I got.  And now we are focusing on that notion of regret  and we want to minimize this thing.  We want to have a regret which is as small as possible.  Yeah.  Would you guess the other criterion?  Yeah, sure.  So let's,  other criterion is instead of having this,  this additive normalization, okay,  where you're subscribed from your,  from your, well, you're subscribed  to the maximum your reward.  The other one, which is the competitive ratio  is just you divide, okay.  And here, what you really want this to be  as small as possible.  And the other one, the competitive ratio  is when you divide your,  your, your, your cumulative pay reward  by the optimal one, the maximum one.  And you want this to be as close to one as possible.  Okay.  So this is called a competitive ratio.  And yeah, I mean, there are some connections  between them, but let's not enter into too many days.  So this, this regret, as you can see,  I can rewrite it using this formula,  this formulation here.  Well, I'm going to introduce a parameter delta i,  which is just the cost of making a mistake.  So the cost of making a mistake is,  is just, oh, sorry.  It's just the difference  between the efficiency of the best treatment  and the efficiency of treatment,  if you, of the treatment i, okay.  Delta i is the cost of prescribing treatment i  instead of prescribing treatment star, the best one.  So that thing, obviously, as you can see,  can, the regret can only increase this time  because that, that, that parameter here is positive.  And those, those things are also positive.  So you have the sum of positive numbers,  we can only increase.  In the worst case, of course, it will increase linearly.  So the question is, can we find an algorithm  which regrets we're going to increase  because we have no choice.  It has to increase.  Okay, so increasing sum of positive numbers.  But increase slowly, sublinearly,  in the square root of t, or even in the log t,  or even in constant.  How can we do that?  That's the question.  And the answer is, well, the following.  The most famous algorithm that does that.  So here I'm going to say this is,  I'm going to focus in non-athletic bounds.  So I want precise, non-athletic, efficient bounds.  There have been algorithms before that.  But here, all those results are really precise  in terms that you control everything.  Okay, all those, all those,  those inequality are really precise  and are non-athletic.  And while I'm here, this symbol here,  smaller or equal than with a tilde below it,  just means that I'm eating a constant.  And a constant in my, in my community,  a constant is a constant.  A constant is two, okay?  If you have like a k, k is not a constant,  okay, it's a parameter.  Or if you have, I don't know what do I have here.  Delta, delta is not a constant.  It doesn't change with time,  but still it's not a constant.  It's a parameter.  Okay, a constant is two, it's pi, it's one million.  Okay, I don't care.  So maybe here, I've eaten one million or two.  I'm not going to tell you.  But that's what we call constant, universal constant.  Okay, it's not a parameter.  So there is this algorithm which is widely famous.  It's called UCB for upper confidence bound.  So the idea is the following.  So I want to prescribe to my patient  the best, the best treatment,  the one which has the highest efficiency.  Of course, so highest efficiency  is the one with the highest mean.  A very good proxy for finding,  for computing the mean of a random process  is to look at its empirical mean.  But here there is something which is really interesting  in online learning is that everything you know  about statistics is incorrect.  If you look at that thing here, the empirical average,  and if you look at the expectation of that guy here,  the expectation of the empirical average,  well, you want to say that the expectation  of the empirical average is equal to mu i.  Okay, you want to say that.  Because that's the first thing you learn in statistics.  When you have a process, the expectation  of that process is equal to its mean.  By definition actually.  But here it's incorrect.  The expectation of the empirical average  does not necessarily converge to the expectation,  to its true expectation.  Why, why is that?  Why is that true?  It's simply because, I mean,  when you have the empirical average  will converge to the true average,  when the data you get are just received as is.  So you say, okay, I have 1,000 data that are iid,  and the expectation of those guys,  of the empirical average on those 1,000 data are in,  I mean, of course the expectation is mu i.  But here those data are not iid.  Because you choose to sample from the process i  based on the previous data you received.  So typically if in the past,  the process i was really bad, bad behavior,  when you're going to sample it less and less.  So at the end, it might be the case  that the expected empirical average  does not converge to the true average.  It's possible.  So you have to be really careful.  Stated otherwise, that guy here,  the empirical average, is biased.  It's a bias estimator of the true mean.  So those are, so if you based your policy  on a non-biased estimator,  well of course your policy is going to diverge.  You might not converge to the best one  because you're looking at a bias estimator.  So you want some hope to unbiased it,  or to control the variance.  And the way to do that is to add some error term,  which is this one.  So it's quite a lot of two log t divided by  the number of samples you have.  And this is called hyper-coffe-dazmone  because it's linked to everything in the quality.  I don't know if you know it.  I mean, otherwise it's not really important.  And the thing is that mu high is going to be  really close to that guy of the empirical average  plus the error term in the orange.  But not necessarily close to the empirical average.  So this guy here is a very good proxy  for what the empirical mean could be.  It's still biased, but it's less biased, yeah.  So this correction is the limitless for x, the real one,  and bounded by one.  So here, this correction is indeed  when x is bounded by one,  or when there are sub-gauchan with a parameter one fourth,  which is more or less equivalent  to being bounded by one.  Exactly.  So if you know the variance of your parameter,  sorry, this is one, but if you have a variance sigma square,  you can have a bond here that involves sigma square.  You're going to put sigma square over two.  And if you don't know that variance,  you can estimate it online and put here  based on everything in equality.  And if you're going to use an estimate of the variance,  and you're going to use Bernstein inequality instead,  and so you get sigma hat here.  Okay?  But here typically is just,  this idea is just saying, well,  with very high probability,  actually with probability one over t to the fourth,  new i is going to be smaller than that thing.  Okay?  Just to note, the fact that you have nothing,  a thing bound is just because we made this assumption.  If you have another type of process,  you could make any per-competence bound here.  As long as you have, all the results I'm going to say,  are going to be true if you have exponential convergence.  And so if you look, if you take this algorithm,  if we call it UCB,  well, you can show that your reglet is going to scale,  is going to increase, of course,  because it has to increase.  But not that quickly.  Actually, the reglet is not going to be linear,  it's just going to be logarithmic.  So your reglet is just going to increase as log t  over the delta k, the sum of log t over delta k,  which is, of course, much slower than t.  So it means that if you compare,  if you look at, let's say you are in a clinical field,  if you could have saved all the patients, t,  and you want to find out which one is the best one,  you will just lose log t patients in the process,  which is not that big.  And if you look at this type of bond,  here it depends on delta.  So you might say, yeah, I want to have uniform guarantees  over all the possible delta,  all the possible cost of action,  all the possible parameters.  And if you take the maximum of that thing here,  well, it more or less sums up to find this equation,  and you can show that your reglet is bounded  as a square root of kt log t.  Of course, because here if delta goes to zero,  this goes to infinity, but it's always going to be smaller  than the square root of kt log t.  So in any case, your reglet is going to increase  as much as the square root of t,  which is way smaller than t.  And if your parameters are nice enough,  then it will increase as log t.  So that has been, so it's prepared, that's in 2002,  so it's 15 years ago.  And after that, there is lots and lots and dozens  of different, even underwrites and thousands of papers  and bandits following this trend, this trend of ideas.  So the question I might ask is why,  because it looks pretty simple.  Actually, it is pretty simple.  And you should just look at the proof.  The proof is, I mean, it's two lines,  so I'm just going to do it.  Well, I'm going to lie in the middle, but still.  So if you don't lie, it's like four lines.  So let's look at the proof  or just to give you some intuition.  So we're going to look at our algorithm.  The algorithm is going to sample, to prescribe  the treatment i, which is not the best one.  Under which condition?  Well, based on this idea, it means that the score  of our treatment i is bigger than the score  of the best treatment.  So it just means that the score of the treatment i,  which is the empirical mean plus the error term,  is bigger than the score of the best one  plus its error term.  I know if you just take that guy here and say,  well, okay, here is where I'm lying,  but actually I'm not lying.  The empirical average is almost equal to mu star,  and that guy is almost equal to mu high.  So if I take that guy on the right part,  I will get delta high.  If I take that guy here, I'll get delta high.  This one is bigger than one, so I can just remove it,  and that one is going to be here.  So I'm going to sample from i,  more or less, when delta i is going to be smaller  than that error from the error term.  And just give me, if you invert this equation,  the number of times you sample from process i  increase as log t over delta i square.  Okay, and this is the main idea of the proof.  And then everything is like to line.  And you can show that this is actually optimal.  You cannot do better than this.  In some sense, I'm not going to enter into this detail.  But here's the idea of that algorithm  and why I do like Bandit,  because you can see the sitting is quite simple to explain.  Okay, you have several processes for treatment.  You want to give one to the other one.  So you can make any other assumption, say,  okay, what if we say, assume that this is possible,  this is not possible, or whatever.  And the proof are basically not that difficult.  The most difficult thing is to find the right algorithm.  Okay, to have the good idea.  It's not like taking a mathematical hammer  and hammering your equation until you,  at the end, you get something which looks nice.  Okay, it's just having a good intuition, which is,  I mean, I think it's nice.  So there are lots of algorithms  that improve the right software,  I've done some hope,  I'm not going to enter into the detail.  If you're interested,  well, can you look at the slides that are going to be on mine.  So here, I assume the data were IID.  But in real life, for instance,  if you look at your spam data,  the mail you receive are not IID.  Why is that?  Because if you think again about the spam filter.  So let's say you're building your spam filter.  And there is an example about this.  So you're building your spam filter.  And what you're going to receive.  So you receive an email.  So the first, I guess the first spam was on Viagra.  So you receive email saying Viagra.  And it's quite easy to understand that  when you have Viagra written in full letters in your mail,  then this is spam.  So the first spam filter say,  well, if Viagra is here,  then it's going to be a spam.  But then the spam standard,  people that are trying to sell Viagra,  figure out that if they put Viagra  in the, I should not say Viagra when I'm recorded.  I should find a better example.  And let's, anyway, it's too late now.  So yeah, those guys figure out that you don't want to put  Viagra in your mail.  So just put v.ive.a.g.l.a.  And then the spam filter say, well,  this modified the distribution of data you receive.  Because before you never saw this kind of string  of letters with the point.  And then, so it means that the data adapted itself  to your own algorithm.  Okay, so the data are not IID,  they are adapting to your algorithm.  You have, you make a decision  and the data are adapt to that decision.  And then same thing.  So the spam filter say, well, v.i.etc  is a spam.  And it gets this spam.  So it say, okay, I'm going to change my algorithm.  Say this is not a spam.  And then the spam standard say,  okay, no, we have to change things.  So just put lits, lits, lits, you know,  you replace i by one and so on and so forth.  And then you have this game between spam standard  and spam filters where each one of them is adapting  to their own strategy.  So at the end we have, when you were looking at  this multi-term bandit, you still have your action.  So, okay, so you still have k action, one to k.  But the thing is your process XIT are no longer IID.  Because XT plus one, the law of XT plus one  depends on how the past.  So you cannot just say, you cannot use the last tool  which are based on empirical process  and only on the study of stochastic empirical processes.  So you have to be more clever.  The rate is defined as usual.  You say, okay, I'm going to look at stage T.  I'm going to look at what was the best decision,  constant decision up to that stage.  And you compare this, I mean, this is the amount of money  of people you will have saved,  how you were given to all of them with the treatment i.  And you compare this to what you got.  And this you want to minimize.  This is closely related to convex optimization.  So here you have, it's more or less convex optimization.  So you can use tricks for convex optimization.  I'm not going to enter into these details,  but you have to mix, to use random strategy.  As we saw before, you want to build unbiased estimator  and so on and so forth.  You can do that.  So that's what we saw yesterday.  We mentioned that estimator yesterday.  It's important sampling estimator.  So you have techniques to do that.  But the main message is the last one.  So if you're using this kind of algorithm,  then you can show that no matter what the sequence  of action is, okay?  So the data you receive can be generated by an adversary,  by another algorithm that is trying to screw you.  Okay, so you're adding a spam filter.  So you're trying to build a spam filter.  And the spam standard are adapting to your algorithm,  to your own algorithm.  And no matter what your adversary is,  no matter how strong it is,  you regret is not going to increase linearly.  You can find an algorithm so that you regret  only increase a square root of t times K log k.  So this is the very, actually,  at first time when you think about it,  it's kind of weird because you made no assumption at all  on the process XTI, no assumption at all.  And still you manage to learn which one is the best one  without any assumption.  And everything can change from one stage to another one.  So it's kind of, it's not that easy  to understand why it's working actually.  If you think about it, you have no assumption  on the data and you want to do as well  as the best strategy, but still it's possible.  And the idea, just in a few words,  is actually just to compensate your losses.  Okay, if at some time you have some losses  compared to action one and you have some gains,  so you perform better than action two,  then you can compensate the surplus you get  from action two to action one.  So just a matter of compensating your loss and gains.  But this is the idea, at the end,  the thing is you regret only scale as square root of t.  Which was the same, it was exactly,  this was, except for the long part,  but this was exactly the rates of the rate of error  of the optimal rates of error in the stochastic case.  So this means, actually, that if you look at it  at this last line here, it means that the adversarial world,  when you make no assumption at all on all the data  you can receive and the data can even adapt  to your own algorithm, this world is not more difficult  than the worst stochastic case.  Okay, so that was a 30 minutes course on Bandit.  Okay, all you need to know about Bandit theory.  So I'll just save you like 20 hours of my M2 courses.  So let's go back to action.  So remember, we have this problem here.  How can we use this idea of Bandit in our auction problem?  So we have, I mean, yeah, so we have this auction.  So Le Monde is offering a slot to Creteau or Rocketfuel  to put an ad on my webpage.  And the question is from, the auction is second price.  And the question is how can Creteau and Rocketfuel  learn what they should be?  So, the first question you might ask is,  what is that second price auction?  How come when you bid something,  you're paying the second highest price?  And the thing is, so there's this auction,  we call it sometimes V-Cray auction,  it has a really interesting mechanism, auction mechanism,  because what we call it's truthful.  And actually V-Cray, which in what you did,  got a Nobel Prize for that.  So let's say what the second price auction was.  So you have a good, that is sell on auction.  So it's either an ad like this,  but it can also be, I don't know, like a boat or whatever.  Or a painting.  So each buyer is going to, so he has his price evaluation,  so by your eye, things that for him,  the good is worth V-high, that's his valuation,  and he puts a bid V-high, okay?  So that's a secret auction, closed auction,  so he's only one, so just say, okay, I'm willing to pay,  that's how much of money for, I'm willing to bid,  that's how much of money for that ad or for that boat.  And I think so, you gather all your bids,  and the thing is, so you're going to look,  the winner of the auction is going to be the guy  with the highest bid, as I said before, which makes sense.  Okay, because he's the one which wants the good the most.  So the winner is B, so B-sharp,  no, B-sharp is the one you're going to pay.  So the winner is the guy with the highest bid,  and he's going to pay the second highest bid.  He's not going to pay his bid,  he's going to pay the second highest bid, B-sharp.  So why are we using this mechanism?  It's because, as I said before, it's truthful.  It means that your optimal strategy,  no matter what your opponents are doing,  no matter what you think they're doing,  no matter what their valuation are,  no matter what anything, your optimal action,  you have nothing better to do  than bidding your own valuation.  Okay, if you think this boat is worth $100,000,  then you bid $100,000.  If you think that this auction is worth one cent,  you bid one cent, and nothing more, nothing less.  You cannot try to be a smarter,  ever less and bid just a bit lower or a bit above  to maximize your revenue, it makes no sense,  for the following reason.  So your utility, so what you gain,  you're expecting gain is just,  well, if you win the auction,  if you don't win the auction, you get zero.  Okay, you had zero before, you had zero at the end.  So your utility is, if you win that auction,  so if your bid is bigger than the second highest bid,  you get V high minus the second highest bid.  So now let's say you want to be a smart ass,  and say, well, I'm going to bid more than my valuation.  Okay, my bid is going to be bigger than my valuation.  What might happen?  Well, you might win the auction.  Okay, V high might be bigger than V sharp.  But if V sharp is bigger than V high,  at the end you're going to pay more,  you're going to pay something,  you're going to pay more than the valuation of your good.  So you're going to get a negative revenue.  Well, if you had bid only V high,  your revenue is always going to be,  your revenue is always going to be positive.  Okay, or equal to zero.  Because V high is V high,  so you're only going to pay something  when V sharp is smaller than V high.  So if you're trying to overbid,  the only thing that could happen is,  you will not have one detection with your bidding V high,  your valuation, so you want the action,  but you pay more than what is worth.  So you don't want to overbid.  And if you bid, oh, there should be a smaller,  smaller than, if you bid smaller than your valuation,  if you say, okay, I'm going to try to save some money,  what might happen is just going to,  you're going to lose that auction.  And actually, if you think about it,  since you pay the second highest price,  the amount of money, if you win the auction,  conditionally to the fact that you won the auction,  the amount of money you're going to pay  is independent of your bids.  So the only thing that might happen is,  instead of winning an auction and making a small surplus,  you're going to lose that auction.  So the optimal strategy is,  it's always to bid your valuation.  So in this,  hard displaying,  if you want to display an ad,  the optimal strategy is, typically,  to bid the probability that someone click on your ad.  So you're trying to learn what is the probability that,  so Crito is trying to learn what is the probability  that I have on clicking on their ad.  Okay, because if they knew that,  if they knew that my probability is P,  then they should bid P.  So this, another guy got another,  I mean, my son got another Nobel Prize  because he improved the mechanism  by allowing the seller to have a reserve price,  which means that nothing is sold if there's no bid  below the reserve price.  And when it's sold, it's at least a reserve price,  but that's a bit irrelevant.  So let's look at our learning model.  So,  and we're going to place ourselves  in the shoes of Crito or Rocketjoule.  So we want to learn what is the probability  that I have to click on the ad.  Okay, they want to learn what is the probability  that me or you, guys,  is going to click on one ad.  And to do that, well, they need some data.  So they need to buy some data  to learn what is the probability of clicking.  So there's two ways to buy data.  I thought you just say, okay, well,  I'm going to buy 1,000 ad and look at what it is,  as we said before, and then you just compute the array.  Or you can do it in a more clever way.  And let's look at the model.  So we have several rounds, so that's all the actions.  So we have action one because I arrive on Le Monde  the first time, then the second time,  the third time, so on and so forth, like T times.  So they know that I'm going to be here for T times.  Okay, I'm going to click on Le Monde,  I don't know, like once a day,  so like three times a day,  so there is at least 1,000 options.  Okay, so we know that,  let's say we're going to fix T to be 1,000.  So that's the number of ads that can be displayed  and it's sequentially.  Okay, so when ads T arrived,  then each bidder, so each one of the companies  we have seen before, so the Criteo,  Rocketshul, Google, Yahoo, and many more,  can place bid, BT, between zero and one.  Okay, because that's typically the probability,  they assume this is the probability of clicking.  Okay?  So if, so we are Criteo, okay,  we are in a shoes on one of those companies,  let's say we are Criteo.  If BT, if our bid is bigger than the highest bid  of our opponent, it means that we have the highest bid,  then we win this auction.  Okay?  And what we paid is empty.  And we get to observe, let's say a click.  So you get to observe BT, the value, which is zero and one,  can be even zero, it's either zero or one.  Okay, let's say that BT is either zero or one,  to simplify stuff.  So at the end, our total utility that we got  during this process is, well, we saw move all the action,  so you look at all the action you have won,  when our bid was the biggest one,  our bid was bigger than the second highest one.  And what we got is BT, so it's zero or one,  depending if there has been a click,  minus what we paid.  That's our utility, and that's the thing we want to maximize.  So I'm not going to do this pitch again,  that this thing can be arbitrarily high or arbitrarily small,  depending on your algorithm is good or bad,  so we're just going to look at the regret  to normalize that thing.  So that in orange is the total amount of money we made.  And in black here, it's the maximum amount of money  we could have made had we always bid the same B.  Okay, if we made a B, then we will have done that,  that option if B is bigger than your second highest bid,  and this is the money we will have made, BT minus empty.  And we maximize this over B.  And our regret is going to be the difference  between those guys.  So from here, I made no assumption on what's empty  and BT are, whether they are stochastic,  SIR or whatever, or those data are generated.  So typically, BT is the value of a good,  is the probability that I have to click on one ad.  So typically, I mean, BT is whether it will click  on the ad or not, and typically, these are stochastic.  Okay, we can assume that the probability  that I have on clicking on the ad won't change each day.  Well, if I have, it's not true, but let's say it is.  So that's the first option we can make.  Okay, we can assume that the probability that I have  to click on the ad is stationary, it's independent of time.  And so the value of an ad for a criteria, which is BT,  which is 0 and 1, whether I click or not,  this is an idea process.  Here comes the other part, empty,  the second highest bid of my opponent.  I can assume that this is stochastic,  which means that my opponents are always going  to bid the same thing.  I mean, the bid is going to be constant with time.  Actually, this is true.  This is an assumption which makes sense,  because when you look at it, when you look at data,  it's almost true.  So I have lots of anecdotes I want to share with you,  but I don't have time, so if you are interested  in this kind of stuff, go ask me at lunch.  All you have to say is, well, I can assume that empty  is not going to be stochastic, because our opponents  are going to adapt to our behavior and so on and so forth.  So empty can be anything, and I will be able to adapt  to any sequence of bids.  So that's a pretty cool adversarial.  Okay, what's the second idea as in spam filtering.  Anyway, in that case here, if you look at your, oops,  if you look at the definition of regret,  when you maximize that thing with b,  and empty is independent on vt, which makes sense,  the optimal is always attained when b is taken equal to v,  your expected value.  Okay, so the regret revised as this.  Okay, that difference in black,  you should have bet at each time v,  and you bet inside bt, and this is your regret.  The difference between what you could have got at most  minus what you got.  The other thing we could look at is the adversarial  I'm not going to speak about it today,  but you have slides so you can just look at it online,  and it's when you make no assumption at all on vt either.  So what are we going to do in a stochastic case?  Well, as a algorithm we're going to use,  it is based on UCB, it's a variant of UCB,  that we call UCBid, because it's bidding  on an upper confidence bond.  And the thing is, our bid, we would like to bid the value v,  but we know, so if you look at the empirical average  of success, we know that that guy is biased.  Okay, I told you that this is the bias estimate of v.  So as before, we're going to add an error term,  so that this is still biased, okay, but it's less biased.  And so a negative, the number of auctions we want up to now,  and this is what we're going to bid.  And if we do more or less the same proof,  where it's way more difficult because it's continuous,  we have a continuous action and things are more difficult,  we can prove using the same ideas that the regret  is going to increase logarithmically in log t over delta.  So the question is what is delta?  Delta is the smallest interval between v  and, so it's an interval between v  and the smallest bid of open-end, which is above v.  Okay, so it means that we have no bids between v  and v plus delta.  Of course, the thing, we don't know it.  We don't know v and we don't know delta in advance.  And if delta is, so if your open-end is nice enough,  then your regret is going to scale on illogatmically.  But delta can be as close to zero as it wants,  if it doesn't want to be nice.  And this thing can also prove that it's never going to be  bigger than the square root of t.  So we have an algorithm such that it behaves as  so you can learn the optimal value of,  you can learn the value of a, of a,  and it can bid this value almost optimally.  The only thing it's going to lose is square root of t,  the factor of square root of t, which is,  which is admissible.  And if your open-end is nice, nice enough,  then it's log t over delta.  So I think delta, I said it can be small,  but if our open-end is like playing stochastic,  maybe the probability that that bid fall in that interval  is going to be really small.  And we can control this using some margin condition.  So I'm going to spare you the details,  but we can interpolate between,  we can have some continuous interpolation  depending on the strength or the badness or opponent  between the slope t and the square root of t.  Okay, there is this parameter, alpha,  that interpolates between those two.  How much time do we have?  Like it's over?  Okay, I only have one minute.  Perfect.  So that was the take-home message from the slide,  is that we can interpolate between this fast rate  of log delta and the rate of square root of t.  Now, as I said, we also have another algorithm  for when the data are,  we made no assumption of the data in the adversarial case.  I'm not going to describe it.  And same thing, we get a rate of adjunct in square root of t.  And all the results are, I see the constant are exact,  here it's a four.  And they are all more or less optimal up to log term  because we can show that you cannot build an algorithm  which is better than this.  Okay, there are always a way to screw any other algorithm.  That's the summary of our results.  So let's remember we had a whole this multi-ambient theory  that is 15 years old now.  And we adapted it to these sequential auctions.  And thing is, so our action space is no longer finite,  but in finite, it continues between 0 and 1.  And we still got to manage to get rates of adjuncts  as scale as square root of log t,  as log t or square root of log t,  which was quite surprising actually.  And even if you look more in detail into those bones,  if you're used to them, you can see that there's some  really, really interesting stuff going around.  So I'm not going to speak about this  because I don't have time.  Same thing, it's online.  But I would just to say that this is,  I find this very interesting.  Maybe for you it's just quite interesting.  Anyway, all goes, all takes our nature.  But can we use them, I mean, as it is in real life,  so question, the answer is obviously no  because there's many, many issues.  Here we made lots of assumptions  that are not satisfied in real life.  So there's lots and lots of works to do  before we can apply directly those ideas  into the real life problem.  And of course, if you are interested into doing that,  well, please come see me and we can discuss  all of these issues.  And they are described after, I mean,  there is a bunch of remaining slides here,  but it's just for online.  So I just want to finish that talk with two announcements.  There is 10 hour lectures by Tim Hofgarden from Sanford  on auction, data driven optimal auction.  So this is going to be in pre-technic,  so in late September.  And at Crito, we're organizing what we call  a machine learning and a reward workshop,  probably on the 21st of November.  And if you have any questions about any of those events,  please come to, come ask me for answers.  Thank you.  Thank you.  One or two short questions?  I'm not any specialist in this,  but I was wondering, in the auction case,  can you take into account some kind of  internal information or privileged information,  like for example, some auctioners are  being given information by the organizers.  Is it possible to take these kind of things in account?  So actually here, that's the question,  oh, you heard it.  So in this kind of, I mean, that's in a,  I want to say in real life auctions,  when you're trying to say, to buy a painting  or a boat or a house or whatever,  there is some private information that tells you  what is the true value of this goods  you're trying to buy.  And here you want to leverage it and see,  and if you see what is the other one that you're buying,  then it, I mean, modifies your building strategies.  But here actually, something which is really different,  when you have a user that arrives,  the value for Creteo is totally different  from the value is independent of the value for Rocketfuel.  For the simple reason that Creteo has some clients,  so as I say, there was Microsoft,  and Microsoft is going to booking,  but here is the ad for Microsoft,  and Rocketfuel has the ad for Air France.  And of course, Air France is not going to ask  two re-targeting companies, that's Creteo and Rocketfuel,  to manage their company.  So only one company is advertising for Air France,  only one of them is advertising for Microsoft.  So at the end, we have this ad for Microsoft  and the ad for Air France,  and the probability of clicking are totally independent.  Well, almost independent.  So the information that Rocketfuel has on me,  whether I'm going to click on the ad for Air France,  it is not going to be helpful for Creteo to determine  which is the probability that I have on clicking on its ad.  So the private information in that case makes less sense  that if you have a common value of the good,  which is typically when you buy a house,  it has some price, which is the market value of that house,  and everybody has a different signal about it.  And you're trying to gather this signal  and try to find the optimal price of that thing.  But here, we are really in a case where the good that I sold  has a different value for everyone.  So having private information and trying to leverage it  makes sense, but it's just using the data you have  and trying to be, because here I just say that  we don't gather any data on the user,  just saying, well, it's always the same user  with the same stochastic probability.  But then actually, this is not true  because my browsing history will depend on Creteo  or Rocketfuel has some private information about my behavior,  and of course, they are leveraging this  to update their, the probability of clicking.  But yeah.  So I was wondering about the,  so here you talk about the expected regret.  So I was just wondering what is the behavior  of the regret pathways?  So do we have any, is there any control pathways  on the regret like, well, to know if the scaling  like square root t of log t is something just available  in mean or also on the full distribution of the regret?  No, you can, so this algorithm actually  just working for expectations.  So it just in mean you have this kind of regret.  Sometimes it can be linear, sometimes it can be smaller.  But you also have a variance of those algorithms  that take that into account and you can show that  you can put some probability and say, okay,  I want to have this, I mean, some high probability version  of those results.  Okay, instead of having square root of t log t,  you can replace some t by one over delta.  Where delta is the probability you want to control.  Typically, you can do that.  But that's, you just have to modify a bit your algorithm.  It seems very similar to the original truth  just that the variance can be in one DOWNREST  quantity.  That's, that's a really small chance  that the probability of thislied  set of 3 is not a factor that people can use籌  because in real world,
2017-07-20_Perchet_0_95.png 2017-07-20_Perchet_96_155.png 2017-07-20_Perchet_156_215.png 2017-07-20_Perchet_216_275.png 2017-07-20_Perchet_276_395.png 2017-07-20_Perchet_396_659.png 2017-07-20_Perchet_660_731.png 2017-07-20_Perchet_732_791.png 2017-07-20_Perchet_792_1007.png 2017-07-20_Perchet_1008_1595.png 2017-07-20_Perchet_1596_1811.png 2017-07-20_Perchet_1812_2231.png 2017-07-20_Perchet_2232_2303.png 2017-07-20_Perchet_2304_11339.png 2017-07-20_Perchet_11340_25727.png 2017-07-20_Perchet_25728_26123.png 2017-07-20_Perchet_26124_26627.png 2017-07-20_Perchet_26628_29807.png 2017-07-20_Perchet_29808_30047.png 2017-07-20_Perchet_30048_30947.png 2017-07-20_Perchet_30948_32975.png 2017-07-20_Perchet_32976_34619.png 2017-07-20_Perchet_34620_37739.png 2017-07-20_Perchet_37740_38159.png 2017-07-20_Perchet_38160_45863.png 2017-07-20_Perchet_45864_49499.png 2017-07-20_Perchet_49500_54239.png 2017-07-20_Perchet_54240_55055.png 2017-07-20_Perchet_55056_55139.png 2017-07-20_Perchet_55140_62567.png 2017-07-20_Perchet_62568_63515.png 2017-07-20_Perchet_63516_66587.png 2017-07-20_Perchet_66588_66707.png 2017-07-20_Perchet_66708_67187.png 2017-07-20_Perchet_67188_67283.png 2017-07-20_Perchet_67284_74231.png 2017-07-20_Perchet_74232_80651.png 2017-07-20_Perchet_80652_83999.png 2017-07-20_Perchet_84000_84755.png 2017-07-20_Perchet_84756_84887.png 2017-07-20_Perchet_84888_84935.png 2017-07-20_Perchet_84936_86579.png 2017-07-20_Perchet_86580_88559.png 2017-07-20_Perchet_88560_88607.png 2017-07-20_Perchet_88608_91271.png 2017-07-20_Perchet_91272_91727.png 2017-07-20_Perchet_91728_91883.png 2017-07-20_Perchet_91884_92687.png 2017-07-20_Perchet_92688_93203.png 2017-07-20_Perchet_93204_95003.png 2017-07-20_Perchet_95004_95051.png 2017-07-20_Perchet_95052_95126.png
Thanks for the invitation. It's always a pleasure to be here. And I'm going to speak with my friend Philippe Régault. He's a student, John Whid from MIT. So the thing is, I'm going to speak about two things, two main topics today, which are, as you can see in the title, Bandit. Another one is auction. So Bandit is a subfield of learning theory. And more specifically of reinforcement learning, the talk we saw yesterday evening. And the main idea is that you have someone, particularly in algorithms, that are going to take decision and get rewarded for this sequence of decision. And auction, well, I guess all of you know what auction is. So I will motivate our problem. And then I will show you some theory behind the multi-term Bandit thing and how we can apply it in a real life auction, real life problem, motivated by some stuff we do at Criteo. So it's not the right button. OK. So what are multi-term Bandits? So the original motivation of multi-term Bandits goes back to the 30s, when we wanted, where Thompson wanted to study how to do clinical trials, sequential clinical trials, and with some objectives. So what was his idea? He says, OK, let's say you are a pharmacist company and you have two treatments, either the red one or the blue one. And you want to find which one is the best one. OK, so you will hire a bunch of patients. And you want to decide whether it's the red or the blue one, which has the highest efficiency. So simplify, let's just say, when you give a treatment to someone, it's either cured or dead. So there's just, of course, a simplifying assumption, but just to give you some intuition. So if you want to do some basic statistics, you will say, OK, let's say you have 1,000 patients. You want to compute to do some inference. You want to know which one has the highest efficiency. The basic stuff to do is, well, I'm going to give the red pill to 500 of my patients and the blue pill to 500 of my patients. Then I will compute. I will see how many patients survived. And I will claim that the best treatment is the one that saves most of the people. So that's a very good answer. It works. It works really well. But the thing is, if, let's say, the red pill kills everybody and the blue pill saves everybody, if you do that, if you do this in a statistical perspective, you're just going to kill half of your patients. So indeed, you will know at the end that the blue pill is the best one, but you will have killed 500 people. And this is something we want to avoid when we're doing the clinical trials. So the idea of Thompson says, well, I'm not going to do clinical trials as it is right. I mean, we're using these ideas, these techniques. What I want to do is get a patient, give him a treatment, see if he survives or not. Based on this information, I will give another treatment to another patient and so on and so forth. And my idea is to find which one is the best one between the two treatments, the red one or the blue one. But at the same time, I want to save as many patients as possible, which here, what we call sometimes ethical. So that was during the 30s. And so we had some, well, this guy got quite famous for this. And then we had some theoretical study of that problem during the 50s by Robins, like in Robins. And then it's, so again, in the 80s and 90s, some work on bandits. And then it kind of declined. Nobody really cared about bandits. Until the beginning in 2000, where this idea of multi-impeded had a new application. And the thing is, it's not really about clinical trials. And the application is from an online auction, an online advertisement displaying. The thing is, when you go to a website, sometimes you have some ads on these websites. And oh, sorry about that. How do you, is this the phone? Yes. So when you go to a website, you have a banner with an ad on it. And if you are the user, click on the ad, then the guy that put the ad gets rewarded. So if you go to Le Monde, for instance, that website, to lemonde.fr. And if it displays, like simplifying, but if they say display an ad for Trois-Huist, if you click on Trois-Huist, then Le Monde gets paid. So here, it's kind of a similar thing that having a clinical trial. Le Monde has two options, the red one or the blue one. And it can give the red treatment or the blue treatment to the next user that arrives. And it will get paid if the red treatment is efficient, which means that if the user click on the ad. So here, same thing. We have two different ads to display, the red one or the blue one. Le Monde wants to know which one is the best one. And he wants to do it as quickly as possible because he wants to have as many clicks as possible because clicks are money. And that's the idea. That's the motivating idea of this talk. And this problem here of displaying the right ad on websites, actually a huge problem. Lots and lots of companies are working on it. You see why? Omni, actually. Because there is billions and billions of ad displayed every day. And so there is billions of billions of dollars involved with that problem. So it's a really important one. So let's look at it, how it actually really works. And because where the options arrive. So when you arrive on a website, and so here, it's a picture from Le Monde. From yesterday, I went to Le Monde yesterday. And I went twice on Le Monde. So I just refreshed Le Monde. So the first time, I got this ad here. So for Microsoft. I know it's tiny, but it's for Microsoft. And then I just refreshed my browser. And I got another ad for Air France. So of course, I got these ads because in the past, I browsed on the website of the Microsoft and on the websites of Le Monde, of Air France. So anyway, so I got these two ads. And here, I don't know if you know that, but if you look at those ads, can we see here, yeah, on the top right, you have a blue arrow over here and the same here. And if you click on it, you can see who sent you that ad. And here for the purpose of that talk, I did that. And you can see that if you click this ad here, this was sent to me by Criteo, my own company. While that ad here was sent to me by Rocketfuel, another company, a concurrent. So the question is, who gets to decide which ad I'm going to see? Why this ad is shown to me by Criteo? While it's here, Rocketfuel, that's an exact ad. And the process of deciding which company that our advertising gets to put an ad on the website is, well, it's an auction. It follows, it's as follows. So actually Le Monde, that's on Le Monde, is not choosing by himself the ad he wants to display. He's not choosing between Office and Air France. I guess, yeah, Air France, anyway. So what Le Monde does is, well, he has a bunch of clients, Criteo, Rocketfuel, and all other companies, and he contacts them directly or not, it's not really relevant. And he say, well, I have the Année Perche that arrived on my website, so you know him very well because he is not deleting his cookies, so you know him very well, you know what is boarding, and he's on my website. And I have a slot for an ad, typically in the right part of the Le Monde, so I have a slot for this ad. Who wants to put an ad here? And he says, so I'm running an auction, a second price auction, and who wants to put an ad here? How much do you value the fact that you can display an ad here for him? Criteo and Rocketfuel answer and say, okay, well, I don't know, maybe Criteo says here, said I'm willing to pay two cents for this opportunity, while Rocketfuel say, well, I'm willing to pay one cent, so Criteo wants that auction. And the display an ad. And what Criteo paid is what we call, so the second price, Criteo won the opportunity to display an ad for Microsoft or anything else, but he paid only the bid of Rocketfuel. Okay, so when you bid two cents, if you're in an auction, if you're opponent bid one cent, then you will pay one cent. You're not paying your own bid, you're paying the second bid, the second highest bid. Therefore, for some reason for that, I will explain them later on. So then let's say that Criteo won, he paid to Le Monde one cent, which was the bid of Rocketfuel, then he display an ad to me, which was for Microsoft, and then it's Criteo that is going to get paid by Microsoft if I click on the ad. If I don't click on the ad, Criteo is not going to get paid, and so he just wasted money by displaying an ad to me. And actually that's what happened, I did not click on that ad, so Criteo learned that I was not willing to click on the ad for Office or for Microsoft, and then when I refreshed my browser, there was another auction, so Le Monde said, well, Yanné Perche is here again, do you, how much do you value the fact that you can display an ad and so on and so forth? Criteo said, well, probably they say, okay, I displayed an ad to him two seconds ago, he didn't click, so now he's worth like zero to me, so they bid zero, Rocketfuel probably bid one, and they got the one cent, they got the win the auction, and they got the opportunity to display an ad. And that's all things works. I have to say that I had lots and lots of auctions every day, there's billions of auctions every day. So just to give you an idea of how many auctions we have there is in the world every day, just imagine that all those data, the data that are just sending by Le Monde saying, Viané wants, so we have an auction for Viané, and all those data gathered around the world, they cannot be stored, and even Google don't manage, don't know how to store that many data, okay, so it's not like big data, it's even way more than big data, I mean it's so big, you cannot store them, so you have to throw away the data, so because there's billions and billions every day of structure auction. Anyway, so now the problem of we had that hand is, well, Criteo here, he wants to bid, so he wants to bid what he said, he wants to put an optimal bid to the auction, so their difficulty for Criteo or Ketru is the same thing, is to learn how much they should bid, and that's the first thing, because they know me, they know I'm, sorry, I'm a perche, I have this boring history, so they know basically what I'm buying, where, when, but the thing is how much should they build to optimize their revenue, and this is the thing that, based on your data, the question is how can you learn the optimal strategy in those auctions, and then when they win that auction, there's another issue that arrives, because when Criteo just say, okay, I'm going to bid two cents for putting in that for Viannée, for me, the thing is, they don't have just one client, they don't have only Microsoft as a client, they also have like a CDS-KUNT or booking, so they can put in that for CDS-KUNT or booking or whatever, so here from the point of view of Criteo, once they want the auction, everything is not done, they still have to decide which ad to display, and how they're going to construct that ad, and so on and so forth, so lots and lots of decisions that must be taken by Criteo or any of their companies to learn the optimal behavior to adopt in this repeated interaction, and this is where, I mean, there's clear connection with reinforcement learning, as we saw in last talk yesterday, because you have repeated interaction, you take decision, based on decision, you get some reward with the guide click on that on your ad, and then you try to update your strategy, your policy based on what you saw in the past. Okay, so here, just to give you an intuition, to give you some ideas, if you click, still on those things here, you have lots of options, you can control the cookies that you are willing to, they can control your cookies, and you can decide, companies by companies, which cookies you're going to allow or not, and this is just the list of companies that are betting when your ad is displayed. So see again, this is a really huge market, I don't know how many of them there are, but you just, I mean, it's like probably 100 or so. So see, those are all the companies, we don't see it, but here is Criteo, so Criteo is over here, where you have Facebook, I guess, which is over here, you have Yahoo here, so all those companies, Rocket Fuel of course is around here, so you have all those companies that are betting at the same time, and it's a huge, huge, huge market. So let's, so that's what's the motivation for Bandit, another motivation for the Bandit theory is motivated by this, what we call spam filtering. So it has nothing to do with auctions, with ad displaying, it's another motivating example. So first one was clinical trial, second one was auction for displaying ads, the second one is spam filtering. So as you all know, when you receive an email, your spam filters decide whether it's a spam or not a spam. So it's the same thing, each time you receive an email, it takes a decision, and it gets rewarded by one, if it makes the right decision, and it gets rewarded by zero, if it makes the wrong decision. The right decision being, well, you classify correctly, the wrong decision being you misclassify your mail. And here's just a message, if you're already bored with my talk, which I mean, I'm okay with that. The thing is, so what do we call it, sometimes we don't know about this, what do we call it, spam. So just a thing is, like a spam, as you can see here, is actually a fake ham, that is sold in the UK and US. It's like a recomposed ham. And you cannot tell by the look of it, whether it's good or bad for you, okay? But actually, well, the fake ham is not that good, while the good ham is better, hopefully. And so this spam filtering is to distinguish between the good and the bad ham, okay? And this has been, so it was, that was a brand, and you have this sketch from the multi-peaton, and I don't remember, I think it's 79, where they are going to this restaurant and they are ordering stuff, and the food and they're asking the waiter what is on the menu, and everything is based on spam, so it's just the spamming, actually, the spam, spam, spam, spam, spam, spam, during the whole sketch. And this is why we are motioning a spam. And the name, I mean, that's where the name of spam mail that came, okay? So this is, at least, something you can bring back to home if you don't understand about learning, learning theory. So let's go back to bandit theory, how does that work? So to simplify things, we just look at the original setup where you have the clinical trials, you are, oh, sorry. You have two treatments, the red one and the blue one, and you're a company and you want to know whether the best one is the red one or the blue one. Each time a patient arrives, you can give him the red or the blue one, and he will die or survive depending on the efficiency of your treatment. So how does that come? So here, let's say you have a bunch of patients that arrive one after the other one, okay, a line of time, each one is a patient. So you have the first patient that arrives. You don't know anything about your treatment, let's say you give him the blue treatment. And you wait for quite a long maybe, or let's say it's instantaneous, and you see that the guy died. So based on this information, you know that first guy, you got him the blue treatment and he died. You have to take another decision. So maybe you want to try the red one. So, but you only have this information. So let's say you try the red one. You wait a bit, and you see that that guy survived. So now you have the third patient that arrives. Based on this information, you say maybe the red one is better than the blue one. So you try again the red one. Patients survive again. Okay, fourth one, okay, maybe the red one, and here you see someone died. So now you have two options. Maybe, maybe indeed the red one is the best one, or maybe it's the blue one and you are not lucky. Maybe you killed the patient, but that was just bad luck. You know in statistics, it's hard to make a statistic based on one sample. So here based on this, you say okay, clearly sometimes the patient with the red treatment dies, and sometimes the patient with the blue treatment dies. So in order to know which one is the best, I might have to sample more the blue patient, the blue treatment. So for the next guy, you're going to take blue and see that he survived, and so on and so forth. But here's a message of that slide, here you have a sequential treatment, okay, sequential, you take sequential decision, and you can only base your decision based on what you saw. Here you can just, you don't know if the patient would have survived if you have given him the red treatment. You don't know that, you have no idea. Same thing here, you don't know if that patient would have survived if you have given him the blue treatment. So you are basing your decision only on the thing you saw. And this is the difficulty of the bandit literature, is you're basing all your decision on what you saw and not on what you didn't know. It seems trivial like this, but I mean, this is really important actually. And the objective is, as I said, is to save as many patients as possible. So typically here, if you put zero for people that died and one to people that live, then you want to maximize the number of success, the number of ones you received. So that thing here, you can easily see that this could be an ad, okay, that could be the blue ad and the red ad. And being dead means that you don't have a click. Surviving means that you get a click and you want to maximize the number of click because a click is money. So let's look at, there is a bunch of literature on this, a bunch of ideas, and let's look at how it works. I mean a way to solve that problem, to have an algorithm which makes sense. So let's look at what we call stochastic mutambenit, which are data IID. So let's say that, so this thing is following, you have, as we have saw in yesterday's talk, you have K actions, each time you have K actions, so you have K treatment you can sample from, okay, you have the treatment red, the blue one, but you have also, I don't know, the green one. So let's say you have K treatment. And you want to sample sequentially from those treatments. And at stage T, when you have the patient T that arrives, you can give him one of those treatments. And if you give the patient T the treatment I, you will get as a reward XT of I. So we, I mean, I used to assume that X of Y was either 0 and 1, but this is just a simplifying assumption. I can assume that they are sub-Gaussian, or actually Gauchan, that's irrelevant. Okay, so being 0 and 1 just simplifies the talk. So let's say that XT of OI, IID, so that's an IID process, of expectation mu high. So mu high is the probability that a patient survived, or the probability that someone clicked on your add. So of course, if you know those parameters, if you knew mu high in advance, so if you know that the treatment red is better than the treatment blue, you will give the red treatment to everybody, for sure. Unless you are, I mean, anyway. So if you knew mu high in advance, you will give to anyone the best treatment. Here, the thing is you don't know this mu high. The question is how can you learn which one is the best one without sacrificing, without killing too many people, or without losing too much money? So to do that, you're going to build a policy, as I show in the slide, a policy is just based on what I see either to choose the action red or the action blue. So you want to build such a policy that maximizes your reward, the expected reward, as we saw yesterday. So you want to maximize your expected reward. So that's the kind of stuff you want to do. And the maximum reward is, I mean, in expectation is the sum of mu Pt, where Pt is the treatment you give to patient T. So here is an issue with that formulation here, is that, as you can see, those mu can hold be arbitrarily big or arbitrarily small. There's no constraint on mu, there's no prior on mu. Okay, we are in a non-parametric world. We have no assumption on mu at all, it can be anything. So the thing is, if you have an algorithm that gets a lot of money, okay, let's say that's your expected money. And you say, well, after stage T, I got T rows. So I have a very good algorithm because I got one T rows every day. Maybe it does not mean that your algorithm is really good. You get T rows, it just means that all those parameters mu i are really big. And maybe the smallest mu i is actually one. All of them are bigger than one, they are all equal to two, except one, which are equal to one. And you are really happy of getting T rows where you could have got two T rows. So it's not because that number is big that you are found a good algorithm. It's not because you have a lot of money that your algorithm is good because you could have got even more money. And same thing, if you have, let's say at stage C, you have almost no money at all, okay, you just have epsilon T. It doesn't mean that your algorithm is bad. Maybe all the other options were even worse. So having lots of money or higher reward doesn't mean that your algorithm is good. And the same way around, if your total reward is bad, it doesn't mean that your algorithm is bad. So we have to normalize that number. And there is two ways to normalize that number, depending if you're from the learning theory or from the learning theory community or from the CS community. And so I'm from learning theory, so I'm going to use what we call the really great. The one is the competitive ratio. So the great is, well, you look at what you got. Okay, that's an expectation of your expected reward. And as I told you, if you knew in advance all those mu i's here, you would have given to all your patients the best treatment. And so this is the number of patients you would have solved. The expected highest number of highest expected reward you would have got, how do you know all those parameters? So this is what we call the regret is the difference between those two numbers. And this is just, I mean, why we call it regret is just because it's, I mean, the literal translation, literal sense, it's just the difference between what you could have got and what you got. Because just what I could have got, I had I known all those parameters, minus what I got. And now we are focusing on that notion of regret and we want to minimize this thing. We want to have a regret which is as small as possible. Yeah. Would you guess the other criterion? Yeah, sure. So let's, other criterion is instead of having this, this additive normalization, okay, where you're subscribed from your, from your, well, you're subscribed to the maximum your reward. The other one, which is the competitive ratio is just you divide, okay. And here, what you really want this to be as small as possible. And the other one, the competitive ratio is when you divide your, your, your, your cumulative pay reward by the optimal one, the maximum one. And you want this to be as close to one as possible. Okay. So this is called a competitive ratio. And yeah, I mean, there are some connections between them, but let's not enter into too many days. So this, this regret, as you can see, I can rewrite it using this formula, this formulation here. Well, I'm going to introduce a parameter delta i, which is just the cost of making a mistake. So the cost of making a mistake is, is just, oh, sorry. It's just the difference between the efficiency of the best treatment and the efficiency of treatment, if you, of the treatment i, okay. Delta i is the cost of prescribing treatment i instead of prescribing treatment star, the best one. So that thing, obviously, as you can see, can, the regret can only increase this time because that, that, that parameter here is positive. And those, those things are also positive. So you have the sum of positive numbers, we can only increase. In the worst case, of course, it will increase linearly. So the question is, can we find an algorithm which regrets we're going to increase because we have no choice. It has to increase. Okay, so increasing sum of positive numbers. But increase slowly, sublinearly, in the square root of t, or even in the log t, or even in constant. How can we do that? That's the question. And the answer is, well, the following. The most famous algorithm that does that. So here I'm going to say this is, I'm going to focus in non-athletic bounds. So I want precise, non-athletic, efficient bounds. There have been algorithms before that. But here, all those results are really precise in terms that you control everything. Okay, all those, all those, those inequality are really precise and are non-athletic. And while I'm here, this symbol here, smaller or equal than with a tilde below it, just means that I'm eating a constant. And a constant in my, in my community, a constant is a constant. A constant is two, okay? If you have like a k, k is not a constant, okay, it's a parameter. Or if you have, I don't know what do I have here. Delta, delta is not a constant. It doesn't change with time, but still it's not a constant. It's a parameter. Okay, a constant is two, it's pi, it's one million. Okay, I don't care. So maybe here, I've eaten one million or two. I'm not going to tell you. But that's what we call constant, universal constant. Okay, it's not a parameter. So there is this algorithm which is widely famous. It's called UCB for upper confidence bound. So the idea is the following. So I want to prescribe to my patient the best, the best treatment, the one which has the highest efficiency. Of course, so highest efficiency is the one with the highest mean. A very good proxy for finding, for computing the mean of a random process is to look at its empirical mean. But here there is something which is really interesting in online learning is that everything you know about statistics is incorrect. If you look at that thing here, the empirical average, and if you look at the expectation of that guy here, the expectation of the empirical average, well, you want to say that the expectation of the empirical average is equal to mu i. Okay, you want to say that. Because that's the first thing you learn in statistics. When you have a process, the expectation of that process is equal to its mean. By definition actually. But here it's incorrect. The expectation of the empirical average does not necessarily converge to the expectation, to its true expectation. Why, why is that? Why is that true? It's simply because, I mean, when you have the empirical average will converge to the true average, when the data you get are just received as is. So you say, okay, I have 1,000 data that are iid, and the expectation of those guys, of the empirical average on those 1,000 data are in, I mean, of course the expectation is mu i. But here those data are not iid. Because you choose to sample from the process i based on the previous data you received. So typically if in the past, the process i was really bad, bad behavior, when you're going to sample it less and less. So at the end, it might be the case that the expected empirical average does not converge to the true average. It's possible. So you have to be really careful. Stated otherwise, that guy here, the empirical average, is biased. It's a bias estimator of the true mean. So those are, so if you based your policy on a non-biased estimator, well of course your policy is going to diverge. You might not converge to the best one because you're looking at a bias estimator. So you want some hope to unbiased it, or to control the variance. And the way to do that is to add some error term, which is this one. So it's quite a lot of two log t divided by the number of samples you have. And this is called hyper-coffe-dazmone because it's linked to everything in the quality. I don't know if you know it. I mean, otherwise it's not really important. And the thing is that mu high is going to be really close to that guy of the empirical average plus the error term in the orange. But not necessarily close to the empirical average. So this guy here is a very good proxy for what the empirical mean could be. It's still biased, but it's less biased, yeah. So this correction is the limitless for x, the real one, and bounded by one. So here, this correction is indeed when x is bounded by one, or when there are sub-gauchan with a parameter one fourth, which is more or less equivalent to being bounded by one. Exactly. So if you know the variance of your parameter, sorry, this is one, but if you have a variance sigma square, you can have a bond here that involves sigma square. You're going to put sigma square over two. And if you don't know that variance, you can estimate it online and put here based on everything in equality. And if you're going to use an estimate of the variance, and you're going to use Bernstein inequality instead, and so you get sigma hat here. Okay? But here typically is just, this idea is just saying, well, with very high probability, actually with probability one over t to the fourth, new i is going to be smaller than that thing. Okay? Just to note, the fact that you have nothing, a thing bound is just because we made this assumption. If you have another type of process, you could make any per-competence bound here. As long as you have, all the results I'm going to say, are going to be true if you have exponential convergence. And so if you look, if you take this algorithm, if we call it UCB, well, you can show that your reglet is going to scale, is going to increase, of course, because it has to increase. But not that quickly. Actually, the reglet is not going to be linear, it's just going to be logarithmic. So your reglet is just going to increase as log t over the delta k, the sum of log t over delta k, which is, of course, much slower than t. So it means that if you compare, if you look at, let's say you are in a clinical field, if you could have saved all the patients, t, and you want to find out which one is the best one, you will just lose log t patients in the process, which is not that big. And if you look at this type of bond, here it depends on delta. So you might say, yeah, I want to have uniform guarantees over all the possible delta, all the possible cost of action, all the possible parameters. And if you take the maximum of that thing here, well, it more or less sums up to find this equation, and you can show that your reglet is bounded as a square root of kt log t. Of course, because here if delta goes to zero, this goes to infinity, but it's always going to be smaller than the square root of kt log t. So in any case, your reglet is going to increase as much as the square root of t, which is way smaller than t. And if your parameters are nice enough, then it will increase as log t. So that has been, so it's prepared, that's in 2002, so it's 15 years ago. And after that, there is lots and lots and dozens of different, even underwrites and thousands of papers and bandits following this trend, this trend of ideas. So the question I might ask is why, because it looks pretty simple. Actually, it is pretty simple. And you should just look at the proof. The proof is, I mean, it's two lines, so I'm just going to do it. Well, I'm going to lie in the middle, but still. So if you don't lie, it's like four lines. So let's look at the proof or just to give you some intuition. So we're going to look at our algorithm. The algorithm is going to sample, to prescribe the treatment i, which is not the best one. Under which condition? Well, based on this idea, it means that the score of our treatment i is bigger than the score of the best treatment. So it just means that the score of the treatment i, which is the empirical mean plus the error term, is bigger than the score of the best one plus its error term. I know if you just take that guy here and say, well, okay, here is where I'm lying, but actually I'm not lying. The empirical average is almost equal to mu star, and that guy is almost equal to mu high. So if I take that guy on the right part, I will get delta high. If I take that guy here, I'll get delta high. This one is bigger than one, so I can just remove it, and that one is going to be here. So I'm going to sample from i, more or less, when delta i is going to be smaller than that error from the error term. And just give me, if you invert this equation, the number of times you sample from process i increase as log t over delta i square. Okay, and this is the main idea of the proof. And then everything is like to line. And you can show that this is actually optimal. You cannot do better than this. In some sense, I'm not going to enter into this detail. But here's the idea of that algorithm and why I do like Bandit, because you can see the sitting is quite simple to explain. Okay, you have several processes for treatment. You want to give one to the other one. So you can make any other assumption, say, okay, what if we say, assume that this is possible, this is not possible, or whatever. And the proof are basically not that difficult. The most difficult thing is to find the right algorithm. Okay, to have the good idea. It's not like taking a mathematical hammer and hammering your equation until you, at the end, you get something which looks nice. Okay, it's just having a good intuition, which is, I mean, I think it's nice. So there are lots of algorithms that improve the right software, I've done some hope, I'm not going to enter into the detail. If you're interested, well, can you look at the slides that are going to be on mine. So here, I assume the data were IID. But in real life, for instance, if you look at your spam data, the mail you receive are not IID. Why is that? Because if you think again about the spam filter. So let's say you're building your spam filter. And there is an example about this. So you're building your spam filter. And what you're going to receive. So you receive an email. So the first, I guess the first spam was on Viagra. So you receive email saying Viagra. And it's quite easy to understand that when you have Viagra written in full letters in your mail, then this is spam. So the first spam filter say, well, if Viagra is here, then it's going to be a spam. But then the spam standard, people that are trying to sell Viagra, figure out that if they put Viagra in the, I should not say Viagra when I'm recorded. I should find a better example. And let's, anyway, it's too late now. So yeah, those guys figure out that you don't want to put Viagra in your mail. So just put v.ive.a.g.l.a. And then the spam filter say, well, this modified the distribution of data you receive. Because before you never saw this kind of string of letters with the point. And then, so it means that the data adapted itself to your own algorithm. Okay, so the data are not IID, they are adapting to your algorithm. You have, you make a decision and the data are adapt to that decision. And then same thing. So the spam filter say, well, v.i.etc is a spam. And it gets this spam. So it say, okay, I'm going to change my algorithm. Say this is not a spam. And then the spam standard say, okay, no, we have to change things. So just put lits, lits, lits, you know, you replace i by one and so on and so forth. And then you have this game between spam standard and spam filters where each one of them is adapting to their own strategy. So at the end we have, when you were looking at this multi-term bandit, you still have your action. So, okay, so you still have k action, one to k. But the thing is your process XIT are no longer IID. Because XT plus one, the law of XT plus one depends on how the past. So you cannot just say, you cannot use the last tool which are based on empirical process and only on the study of stochastic empirical processes. So you have to be more clever. The rate is defined as usual. You say, okay, I'm going to look at stage T. I'm going to look at what was the best decision, constant decision up to that stage. And you compare this, I mean, this is the amount of money of people you will have saved, how you were given to all of them with the treatment i. And you compare this to what you got. And this you want to minimize. This is closely related to convex optimization. So here you have, it's more or less convex optimization. So you can use tricks for convex optimization. I'm not going to enter into these details, but you have to mix, to use random strategy. As we saw before, you want to build unbiased estimator and so on and so forth. You can do that. So that's what we saw yesterday. We mentioned that estimator yesterday. It's important sampling estimator. So you have techniques to do that. But the main message is the last one. So if you're using this kind of algorithm, then you can show that no matter what the sequence of action is, okay? So the data you receive can be generated by an adversary, by another algorithm that is trying to screw you. Okay, so you're adding a spam filter. So you're trying to build a spam filter. And the spam standard are adapting to your algorithm, to your own algorithm. And no matter what your adversary is, no matter how strong it is, you regret is not going to increase linearly. You can find an algorithm so that you regret only increase a square root of t times K log k. So this is the very, actually, at first time when you think about it, it's kind of weird because you made no assumption at all on the process XTI, no assumption at all. And still you manage to learn which one is the best one without any assumption. And everything can change from one stage to another one. So it's kind of, it's not that easy to understand why it's working actually. If you think about it, you have no assumption on the data and you want to do as well as the best strategy, but still it's possible. And the idea, just in a few words, is actually just to compensate your losses. Okay, if at some time you have some losses compared to action one and you have some gains, so you perform better than action two, then you can compensate the surplus you get from action two to action one. So just a matter of compensating your loss and gains. But this is the idea, at the end, the thing is you regret only scale as square root of t. Which was the same, it was exactly, this was, except for the long part, but this was exactly the rates of the rate of error of the optimal rates of error in the stochastic case. So this means, actually, that if you look at it at this last line here, it means that the adversarial world, when you make no assumption at all on all the data you can receive and the data can even adapt to your own algorithm, this world is not more difficult than the worst stochastic case. Okay, so that was a 30 minutes course on Bandit. Okay, all you need to know about Bandit theory. So I'll just save you like 20 hours of my M2 courses. So let's go back to action. So remember, we have this problem here. How can we use this idea of Bandit in our auction problem? So we have, I mean, yeah, so we have this auction. So Le Monde is offering a slot to Creteau or Rocketfuel to put an ad on my webpage. And the question is from, the auction is second price. And the question is how can Creteau and Rocketfuel learn what they should be? So, the first question you might ask is, what is that second price auction? How come when you bid something, you're paying the second highest price? And the thing is, so there's this auction, we call it sometimes V-Cray auction, it has a really interesting mechanism, auction mechanism, because what we call it's truthful. And actually V-Cray, which in what you did, got a Nobel Prize for that. So let's say what the second price auction was. So you have a good, that is sell on auction. So it's either an ad like this, but it can also be, I don't know, like a boat or whatever. Or a painting. So each buyer is going to, so he has his price evaluation, so by your eye, things that for him, the good is worth V-high, that's his valuation, and he puts a bid V-high, okay? So that's a secret auction, closed auction, so he's only one, so just say, okay, I'm willing to pay, that's how much of money for, I'm willing to bid, that's how much of money for that ad or for that boat. And I think so, you gather all your bids, and the thing is, so you're going to look, the winner of the auction is going to be the guy with the highest bid, as I said before, which makes sense. Okay, because he's the one which wants the good the most. So the winner is B, so B-sharp, no, B-sharp is the one you're going to pay. So the winner is the guy with the highest bid, and he's going to pay the second highest bid. He's not going to pay his bid, he's going to pay the second highest bid, B-sharp. So why are we using this mechanism? It's because, as I said before, it's truthful. It means that your optimal strategy, no matter what your opponents are doing, no matter what you think they're doing, no matter what their valuation are, no matter what anything, your optimal action, you have nothing better to do than bidding your own valuation. Okay, if you think this boat is worth $100,000, then you bid $100,000. If you think that this auction is worth one cent, you bid one cent, and nothing more, nothing less. You cannot try to be a smarter, ever less and bid just a bit lower or a bit above to maximize your revenue, it makes no sense, for the following reason. So your utility, so what you gain, you're expecting gain is just, well, if you win the auction, if you don't win the auction, you get zero. Okay, you had zero before, you had zero at the end. So your utility is, if you win that auction, so if your bid is bigger than the second highest bid, you get V high minus the second highest bid. So now let's say you want to be a smart ass, and say, well, I'm going to bid more than my valuation. Okay, my bid is going to be bigger than my valuation. What might happen? Well, you might win the auction. Okay, V high might be bigger than V sharp. But if V sharp is bigger than V high, at the end you're going to pay more, you're going to pay something, you're going to pay more than the valuation of your good. So you're going to get a negative revenue. Well, if you had bid only V high, your revenue is always going to be, your revenue is always going to be positive. Okay, or equal to zero. Because V high is V high, so you're only going to pay something when V sharp is smaller than V high. So if you're trying to overbid, the only thing that could happen is, you will not have one detection with your bidding V high, your valuation, so you want the action, but you pay more than what is worth. So you don't want to overbid. And if you bid, oh, there should be a smaller, smaller than, if you bid smaller than your valuation, if you say, okay, I'm going to try to save some money, what might happen is just going to, you're going to lose that auction. And actually, if you think about it, since you pay the second highest price, the amount of money, if you win the auction, conditionally to the fact that you won the auction, the amount of money you're going to pay is independent of your bids. So the only thing that might happen is, instead of winning an auction and making a small surplus, you're going to lose that auction. So the optimal strategy is, it's always to bid your valuation. So in this, hard displaying, if you want to display an ad, the optimal strategy is, typically, to bid the probability that someone click on your ad. So you're trying to learn what is the probability that, so Crito is trying to learn what is the probability that I have on clicking on their ad. Okay, because if they knew that, if they knew that my probability is P, then they should bid P. So this, another guy got another, I mean, my son got another Nobel Prize because he improved the mechanism by allowing the seller to have a reserve price, which means that nothing is sold if there's no bid below the reserve price. And when it's sold, it's at least a reserve price, but that's a bit irrelevant. So let's look at our learning model. So, and we're going to place ourselves in the shoes of Crito or Rocketjoule. So we want to learn what is the probability that I have to click on the ad. Okay, they want to learn what is the probability that me or you, guys, is going to click on one ad. And to do that, well, they need some data. So they need to buy some data to learn what is the probability of clicking. So there's two ways to buy data. I thought you just say, okay, well, I'm going to buy 1,000 ad and look at what it is, as we said before, and then you just compute the array. Or you can do it in a more clever way. And let's look at the model. So we have several rounds, so that's all the actions. So we have action one because I arrive on Le Monde the first time, then the second time, the third time, so on and so forth, like T times. So they know that I'm going to be here for T times. Okay, I'm going to click on Le Monde, I don't know, like once a day, so like three times a day, so there is at least 1,000 options. Okay, so we know that, let's say we're going to fix T to be 1,000. So that's the number of ads that can be displayed and it's sequentially. Okay, so when ads T arrived, then each bidder, so each one of the companies we have seen before, so the Criteo, Rocketshul, Google, Yahoo, and many more, can place bid, BT, between zero and one. Okay, because that's typically the probability, they assume this is the probability of clicking. Okay? So if, so we are Criteo, okay, we are in a shoes on one of those companies, let's say we are Criteo. If BT, if our bid is bigger than the highest bid of our opponent, it means that we have the highest bid, then we win this auction. Okay? And what we paid is empty. And we get to observe, let's say a click. So you get to observe BT, the value, which is zero and one, can be even zero, it's either zero or one. Okay, let's say that BT is either zero or one, to simplify stuff. So at the end, our total utility that we got during this process is, well, we saw move all the action, so you look at all the action you have won, when our bid was the biggest one, our bid was bigger than the second highest one. And what we got is BT, so it's zero or one, depending if there has been a click, minus what we paid. That's our utility, and that's the thing we want to maximize. So I'm not going to do this pitch again, that this thing can be arbitrarily high or arbitrarily small, depending on your algorithm is good or bad, so we're just going to look at the regret to normalize that thing. So that in orange is the total amount of money we made. And in black here, it's the maximum amount of money we could have made had we always bid the same B. Okay, if we made a B, then we will have done that, that option if B is bigger than your second highest bid, and this is the money we will have made, BT minus empty. And we maximize this over B. And our regret is going to be the difference between those guys. So from here, I made no assumption on what's empty and BT are, whether they are stochastic, SIR or whatever, or those data are generated. So typically, BT is the value of a good, is the probability that I have to click on one ad. So typically, I mean, BT is whether it will click on the ad or not, and typically, these are stochastic. Okay, we can assume that the probability that I have on clicking on the ad won't change each day. Well, if I have, it's not true, but let's say it is. So that's the first option we can make. Okay, we can assume that the probability that I have to click on the ad is stationary, it's independent of time. And so the value of an ad for a criteria, which is BT, which is 0 and 1, whether I click or not, this is an idea process. Here comes the other part, empty, the second highest bid of my opponent. I can assume that this is stochastic, which means that my opponents are always going to bid the same thing. I mean, the bid is going to be constant with time. Actually, this is true. This is an assumption which makes sense, because when you look at it, when you look at data, it's almost true. So I have lots of anecdotes I want to share with you, but I don't have time, so if you are interested in this kind of stuff, go ask me at lunch. All you have to say is, well, I can assume that empty is not going to be stochastic, because our opponents are going to adapt to our behavior and so on and so forth. So empty can be anything, and I will be able to adapt to any sequence of bids. So that's a pretty cool adversarial. Okay, what's the second idea as in spam filtering. Anyway, in that case here, if you look at your, oops, if you look at the definition of regret, when you maximize that thing with b, and empty is independent on vt, which makes sense, the optimal is always attained when b is taken equal to v, your expected value. Okay, so the regret revised as this. Okay, that difference in black, you should have bet at each time v, and you bet inside bt, and this is your regret. The difference between what you could have got at most minus what you got. The other thing we could look at is the adversarial I'm not going to speak about it today, but you have slides so you can just look at it online, and it's when you make no assumption at all on vt either. So what are we going to do in a stochastic case? Well, as a algorithm we're going to use, it is based on UCB, it's a variant of UCB, that we call UCBid, because it's bidding on an upper confidence bond. And the thing is, our bid, we would like to bid the value v, but we know, so if you look at the empirical average of success, we know that that guy is biased. Okay, I told you that this is the bias estimate of v. So as before, we're going to add an error term, so that this is still biased, okay, but it's less biased. And so a negative, the number of auctions we want up to now, and this is what we're going to bid. And if we do more or less the same proof, where it's way more difficult because it's continuous, we have a continuous action and things are more difficult, we can prove using the same ideas that the regret is going to increase logarithmically in log t over delta. So the question is what is delta? Delta is the smallest interval between v and, so it's an interval between v and the smallest bid of open-end, which is above v. Okay, so it means that we have no bids between v and v plus delta. Of course, the thing, we don't know it. We don't know v and we don't know delta in advance. And if delta is, so if your open-end is nice enough, then your regret is going to scale on illogatmically. But delta can be as close to zero as it wants, if it doesn't want to be nice. And this thing can also prove that it's never going to be bigger than the square root of t. So we have an algorithm such that it behaves as so you can learn the optimal value of, you can learn the value of a, of a, and it can bid this value almost optimally. The only thing it's going to lose is square root of t, the factor of square root of t, which is, which is admissible. And if your open-end is nice, nice enough, then it's log t over delta. So I think delta, I said it can be small, but if our open-end is like playing stochastic, maybe the probability that that bid fall in that interval is going to be really small. And we can control this using some margin condition. So I'm going to spare you the details, but we can interpolate between, we can have some continuous interpolation depending on the strength or the badness or opponent between the slope t and the square root of t. Okay, there is this parameter, alpha, that interpolates between those two. How much time do we have? Like it's over? Okay, I only have one minute. Perfect. So that was the take-home message from the slide, is that we can interpolate between this fast rate of log delta and the rate of square root of t. Now, as I said, we also have another algorithm for when the data are, we made no assumption of the data in the adversarial case. I'm not going to describe it. And same thing, we get a rate of adjunct in square root of t. And all the results are, I see the constant are exact, here it's a four. And they are all more or less optimal up to log term because we can show that you cannot build an algorithm which is better than this. Okay, there are always a way to screw any other algorithm. That's the summary of our results. So let's remember we had a whole this multi-ambient theory that is 15 years old now. And we adapted it to these sequential auctions. And thing is, so our action space is no longer finite, but in finite, it continues between 0 and 1. And we still got to manage to get rates of adjuncts as scale as square root of log t, as log t or square root of log t, which was quite surprising actually. And even if you look more in detail into those bones, if you're used to them, you can see that there's some really, really interesting stuff going around. So I'm not going to speak about this because I don't have time. Same thing, it's online. But I would just to say that this is, I find this very interesting. Maybe for you it's just quite interesting. Anyway, all goes, all takes our nature. But can we use them, I mean, as it is in real life, so question, the answer is obviously no because there's many, many issues. Here we made lots of assumptions that are not satisfied in real life. So there's lots and lots of works to do before we can apply directly those ideas into the real life problem. And of course, if you are interested into doing that, well, please come see me and we can discuss all of these issues. And they are described after, I mean, there is a bunch of remaining slides here, but it's just for online. So I just want to finish that talk with two announcements. There is 10 hour lectures by Tim Hofgarden from Sanford on auction, data driven optimal auction. So this is going to be in pre-technic, so in late September. And at Crito, we're organizing what we call a machine learning and a reward workshop, probably on the 21st of November. And if you have any questions about any of those events, please come to, come ask me for answers. Thank you. Thank you. One or two short questions? I'm not any specialist in this, but I was wondering, in the auction case, can you take into account some kind of internal information or privileged information, like for example, some auctioners are being given information by the organizers. Is it possible to take these kind of things in account? So actually here, that's the question, oh, you heard it. So in this kind of, I mean, that's in a, I want to say in real life auctions, when you're trying to say, to buy a painting or a boat or a house or whatever, there is some private information that tells you what is the true value of this goods you're trying to buy. And here you want to leverage it and see, and if you see what is the other one that you're buying, then it, I mean, modifies your building strategies. But here actually, something which is really different, when you have a user that arrives, the value for Creteo is totally different from the value is independent of the value for Rocketfuel. For the simple reason that Creteo has some clients, so as I say, there was Microsoft, and Microsoft is going to booking, but here is the ad for Microsoft, and Rocketfuel has the ad for Air France. And of course, Air France is not going to ask two re-targeting companies, that's Creteo and Rocketfuel, to manage their company. So only one company is advertising for Air France, only one of them is advertising for Microsoft. So at the end, we have this ad for Microsoft and the ad for Air France, and the probability of clicking are totally independent. Well, almost independent. So the information that Rocketfuel has on me, whether I'm going to click on the ad for Air France, it is not going to be helpful for Creteo to determine which is the probability that I have on clicking on its ad. So the private information in that case makes less sense that if you have a common value of the good, which is typically when you buy a house, it has some price, which is the market value of that house, and everybody has a different signal about it. And you're trying to gather this signal and try to find the optimal price of that thing. But here, we are really in a case where the good that I sold has a different value for everyone. So having private information and trying to leverage it makes sense, but it's just using the data you have and trying to be, because here I just say that we don't gather any data on the user, just saying, well, it's always the same user with the same stochastic probability. But then actually, this is not true because my browsing history will depend on Creteo or Rocketfuel has some private information about my behavior, and of course, they are leveraging this to update their, the probability of clicking. But yeah. So I was wondering about the, so here you talk about the expected regret. So I was just wondering what is the behavior of the regret pathways? So do we have any, is there any control pathways on the regret like, well, to know if the scaling like square root t of log t is something just available in mean or also on the full distribution of the regret? No, you can, so this algorithm actually just working for expectations. So it just in mean you have this kind of regret. Sometimes it can be linear, sometimes it can be smaller. But you also have a variance of those algorithms that take that into account and you can show that you can put some probability and say, okay, I want to have this, I mean, some high probability version of those results. Okay, instead of having square root of t log t, you can replace some t by one over delta. Where delta is the probability you want to control. Typically, you can do that. But that's, you just have to modify a bit your algorithm. It seems very similar to the original truth just that the variance can be in one DOWNREST quantity. That's, that's a really small chance that the probability of thislied set of 3 is not a factor that people can use籌 because in real world,
declined. Nobody really cared about bandits. multi-impeded had a new application. And the motivating idea of this talk. And this problem that talk, I did that. And you can see that if Therefore, for some reason for that, I will a simplifying assumption. I can assume that they you're from the learning theory or from the what you got. Because just what I could have got, possible. And the other one, the competitive really precise in terms that you control constant. A constant is two, okay? If you have you know about statistics is incorrect. If you say you are in a clinical field, if you could all the possible parameters. And if you take the you should just look at the proof. The proof is, better than this. In some sense, I'm not going to optimization. I'm not going to enter into these we are in a shoes on one of those companies, machine learning and a reward workshop, probably you. One or two short questions? I'm not any available in mean or also on the full