2
$\begingroup$

Let's say Morpheus has multiple users to offer colored pills(from an infinite set of colored pills), there are in total 3 unique colored pills(red, blue, green) Morpheus can offer. The trick is, Morpheus can offer only one pill to a user and the user has a choice to either take the pill or deny it. (Also, user's decisions are independent of each other)

Now Morpheus wants to be smart about his offer and wants to model the user such that the user selects the pill he is offering. The users are moody and there is some uncertainty that they would randomly take a choice.

Rejection can be because of multiple unknown reasons such as I didn't like the color of the pill, I will choose the pill later, I want to understand more about this pill, Show me other pills before I decide

Now there are two ways I can think of modeling this:

  1. Treating this as binary classification
  2. Treating this as multi-class classification

When I treat this as binary classification, I pass pill color as feature with other user features to the model, and my output is the probability of user taking or rejecting a pill given the pill color. Morpheus can then offer the pill color with the highest probability. This will use both Accept and Reject decisions of a user while modeling, but there is some uncertainty and the same type of users can accept or reject randomly.

When I treat this as a multi-class classification, where I try to predict the pill color itself. I would not use the rejected case in my training and would only consider cases when the user chose something. In this way, I can reduce uncertainty in this case but would have to completely ignore rejected cases. Morpheus then can either use softmax or sigmoid for each class and take argmax to get the best choice to offer.

I am not sure if there are other ways to model this problem, but out of these two which can be a better way?

pills

$\endgroup$
6
  • $\begingroup$ Do the Neos accept/reject sequentially? In other words, If Neo1 accepts the first pill, are there only two pills left to propose to Neo2 and Neo3? I'd assume so, because the alternative is that all actions happen simultaneously, which can lead to two Neos picking the same color (unless I am misunderstanding the problem). $\endgroup$ – Benji Albert Jul 19 '20 at 20:51
  • $\begingroup$ All Neos are independent and can be presented same color. You can consider that Morpheus has infinite pills of all three colors. The problem is what color Morpheus should offer such that most Neos take the pill and do not reject. $\endgroup$ – puneet Jul 19 '20 at 21:05
  • $\begingroup$ If they are entirely independent, what is the purpose of considering multiple users? $\endgroup$ – Benji Albert Jul 19 '20 at 21:09
  • $\begingroup$ I don't follow. I can't recall where I mentioned that I am considering multiple users for the model. All I want to provide Morpheus with best choice to offer an individual Neo. So that overall maximum number of Neos take the pill and do not reject. $\endgroup$ – puneet Jul 19 '20 at 21:14
  • 1
    $\begingroup$ That line simply means that there are multiple Neos, to which Morpheus has to offer a pill. I'll change this to be more explicit. Although choice is independent but from Morpheus perspective he will measure his success over all the Neos $\endgroup$ – puneet Jul 19 '20 at 21:19
3
+50
$\begingroup$

This is a textbook multi-armed bandit problem where Morpheus needs to learn the correct policy about offering pills. As you’ve said the Neos are independent, and making the assumption that there is a best pill overall, we need an algorithm that will experiment with each of the pills to find out which one is most likely to be accepted. This is the same as having three one armed bandit slot machines and trying to find out which one will pay out most frequently.

In the case where the Neos are observable (so that we have some information about each Neo and can predict what pill they would like based on their characteristics) this becomes a contextual bandit problem. This is the basic form of reinforcement learning problems

In a contextual bandit problem, you need to balance exploration (trying out offering different pills to different Neos to find out what they like) with exploitation (choosing what seems to be the best pill based on what we saw so far). This is why straight-up supervised multinomial classification approaches (as in e.g. Benji Albert’s answer) will struggle to converge: they don’t explore the “action space” (i.e. try out a bunch of responses) sufficiently in order to generate a variety of training examples for themselves.

$\endgroup$
11
  • $\begingroup$ "Best pill overall" ... I would say although Neo's choices are independent but, they might have some underlying reason. So it will be more like "Best pill for this particular Neo" $\endgroup$ – puneet Jul 19 '20 at 22:44
  • 1
    $\begingroup$ Updated my answer to include the case where we might be able to learn to guess what pill to offer based on what each Neo looks like 👍 $\endgroup$ – Nicholas James Bailey Jul 20 '20 at 6:49
  • $\begingroup$ I don’t agree with your concerns about reinforcement learning, but I don’t have enough space here to go too deeply into them. Supervised algorithms like the one you’re suggesting will struggle to converge without a policy to help them try out what might seem like non-optimal solutions based on the examples seem so far. This is because this is a bandit problem, so unlike in supervised learning the answers your model generates will not be corrected to help it learn. You have to generate your training data by purposefully seeking to generate surprising reactions from Neo. $\endgroup$ – Nicholas James Bailey Jul 20 '20 at 13:18
  • $\begingroup$ Maybe you could open a question about reinforcement learning if it’s not clear why it works better than supervised approaches for bandit problems? $\endgroup$ – Nicholas James Bailey Jul 20 '20 at 15:05
  • 1
    $\begingroup$ Up to a point reinforcement learning algorithms can work well, but as I’m sure you can intuit highly stochastic environments (those with lots of aleatoric uncertainty) need even more exploration vs exploration as some experiences will be misleading. Here’s a cool paper from a few months ago: arxiv.org/pdf/1905.09638.pdf $\endgroup$ – Nicholas James Bailey Jul 20 '20 at 17:18
0
$\begingroup$

In your specific case our test "Neos" may not take a pill at all since Morpheus only offers one pill of a specific color.

We would have to either amend our multi-class model to include "No color / Rejection" or the binary model would work much better.

From a practical stand-point I would use a multi-class model here for one simple reason:

It is the only one that straigh-up solves Morpheus use case!

If we design a binary model with pill color as a predictor we would have to then run the model three times (with the persons data and each pill color), compare the prediction of acceptance and choose the best outcome whereas a multi-class model simply tells us the pill color with the highest acceptance likelihood.

Now from a theoretical stand-point we also have to consider that the classes are presented independently of each other unlike in the movie. One color only is presented and users do not have knowledge of other colors so no relative preference is build. The context of the decision therefore is a bit closer to the binary model.

However in the end as in all prediction cases, performance wins. So I'd simply build both models and compare performance.

$\endgroup$
4
  • $\begingroup$ Thanks for your answer! I didn't want to add Rejection label to multi-class because Morpheus has to offer at least one color, and the idea is whatever color Morpheus will offer should have the highest likelihood of "Neos" selecting that color. So theoretically adding Rejections would give me what advantage over just adding the positive classes i.e. picked colors? $\endgroup$ – puneet Jul 17 '20 at 17:03
  • $\begingroup$ Since rejections are an actual valid response omitting them would lead to a worse performing model. In theory a model that doesn't know that rejections are possible could lead to worse suggestions of color than a multi-class model which includes rejections as well as a second choice. But to be frank I can't say for sure. $\endgroup$ – Fnguyen Jul 17 '20 at 17:21
  • $\begingroup$ I hear what you are saying, but what would a model whose highest probability spits out "Reject" mean in this situation? Morpheus would still need to give a choice of a pill. From Morpheus' perspective, he has to offer at least the best possible pill that the user might take. $\endgroup$ – puneet Jul 17 '20 at 23:10
  • $\begingroup$ Yes but the question here is whether the second highest probability choice of a model which includes rejections is better than the highest probability choice of a model which doesn't. $\endgroup$ – Fnguyen Jul 18 '20 at 7:54

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.