Institut de l'intelligence artificielle de l'Alberta

Amii à NeurIPS 2022 | Amii

Publié

23 novembre 2022

Amii est fière de partager les travaux de nos chercheurs qui seront présentés à la trente-sixième conférence annuelle. Systèmes neuronaux de traitement de l'information (NeurIPS), une conférence hybride qui se tiendra en ligne et à la Nouvelle-Orléans du 28 novembre au 9 décembre 2022.

Lancée en 1987, NeurIPS est devenue une conférence de premier plan sur l'apprentissage automatique et les neurosciences cognitives. Chaque année, elle attire des chercheurs de nombreuses disciplines différentes, dont la théorie de l'information, la vision par ordinateur et la linguistique.

Cette année, 19 articles cosignés par des boursiers Amii, des titulaires de chaires en IA du Canada et des chercheurs en début de carrière ont été acceptés à NeurIPS. ICRA et des chercheurs en début de carrière ont été acceptés à NeurIPS, en plus des ateliers et des concours.

Itération de la valeur doublement asynchrone : Rendre l'itération de la valeur asynchrone dans les actions

Tian Tian - Kenny Young - Richard Sutton

L'itération de valeurs (VI) est une méthode de programmation dynamique fondamentale, importante pour l'apprentissage et la planification dans le contrôle optimal et l'apprentissage par renforcement. La VI procède par lots, où la mise à jour de la valeur de chaque état doit être terminée avant que le lot suivant de mises à jour puisse commencer. L'achèvement d'un seul lot est excessivement coûteux si l'espace d'état est grand, ce qui rend la VI peu pratique pour de nombreuses applications. Le VI asynchrone permet de résoudre le problème du grand espace d'état en mettant à jour un état à la fois, en place et dans un ordre arbitraire. Cependant, le VI asynchrone nécessite toujours une maximisation sur l'espace d'action entier, ce qui le rend peu pratique pour les domaines avec un grand espace d'action. Pour résoudre ce problème, nous proposons l'itération de valeur doublement asynchrone (DAVI), un nouvel algorithme qui généralise l'idée d'asynchronie des états aux états et aux actions. Plus concrètement, DAVI maximise sur un sous-ensemble échantillonné d'actions qui peut être de n'importe quelle taille définie par l'utilisateur. Cette approche simple qui consiste à utiliser l'échantillonnage pour réduire les calculs conserve des propriétés théoriques similaires à celles de VI, sans qu'il soit nécessaire d'attendre un balayage complet de tout l'espace d'action à chaque mise à jour. Dans cet article, nous montrons que DAVI converge vers la fonction de valeur optimale avec une probabilité de un, converge à un taux quasi-géométrique avec une probabilité de 1 -δ, et renvoie une politique quasi-optimale en temps de calcul qui correspond presque à une limite précédemment établie pour VI. Nous démontrons aussi empiriquement l'efficacité de DAVI dans plusieurs expériences.

MultiScan : Numérisation RGBD évolutive pour les environnements 3D avec objets articulés

Yongsen Mao - Yiming Zhang - Hanxiao Jiang - Angel Chang - Manolis Savva

Nous présentons MultiScan, un pipeline de construction de jeux de données RVBD évolutif qui utilise des appareils mobiles de base pour numériser des scènes intérieures avec des objets articulés et des interfaces d'annotation sémantique basées sur le Web pour annoter efficacement la sémantique des objets et des pièces ainsi que les paramètres de mobilité des pièces. Nous utilisons ce pipeline pour collecter 230 scans de 108 scènes intérieures contenant 9458 objets et 4331 pièces. Le jeu de données MultiScan qui en résulte fournit des flux RGBD avec des poses de caméra par image, des maillages de surface 3D texturés, des étiquettes sémantiques richement annotées au niveau des pièces et des objets, et des paramètres de mobilité des pièces. Nous validons notre jeu de données sur des tâches de segmentation d'instances et d'estimation de la mobilité des pièces, ainsi que sur des méthodes de référence pour ces tâches issues de travaux antérieurs. Nos expériences montrent que la segmentation des pièces et l'estimation de la mobilité dans les scènes 3D réelles restent difficiles malgré les progrès récents dans la segmentation des objets 3D.

Équité conforme via la régression quantile

Meichen Liu - Lei Ding - Dengdeng Yu - Wulong Liu - Linglong Kong - Bei Jiang

