In a contextual bandit problem, why can't we use inverse probability weighting (inverse propensity score) with a deterministic policy as the logging policy? Could you give me a concrete example?


Consider a coin-flipping experiment, where we first select a coin (context - $x$), flip the selected coin to receive an action $y$ (head or tail) and finally, based on the context and the action, we receive a reward $\delta(x,y)$. The reward function $\delta(x,y)$ is not known and it is observed only through the experiment results.

Intuitively, we cannot learn from a deterministic policy (that is the coin toss would always return either head or tail for a given coin), because we would never observe the reward for the unseen action - that is the policy does not explore at all.

The IPS estimate tries to estimate the reward received by a logging policy $\pi_0(y|x)$ if we would use an alternative policy $\pi_A(y|x)$ instead of $\pi_0(y|x)$. In our setup, it means that we $N$-times choose a coin ($x_i$) according to some $p(x)$, flip it and based on the coin-flip result $y_i$ (according to $\pi_{0,i}=\pi_0(y=y_i|x=x_i)$) receive a reward for given context and action $\delta_i=\delta(x_i, y_i)$. Thus we have available a collection of tuples $\{(x_i, y_i,\delta_i, \pi_{0,i})\}_{i=1}^N$.

To answer the original question, we consider the IPS derivation as $$ R(\pi_A)\stackrel{(a)}{=}\mathrm{E}_{x\sim P(x), y\sim \pi_A(y \vert x)} \left[\delta(x,y)\right] \stackrel{(b)}{=}\mathrm{E}_{x\sim P(x), y\sim \pi_0(y \vert x)} \left[\frac{\pi_A(y \vert x)}{\pi_0(y \vert x)}\delta(x,y)\right] \\ \stackrel{(c)}{\approx} \frac{1}{N}\sum_{i=1}^N \frac{\pi_{A}(x_i \vert y_i)}{\pi_{0}(x_i \vert y_i)} \delta_i = \hat{R}_{\mathrm{IPS}}(\pi_A), $$ where (a) is the definition of target estimate, (b) is the crucial step for the IPS derivation, where we switch the expectation over $\pi_A$ to expectaion over $\pi_0$. One can see that division by zero occurs if $\pi_0(y|x)=0$ for some $x,y$ (among others, a deterministic $\pi_0$ leads to $\pi_0(y|x)=0$ for some $y$). Monte Carlo approximation is used in (c), where and it basicly aproximate the expectation by empirical mean. Thus we shown that IPS gives an infinite reward estimate in case of deterministic $\pi_0$ that obviously makes no sense in practical applications.

| cite | improve this answer | |

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.