297 results on '"Arapostathis, Ari"'
Search Results
2. Linear and dynamic programs for risk-sensitive cost minimization
- Author
-
Arapostathis, Ari and Borkar, Vivek S.
- Subjects
Mathematics - Optimization and Control - Abstract
We derive equivalent linear and dynamic programs for infinite horizon risk-sensitive control for minimization of the asymptotic growth rate of the cumulative cost., Comment: 6 pages
- Published
- 2021
3. Convex Analytic Method Revisited: Further Optimality Results and Performance of Deterministic Policies in Average Cost Stochastic Control
- Author
-
Arapostathis, Ari and Yüksel, Serdar
- Subjects
Mathematics - Optimization and Control ,90C40, 93E20 - Abstract
The convex analytic method has proved to be a very versatile method for the study of infinite horizon average cost optimal stochastic control problems. In this paper, we revisit the convex analytic method and make three primary contributions: (i) We present an existence result for controlled Markov models that lack weak continuity of the transition kernel but are strongly continuous in the action variable for every fixed state variable. (ii) For average cost stochastic control problems in standard Borel spaces, while existing results establish the optimality of stationary (possibly randomized) policies, few results are available on the optimality of deterministic policies. We review existing results and present further conditions under which an average cost optimal stochastic control problem admits optimal solutions that are deterministic stationary. (iii) We establish conditions under which the performance under stationary deterministic (and also quantized) policies is dense in the set of performance values under randomized stationary policies., Comment: To appear in Journal of Mathematical Analysis and Applications
- Published
- 2021
4. On the monotonicity property of the generalized eigenvalue for weakly-coupled cooperative elliptic systems
- Author
-
Arapostathis, Ari, Biswas, Anup, and Pradhan, Somnath
- Subjects
Mathematics - Analysis of PDEs ,Mathematics - Probability ,Mathematics - Spectral Theory ,93E20, 60J60 - Abstract
We consider general linear non-degenerate weakly-coupled cooperative elliptic systems and study certain monotonicity properties of the generalized principal eigenvalue in $\mathbb{R}^d$ with respect to the potential. It is shown that monotonicity on the right is equivalent to the recurrence property of the twisted operator which is, in turn, equivalent to the minimal growth property at infinity of the principal eigenfunctions. The strict monotonicity property of the principal eigenvalue is shown to be equivalent with the exponential stability of the twisted operators. An equivalence between the monotonicity property on the right and the stochastic representation of the principal eigenfunction is also established., Comment: 29 pages
- Published
- 2020
5. Generalized principal eigenvalues on $\mathbb{R}^d$ of second order elliptic operators with rough nonlocal kernels
- Author
-
Arapostathis, Ari, Biswas, Anup, and Roychowdhury, Prasun
- Subjects
Mathematics - Analysis of PDEs ,Mathematics - Spectral Theory ,35P30, 35B50 - Abstract
We study the generalized eigenvalue problem on the whole space for a class of integro-differential elliptic operators. The nonlocal operator is over a finite measure, but this has no particular structure. Some of our results even hold for singular kernels. The first part of the paper presents results concerning the existence of a principal eigenfunction. Then we present various necessary and/or sufficient conditions for the maximum principle to hold, and use these to characterize the simplicity of the principal eigenvalue., Comment: 23 pages
- Published
- 2020
- Full Text
- View/download PDF
6. On system-wide safety staffing of large-scale parallel server networks
- Author
-
Hmedi, Hassan, Arapostathis, Ari, and Pang, Guodong
- Subjects
Mathematics - Probability ,Electrical Engineering and Systems Science - Systems and Control ,90B22, 60K25, 49L20, 90B36 - Abstract
We introduce a "system-wide safety staffing" (SWSS) parameter for multiclass multi-pool networks of any tree topology, Markovian or non-Markovian, in the Halfin-Whitt regime. This parameter can be regarded as the optimal reallocation of the capacity fluctuations (positive or negative) of order $\sqrt{n}$ when each server pool employs a square-root staffing rule. We provide an explicit form of the SWSS as a function of the system parameters, which is derived using a graph theoretic approach based on Gaussian elimination. For Markovian networks, we give an equivalent characterization of the SWSS parameter via the drift parameters of the limiting diffusion. We show that if the SWSS parameter is negative, the limiting diffusion and the diffusion-scaled queueing processes are transient under any Markov control, and cannot have a stationary distribution when this parameter is zero. If it is positive, we show that the diffusion-scaled queueing processes are uniformly stabilizable, that is, there exists a scheduling policy under which the stationary distributions of the controlled processes are tight over the size of the network. In addition, there exists a control under which the limiting controlled diffusion is exponentially ergodic. Thus we have identified a necessary and sufficient condition for the uniform stabilizability of such networks in the Halfin-Whitt regime. We use a constant control resulting from the leaf elimination algorithm to stabilize the limiting controlled diffusion, while a family of Markov scheduling policies which are easy to compute are used to stabilize the diffusion-scaled processes. Finally, we show that under these controls the processes are exponentially ergodic and the stationary distributions have exponential tails., Comment: 36 pages
- Published
- 2020
7. A variational characterization of the optimal exit rate for controlled diffusions
- Author
-
Arapostathis, Ari and Borkar, Vivek S.
- Subjects
Mathematics - Probability ,Mathematics - Optimization and Control ,60J25, 49G05, 60J60 - Abstract
The main result in this paper is a variational formula for the exit rate from a bounded domain for a diffusion process in terms of the stationary law of the diffusion constrained to remain in this domain forever. Related results on the geometric ergodicity of the controlled Q-process are also presented., Comment: 14 pages
- Published
- 2020
8. Uniform stability of some large-scale parallel server networks
- Author
-
Hmedi, Hassan, Arapostathis, Ari, and Pang, Guodong
- Published
- 2022
- Full Text
- View/download PDF
9. On the relative value iteration with a risk-sensitive criterion
- Author
-
Arapostathis, Ari and Borkar, Vivek S.
- Subjects
Mathematics - Optimization and Control ,Mathematics - Probability ,90C40, 93E20, 49K40 (60J25, 60J60) - Abstract
A multiplicative relative value iteration algorithm for solving the dynamic programming equation for the risk-sensitive control problem is studied for discrete time controlled Markov chains with a compact Polish state space, and controlled diffusions in on the whole Euclidean space. The main result is a proof of convergence to the desired limit in each case., Comment: 14 pages
- Published
- 2019
10. Optimal sensor scheduling under intermittent observations subject to network dynamics
- Author
-
Hmedi, Hassan, Carroll, Johnson, and Arapostathis, Ari
- Subjects
Electrical Engineering and Systems Science - Systems and Control ,Mathematics - Optimization and Control - Abstract
Motivated by various distributed control applications, we consider a linear system with Gaussian noise observed by multiple sensors which transmit measurements over a dynamic lossy network. We characterize the stationary optimal sensor scheduling policy for the finite horizon, discounted, and long-term average cost problems and show that the value iteration algorithm converges to a solution of the average cost problem. We further show that the suboptimal policies provided by the rolling horizon truncation of the value iteration also guarantee stability and provide near-optimal average cost. Lastly, we provide qualitative characterizations of the multidimensional set of measurement loss rates for which the system is stabilizable for a static network, significantly extending earlier results on intermittent observations., Comment: 25 pages
- Published
- 2019
11. On the policy improvement algorithm for ergodic risk-sensitive control
- Author
-
Arapostathis, Ari, Biswas, Anup, and Pradhan, Somnath
- Subjects
Mathematics - Optimization and Control ,Mathematics - Probability ,35P30, 93E20, 60J60 - Abstract
In this article we consider the ergodic risk-sensitive control problem for a large class of multidimensional controlled diffusions on the whole space. We study the minimization and maximization problems under either a blanket stability hypothesis, or a near-monotone assumption on the running cost. We establish the convergence of the policy improvement algorithm for these models. We also present a more general result concerning the region of attraction of the equilibrium of the algorithm., Comment: 20 pages
- Published
- 2019
- Full Text
- View/download PDF
12. Risk-sensitive control for a class of diffusions with jumps
- Author
-
Arapostathis, Ari and Biswas, Anup
- Subjects
Mathematics - Optimization and Control ,Mathematics - Analysis of PDEs ,Mathematics - Probability ,35P30, 60J60 (Primary), 37J25, 35Q93 (Secondary) - Abstract
We consider a class of diffusions controlled through the drift and jump size, and driven by a jump L\'evy process and a nondegenerate Wiener process, and we study infinite horizon (ergodic) risk-sensitive control problem for this model. We start with the controlled Dirichlet eigenvalue problem in smooth bounded domains, which also allows us to generalize current results in the literature on exit rate control problems. Then we consider the infinite horizon average risk-sensitive minimization problem and maximization problems on the whole domain. Under suitable hypotheses, we establish existence and uniqueness of a principal eigenfunction for the Hamilton-Jacobi-Bellman (HJB) operator on the whole space, and fully characterize stationary Markov optimal controls as the measurable selectors of this HJB equation., Comment: 33 pages
- Published
- 2019
13. Exponential ergodicity and steady-state approximations for a class of Markov processes under fast regime switching
- Author
-
Arapostathis, Ari, Pang, Guodong, and Zheng, Yi
- Subjects
Mathematics - Probability ,60K25, 90B20, 90B36, 49L20, 60F17 - Abstract
We study ergodic properties of a class of Markov-modulated general birth-death processes under fast regime switching. The first set of results concerns the ergodic properties of the properly scaled joint Markov process with a parameter that is taken large. Under very weak hypotheses, we show that if the averaged process is exponentially ergodic for large values of the parameter, then the same applies to the original joint Markov process. The second set of results concerns steady-state diffusion approximations, under the assumption that the 'averaged' fluid limit exists. Here, we establish convergence rates for the moments of the approximating diffusion process to those of the Markov modulated birth-death process. This is accomplished by comparing the generator of the approximating diffusion and that of the joint Markov process. We also provide several examples which demonstrate how the theory can be applied., Comment: 23 pages
- Published
- 2019
14. Optimal scheduling of critically loaded multiclass GI/M/n+M queues in an alternating renewal environment
- Author
-
Arapostathis, Ari, Pang, Guodong, and Zheng, Yi
- Subjects
Mathematics - Optimization and Control ,Mathematics - Probability ,Primary: 90B22, 90B36, 60K37. Secondary: 60K25, 60J75, 60F17 - Abstract
In this paper, we study optimal control problems for multiclass GI/M/n+M queues in an alternating renewal (up-down) random environment in the Halfin-Whitt regime. Assuming that the downtimes are asymptotically negligible and only the service processes are affected, we show that the limits of the diffusion-scaled state processes under non-anticipative, preemptive, work-conserving scheduling policies, are controlled jump diffusions driven by a compound Poisson jump process. We establish the asymptotic optimality of the infinite-horizon discounted and long-run average (ergodic) problems for the queueing dynamics. Since the process counting the number of customers in each class is not Markov, the usual martingale arguments for convergence of mean empirical measures cannot be applied. We surmount this obstacle by demonstrating the convergence of the generators of an augmented Markovian model which incorporates the age processes of the renewal interarrival times and downtimes. We also establish long-run average moment bounds of the diffusion-scaled queueing processes under some (modified) priority scheduling policies. This is accomplished via Foster-Lyapunov equations for the augmented Markovian model., Comment: 32 pages
- Published
- 2019
15. Ergodic control of diffusions with compound Poisson jumps under a general structural hypothesis
- Author
-
Arapostathis, Ari, Pang, Guodong, and Zheng, Yi
- Subjects
Mathematics - Optimization and Control ,Mathematics - Probability ,Primary: 93E20, 60J75, 35Q93. Secondary: 60J60, 35F21, 93E15 - Abstract
We study the ergodic control problem for a class of controlled jump diffusions driven by a compound Poisson process. This extends the results of [SIAM J. Control Optim. 57 (2019), no. 2, 1516-1540] to running costs that are not near-monotone. This generality is needed in applications such as optimal scheduling of large-scale parallel server networks. We provide a full characterization of optimality via the Hamilton-Jacobi-Bellman (HJB) equation, for which we additionally exhibit regularity of solutions under mild hypotheses. In addition, we show that optimal stationary Markov controls are a.s. pathwise optimal. Lastly, we show that one can fix a stable control outside a compact set and obtain near-optimal solutions by solving the HJB on a sufficiently large bounded domain. This is useful for constructing asymptotically optimal scheduling policies for multiclass parallel server networks., Comment: 20 pages
- Published
- 2019
- Full Text
- View/download PDF
16. Uniform stability of some large-scale parallel server networks
- Author
-
Hmedi, Hassan, Arapostathis, Ari, and Pang, Guodong
- Subjects
Mathematics - Optimization and Control ,Electrical Engineering and Systems Science - Systems and Control ,Mathematics - Probability ,90B22 (Primary), 60K25, 49L20, 90B36 (Secondary) - Abstract
In this paper we study the uniform stability properties of two classes of parallel server networks with multiple classes of jobs and multiple server pools of a tree topology. These include a class of networks with a single non-leaf server pool, such as the 'N' and 'M' models, and networks of any tree topology with class-dependent service rates. We show that with $\sqrt{n}$ safety staffing, and no abandonment, in the Halfin--Whitt regime, the diffusion-scaled controlled queueing processes are exponentially ergodic and their invariant probability distributions are tight, uniformly over all stationary Markov controls. We use a unified approach in which the same Lyapunov function is used in the study of the prelimit and diffusion limit. A parameter called the spare capacity (safety staffing) of the network plays a central role in characterizing the stability results: the parameter being positive is necessary and sufficient that the limiting diffusion is uniformly exponentially ergodic over all stationary Markov controls. We introduce the concept of "system-wide work conserving policies", which are defined as policies that minimize the number of idle servers at all times. This is stronger than the so-called joint work conservation. We show that, provided the spare capacity parameter is positive, the diffusion-scaled processes are geometrically ergodic and the invariant distributions are tight, uniformly over all "system-wide work conserving policies". In addition, when the spare capacity is negative we show that the diffusion-scaled processes are transient under any stationary Markov control, and when it is zero, they cannot be positive recurrent., Comment: 32 pages
- Published
- 2019
17. Subexponential upper and lower bounds in Wasserstein distance for Markov processes
- Author
-
Arapostathis, Ari, Pang, Guodong, and Sandrić, Nikola
- Subjects
Mathematics - Probability ,60J05, 60J25, 60H10, 60J75 - Abstract
In this article, relying on Foster-Lyapunov drift conditions, we establish subexponential upper and lower bounds on the rate of convergence in the $\mathrm{L}^p$-Wasserstein distance for a class of irreducible and aperiodic Markov processes. We further discuss these results in the context of Markov L\'evy-type processes. In the lack of irreducibility and/or aperiodicity properties, we obtain exponential ergodicity in the $\mathrm{L}^p$-Wasserstein distance for a class of It\^{o} processes under an asymptotic flatness (uniform dissipativity) assumption. Lastly, applications of these results to specific processes are presented, including Langevin tempered diffusion processes, piecewise Ornstein-Uhlenbeck processes with jumps under constant and stationary Markov controls, and backward recurrence time chains, for which we provide a sharp characterization of the rate of convergence via matching upper and lower bounds., Comment: 32 pages
- Published
- 2019
18. On uniqueness of solutions to viscous HJB equations with a subquadratic nonlinearity in the gradient
- Author
-
Arapostathis, Ari, Biswas, Anup, and Caffarelli, Luis
- Subjects
Mathematics - Analysis of PDEs ,Mathematics - Optimization and Control ,35J60, 35P30, 35B40, 35B50 - Abstract
Uniqueness of positive solutions to viscous Hamilton-Jacobi-Bellman (HJB) equations of the form $-\Delta u(x) + \frac{1}{\gamma} |D{u}(x)|^\gamma = f(x) - \lambda$, with $f$ a coercive function and $\lambda$ a constant, in the subquadratic case, that is, $\gamma\in(1,2)$, appears to be an open problem. Barles and Meireles [Comm. Partial Differential Equations 41 (2016)] show uniqueness in the case that $f(x) \approx |x|^\beta$ and $|D f(x)|\lessapprox |x|^{(\beta-1)_+}$ for some $\beta>0$, essentially matching earlier results of Ichihara, who considered more general Hamiltonians but with better regularity for $f$. Without enforcing this assumption, to our knowledge, there are no results on uniqueness in the literature. In this short article, we show that the equation has a unique positive solution for any locally Lipschitz continuous, coercive $f$ which satisfies $|D f(x)| \le \kappa\bigl(1 +|f(x)|^{2-\frac{1}{\gamma}}\bigr)$ for some positive constant $\kappa$. Since $2-\frac{1}{\gamma}>1$, this assumption imposes very mild restrictions on the growth of the potential $f$. We also show that this solution fully characterizes optimality for the associated ergodic problem. Our method involves the study of an infinite dimensional linear program for elliptic equations for measures, and is very different from earlier approaches. It also applies to the larger class of Hamiltonians studied by Ichihara, and we show that it is well suited to provide verification of optimality results for the associated ergodic control problems, even in a pathwise sense, and without resorting to the parabolic problem., Comment: 12 pages
- Published
- 2019
- Full Text
- View/download PDF
19. `Controlled' versions of the Collatz-Wielandt and Donsker-Varadhan formulae
- Author
-
Arapostathis, Ari and Borkar, Vivek S.
- Subjects
Mathematics - Optimization and Control ,60J60, 60J25, 35K59, 35P15, 60F10 - Abstract
This is an overview of the work of the authors and their collaborators on the characterization of risk sensitive costs and rewards in terms of an abstract Collatz-Wielandt formula and in case of rewards, also a controlled version of the Donsker-Varadhan formula. For the finite state and action case, this leads to useful linear and dynamic programming formulations in the reducible case., Comment: 11 pages
- Published
- 2019
20. A variational characterization of the risk-sensitive average reward for controlled diffusions on $\mathbb{R}^d$
- Author
-
Arapostathis, Ari, Biswas, Anup, Borkar, Vivek S., and Kumar, K. Suresh
- Subjects
Mathematics - Analysis of PDEs ,Mathematics - Optimization and Control ,Mathematics - Probability ,Primary 60J60, Secondary 60J25, 35K59, 35P15, 60F10 - Abstract
We address the variational formulation of the risk-sensitive reward problem for non-degenerate diffusions on $\mathbb{R}^d$ controlled through the drift. We establish a variational formula on the whole space and also show that the risk-sensitive value equals the generalized principal eigenvalue of the semilinear operator. This can be viewed as a controlled version of the variational formulas for principal eigenvalues of diffusion operators arising in large deviations. We also revisit the average risk-sensitive minimization problem and by employing a gradient estimate developed in this paper, we extend earlier results to unbounded drifts and running costs., Comment: 29 pages
- Published
- 2019
- Full Text
- View/download PDF
21. Average cost optimal control under weak ergodicity hypotheses: Relative value iterations
- Author
-
Arapostathis, Ari and Borkar, Vivek S.
- Subjects
Mathematics - Optimization and Control ,Electrical Engineering and Systems Science - Systems and Control ,90C40 (93E20) - Abstract
We study Markov decision processes with Polish state and action spaces. The action space is state dependent and is not necessarily compact. We first establish the existence of an optimal ergodic occupation measure using only a near-monotone hypothesis on the running cost. Then we study the well-posedness of Bellman equation, or what is commonly known as the average cost optimality equation, under the additional hypothesis of the existence of a small set. We deviate from the usual approach which is based on the vanishing discount method and instead map the problem to an equivalent one for a controlled split chain. We employ a stochastic representation of the Poisson equation to derive the Bellman equation. Next, under suitable assumptions, we establish convergence results for the 'relative value iteration' algorithm which computes the solution of the Bellman equation recursively. In addition, we present some results concerning the stability and asymptotic optimality of the associated rolling horizon policies., Comment: 32 pages
- Published
- 2019
22. Uniform polynomial rates of convergence for a class of L\'evy-driven controlled SDEs arising in multiclass many-server queues
- Author
-
Arapostathis, Ari, Hmedi, Hassan, Pang, Guodong, and Sandrić, Nikola
- Subjects
Mathematics - Probability ,60J75, 60H10 - Abstract
We study the ergodic properties of a class of controlled stochastic differential equations (SDEs) driven by $\alpha$-stable processes which arise as the limiting equations of multiclass queueing models in the Halfin-Whitt regime that have heavy-tailed arrival processes. When the safety staffing parameter is positive, we show that the SDEs are uniformly ergodic and enjoy a polynomial rate of convergence to the invariant probability measure in total variation, which is uniform over all stationary Markov controls resulting in a locally Lipschitz continuous drift. We also derive a matching lower bound on the rate of convergence (under no abandonment). On the other hand, when all abandonment rates are positive, we show that the SDEs are exponentially ergodic uniformly over the above-mentioned class of controls. Analogous results are obtained for L\'evy-driven SDEs arising from multiclass many-server queues under asymptotically negligible service interruptions. For these equations, we show that the aforementioned ergodic properties are uniform over all stationary Markov controls. We also extend a key functional central limit theorem concerning diffusion approximations so as to make it applicable to the models studied here.
- Published
- 2019
- Full Text
- View/download PDF
23. On the monotonicity property of the generalized eigenvalue for weakly-coupled cooperative elliptic systems
- Author
-
Arapostathis, Ari, Biswas, Anup, and Pradhan, Somnath
- Published
- 2023
- Full Text
- View/download PDF
24. On uniform exponential ergodicity of Markovian multiclass many-server queues in the Halfin-Whitt regime
- Author
-
Arapostathis, Ari, Hmedi, Hassan, and Pang, Guodong
- Subjects
Mathematics - Optimization and Control ,Electrical Engineering and Systems Science - Systems and Control ,Mathematics - Probability ,90B22, 60K25, 90B15 - Abstract
We study ergodic properties of Markovian multiclass many-server queues which are uniform over scheduling policies, as well as the size n of the system. The system is heavily loaded in the Halfin-Whitt regime, and the scheduling policies are work-conserving and preemptive. We provide a unified approach via a Lyapunov function method that establishes Foster-Lyapunov equations for both the limiting diffusion and the prelimit diffusion-scaled queueing processes simultaneously. We first study the limiting controlled diffusion, and we show that if the spare capacity (safety staffing) parameter is positive, then the diffusion is exponentially ergodic uniformly over all stationary Markov controls, and the invariant probability measures have uniform exponential tails. This result is sharp, since when there is no abandonment and the spare capacity parameter is negative, then the controlled diffusion is transient under any Markov control. In addition, we show that if all the abandonment rates are positive, the invariant probability measures have sub-Gaussian tails, regardless whether the spare capacity parameter is positive or negative. Using the above results, we proceed to establish the corresponding ergodic properties for the diffusion-scaled queueing processes. In addition to providing a simpler proof of the results in Gamarnik and Stolyar [Queueing Syst (2012) 71:25-51], we extend these results to the multiclass models with renewal arrival processes, albeit under the assumption that the mean residual life functions are bounded. For the Markovian model with Poisson arrivals, we obtain stronger results and show that the convergence to the stationary distribution is at an exponential rate uniformly over all work-conserving stationary Markov scheduling policies., Comment: 28 pages
- Published
- 2018
25. A variational formula for risk-sensitive control of diffusions in $\mathbb{R}^d$
- Author
-
Arapostathis, Ari and Biswas, Anup
- Subjects
Mathematics - Optimization and Control ,Mathematics - Analysis of PDEs ,Mathematics - Probability ,Primary 60J60, Secondary 60J25, 35P15, 60F10, 49G05 - Abstract
We address the variational problem for the generalized principal eigenvalue on $\mathbb{R}^d$ of linear and semilinear elliptic operators associated with nondegenerate diffusions controlled through the drift. We establish the Collatz-Wielandt formula for potentials that vanish at infinity under minimal hypotheses, and also for general potentials under blanket geometric ergodicity assumptions. We also present associated results having the flavor of a refined maximum principle., Comment: 19 pages
- Published
- 2018
- Full Text
- View/download PDF
26. On the global convergence of relative value iteration for infinite-horizon risk-sensitive control of diffusions
- Author
-
Hmedi, Hassan, Arapostathis, Ari, and Pang, Guodong
- Published
- 2023
- Full Text
- View/download PDF
27. Generalized principal eigenvalues on Rd of second order elliptic operators with rough nonlocal kernels
- Author
-
Arapostathis, Ari, Biswas, Anup, and Roychowdhury, Prasun
- Published
- 2023
- Full Text
- View/download PDF
28. Optimal control of Markov-modulated multiclass many-server queues
- Author
-
Arapostathis, Ari, Das, Anirban, Pang, Guodong, and Zheng, Yi
- Subjects
Mathematics - Probability ,Mathematics - Optimization and Control ,60K25, 68M20, 90B22, 90B36 - Abstract
We study multiclass many-server queues for which the arrival, service and abandonment rates are all modulated by a common finite-state Markov process. We assume that the system operates in the "averaged" Halfin-Whitt regime, which means that it is critically loaded in the average sense, although not necessarily in each state of the Markov process. We show that under any static priority policy, the Markov-modulated diffusion-scaled queueing process is geometrically ergodic. This is accomplished by employing a solution to an associated Poisson equation in order to construct a suitable Lyapunov function. We establish a functional central limit theorem for the diffusion-scaled queueing process and show that the limiting process is a controlled diffusion with piecewise linear drift and constant covariance matrix. We address the infinite-horizon discounted and long-run average (ergodic) optimal control problems and establish asymptotic optimality., Comment: 27 pages
- Published
- 2018
- Full Text
- View/download PDF
29. Augmenting Max-Weight with Explicit Learning for Wireless Scheduling with Switching Costs
- Author
-
Krishnasamy, Subhashini, T, Akhil P, Arapostathis, Ari, Sundaresan, Rajesh, and Shakkottai, Sanjay
- Subjects
Electrical Engineering and Systems Science - Systems and Control - Abstract
In small-cell wireless networks where users are connected to multiple base stations (BSs), it is often advantageous to switch off dynamically a subset of BSs to minimize energy costs. We consider two types of energy cost: (i) the cost of maintaining a BS in the active state, and (ii) the cost of switching a BS from the active state to inactive state. The problem is to operate the network at the lowest possible energy cost (sum of activation and switching costs) subject to queue stability. In this setting, the traditional approach -- a Max-Weight algorithm along with a Lyapunov-based stability argument -- does not suffice to show queue stability, essentially due to the temporal co-evolution between channel scheduling and the BS activation decisions induced by the switching cost. Instead, we develop a learning and BS activation algorithm with slow temporal dynamics, and a Max-Weight based channel scheduler that has fast temporal dynamics. We show using convergence of time-inhomogeneous Markov chains, that the co-evolving dynamics of learning, BS activation and queue lengths lead to near optimal average energy costs along with queue stability., Comment: A shorter version of this paper appeared in the Proceedings of IEEE Conference on Computer Communications (IEEE Infocom 2017)
- Published
- 2018
- Full Text
- View/download PDF
30. A counterexample to a nonlinear version of the Krein-Rutman theorem by R. Mahadevan
- Author
-
Arapostathis, Ari
- Subjects
Mathematics - Functional Analysis ,Primary 47H07, 47H10, 47J10, secondary 47B65 - Abstract
In this short note we present a simple counterexample to a nonlinear version of the Krein-Rutman theorem reported in [Nonlinear Anal. 11 (2007), 3084-3090]. Correct versions of this theorem, and related results for superadditive maps are also presented., Comment: To appear in Nonlinear Analysis, 6 pages
- Published
- 2018
- Full Text
- View/download PDF
31. On Learning the $c\mu$ Rule in Single and Parallel Server Networks
- Author
-
Krishnasamy, Subhashini, Arapostathis, Ari, Johari, Ramesh, and Shakkottai, Sanjay
- Subjects
Computer Science - Performance ,Mathematics - Optimization and Control - Abstract
We consider learning-based variants of the $c \mu$ rule for scheduling in single and parallel server settings of multi-class queueing systems. In the single server setting, the $c \mu$ rule is known to minimize the expected holding-cost (weighted queue-lengths summed over classes and a fixed time horizon). We focus on the problem where the service rates $\mu$ are unknown with the holding-cost regret (regret against the $c \mu$ rule with known $\mu$) as our objective. We show that the greedy algorithm that uses empirically learned service rates results in a constant holding-cost regret (the regret is independent of the time horizon). This free exploration can be explained in the single server setting by the fact that any work-conserving policy obtains the same number of samples in a busy cycle. In the parallel server setting, we show that the $c \mu$ rule may result in unstable queues, even for arrival rates within the capacity region. We then present sufficient conditions for geometric ergodicity under the $c \mu$ rule. Using these results, we propose an almost greedy algorithm that explores only when the number of samples falls below a threshold. We show that this algorithm delivers constant holding-cost regret because a free exploration condition is eventually satisfied.
- Published
- 2018
32. Ergodic control of a class of jump diffusions with finite L\'evy measures and rough kernels
- Author
-
Arapostathis, Ari, Caffarelli, Luis, Pang, Guodong, and Zheng, Yi
- Subjects
Mathematics - Optimization and Control ,Mathematics - Analysis of PDEs ,93E20, 60J75, 35Q93 (Primary), 60J60, 35F21, 93E15 (Secondary) - Abstract
We study the ergodic control problem for a class of jump diffusions in $\mathbb{R}^d$, which are controlled through the drift with bounded controls. The Levy measure is finite, but has no particular structure; it can be anisotropic and singular. Moreover, there is no blanket ergodicity assumption for the controlled process. Unstable behavior is `discouraged' by the running cost which satisfies a mild coercive hypothesis (i.e., is near-monotone). We first study the problem in its weak formulation as an optimization problem on the space of infinitesimal ergodic occupation measures, and derive the Hamilton-Jacobi-Bellman equation under minimal assumptions on the parameters, including verification of optimality results, using only analytical arguments. We also examine the regularity of invariant measures. Then, we address the jump diffusion model, and obtain a complete characterization of optimality., Comment: 21 pages
- Published
- 2018
- Full Text
- View/download PDF
33. On ergodic control problem for viscous Hamilton–Jacobi equations for weakly coupled elliptic systems
- Author
-
Arapostathis, Ari, Biswas, Anup, and Roychowdhury, Prasun
- Published
- 2022
- Full Text
- View/download PDF
34. Certain Liouville properties of eigenfunctions of elliptic operators
- Author
-
Arapostathis, Ari, Biswas, Anup, and Ganguly, Debdip
- Subjects
Mathematics - Functional Analysis ,Mathematics - Analysis of PDEs ,Mathematics - Probability ,35J15 (Primary), 35A02, 35B40, 35B60 (Secondary) - Abstract
We present certain Liouville properties of eigenfunctions of second-order elliptic operators with real coefficients, via an approach that is based on stochastic representations of positive solutions, and criticality theory of second-order elliptic operators. These extend results of Y. Pinchover to the case of nonsymmetric operators of Schr\"odinger type. In particular, we provide an answer to an open problem posed by Pinchover in [Comm. Math. Phys. 272 (2007), no. 1, 75-84, Problem 5]. In addition, we prove a lower bound on the decay of positive supersolutions of general second-order elliptic operators in any dimension, and discuss its implications to the Landis conjecture., Comment: 33 pages
- Published
- 2017
- Full Text
- View/download PDF
35. Ergodicity of L\'evy-driven SDEs arising from multiclass many-server queues
- Author
-
Arapostathis, Ari, Pang, Guodong, and Sandrić, Nikola
- Subjects
Mathematics - Probability ,60J75, 60H10 (Primary), 60G17, 60J25, 60K25 (Secondary) - Abstract
We study the ergodic properties of a class of multidimensional piecewise Ornstein-Uhlenbeck processes with jumps, which contains the limit of the queueing processes arising in multiclass many-server queues with heavy-tailed arrivals and/or asymptotically negligible service interruptions in the Halfin-Whitt regime as special cases. In these queueing models, the It\^o equations have a piecewise linear drift, and are driven by either (1) a Brownian motion and a pure-jump L\'evy process, or (2) an anisotropic L\'evy process with independent one-dimensional symmetric $\alpha$-stable components, or (3) an anisotropic L\'evy process as in (2) and a pure-jump L\'evy process. We also study the class of models driven by a subordinate Brownian motion, which contains an isotropic (or rotationally invariant) $\alpha$-stable L\'evy process as a special case. We identify conditions on the parameters in the drift, the L\'evy measure and/or covariance function which result in subexponential and/or exponential ergodicity. We show that these assumptions are sharp, and we identify some key necessary conditions for the process to be ergodic. In addition, we show that for the queueing models described above with no abandonment, the rate of convergence is polynomial, and we provide a sharp quantitative characterization of the rate via matching upper and lower bounds., Comment: 42 pages
- Published
- 2017
- Full Text
- View/download PDF
36. Infinite horizon asymptotic average optimality for large-scale parallel server networks
- Author
-
Arapostathis, Ari and Pang, Guodong
- Subjects
Mathematics - Optimization and Control ,Computer Science - Systems and Control ,60K25, 68M20, 90B22, 90B36 - Abstract
We study infinite-horizon asymptotic average optimality for parallel server network with multiple classes of jobs and multiple server pools in the Halfin-Whitt regime. Three control formulations are considered: 1) minimizing the queueing and idleness cost, 2) minimizing the queueing cost under a constraints on idleness at each server pool, and 3) fairly allocating the idle servers among different server pools. For the third problem, we consider a class of bounded-queue, bounded-state (BQBS) stable networks, in which any moment of the state is bounded by that of the queue only (for both the limiting diffusion and diffusion-scaled state processes). We show that the optimal values for the diffusion-scaled state processes converge to the corresponding values of the ergodic control problems for the limiting diffusion. We present a family of state-dependent Markov balanced saturation policies (BSPs) that stabilize the controlled diffusion-scaled state processes. It is shown that under these policies, the diffusion-scaled state process is exponentially ergodic, provided that at least one class of jobs has a positive abandonment rate. We also establish useful moment bounds, and study the ergodic properties of the diffusion-scaled state processes, which play a crucial role in proving the asymptotic optimality., Comment: 35 pages. arXiv admin note: text overlap with arXiv:1602.03275
- Published
- 2017
- Full Text
- View/download PDF
37. Strict monotonicity of principal eigenvalues of elliptic operators in $\mathbb{R}^d$ and risk-sensitive control
- Author
-
Arapostathis, Ari, Biswas, Anup, and Saha, Subhamay
- Subjects
Mathematics - Analysis of PDEs ,Mathematics - Optimization and Control ,Mathematics - Probability ,Primary 35P15. Secondary 35B4, 35Q93, 60J60, 93E20 - Abstract
This paper studies the eigenvalue problem on $\mathbb{R}^d$ for a class of second order, elliptic operators of the form $\mathscr{L} = a^{ij}\partial_{x_i}\partial_{x_j} + b^{i}\partial_{x_i} + f$, associated with non-degenerate diffusions. We show that strict monotonicity of the principal eigenvalue of the operator with respect to the potential function $f$ fully characterizes the ergodic properties of the associated ground state diffusion, and the unicity of the ground state, and we present a comprehensive study of the eigenvalue problem from this point of view. This allows us to extend or strengthen various results in the literature for a class of viscous Hamilton-Jacobi equations of ergodic type with smooth coefficients to equations with measurable drift and potential. In addition, we establish the strong duality for the equivalent infinite dimensional linear programming formulation of these ergodic control problems. We also apply these results to the study of the infinite horizon risk-sensitive control problem for diffusions, and establish existence of optimal Markov controls, verification of optimality results, and the continuity of the controlled principal eigenvalue with respect to stationary Markov controls., Comment: 45 pages
- Published
- 2017
- Full Text
- View/download PDF
38. Optimal Scheduling of Critically Loaded Multiclass GI/M/n+M Queues in an Alternating Renewal Environment
- Author
-
Arapostathis, Ari, Pang, Guodong, and Zheng, Yi
- Published
- 2021
- Full Text
- View/download PDF
39. Subexponential Upper and Lower Bounds in Wasserstein Distance for Markov Processes
- Author
-
Sandrić, Nikola, Arapostathis, Ari, and Pang, Guodong
- Published
- 2022
- Full Text
- View/download PDF
40. Some new results on sample path optimality in ergodic control of diffusions
- Author
-
Arapostathis, Ari
- Subjects
Mathematics - Optimization and Control ,Mathematics - Probability - Abstract
We present some new results on sample path optimality for the ergodic control problem of a class of non-degenerate diffusions controlled through the drift. The hypothesis most often used in the literature to ensure the existence of an a.s. sample path optimal stationary Markov control requires finite second moments of the first hitting times $\tau$ of bounded domains over all admissible controls. We show that this can be considerably weakened: ${\mathrm E}[\tau^2]$ may be replaced with ${\mathrm E}[\tau\ln^+(\tau)]$, thus reducing the required rate of convergence of averages from polynomial to logarithmic. A Foster-Lyapunov condition which guarantees this is also exhibited. Moreover, we study a large class of models that are neither uniformly stable, nor have a near-monotone running cost, and we exhibit sufficient conditions for the existence of a sample path optimal stationary Markov control., Comment: 10 pages
- Published
- 2016
- Full Text
- View/download PDF
41. Infinite Horizon Average Optimality of the N-network Queueing Model in the Halfin-Whitt Regime
- Author
-
Arapostathis, Ari and Pang, Guodong
- Subjects
Mathematics - Optimization and Control ,Computer Science - Systems and Control ,Mathematics - Probability ,60K25, 68M20, 90B22, 90B36 - Abstract
We study the infinite horizon optimal control problem for N-network queueing systems, which consist of two customer classes and two server pools, under average (ergodic) criteria in the Halfin-Whitt regime. We consider three control objectives: 1) minimizing the queueing (and idleness) cost, 2) minimizing the queueing cost while imposing a constraint on idleness at each server pool, and 3) minimizing the queueing cost while requiring fairness on idleness. The running costs can be any nonnegative convex functions having at most polynomial growth. For all three problems we establish asymptotic optimality, namely, the convergence of the value functions of the diffusion-scaled state process to the corresponding values of the controlled diffusion limit. We also present a simple state-dependent priority scheduling policy under which the diffusion-scaled state process is geometrically ergodic in the Halfin-Whitt regime, and some results on convergence of mean empirical measures which facilitate the proofs., Comment: 35 pages
- Published
- 2016
- Full Text
- View/download PDF
42. Infinite horizon risk-sensitive control of diffusions without any blanket stability assumptions
- Author
-
Arapostathis, Ari and Biswas, Anup
- Subjects
Mathematics - Optimization and Control ,Mathematics - Analysis of PDEs ,Mathematics - Probability ,35R60, 93E20 - Abstract
We consider the infinite horizon risk-sensitive problem for nondegenerate diffusions with a compact action space, and controlled through the drift. We only impose a structural assumption on the running cost function, namely near-monotonicity, and show that there always exists a solution to the risk-sensitive Hamilton-Jacobi-Bellman (HJB) equation, and that any minimizer in the Hamiltonian is optimal in the class of stationary Markov controls. Under the additional hypothesis that the coefficients of the diffusion are bounded, and satisfy a condition that limits (even though it still allows) transient behavior, we show that any minimizer in the Hamiltonian is optimal in the class of all admissible controls. In addition, we present a sufficient condition, under which the solution of the HJB is unique (up to a multiplicative constant), and establish the usual verification result. We also present some new results concerning the multiplicative Poisson equation for elliptic operators in $\mathbb{R}^d$., Comment: 37 pages
- Published
- 2016
- Full Text
- View/download PDF
43. On Solutions of Mean Field Games with Ergodic Cost
- Author
-
Arapostathis, Ari, Biswas, Anup, and Carroll, Johnson
- Subjects
Mathematics - Optimization and Control ,Mathematics - Probability ,Primary: 91A13, 93E20, Secondary: 82B05 - Abstract
A general class of mean field games are considered where the governing dynamics are controlled diffusions in $\mathbb{R}^d$. The optimization criterion is the long time average of a running cost function. Under various sets of hypotheses, we establish the existence of mean field game solutions. We also study the long time behavior of mean field game solutions associated with the finite horizon problem, and under the assumption of geometric ergodicity for the dynamics, we show that these converge to the ergodic mean field game solution as the horizon tends to infinity. Lastly, we study the associated $N$-player games, show existence of Nash equilibria, and establish the convergence of the solutions associated to Nash equilibria of the game to a mean field game solution as $N\to\infty$., Comment: 40 pages
- Published
- 2015
- Full Text
- View/download PDF
44. Ergodic Diffusion Control of Multiclass Multi-Pool Networks in the Halfin-Whitt Regime
- Author
-
Arapostathis, Ari and Pang, Guodong
- Subjects
Mathematics - Probability ,Computer Science - Systems and Control ,Mathematics - Optimization and Control ,60K25, 68M20, 90B22, 90B36 - Abstract
We consider Markovian multiclass multi-pool networks with heterogeneous server pools, each consisting of many statistically identical parallel servers, where the bipartite graph of customer classes and server pools forms a tree. Customers form their own queue and are served in the first-come first-served discipline, and can abandon while waiting in queue. Service rates are both class and pool dependent. The objective is to study the limiting diffusion control problems under the long run average (ergodic) cost criteria in the Halfin--Whitt regime. Two formulations of ergodic diffusion control problems are considered: (i) both queueing and idleness costs are minimized, and (ii) only the queueing cost is minimized while a constraint is imposed upon the idleness of all server pools. We develop a recursive leaf elimination algorithm that enables us to obtain an explicit representation of the drift for the controlled diffusions. Consequently, we show that for the limiting controlled diffusions, there always exists a stationary Markov control under which the diffusion process is geometrically ergodic. The framework developed in our earlier work is extended to address a broad class of ergodic diffusion control problems with constraints. We show that that the unconstrained and constrained problems are well posed, and we characterize the optimal stationary Markov controls via HJB equations., Comment: 32 pages
- Published
- 2015
- Full Text
- View/download PDF
45. Controlled equilibrium selection in stochastically perturbed dynamics
- Author
-
Arapostathis, Ari, Biswas, Anup, and Borkar, Vivek S.
- Subjects
Mathematics - Probability ,Mathematics - Dynamical Systems ,Mathematics - Optimization and Control ,35R60, 93E20 - Abstract
We consider a dynamical system with finitely many equilibria and perturbed by small noise, in addition to being controlled by an `expensive' control. The controlled process is optimal for an ergodic criterion with a running cost that consists the sum of the control effort and a penalty function on the state space. We study the optimal stationary distribution of the controlled process as the variance of the noise becomes vanishingly small. It is shown that depending on the relative magnitudes of the noise variance and the `running cost' for control, one can identify three regimes, in each of which the optimal control forces the invariant distribution of the process to concentrate near equilibria that can be characterized according to the regime. We also obtain moment bounds for the optimal stationary distribution. Moreover, we show that in the vicinity of the points of concentration the density of optimal stationary distribution approximates the density of a Gaussian, and we explicitly solve for its covariance matrix., Comment: 51 pages
- Published
- 2015
- Full Text
- View/download PDF
46. Ergodic control of diffusions with compound Poisson jumps under a general structural hypothesis
- Author
-
Arapostathis, Ari, Pang, Guodong, and Zheng, Yi
- Published
- 2020
- Full Text
- View/download PDF
47. Ergodic control of multi-class $M/M/N+M$ queues in the Halfin-Whitt regime
- Author
-
Arapostathis, Ari, Biswas, Anup, and Pang, Guodong
- Subjects
Mathematics - Probability ,Computer Science - Systems and Control ,Mathematics - Optimization and Control - Abstract
We study a dynamic scheduling problem for a multi-class queueing network with a large pool of statistically identical servers. The arrival processes are Poisson, and service times and patience times are assumed to be exponentially distributed and class dependent. The optimization criterion is the expected long time average (ergodic) of a general (nonlinear) running cost function of the queue lengths. We consider this control problem in the Halfin-Whitt (QED) regime, that is, the number of servers $n$ and the total offered load $\mathbf{r}$ scale like $n\approx\mathbf{r}+\hat{\rho}\sqrt{\mathbf{r}}$ for some constant $\hat{\rho}$. This problem was proposed in [Ann. Appl. Probab. 14 (2004) 1084-1134, Section 5.2]. The optimal solution of this control problem can be approximated by that of the corresponding ergodic diffusion control problem in the limit. We introduce a broad class of ergodic control problems for controlled diffusions, which includes a large class of queueing models in the diffusion approximation, and establish a complete characterization of optimality via the study of the associated HJB equation. We also prove the asymptotic convergence of the values for the multi-class queueing control problem to the value of the associated ergodic diffusion control problem. The proof relies on an approximation method by spatial truncation for the ergodic control of diffusion processes, where the Markov policies follow a fixed priority policy outside a fixed compact set., Comment: Published at http://dx.doi.org/10.1214/14-AAP1081 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)
- Published
- 2014
- Full Text
- View/download PDF
48. On a Class of Stochastic Differential Equations With Jumps and Its Properties
- Author
-
Arapostathis, Ari, Biswas, Anup, and Caffarelli, Luis
- Subjects
Mathematics - Probability ,60J45, 60J75, 58F11 - Abstract
We study stochastic differential equations with jumps with no diffusion part. We provide some basic stochastic characterizations of solutions of the corresponding non-local partial differential equations and prove the Harnack inequality for a class of these operators. We also establish key connections between the recurrence properties of these jump processes and the non-local partial differential operator. One of the key results is the regularity of solutions of the Dirichlet problem for a class of operators with locally weakly H\"older continuous kernels., Comment: 40 pages
- Published
- 2014
49. ERGODICITY OF A LÉVY-DRIVEN SDE ARISING FROM MULTICLASS MANY-SERVER QUEUES
- Author
-
Arapostathis, Ari, Pang, Guodong, and Sandrić, Nikola
- Published
- 2019
50. Risk-Sensitive Control and an Abstract Collatz-Wielandt Formula
- Author
-
Arapostathis, Ari, Borkar, Vivek S., and Kumar, K. Suresh
- Subjects
Mathematics - Optimization and Control ,Primary 60J60, Secondary 60F10, 93E20 - Abstract
The "value" of infinite horizon risk-sensitive control is the principal eigenvalue of a certain positive operator. This facilitates the use of Chang's extension of the Collatz-Wielandt formula to derive a variational characterization thereof. For the uncontrolled case, this reduces to the Donsker-Varadhan functional.
- Published
- 2013
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.