0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Make sure my edits did not change the meaning of your post (it's a good idea to have a descriptive title, which is actually your question - that's what I tried to do here). Honestly, it's not fully clear to me what you're asking here or where the confusion lies, though. You have different action sets for different locations, but apart from that your post is quite unclear. Are you familiar with MDPs? Please, provide a description of your actual problem, that would be more helpful, IMHO. $\endgroup$
    – nbro
    Jul 3, 2022 at 20:17

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thank you Neil for taking the time. I already implemented it as a stateful machine and I change potential actions based on locations. There is also the end of states and as you said I already put the agent in a starting state when it comes to somehow end. My question is related to the reward function. I know you mentioned some techniques like RNN(LSTM or GRU), but it would be helpful if you can clarify that part or maybe share some relevant links so that I may try to understand ? $\endgroup$ Jul 3, 2022 at 17:19
  • $\begingroup$ @Ferda-Ozdemir-Sonmez: OK, the reason for my answer here is that you are calling your system a bandit problem, but it is not one. I am not clear what your problem with the reward function is? $\endgroup$ Jul 3, 2022 at 19:06
  • $\begingroup$ @Ferda-Ozdemir-Sonmez - maybe this Q&A could help: ai.stackexchange.com/questions/22851/… ? $\endgroup$ Jul 3, 2022 at 19:14
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .