1
$\begingroup$

I am solving a problem for which I have to select best possible server(level 1) to hit for a given data. These server(level 1) in turn hit some other servers(level 2) to complete the request. The level 1 servers have the same set of level 2 servers integrated with them. For a particular request I am getting success or failure as response.

For this I am using Thompson Sampling with Bernoulli prior. On success I am considering reward as 1 and for failure it is 0. But in case of failure I am receiving error as well. In some error it is evident that the error is due to some issue at server(level 1) end and hence reward 0 makes sense but some error results from request data errors or issue at level 2 servers. For these kind of errors we cant penalize the level 1 servers with reward 0 nor can we reward them with value 1.

Currently I am using 0.5 as reward for such cases.

Exploring over Internet I couldn't find any method/algorithm to calculate the reward for such cases in a proper(informed) way.

What could be the possible way to calculate reward in such cases?

$\endgroup$
3

1 Answer 1

1
$\begingroup$

If I understand well, server 2 errors happen independently of server 1 choice. Hence, when you receive server 2 errors it means that any action (any choice of server 1) would have fail.

If it is the case, I would update all the arms (actions) with a "0" reward sample. Indeed, when server 2 fails, it means that any arm would have failed. Hence, you are in a full-information feedback (that is, you know the reward for all the actions) and not in a bandit feedback (you see only the reward for the action you have selected). An alternative view would be to ignore these samples (that is, not update TS values and behave like this sample do not exist).

Indeed, adding 0.5 may bias your reward, especially if the error rate for server 1 is very close to zero or one. Think about a perfectly fine server which never fails. Adding 0.5 will bias its reward so it could be comparable (for a bandit algorithm like TS) with a server which has a small probability a failure (e.g. 10%).

If you really want to add custom reward: you can switch to UCB algorithm (which is designed for subgaussian/bounded rewards) or to TS with another prior (for which 0.5 reward makes sense, like gaussian).

If you really want to add your custom reward AND stick to TS with bernoulli prior (I would not do that), then you could add "0.5" to your parameter a and b and then round them when it comes to sample the beta distribution (with a and b values). (I am using the notation of your article).

Last remark, it seems that your setup is indeed bandit but are you sure it is stationnary? That is, reward are independent samples from the same distribution (the core assumption behind TS or UCB). For instance if you get for an arm: "11111111111000000000000011111111", it is probably not independent, and you should consider exploiting this non stationarity.

$\endgroup$

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.