Browsing by Author "Yüksel, S."

Now showing 1 - 12 of 12

Metadata only
Approximations for constrained Markov decision problems
(Springer, 2018) Saldı, Naci; Linder, T.; Yüksel, S.; Natural and Mathematical Sciences; SALDI, Naci
This chapter studies the finite-state approximation of a discrete-time constrained Markov decision process with compact state space, under the discounted and average cost criteria. Using the linear programming formulation of the constrained discounted problem, we prove the convergence of the optimal value function of the finite-state model to the optimal value function of the original model. Under further continuity conditions on the transition probability of the original discounted model, we also establish a method to compute approximately optimal policies. For the average cost criterion, instead of using the finite-state linear programming approximation method, we use a direct method to establish analogous results under drift and minorization conditions which guarantee the geometric ergodicity of Markov chains induced by stationary policies.
Metadata only
Approximations for partially observed Markov decision processes
(Birkhäuser Basel, 2018) Saldı, Naci; Linder, T.; Yüksel, S.; Natural and Mathematical Sciences; SALDI, Naci
This chapter studies the finite-model approximation of discrete-time partially observed Markov decision process. We will find that by performing the standard reduction method, where one transforms a partially observed model to a belief-based fully observed model, we can apply and properly generalize the results in the preceding chapters to obtain approximation results. The versatility of approximation results under weak continuity conditions become particularly evident while investigating the applicability of these results to the partially observed case. We also provide systematic procedures for the quantization of the set of probability measures on the state space of POMDPs which is the state space of belief-MDPs.
Metadata only
Asymptotic optimality of finite models for witsenhausen’s counterexample and beyond
(Birkhäuser Basel, 2018) Saldı, Naci; Linder, T.; Yüksel, S.; Natural and Mathematical Sciences; SALDI, Naci
In this chapter, we study the approximation of Witsenhausen’s counterexample and the Gaussian relay channel problem by using the results of the previous chapter. In particular, our goal is to establish that finite models obtained through the uniform quantization of the observation and action spaces result in a sequence of policies whose costs converge to the value function. We note that the operation of quantization has typically been the method to show that a non-linear policy can perform better than an optimal linear policy, both for Witsenhausen’s counterexample [10, 86] and the Gaussian relay channel problem [88, 152]. Our findings show that for a large class of problems, quantized policies not only may perform better than linear policies, but that they are actually almost optimal.
Metadata only
Finite approximations in discrete-time stochastic control : quantized models and asymptotic optimality
(Birkhäuser Basel, 2018) Saldı, Naci; Linder, T.; Yüksel, S.; Natural and Mathematical Sciences; SALDI, Naci
In 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.
Metadata only
Finite approximations in discrete-time stochastic control quantized models and asymptotic optimality introduction and summary
(Birkhäuser Basel, 2018) Saldı, Naci; Linder, T.; Yüksel, S.; Natural and Mathematical Sciences; SALDI, Naci
Control and optimization of dynamical systems in the presence of stochastic uncertainty is a mature field with a large range of applications. A comprehensive treatment of such problems can be found in excellent books and other resources including [7, 16, 29, 68, 84, 95, 104], and [6]. To date, there exist a nearly complete theory regarding the existence and structure of optimal solutions under various formulations as well as computational methods to obtain such optimal solutions for problems with finite state and control spaces. However, there still exist substantial computational challenges involving problems with large state and action spaces, such as standard Borel spaces. For such state and action spaces, obtaining optimal policies is in general computationally infeasible.
Metadata only
Finite model approximations in decentralized stochastic control
(Birkhäuser Basel, 2018) Saldı, Naci; Linder, T.; Yüksel, S.; Natural and Mathematical Sciences; SALDI, Naci
In this chapter, we study the approximation of static and dynamic team problems using finite models which are obtained through the uniform discretization, on a finite grid, of the observation and action spaces of agents. In particular, we are interested in the asymptotic optimality of quantized policies.
Metadata only
Finite-action approximation of Markov decision processes
(Birkhäuser Basel, 2018) Saldı, Naci; Linder, T.; Yüksel, S.; Natural and Mathematical Sciences; SALDI, Naci
In this chapter, we study the finite-action approximation of optimal control policies for discrete-time Markov decision processes (MDPs) with Borel state and action spaces, under discounted and average cost criteria. One main motivation for considering this problem stems from the optimal information transmission problem in networked control systems. In many applications of networked control, perfect transmission of the control actions to an actuator is infeasible when there is a communication channel of finite capacity between a controller and an actuator. Hence, the actions of the controller must be discretized (quantized) to facilitate reliable transmission. Although the problem of optimal information transmission from a plant/sensor to a controller has been studied extensively (see, e.g., [148] and references therein), much less is known about the problem of transmitting actions from a controller to an actuator. Such transmission schemes usually require a simple encoding/decoding rule since the actuator does not have the computational capability of the controller to use complex algorithms. For this reason, time-invariant scalar quantization is a practically useful encoding method for controller-actuator communication.
Metadata only
Finite-state approximation of Markov decision processes
(Springer, 2018) Saldı, Naci; Linder, T.; Yüksel, S.; Natural and Mathematical Sciences; SALDI, Naci
In 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.
Metadata only
Independently randomized symmetric policies are optimal for exchangeable stochastic teams with infinitely many decision makers
(IEEE, 2020-12-14) Sanjari, S.; Saldı, Naci; Yüksel, S.; Natural and Mathematical Sciences; SALDI, Naci
We study stochastic team (known also as decentralized stochastic control or identical interest stochastic game) problems with large or countably infinite number of decision makers, and characterize existence and structural properties for (globally) optimal policies. We consider in particular both static and dynamic non-convex team problems where the cost function and dynamics satisfy an exchangeability condition. We first establish a de Finetti type representation theorem for exchangeable decentralized policies, that is, for the probability measures induced by admissible policies under decentralized information structures. For a general setup of stochastic team problems with N decision makers, under exchangeability of observations of decision makers and the cost function, we show that without loss of global optimality, the search for optimal policies over any convex set of probability measures on policies can be restricted to those that are N-exchangeable. Then, by extending N-exchangeable policies to infinitely exchangeable ones, establishing a convergence argument for the induced costs, and using the presented de Finetti type theorem, we establish the existence of an optimal decentralized policy for static and dynamic teams with countably infinite number of decision makers, which turns out to be symmetric (i.e., identical) and randomized. In particular, unlike prior work, convexity of the cost is not assumed.
Metadata only
Prelude to part I
(Springer, 2018) Saldı, Naci; Linder, T.; Yüksel, S.; Natural and Mathematical Sciences; SALDI, Naci
Part I involves classical stochastic control problems, with a single decision maker acting repeatedly over time with its information set growing at each time stage.
Metadata only
Prelude to part II
(Springer, 2018) Saldı, Naci; Linder, T.; Yüksel, S.; Natural and Mathematical Sciences; SALDI, Naci
In Part II, we focus on decentralized stochastic control problems and their applications. In Chapter 8, we present our results on the finite model approximation of multi-agent stochastic control problems (team decision problems). We show that optimal strategies obtained from finite models approximate the optimal cost with arbitrary precision under mild technical assumptions. In particular, we show that quantized team policies are asymptotically optimal. In Chapter 9, the results are applied to Witsenhausen’s counterexample and the Gaussian relay channel problem.
Metadata only
Weak Feller property of non-linear filters
(Elsevier, 2019-12) Kara, A. D.; Saldı, Naci; Yüksel, S.; Natural and Mathematical Sciences; SALDI, Naci
Weak 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. Establishing sufficient conditions for the weak Feller property for such processes is a significant problem, studied under various assumptions and setups in the literature. 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.