How can I incorporate domain knowledge to choose actions in the case of large action spaces in multi-armed bandits?

Question

Suppose one is using a multi-armed bandit, and one has relatively few "pulls" (i.e. timesteps) relative to the action set. For example, maybe there are 200 timesteps and 100 possible actions.

However, you do have information on how similar actions are to each other. For example, I might want to rent a car, and know the model, year, and mileage of each car. (Specifically, I want to rent a car on a daily basis for each day in a 200 day period; on each day, I can either continue with the existing car or rent a new one. There are 100 possible cars.)

How can I exploit this information to choose actions that maximize my payoff?

Answer 1

You will want to look into Contextual Multi-Armed Bandits. These are MAB problems that additionally involve feature vectors in some way.

You'll sometimes see researchers considering problems where you get to see a single feature vector per timestep (like an "environment state" you're in) which may provide useful information. You'll also sometimes see researchers considering problems where you observe a single feature vector per arm/action (per timestep). That second case is pretty much what you're describing; every arm/action has a feature vector (model, year, mileage of car), and you can use those to make predictions and generalize across arms.

To give a little bit of flavour for these algorithms, the most common ones simply assume that the rewards you observe after pulling arms are given by a linear combination of features, plus some noise. Then, they simply try to find (through online learning) a parameter vector such that observed rewards can be accurately approximated by the dot product of the parameter vector and a feature vector. Of course, there are lots of different variants of algorithms, and not all are linear, but this gives an idea of what they generally look like.