Contextual Bandit Learning with Predictable Rewards

Abstract

Contextual bandit learning is a reinforcement learning problem where the learner repeatedly receives a set of features (context), takes an action and receives a reward based on the action and context. We consider this problem under a realizability assumption: there exists a function in a (known) function class, always capable of predicting the expected reward, given the action and context. Under this assumption, we show three things. We present a new algorithm---Regressor Elimination--- with a regret similar to the agnostic setting (i.e. in the absence of realizability assumption). We prove a new lower bound showing no algorithm can achieve superior performance in the worst case even with the realizability assumption. However, we do show that for any set of policies (mapping contexts to actions), there is a distribution over rewards (given context) such that our new algorithm has constant regret unlike the previous approaches.

References in corpus (1)

• Efficient Optimal Learning for Contextual Bandits

Cited by in corpus (18)

• Making Contextual Decisions with Low Technical Debt
• Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits
• Sequential Transfer in Multi-armed Bandit with Finite Set of Models
• A Contextual Bandit Bake-off
• Practical Contextual Bandits with Regression Oracles
• Model selection for contextual bandits
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Federated Residual Learning
• PAC Reinforcement Learning with Rich Observations
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination
• Leveraging Good Representations in Linear Contextual Bandits
• Multi-Product Dynamic Pricing in High-Dimensions with Heterogeneous Price Sensitivity
• Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits
• Towards General Function Approximation in Zero-Sum Markov Games
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy
• Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability