We address differentially private stochastic bandit problems by leveraging Thompson Sampling with Gaussian priors and Gaussian differential privacy (GDP). We propose DP-TS-UCB, a novel parametrized private algorithm that enables trading off privacy and regret. DP-TS-UCB satisfies $ \tilde{O} \left(T^{0.25(1-\alpha)}\right)$-GDP and achieves $O \left(K\ln^{\alpha+1}(T)/\Delta \right)$ regret bounds, where $K$ is the number of arms, $ \Delta$ is the sub-optimality gap, $T$ is the learning horizon, and $\alpha \in [0,1]$ controls the trade-off between privacy and regret. Theoretically, DP-TS-UCB relies on anti-concentration bounds for the Gaussian distributions, linking the exploration mechanisms of Thompson Sampling and Upper Confidence Bound, which may be of independent research interest.

We propose two Thompson Sampling-like, model-based learning algorithms for episodic Markov decision processes (MDPs) with a finite time horizon. Our proposed algorithms are inspired by Optimistic Thompson Sampling (O-TS), empirically studied in Chapelle and Li [2011], May et al. [2012] for stochastic multi-armed bandits. The key idea for the original O-TS is to clip the posterior distribution in an optimistic way to ensure that the sampled models are always better than the empirical models. Both of our proposed algorithms are easy to implement and only need one posterior sample to construct an episode-dependent model. Our first algorithm, Optimistic Thompson Sampling for MDPs (O-TS-MDP), achieves a $\widetilde{O} \left(\sqrt{AS^2H^4T} \right)$ regret bound, where $S$ is the size of the state space, $A$ is the size of the action space, $H$ is the number of time-steps per episode and $T$ is the number of episodes. Our second algorithm, Optimistic Thompson Sampling plus for MDPs (O-TS-MDP$^+$), achieves the (near)-optimal $\widetilde{O} \left(\sqrt{ASH^3T} \right)$ regret bound by taking a more aggressive clipping strategy. Since O-TS was only empirically studied previously, we derive regret bounds of O-TS for stochastic bandits. In addition, we propose, O-TS-Bandit$^+$, a randomized version of UCB1 [Auer et al., 2002], for stochastic bandits. Both O-TS and O-TS-Bandit$^+$ achieve the optimal $O\left(\frac{A\ln(T)}{\Delta} \right)$ problem-dependent regret bound, where $\Delta$ denotes the sub-optimality gap.

We address differentially private stochastic bandits. We present two (near)-optimal Thompson Sampling-based learning algorithms: DP-TS and Lazy-DP-TS. The core idea in achieving optimality is the principle of optimism in the face of uncertainty. We reshape the posterior distribution in an optimistic way as compared to the non-private Thompson Sampling. Our DP-TS achieves a $\sum\limits_{j \in \mathcal{A}: \Delta_j > 0} O \left(\frac{\log(T)}{\min \left\{\epsilon, \Delta_j \right\} )} \log \left(\frac{\log(T)}{\epsilon \cdot \Delta_j} \right) \right)$ regret bound, where $\mathcal{A}$ is the arm set, $\Delta_j$ is the sub-optimality gap of a sub-optimal arm $j$, and $\epsilon$ is the privacy parameter. Our Lazy-DP-TS gets rid of the extra $\log$ factor by using the idea of dropping observations. The regret of Lazy-DP-TS is $ \sum\limits_{j \in \mathcal{A}: \Delta_j > 0} O \left(\frac{\log(T)}{\min \left\{\epsilon, \Delta_j \right\}} \right)$, which matches the regret lower bound. Additionally, we conduct experiments to compare the empirical performance of our proposed algorithms with the existing optimal algorithms for differentially private stochastic bandits.

