THIS IS A CONTINUATION OF N00014-12-1-0998 Information Structures, Signaling, and Competitively Optimal Policies in Dece
Abstract
Short Work Statement:This proposal is aimed at developing a general mathematical framework, theory, and effi?cient algorithms for decentralized online optimization problems.Objective:This proposal is aimed at developing a general mathematical framework, theory, and effi?cient algorithms for decentralized online optimization problems. This development is motivated by the emergence of problems, involving a large number of autonomous agents who must cooperate in order to jointly optimize a given series of objectives in a dynamic and highly uncertain environment.Approach:The work in this proposal is concerned with optimization problems, in which the objective function varies with time in an arbitrary and unpredictable manner, and the agents knowledge of both the objective function and the behavior of other agents is purely local. Existing approaches in the literature on online optimization either consider the fully centralized case or focus on a particular model of decentralized processing, in which each agent must compute its own approximations of the entire vector of team decisions by exchanging information with other agents. In this model, whichdoes not take full advantage of the communication structure, the communication and the computation resources are allocated ine?ciently, and indeed canincrease rapidly with the number of agents.The proposed research addresses these major limitations by exporting insights and techniques from the disciplines of dynamic team decision theory and decentralized control. At the heart of our approach lies the concept of signaling, i.e., the possibility of the agents communicating through their decisions, effectively embedding in them the informationneeded by other agents and that otherwise would be accessible to them only in the fully centralized setting with perfect observations. In other words, signaling is the mechanism, by which the agents can approach, as closely as possible, the level of performance attainable in the centralized scenario. The theoretical study of information structures and their signaling potential will, in turn, enable the development and analysis of new e?cient algorithms for decentralized online optimization. The research team pulls together complementary expertise in online learning and optimization, dynamic game theory, and decentralized control, and is therefore uniquely positioned to carry out the proposed research.Overall Merits and ONR Relevance:This research is innovative in that it inlcudes the development of rigorous algorithmic-analysis techniques fordecentralized online optimization that provides performance predictions through sound estimates of the closeness a decentralized online solution to a centralized, global offline optimal solution; such performance guarantees contribute tremendously to trust in these systems, which is critical for their deployment. The Navy is moving towards deploying large, complex systems that are beyond centralized control. A canonical example of such a system is a fleet of unmanned vehicles with limited communications operating in a dynamic environment. Important characteristics of these systems are that 1) they are decentralized (i.e., system components can take independent actions), and 2) the environment in which the system operates is not necessarily known a priori,and is revealed over time. The objective of this topic is to develop scientific principles and algorithms for solvingdecentralized, online optimization problems.Progress:The PIs designed two algorithms that allow agents to correctly learn. In particular, both algorithms produce beliefs that concentrate on the correct hypotheses with probability 1. They proved geometric convergence rate for both algorithms. Unlike the existing rate results, the results are non-asymptotic and explicit in terms of learning parameters and problem characteristics. Thus, they can be used to design practical stopping criteria for the algorithms. One of the proposed algorithms has the be
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 23, 2016
- Source ID
- N000141612791
Entities
People
- Maxim Raginsky
Organizations
- Office of Naval Research
- United States Navy
- University of Illinois Urbana–Champaign