I am trying to use VW to perform ranking using the contextual bandit framework, specifically using --cb_explore_adf --softmax --lambda X. The choice of softmax is because, according to VW's docs: "This is a different explorer, which uses the policy not only to predict an action but also predict a score indicating the quality of each action." This quality-related score is what I would like to use for ranking.
The scenario is this: I have a list of items [A, B, C, D], and I would like to sort it in an order that maximizes a pre-defined metric (e.g., CTR). One of the problems, as I see, is that we cannot evaluate the items individually because we can't know for sure which item made the user click or not.
To test some approaches, I've created a dummy dataset. As a way to try and solve the above problem, I am using the entire ordered list as a way to evaluate if a click happens or not (e.g., given the context for user X, he will click if the items are [C, A, B, D]). Then, I reward the items individually according to their position on the list, i.e., reward = 1/P for 0 < P < len(list). Here, the reward for C, A, B, D is 1, 0.5, and 0.25, 0.125, respectively. If there's no click, the reward is zero for all items. The reasoning behind this is that more important items will stabilize on top and less important on the bottom.
Also, one of the difficulties I found was defining a sampling function for this approach. Typically, we're interested in selecting only one option, but here I have to sample multiple times (4 in the example). Because of that, it's not very clear how I should incorporate exploration when sampling items. I have a few ideas:
- Copy the probability mass function and assign it to
copy_pmf. Draw a random number between 0 andmax(copy_pmf)and for each probability value incopy_pmf, increment thesum_probvariable (very similar to the tutorial here:https://vowpalwabbit.org/tutorials/cb_simulation.html). Whensum_prob > draw, we add the current item/prob to a list. Then, we remove this probability fromcopy_pmf, setsum_prob = 0, and draw a new number again between 0 andmax(copy_pmf)(which might change or not). - Another option is drawing a random number and, if the maximum probability, i.e.,
max(pmf)is greater than this number, we exploit. If it isn't, we shuffle the list and return this (explore). This approach requires tuning thelambdaparameter, which controls the outputpmf(I have seen cases where the max prob is > 0.99, which would mean around a 1% chance of exploring. I have also seen instances where max prob is ~0.5, which is around 50% exploration.
I would like to know if there are any suggestions regarding this problem, specifically sampling and the reward function. Also, if there are any things I might be missing here.
Thank you!