We consider differentially private algorithms for reinforcement learning in continuous spaces, such that neighboring reward functions are indistinguishable. This protects the reward information from being exploited by methods such as inverse reinforcement learning. Existing studies that guarantee differential privacy are not extendable to infinite state spaces, as the noise level to ensure privacy will scale accordingly to infinity. Our aim is to protect the value function approximator, without regard to the number of states queried to the function. It is achieved by adding functional noise to the value function iteratively in the training. We show rigorous privacy guarantees by a series of analyses on the kernel of the noise space, the probabilistic bound of such noise samples, and the composition over the iterations. We gain insight into the utility analysis by proving the algorithm's approximate optimality when the state space is discrete. Experiments corroborate our theoretical findings and show improvement over existing approaches.

We consider a generic model of distributed caching systems, where the cache servers are constrained by two main resources: memory size and bandwidth. Content distribution networks (CDNs) providing video contents and peer-to-peer video-on-demand services are a few examples of such systems. The throughput of these systems crucially depends on how these resources are managed, i.e., how contents are replicated across servers and how requests of specific contents are matched to servers storing the contents. In this paper, we formulate the problem of computing the replication policy and the matching policy, which jointly maximizes the throughput of the caching system. It is shown that computing the optimal replication policy for a given finite system is an NP-hard problem. A greedy replication scheme is then proposed and is shown to achieve a constant factor approximation guarantee when combined with the optimal matching policy. We note that the optimal matching policy has the problem of interruption in service of the ongoing requests due to re-assignment or repacking of the existing requests. To avoid this problem, we propose a simple randomized online matching scheme and analyze its performance in conjunction with the proposed replication scheme. We consider a limiting regime, where the number of servers is large and the arrival rates of the contents are scaled proportionally, and show that the proposed policies achieve asymptotic optimality. Extensive simulation results are presented to evaluate the performance of different policies and study the behavior of the caching system under different service time distributions of the requests.

We consider models of content delivery networks in which the servers are constrained by two main resources: memory and bandwidth. In such systems, the throughput crucially depends on how contents are replicated across servers and how the requests of specific contents are matched to servers storing those contents. In this paper, we first formulate the problem of computing the optimal replication policy which if combined with the optimal matching policy maximizes the throughput of the caching system in the stationary regime. It is shown that computing the optimal replication policy for a given system is an NP-hard problem. A greedy replication scheme is proposed and it is shown that the scheme provides a constant factor approximation guarantee. We then propose a simple randomized matching scheme which avoids the problem of interruption in service of the ongoing requests due to re-assignment or repacking of the existing requests in the optimal matching policy. The dynamics of the caching system is analyzed under the combination of proposed replication and matching schemes. We study a limiting regime, where the number of servers and the arrival rates of the contents are scaled proportionally, and show that the proposed policies achieve asymptotic optimality. Extensive simulation results are presented to evaluate the performance of different policies and study the behavior of the caching system under different service time distributions of the requests.

We consider the problem of active sequential hypothesis testing where a Bayesian decision maker must infer the true hypothesis from a set of hypotheses. The decision maker may choose for a set of actions, where the outcome of an action is corrupted by independent noise. In this paper we consider a special case where the decision maker has limited knowledge about the distribution of observations for each action, in that only a binary value is observed. Our objective is to infer the true hypothesis with low error, while minimizing the number of action sampled. Our main results include the derivation of a lower bound on sample size for our system under limited knowledge and the design of an active learning policy that matches this lower bound and outperforms similar known algorithms.

Accurate prediction of wireless network performance is important when performing link adaptation or resource allocation. However, the complexity of interference interactions at MAC and PHY layers, as well as the vast variety of possible wireless configurations make it notoriously hard to design explicit performance models. In this paper, we advocate an approach of “learning by observation” that can remove the need for designing explicit and complex performance models. We use machine learning techniques to learn implicit performance models, from a limited number of real-world measurements. These models do not require to know the internal mechanics of interfering Wi-Fi links. Yet, our results show that they improve accuracy by at least 49% compared to measurement-seeded models based on SINR. To demonstrate that learned models can be useful in practice, we build a new algorithm that uses such a model as an oracle to jointly allocate spectrum and transmit power. Our algorithm is utility-optimal, distributed, and it produces efficient allocations that significantly improve performance and fairness.

