Publications

The Value Function Polytope in Reinforcement Learning
Robert Dadashi
Adrien Ali Taiga
Nicolas Le Roux
Dale Schuurmans
Marc Gendron-Bellemare
We establish geometric and topological properties of the space of value functions in finite state-action Markov decision processes. Our main… (see more) contribution is the characterization of the nature of its shape: a general polytope (Aigner et al., 2010). To demonstrate this result, we exhibit several properties of the structural relationship between policies and value functions including the line theorem, which shows that the value functions of policies constrained on all but one state describe a line segment. Finally, we use this novel perspective to introduce visualizations to enhance the understanding of the dynamics of reinforcement learning algorithms.
2019-05-24
Proceedings of the 36th International Conference on Machine Learning (published)
proceedings.mlr.press
arxiv.org
Understanding the impact of entropy on policy optimization
Zafarali Ahmed
Nicolas Le Roux
Mohammad Norouzi
Dale Schuurmans
Entropy regularization is commonly used to improve policy optimization in reinforcement learning. It is believed to help with \emph{explorat… (see more)ion} by encouraging the selection of more stochastic policies. In this work, we analyze this claim using new visualizations of the optimization landscape based on randomly perturbing the loss function. We first show that even with access to the exact gradient, policy optimization is difficult due to the geometry of the objective function. Then, we qualitatively show that in some environments, a policy with higher entropy can make the optimization landscape smoother, thereby connecting local optima and enabling the use of larger learning rates. This paper presents new tools for understanding the optimization landscape, shows that policy entropy serves as a regularizer, and highlights the challenge of designing general-purpose policy optimization algorithms.
2019-05-24
Proceedings of the 36th International Conference on Machine Learning (published)
proceedings.mlr.press
arxiv.org
Usability of Virtual Reality Application Through the Lens of the User Community: A Case Study
Wenting Wang
Jinghui Cheng
Jin Guo
The increasing availability and diversity of virtual reality (VR) applications highlighted the importance of their usability. Function-orien… (see more)ted VR applications posed new challenges that are not well studied in the literature. Moreover, user feedback becomes readily available thanks to modern software engineering tools, such as app stores and open source platforms. Using Firefox Reality as a case study, we explored the major types of VR usability issues raised in these platforms. We found that 77% of usability feedbacks can be mapped to Nielsen's heuristics while few were mappable to VR-specific heuristics. This result indicates that Nielsen's heuristics could potentially help developers address the usability of this VR application in its early development stage. This work paves the road for exploring tools leveraging the community effort to promote the usability of function-oriented VR applications.
2019-05-02
Extended Abstracts of the 2019 CHI Conference on Human Factors in Computing Systems (published)
doi.org
arxiv.org
Continual Learning with Self-Organizing Maps
Pouya Bashivan
Martin Schrimpf
Robert Ajemian
Irina Rish
Matthew D Riemer
Yuhai Tu
Despite remarkable successes achieved by modern neural networks in a wide range of applications, these networks perform best in domain-speci… (see more)fic stationary environments where they are trained only once on large-scale controlled data repositories. When exposed to non-stationary learning environments, current neural networks tend to forget what they had previously learned, a phenomena known as catastrophic forgetting. Most previous approaches to this problem rely on memory replay buffers which store samples from previously learned tasks, and use them to regularize the learning on new ones. This approach suffers from the important disadvantage of not scaling well to real-life problems in which the memory requirements become enormous. We propose a memoryless method that combines standard supervised neural networks with self-organizing maps to solve the continual learning problem. The role of the self-organizing map is to adaptively cluster the inputs into appropriate task contexts - without explicit labels - and allocate network resources accordingly. Thus, it selectively routes the inputs in accord with previous experience, ensuring that past learning is maintained and does not interfere with current learning. Out method is intuitive, memoryless, and performs on par with current state-of-the-art approaches on standard benchmarks.
2019-04-19
ArXiv (preprint)
arxiv.org
arxiv.org
Connecting Weighted Automata and Recurrent Neural Networks through Spectral Learning
Guillaume Rabusseau
Tianyu Li
Doina Precup
In this paper, we unravel a fundamental connection between weighted finite automata~(WFAs) and second-order recurrent neural networks~(2-RNN… (see more)s): in the case of sequences of discrete symbols, WFAs and 2-RNNs with linear activation functions are expressively equivalent. Motivated by this result, we build upon a recent extension of the spectral learning algorithm to vector-valued WFAs and propose the first provable learning algorithm for linear 2-RNNs defined over sequences of continuous input vectors. This algorithm relies on estimating low rank sub-blocks of the so-called Hankel tensor, from which the parameters of a linear 2-RNN can be provably recovered. The performances of the proposed method are assessed in a simulation study.
2019-04-11
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics (published)
proceedings.mlr.press
arxiv.org
Distributional reinforcement learning with linear function approximation
Marc Gendron-Bellemare
Nicolas Le Roux
Pablo Samuel Castro
Subhodeep Moitra
Despite many algorithmic advances, our theoretical understanding of practical distributional reinforcement learning methods remains limited.… (see more) One exception is Rowland et al. (2018)'s analysis of the C51 algorithm in terms of the Cramer distance, but their results only apply to the tabular setting and ignore C51's use of a softmax to produce normalized distributions. In this paper we adapt the Cramer distance to deal with arbitrary vectors. From it we derive a new distributional algorithm which is fully Cramer-based and can be combined to linear function approximation, with formal guarantees in the context of policy evaluation. In allowing the model's prediction to be any real vector, we lose the probabilistic interpretation behind the method, but otherwise maintain the appealing properties of distributional approaches. To the best of our knowledge, ours is the first proof of convergence of a distributional algorithm combined with function approximation. Perhaps surprisingly, our results provide evidence that Cramer-based distributional methods may perform worse than directly approximating the value function.
2019-04-11
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics (published)
proceedings.mlr.press
arxiv.org
Multitask Metric Learning: Theory and Algorithm
Boyu Wang
Hejia Zhang
Peng Liu
Zebang Shen
Joelle Pineau
In this paper, we study the problem of multitask metric learning (mtML). We first examine the generalization bound of the regularized mtML f… (see more)ormulation based on the notion of algorithmic stability, proving the convergence rate of mtML and revealing the trade-off between the tasks. Moreover, we also establish the theoretical connection between the mtML, single-task learning and pooling-task learning approaches. In addition, we present a novel boosting-based mtML (mt-BML) algorithm, which scales well with the feature dimension of the data. Finally, we also devise an efficient second-order Riemannian retraction operator which is tailored specifically to our mt-BML algorithm. It produces a low-rank solution of mtML to reduce the model complexity, and may also improve generalization performances. Extensive evaluations on several benchmark data sets verify the effectiveness of our learning algorithm.
2019-04-11
International Conference on Artificial Intelligence and Statistics (published)
dblp.uni-trier.de
Multitask Metric Learning: Theory and Algorithm
Boyu Wang
Hejia Zhang
Peng Liu
Zebang Shen
Joelle Pineau
In this paper, we study the problem of multitask metric learning (mtML). We first examine the generalization bound of the regularized mtML f… (see more)ormulation based on the notion of algorithmic stability, proving the convergence rate of mtML and revealing the trade-off between the tasks. Moreover, we also establish the theoretical connection between the mtML, single-task learning and pooling-task learning approaches. In addition, we present a novel boosting-based mtML (mt-BML) algorithm, which scales well with the feature dimension of the data. Finally, we also devise an efficient second-order Riemannian retraction operator which is tailored specifically to our mt-BML algorithm. It produces a low-rank solution of mtML to reduce the model complexity, and may also improve generalization performances. Extensive evaluations on several benchmark data sets verify the effectiveness of our learning algorithm.
2019-04-11
International Conference on Artificial Intelligence and Statistics (published)
proceedings.mlr.press
Negative Momentum for Improved Game Dynamics
Gauthier Gidel
Reyhane Askari Hemmat
Mohammad Pezeshki
Gabriel Huang
Rémi LE PRIOL
Simon Lacoste-Julien
Ioannis Mitliagkas
Games generalize the single-objective optimization paradigm by introducing different objective functions for different players. Differentiab… (see more)le games often proceed by simultaneous or alternating gradient updates. In machine learning, games are gaining new importance through formulations like generative adversarial networks (GANs) and actor-critic systems. However, compared to single-objective optimization, game dynamics are more complex and less understood. In this paper, we analyze gradient-based methods with momentum on simple games. We prove that alternating updates are more stable than simultaneous updates. Next, we show both theoretically and empirically that alternating gradient updates with a negative momentum term achieves convergence in a difficult toy adversarial problem, but also on the notoriously difficult to train saturating GANs.
2019-04-11
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics (published)
proceedings.mlr.press
arxiv.org
A Survey on Practical Applications of Multi-Armed and Contextual Bandits
Djallel Bouneffouf
Irina Rish
In recent years, multi-armed bandit (MAB) framework has attracted a lot of attention in various applications, from recommender systems and i… (see more)nformation retrieval to healthcare and finance, due to its stellar performance combined with certain attractive properties, such as learning from less feedback. The multi-armed bandit field is currently flourishing, as novel problem settings and algorithms motivated by various practical applications are being introduced, building on top of the classical bandit problem. This article aims to provide a comprehensive review of top recent developments in multiple real-life applications of the multi-armed bandit. Specifically, we introduce a taxonomy of common MAB-based applications and summarize state-of-art for each of those domains. Furthermore, we identify important current trends and provide new perspectives pertaining to the future of this exciting and fast-growing field.
2019-04-02
ArXiv (preprint)
arxiv.org
arxiv.org
Multi-Agent Estimation and Filtering for Minimizing Team Mean-Squared Error
Mohammad Afshari
Aditya Mahajan
Motivated by estimation problems arising in autonomous vehicles and decentralized control of unmanned aerial vehicles, we consider multi-age… (see more)nt estimation and filtering problems in which multiple agents generate state estimates based on decentralized information and the objective is to minimize a coupled mean-squared error which we call team mean-square error. We call the resulting estimates as minimum team mean-squared error (MTMSE) estimates. We show that MTMSE estimates are different from minimum mean-squared error (MMSE) estimates. We derive closed-form expressions for MTMSE estimates, which are linear function of the observations where the corresponding gain depends on the weight matrix that couples the estimation error. We then consider a filtering problem where a linear stochastic process is monitored by multiple agents which can share their observations (with delay) over a communication graph. We derive expressions to recursively compute the MTMSE estimates. To illustrate the effectiveness of the proposed scheme we consider an example of estimating the distances between vehicles in a platoon and show that MTMSE estimates significantly outperform MMSE estimates and consensus Kalman filtering estimates.
2019-03-28
ArXiv (preprint)
doi.org
arxiv.org
Interpolation Consistency Training for Semi-Supervised Learning
Vikas Verma
Alex Lamb
Juho Kannala
Yoshua Bengio
David Lopez-Paz
2019-03-09
ArXiv (preprint)
doi.org
arxiv.org