Is reinforcement learning only suitable for path dependent problems?

Question

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.

Answer 1

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.

Answer 2

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.