BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Naci Saldi

Naci Saldi appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.OCSystems and Controleess.SYInformation Theorymath.ITComputer Science and Game Theory

Catalog footprint

What is connected

10works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

10 published item(s)

preprint2023arXiv

Linear Mean-Field Games with Discounted Cost

In this paper, we introduce discrete-time linear mean-field games subject to an infinite-horizon discounted-cost optimality criterion. The state space of a generic agent is a compact Borel space. At every time, each agent is randomly coupled with another agent via their dynamics and one-stage cost function, where this randomization is generated via the empirical distribution of their states (i.e., the mean-field term). Therefore, the transition probability and the one-stage cost function of each agent depend linearly on the mean-field term, which is the key distinction between classical mean-field games and linear mean-field games. Under mild assumptions, we show that the policy obtained from infinite population equilibrium is $\varepsilon(N)$-Nash when the number of agents $N$ is sufficiently large, where $\varepsilon(N)$ is an explicit function of $N$. Then, using the linear programming formulation of MDPs and the linearity of the transition probability in mean-field term, we formulate the game in the infinite population limit as a generalized Nash equilibrium problem (GNEP) and establish an algorithm for computing equilibrium with a convergence guarantee.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Non-signaling Approximations of Stochastic Team Problems

In this paper, we consider non-signaling approximation of finite stochastic teams. We first introduce a hierarchy of team decision rules that can be classified in an increasing order as randomized policies, quantum-correlated policies, and non-signaling policies. Then, we establish an approximation of team-optimal policies for sequential teams via extendible non-signaling policies. We prove that the distance between extendible non-signaling policies and decentralized policies is small if the extension is sufficiently large. Using this result, we establish a linear programming (LP) approximation of sequential teams. Finally, we state an open problem regarding computation of optimal value of quantum-correlated policies.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Value Iteration Algorithm for Mean-field Games

In 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 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 mean-field equilibrium. In our value iteration algorithm, we use $Q$-functions instead of value functions.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Asymptotic Optimality of Finite Approximations to Markov Decision Processes with Borel Spaces

Calculating optimal policies is known to be computationally difficult for Markov decision processes (MDPs) with Borel state and action spaces. This paper studies finite-state approximations of discrete time Markov decision processes with Borel state and action spaces, for both discounted and average costs criteria. The stationary policies thus obtained are shown to approximate the optimal stationary policy with arbitrary precision under quite general conditions for discounted cost and more restrictive conditions for average cost. For compact-state MDPs, we obtain explicit rate of convergence bounds quantifying how the approximation improves as the size of the approximating finite state space increases. Using information theoretic arguments, the order optimality of the obtained convergence rates is established for a large class of problems. We also show that, as a pre-processing step the action space can also be finitely approximated with sufficiently large number points; thereby, well known algorithms, such as value or policy iteration, Q-learning, etc., can be used to calculate near optimal policies.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Convex Analysis in Decentralized Stochastic Control, Strategic Measures and Optimal Solutions

This paper is concerned with the properties of the sets of strategic measures induced by admissible team policies in decentralized stochastic control and the convexity properties in dynamic team problems. To facilitate a convex analytical approach, strategic measures for team problems are introduced. Properties such as convexity, and compactness and Borel measurability under weak convergence topology are studied, and sufficient conditions for each of these properties are presented. These lead to existence of and structural results for optimal policies. It will be shown that the set of strategic measures for teams which are not classical is in general non-convex, but the extreme points of a relaxed set consist of deterministic team policies, which lead to their optimality for a given team problem under an expected cost criterion. Externally provided independent common randomness for static teams or private randomness for dynamic teams do not improve the team performance. The problem of when a sequential team problem is convex is studied and necessary and sufficient conditions for problems which include teams with a non-classical information structure are presented. Implications of this analysis in identifying probability and information structure dependent convexity properties are presented.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Finite Model Approximations and Asymptotic Optimality of Quantized Policies in Decentralized Stochastic Control