In recent years there has been an explosive growth of digital content in the form of news feeds, videos, and original content on online platforms such as blogs and social networks. Indeed, such platforms have been used as a means of sharing and republishing information, leading to a large collection of content that users must sift through. We consider the problem of curating this vast catalogue of content such that aggregators or publishers can offer readers content that is of interest to them, with minimal spam. Under a game-theoretic model we obtain several results on the optimal content selection and on the efficiency of distributed curation.

We consider the performance of information propagation through social networks in a scenario where each user has a budget of attention, that is, a constraint on the frequency with which he pulls content from neighbors. In this context we ask the question “when users make selfish decisions on how to allocate their limited access frequency among neighbors, does information propagate efficiently?” For the metric of average propagation delay, we provide characterizations of the optimal social cost and the social cost under selfish user optimizations for various topologies of interest. Three situations may arise: well-connected topologies where delay is small even under selfish optimization; tree-like topologies where selfish optimization performs poorly while optimal social cost is low; and “stretched” topologies where even optimal social cost is high. We propose a mechanism for incentivizing users to modify their selfish behaviour, and observe its efficiency in the family of tree-like topologies mentioned above.

Hajek and Zhu recently showed that the BitTorrent protocol can become unstable when peers depart immediately after downloading all pieces of a file. In light of this result, Zhou et al. propose bundling swarms together, allowing peers to exchange pieces across different swarms, and claim that such "universal swarms" can increase BitTorrent's stability region. In this work, we formally characterize the stability region of universal swarms and show that they indeed exhibit excellent stability properties. In particular, bundling allows a single seed with limited upload capacity to serve an arbitrary number of disjoint swarms if the arrival rate of peers in each swarm is lower than the seed upload capacity. Our result also shows that the stability region is insensitive to peers' upload capacity, piece selection policies and number of swarms.

Hajek and Zhu recently showed that the BitTorrent protocol can become unstable when peers depart immediately after downloading all pieces of a file. In light of this result, Zhou et al. propose bundling swarms together, allowing peers to exchange pieces across different swarms, and claim that such "universal swarms" can increase BitTorrent's stability region. In this work, we formally characterize the stability region of universal swarms and show that they indeed exhibit excellent stability properties. In particular, bundling allows a single seed with limited upload capacity to serve an arbitrary number of disjoint swarms if the arrival rate of peers in each swarm is lower than the seed upload capacity. Our result also shows that the stability region is insensitive to peers' upload capacity, piece selection policies and number of swarms.

Optimal dissemination schemes have previously been studied for peer-to-peer live streaming applications. Live streaming being a delay-sensitive application, fine tuning of dissemination parameters is crucial. In this paper, we investigate optimal sizing of chunks, the units of data exchange, and probe sets, the number peers a given node probes before transmitting chunks. Chunk size can have significant impact on diffusion rate (chunk miss ratio), diffusion delay, and overhead. The size of the probe set can also affect these metrics, primarily through the choices available for chunk dissemination. We perform extensive simulations on the so-called random-peer, latest-useful dissemination scheme. Our results show that size does matter, with the optimal size being not too small in both cases.

The downlink capacity of cellular networks is known to be strongly limited by inter-cell interference. In order to mitigate this interference, a number of frequency reuse schemes have recently been proposed. In this paper, we compare the potential capacity gains of these schemes accounting for the random nature of traffic.