L'équité algorithmique a fait l'objet d'une attention accrue dans les domaines socialement sensibles. Alors qu'une riche littérature sur l'équité moyenne a été établie, la recherche sur l'équité quantile reste rare mais vitale. Pour répondre à ces besoins et mettre en avant l'importance de l'équité quantile, nous proposons un nouveau cadre pour apprendre une fonction quantile à valeur réelle sous l'exigence d'équité de la parité démographique en ce qui concerne les attributs sensibles, tels que la race ou le sexe, et ainsi dériver un intervalle de prédiction équitable fiable. En utilisant des techniques de transport optimal et de synchronisation fonctionnelle, nous établissons des garanties théoriques de couverture sans distribution et d'équité exacte pour l'intervalle de prédiction induit construit par des quantiles équitables. Un pipeline pratique est fourni pour incorporer des régressions quantiles flexibles avec un algorithme efficace de post-traitement d'ajustement de l'équité. Nous démontrons la performance empirique supérieure de cette approche sur plusieurs ensembles de données de référence. Nos résultats montrent la capacité du modèle à découvrir le mécanisme sous-jacent au compromis équité/exactitude dans un large éventail d'applications sociétales et médicales.

Identification, amplification et mesure : Un pont vers la confidentialité différentielle gaussienne

Yi Liu - Ke Sun - Bei Jiang - Linglong Kong

La confidentialité différentielle gaussienne (GDP) est une famille de notions de confidentialité à paramètre unique qui fournit des garanties cohérentes pour éviter l'exposition d'informations individuelles sensibles. Malgré l'interprétabilité supplémentaire et les limites plus étroites sous composition que fournit GDP, de nombreux mécanismes largement utilisés (par exemple, le mécanisme de Laplace) fournissent intrinsèquement des garanties GDP mais ne parviennent souvent pas à tirer parti de ce nouveau cadre car leurs garanties de confidentialité ont été dérivées dans un contexte différent. Dans cet article, nous étudions les propriétés asymptotiques des profils de confidentialité et développons un critère simple pour identifier les algorithmes ayant des propriétés GDP. Nous proposons une méthode efficace pour les algorithmes GDP afin de réduire les valeurs possibles d'une mesure de confidentialité optimale, μ, avec une marge d'erreur arbitrairement petite et quantifiable. Pour les algorithmes non GDP, nous fournissons une procédure de post-traitement qui peut amplifier les garanties de confidentialité existantes pour répondre à la condition GDP. Comme applications, nous comparons deux familles de notions de confidentialité à un seul paramètre, ϵ-DP, et μ-GDP, et nous montrons que tous les algorithmes ϵ-DP sont intrinsèquement aussi GDP. Enfin, nous montrons que la combinaison de notre processus de mesure et du théorème de composition de GDP est un outil puissant et pratique pour traiter les compositions par rapport aux théorèmes de composition classiques et avancés.

Le forçage de l'enseignant récupère les fonctions de récompense pour la génération de textes

Yongchang Hao - Yuxin Liu - Lili Mou

L'apprentissage par renforcement (RL) a été largement utilisé dans la génération de textes pour atténuer le problème du biais d'exposition ou pour utiliser des ensembles de données non parallèles. La fonction de récompense joue un rôle important dans la réussite de l'apprentissage par renforcement. Cependant, les fonctions de récompense précédentes sont généralement spécifiques à une tâche et peu nombreuses, ce qui limite l'utilisation de la RL. Dans notre travail, nous proposons une approche indépendante de la tâche qui dérive une fonction de récompense progressive directement d'un modèle formé avec le forçage de l'enseignant. Nous proposons en outre une modification simple pour stabiliser l'entraînement RL sur des ensembles de données non parallèles avec notre fonction de récompense induite. Les résultats empiriques montrent que notre méthode surpasse les méthodes d'auto-formation et de régression par récompense sur plusieurs tâches de génération de texte, confirmant l'efficacité de notre fonction de récompense.

Sur les taux de convergence globale du jeu décentralisé de gradient Softmax dans les jeux potentiels de Markov

Runyu Zhang - Jincheng Mei - Bo Dai - Dale Schuurmans- Na Li

Le gradient de politique Softmax est un algorithme populaire pour l'optimisation de la politique dans l'apprentissage par renforcement mono-agent, en particulier parce que la projection n'est pas nécessaire pour chaque mise à jour du gradient. Cependant, dans les systèmes multi-agents, l'absence de coordination centrale introduit des difficultés supplémentaires importantes dans l'analyse de la convergence. Même pour un jeu stochastique avec un intérêt identique, il peut y avoir plusieurs équilibres de Nash (NEs), ce qui désactive les techniques de preuve qui reposent sur l'existence d'un optimum global unique. De plus, la paramétrisation softmax introduit des politiques non-NE avec un gradient nul, ce qui rend difficile la recherche de NEs par les algorithmes basés sur le gradient. Dans cet article, nous étudions la convergence en temps fini du jeu de gradient softmax décentralisé dans une forme spéciale de jeu, les jeux de potentiel de Markov (MPG), qui incluent le jeu d'intérêt identique comme cas spécial. Nous étudions à la fois le jeu par gradient et le jeu par gradient naturel, avec et sans régularisation par barrière logarithmique. Les taux de convergence établis pour les cas non régularisés contiennent une constante dépendant de la trajectoire qui peut être \emph{arbitrairement grande}, alors que la régularisation log-barrière surmonte cet inconvénient, au prix d'une dépendance légèrement moins bonne à l'égard d'autres facteurs tels que la taille de l'ensemble d'actions. Une étude empirique sur un jeu de matrice d'intérêt identique confirme les résultats théoriques.

