Is there a way to form a reward function so that it would take into account the order of the actions?

Question

I want to design a multi-arm bandit system for a multi-step, multi-location system. Locations are dynamic, so I can not design the system based on them. In each location, the alternative actions that can be taken would be different. When you take correct actions, taken in correct locations, then some rewards would be earned. Some other alternative rewards can be incorporated in the system for the activities taken before reaching the correct state.

I know this may not be very clear. What I want to ask is "Is there a way to form a reward function so that it would take into account the order of the actions or the correctness of the order of the actions?".

Previously, I have implemented some other multi-arm bandit problems, but they were more straightforward. I need some ideas to help me to implement this new type of problem from some experts.

Answer 1

You are describing an environment which requires a full Markov Decision Process (MDP) to model it and reinforcement learning (RL) algorithms to solve it. You will not be able to adapt k-armed bandit algorithms, without effectively re-inventing MDPs.

The two key details that make this full RL, and not a bandit problem, are:

• Decisions are sequential, with options and outcomes that depend on previous decisions.

• Action choices make changes to variables (which in MDP would be part of the state description) that impact outcomes of future actions.

If you allow the agent to access the state including effects of previous actions encoded in a way that it has enough data to correctly predict rewards, then you have a normal MDP and most RL methods should be applicable.

If you do not allow the agent to use a convenient history of past actions (and/or their effects) as part of the state, then you will have constructed a partially observable MDP (POMDP) and may need a more advanced approach to solve it. For instance, using an RNN (most likely an LSTM or a GRU architecture) to process state sequence and predict action values could learn about the hidden sequence.

In terms of implementing a simulation of your environment, you will need to model it as a stateful system, and will have to include a concept of forward step in the sequence which modifies the state variables (regardless of whether these variables are made available to the agent in any observations). This would include the location information, and any other factors that change the allowed actions or outcome. As well as a step function, you will probably want a state reset function that puts the system into a starting state, or one of a range of possible starting states.

If your environment is episodic (a sequence can end), then you will need a way to flag that so that the learning agent can react to the end of an episode and request a new starting state.

Answer 2

Neil Slater has a solid answer. In general you could have a bandit algorithm in which the reward $r \sim f(. | a)$, or an mdp where reward $r \sim f(. |s,a,s')$. Here $a$ is the current action, $s$ is the current state, and $s'$ is the next state. How you encode $f$ if a bandit or mdp is up to you whether deterministic or based on assuming a parametric family. Of course, an MDP is not the most general setup either, but describing a setting with a highly action/state dependent history is not simple to do for mathematical analysis (and coding too).

Hence if you want something more complex than what an mdp assumes, that's up to you to code/describe, or to initialize something more complex like an rnn as Neil Slater says and use that as your reward. Without nice data to train it though, an rnn reward function may not give very sensical rewards.