The design of scheduling policies for wireless data systems has been driven by a compromise between the objectives of high overall system throughput and the degree of fairness among users, while exploiting multi-user diversity, i.e., fast-fading variations. These policies have been thoroughly investigated in the absence of user mobility, i.e., without slow fading variations. In the present paper, we examine the impact of intra- and inter-cell user mobility on the trade-off between throughput and fairness, and on the suitable choice of alpha-fair scheduling policies. We consider a dynamic setting where users come and go over time as governed by random finite-size data transfers, and explicitly allow for users to roam around. It is demonstrated that the overall performance improves as the fairness parameter alpha is reduced, and in particular, that proportional fair scheduling may yield relatively poor performance, in sharp contrast to the standard scenario with only fast fading. Since a lower alpha tends to affect short-term fairness, we explore how to set the fairness parameter so as to strike the right balance between overall performance and short-term fairness. It is further established that mobility tends to improve the performance, even when the network operates under a local fair scheduling policy as opposed to a globally optimal strategy. We present extensive simulation results to confirm and illustrate the analytical findings.

We investigate performance bounds of P2P systems by application of the law of bandwidth conservation. This approach is quite general and allows us to consider various sharing systems such as fixed-rate streaming, VoD-type streaming, and elastic file sharing. Starting from a general law of bandwidth conservation, we consider several specific cases that apply to various P2P systems. For dynamic systems with a stationary arrival process, we show that simple seeding policies result in regimes where the download rates are arbitrarily fast. We consider a case with equal download rate among all peers as well as cases where the download rate is a function of upload rates, inspired by BitTorrent's tit-for-tat policy. In particular, we show that the sustainable proportion of free-riders is closely related to the tit-for-tat parameter.

Channel-aware scheduling strategies have emerged as an effective mechanism for improving the throughput of wireless data users by exploiting rate variations. The improvement in throughput comes however at the expense of an increase in the variability of the service rate received over time. While the larger variability only has a limited impact on delay-tolerant data transfers, it does severely affect delay-sensitive applications. In order to examine the merits of channel-aware scheduling for the latter users, we consider a wireless system supporting a combination of streaming and elastic traffic. We first examine a scenario with rate-adaptive streaming traffic, and analyze the flow-level performance in terms of transfer delays and user throughputs for various canonical resource sharing schemes. Simulation experiments demonstrate that the analytical results yield remarkably accurate estimates, and indicate that channel-aware scheduling achieves significant performance gains. Next we investigate a scenario where the streaming sources have an intrinsic rate profile and stringent delay requirements. In that case, channel-aware scheduling yields only modest performance gains, and may even be harmful.

We consider wireless multihop data networks with random multi-access mechanisms at the MAC layer. Our aim is to study the performance as perceived by users in a dynamic setting where data flows are generated randomly by users and cease upon completion. This task comprises two major difficulties: first, the behavior of random multi-access algorithms at slot- level in a multi-hop network is even more complex than in the case of a single hop hotspot. Second, in order to study user-level performance accounting for a dynamic population of flows, one has to first characterize the so-called rate region when the population is fixed. The rate region is defined by the set of rates at which the different active users can generate packets without inducing any instabilities in the network. Since links interact with each other through interference, characterizing the rate region is as difficult as studying the behavior of a set of interacting queues. In addition, the behavior of the congestion control algorithm must be taken into account since it impacts the set of active links and then interference. We propose a model, based on the so-called mean field approach, that circumvents both difficulties and allows the derivation of explicit expressions for the rate region. Finally, using these expressions we analyze the flow-level performance of the network.

Abstract—The performance of wireless data systems has been thoroughly studied in the context of a single base station. In the present paper we analyze networks with several interacting base stations, and specifically examine the capacity impact of intraand inter-cell mobility. We consider a dynamic setting where users come and go over time as governed by random finite-size data transfers, and explicitly allow for users to roam around over the course of their service. We show that mobility tends to increase the capacity, not only in case of globally optimal scheduling, but also when each of the base stations operates according to a fair sharing policy. The latter approach offers the advantages that it avoids complex centralized control, and grants each user a fair share of the resources, preventing the potential starvation that may occur under a globally optimal strategy. An important implication is that a simple, conservative capacity estimate is obtained by ‘ignoring’ mobility, and assuming that users remain stationary for the duration of their service. We further demonstrate that the capacity region for globally optimal scheduling is in general strictly larger than the stability region for a fair sharing discipline. However, if the users distribute themselves so as to maximize their individual throughputs, thus enabling some implicit coordination, then a fair sharing policy is in fact guaranteed to achieve stability whenever a globally optimal strategy is able to do so.