Un algorithme de contrôle de la longueur au niveau des caractères pour le résumé de phrases non autorégressif.

Puyuan Liu - Xiang Zhang - Lili Mou

Le résumé de phrases a pour but de comprimer une longue phrase en une phrase courte qui en conserve l'essentiel, et a de nombreuses applications dans le monde réel, comme la génération de titres. Dans des travaux antérieurs, les chercheurs ont développé diverses approches pour améliorer le score ROUGE, qui est la principale mesure d'évaluation du résumé, alors que le contrôle de la longueur du résumé n'a pas attiré beaucoup d'attention. Dans notre travail, nous abordons un nouveau problème de contrôle explicite de la longueur des caractères pour le résumé, et nous proposons un algorithme de programmation dynamique basé sur le modèle de classification temporelle connexionniste (CTC). Les résultats montrent que notre approche permet non seulement d'obtenir des scores ROUGE plus élevés, mais aussi de produire des phrases plus complètes.

L'incitation à la chaîne de pensée suscite le raisonnement dans les grands modèles linguistiques

Jason Wei - Xuezhi Wang - Dale Schuurmans - Maarten Bosma - brian ichter - Fei Xia - Ed Chi - Quoc V Le - Denny Zhou

Nous étudions comment la génération d'une chaîne de pensée - une série d'étapes de raisonnement intermédiaires - améliore de manière significative la capacité des grands modèles de langage à effectuer des raisonnements complexes. En particulier, nous montrons comment de telles capacités de raisonnement émergent naturellement dans des modèles de langage suffisamment grands via une méthode simple appelée "chain of thought prompting", où quelques démonstrations de chaînes de pensée sont fournies comme exemples dans le prompting. Des expériences menées sur trois grands modèles de langage montrent que l'incitation à la chaîne de pensée améliore les performances dans toute une série de tâches de raisonnement arithmétique, logique et symbolique. Les gains empiriques peuvent être frappants. Par exemple, l'incitation d'un modèle de langage de 540B paramètres avec seulement huit exemples de chaîne de pensée permet d'atteindre une précision de pointe sur le repère GSM8K de problèmes de mots mathématiques, dépassant même le GPT-3 finement réglé avec un vérificateur.

Le rôle des lignes de base dans l'optimisation par gradient des politiques

Jincheng Mei - Wesley Chung - Valentin Thomas - Bo Dai - Csaba Szepesvari - Dale Schuurmans

We study the effect of baselines in on-policy stochastic policy gradient optimization, and close the gap between the theory and practice of policy optimization methods. Our first contribution is to show that the \emph{state value} baseline allows on-policy stochastic \emph{natural} policy gradient (NPG) to converge to a globally optimal policy at an O(1/t) rate, which was not previously known. The analysis relies on two novel findings: the expected progress of the NPG update satisfies a stochastic version of the non-uniform \L{}ojasiewicz (N\L{}) inequality, and with probability 1 the state value baseline prevents the optimal action's probability from vanishing, thus ensuring sufficient exploration. Importantly, these results provide a new understanding of the role of baselines in stochastic policy gradient: by showing that the variance of natural policy gradient estimates remains unbounded with or without a baseline, we find that variance reduction \emph{cannot} explain their utility in this setting. Instead, the analysis reveals that the primary effect of the value baseline is to \textbf{reduce the aggressiveness of the updates} rather than their variance. That is, we demonstrate that a finite variance is \emph{not necessary} for almost sure convergence of stochastic NPG, while controlling update aggressiveness is both necessary and sufficient. Additional experimental results verify these theoretical findings.

Mise à l'échelle optimale pour les propositions localement équilibrées dans les espaces discrets

Haoran Sun - Hanjun Dai - Dale Schuurmans

