1
$\begingroup$

I have a game that I would like a neural network to teach itself. In the game there are an infinite number of initial states and the agent can then take one binary action, which will give him a reward or a punishment (of variable amount, which can be deduced from the initial state of the game). After each move, the game is reset.

Is this a problem that might be suitable for reinforcement learning?

I'm asking because it appears to me that a simple backpropagation cannot solve this problem accurately, or at least it's not clear to me if such a loss function with asymmetric payoffs, combined with binary crossentropy could work.

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ This sounds like a bandit problem to me, which is generally more manageable than RL anyway. $\endgroup$ – Dougal Jul 10 '18 at 16:06
  • $\begingroup$ In my case the payoff is known in advance, not sure this is the case in the bandit problem $\endgroup$ – Nickpick Jul 10 '18 at 16:23
  • $\begingroup$ Oh, I guess I misunderstood. I don't understand then: what's the goal of your learning problem? To predict the reward given your initial state? $\endgroup$ – Dougal Jul 10 '18 at 16:25
  • $\begingroup$ Yes, given some explanatory variables, the actor needs to take the correct action. If the action is correct, the actor is rewarded with a known variable payoff. If he is incorrect, it's a known variable punishment. The goal is to maximize the payoff. $\endgroup$ – Nickpick Jul 10 '18 at 16:26
1
$\begingroup$

Your description most closely matches a contextual bandit problem. It looks like you can also make some simplifying assumptions that will make the agent more effective than in the general case though.

In comments you are concerned that because you already know the reward or punishment structure, that it is not a bandit problem.

However, that just means you can take advantage of the knowledge to construct better expected rewards once you have sampled the correct action. A contextual bandit solver will still solve an environment where correct actions deterministically score +1 and incorrect actions score -1. In your case, if you are able to analytically calculate the expected reward or penalty, then you can use that value instead of the sampled reward, and that should help with speeding up learning.

In order to collect data to learn the game you will need to make some initial exploratory action choices. Once the results of these actions are known, the agent may start to have a better than random chance of choosing the correct action.

What you will be hoping for is after each new piece of data, the agent will be able to generalise from states it has seen to new unseen ones and choose the correct action. To help with this, you may be able to take random mini-batches of recent history and use them to repeatedly train a neural network (or other function approximator) in order to predict the likely rewards from each action.

In essence this is very similar to online supervised learning, using data you are collecting during playing the game to train a regression model. The model can either take state as input and return two values (one prediction for each action), or can take [state, action] pair and return the prediction for that combination.

Given your description, I think you can probably get away with a simple greedy action selection - just choose the action that predicts the best expected reward at each step.

I would also suggest that you can use some percentage of the data you collect as a hold-out cross-validation set too. That could help you tune the amount of training to apply between real actions - this is critical because you want to generalise to new states and not overfit.

It is not 100% clear from your description, but if the action not taken would always have the reverse effect to the one taken, and you would know the reward from that, then you can use that data too - simply add it to the history that you sample from in order to process updates.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Just optimising over the best action definitely does not lead to an optimal payoff. Also in your link it makes reference to LinRel (Linear Associative Reinforcement Learning) algorithm. So reinforcement learning after all, but just with one step? $\endgroup$ – Nickpick Jul 11 '18 at 11:50
  • 2
    $\begingroup$ A contextual bandit is essentially RL without time steps. The missing time and evolution of the state is a big difference in practice though. You can apply RL algorithms in your case, just many of them (such as Q Learning) will be inefficient. $\endgroup$ – Neil Slater Jul 11 '18 at 13:02
  • $\begingroup$ I do have a large sample set of states and correct actions with their respective payoffs of the confusion matrix. My problem really is that a classifier is not enough, it needs to weight all outcomes in the confusion matrix to optimise the payoff. I couldn’t find any way to do that so far. Just using weights for individual samples doesn’t work, because true positive, true negatives, false positives and false negatives all need to be weighted differently for every sample. $\endgroup$ – Nickpick Jul 12 '18 at 0:01
  • 1
    $\begingroup$ @Nickpick: Given that you say the expected payoffs can be calculated directly from the state, then a classifier that gives a confidence value $p(class)$ should be adaptable to give expected rewards. Using a contextual bandit solver framed as a regression is pretty similar to that - the difference is that it should resolve directly to the expected rewards. IMO the classifier would be more robust in your case since you say you have a reliable way to calculate the expected reward from the state (and whether the class is correct). But they are both estimating the same thing. $\endgroup$ – Neil Slater Jul 12 '18 at 7:05
  • 1
    $\begingroup$ @Dougal: I agree. I was suggesting a classifier that output confidence would need to be paired with a risk/reward model based on expected rewards depending on whether the classifier was right or wrong. The OP claims that they can calculate the expected rewards directly and accurately from the state. $\endgroup$ – Neil Slater Jul 12 '18 at 19:52
0
$\begingroup$

This doesn't sound like a good fit to reinforcement learning for me. RL algorithms have to learn how their actions affect the world, what the payoffs for your actions are, and how to do long-term "credit assignment," etc., none of which are aspects of your problem.

Instead I'd recommend something like: learn a regression model from the state to the reward. Then take your action if the reward estimate is positive.

This is (maybe) better than just training a classifier, because it gets stronger signal in cases where it should really really be positive. You might prefer to design a loss with harsher penalties when you make the wrong choice, though.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I like the idea. So you suggest to predict the payoff but with a customized loss function, that is asymmetric to false negative and false positives? But how would that need to be quantified if I can't just take the mse? $\endgroup$ – Nickpick Jul 10 '18 at 16:52
  • $\begingroup$ It's worth noting, that using a customized loss function on top of binary cross entropy doesn't seem to make the network to converge. I tried it here: github.com/dickreuter/betfair-horse-racing/blob/… $\endgroup$ – Nickpick Jul 10 '18 at 17:18

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.