Online Optimization and Learning in a Complex Environment
Abstract
The main focus of our long-term research is on the fundamental aspects of sequential de-cision making under uncertainty, when inform""ation about the past and current environment is accessible through heterogeneous datasets, possibly noisy and/or adversarial in natu""re, and when the future environment is not perfectly known in advance and may adapt to past decisions.More speci~cally, in this pr""oposal, we are interested in the interplay of three main phe-nomena (heterogeneous and dynamically generated input data from various"" sources, includ-ing noisy and/or adversarial ones, online decisions, and online learning), and the corre-sponding fundamental quest"ions when facing a problem exhibiting one or several of these phenomena: (i) how to properly model and quantify the degree of uncert"ainty in such a problem, and its impact on our ability to ~solve~ it, (ii) how to simultaneously optimize and learn in such an envir""onment, and (iii) how to design provably good algorithms for such problems.In our current ONR research grant N00014-15-1-2083 (~On""line Optimization and Learn-ing Problems Under Uncertainty~), we have addressed some of these questions (assuming perfect informatio"n about the past) concentrating our e~orts on some basic canonical online optimization problems such as (i) online versions of sched"uling problems, (ii) online versions of various matching problems, (iii) online versions of general resource allocation problems, an"d (iv) online convex optimization and games. We also started to include key concepts of online learning into our general online optimization framework using extensions of the multi-armed bandit benchmark model for repeated decision-making in stochastic environ-men"ts with limited feedback on the outcomes of alternatives.The systematic integration of online optimization and online learning, to""gether with the use of machine learning techniques, will be a central approach of the research in this renewal. We will also conside""r several new fundamental questions within our long-term research agenda which have emerged as part of our recent research e~ort, de"aling with (i) low rank matrix completion problems under noisy and/or adversarial input and (ii) decentralized and/or distributed versions of the multi-armed bandit models.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 20, 2018
- Source ID
- N000141812122
Entities
People
- Patrick Jaillet
Organizations
- Massachusetts Institute of Technology
- Office of Naval Research
- United States Navy