L'échelonnement optimal a été bien étudié pour les algorithmes de Metropolis-Hastings (M-H) dans les espaces continus, mais une compréhension similaire a fait défaut dans les espaces discrets. Récemment, il a été prouvé qu'une famille de propositions localement équilibrées (LBP) pour les espaces discrets était asymptotiquement optimale, mais la question de l'échelonnement optimal est restée ouverte. Dans cet article, nous établissons, pour la première fois, que l'efficacité de M-H dans les espaces discrets peut également être caractérisée par un taux d'acceptation asymptotique qui est indépendant de la distribution cible. De plus, nous vérifions, à la fois théoriquement et empiriquement, que les taux d'acceptation optimaux pour LBP et la marche aléatoire de Metropolis (RWM) sont respectivement de 0,574 et 0,234. Ces résultats permettent également d'établir que la LBP est asymptotiquement O(N23) plus efficace que la RWM par rapport à la dimension N du modèle. La connaissance du taux d'acceptation optimal permet d'ajuster automatiquement la taille du voisinage d'une distribution de propositions dans un espace discret, de manière directement analogue au contrôle de la taille des pas dans les espaces continus. Nous démontrons empiriquement qu'un tel échantillonnage M-H adaptatif peut améliorer de manière robuste l'échantillonnage dans une variété de distributions cibles dans des espaces discrets, y compris l'entraînement de modèles profonds basés sur l'énergie.

Une méthode simple d'entropie croisée décentralisée

Zichen Zhang - Jun Jin - Martin Jagersand - Jun Luo - Dale Schuurmans

La méthode de l'entropie croisée (CEM) est couramment utilisée pour la planification dans l'apprentissage par renforcement basé sur un modèle (MBRL) où une approche centralisée est généralement utilisée pour mettre à jour la distribution d'échantillonnage en se basant uniquement sur les résultats des opérations top-k sur les échantillons. Dans cet article, nous montrons qu'une telle approche centralisée rend le CEM vulnérable aux optima locaux, ce qui nuit à son efficacité d'échantillonnage. Pour résoudre ce problème, nous proposons une CEM décentralisée (DecentCEM), une amélioration simple mais efficace de la CEM classique, en utilisant un ensemble d'instances CEM fonctionnant indépendamment les unes des autres, et chacune effectuant une amélioration locale de sa propre distribution d'échantillonnage. Nous fournissons une analyse théorique et empirique pour démontrer l'efficacité de cette simple approche décentralisée. Nous montrons empiriquement que, par rapport à l'approche centralisée classique utilisant une seule ou même un mélange de distributions gaussiennes, notre DecentCEM trouve l'optimum global de manière beaucoup plus cohérente et améliore ainsi l'efficacité de l'échantillonnage. De plus, nous introduisons notre DecentCEM dans le problème de planification de MBRL, et évaluons notre approche dans plusieurs environnements de contrôle continu, en comparaison avec les approches MBRL basées sur la CEM (PETS et POPLIN). Les résultats montrent une amélioration de l'efficacité de l'échantillon en remplaçant simplement le module CEM classique par notre module DecentCEM, tout en ne sacrifiant qu'une quantité raisonnable de coût de calcul. Enfin, nous réalisons des études d'ablation pour une analyse plus approfondie.

Imitation de la chaîne de pensée avec clonage de procédure

Mengjiao (Sherry) Yang - Dale Schuurmans- Pieter Abbeel - Ofir Nachum

