Episodic Contextual Bandits with Knapsacks under Conversion Models
This work addresses dynamic resource allocation problems like pricing and auctions with episodic replenishment, representing an incremental advance in contextual bandit literature.
The paper tackles the problem of episodic contextual bandits with knapsacks under conversion models, where a decision maker interacts with non-stationary contexts and shared latent conversion models across episodes, and it achieves a regret sub-linear in the number of episodes by designing an online algorithm that leverages a confidence bound oracle.
We study an online setting, where a decision maker (DM) interacts with contextual bandit-with-knapsack (BwK) instances in repeated episodes. These episodes start with different resource amounts, and the contexts' probability distributions are non-stationary in an episode. All episodes share the same latent conversion model, which governs the random outcome contingent upon a request's context and an allocation decision. Our model captures applications such as dynamic pricing on perishable resources with episodic replenishment, and first price auctions in repeated episodes with different starting budgets. We design an online algorithm that achieves a regret sub-linear in $T$, the number of episodes, assuming access to a \emph{confidence bound oracle} that achieves an $o(T)$-regret. Such an oracle is readily available from existing contextual bandit literature. We overcome the technical challenge with arbitrarily many possible contexts, which leads to a reinforcement learning problem with an unbounded state space. Our framework provides improved regret bounds in certain settings when the DM is provided with unlabeled feature data, which is novel to the contextual BwK literature.