Minimisation du regret pour des récompenses linéaires par morceaux : contrats, enchères, et au-delà

La plupart des modèles microéconomiques d'intérêt impliquent l'optimisation d'une fonction linéaire par morceaux. Cela inclut la conception de contrats dans des problèmes principal-agent avec action cachée, la vente d'un article dans des enchères à prix affiché, et les enchères à un prix d'appel. Lorsque les paramètres du modèle pertinents sont inconnus et déterminés par certaines distributions de probabilité (inconnues), le problème devient d'apprendre comment optimiser une fonction de récompense linéaire par morceaux inconnue et stochastique. Un tel problème est généralement formulé dans le cadre d'un apprentissage en ligne, où le décideur (apprenant) cherche à minimiser le regret de ne pas connaître une décision optimale rétrospectivement. Cet article introduit un cadre général d'apprentissage en ligne qui offre une approche unifiée pour s'attaquer à la minimisation du regret pour des récompenses linéaires par morceaux, sous une hypothèse de monotonie appropriée souvent satisfaite par les modèles microéconomiques. Nous concevons un algorithme d'apprentissage qui atteint un regret de O(nT), où n est le nombre de