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?