I am currently reading the paper "Learning from Logged Implicit Exploration Data" https://arxiv.org/pdf/1003.0120.pdf. But I believe the questions I have can be answered without reading the whole paper, so I would greatly appreciate it if you help me.

The paper considers a contextual bandit problem and wants to do the offline evaluation of a new policy when the logging policy is unknown and thus could be deterministic so that we can't just apply inverse propensity score.

I have 2 questions about the part below. enter image description here

  1. why can the situation explained be treated as randomizing between actions $a$ and $b$? I understand it is assumed that the number of events is the same each day and the events are IID. But then does that mean it is randomizing because the action that is called action $a$ could have been called action $b$ and used on day 2, instead of day 1? The whole situation is deterministic, so I don't understand why this can be viewed as randomizing.

  2. So the definition of $\hat{\pi}(a|x)$ is simply (the number of the action $a$ displayed given the feature $x$/the total number of actions displayed$)?

Thank you!


1) As far as I could figure, the point in (1) is to give a reasoning on why you could treat it as a random selection process. They give an example where the day might not be part of the context they want to consider (for example - the algorithm had a chance to choose differently, but didn't). In general, if everything is deterministic, then at each context you will get just a determined bandit, and won't be able to correct the selection bias.

2) $\hat{\pi}(a \mid x)$ doesn't have to be the specific estimator you described. It can work with any estimator of $\pi(a \mid x)$ (for example - multinomial regression, if you believe that it was the way the bandits where chosen). Note that bad estimators for $\pi$ would yield bad estimators for the policy performance.

| cite | improve this answer | |
  • $\begingroup$ Thanks! I just need little bit more clarification. 1) You said "They give an example where the day might not be part of the context they want to consider". Does it mean that without considering the day, the situation could be either (a, b) or (b, a), so the probability is 1/2? $\endgroup$ – Hunnam Jul 30 '19 at 0:21
  • $\begingroup$ Yes, but they sort of deduce it from the data - they saw $a$ once and $b$ once, and therefore attribute 0.5 chance for either. That's the reason for the end of the comment - when the number of events is the sameeach day, and the events are IID $\endgroup$ – tmrlvi Jul 30 '19 at 0:26
  • $\begingroup$ 2) I am an undergrad who has no statistics background (currently self studying), so I don't know what multinomial regression is (of course I can google it). You mean here that there are ways that make it possible to estimate the probability of a deterministic policy? I don't understand how it can be possible because the probability of a deterministic policy choosing an action is either 0 or 1... it seems like this must be explained by 1), but my bad understanding prevents that! $\endgroup$ – Hunnam Jul 30 '19 at 0:27
  • $\begingroup$ Ok, so when the assumptions are satisfied, then we are able to treat the data as being randomized. Is this right? And we just apply this reasoning when we work with the estimator of $\pi$, no matter which one we are working with. $\endgroup$ – Hunnam Jul 30 '19 at 0:30
  • $\begingroup$ 2) In essence, there are stochastic policies that are "close enough" to the deterministic one. Rigorously, this is treated by Corollary 3.1. Note that the "close enough" is capture by both the regret and the threshold $\tau$. $\endgroup$ – tmrlvi Jul 30 '19 at 0:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.