In the optimization of dynamic systems, the variables typically have constraints. Such problems can be modeled as a Constrained Markov Decision Process (CMDP). This paper considers the peak Constrained Markov Decision Process (PCMDP), where the agent chooses the policy to maximize total reward in the finite horizon as well as satisfy constraints at each epoch with probability 1. We propose a model-free algorithm that converts PCMDP problem to an unconstrained problem and a Q-learning based approach is applied. We define the concept of probably approximately correct (PAC) to the proposed PCMDP problem. The proposed algorithm is proved to achieve an $(\epsilon,p)$-PAC policy when the episode $K\geq\Omega(\frac{I^2H^6SA\ell}{\epsilon^2})$, where $S$ and $A$ are the number of states and actions, respectively. $H$ is the number of epochs per episode. $I$ is the number of constraint functions, and $\ell=\log(\frac{SAT}{p})$. We note that this is the first result on PAC kind of analysis for PCMDP with peak constraints, where the transition dynamics are not known apriori. We demonstrate the proposed algorithm on an energy harvesting problem and a single machine scheduling problem, where it performs close to the theoretical upper bound of the studied optimization problem.

In this paper, we consider the problem of optimization and learning for constrained and multi-objective Markov decision processes, for both discounted rewards and expected average rewards. We formulate the problems as zero-sum games where one player (the agent) solves a Markov decision problem and its opponent solves a bandit optimization problem, which we here call Markov-Bandit games. We extend $Q$-learning to solve Markov-Bandit games and show that our new $Q$-learning algorithms converge to the optimal solutions of the zero-sum Markov-Bandit games, and hence converge to the optimal solutions of the constrained and multi-objective Markov decision problems. We provide numerical examples where we calculate the optimal policies and show by simulations that the algorithm converges to the calculated optimal policies. To the best of our knowledge, this is the first time Q-learning algorithms guarantee convergence to optimal stationary policies for the multi-objective Reinforcement Learning problem with discounted and expected average rewards, respectively.

In this paper, we revisit the problem of finding the average capacity of the Gaussian feedback channel. First, we consider the problem of finding the average capacity of the analog Gaussian noise channel, where the noise has an arbitrary spectral density. We introduce a new approach to the problem, where we solve the problem over a finite number of transmissions and then consider the limit of an infinite number of transmissions. Furthermore, we consider the important special case of stationary Gaussian noise with finite memory. We show that the channel capacity at stationarity can be found by solving a semi-definite program, and hence computationally tractable. We also give new proofs and results of the non-stationary solution which bridges the gap between results in the literature for the stationary and non-stationary feedback channel capacities. It is shown that a linear communication feedback strategy is optimal. Similar to the solution of the stationary problem, it is shown that the optimal linear strategy is to transmit a linear combination of the information symbols to be communicated and the innovations for the estimation error of the state of the noise process.

In probability theory, time series analysis, and signal processing, many identification and estimation methods rely on covariance estimates as an intermediate statistics. Errors in estimated covariances propagate and degrade the quality of the estimation result. In particular, in large network systems where each system node of the network gather and pass on results, it is important to know the reliability of the information so that informed decisions can be made. In this work, we design confidence regions based on covariance estimates and study how these can be used for spectral estimation. In particular, we consider three different confidence regions based on sets of unitarily invariant matrices and bound the eigenvalue distribution based on three principles: uniform bounds; arithmetic and harmonic means; and the Marcenko-Pastur Law eigenvalue distribution for random matrices. Using these methodologies we robustly bound the energy in a selected frequency band, and compare the resulting spectral bound from the respective confidence regions.

In this paper, we consider communication over the bandwidth limited analog white Gaussian noise channel using non-orthogonal pulses. In particular, we consider non-orthogonal transmission by signaling samples at a rate higher than the Nyquist rate. Using the faster-than- Nyquist (FTN) framework, Mazo showed that one may transmit symbols carried by sinc pulses at a higher rate than that dictated by Nyquist without loosing bit error rate. However, as we will show in this paper, such pulses are not necessarily well localized in time. In fact, assuming that signals in the FTN framework are well localized in time, one can construct a signaling scheme that violates the Shannon capacity bound. We also show directly that FTN signals are in general not well localized in time. We also consider FTN signaling in the case of pulses that are different from the sinc pulses. We show that one may use a precoding scheme of low complexity, in order to remove the intersymbol interference. This leads to the possibility of increasing the number of transmitted samples per time unit and compensate for spectral inefficiency due to signaling at the Nyquist rate of the non sinc pulses. We demonstrate the power of the precoding scheme by simulations.