Bad Values but Good Behavior: Learning Highly Misspecified Bandits and MDPs

2023/10/13 by Debangshu Banerjee, Banerjee, Debangshu, Aditya Gopalan +1
Decision Sciences · #Advanced Bandit Algorithms Research #Artificial Intelligence (cs.AI) #Decision-Making and Behavioral Economics #FOS: Computer and information sciences #Forecasting Techniques and Applications #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2310.09358

openalex publication_date 2023/10/13 · openalex created_date 2023/10/18 · openalex updated_date 2026/07/28

Abstract

Parametric, feature-based reward models are employed by a variety of algorithms in decision-making settings such as bandits and Markov decision processes (MDPs). The typical assumption under which the algorithms are analysed is realizability, i.e., that the true values of actions are perfectly explained by some parametric model in the class. We are, however, interested in the situation where the true values are (significantly) misspecified with respect to the model class. For parameterized bandits, contextual bandits and MDPs, we identify structural conditions, depending on the problem instance and model class, under which basic algorithms such as ε-greedy, LinUCB and fitted Q-learning provably learn optimal policies under even highly misspecified models. This is in contrast to existing worst-case results for, say misspecified bandits, which show regret bounds that scale linearly with time, and shows that there can be a nontrivially large set of bandit instances that are robust to misspecification.

Related

• Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification
• Regret Bound Balancing and Elimination for Model Selection in Bandits\n and RL
• Worst-case Performance of Greedy Policies in Bandits with Imperfect Context Observations
• Learning with Good Feature Representations in Bandits and in RL with a Generative Model
• Learning the Reward Function for a Misspecified Model