In this paper, we consider finite model approximations of a large class of static and dynamic team problems where these models are constructed through uniform quantization of the observation and action spaces of the agents. The strategies obtained from these finite models are shown to approximate the optimal cost with arbitrary precision under mild technical assumptions. In particular, quantized team policies are asymptotically optimal. This result is then applied to Witsenhausen's celebrated counterexample and the Gaussian relay channel problem. For the Witsenhausen's counterexample, our approximation approach provides, to our knowledge, the first rigorously established result that one can construct an $\varepsilon$-optimal strategy for any $\varepsilon > 0$ through a solution of a simpler problem.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Near Optimality of Quantized Policies in Stochastic Control Under Weak Continuity Conditions

This paper studies the approximation of optimal control policies by quantized (discretized) policies for a very general class of Markov decision processes (MDPs). The problem is motivated by applications in networked control systems, computational methods for MDPs, and learning algorithms for MDPs. We consider the finite-action approximation of stationary policies for a discrete-time Markov decision process with discounted and average costs under a weak continuity assumption on the transition probability, which is a significant relaxation of conditions required in earlier literature. The discretization is constructive, and quantized policies are shown to approximate optimal deterministic stationary policies with arbitrary precision. The results are applied to the fully observed reduction of a partially observed Markov decision process, where weak continuity is a much more reasonable assumption than more stringent conditions such as strong continuity or continuity in total variation.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Output Constrained Lossy Source Coding with Limited Common Randomness

This paper studies a Shannon-theoretic version of the generalized distribution preserving quantization problem where a stationary and memoryless source is encoded subject to a distortion constraint and the additional requirement that the reproduction also be stationary and memoryless with a given distribution. The encoder and decoder are stochastic and assumed to have access to independent common randomness. Recent work has characterized the minimum achievable coding rate at a given distortion level when unlimited common randomness is available. Here we consider the general case where the available common randomness may be rate limited. Our main result completely characterizes the set of achievable coding and common randomness rate pairs at any distortion level, thereby providing the optimal tradeoff between these two rate quantities. We also consider two variations of this problem where we investigate the effect of relaxing the strict output distribution constraint and the role of `private randomness' used by the decoder on the rate region. Our results have strong connections with Cuff's recent work on distributed channel synthesis. In particular, our achievability proof combines a coupling argument with the approach developed by Cuff, where instead of explicitly constructing the encoder-decoder pair, a joint distribution is constructed from which a desired encoder-decoder pair is established. We show however that for our problem, the separated solution of first finding an optimal channel and then synthesizing this channel results in a suboptimal rate region.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Quantized Stationary Control Policies in Markov Decision Processes

For a large class of Markov Decision Processes, stationary (possibly randomized) policies are globally optimal. However, in Borel state and action spaces, the computation and implementation of even such stationary policies are known to be prohibitive. In addition, networked control applications require remote controllers to transmit action commands to an actuator with low information rate. These two problems motivate the study of approximating optimal policies by quantized (discretized) policies. To this end, we introduce deterministic stationary quantizer policies and show that such policies can approximate optimal deterministic stationary policies with arbitrary precision under mild technical conditions, thus demonstrating that one can search for $\varepsilon$-optimal policies within the class of quantized control policies. We also derive explicit bounds on the approximation error in terms of the rate of the approximating quantizers. We extend all these approximation results to randomized policies. These findings pave the way toward applications in optimal design of networked control systems where controller actions need to be quantized, as well as for new computational methods for generating approximately optimal decision policies in general (Polish) state and action spaces for both discounted cost and average cost.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Randomized Quantization and Source Coding with Constrained Output Distribution

This paper studies fixed-rate randomized vector quantization under the constraint that the quantizer's output has a given fixed probability distribution. A general representation of randomized quantizers that includes the common models in the literature is introduced via appropriate mixtures of joint probability measures on the product of the source and reproduction alphabets. Using this representation and results from optimal transport theory, the existence of an optimal (minimum distortion) randomized quantizer having a given output distribution is shown under various conditions. For sources with densities and the mean square distortion measure, it is shown that this optimum can be attained by randomizing quantizers having convex codecells. For stationary and memoryless source and output distributions a rate-distortion theorem is proved, providing a single-letter expression for the optimum distortion in the limit of large block-lengths.

0 citations0 reviewsNo code linkedOpen access