Un algorithme pour une prise de décision optimale sous des récompenses bruyantes à queue lourde

Un algorithme pour une prise de décision optimale sous des récompenses bruyantes à queue lourde

Crédit : Pixabay/CC0 Domaine public

En science des données, les chercheurs traitent généralement des données contenant des observations bruyantes. Un problème important exploré par les data scientists dans ce contexte est le problème de la prise de décision séquentielle. Ceci est communément appelé « bandit multi-armé stochastique » (MAB stochastique).

Ici, un agent intelligent explore et sélectionne séquentiellement des actions basées sur des récompenses bruyantes dans un environnement incertain. Son objectif est de minimiser le regret cumulatif – la différence entre la récompense maximale et la récompense attendue des actions sélectionnées. Un petit regret implique une prise de décision plus efficace.

La plupart des études existantes sur les MAB stochastiques ont effectué une analyse des regrets en supposant que le bruit de récompense suit une distribution à queue légère. Cependant, de nombreux ensembles de données du monde réel montrent en fait une distribution de bruit à queue lourde. Il s’agit notamment des données sur les modèles de comportement des utilisateurs utilisées pour développer des systèmes de recommandation personnalisés, des données sur le cours des actions pour le développement automatique des transactions et des données de capteur pour la conduite autonome.

Dans une étude récente, le professeur adjoint Kyungjae Lee de l’Université Chung-Ang et le professeur adjoint Sungbin Lim de l’Institut des sciences et technologies d’Ulsan, tous deux en Corée, ont abordé cette question. Dans leur analyse théorique, ils ont prouvé que les algorithmes existants pour les MAB stochastiques étaient sous-optimaux pour les récompenses à queue lourde.

Plus précisément, les méthodes employées dans ces algorithmes – borne de confiance supérieure robuste (UCB) et exploration perturbée de manière adaptative (APE) avec perturbation illimitée – ne garantissent pas une optimalité minimax (minimisation de la perte maximale possible).

« Sur la base de cette analyse, des méthodes minimax optimales robustes (MR) UCB et APE ont été proposées. MR-UCB utilise une limite de confiance plus étroite d’estimateurs moyens robustes, et MR-APE est sa version randomisée. Elle utilise une perturbation bornée dont l’échelle suit la confiance modifiée liée à MR-UCB », explique le Dr Lee, parlant de leur travail, qui a été publié dans Transactions IEEE sur les réseaux de neurones et les systèmes d’apprentissage.

Les chercheurs ont ensuite dérivé des limites supérieures indépendantes et dépendantes de l’écart du regret cumulé. Pour les deux méthodes proposées, cette dernière valeur correspond à la limite inférieure sous l’hypothèse de bruit à queue lourde, atteignant ainsi l’optimalité minimax. De plus, les nouvelles méthodes nécessitent un minimum d’informations préalables et ne dépendent que de l’ordre maximum du moment borné des récompenses. En revanche, les algorithmes existants nécessitent la limite supérieure de ce moment a priori – des informations qui peuvent ne pas être accessibles dans de nombreux problèmes du monde réel.

Après avoir établi leur cadre théorique, les chercheurs ont testé leurs méthodes en réalisant des simulations sous bruits de Pareto et Fréchet. Ils ont constaté que MR-UCB surpassait systématiquement les autres méthodes d’exploration et était plus robuste avec une augmentation du nombre d’actions sous un bruit à queue lourde.

En outre, le duo a vérifié leur approche pour les données du monde réel à l’aide d’un ensemble de données de crypto-monnaie, montrant que MR-UCB et MR-APE étaient bénéfiques – limites de regret optimales minimax et connaissances préalables minimales – pour s’attaquer au MAB stochastique synthétique et réel à queue lourde. problèmes.

« Étant vulnérables au bruit à queue lourde, les algorithmes MAB existants affichent des performances médiocres dans la modélisation des données boursières. Ils ne parviennent pas à prédire de grandes hausses ou des baisses soudaines des cours des actions, entraînant d’énormes pertes. En revanche, MR-APE peut être utilisé dans le commerce autonome systèmes avec des rendements attendus stables grâce à l’investissement en actions », explique le Dr Lee, discutant des applications potentielles des travaux actuels.

« De plus, il peut être appliqué aux systèmes de recommandation personnalisés puisque les données comportementales montrent un bruit à queue lourde. Avec de meilleures prédictions du comportement individuel, il est possible de fournir de meilleures recommandations que les méthodes conventionnelles, ce qui peut maximiser les revenus publicitaires », conclut-il.

Fourni par l’Université Chung Ang