Search

In many real-world situations, there are constraints on the ways in which a physical system can be manipulated. We investigate the entropy production (EP) and extractable work involved in bringing a system from some initial distribution $p$ to some final distribution $p'$, given that the set of master equations available to the driving protocol obeys some constraints. We first derive general bounds on EP and extractable work, as well as a decomposition of the nonequilibrium free energy into an "accessible free energy" (which can be extracted as work, given a set of constraints) and an "inaccessible free energy" (which must be dissipated as EP). In a similar vein, we consider the thermodynamics of information in the presence of constraints, and decompose the information acquired in a measurement into "accessible" and "inaccessible" components. This decomposition allows us to consider the thermodynamic efficiency of different measurements of the same system, given a set of constraints. We use our framework to analyze protocols subject to symmetry, modularity, and coarse-grained constraints, and consider various examples including the Szilard box, the 2D Ising model, and a multi-particle flashing ratchet.

Recent work has shown how information theory extends conventional full-rationality game theory to allow bounded rational agents. The associated mathematical framework can be used to solve distributed optimization and control problems. This is done by translating the distributed problem into an iterated game, where each agent's mixed strategy (i.e. its stochastically determined move) sets a different variable of the problem. So the expected value of the objective function of the distributed problem is determined by the joint probability distribution across the moves of the agents. The mixed strategies of the agents are updated from one game iteration to the next so as to converge on a joint distribution that optimizes that expected value of the objective function. Here, a set of new techniques for this updating is presented. These and older techniques are then extended to apply to uncountable move spaces. We also present an extension of the approach to include (in)equality constraints over the underlying variables. Another contribution is that we show how to extend the Monte Carlo version of the approach to cases where some agents have no Monte Carlo samples for some of their moves, and derive an "automatic annealing schedule".

Recent work on the foundational underpinnings of black-box optimization has begun to uncover a rich mathematical structure. In particular, it is now known that an inner product between the optimization algorithm and the distribution of optimization problems likely to be encountered fixes the distribution over likely performances in running that algorithm. One ramification of this is the "No Free Lunch" (NFL) theorems, which state that any two algorithms are equivalent when their performance is averaged across all possible problems. This highlights the need for exploiting problem-specific knowledge to achieve better than random performance. In this paper, we present a general framework covering most optimization scenarios. In addition to the optimization scenarios addressed in the NFL results, this framework covers multiarmed bandit problems and evolution of multiple coevolving players. As a particular instance of the latter, it covers "self-play" problems. In these problems, the set of players work together to produce a champion, who then engages one or more antagonists in a subsequent multiplayer game. In contrast to the traditional optimization case where the NFL results hold, we show that in self-play there are free lunches: in coevolution some algorithms have better performance than other algorithms, averaged across all possible problems. However, in the typical coevolutionary scenarios encountered in biology, where there is no champion, the NFL theorems still hold.

We examine the potential for a simple auction to allocate arrival slots during Ground Delay Programs (GDPs) more efficiently than the currently used system. We find that the second-price slot auction has the potential to lower social costs but further analysis is needed to determine which pre-GDP schedules are best suited for an auction. The analysis of these auctions uses Predictive Game Theory (PGT) Wolpert and Bono (2013, 2010), a new approach that produces a probability distribution over strategies instead of an equilibrium set. Furthermore, the slot auction game of this paper represents the first application of PGT to a game of imperfect information and to a pure strategy space.

We explore the two-armed bandit with Gaussian payoffs as a theoretical model for optimization. The problem is formulated from a Bayesian perspective, and the optimal strategy for both one and two pulls is provided. We present regions of parameter space where a greedy strategy is provably optimal. We also compare the greedy and optimal strategies to one based on a genetic algorithm. In doing so, we correct a previous error in the literature concerning the Gaussian bandit problem and the supposed optimality of genetic algorithms for this problem. Finally, we provide an analytically simple bandit model that is more directly applicable to optimization theory than the traditional bandit problem and determine a near-optimal strategy for that model.

A framework is developed to explore the connection between effective optimization algorithms and the problems they are solving. A number of "no free lunch" (NFL) theorems are presented which establish that for any algorithm, any elevated performance over one class of problems is offset by performance over another class. These theorems result in a geometric interpretation of what it means for an algorithm to be well suited to an optimization problem. Applications of the NFL theorems to information-theoretic aspects of optimization and benchmark measures of performance are also presented. Other issues addressed include time-varying optimization problems and a priori "head-to-head" minimax distinctions between optimization algorithms, distinctions that result despite the NFL theorems' enforcing of a type of uniformity over all algorithms.

