Polyak–Ruppert averaging is a widely used technique to achieve the optimal asymptotic variance of stochastic approximation (SA) algorithms, yet its high-probability performance guarantees remain underexplored in general settings. In this paper, we present a general framework for establishing non-asymptotic concentration bounds for the error of averaged SA iterates. Our approach assumes access to individual concentration bounds for the unaveraged iterates and yields a sharp bound on the averaged iterates. We also construct an example, showing the tightness of our result up to constant multiplicative factors. As direct applications, we derive tight concentration bounds for contractive SA algorithms and for algorithms such as temporal difference learning and $Q$-learning with averaging, obtaining new bounds in settings where traditional analysis is challenging.

We consider the following distributed service model: jobs with unit mean, exponentially distributed, and independent processing times arrive as a Poisson process of rate λ N, with 0<λ<1, and are immediately dispatched to one of several queues associated with N identical servers with unit processing rate. We assume that the dispatching decisions are made by a central dispatcher endowed with a finite memory, and with the ability to exchange messages with the servers. We study the fundamental resource requirements (memory bits and message exchange rate), in order to drive the expected steady-state queueing delay of a typical job to zero, as N increases. We propose a certain policy and establish (using a fluid limit approach) that it drives the delay to zero when either (i) the message rate grows superlinearly with N, or (ii) the memory grows superlogarithmically with N. Moreover, we show that any policy that has a certain symmetry property, and for which neither condition (i) or (ii) holds, results in an expected queueing delay which is bounded away from zero.

This paper considers the problem of allocating exchange rates in peer-to-peer dissemination, which must consider the dual objectives of throughput efficiency and reciprocity between peers, the latter essential to cooperation incentives. This question has been studied in prior research for wired networks under an upload constraint, where the focus is on achieving reciprocity through decentralized peer interactions. We consider here a wireless network substrate, for which link capacities are non-uniform according to the peering choice, and exchanges may be subject to interference. A convex optimization problem is formulated that trades off efficiency and reciprocity, and various schemes are investigated to achieve a decentralized solution.

IEEE 802.11n, the latest version of the widely used standard for wireless LANs, promises significant increases in speed by incorporating multiple enhancements at the physical layer. In this paper we demonstrate that, on the contrary, the straightforward deployment of 802.11n in conjunction with TCP over a simple, single access-point network, can dramatically underachieve the promised speeds. Part of the deficiency is due to overheads and can be improved by the technique of packet aggregation present in the standard. However more subtle problems are identified, in particular the downward equalization of throughputs that occurs under physical rate diversity, or the unreasonable portion of resources taken by uplink flows when competing with the more numerous downlink connections. These difficulties are demonstrated and their causes explained through a sequence of experiments with the ns3 packet simulator. Our analysis leads us to propose a desirable resource allocation for these situations of competition, and an architecture for control in the access-point to achieve it. Our solution involves a combination of packet aggregation, multiple queues and TCP-ACK isolation, compatible with the standard and where all the control resides at the AP. We demonstrate analytically and through extensive simulation that our method is able to provide significant enhancements in performance under a variety of traffic conditions.