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
 A: 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.
A: 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.