We address the question: “Are some classes of combinatorial optimization problems intrinsically harder than others, without regard to the algorithm one uses, or can difficulty only be assessed relative to particular algorithms?” We provide a measure of the hardness of a particular optimization problem for a particular optimization algorithm and present two algorithm-independent quantities that use this measure to provide answers to our question. In the first of these we average hardness over all possible algorithms and show that according to this quantity, there are no distinctions between optimization problems. In this sense no problems are intrinsically harder than others. For the second quantity, rather than average over all algorithms, we consider the level of hardness of a problem (or class of problems) for the associated optimal algorithm. By this criteria there are classes of problems that are intrinsically harder than others.

We consider the problem of designing the the utility functions of the utility-maximizing agents in a multi-agent system so that they work synergistically to maximize a global utility. The particular problem domain we explore is the control of network routing by placing agents on all the routers in the network. Conventional approaches to this task have the agents all use the Ideal Shortest Path routing Algorithm (ISPA). We demonstrate that in many cases, due to the side-effects of one agent's actions on another agent's performance, having agents use ISPA's is suboptimal as far as global aggregate cost is concerned, even when they are only used to route infinitesimally small amounts of traffic. The utility functions of the individual agents are not ``aligned'' with the global utility, intuitively speaking. As a particular example of this we present an instance of Braess' paradox in which adding new links to a network whose agents all use the ISPA results in a decrease in overall throughput. We also demonstrate that load-balancing, in which the agents' decisions are collectively made to optimize the global cost incurred by all traffic currently being routed, is suboptimal as far as global cost averaged across time is concerned. This is also due to `side-effects', in this case of current routing decision on future traffic. The mathematics of Collective Intelligence (COIN) is concerned precisely with the issue of avoiding such deleterious side-effects in multi-agent systems, both over time and space. We present key concepts from that mathematics and use them to derive an algorithm whose ideal version should have better performance than that of having all agents use the ISPA, even in the infinitesimal limit. We present experiments verifying this, and also showing that a machine-learning-based version of this COIN algorithm in which costs are only imprecisely estimated via empirical means (a version potentially applicable in the real world) also outperforms the ISPA, despite having access to less information than does the ISPA. In particular, this COIN algorithm almost always avoids Braess' paradox.

In experimental tests of human behavior in unstructured bargaining games, typically many joint utility outcomes are found to occur, not just one. This suggests we predict the outcome of such a game as a probability distribution. This is in contrast to what is conventionally done (e.g, in the Nash bargaining solution), which is predict a single outcome. We show how to translate Nash’s bargaining axioms to provide a distribution over outcomes rather than a single outcome. We then prove that a subset of those axioms forces the distribution over utility outcomes to be a power-law distribution. Unlike Nash’s original result, our result holds even if the feasible set is finite. When the feasible set is convex and comprehensive, the mode of the power law distribution is the Harsanyi bargaining solution, and if we require symmetry it is the Nash bargaining solution. However, in general these modes of the joint utility distribution are not the experimentalist’s Bayes-optimal predictions for the joint utility. Nor are the bargains corresponding to the modes of those joint utility distributions the modes of the distribution over bargains in general, since more than one bargain may result in the same joint utility. After introducing distributional bargaining solution concepts, we show how an external regulator can use them to optimally design an unstructured bargaining scenario. Throughout we demonstrate our analysis in computational experiments involving flight rerouting negotiations in the National Airspace System. We emphasize that while our results are formulated for unstructured bargaining, they can also be used to make predictions for noncooperative games where the modeler knows the utility functions of the players over possible outcomes of the game, but does not know the move spaces the players use to determine those outcomes.