Though initially designed for data transport, there is increasing interest in using the 802.11 WLAN protocol for voice and other real time services. This paper presents a performance model for voice over WLAN under distributed control. The model is based on classical decoupling arguments and allows an analytical evaluation of network capacity in terms of tuneable protocol parameters. We determine parameter settings that maximize the number of simultaneous conversations and demonstrate the significant impact on capacity of the voice packet size. Models are developed for both dedicated and integrated networks using the priority features of 802.11e

The performance of wireless data systems has been extensively studied in the context of a single base station. In the present paper we investigate the flow-level performance in networks with multiple base stations. We specifically examine the complex, dynamic interaction of the number of active flows in the various cells introduced by the strong impact of interference between neighboring base stations. For the downlink data transmissions that we consider, lower service rates caused by increased interference from neighboring base stations result in longer delays and thus a higher number of active flows. This in turn results in a longer duration of interference on surrounding base stations, causing a strong correlation between the activity states of the base stations. Such a system can be modelled as a network of multi-class processor-sharing queues, where the service rates for the various classes at each queue vary over time as governed by the activity state of the other queues. The complex interaction between the various queues renders an exact analysis intractable in general. A simplified network with only one class per queue reduces to a coupled-processors model, for which there are few results, even in the case of two queues. We thus derive bounds and approximations for key performance metrics like the number of active flows, transfer delays, and flow throughputs in the various cells. Importantly, these bounds and approximations are insensitive, yielding simple expressions, that render the detailed statistical characteristics of the system largely irrelevant.

We study the effect of two control parameters of the universal mobile telecommunication system handoff algorithm on resource allocation and the outage probability of the forward link. We thereby provide information on the effect of the parameters on the probability distributions of the number of base stations (BSs) supporting a mobile station (MS), the number of MSs supported by a single BS (per carrier), and the maximal cell size, subject to a given probability of downlink outage on the cell boundary. Denoting the set of BSs supporting an MS in soft handoff as the active group, the first parameter n/sub A/ is the maximum allowed size of the active group. The second, denoted /spl tau/, is the upper limit on the difference between the local mean received power from the dominant BS and that from any other member of the active group (in decibels), where the term "dominant" refers to the BS with the lowest path loss to the MS. We assume that the MS is equipped with a Rake receiver capable of performing "maximal ratio combining" of the signals it receives from the transmitting BSs. We present general analytical derivations along with results derived for specific situations through simulations and numerical integration.

Traditional definitions of capacity of CDMA networks are either related to the number of calls they can handle or to the arrival rate that guarantees that the rejection rate is below a given fraction (Erlang capacity). We extend the latter definition to other quality of service (QoS). We consider best-effort (BE) traffic sharing the network resources with real-time (RT) applications. BE applications can adapt their instantaneous transmission rate to the available one and thus need not be subject to admission control or outages. Their meaningful QoS is the average delay. The delay aware capacity is defined as the arrival rate of BE calls that the system can handle such that their expected delay is bounded by a given constant. We compute both the blocking probability of the RT traffic having an adaptive grade of service (GoS) as well as the expected delay of the BE traffic for an uplink multicell WCDMA system. This yields the Erlang capacity for former and the delay capacity for the latter.

We present a model for soft, hand-off in wireless cellular networks. In such networks, due to overlapping cells, hand-offs are not instantaneous and multiple channels may be occupied by a single mobile for a non-zero freeze time period.