How to generalise over multiple simultaneous dependent actions in Reinforcement Learning

Question

I am trying to build an RL agent to price paid-for-seating on commercial flights. I should reiterate here - I am not talking about the price of the ticket - rather, I am talking about the pricing you see if you click on the seat map to choose where on the plane you sit (exits rows, window seats, etc). The general set up is:

1. After choosing their flights (for a booking of n people), a customer will view a web page with the available seat types and their prices visible.
2. They select between zero and n seats from a seat map with a variety of different prices for different seats, to be added to their booking.
3. The revenue from step 2 is observed as the reward.

Each 'episode' is the selling cycle of one flight. Whether the customer buys a chosen seat or not, the inventory goes down as they still have a ticket for the flight so will get a seat at departure. I would like to change prices on the fly, rather than fix a set of optimal prices throughout the selling cycle.

I have not decided on a general architecture yet. I want to take various booking, flight, and inventory information into account, so I know I will be using function approximation (most likely a neural net) to generalise over the state space.

However, I am less clear on how to set up my action space. I imagine an action would amount to a vector with a price for each different seat type (window seat, exit row, etc). If I have, for example, 8 different seat types, and 10 different price points for each, this gives me a total of 10^8 different actions, many of which will be very similar. In a sense, each action is comprised of a combination of sub-actions - the action of pricing each seat type.

Additionally, each sub-action (pricing one seat type) is somewhat dependent on the others, in the sense that the price of one seat type will likely affect the demand (and hence reward contribution) for another. For example, if you set window seats to a very cheap price, people will be less likely to spend a normal amount for the other seat types. Hence, I doubt the problem can be decomposed into a set of sub-problems.

I'm interested if there has been any research into dealing with a problem like this. Clearly any agent I build needs some way to generalise across actions to some degree, since collecting real data on millions of actions is not possible, even just for one state.

As I see it, this comes down to three questions:

1. Is it possible to get an agent that can deal with a set of actions (prices) as a single decision?
2. Is it possible to get this agent to understand actions in relative terms? Say for example, one set of potential prices is [10, 12, 20], for middle seats, aisle seats, and window seats. Can I get my agent to realise that there is a natural ordering there, and that the first two pricing actions are more similar to each other than to the third possible action?
3. Further to this, is it possible to generalise from this set of actions - could an agent be set up to understand that the set of prices [10, 13, 20] is very similar to the first set?

I haven't been able to find any literature on this, especially relating to the second question - any help would be much appreciated!

Answer 1

If you want to treat the problem as a full Reinforcement Learning problem, I'd recommend to try avoiding the combinatorial explosion of the action space by treating every sub-action as a separate decision point, a separate full action. If you have, for example, already selected 4 sub-actions for a particular customer, you can try to include those in some way in the state representation / input when moving on to the 5th sub-action. By including already-selected sub-actions in the state space, your algorithm can learn to take into account that optimal prices for some seat types will depend on what prices were already selected for others.

I do suspect such a full RL formulation will still be a difficult problem to learn though, will require huge amounts of experience. It may be worth considering to simplify it anyway, treat it as a Contextual + Combinatorial Multi-Armed Bandit Problem. That way you won't be able to learn long-term effects across multiple different customers as you described in the comments, but you will likely at least be able to learn something that works decently well with less experience. Recently, an interesting new book appeared on MAB problems, which is available for free here. You will find many chapters on Contextual MABs there, and also one chapter (chapter 30) on Combinatorial MABs.

Note that with either of these "combinatorial" approaches, you can also try to play around with the order in which you select sub-actions. For example, the sub-action / price point selected for seat type A might have a significant influence on what the optimal remaining policy would be for other seat types, whereas the sub-action for seat type B might have no influence on other seat types. It would then be useful to always prioritize selecting sub-actions for seat type A. You can try to identify these kinds of effects by keeping track of (co)variances in observed returns.

---

1. Is it possible to get an agent that can deal with a set of actions (prices) as a single decision?

The solutions I proposed above do not do this explicitly, they circumvent the issue by taking multiple sequential decisions. There does appear to be some research in RL with vector-valued actions. For example, the paper Clipped Action Policy Gradient briefly mentions vector-valued actions in Subsection 3.2. I am not personally familiar enough with RL + vector-valued actions to make a direct recommendation as to what approaches do or don't work well, but maybe this can at least help you find more relevant literature if this is a direction you'd like to pursue.

2. Is it possible to get this agent to understand actions in relative terms? Say for example, one set of potential prices is [10, 12, 20], for middle seats, aisle seats, and window seats. Can I get my agent to realise that there is a natural ordering there, and that the first two pricing actions are more similar to each other than to the third possible action?
3. Further to this, is it possible to generalise from this set of actions - could an agent be set up to understand that the set of prices [10, 13, 20] is very similar to the first set?

This kind of generalization should again come naturally from using function approximation with either of the solutions proposed above.