I have a set of $N$ items of which a subset of arbitrary size can be chosen. I want a reinforcement learning (RL) agent to perform the subset selection and am unsure how to best design the action space and action selection process.
These four approaches came to my mind:
- Encode all possible subsets into different actions and let the agent choose a single action (=subset). While this is straight forward, it would require a huge action space with $2^N$ actions - I doubt that an agent would learn anything here.
- Instead of selecting the entire subset at once, make sequential decisions. One option would be to sequentially select each item and ask the agent whether to include it in the subset. This would result in $N$ binary decisions, so much easier. But I would need to include extra information about the current item and previously selected items in the state since that should affect the agent's decisions. Also I'll have to determine an order in which to present the items to the agent, which will likely affect its decisions and the outcome.
- To avoid determining the order of presented items, I could also simply ask the agent in each sequential decision which item it wants to add to the subset or if it wants to stop adding items to the subset. This would lead to up to $N$ sequential actions, where each action is a selection of one of $N+1$ options (incl. the "stop" action).
- Finally, I could use continuous actions and have the agent assign a probability distribution over the $N$ items. Then I'll take all items with a probability of $\geq 1/N$ and add them to the set. This would mean, I have an action space of $N$ continuous dimensions in $[0,1]$.
What do you think is the most promising approach? I'm currently mostly in favor of approach 2 and 3 because I want to avoid the huge action space of approach 1 and the continuous actions of approach 4.
An additional question is how I would implement sequential actions (approach 2 and 3) following the OpenAI Gym interface. The interface defines
step(action) to already return the reward and next state. But in the case of sequential actions, I'd want to submit multiple actions before aggregating them to my complete subset and then applying the subset to the environment to get the reward and next state for all actions.
Any recommendations or best practices here?
I suppose, I could build my environment to "collect" multiple actions always returning a reward of 0 and then applying all actions and returning the full reward. But I'm not sure if that would lead to credit assignment problems.