In this work, we study the system of two interacting non-cooperative Q-learning agents, where one agent has the privilege of observing the other's actions. We show that this information asymmetry can lead to a stable outcome of population learning, which does not occur in an environment of general independent learners. Furthermore, we discuss the resulted post-learning policies, show that they are almost optimal in the underlying game sense, and provide numerical hints of almost welfare-optimal of the resulted policies.

Online-learning literature has focused on designing algorithms that ensure sub-linear growth of the cumulative long-term constraint violations. The drawback of this guarantee is that strictly feasible actions may cancel out constraint violations on other time slots. For this reason, we introduce a new performance measure, whose particular instance is the cumulative positive part of the constraint violations. We propose a class of non-causal algorithms for online-decision making, which guarantees, in slowly changing environments, sub-linear growth of this quantity despite noisy first-order feedback. Furthermore, we demonstrate by numerical experiments the performance gain of our method relative to state of the art.

We consider the problem of resource congestion control for competing online learning agents under privacy and security constraints. Based on the non-cooperative game as the model for agents' interaction and the noisy online mirror ascent as the model for the rationality of the agents, we propose a novel pricing mechanism that gives the agents incentives for sustainable use of the resources. An advantage of our method is that it is privacy-preserving in the sense that mainly the resource congestion serves as an orientation for our pricing mechanism, in place of the agents' preference and state. Moreover, our method is robust against adversary agents' feedback in the form of the noisy gradient. We present the following result of our theoretical investigation: In case that the feedback noise is persistent, and for several choices of the intrinsic parameter (the learning rate) of the agents and of the mechanism parameters (the learning rate of the price-setters, their progressivity, and the extrinsic price sensitivity of the agents), we show that the accumulative violation of the resource constraints of the resulted iterates is sub-linear w.r.t the time horizon. To support our theoretical findings, we provide some numerical simulations.

High peak values of transmission signals in wireless communication systems lead to wasteful energy consumption and degradation of several transmission performances. We continue the theoretical contributions made by Boche and Farell toward the understanding of peak value reduction, using the strategy known as tone reservation for orthogonal transmission schemes. There it was shown that for orthogonal frequency-division multiplexing (OFDM) systems, the combinatorial object called arithmetic progression plays an important role in setting limitations for the applicability of the tone reservation method. In this paper, we show that the combinatorial object introduced as perfect Walsh sum (PWS) plays a similar role for code-division multiple access (CDMA) systems as arithmetic progression for OFDM systems. By specific construction, we show that for a chosen numbers m and n, all subsets I of the set [N] of the first N = 2nnatural numbers, which has the density in [N] larger than a given δ ∈ (0, 1), i.e., |I| / N ≥ δ, and which is sufficiently large enough, in the sense that |I| ≥ 2(2/δ)2m-1, contains a PWS of size 2m. By means of this result, and motivated by the previously mentioned connection between arithmetic progression and PWS, we show results for the PWS which are analogous to the famous Szemerédi theorem on arithmetic progressions, ConlonGower's theorem on probabilistic construction of “sparse” sets containing an arithmetic progression, and even a solution of an analogon to the Erdos' conjecture on arithmetic progressions. Those results give in particular an insight into the asymptotic limitations of tone reservation method for the CDMA systems. Besides, we show that a subset I of [N] is a PWS if and only if the embedding inequality of the subspace of L1([0, 1]), containing linear combinations of Walsh functions indexed by elements of I, holds with the minimum possible embedding constant √|I|. The corresponding approach based in particular by the fact that the PWSs are the only Walsh sums having unit L1-norm, proven in this paper. By means of that results, we show that the minimum possible threshold constant for which the tone reservation method is applicable yields √|I| if and only if the information set I is a PWS.

It is known that there exist signals in Paley-Wiener space PWπ1of bandlimited signals with absolutely integrable Fourier transform, for which the peak value of the Shannon sampling series diverges unboundedly. In this paper we analyze the structure of the set of signals which lead to strong divergence. Strong divergence is closely linked to the existence of adaptive methods. We prove that there exists an infinite dimensional closed subspace of PW1π1, all signals of which, except the zero signal, lead to strong divergence of the peak value of the Shannon sampling series.

