1,720,986 research outputs found
Discrete-time average-cost mean-field games on Polish spaces
No full textIn stochastic dynamic games, when the number of players is sufficiently large and the interactions between agents depend on empirical state distribution, one way to approximate the original game is to introduce infinite-population limit of the problem. In the infinite population limit, a generic agent is faced with a so-called mean-field game. In this paper, we study discrete-time mean-field games with average-cost criteria. Using average cost optimality equation and Kakutani's fixed point theorem, we establish the existence of Nash equilibria for mean-field games under drift and minorization conditions on the dynamics of each agent. Then, we show that the equilibrium policy in the mean-field game, when adopted by each agent, is an approximate Nash equilibrium for the corresponding finite-agent game with sufficiently many agents.TÜBİTAKPublisher versio
Partially Observed Discrete-Time Risk-Sensitive Mean Field Games
Get PDFIn this paper, we consider discrete-time partially observed mean-field games
with the risk-sensitive optimality criterion. We introduce risk-sensitivity
behaviour for each agent via an exponential utility function. In the game
model, each agent is weakly coupled with the rest of the population through its
individual cost and state dynamics via the empirical distribution of states. We
establish the mean-field equilibrium in the infinite-population limit using the
technique of converting the underlying original partially observed stochastic
control problem to a fully observed one on the belief space and the dynamic
programming principle. Then, we show that the mean-field equilibrium policy,
when adopted by each agent, forms an approximate Nash equilibrium for games
with sufficiently many agents. We first consider finite-horizon cost function,
and then, discuss extension of the result to infinite-horizon cost in the
next-to-last section of the paper.Comment: 37 pages. arXiv admin note: substantial text overlap with
arXiv:1705.02036, arXiv:1808.0392
Finite approximations in discrete-time stochastic control: quantized models and asymptotic optimality
No full textIn a unified form, this monograph presents fundamental results on the approximation of centralized and decentralized stochastic control problems, with uncountable state, measurement, and action spaces. It demonstrates how quantization provides a system-independent and constructive method for the reduction of a system with Borel spaces to one with finite state, measurement, and action spaces. In addition to this constructive view, the book considers both the information transmission approach for discretization of actions, and the computational approach for discretization of states and actions. Part I of the text discusses Markov decision processes and their finite-state or finite-action approximations, while Part II builds from there to finite approximations in decentralized stochastic control problems. This volume is perfect for researchers and graduate students interested in stochastic controls. With the tools presented, readers will be able to establish the convergence of approximation models to original models and the methods are general enough that researchers can build corresponding approximation results, typically with no additional assumptions
Value iteration algorithm for mean-field games
No full textIn the literature, existence of mean-field equilibria has been established for discrete-time mean field games under both the discounted cost and the average cost optimality criteria. In this paper, we provide a value iteration algorithm to compute stationary mean-field equilibrium for both the discounted cost and the average cost criteria, whose existence proved previously. We establish that the value iteration algorithm converges to the fixed point of a mean-field equilibrium operator. Then, using this fixed point, we construct a stationary mean-field equilibrium. In our value iteration algorithm, we use Q-functions instead of value functions.TÜBİTA
On weak feller continuity properties of non-linear filters
No full textWeak Feller property of controlled and control free Markov chains leads to many desirable properties. In control-free setups this leads to the existence of invariant probability measures for compact spaces and applicability of numerical approximation methods. For controlled setups, this leads to existence and approximation results for optimal control policies. We know from stochastic control theory that partially observed systems can be converted to fully observed systems by replacing the original state space with a probability measure-valued state space, with the corresponding kernel acting on probability measures known as the non-linear filter process. In this paper, we prove the weak Feller property of the non-linear filter process (i) first under weak continuity of the transition probability of controlled Markov chain and total variation continuity of its observation channel, and then, (ii) under total variation continuity of the transition probability of controlled Markov chain. The former result (i) has first appeared in Feinberg et. al. (2016). Here, we present a concise and easy to follow alternative proof for this existing result. The latter result (ii) establishes weak Feller property of non-linear filter process under conditions which have not been previously reported in the literature.Natural Sciences and Engineering Research Council of Canad
Finite-state approximation of Markov decision processes
No full textIn this chapter we study the finite-state approximation problem for computing near optimal policies for discrete-time MDPs with Borel state and action spaces, under discounted and average costs criteria. Even though existence and structural properties of optimal policies of MDPs have been studied extensively in the literature, computing such policies is generally a challenging problem for systems with uncountable state spaces. This situation also arises in the fully observed reduction of a partially observed Markov decision process even when the original system has finite state and action spaces. Here we show that one way to compute approximately optimal solutions for such MDPs is to construct a reduced model with a new transition probability and one-stage cost function by quantizing the state space, i.e., by discretizing it on a finite grid. It is reasonable to expect that when the one-stage cost function and the transition probability of the original model has certain continuity properties, the cost of the optimal policy for the approximating finite model converges to the optimal cost of the original model as the discretization becomes finer. Moreover, under additional continuity conditions on the transition probability and the one stage cost function we also obtain bounds on the accuracy of the approximation in terms of the number of points used to discretize the state space, thereby providing a tradeoff between the computation cost and the performance loss in the system. In particular, we study the following two problems
Asymptotic optimality of finite model approximations for partially observed markov decision processes with discounted cost
No full textWe consider finite model approximations of discrete-time partially observed Markov decision processes (POMDPs) under the discounted cost criterion. After converting the original partially observed stochastic control problem to a fully observed one on the belief space, the finite models are obtained through the uniform quantization of the state and action spaces of the belief space Markov decision process (MDP). Under mild assumptions on the components of the original model, it is established that the policies obtained from these finite models are nearly optimal for the belief space MDP, and so, for the original partially observed problem. The assumptions essentially require that the belief space MDP satisfies a mild weak continuity condition. We provide an example and introduce explicit approximation procedures for the quantization of the set of probability measures on the state space of POMDP (i.e., belief space).Natural Sciences and Engineering Research Council of Canada (NSERC
Large deviations principle for discrete-time mean-field games
No full textIn this paper, we establish a large deviations principle (LDP) for interacting particle systems that arise from state and action dynamics of discrete-time mean-field games under the equilibrium policy of the infinite-population limit. The LDP is proved under weak Feller continuity of state and action dynamics. The proof is based on transferring LDP for empirical measures of initial states and noise variables under setwise topology to the original game model via contraction principle, which was first suggested by Delarue, Lacker, and Ramanan to establish LDP for continuous-time mean-field games under common noise. We also compare our work with LDP results established in prior literature for interacting particle systems, which are in a sense uncontrolled versions of mean-field games
Markov-Nash equilibria in mean-field games with discounted cost
No full textIn this paper, we consider discrete-time dynamic games of the mean-field type with a finite number of agents subject to an infinite-horizon discounted-cost optimality criterion. The state space of each agent is a Polish space. At each time, the agents are coupled through the empirical distribution of their states, which affects both the agents' individual costs and their state transition probabilities. We introduce a new solution concept of the Markov--Nash equilibrium, under which a policy is player-by-player optimal in the class of all Markov policies. Under mild assumptions, we demonstrate the existence of a mean-field equilibrium in the infinite-population limit , and then show that the policy obtained from the mean-field equilibrium is approximately Markov--Nash when the number of agents is sufficiently large.Air Force Office of Scientific Research ; Office of Naval ResearchPublisher versio
Regularized stochastic team problems
No full textIn this paper, we introduce regularized stochastic team problems. Under mild assumptions, we prove that there exists a unique fixed point of the best response operator, where this unique fixed point is the optimal regularized team decision rule. Then, we establish an asynchronous distributed algorithm to compute this optimal strategy. We also provide a bound that shows how the optimal regularized team decision rule performs in the original stochastic team problem
- …
