In this paper we study the bicausal optimal transport problem for Markov chains, an optimal transport formulation suitable for stochastic processes which takes into consideration the accumulation of information as time evolves. Our analysis is based on a relation between the transport problem and the theory of Markov decision processes. This way we are able to derive necessary and sufficient conditions for optimality in the transport problem, as well as an iterative algorithm, namely the value iteration, for the calculation of the transportation cost. Additionally, we draw the connection with the classic theory on couplings for Markov chains, and in particular with the notion of faithful couplings.

This paper develops a Hoeffding inequality for the partial sums Σk=1nf(Xk), where {Xk}k∈Z>0is an irreducible Markov chain on a finite state space S, and f : S → [a, b] is a real-valued function. Our bound is simple, general, since it only assumes irreducibility and finiteness of the state space, and powerful. In order to demonstrate its usefulness we provide two applications in multi-armed bandit problems. The first is about identifying an approximately best Markovian arm, while the second is concerned with regret minimization in the context of Markovian bandits.

We study an extension of the classic stochastic multi-armed bandit problem which involves multiple plays and Markovian rewards in the rested bandits setting. In order to tackle this problem we consider an adaptive allocation rule which at each stage combines the information from the sample means of all the arms, with the Kullback-Leibler upper confidence bound of a single arm which is selected in round-robin way. For rewards generated from a one-parameter exponential family of Markov chains, we provide a finite-time upper bound for the regret incurred from this adaptive allocation rule, which reveals the logarithmic dependence of the regret on the time horizon, and which is asymptotically optimal. For our analysis we devise several concentration results for Markov chains, including a maximal inequality for Markov chains, that may be of interest in their own right. As a byproduct of our analysis we also establish asymptotically optimal, finite-time guarantees for the case of multiple plays, and i.i.d. rewards drawn from a one-parameter exponential family of probability densities. Additionally, we provide simulation results that illustrate that calculating Kullback-Leibler upper confidence bounds in a round-robin way, is significantly more efficient than calculating them for every arm at each round, and that the expected regrets of those two approaches behave similarly.

In aiming to create added intelligence for Things interfacing with IoT principles in the form of Services, Smart Heating Management is consistently a field of promising research. In the currently demonstrated work, an approach will be described for an operational software framework of modular components that can create intelligence in Housing Units as those presented in our scenario. The framework is based on the lightweight Case Based Reasoning approach and principles in order to describe the Problem and Solution of heating management, as well as to extract knowledge from generic historical data. Collaboration between houses is included through the sharing of anonymized high level problem-solution data, as an instantiation of the same social learning principles that govern human behavior and enable Knowledge diffusion. The approach is validated through historical data acquired in two time periods from the Camden (London) community residencies and demonstrates an average of 22% savings in boiler active time. Knowledge sharing is also analyzed along with the benefits and pitfalls it might produce.

We give a complete characterization of the sampling complexity of best Markovian arm identification in one-parameter Markovian bandit models. We derive instance specific nonasymptotic and asymptotic lower bounds which generalize those of the IID setting. We analyze the Track-and-Stop strategy, initially proposed for the IID setting, and we prove that asymptotically it is at most a factor of four apart from the lower bound. Our one-parameter Markovian bandit model is based on the notion of an exponential family of stochastic matrices for which we establish many useful properties. For the analysis of the Track-and-Stop strategy we derive a novel and optimal concentration inequality for Markov chains that may be of interest in its own right.

Cloud computing has changed considerably the architecture of modern IT systems introducing new design principles based on the notion of the service as main building unit. Decoupling the service offering from the underlying infrastructure, cloud computing allows for more efficient management of the required resources which in business level is translated into higher flexibility and increased profit. To this end, Clouds are not only an innovative technological environment but also a beneficial market for all the involved stakeholders. This market expands continuously and new service aggregations, customizations and business models are offered in order to cover the needs of all end-users. However, even in this new business ecosystem, the question still remains: “Which offering should I buy”? In this paper we present an approach for incorporating business intelligence in cloud marketplaces through a mechanism for answering this question based on the individual requirements and use profile of each particular cloud customer.