1,354,077 research outputs found
A Lyapunov-based version of the value iteration algorithm formulated as a discrete-time switched affine system
No full textIn this paper, we analyse the convergence properties of the Dynamic Programming Value Iteration algorithm by exploiting the stability theory of discrete-time switched affine systems. More specifically, by formulating the Value Iteration algorithm as a switched affine system, a Lyapunov-based optimal policy selection strategy is designed to guarantee the practical stabilisation of the resulting system towards an invariant set of attraction containing a given target value function. The switching control algorithm, referred to as Lyapunov-based Value Iteration algorithm, can be regarded as a convergence analysis tool and can be adopted to verify if and how such target value function can be approached by choosing from a subset of suitable stationary policies, at each time slot. The usage of the proposed algorithm in practice is also discussed. Finally, two different applications are provided to further illustrate and examine the key-aspects of the approach presented
Applying unweighted least-squares based techniques to stochastic dynamic programming: Theory and application
No full textBig data and the curse of dimensionality are common vocabularies that researchers in different communities have recently been dealing with, e.g. dynamic programming (DP) in automatic control system society. A novel unweighted sampled based least square projection approach is proposed in this study to address the issue of the large state space in the DP optimisation problem. The method, in particular, takes into account both contraction mapping and monotonicity properties of the DP algorithm for value function approximation. Specifically, the batch of samples are gathered by uniform probability distribution at first, and an unweighted LS sub-problem in the subspace is solved. As the case study, a new Markov decision process model associated with a resource allocation problem is considered to illustrate the technique and evaluate its effectiveness. It is noted that the approach can be employed for different applications as well. Moreover, a MATLAB based software is developed to implement and examine different parts of the proposed method. Simulation examples are considered to support the results of the approach via developed software. The idea makes a connection between the recent advances in big data analysis and approximate DP as well
Stochastic dynamic programming solution to transmission scheduling: Multi sensor-multi process with wireless noisy channel
No full textWe investigate sensor scheduling for remote estimation when multiple smart sensors monitor multiple stochastic dynamical systems. The sensors transmit their measurements to a remote estimator through a noisy wireless communication channel. Such a remote estimator can receive multiple packets simultaneously sent by local sensors. Sensors transmit their measurements if their Signal Interference and Noise Ratio (SINR) is above a threshold. We compute the optimal policy for sensor scheduling by minimizing expected error covariance subject to total signal transmissions from all sensors. We model this problem as Markov Decision Process (MDP) with discounted cost per stage in the finite time horizon framework, then we employ stochastic Dynamic Programming as the optimization method. A novel algorithm based on sampling and machine learning techniques is proposed as the approximation. At each phase of the DP algorithm, samples are collected using a uniform probability distribution. The data is used to feed Neural Network (NN) and Random Forest (RF) models for cost function and policy approximation. The results of the proposed framework are supported by simulation examples comparing RF and NN as Approximate DP (ADP). Note that this idea builds a bridge among the recent advances in the area of data science, Machine Learning, and the ADP
A kernel-based approximate dynamic programming approach: Theory and application
Get PDFThis article proposes a novel kernel-based Dynamic Programming (DP) approximation method to tackle the typical curse of dimensionality of stochastic DP problems over the finite time horizon. Such a method utilizes kernel functions in combination with Support Vector Machine (SVM) regression to determine an approximate cost function for the entire state space of the underlying Markov Decision Process (MDP), by leveraging cost function computed for selected representative states. Kernel functions are used to define the so-called kernel matrix, while the parameter vector of the given kernel-based cost function approximation is computed by moving backwards in time from the terminal condition and by applying SVM regression. This way, the difficulty of selecting a proper set of features is also tackled. The proposed method is then extended to the infinite time horizon case. To show the effectiveness of the proposed approach, the resulting Recursive Residual Approximate Dynamic Programming (RR-ADP) algorithm is applied to the sensor scheduling design in multi-process remote state estimation problems
Allocating resources via price management systems: a dynamic programming-based approach
No full textIn this paper, a novel model for price management systems in resource allocation problems is proposed. Stochastic customer requests for resource allocations and releases are modelled as constrained parallel Birth–Death Processes (BDP). We address both instant (i.e. the customer requires a resource to be allocated immediately) and advance (i.e. the customer books a resource for future use) reservation requests, the latter with both bounded and unbounded time interval options. Algorithms based on Dynamic Programming (DP) principles are proposed for the calculation of suitable price profiles. At the core of such algorithms, there is the resolution of stochastic optimisation problems. In particular, the maximisation of the expected total revenue is formulated via a constrained Stochastic Dynamic Programming (SDP) approach, which becomes time-variant in case of advance reservation requests. Approximate Dynamic Programming (ADP) techniques are adopted in case of large state spaces. Simulations are performed to show the effectiveness of the proposed models and the related algorithms
Approximate dynamic programming for stochastic resource allocation problems
No full textA stochastic resource allocation model, based on the principles of Markov decision processes (MDPs), is proposed in this paper. In particular, a general-purpose framework is developed, which takes into account resource requests for both instant and future needs. The considered framework can handle two types of reservations (i.e., specified and unspecified time interval reservation requests), and implement an overbooking business strategy to further increase business revenues. The resulting dynamic pricing problems can be regarded as sequential decision-making problems under uncertainty, which is solved by means of stochastic dynamic programming (DP) based algorithms. In this regard, Bellman's backward principle of optimality is exploited in order to provide all the implementation mechanisms for the proposed reservation pricing algorithm. The curse of dimensionality, as the inevitable issue of the DP both for instant resource requests and future resource reservations, occurs. In particular, an approximate dynamic programming (ADP) technique based on linear function approximations is applied to solve such scalability issues. Several examples are provided to show the effectiveness of the proposed approach
Allocating resources via price management systems: a dynamic programming-based approach
No full textIn this paper, a novel model for price management systems in resource allocation problems is proposed. Stochastic customer requests for resource allocations and releases are modelled as constrained parallel Birth–Death Processes (BDP). We address both instant (i.e. the customer requires a resource to be allocated immediately) and advance (i.e. the customer books a resource for future use) reservation requests, the latter with both bounded and unbounded time interval options. Algorithms based on Dynamic Programming (DP) principles are proposed for the calculation of suitable price profiles. At the core of such algorithms, there is the resolution of stochastic optimisation problems. In particular, the maximisation of the expected total revenue is formulated via a constrained Stochastic Dynamic Programming (SDP) approach, which becomes time-variant in case of advance reservation requests. Approximate Dynamic Programming (ADP) techniques are adopted in case of large state spaces. Simulations are performed to show the effectiveness of the proposed models and the related algorithms
Transmission scheduling for multi-process multi-sensor remote estimation via approximate dynamic programming
No full textIn this paper, we consider a remote estimation problem where multiple dynamical systems are observed by smart sensors, which transmit their local estimates to a remote estimator over channels prone to packet losses. Unlike previous works, we allow multiple sensors to transmit simultaneously even though they can cause interference, thanks to the multi-packet reception capability at the remote estimator. In this setting, the remote estimator can decode multiple sensor transmissions (successful packet arrivals) as long as their signal-to-interference-and-noise ratios (SINR) are above a certain threshold. In this setting, we address the problem of optimal sensor transmission scheduling by minimizing a finite horizon discounted expected estimation error covariance cost across all systems at the remote estimator, subject to an average transmission cost. While this problem can be posed as a stochastic control problem, the optimal solution requires solving a Bellman equation for a dynamic programming (DP) problem, the complexity of which scales exponentially with the number of systems being measured and their state dimensions. In this paper, we resort to a novel Least Squares Temporal Difference (LSTD) Approximate Dynamic Programming (ADP) based approach to approximating the value function. More specifically, an off-policy based LSTD approach, named in short Enhanced-Exploration Greedy LSTD (EG-LSTD), is proposed. We discuss the convergence analysis of the EG-LSTD algorithm and its implementation. A Python based program is developed to implement and analyse the different aspects of the proposed method. Simulation examples are presented to support the results of the proposed approach both for the exact DP and ADP cases
Enhanced Exploration Least-Squares Methods for Optimal Stopping Problems
No full textThis letter presents an Approximate Dynamic Programming (ADP) least-squares based approach for solving optimal stopping problems with a large state space. By extending some previous work in the area of optimal stopping problems, it provides a framework for their formulation and resolution. The proposed method uses a combined on/off policy exploration mechanism, where states are generated by means of state transition probability distributions different from the ones dictated by the underlying Markov decision processes. The contraction mapping property of the associated projected Bellman operator is analysed as well as the convergence of the resulting algorithm
Price Management in Resource Allocation Problem with Approximate Dynamic Programming
No full textThe problem of managing the price for resource allocation arises in several applications, such as purchasing plane tickets, reserving a parking slot, booking a hotel room or renting SW/HW resources on a cloud. In this paper, we model a price management resource allocation problem with parallel Birth-Death stochastic Processes (BDPs) to account for the fact that the same resource can be possibly purchased by customers at different prices. In addition, customers can hold the resource at the purchase price to the necessary extent. The maximization of the revenue in both the finite and infinite time horizon cases is addressed in this paper with Stochastic Dynamic Programming (DP) approaches. To overcome the difficulty in solving the corresponding optimization problem due to the state space explosion, Approximate Dynamic Programming (ADP) techniques (in particular, the Least Square Temporal Difference method along with Monte Carlo simulations) are adopted. Furthermore, a MATLAB Toolbox is developed with the aim of solving stochastic DP/ADP problems and supporting probabilistic analysis. Extensive simulations are performed to show the effectiveness of the proposed model and the optimization approach
- …