Under its conventional positive interpretation, game theory makes predictions about the mixed strategy profile of the players in a noncooperative game by specifying a "solution set" of such profiles, e.g., the set of Nash equilibria of that game. Profiles outside of that set are implicitly assigned probability zero, and relative probabilities of profiles in that set are not provided. In contrast, Bayesian analysis does not make predictions about the state of a system by specifying a set of possible states of that system. Rather it provides a probability density over all those states, conditioned on all relevant information we have concerning the system. So when the "state of a system" is the strategy profile of the players of a game, and our information comprises the game specification, a Bayesian analysis would result in a posterior density over the set of all profiles, conditioned on the game specification. Evidently the very form of a prediction provided by a Bayesian analysis is different from the form provided by solution sets. In this paper, we show how to construct a Bayesian posterior density over profiles and discuss its practical advantages over solution sets. As an example, by combining this posterior density with a loss function of the scientist making the prediction, standard decision theory fixes the unique Bayes-optimal prediction of the profile conditioned on the game specification. So it provides a universal refinement. As another example, Bayesian regulators of the players involved in a game would use such a posterior density to make Bayes-optimal choices of a mechanism to control player behavior (and thereby fully adhere to Savage's axioms). In particular, a regulator can do this in situations where conventional mechanism design cannot provide advice. We illustrate all of this numerically with Cournot duopoly games.

Conventionally, game theory predicts that the mixed strategy profile of players in a noncooperative game will satisfy some equilibrium concept. Relative probabil- ities of the strategy profiles satisfying the concept are unspecified, and all strategies not satisfying it are implicitly assigned probability zero. As an alternative, we re- cast the prediction problem of game theory as statistically estimating the strategy profile, from "data" that consists of the game specification. This replaces the focus of game theory, on specifying a set of "equilibrium" mixed strategies, with a new focus, on specifying a probability density over all mixed strategies. We explore a Bayesian version of such a Predictive Game Theory (PGT). We show that for some games the peaks of the posterior over strategy profiles approximate quantal response equilibria. We also show how PGT provides a best single prediction for any noncooperative game, i.e., a universal refinement. We also show how regula- tors can use PGT to make optimal decisions in situations where conventional game theory cannot provide advice.

A significant body of research under the rubric of blackbox optimization addresses the problem of optimization in a design space where the designs are evaluated by a computer simulation. For many such simulations, conventional local optimization methods prove inadequate, owing to the presence of local minima, local non-smoothness, and so on. A more effective approach would learn the global characteristics of the design space, and sample from disparate regions as it progresses. Several probabilistic approaches to this problem are based on the following idea: during the course of any search process, our partial knowledge of the design space grows as we evaluate a growing number of designs, and this knowledge can be elegantly expressed in terms of probability distributions. This is usually done using surrogate models, or data fits. We would like to use this partial knowledge to lead us to promising new designs, and this involves searching the data fit for points where the uncertainty of the fit, in conjunction with the fit itself, indicates a good chance of finding a improved design. This is the basis for the well-known Efficient Global Optimization (EGO) algorithm. This task can be regarded as an auxiliary optimization problem, but one that has some undesirable characteristics, including large flat regions and multiple local optima. Previous solution approaches have included branch and bound (the EGO algorithm), and local optimization with multi-start. In this paper, we present a new approach, itself based on probability distributions. Probability Collectives (PC) is an optimization framework in which a given optimization problem is transformed to one over probability distributions. This transformation often enables us to overcome problems such as local non-smoothness and multiple local optima. One particular PC approach is closely related to function smoothing and filtering. Our formulation is a type of Monte Carlo Optimization, often encountered in machine learning algorithms. We briefly introduce this approach, and apply it to the auxiliary optimization problem described above. Finally, we compare this technique with other algorithms, including a heuristic sampling algorithm, and a genetic algorithm.

In this paper, we review an optimization technique called Probability Collectives (PC), and compare its approach with that of quadratic Response Surface Methods (RSM), on some standard continuous test functions for unconstrained minimization, both in the presence and absence of uncertainty in the function evaluations. Probability Collectives (PC) is an optimization framework where optimization is performed over probability distributions over the variables of interest, rather than the variables themselves. In order to find a solution to the original optimization problem, we sample the final solution of the transformed problem, which is a probability distribution. In other words, PC is a transform technique with the special property that the inverse transform is performed stochastically. This transformation yields algorithms that are relatively insensitive to structural properties of the underlying objective function, like continuity, convexity, and dierentiability; optimization under uncertainty becomes natural and straightforward; finally, the distributions yield sensitivity information about the original problem. Some PC algorithms bear a strong resemblance to RSM, and in this paper, we investigate these similarities, and compare performances of these techniques on some simple test functions.

In extensive form noncooperative game theory, at each instant t, each agent i sets its state x i independently of the other agents, by sampling an associated distribution, q i(x i). The coupling between the agents arises in the joint evolution of those distributions. Distributed control problems can be cast the same way. In those problems the system designer sets aspects of the joint evolution of the distributions to try to optimize the goal for the overall system. Now information theory tells us what the separate q i of the agents are most likely to be if the system were to have a particular expected value of the objective function G(x 1, x 2, ...). So one can view the job of the system designer as speeding an iterative process. Each step of that process starts with a specified value of E(G), and the convergence of the q i to the most likely set of distributions consistent with that value. After this the target value for E q(G) is lowered, and then the process repeats. Previous work has elaborated many schemes for implementing this process when the underlying variables x i all have a finite number of possible values and G does not extend to multiple instants in time. That work also is based on a fixed mapping from agents to control devices, so that the the statistical independence of the agents’ moves means independence of the device states. This paper also extends that work to relax all of these restrictions. This extends the applicability of that work to include continuous spaces and Reinforcement Learning. This paper also elaborates how some of that earlier work can be viewed as a first-principles justification of evolution-based search algorithms.

We compare Genetic Algorithms (GA's) with Probability Collectives (PC), a new framework for distributed optimization and control. In contrast to GA's, PC-based methods do not update populations of solutions. Instead they update an explicitly parameterized probability distribution p over the space of solutions. That updating of p arises as the optimization of a functional of p. The functional is chosen so that any p that optimizes it should be p peaked about good solutions. The PC approach has deep connections with both game theory and statistical physics. We review the PC approach using its motivation as the information theoretic formulation of bounded rationality for multi-agent systems (MAS). It is then compared with GA's on a diverse set of problems. To handle high dimensional surfaces, in the PC method investigated here p is restricted to a product distribution. Each distribution in that product is controlled by a separate agent. The test functions were selected for their difficulty using either traditional gradient descent or genetic algorithms. On those functions the PC-based approach significantly outperforms traditional GA's in both rate of descent, trapping in false minima, and long term optimization.

Aerospace systems continue to grow in complexity while demanding optimal performance. This requires the systems to be both designed and controlled optimally. Aerospace systems are also typically comprised of many interacting components, some of which may have competing requirements. The optimization approaches used for aerospace systems usually require centralized coordination and synchronous updates. In addition, while the approaches treat the large numbers of variables, they may not take advantage of the fact that the coupling may only be between a relatively small number of the variables. Distributed optimization algorithms, such as the approach based upon collectives presented in this paper, attempt to exploit this aspect. A collective is deflned as a multi-agent system where each agent is self-interested and capable of learning. Furthermore, a collective has a specifled system objective which rates the performance of the joint actions of the agents. Although collectives have been used for a number of distributed optimization problems in computer science, recent developments based upon Probability Collectives (PC) theory enhance their applicability to discrete, continuous, mixed, and constrained optimization problems. This paper will present the theoretical underpinnings of the approach for these various problem domains. Several example problems are used to illustrate the technique and to provide insight into its behavior. The examples include discrete, constrained, and continuous problems. In particular a constrained discrete structural optimization and a continuous trajectory optimization illustrate the breadth of the collectives approach.

We consider the problem of designing a set of computational agents so that as they all pursue their self-interests a global function G of the collective system is optimized. Three factors govern the quality of such design. The first relates to conventional exploration-exploitation search algorithms for finding the maxima of such a global function, e.g., simulated annealing. Game-theoretic algorithms instead are related to the second of those factors, and the third is related to techniques from the field of machine learning. Here we demonstrate how to exploit all three factors by modifying the search algorithm's exploration stage so that rather than by random sampling, each coordinate of the underlying search space is controlled by an associated machine-learning-based ``player'' engaged in a non-cooperative game. Experiments demonstrate that this modification improves SA by up to an order of magnitude for bin-packing and for a model of an economic process run over an underlying network. These experiments also reveal novel small worlds phenomena.

Product distribution theory is a new collective intelligence-based framework for analyzing and controlling distributed systems. Its usefulness in distributed stochastic optimization is illustrated here through an airline fleet assignment problem. This problem involves the allocation of aircraft to a set of flights legs in order to meet passenger demand, while satisfying a variety of linear and non-linear constraints. Over the course of the day, the routing of each aircraft is determined in order to minimize the number of required flights for a given fleet. The associated flow continuity and aircraft count constraints have led researchers to focus on obtaining quasi-optimal solutions, especially at larger scales. In this paper, the authors propose the application of this new stochastic optimization algorithm to a non-linear objective cold start fleet assignment problem. Results show that the optimizer can successfully solve such highly-constrained problems (130 variables, 184 constraints).

Often adaptive, distributed control can be viewed as an iterated game between independent players. The coupling between the players' mixed strategies, arising as the system evolves, is determined by the system designer. Information theory tells us that the most likely joint strategy of the players, given a value of the expectation of the overall control objective function, is the minimizer of a Lagrangian function of the joint strategy. So the goal of the system designer is to speed evolution of the joint strategy to that Lagrangian minimizing point, lower the expected value of the control objective function, and repeat. Here, we discuss how to do this using local descent procedures, and thereby achieve efficient, adaptive, distributed control.

The "Collective Intelligence" (COIN) framework concerns the design of collectives of agents so that as those agents strive to maximize their individual utility functions, their interaction causes a provided "world" utility function concerning the entire collective to be also maximized. Here we show how to extend that framework to scenarios having Markovian dynamics when no re-evolution of the system from counter-factual initial conditions (an often expensive calculation) is permitted. Our approach transforms the(time-extended) argument of each agent's utility function before evaluating that function. This transformation has benefits in scenarios not involving Markovian dynamics, in particular scenarios where not all of the arguments of an agent's utility function are observable. We investigate this transformation in simulations involving both linear and quadratic (nonlinear) dynamics. In addition, we find that a certain subset of these transformations, which result in utilities that have low "opacity (analogous to having high signal to noise) but are not "factored" (analogous to not being incentive compatible), reliably improve performance over that arising with factored utilities. We also present a Taylor Series method for the fully general nonlinear case.