L'apprentissage par imitation vise à extraire des politiques performantes à partir de démonstrations enregistrées de comportements d'experts. Il est courant de formuler l'apprentissage par imitation comme un problème d'apprentissage supervisé dans lequel on ajuste un approximateur de fonction à la correspondance entrée-sortie présentée par les démonstrations enregistrées (observations d'entrée vers actions de sortie). Bien que la formulation de l'apprentissage par imitation comme un problème d'apprentissage supervisé entrée-sortie permette une application dans une grande variété de contextes, il s'agit également d'une vision trop simpliste du problème dans des situations où les démonstrations d'experts fournissent un aperçu beaucoup plus riche du comportement des experts. Par exemple, des applications telles que la navigation sur des chemins, la manipulation de robots et les jeux de stratégie acquièrent des démonstrations d'experts par le biais de la planification, de la recherche ou d'un autre algorithme à plusieurs étapes, révélant non seulement l'action de sortie à imiter, mais aussi la procédure permettant de déterminer cette action. Bien que ces calculs intermédiaires puissent utiliser des outils dont l'agent ne dispose pas pendant l'inférence (par exemple, des simulateurs d'environnement), ils sont néanmoins instructifs pour expliquer la correspondance entre l'état et les actions d'un expert. Afin d'exploiter correctement les informations relatives à la procédure de l'expert sans s'appuyer sur les outils privilégiés que l'expert a pu utiliser pour exécuter la procédure, nous proposons le clonage de procédure, qui applique la prédiction de séquence supervisée pour imiter la série complète de calculs de l'expert. De cette façon, le clonage de procédure apprend non seulement ce qu'il faut faire (c'est-à-dire l'action de sortie), mais aussi comment et pourquoi le faire (c'est-à-dire la procédure). Grâce à une analyse empirique de la navigation, de la manipulation robotique simulée et des environnements de jeu, nous montrons que l'imitation des calculs intermédiaires du comportement d'un expert permet au clonage de procédure d'apprendre des politiques présentant une généralisation significative à des configurations environnementales inconnues, y compris les configurations pour lesquelles l'exécution directe de la procédure de l'expert est infaisable.

Évaluation de modèles génératifs de graphes avec des caractéristiques apprises de manière contradictoire

Hamed Shirzad - Kaveh Hassani - Danica J. Sutherland

Un large éventail de modèles a été proposé pour les modèles génératifs de graphes, ce qui nécessite des méthodes efficaces pour évaluer leur qualité. Jusqu'à présent, la plupart des techniques utilisent soit des mesures traditionnelles basées sur le comptage des sous-graphes, soit les représentations de réseaux neuronaux graphiques (GNN) initialisés de manière aléatoire. Nous proposons d'utiliser les représentations de GNNs entraînés de manière constrastive, plutôt que des GNNs aléatoires, et montrons que cela donne des mesures d'évaluation plus fiables. Cependant, ni les approches traditionnelles ni les approches basées sur les GNN ne dominent l'autre : nous donnons des exemples de graphes que chaque approche est incapable de distinguer. Nous démontrons que les réseaux de sous-structures de graphes (GSN), qui combinent en quelque sorte les deux approches, sont meilleurs pour distinguer les distances entre les ensembles de données de graphes.

Une théorie non asymptotique de l'enveloppe de Moreau pour les modèles linéaires généralisés de haute dimension

Lijia Zhou - Frederic Koehler - Pragya Sur - Danica J. Sutherland - Nati Srebro

Nous prouvons une nouvelle borne de généralisation qui montre pour toute classe de prédicteurs linéaires dans l'espace gaussien, la complexité de Rademacher de la classe et l'erreur d'apprentissage sous toute perte continue ℓ peuvent contrôler l'erreur de test sous toutes les enveloppes de Moreau de la perte ℓ. Nous utilisons notre limite d'échantillon fini pour récupérer directement le " taux optimiste " de Zhou et al. (2021) pour la régression linéaire avec la perte carrée, qui est connu pour être serré pour l'interpolation minimale ℓ2-normale, mais nous traitons également des paramètres plus généraux où l'étiquette est générée par un modèle multi-index potentiellement mal spécifié. Le même argument permet d'analyser l'interpolation bruyante des classificateurs à marge maximale par la perte carrée de la charnière, et établit des résultats de cohérence dans des paramètres de covariance en pointe. Plus généralement, lorsque la perte est supposée être Lipschitz, notre limite améliore effectivement le lemme de contraction bien connu de Talagrand par un facteur de deux, et nous prouvons la convergence uniforme des interpolateurs (Koehler et al. 2021) pour toutes les pertes lisses et non négatives. Enfin, nous montrons que l'application de notre limite de généralisation à l'aide de la largeur gaussienne localisée sera généralement nette pour les minimiseurs de risque empiriques, établissant une théorie de l'enveloppe de Moreau non asymptotique pour la généralisation qui s'applique en dehors des régimes d'échelle proportionnelle, qui traite la mauvaise spécification du modèle et qui complète les théories de l'enveloppe de Moreau asymptotiques existantes pour la M-estimation.

Théorie du bandit et évolution dirigée guidée par l'échantillonnage de Thompson pour l'optimisation des séquences

Hui Yuan - Chengzhuo Ni - Huazheng Wang - Xuezhou Zhang - Le Cong - Csaba Szepesvari - Mengdi Wang

L'évolution dirigée (ED), une méthode de laboratoire humide qui a fait date et qui a vu le jour dans les années 1960, permet de découvrir de nouvelles conceptions de protéines par l'évolution d'une population de séquences candidates. Les progrès récents de la biotechnologie ont rendu possible la collecte de données à haut débit, ce qui permet d'utiliser l'apprentissage automatique pour établir la relation entre la séquence et la fonction d'une protéine. L'ED assistée par l'apprentissage automatique suscite un intérêt croissant pour accélérer l'optimisation des protéines. Dans cet article, nous établissons un lien entre l'apprentissage automatique et la théorie de l'apprentissage par les bandits et nous tentons pour la première fois d'étudier la minimisation des regrets dans le cadre de l'apprentissage automatique. Nous proposons un cadre d'évolution dirigée guidée par l'échantillonnage de Thompson (TS-DE) pour l'optimisation des séquences, où la correspondance séquence-fonction est inconnue et où l'interrogation d'une valeur unique est sujette à des mesures coûteuses et bruyantes. La TS-DE met à jour un a posteriori de la fonction sur la base des mesures collectées. Il utilise une estimation de la fonction échantillonnée a posteriori pour guider les étapes de croisement, de recombinaison et de mutation de l'algorithme DE. Dans le cas d'un modèle linéaire, nous montrons que TS-DE bénéficie d'un regret bayésien de l'ordre de O~(d2MT), où d est la dimension de la caractéristique, M la taille de la population et T le nombre de tours. Cette limite de regret est presque optimale, confirmant que l'apprentissage par banditisme peut accélérer l'ED de manière prouvée. Elle peut avoir des implications pour l'optimisation de séquences plus générales et les algorithmes évolutionnaires.

Itération de politique approximative confiante pour une planification locale efficace dans les MDPs réalisables q(π)

Gellért Weisz - András György - Csaba Szepesvari

Nous considérons la programmation dynamique approximative dans les processus de décision de Markov γ-décalés et l'appliquons à la planification approximative avec une approximation linéaire de la fonction de valeur. Notre première contribution est une nouvelle variante de l'itération de politique approximative (API), appelée itération de politique approximative confiante (CAPI), qui calcule une politique stationnaire déterministe avec une limite d'erreur optimale s'échelonnant linéairement avec le produit de l'horizon effectif H et de l'erreur d'approximation dans le pire des cas ϵ des fonctions action-valeur des politiques stationnaires. Cette amélioration par rapport à l'API (dont l'erreur s'échelonne avec H2) se fait au prix d'une augmentation d'un facteur H du coût de la mémoire. Contrairement à Scherrer et Lesner [2012], qui recommandent de calculer une politique non stationnaire pour obtenir une amélioration similaire (avec le même surcoût mémoire), nous sommes en mesure de nous en tenir aux politiques stationnaires. Cela permet notre deuxième contribution, l'application de l'IPAO à la planification avec un accès local à un simulateur et une approximation de fonction linéaire à d dimensions. Ainsi, nous concevons un algorithme de planification qui applique la CAPI pour obtenir une séquence de politiques avec des précisions successivement raffinées sur un ensemble d'états évoluant dynamiquement. L'algorithme produit une politique O~(dHϵ)-optimale après avoir émis O~(dH(4)/ϵ(2)) requêtes au simulateur, atteignant simultanément la limite de précision optimale et la limite de complexité de requête la plus connue, alors que les algorithmes précédents dans la littérature n'atteignent qu'une seule de ces deux limites. On montre que cette complexité de requête est serrée pour tous les paramètres sauf H. Ces améliorations se font au prix d'une légère augmentation (polynomiale) de la mémoire et des coûts de calcul de l'algorithme et de sa politique de sortie.

Limites de complexité d'échantillonnage quasi-optimales pour les MDP sous contrainte

Sharan Vaswani - Lin Yang - Csaba Szepesvari

Contrairement aux progrès réalisés dans la caractérisation de la complexité d'échantillonnage pour la résolution des processus de décision de Markov (MDP), la complexité statistique optimale pour la résolution des MDP contraints (CMDP) reste inconnue. Nous résolvons cette question en fournissant des limites supérieures et inférieures minimax sur la complexité de l'échantillon pour l'apprentissage de politiques quasi-optimales dans un PDMC actualisé avec accès à un modèle génératif (simulateur). En particulier, nous concevons un algorithme basé sur le modèle qui prend en compte deux paramètres : (i) la faisabilité relaxée, où de petites violations de contraintes sont autorisées, et (ii) la faisabilité stricte, où la politique de sortie doit satisfaire la contrainte. Pour (i), nous prouvons que notre algorithme retourne une politique ϵ-optimale avec une probabilité de 1-δ, en effectuant O~(SAlog(1/δ)(1-γ)3ϵ2) requêtes au modèle génératif, ce qui correspond à la complexité de l'échantillon pour les MDPs sans contrainte. Pour (ii), nous montrons que la complexité d'échantillonnage de l'algorithme est limitée supérieurement par A log O~(SAlog(1/δ)(1-γ)5ϵ2ζ2) où ζ est la constante de Slater dépendant du problème qui caractérise la taille de la région réalisable. Enfin, nous prouvons une borne inférieure correspondante pour le cadre de faisabilité strict, obtenant ainsi les premières bornes optimales quasi minimax pour les CMDP actualisés. Nos résultats montrent que l'apprentissage des CMDP est aussi facile que celui des MDP lorsque de petites violations de contraintes sont autorisées, mais qu'il est intrinsèquement plus difficile lorsque nous exigeons une violation nulle des contraintes.

Apprentissage par renforcement efficace par rapport à l'échantillon pour les jeux de Markov partiellement observables.

Qinghua Liu - Csaba Szepesvari - Chi Jin

Cet article examine les tâches difficiles de l'apprentissage par renforcement multi-agents (MARL) dans le cadre de l'observabilité partielle, où chaque agent ne voit que ses propres observations et actions individuelles qui révèlent des informations incomplètes sur l'état sous-jacent du système. Cet article étudie ces tâches dans le cadre du modèle général des jeux de Markov partiellement observables (POMGs) multijoueurs à somme globale, qui est beaucoup plus vaste que le modèle standard des jeux à information imparfaite de forme extensive (IIEFGs). Nous identifions une riche sous-classe de POMGs ---- POMGs faiblement révélateurs --- dans lesquels l'apprentissage efficace par échantillonnage est réalisable. Dans le cadre d'un jeu personnel, nous prouvons qu'un algorithme simple combinant l'optimisme et l'estimation du maximum de vraisemblance (MLE) est suffisant pour trouver des équilibres de Nash approximatifs, des équilibres corrélés, ainsi que des équilibres corrélés grossiers de POMGs faiblement révélateurs, dans un nombre polynomial d'échantillons lorsque le nombre d'agents est petit. Dans le cadre d'un jeu contre des adversaires, nous montrons qu'une variante de notre algorithme MLE optimiste est capable d'atteindre un regret sublinéaire lorsqu'elle est comparée aux politiques maximales optimales. À notre connaissance, ce travail fournit la première ligne de résultats efficaces en termes d'échantillons pour l'apprentissage des POMGs.

Sur l'enseignement par lot avec une complexité d'échantillon limitée par VCD

Farnam Mansouri - Hans Simon - Adish Singla - Sandra Zilles

Dans l'enseignement automatique, un concept est représenté par (et déduit de) un petit nombre d'exemples étiquetés. Divers modèles d'enseignement dans la littérature présentent l'interaction entre l'enseignant et l'apprenant de manière à obtenir une faible complexité (en termes de nombre d'exemples requis pour l'enseignement d'un concept) tout en obéissant à certaines contraintes destinées à empêcher une collusion injuste entre l'enseignant et l'apprenant. Ces dernières années, un objectif majeur de la recherche a été de montrer des relations intéressantes entre la complexité de l'enseignement et la dimension VC (VCD). Jusqu'à présent, la seule relation intéressante connue dans le cadre de l'enseignement par lots est une limite supérieure quadratique dans la VCD, sur un paramètre appelé dimension d'enseignement récursif. La seule limite supérieure connue de la complexité de l'enseignement qui est linéaire dans la VCD a été obtenue dans un modèle d'enseignement par séquences plutôt que par lots. Cet article est le premier à fournir une limite supérieure de la VCD sur un paramètre de complexité d'enseignement par lots. Ce paramètre, appelé STDmin, est présenté ici comme un modèle d'enseignement qui intègre intuitivement une notion d'"importance" d'un exemple pour un concept. En concevant le modèle d'enseignement STDmin, nous soutenons que la notion standard d'absence de collusion de la littérature peut être inadéquate pour certaines applications ; nous proposons donc trois propriétés souhaitables de la complexité de l'enseignement et démontrons qu'elles sont satisfaites par STDmin.

Ateliers

Deuxième atelier sur le traitement efficace du langage naturel et de la parole (ENLSP-II)

Mehdi Rezagholizadeh - Peyman Passban - Yue Dong - Lili Mou - Pascal Poupart - Ali Ghodsi - Qun Liu

La deuxième version de l'atelier sur le traitement efficace du langage naturel et de la parole (ENLSP-II) se concentre sur les problèmes fondamentaux et les défis à relever pour rendre le traitement du langage naturel et de la parole (en particulier les modèles pré-entraînés) plus efficace en termes de données, de modèles, de formation et d'inférence. Le programme de l'atelier offre une plateforme interactive pour rassembler différents experts et talents du monde universitaire et de l'industrie par le biais de conférences invitées, de discussions en panel, de soumissions d'articles, de revues, de posters interactifs, de présentations orales et d'un programme de mentorat. Il s'agira d'une occasion unique d'aborder les problèmes d'efficacité des modèles actuels, de créer des liens, d'échanger des idées et de réfléchir à des solutions, et de favoriser de futures collaborations. Les sujets de cet atelier peuvent intéresser les personnes travaillant sur l'apprentissage automatique général, l'apprentissage profond, l'optimisation, la théorie et les applications NLP & Speech.

Atelier sur l'apprentissage par renforcement profond

Karol Hausman - Qi Zhang - Matthew Taylor - Martha White - Suraj Nair - Manan Tomar - Risto Vuorio - Ted Xiao - Zeyu Zheng

Ces dernières années, l'utilisation de réseaux neuronaux profonds comme approximateurs de fonctions a permis aux chercheurs d'étendre les techniques d'apprentissage par renforcement pour résoudre des tâches de contrôle de plus en plus complexes. Le domaine émergent de l'apprentissage par renforcement profond a conduit à des résultats empiriques remarquables dans des domaines riches et variés comme la robotique, les jeux de stratégie et les interactions multi-agents. Cet atelier réunira des chercheurs travaillant à l'intersection de l'apprentissage profond et de l'apprentissage par renforcement, et il aidera les chercheurs intéressés en dehors du domaine à obtenir une vue d'ensemble de l'état actuel de l'art et des directions potentielles pour les contributions futures.

Atelier sur l'apprentissage par renforcement pour la vie réelle (RL4RealLife)

Yuxi Li - Emma Brunskill - Minmin Chen - Omer Gottesman - Lihong Li - Yao Liu - Zhiwei Tony Qin - Matthew Taylor

Découvrez comment améliorer l'adoption de la RL dans la pratique, en discutant des principaux problèmes de recherche, des SOTA, et des histoires de réussite, des idées, des leçons, des algorithmes pratiques de RL, des questions pratiques et des applications avec des experts de premier plan du monde universitaire et de l'industrie à l'atelier RL4RealLife de NeurIPS 2022.

Concours

Défi de réarrangement de l'habitat

Andrew Szot - Karmesh Yadav - Alexander Clegg - Vincent-Pierre Berges - Aaron Gokaslan - Angel Chang - Manolis Savva - Zsolt Kira - Dhruv Batra

Nous proposons le défi du réarrangement de l'habitat. Plus précisément, un robot virtuel (le manipulateur mobile Fetch) est lancé dans un environnement de simulation inédit et doit réorganiser des objets depuis leur position initiale jusqu'à la position souhaitée. Il s'agit de prendre et de placer des objets dans des récipients (comptoir, évier, canapé, table) et d'ouvrir et de fermer des conteneurs (tiroirs, réfrigérateurs) selon les besoins. Le robot fonctionne entièrement à partir de capteurs embarqués - caméras RVB-D montées sur la tête et les bras, capteurs proprioceptifs de position articulaire (pour le bras) et capteurs d'égomotion (pour la base mobile) - et ne peut accéder à aucune information d'état privilégiée (pas de cartes préconstruites, pas de modèles 3D de pièces ou d'objets, pas de capteurs physiquement implausibles fournissant des informations sur la masse, la friction et l'articulation des conteneurs). Il s'agit d'une tâche difficile d'IA incarnée impliquant la perception incarnée, la copie mobile, la prise de décision séquentielle dans des tâches à long terme et (potentiellement) l'apprentissage par renforcement et imitation. Le développement de tels systèmes intelligents incarnés est un objectif d'une grande valeur scientifique et sociétale, y compris des applications pratiques dans les robots assistants domestiques.

Les SMARTS de la conduite

Amir Rasouli - Matthew Taylor - Iuliia Kotseruba - Tianpei Yang - Randolph Goebel - Soheil Mohamad Alizadeh Shabestary - Montgomery Alban - Florian Shkurti - Liam Paull

Driving SMARTS est un concours régulier visant à s'attaquer aux problèmes causés par le changement de distribution des contextes d'interaction dynamique qui sont prévalents dans la conduite autonome (DA) du monde réel. Le concours proposé est conçu pour soutenir des solutions méthodologiques diverses, telles que l'apprentissage par renforcement (RL) et les méthodes d'apprentissage hors ligne, en utilisant une combinaison de données de conduite autonome naturelles et la plateforme de simulation open-source SMARTS. La structure en deux volets permet de se concentrer sur différents aspects du changement de distribution. La piste 1 est ouverte à toutes les méthodes et donnera aux chercheurs en ML de différents horizons l'occasion de résoudre un défi réel de conduite autonome. La piste 2 est conçue pour les méthodes d'apprentissage strictement hors ligne. Par conséquent, des comparaisons directes peuvent être faites entre différentes méthodes dans le but d'identifier de nouvelles directions de recherche prometteuses. Le dispositif proposé consiste en 1) des données de conduite autonome du monde réel rejouées en simulation pour assurer la fidélité des scénarios, 2) un cadre accueillant diverses méthodes de résolution du problème, et 3) deux lignes de base : aléatoire et basée sur RL. En tant que tel, il offre une occasion unique pour l'étude raisonnée de divers aspects du déploiement des véhicules autonomes.

Discussions éclair

Exposés éclairs 6A-4

Angel Chang


Exposés éclairs 1B-4

Lili Mou

Auteurs

Angel Chang

Martha White

Lili Mou

Linglong Kong

Richard S. Sutton

Randy Goebel

Danica J. Sutherland

Dale Schuurmans

Csaba Szepesvári

Bei Jiang

Partager