High peak values of transmission signals in wireless communication systems lead to wasteful energy consumption and degradation of several transmission performances. We continue the theoretical contributions made by B. and Farell [1, 2] towards the understanding of peak value reduction, using the strategy known as tone reservation for orthogonal transmission schemes. There it was shown that for OFDM systems, the combinatorial object called arithmetic progression plays an important role in setting limitations for the applicability of the tone reservation method. In this work, we consider ourselves with the performance of the tone reservation in the probabilistic asymptotic setting. We show in particular that for a sufficiently large number N of carriers, choosing each element of that set independently with arbitrary small probability, yields in turn a set of carriers, for which the PAPR reduction problem is not solvable with certain explicitly given threshold constants with probability 1 as N goes to infinity.

In this paper we analyze the peak-to-average power ratio (PAPR) reduction by tone reservation for orthogonal frequency division multiplexing (OFDM) schemes. In addition to the strong solvability of the PAPR reduction problem, where the PAPR has to be bounded by some constant, we consider a weaker form of solvability, where only the boundedness of the peak value of the signal is required. We show that for OFDM both forms of solvability are equivalent. Further, we show that in the case where the PAPR problem is not solvable, the set of input signals that lead to an unbounded OFDM signal is a residual set. As a consequence, if the upper density of the carriers, used for information transmission, is positive, the set of input signals that lead to a bounded OFDM signal is a meager set.

The high peak value of the transmission signal of wireless communication systems lead to wasteful energy consumption and degradation of several transmission performances. We continue the theoretical contributions made in [1], [2] towards the understanding of tone reservation method for orthogonal transmission schemes. There it was shown that the combinatorial object called arithmetic progression plays an important role in setting limitations for the applicability of the tone reservation method for OFDM system. In this work, we introduce the combinatorial object called perfect Walsh sum (PWS), playing a similar role for CDMA systems as arithmetic progression for OFDM systems. We show that for a given m, n ϵ N and δ ϵ (0, 1), every subset I of the set [N] of the first N=2nnumbers, which fulfills |I|/N ≥ δ and |I| ≥ 2(2/δ)2m - 1, contains a PWS of size 2m. Consequences of the latter are results analogous to the famous Szemerédi Theorem on arithmetic progressions, Conlon-Gower's Theorem on probabilistic construction of “sparse” sets containing an arithmetic progression, and even a solution of Erdos' conjecture on arithmetic progressions. Those results give in particular an insight into the asymptotic behaviour of tone reservation method for CDMA systems.

In this work, we show by means of the technique inspired by the Banach-Steinhaus Thm., that typically the Fourier transform of an integrable signal decays arbitrarily slowly toward the infinity, and has an arbitrary weak worst continuity/smoothness behaviour. However, the corresponding characterization can only be given weakly by means of the limit superior. Those statements gives therefore a tightening of the famous Riemann-Lebesgue's Lemma. Furthermore, we give a construction of functions, whose Fourier transform decays slowly than an arbitrary given decay rate. Inspired by that, we are also able to give an alternative proof of the strong divergence of the Shannon sampling series [1] for signals in the Paley-Wiener space PW(ωg)1, band-limited to an arbitrary ωgϵ ℝ+. The corresponding construction of signals is stronger than the existent one given by Boche and Farell, and gives a new insight into the divergence phenomenon of the Shannon sampling series.

Knowing whether a reconstruction process, for example the Shannon sampling series, is strongly divergent in terms of the lim or only weakly divergent in terms of the lim sup is important, because strong divergence is linked to the non-existence of adaptive reconstruction processes. For non-adaptive reconstruction processes the existence is answered by the Banach-Steinhaus theory. However, the analysis of adaptive reconstruction processes is more difficult and not covered by the former theory. In this paper we consider the Paley-Wiener space PWπ1of bandlimited signals with absolutely integrable Fourier transform and analyze the structure of the set of signals for which the peak value of the Shannon sampling series is strongly divergent. We show that this set is lineable, i.e., that there exists an infinite dimensional subspace, all signals of which, except the zero signal, lead to strong divergence. Consequently, for all signals from this subspace, adaptivity in the number of samples that are used in the Shannon sampling series does not create a convergent reconstruction process.

This paper provides a quantitative notion of the sparsity for infinite dimensional atomic spaces, which play an important role in many signal processing applications. This notion of sparsity is defined as the ratio of the number of redundant samples (not necessary to recover any signal in the atomic space) to the number of all available samples of a particular canonical sampling system. It is shown that the so defined sparsity can be expressed in terms of the support of the spectral density of the sequence which generates the atomic space.