Off-policy evaluation of reinforcement learning: How to compute importance weights

I am working on a project that will use reinforcement learning to recommended products to customers in a mobile app. We have a few years of historical data available, which I would like to use for evaluation.

I would like to do what they are doing in this paper: https://www.ijcai.org/Proceedings/15/Papers/257.pdf

Specifically, I want to compute the importance weighted returns given by: $\hat{\rho}(\pi_e|\tau_i, \pi_i) = R(\tau_i)\prod_{t=1}^T \frac{\pi_e(a_t^{\tau_i}|s_t^{\tau_i})}{\pi_i(a_t^{\tau_i}|s_t^{\tau_i})}$

where $\pi_e$ is the policy to be evaluated, and $\pi_i$ is the policy that generated the data. $R(\tau_i)$ is the reward of the trajectory $\tau$. $a_t$ is the action at time t, and $s_t$ is the state at time t.

Now, my question is:

How do I compute $\pi_i(a_t^{\tau_i}|s_t^{\tau_i})$ ?

In the paper, this is not explained, so I suspect the solution may be simple. I just don't understand exactly how this distribution should be estimated given the historical data.

If anyone has an example of code that does this, or just an answer to the question, it would be highly appreciated.

Thanks,

Esben

• Could you also explain in your question what the remaining terms of the equation (a's and s's) represent?
– mkt
Jul 25 '17 at 12:18
• They are the states and actions - I have added that to the question. Jul 26 '17 at 6:33

It's likely that in the paper, that $\pi_i$ is supplied by the agent during active learning. When used for optimal control, for example, it is common to use an $\epsilon$-greedy policy for behaviour and deterministic greedy policy for the learning target.

For offline learning, it is still common to work with a known policy, such as simple equiprobable action selection. Again in this case the behaviour policy is known by design, it is not constructed afterwards from the data.

As the main objective for importance sampling is to weight trajectories from observation to target policy, you may suffer from sampling bias if use the same observations to estimate behaviour policy and weight sample returns.

You might be able to estimate an effective behaviour policy from your data, but that would probably cause problems with variance and maybe also bias, especially if it is not essentially true that the history is from a single policy. Off policy learning already suffers from larger variance than on policy. I have not ever tried estimating a behaviour policy from data like this, so I cannot say for sure whether it would not work, just I have concerns.

However, you may have to give up on the idea of importance sampling. That does not prevent you using an off-policy approach. You could for example use single step Q-learning, with experience replay sampling from your history. This will learn from the state transitions and rewards that you have stored, and will not need any data from the behaviour policy. What you may not be able to do is any multiple step algorithms such as Q($\lambda$), because these need longer trajectories.

• Thank you for the reply. In the paper, some of the historical data was generated by following a random policy. In that case $\pi_i$ just picks a random action from the action set, regardless of state. However, my historical data is generated using many different ad hoc approaches, so not random. I would assume that this is a normal case, so I would think it should be possible to estimate an effective behaviour policy. I just haven't seen an example. Jul 26 '17 at 6:38
• Yes I was just reading your question again, and wondering about your scenario. If your recommendations were generated randomly, then you may have a similar situation. In which case you could have a simple value for $\pi_i(a|s) = \frac{1}{|N|}$ for all states, which would be fine if you had history for N Jul 26 '17 at 6:45
• However in the case you have, you have lost the policy data, so cannot really use it. I'm not aware of any standard approach to reconstruct it. Jul 26 '17 at 6:49

This is not a complete answer, but I feel like the previous answers misunderstood your original question. I think this will provide you with the necessary tools you need to implement what you desire. First, refer to this paper:

https://homes.cs.washington.edu/~zoran/orderingpaperExtended.pdf

If you look at section 7.3, they reformulate what you have written as optimizing the expected reward, conditioned on the policies, in terms of a weight $\theta_a$ associated with action $a$ . You can then implement a log likelihood method to find the optimal action sequence. If you're wondering where time comes into play, see below.

More concretely, write the expected reward as:

$$\hat {\mathbb{E}}\left[ \sum_{t=1}^T r_t \lvert \pi_p \right]= \sum_{t=1}^T \frac{1}{m} \sum_{i=1}^m \frac{\prod \pi_p(a_{i,1}, \cdots, a_{i,t} \lvert h_{t−1,i})}{\prod \pi_q(a_{i,1}, \cdots, a_{i,t} \lvert h_{t−1,i})} r_{t,i}$$

Then use the softmax prior for some unknown weight $$\theta_i$$:

$$\pi(a_i | h_{t−1,i}) = \frac{ \exp( − \theta_i^T \cdot \psi_t)}{\sum_{a_j} \exp(−\theta_j^T \cdot \psi_T)}$$

Feel free to comment/message me if you would like to know more details, but I think this paper has all of the ingredients you need.