Member, IEEE Panayotis Mertikopoulos

Member, IEEE E Veronica Belmega

Transmit without Regrets: Online Optimization in MIMO-OFDM Cognitive Radio Systems

Keywords: Cognitive radio, exponential learning, MIMO, OFDM, regret minimization, online optimization. I. Introduction

In this paper, we examine cognitive radio systems that evolve dynamically over time due to changing user and environmental conditions. To combine the advantages of orthogonal frequency division multiplexing (OFDM) and multiple-input, multiple-output (MIMO) technologies, we consider a MIMO-OFDM cognitive radio network where wireless users with multiple antennas communicate over several non-interfering frequency bands. As the network's primary users (PUs) come and go in the system, the communication environment changes constantly (and, in many cases, randomly). Accordingly, the network's unlicensed, secondary users (SUs) must adapt their transmit profiles "on the fly" in order to maximize their data rate in a rapidly evolving environment over which they have no control. In this dynamic setting, static solution concepts (such as Nash equilibrium) are no longer relevant, so we focus on dynamic transmit policies that lead to no regret: specifically, we consider policies that perform at least as well as (and typically outperform) even the best fixed transmit profile in hindsight. Drawing on the method of matrix exponential learning and online mirror descent techniques, we derive a no-regret transmit policy for the system's SUs which relies only on local channel state information (CSI). Using this method, the system's SUs are able to track their individually evolving optimum transmit profiles remarkably well, even under rapidly (and randomly) changing conditions. Importantly, the proposed augmented exponential learning (AXL) policy leads to no regret even if the SUs' channel measurements are subject to arbitrarily large observation errors (the imperfect CSI case), thus ensuring the method's robustness in the presence of uncertainties.

growing volume of data traffic and cellphone calls. Exacerbating this issue, studies by the US Federal Communications Commission (FCC) and the National Telecommunications and Information Administration (NTIA) have shown that this vital commodity is effectively squandered through underutilization and inefficient use: only 15% to 85% of the licensed radio spectrum is used on average, leaving ample spectral voids that could be exploited for opportunistic radio access [START_REF] Schinasi | Spectrum management: Better knowledge needed to take advantage of technologies that may improve spectrum efficiency[END_REF][START_REF]Report of the spectrum efficiency working group[END_REF].

In view of the above, the emerging paradigm of cognitive radio (CR) has attracted considerable interest as a promising counter to spectrum scarcity [START_REF] Mitola | Cognitive radio: making software radios more personal[END_REF][START_REF] Zhao | A survey of dynamic spectrum access[END_REF][START_REF] Haykin | Cognitive radio: Brain-empowered wireless communications[END_REF][START_REF] Goldsmith | Breaking spectrum gridlock with cognitive radios: An information theoretic perspective[END_REF]. At its core, this paradigm is simply a two-level hierarchy between communicating users based on spectrum licensing. On the one hand, the network's primary users (PUs) have purchased spectrum rights but allow others to access it provided that their negotiated quality of service (QoS) guarantees are not violated; on the other hand, the network's secondary users (SUs) are free-riding on the licensed part of the spectrum, but they have no QoS guarantees and must conform to the constraints imposed by the PUs. In this way, by opening up the unfilled "white spaces" of the licensed spectrum to opportunistic radio access, the overall utilization of the wireless medium can be greatly increased without compromising the performance guarantees that the network's licensed users have already paid for.

Orthogonally to the above, the seminal prediction that multiple-input and multiple-output (MIMO) technologies can lead to substantial gains in information throughput [START_REF] Foschini | On limits of wireless communications in a fading environment when using multiple antennas[END_REF][START_REF] Telatar | Capacity of multi-antenna Gaussian channels[END_REF] opens up additional ways for overcoming spectrum scarcity.

In particular, by employing multiple antennas, it is possible to exploit spatial degrees of freedom in the transmission and reception of radio signals, the only physical limit being the number of antennas that can be deployed on a portable device. As a result, the existing wireless medium can accommodate greater volumes of data traffic per Hertz without requiring the reallocation (and subsequent re-regulation) of additional frequency bands.

In this paper, we combine these two approaches and focus on dynamic MIMO cognitive radio systems comprising several wireless users (primary and secondary alike) who communicate over multiple non-interfering channels. In this evolving (and unregulated) context, the intended receiver of a message has to cope with unwarranted interference from a large number of transmitters, a factor which severely limits the capacity of the wireless system in question. As a result, given that the system's SUs cannot rely on contractual QoS guarantees to achieve their desired throughput levels, the maximization of their achievable transmission rates under the operational constraints imposed by the network's PUs becomes a critical issue.

On that account, and given that the theoretical performance limits of MIMO systems still elude us (even in basic network models such as the interference channel), a widespread approach is to treat the interference from other users as additive colored noise and to use the mutual information for Gaussian input and noise as a unilateral performance metric [START_REF] Telatar | Capacity of multi-antenna Gaussian channels[END_REF]. However, since users cannot be assumed to have full information on the wireless system as it evolves over time (due to the arrival of new users, fluctuations in the PUs' demand, etc.), they must optimize their signal characteristics "on the fly", based only on locally available information. Hence, our aim is to derive a dynamic transmit policy that allows the system's SUs to adapt to changes in the wireless medium and to track their individually optimum transmission profiles using only local (and possibly imperfect) channel state information (CSI). This setting is fairly general and involves cognitive SUs with significant control over both spatial (MIMO) and spectral (OFDM) degrees of freedom. To the best of our knowledge, only special cases of this problem have been considered in a CR setting. For instance, [START_REF] Zhang | Optimal spectrum sharing in MIMO cognitive radio networks via semidefinite programming[END_REF][START_REF] Scutari | MIMO cognitive radio: A game theoretical approach[END_REF][START_REF] Wang | Robust MIMO cognitive radio via game theory[END_REF] analyzed the case where there is only one channel and the environment is static (i.e. the system's SUs only react to each other and the PUs' spectrum utilization is fixed); in this context, [START_REF] Zhang | Optimal spectrum sharing in MIMO cognitive radio networks via semidefinite programming[END_REF] characterized the best spatial covariance profile for the interacting SUs whereas [START_REF] Scutari | MIMO cognitive radio: A game theoretical approach[END_REF][START_REF] Wang | Robust MIMO cognitive radio via game theory[END_REF] described how to reach a Nash equilibrium in the resulting non-cooperative game. On the other hand, the authors of [START_REF] Nie | Adaptive channel allocation spectrum etiquette for cognitive radio networks[END_REF][START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF][START_REF] Li | Multi-agent Q-learning of channel selection in multi-user cognitive radio systems: A two by two case[END_REF][START_REF] Gai | Learning multiuser channel allocations in cognitive radio networks: A combinatorial multi-armed bandit formulation[END_REF] proposed different learning schemes for optimal channel selection in dynamic environments where the PUs' evolving behavior cannot be anticipated by the system's SUs, but only in the case where the SUs are equipped with a single antenna and cannot split power across subcarriers.

Extending the above considerations, our goal in this paper is to derive an adaptive transmit policy for SU rate optimization in dynamically evolving MIMO-OFDM cognitive radio networks. In this online optimization framework, the most widely used performance criterion is that of regret minimization, a concept which was first introduced by Hannan [START_REF] Hannan | Approximation to Bayes risk in repeated play[END_REF] and which has since given rise to a vigorous literature at the interface of optimization, statistics, game theory, and machine learning -see e.g. [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF][START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF] for a comprehensive survey. Specifically, in the language of game theory, the notion of (external) regret compares the agent's cumulative payoff over time to what he would have obtained by constantly playing the same action. Accordingly, the purpose of regret minimization is to devise learning policies that lead to vanishingly small regret against any fixed action and irrespective of how the agent's environment evolves over time.

In view of the above, we will focus on no-regret policies that perform at least as well as the asymptotically best fixed policy in terms of each user's achievable transmission rate -despite the fact that the latter cannot be determined by the SUs when they have no means to anticipate the PUs' behavior. In particular, motivated by the no-regret properties of the exponential weight (EW) algorithm for problems with discrete action sets [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF][START_REF] Vovk | Aggregating strategies[END_REF][START_REF] Littlestone | The weighted majority algorithm[END_REF][START_REF] Auer | Adaptive and self-confident on-line learning algorithms[END_REF], we propose an augmented exponential learning (AXL) approach that can be applied to the continuous regret minimization problem at hand with minimal information requirements. A key challenge here is that any learning algorithm must respect the problem's semidefiniteness constraints; as such, an important component of our AXL scheme is the continuous-time technique of matrix exponential learning that was recently introduced for ordinary (as opposed to online) rate optimization problems in MIMO multiple access channels (MACs) [START_REF] Mertikopoulos | Matrix exponential learning: Distributed optimization in MIMO systems[END_REF] -and which is in turn closely related to the online mirror descent approach of [START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF] and the matrix regularization techniques of [START_REF] Kakade | Regularization techniques for learning with matrices[END_REF].

Of course, since the SUs' optimal transmit profile varies over time, the notions of convergence and/or convergence speed are no longer applicable; instead, the figure of merit is the rate at which the SUs attain a no-regret state. In that respect, AXL guarantees a worst-case average regret of O(T -1/2 ) after T epochs, a bound which is well known to be tight [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF][START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF]. Additionally, AXL retains its no-regret properties even if the SUs' channel measurements are subject to arbitrarily large observation errors (the imperfect CSI case), thus providing significant performance improvements over more traditional water-filling methods that are sensitive to perfect CSI. As a result, the system's SUs are able to track their individually optimum transmit profile as it evolves over time remarkably well, even under rapidly (and randomly) changing conditions.

Paper Outline and Summary of Results

The breakdown of our paper is as follows: in Section II, we introduce our MIMO-OFDM cognitive radio network model and the notion of a no-regret transmission policy in the context of SU rate optimization. In Section III, we decompose this online rate optimization problem into two components, and we propose a no-regret algorithm for each one. Specifically, in Section III-A, we propose an adaptive power allocation policy for the problem's OFDM component, whereas in Section III-B, we derive a dynamic signal covariance policy for the problem's MIMO component based on matrix exponential learning. These components are fused in Section IV where we present our augmented exponential learning (AXL) method for the general MIMO-OFDM setting and we show that it leads to no regret (Theorem 1). Importantly, we also show that the AXL algorithm retains its no-regret properties even when the users only have imperfect CSI at their disposal (Theorem 2). This theoretical analysis is validated and supplemented by numerical simulations in Section V where we also examine the users' ability to track their individually optimum transmit characteristics. To facilitate presentation, proofs and technical details have been delegated to a series of appendices at the end of the paper.

II. System Model

A. The Network Model

The cognitive radio system that we will focus on consists of a set of non-cooperative wireless MIMO users (primary and secondary alike) that communicate over several non-interfering subcarriers by means of an OFDM scheme [START_REF] Bölcskei | On the capacity of OFDM-based spatial multiplexing systems[END_REF][START_REF] Letaief | Dynamic multiuser resource allocation and adaptation for wireless systems[END_REF]. Specifically, let Q = P ∪ S denote the set of the system's users with P (resp. S) representing the system's primary (resp. secondary) users; assume further that each user q ∈ Q is equipped with m q transmit antennas and that the radio spectrum is partitioned into a set K = {1, . . . , K} of K orthogonal frequency bands [START_REF] Bölcskei | On the capacity of OFDM-based spatial multiplexing systems[END_REF]. Then, the aggregate signal y s k ∈ C n s on the k-th subcarrier at the intended receiver of the secondary user s ∈ S (assumed equipped with n s receive antennas) will be:

y s k = H ss k x s k + p∈P H ps k x p k + r∈S,r s H rs k x r k + z s k , (1)
where x q k ∈ C m q is the transmitted message of user q ∈ Q (primary or secondary) over the k-th subcarrier, H qs k is the channel matrix between the q-th transmitter and the intended receiver of user s, and z s k ∈ C n s is the noise in the channel, including thermal, atmospheric and other peripheral interference effects (and modeled as a non-singular, zero-mean Gaussian vector). Accordingly, if we focus for simplicity on a specific SU and drop the user index s ∈ S in (1), we obtain the signal model

y k = H k x k + w k , (2)
where w k denotes the multi-user interference-plus-noise (MUI) over subcarrier k ∈ K at the intended receiver.

The covariance of w k in (2) obviously changes over time due to fading, modulations in the PUs' behavior, etc.; as a result, employing sophisticated successive interference cancellation (SIC) techniques at the receiver is highly nontrivial, especially with regards to the system's unregulated secondary users; Instead, we will work in the single user decoding (SUD) regime where interference by other users (primary and secondary alike) is treated as additive, colored noise. In this context, the transmission rate of a user under the signal model ( 2) is given by the familiar expression [START_REF] Telatar | Capacity of multi-antenna Gaussian channels[END_REF][START_REF] Bölcskei | On the capacity of OFDM-based spatial multiplexing systems[END_REF]:

Φ(P) = k log det W k + H k P k H † k -log det W k , (3)
where:

1) W k = E w k w † k is the multi-user interference-plus-noise covariance matrix over subcarrier k.

2) P k = E[x k x †
k ] is the covariance matrix of the user's transmitted signal on subcarrier k and P = diag(P 1 , . . . , P K ) denotes the user's transmit profile over all subcarriers. In particular, we will write for convenience:

P k = p k Q k , (4)
where

p k = E[x † k x k ]
denotes the user's transmit power over subcarrier k and

Q k = E x k x † k E x † k x k is his normalized signal covariance matrix.
Hence, given that W k may change over time due to evolving user conditions, we obtain the time-dependent objective:

Φ(P; t) = k log det I + H k (t) P k H † k (t) , (5)
where the effective channel matrices H k are given by

H k (t) = W k (t) -1/2 H k (t), (6)
and the time variable t = 1, 2, . . . is assumed discrete (for instance, corresponding to the epochs of a time-slotted system).

Obviously, since we are putting no constraints on the behavior of the system's users, the evolution of the effective channel matrices H k (t) over time can be quite arbitrary as well. Formally, we only make the following (minimal) assumptions:

A1) The effective channel matrices H k (t) are bounded for all t.

A2) The matrices H k (t) change sufficiently slowly relative to the coherence time of the channel so that the standard results of information theory [START_REF] Telatar | Capacity of multi-antenna Gaussian channels[END_REF] continue to hold.

A3) SUs can obtain possibly imperfect (but otherwise unbiased) estimates for H k , e.g. by measuring H k and probing the intended receiver for the MUI covariance matrix W k .

In light of the above, and motivated by the "white-space filling" paradigm advocated (e.g. by the FCC) as a means to minimize interference by unlicensed users [START_REF] Schinasi | Spectrum management: Better knowledge needed to take advantage of technologies that may improve spectrum efficiency[END_REF][START_REF]Report of the spectrum efficiency working group[END_REF][START_REF] Scutari | MIMO cognitive radio: A game theoretical approach[END_REF][START_REF] Huang | Cognitive Radio Networks: Architectures, Protocols, and Standards[END_REF][START_REF] Stevenson | IEEE 802.22: The first cognitive radio wireless regional area network standard[END_REF], we will consider the following constraints for the system's SUs:

C1) Bounded total transmit power:

tr(P) = k p k ≤ P. (7a)
C2) Constrained transmit power per subcarrier:

tr(P k ) = p k ≤ P k . (7b)
C3) Null-shaping constraints:

U † k P k = 0, (7c)
for some tall complex matrix U k with full column rank.

Of the constraints above, (7a) is a physical constraint on the user's total transmit power, (7b) imposes a limit on the interference level that can be tolerated on a given subcarrier, and (7c) is a "hard", spatial version of (7b) which guarantees that certain spatial dimensions per subcarrier are only open to licensed, primary users. In more detail, (7b) is equivalent to limiting the maximal average interference that SUs are allowed to incur on the primary transmission while the matrices U k of (7c) are imposed by the PUs and their columns represent the spatial directions which are forbidden to SU transmission. Such constraints are well-documented in the literature and simply reflect the fact that some carriers or spatial directions per carrier are preferred by the PUs, so stricter constraints are imposed to limit interference by SUs (for a more detailed discussion, see e.g. [START_REF] Scutari | MIMO cognitive radio: A game theoretical approach[END_REF][START_REF] Wang | Robust MIMO cognitive radio via game theory[END_REF][START_REF] Letaief | Dynamic multiuser resource allocation and adaptation for wireless systems[END_REF] and references therein).

Of course, to maximize (5) in the absence of energy awareness considerations, the user must saturate his total power constraint (7a) by transmitting at the highest possible (total) power. 1 Thus, the set of admissible transmit profiles for the rate function (5) may be expressed as:

X = diag(P 1 , . . . , P K ) : P k ∈ C m k ×m k , P k 0, 0 ≤ tr(P k ) ≤ P k and k tr(P k ) = P , (8)
where m k ≡ nullity(U k ) is the number of spatial dimensions that are open to SUs on subcarrier k. Accordingly, writing P k in the decoupled form P k = p k Q k as in (4), we obtain the decomposition X = X 0 × k D k where

X 0 = p ∈ R K : 0 ≤ p k ≤ P k , k p k = P (9)
denotes the set of admissible power allocation vectors and

D k = Q k ∈ C m k ×m k : Q k 0, tr(Q k ) = 1 (10)
is the set of admissible normalized covariance matrices for subcarrier k. We thus obtain the online rate maximization problem: maximize Φ(P; t)

subject to              P = diag(p 1 Q 1 , . . . , p K Q K ), (p 1 , . . . , p K ) ∈ X 0 , Q k ∈ D k . (ORM)
Remark 1. In the following sections, we will need the derivatives of Φ; to that end, some matrix calculus yields

∂Φ ∂P * k ≡ M k (t) = H † k (t) I + H k (t)P k H † k (t) -1 H k (t), (11)
1 Our analysis can be extended to energy-aware objectives where (7a) is not saturated, but we will not pursue such directions due to space limitations.

where P * k denotes the complex conjugate of P k . Since the effective channel matrices H k (t) are assumed bounded for all t, the above shows that there exists some M > 0 such that: M k (t) ≤ M for all k ∈ K, P ∈ X, and for all t ≥ 0.

(12)

B. Online Optimization and Regret Minimization

In our setting, there is no direct causal link between the PUs' behavior and the choices of the SUs, so the rate function Φ may change arbitrarily over time. This leads to a "game against nature" which is played out as follows:

1) At each time slot t = 1, 2 . . . , the agent (i.e. the focal SU) selects an action (transmit profile) P(t) ∈ X.

2) The agent's payoff (transmission rate) Φ(P(t); t) is determined by nature and/or the behavior of other users (via the effective channel matrices H k ).

3) The agent employs some decision rule (dynamic transmit policy) to pick a new transmit profile P(t + 1) ∈ X at stage t + 1, and the process is repeated until transmission ends.

In this dynamic setting, static solution concepts are no longer applicable, so the most widely used optimization criterion is that of regret minimization, a long-term solution concept which was first introduced by Hannan [START_REF] Hannan | Approximation to Bayes risk in repeated play[END_REF] and which has since given rise to an extremely active field of research at the interface of optimization, statistics and theoretical computer science -see e.g. [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF][START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF] for a survey. Roughly speaking, the regret compares the payoff obtained by an agent that follows a dynamic policy to the payoff that he would have obtained by constantly choosing the same action over the entire transmission horizon. More precisely, the cumulative regret of the dynamic policy P(t) ∈ X with respect to P 0 ∈ X is defined as:

Reg T (P 0 ) = T t=1 Φ(P 0 ; t) -Φ(P(t); t) , (13)
i.e. Reg T (P 0 ) measures the cumulative transmission rate difference up to stage T between a benchmark transmit profile P 0 ∈ X and the dynamic policy P(t). The user's average regret then is T -1 Reg T (P 0 ) and the goal of regret minimization is to devise a dynamic policy P(t) that leads to no regret, viz. lim sup

T →∞ 1 T Reg T (P 0 ) ≤ 0, (14)
for all P 0 ∈ X and irrespective of the evolution of the objective Φ(•; t) over time. In other words, if we interpret lim T →∞ T -1 T t=1 Φ(P 0 ; t) as the long-term average transmission rate of P 0 , ( 14) means that the average data rate of the dynamic transmit policy P(t) must be at least as good as that of any benchmark profile P 0 ∈ X.

Remark 2. Obviously, if the optimum transmit policy which maximizes (ORM) could be predicted at every stage t = 1, 2, . . . in an oracle-like fashion, we would have Reg T (P 0 ) ≤ 0 in (13) for all P 0 ∈ X. Therfore, the requirement ( 14) is fundamental in the context of online optimization because negative regret is a key indicator of tracking the maximum of (ORM) as it evolves over time.

Remark 3. In the machine learning literature, there exist other notions of regret (such as internal, swap or adaptive regret [START_REF] Hazan | Efficient learning algorithms for changing environments[END_REF]) for studying online optimization problems in changing environment. Due to space limitations, we will focus our theoretical analysis on the external regret formulation ( 13) and we will rely on the numerical simulations of Section V to show how well our proposed dynamic policies track the evolving maximum of the rate maximization problem (ORM).

Remark 4. If the channel matrices are drawn at each realization from an isotropic distribution [START_REF] Palomar | Uniform power allocation in MIMO channels: a game-theoretic approach[END_REF], spreading power uniformly across carriers and antennas is the optimal choice when nature (including the network's PUs) is actively choosing the worst possible channel realization for the transmitter [START_REF] Palomar | Uniform power allocation in MIMO channels: a game-theoretic approach[END_REF]. A no-regret policy extends this "min-max" concept by ensuring that the policy's achieved transmission rate is asymptotically as good as that of any fixed transmit profile, including obviously the uniform one as a special case where nature is actively playing against the transmitter -e.g. jamming.

III. Power Allocation and Signal Covariance Optimization

To build intuition step-by-step, we will break up the online rate maximization problem (ORM) in simpler components and we will derive a no-regret transmit policy for each one based on an exponential learning principle. These policies will then be fused into an adaptive transmit policy for the full MIMO-OFDM problem in Section IV.

A. The OFDM Component: Online Power Allocation 1) A gentle start -the case P k ≥ P: For illustration purposes, we first examine the case where the power-perchannel constraints (7b) can be absorbed in the total power constraint (7a), i.e. P k ≥ P for all k ∈ K. Also, for scaling purposes, it will be more convenient to consider the normalized power variables

q k = p k /P. ( 15
)
With this in mind, if the normalized signal covariance profile Q = diag(Q 1 , . . . , Q K ) of the focal SU is kept fixed, we obtain the online power allocation problem: maximize Φ(q; t),

subject to q ∈ ∆ (OPA)
where ∆ = q ∈ R K + : K k=1 q k = 1 denotes the set of feasible (normalized) power allocation profiles and we write Φ(q; t) to highlight the dependence of the rate function (5) on the normalized power allocation profile q ∈ ∆ (instead of P ∈ X).

A special case of this problem is when the user cannot split power across subcarriers and can only choose one channel on which to transmit. Essentially, this channel selection framework boils down to the famous "multi-armed bandit" problem of [START_REF] Robbins | Some aspects of the sequential design of experiments[END_REF] (see e.g. [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF][START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF] for a review). As a result, much recent work on CR networks [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF][START_REF] Li | Multi-agent Q-learning of channel selection in multi-user cognitive radio systems: A two by two case[END_REF][START_REF] Gai | Learning multiuser channel allocations in cognitive radio networks: A combinatorial multi-armed bandit formulation[END_REF] has been focused on no-regret channel selection algorithms based on Q-learning [START_REF] Li | Multi-agent Q-learning of channel selection in multi-user cognitive radio systems: A two by two case[END_REF] or upper confidence bound (UCB) techniques [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF].

Unfortunately, these techniques are inherently discrete in nature, so it is not clear how to extend them to the continuous context of (OPA). Instead, motivated by the exponential weight algorithm introduced in [START_REF] Vovk | Aggregating strategies[END_REF][START_REF] Littlestone | The weighted majority algorithm[END_REF][START_REF] Auer | Adaptive and self-confident on-line learning algorithms[END_REF] for sequence prediction, our approach consists of scoring each channel over time and then allocating power proportionally to the exponential of these scores. In particular, inspired by the analysis of [START_REF] Mertikopoulos | Distributed learning policies for power allocation in multiple access channels[END_REF], each channel will be scored by means of the marginal utilities:

v k = ∂Φ ∂q k = P ∂Φ ∂p k = P • tr M k Q k , (16)
where Q k ∈ D k is the user's (fixed) covariance matrix and M k is given by [START_REF] Wang | Robust MIMO cognitive radio via game theory[END_REF]. We thus obtain the exponential learning power allocation policy:

y k (t) = y k (t -1) + v k (t), q k (t + 1) = exp ηt -1/2 y k (t) exp ηt -1/2 y (t) , (XL-PA)
where η > 0 is a learning rate parameter and the √ t factor has been included to moderate very sharp score differences.

Our first result is that (XL-PA) performs asymptotically as well as any fixed power allocation profile q 0 ∈ ∆:

Proposition 1. If P k ≥ P for all k ∈ K, the policy (XL-PA) leads to no regret. Specifically, for every q 0 ∈ ∆, and independently of the system's evolution over time, we have

1 T Reg T (q 0 ) ≤ 1 √ T log K η + 4P 2 M 2 η , (17)
with M given by [START_REF] Nie | Adaptive channel allocation spectrum etiquette for cognitive radio networks[END_REF].

Proof: See Appendices A and E.

Remark 1. The use of the marginal utilities [START_REF] Hannan | Approximation to Bayes risk in repeated play[END_REF] in the exponential learning policy (XL-PA) can be compared to the online gradient descent algorithm introduced in [START_REF] Zinkevich | Online convex programming and generalized infinitesimal gradient ascent[END_REF] where the learner tracks the gradient of his evolving objective and projects back to the problem's feasible set when needed. We did not take such an approach because projections are numerically unstable [START_REF] Cantrell | Modern mathematical methods for physicists and engineers[END_REF] and can become quite costly from a computational standpoint (the problem's constraints would have to be checked individually at every iteration). Nonetheless, the exponential approach of (XL-PA) has strong ties to the method of online mirror descent [START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF] which we discuss later.

2) The general case: The dynamic power allocation policy (XL-PA) concerns the case where the power-per-channel constraints (7b) can be absorbed in the total power constraint (7a). Otherwise, if P k < P for some channel k ∈ K (e.g.

if certain PUs have very low interference tolerance on their licensed channels), (XL-PA) cannot be employed "as is" because it does not respect the constraint p k ≤ P k . When this is the case, the analysis of Appendix B yields the modified policy:

y k (t) = y k (t -1) + v k (t), p k (t + 1) = P k 1 + exp(λ -ηt -1/2 y k ) -1 (XL-PA )
where λ > 0 is defined implicitly so that (7a) is satisfied:

P = k∈K P k 1 + exp(λ -ηt -1/2 y k ) -1 . ( 18
)
Just like (XL-PA), (XL-PA ) exhibits exponential sensitivity to the scores y k modulo a normalization factor corresponding to the constraints (7a) and (7b). Since the RHS of ( 18) is strictly decreasing in λ, it is then easy to calculate the value of λ itself, e.g. by performing a line search for e λ [START_REF] Cantrell | Modern mathematical methods for physicists and engineers[END_REF]. 2 We thus get:

Proposition 2. The policy (XL-PA ) leads to no regret. In particular, for every p 0 ∈ X 0 , the user's regret is bounded by

T -1 Reg T (p 0 ) ≤ O T -1/2 , ( 19
)
irrespective of the system's evolution over time.

Proof: See Appendix B.

Remark. We should note here that (XL-PA ) is not equivalent to (XL-PA) if P k ≥ P; instead, (XL-PA) should be viewed as a simpler alternative to (XL-PA ) that can be employed whenever the maximum power-per-channel constraints (7b) can be subsumed in the total power constraint (7a). For convenience, we will present our results in the simpler case P k ≥ P and we will rely on a series of remarks to translate these remarks to the regime P k < P (cf. Appendices A and B).

B. The MIMO Component: Signal Covariance Optimization

If the user's power allocation profile p = (p 1 , . . . , p K ) remains fixed throughout the transmission horizon, (ORM) boils down to the online signal covariance optimization problem: maximize Φ(Q; t),

subject to Q k 0, tr(Q k ) = 1, (OCOV)
where we now use the notation Φ(Q; t) to highlight the dependence of the user's transmission rate (5) on the normalized

covariance matrix Q = diag(Q 1 , . . . , Q K ) ∈ X + ≡ k D k .
A key challenge in (OCOV) is that any learning algorithm must respect the problem's (implicit) semidefiniteness constraints Q k 0. To that end, motivated by the analysis of [START_REF] Mertikopoulos | Matrix exponential learning: Distributed optimization in MIMO systems[END_REF] (see also the matrix regularization approach of [START_REF] Kakade | Regularization techniques for learning with matrices[END_REF]), we will consider the matrix exponential learning policy

Y k (t) = Y k (t -1) + V k (t), Q k (t + 1) = exp ηt -1/2 Y k (t) tr exp ηt -1/2 Y k (t) , (XL-COV)
where the matrix-valued gradient payoff V k is defined as:

V k = ∂Φ ∂Q * k = p k M k , (20)
and M k is given by [START_REF] Wang | Robust MIMO cognitive radio via game theory[END_REF]. Intuitively, (XL-COV) reinforces the spatial directions that peform well by increasing the corresponding eigenvalues while the t -1/2 factor keeps the eigenvalues of Q k from approaching zero too fast [START_REF] Kwon | A continuous-time approach to online optimization[END_REF].

Along these lines, our analysis in Appendix C yields:

Proposition 3. The dynamic transmit policy (XL-COV) leads to no regret in the online signal covariance optimization problem (OCOV). In particular, for every Q 0 ∈ X + ≡ k D k , and irrespective of the system's evolution over time, we have:

1 T Reg T (Q 0 ) ≤ 1 √ T       K k=1 log m k η + 4P 2 M 2 η       , (21)
where m k is the number of spatial degrees of freedom left open by the constraint (7c).

IV. Learning in the Full MIMO-OFDM Problem

A. Augmented Exponential Learning

Based on the analysis of the previous section, we derive here a dynamic no-regret policy for the full MIMO-OFDM problem (ORM). Working for simplicity with the special case P k ≥ P, (XL-PA) and (XL-COV) yield the dynamic transmit policy:

Algorithm 1 Augmented Exponential Learning (AXL)

Parameter: η > 0.

Initialize: t ← 0; channel scores y k ← 0, Y k ← 0. Repeat t ← t + 1; foreach channel k ∈ K do set              p k ← P exp ηt -1/2 y k exp ηt -1/2 y ; Q k ← exp ηt -1/2 Y k tr exp ηt -1/2 Y k ; foreach channel k ∈ K do measure M k ← H † k I + p k H k Q k H † k -1 H k ;
update scores:

             y k ← y k + P tr[M k Q k ]; Y k ← Y k + p k M k ;
until transmission ends.

The augmented exponential learning (AXL) algorithm above will be our main focus, so a few remarks are in order:

Remark 1. From an implementation point of view, AXL has the following desirable properties:

(P1) It is distributed: each SU only needs to update his individual transmit policy using local CSI (the matrices H k ).

(P2) It is asynchronous: there is no need for a global update timer to synchronize the system's SUs.

(P3) It is stateless: the SUs do not need to know the state of the system (e.g. the network's topology), and/or be aware of each other's actions.

(P4) It is reinforcing: the SUs tend to increase their unilateral transmission rates.

Remark 2. If the maximum power-per-channel constraints imposed on the network's SUs do not satisfy the condition P k ≥ P for all k ∈ K, the power update step of AXL must be modified: specifically, the exponential allocation rule p k ← P exp(ηt -1/2 y k ) exp(ηt -1/2 y ) must be replaced by the update rule of (XL-PA ), i.e. by setting p k ← P k 1 + exp(λ -ηt -1/2 y k ) -1 . To simplify our presentation, we will keep the assumption P k ≥ P with the implicit understanding that if P k < P for some k ∈ K, then it is the modified version of AXL that should be used instead.

With all this in mind, our main result is that the AXL algorithm leads to no regret if P k ≥ P for all channels:

Theorem 1. The adaptive transmit policy generated by AXL leads to no regret in the online rate maximization problem (ORM). In particular, for every fixed transmit profile P 0 ∈ X, and independently of how the system's rate function [START_REF] Haykin | Cognitive radio: Brain-empowered wireless communications[END_REF] evolves over time, the user's regret is bounded by:

1 T Reg T (P 0 ) ≤ 1 √ T       log K + K k=1 log m k η + 4P 2 M 2 η       , ( 22
)
where M is given by ( 12) and m k is the number of spatial dimensions that are left open to SUs by the constraint (7c).

Proof: See Appendices D and E.

Remark 1. As we already explained, if P k < P for some k ∈ K, the power update step in the AXL algorithm should be replaced by the power allocation rule (XL-PA ). In this case, AXL still guarantees an O(T -1/2 ) regret bound but the exact expression is more complicated (see Appendix B for the details).

Remark 2. The proof of Theorem 1 relies on a deep connection between (XL-PA) and (XL-COV) with the Gibbs-Shannon and von Neumann entropy functions respectively. In fact, as we shall see in Appendices A-B, our approach is intimately related to the Hessian-Riemannian optimization method of [START_REF] Alvarez | Hessian Riemannian gradient flows in convex programming[END_REF] and the online mirror descent techniques of [START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF][START_REF] Kakade | Regularization techniques for learning with matrices[END_REF]. Unfortunately, a full description of these methods requires the introduction of significant technical apparatus, so we will not discuss them at length; for a detailed account, the reader is instead referred to [START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF][START_REF] Kwon | A continuous-time approach to online optimization[END_REF].

Remark 3. It should also be noted that the bound ( 22) is not the sum of the bounds ( 17) and ( 21). As we show in Appendices D and E, the reason for this is that Theorem 1 is not a corollary of Propositions 1 and 3 but, rather, a combination of these two independent results.

Remark 4. In practice, the learning parameter η of the AXL algorithm can be tuned freely by the user. As such, if the user can estimate ahead of time the quantity M (which can be seen as an effective bound on the gradient matrices M k over time), η can be chosen so as to optimize the regret guarantee ( 22) -thus leading to lower regret levels faster.

Specifically, some calculations along the lines of [START_REF] Kwon | A continuous-time approach to online optimization[END_REF] show that the optimal choice of η which minimizes the RHS of ( 22) is:

η = 1 2 PM log K + k log m k 1/2 , (23)
which then leads to the optimized regret guarantee:

Reg T (P 0 ) ≤ 4PM log K + k log m k 1/2 T 1/2 . ( 24
)
This bound resembles the bound derived in [START_REF] Kakade | Regularization techniques for learning with matrices[END_REF] for learning processes that stop after a predetermined number of steps; that being said (and in contrast to Theorem 1), unless some sort of "doubling correction" is used [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF], the method proposed in [START_REF] Kakade | Regularization techniques for learning with matrices[END_REF] may lead to positive regret in an infinite horizon setting (such as the one we are considering here).

On the other hand, this also shows that if the user can estimate his transmission horizon in advance (instead of having an infinite backlog of data to transmit), then he can use AXL with constant parameter η given by ( 23) and still enjoy the optimal regret guarantee (24).

Remark 5. Finally, we note that the optimal bound (24) is asymptotically tight with respect to T but not necessarily with respect to the dimensionality of the problem. In particular, the analysis of [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF][START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF] shows that the best bound that can be guaranteed against an adversarial nature is O( √ T ); furthermore, if the state space of the problem is a simplex of dimension K, the tightest possible bound is O(log K) [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF]. In this way, the log K factor of ( 24) is tight; we conjecture that the same holds for the log m k factors because the covariance spectrahedrons D k are simply the product of a simplex with dimension m k with the space of unitary matrices. At any rate, the bound (24) only tightens against an adversarial nature, so, in practical situations, we expect the user's regret to decay much more rapidly (cf. the numerical simulations of Section V).

B. Learning with Imperfect Channel State Information

In practice, a major challenge occurs if the user does not have perfect CSI with which to calculate the matrix gradients [START_REF] Wang | Robust MIMO cognitive radio via game theory[END_REF] that are needed to run the AXL algorithm. To wit, since these gradients are determined by the effective channel matrices H k = W -1/2 k H k , imperfect measurements of the actual channel matrices H k or of the multi-user interference-plus-noise covariance matrices W k would invariably interfere with each update cycle. Accordingly, our aim in this section is to study the robustness of AXL in the presence of measurement errors.

To account for as wide a range of errors as possible, we will assume that at each update period t = 1, 2, . . . , the user can only observe a noisy estimate

Mk (t) = M k (t) + Ξ k (t) (25)
of M k (t), where the noise process Ξ k (t) represents a random and unbiased observational error (not necessarily i.i.d.).

Formally:

Assumption 1. We assume that the observation error Ξ k is:

1) Bounded: Ξ k (t) ≤ Σ (a.s.) for some Σ > 0 and for all t.

2) Unbiased: E Ξ k (t)|F t-1 = 0 where F = {F t } t≥1 denotes the history of the user's choices.

Remarkably, as long as there is no systematic bias in the user's measurements, the AXL algorithm still leads to no regret, even in the presence of arbitrarily large observation errors:

Theorem 2. The AXL algorithm with noisy observations Mk of the form (25) leads to no regret (a.s.). Specifically, if Ξ k ≤ Σ, then, for all P 0 ∈ X and for all z > 0:

(i) The user's expected regret is bounded by:

E T -1 Reg T (P 0 ) ≤ RT -1/2 . ( 26
)
(ii) The user's realized regret is bounded by the perfect CSI guarantee of AXL with exponentially high probability:

P 1 T Reg T (P 0 ) ≤ R √ T + z ≥ 1 -exp - z 2 T 2D 2 Σ 2 , ( 27
)
where D > 0 is a constant and R is the deterministic guarantee [START_REF] Mertikopoulos | Matrix exponential learning: Distributed optimization in MIMO systems[END_REF] of AXL under perfect CSI, viz.:

R = η -1 • log K + k log m k + 4P 2 M 2 η. ( 28
)
Theorem 2 (proven in Appendix F) shows that AXL guarantees an O(T -1/2 ) bound on the user's regret with high probability, even under measurement errors of arbitrarily high magnitude. Accordingly, a few remarks are in order:

Remark 1. The first-and second-order statistics of the measured gradients Mk play different roles in the presence of imperfect CSI: the expected value E Mk = M k of Mk controls the expected regret guarantee of AXL via [START_REF] Huang | Cognitive Radio Networks: Architectures, Protocols, and Standards[END_REF], whereas the variance Var Mk = E Ξ k 2 of Mk controls the deviations of the regret from its "bulk" behavior -but has no impact on the expected regret of AXL.

Remark 2. Note also that Theorem 1 is recovered by [START_REF] Stevenson | IEEE 802.22: The first cognitive radio wireless regional area network standard[END_REF] in the deterministic limit Σ → 0 + : the probability that the user's regret exceeds the determinstic guarantee R/ √ T converges uniformly to 0 as Σ → 0 + .

V. Numerical Results

To validate the predictions of Section IV for the AXL algorithm, we conducted extensive numerical simulations from which we illustrate here a selection of the most representative scenarios -though the observations made below remain valid in most typical mobile wireless environments.

In Fig. 1, we simulated a network consisting of 10 PUs and 40 SUs, all equipped with m k = 3 transmit/receive antennas, and communicating over K = 256 orthogonal subcarriers with a base frequency of ν = 2 GHz. Both the PUs and the SUs were assumed to be mobile with a speed between 3 and 5 km/h (pedestrian movement), and the channel matrices H qs k of (2) were modeled after the well-known Jakes model for Rayleigh fading [START_REF] Calcev | A wideband spatial channel model for system-wide simulations[END_REF]. For simplicity, we assumed that the PUs were going online and offline following a Poisson process (representing exponential arrivals with exponential call times), while the simulated SUs employed the AXL algorithm with η = 1 and an update epoch of δ = 5 ms. 3 We then calculated the maximum regret induced by the AXL for every SU with respect to the uniform transmit profile (where power is spread equally across antennas and frequency bands) and all possible combinations of spreading power uniformly across subcarriers while keeping one or two transmit dimensions closed (we plotted the regret for only 7 SUs in order to reduce graphical clutter). The results of these simulations were plotted in Fig. 1(a): as predicted by Theorem 1, AXL leads to no regret and falls below the no-regret threshold within a few epochs, indicating that its average performance is strictly better than any of the benchmark transmit profiles.

For comparison purposes, we also simulated the same scenario but with the SUs employing a randomized transmit policy. In particular, motivated by [START_REF] Palomar | Uniform power allocation in MIMO channels: a game-theoretic approach[END_REF], we simulated the randomized transmit policy:

Q k (t + 1) = (1 -r)Q k (t) + rR k (t), Q k (0) = m -1 k I, (29)
where the matrix R k (t) is drawn uniformly from the spectrahedron D k of m k × m k positive-definite matrices with unit trace, and r ∈ [0, 1] is a discount parameter interpolating between the uniform distribution Q k ∝ I for r = 0 and the completely random policy R k for r = 1 (in our simulations, we took r = 0.9). Even though this dynamic transmit policy is sampling the state space essentially uniformly for large values of r, Fig. 1(b) shows that several SUs end up having positive regret. We thus see that the no-regret property of AXL is not spurious artifact of exploring the problem's state space in a uniform way, but it is inextricably tied to the underlying learning mechanism.

The negative-regret results of Fig. 1 also suggest that the transmission rate achieved by a given SU is close to the user's (evolving) maximum possible rate given the transmit profiles of every other user. To test this hypothesis, we plotted in Fig. 2 the achieved data rate of a SU employing the AXL algorithm along with the user's maximum achievable data rate and the rates achieved by the uniform policy and the randomized policy ( 29 We see there that AXL adapts to the changing channel conditions and tracks the user's maximum achievable rate remarkably well, in stark contrast to the uniform and randomized transmit policies. 4Finally, to assess the performance of the AXL algorithm with respect to the users' sum rate under successive interference cancellation (SIC) and the robustness of AXL under imperfect CSI, we simulated in Fig. 3 a static multiuser MIMO multiple access channel consisting of a wireless base receiver with 5 antennas, 10 PUs and 40 SUs (each with a random number of transmit antennas picked uniformly between 2 and 6). Each user's channel matrix H qr k ≡ H q k was drawn from a complex Gaussian distribution at the outset of the transmission (but remained static once picked), and we then ran the AXL algorithm with η = 1. The algorithm's performance over time was then assessed by plotting the efficiency ratio

eff(t) = Ψ(t) -Ψ min Ψ max -Ψ min , (30)
where Ψ(t) denotes the users' sum rate at the t-th iteration of the algorithm, and Ψ max (resp. Ψ min ) is the maximum (resp. minimum) value of Ψ over the set of feasible transmit profiles. 5 For comparison purposes, we also plotted the efficiency ratio achieved by water-filling methods -namely iterative water-filling (IWF) and simultaneous water-filling (SWF) [START_REF] Scutari | Simultaneous iterative water-filling for Gaussian frequency-selective interference channels[END_REF]. Remarkably, when the users have perfect CSI, the AXL policy achieves the system's maximum sum rate within 3-4 iterations; by contrast, SWF fails to converge altogether while the convergence time of IWF scales linearly with the number of SUs (Fig. 3(a)). On the other hand, in the presence of imperfect CSI (modeled as zero-mean i.i.d.

Gaussian pertrubations to the gradient matrices M k with relative magnitude of 50%), AXL still achieves the system's sum capacity (albeit at a slower rate) whereas water-filling methods offer no significant advantage over the user's initial transmit profile (cf. Fig. 3(b)).

Worst Case Regret

No Regret Threshold

VI. Conclusions

In this paper, we introduced an adaptive transmit policy for MIMO-OFDM cognitive radio systems that evolve dynamically over time as a function of changing user and environmental conditions. Drawing on the method of matrix exponential learning [START_REF] Mertikopoulos | Matrix exponential learning: Distributed optimization in MIMO systems[END_REF] and online mirror descent [START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF][START_REF] Kakade | Regularization techniques for learning with matrices[END_REF], we derived an augmented exponential learning (AXL) scheme which leads to no regret: for every SU, the proposed transmit policy performs asymptotically as well as the best fixed transmit profile over the entire transmission horizon, and irrespective of how the system evolves over time. In fact, this learning scheme is closely aligned to the direction of change of the users' data rate function, so the system's SUs are able to track their individual optimum transmit profile even under rapidly changing conditions. Importantly, the implementation of the proposed algorithm requires only local CSI; moreover, the algorithm retaints its no-regret properties even in the case of imperfect CSI (with arbitrarily large measurement errors) and significantly outperforms classical water-filling algorithms (where the use of perfect CSI is critical).

To a large extent, our dynamic transmit policy owes its no-regret properties to an associated entropy function (for instance, the von Neumann quantum entropy for the problem's signal covariance component). As a result, by choosing a proper entropy-like kernel (e.g. as in [START_REF] Alvarez | Hessian Riemannian gradient flows in convex programming[END_REF]), we can examine significantly more general situations, including for example pricing and/or energy-awareness constraints.

Finally, we should mention here that when the environment undergoes rapid changes, there are other regret notions which are more suited to adaptability (such as the adaptive regret measure of [START_REF] Hazan | Efficient learning algorithms for changing environments[END_REF]). Studying the performance of augmented exponential learning with respect to different regret valuations lies beyond the scope of the current paper, but we intend to explore this direction in future work.

A. Online Power Allocation: the Case P k ≥ P.

To begin with, note that the exponential mapping of (XL-PA) may be characterized as the solution of the convex program: maximize y|qh(q), subject to q k ≥ 0,

k q k = 1, (31)
where y|q denotes the bilinear pairing y|q = k q k y k and h(q) = k q k log q k denotes the Gibbs-Shannon entropy on the simplex ∆ ≡ ∆(K) spanned by K. More precisely, we have the following classical result [START_REF] Rockafellar | Convex Analysis[END_REF]Chapter 25]:

Lemma 1. For every y ∈ R K , the problem (31) admits the unique solution G(y) with G k (y) = e y k e y .

Consider now the following continuous-time variant of (XL-PA) for t ≥ 0:

ẏk = ∂Φ ∂q k , q(t) = G (γ(t)y(t)) , (32)
where γ(t) = min{η, ηt -1/2 }; moreover, define the cumulative continuous-time regret with respect to some fixed q 0 ∈ ∆ as

Reg c T (q 0 ) = T 0 Φ(q 0 ; t) -Φ(q(t); t) dt, (33)
where Φ(•; t), is a piecewise continuous stream of rate functions and the index c in Reg c T indicates that we are working in continuous time. We then have: Proposition 4. The cumulative regret generated by the learning scheme [START_REF] Zinkevich | Online convex programming and generalized infinitesimal gradient ascent[END_REF] satisfies Reg c T (q 0 ) ≤ η -1 log K • √ T for all q 0 ∈ ∆.

Proof: Let h * (y) denote the convex conjugate of h, i.e. h * (y) = max q∈∆ { y|qh(q)} = y|G(y)h(G(y)).

Moreover, set γ(t) = min{ηt -1/2 , η} and let q(t) be defined as in [START_REF] Zinkevich | Online convex programming and generalized infinitesimal gradient ascent[END_REF] with v(t) = ẏ(t) = ∇ q(t) Φ(q(t); t). By Lemma 1, we will have h * (γy) = log e γy and hence:

d dt h * (γy) = k∈K ∂h * ∂y k γy (γy k + γ ẏk ) = γ y|q + γ v|q , (34)
where we used [START_REF] Zinkevich | Online convex programming and generalized infinitesimal gradient ascent[END_REF] and the fact that ∇ y h * (y) = G(y). By isolating v|q and integrating by parts, we then get:

T 0 v|q dt = h * (γ(T )y(T )) γ(T ) - h * (γ(0)y(0)) γ(0) + T 0 γ γ 2 h * (γy) dt - T 0 γ γ y|q dt = h * (γ(T )y(T )) γ(T ) - h * (0) γ(0) - 0 γ γ 2 h(G(γy)) dt, (35)
where the last step follows from the fact that q = G(γy) and the defining relation h * (γy) = γy|G(γy)h(G(γy)).

Then, given that the minimum of h over ∆ islog K, we also have h * (0) = -h min = log K; thus, with γ ≤ 0, [START_REF] Kwon | A continuous-time approach to online optimization[END_REF] becomes:

T 0 v|q dt ≥ h * (γ(T )y(T )) γ(T ) - h * (0) γ(0) + h * (0) T 0 γ γ 2 dt ≥ γ(T )y(T )|q 0 -h(q 0 ) γ(T ) - log K γ(T ) ≥ y(T )|q 0 - log K η √ T , (36)
where we used the fact that h * (γy) ≥ γy|q 0h(q 0 ) for all q 0 ∈ ∆ in the second line and that h ≤ 0 in the last step.

With Φ concave over ∆, we will also have Φ(q 0 ; t) -Φ(q(t); t) ≤ ∇ q(t) Φ q 0q(t) = v(t)|q 0q(t) ; hence, by [START_REF] Alvarez | Hessian Riemannian gradient flows in convex programming[END_REF], we get:

Reg c T (q 0 ) ≤ T 0 v|q 0 -q dt ≤ log K η √ T , (37)
and our proof is complete.

B. Online Power Allocation: The General

If P k < P for some k, we still obtain a no-regret power allocation policy if we use the modified entropy function

h(p) = k p k log p k + (P k -p k ) log(P k -p k )
, and define the modified Gibbs map:

G 0 (y) = arg max p∈X 0 y|p -h 0 (p) . (38)
Specifically, consider the following modified version of (32):

ẏk = ∂Φ ∂p k , p(t) = G 0 (γ(t)y(t)) , (39)
where Φ(•; t) is a continuous stream of rate functions of the form (5) and γ = min{η, ηt -1/2 }. We then have:

Proposition 5. The learning scheme (39) leads to no regret in continuous time:

Reg c T (p 0 ) ≤ O( √ T ) for all p 0 ∈ X 0 .
Proof: As in the proof of Proposition 4, let h * 0 (y) = max p∈X 0 { y|ph 0 (p)} = y|G 0 (y)h 0 (G 0 (y)) be the convex conjugate of h 0 (p). Since the derivative of h 0 blows up to infinity at the boundary of X 0 , the unique solution to the maximization problem defining G 0 lies at the interior of X 0 . The Karush-Kuhn-Tucker (KKT) conditions thus give y k -∂h 0 ∂p k = λ, where λ is the Lagrange multiplier for the equality constraint p = P. We will then also have

∂h * 0 ∂y k = G 0,k (y) + K =1 y ∂ ∂y k G 0, (y) -K =1 ∂h 0 ∂p ∂ ∂y k G 0, (y) = G 0,k (y)
, where, in the last step, we used the fact that K =1 G 0, (y) = P (so K =1 ∂ y k G 0, = 0 for all k). Thus, letting v(t) = ∇ p Φ(p; t) so that y(t) = t 0 v(s) ds and p(t) = G 0 (γ(t)y(t)), we obtain the basic identity:

d dt h * 0 (γy) = k∈K ∂h * 0 ∂y k γy (γy k + γ ẏk ) = γ y|p + γ v|p , (40)
and the rest of the proof follows as in the case of Prop. 4.

if Y = diag(Y 1 , . . . , Y K ) with Y k Hermitian, we will have h * + (Y) = max Q∈X + tr YQ -h(Q) = k h * k (Y k ) = k log tr exp(Y k ) . Accordingly, if we let V k (t) = ∂ Q * k Φ(Q; t), we get: d dt h * + (γY) = K k=1 tr exp(γY k ) -1 d dt tr exp(γY k ) = K k=1 tr exp(γY k ) -1 tr γY k + γ Ẏk exp(Y k ) γ tr YQ + γ tr VQ (44)
where we set V = diag(V 1 , . . . , V K ). Following the same steps as in the proof of Proposition 4, we then obtain:

T 0 tr VQ dt = h * + (γ(T )Y(T )) γ(T ) - h * + (0) γ(0) - T 0 γ γ 2 h + (Q) dt, (45)
The minimum of h + over

X + = k D k is just -k log m k , so we also have h * (0) = -min Q∈X + h + (Q) = k log m k ;
then, with γ ≤ 0, (45) becomes:

T 0 tr VQ dt ≥ h * + (γ(T )Y(T )) γ(T ) - h * (0) γ(0) + h * + (0) T 0 γ γ 2 dt ≥ tr γ(T )Y(T )Q 0 -h + (Q 0 ) γ(T ) - K k=1 log m k γ(T ) ≥ tr Y(T )Q 0 - K k=1 log m k η √ T , (46)
where we used the fact that h * + (γY) ≥ tr γYQ 0h + (Q 0 ) for all Q 0 ∈ X + in the second line and the fact that h + ≤ 0 in the last step. Since Φ is concave in Q and V = ∇ Q * Φ, the rest of the proof follows in the same way as that of Proposition 4.

D. The Full MIMO-OFDM Problem

Our final step in this continuous-time setting will be to establish the no-regret properties of the following continuoustime variant of the AXL algorithm for P k ≥ P:

ẏk = ∂Φ ∂q k , Ẏk = ∂Φ ∂Q * k , q k = exp(γy k ) K =1 exp(γy ) , Q k = exp(γY k ) tr exp(γY k ) , (47)
with γ = min{η, ηt -1/2 } as usual. Without further ado, we have: Proposition 7. If P k ≥ P for all k ∈ K, then, for all P 0 ∈ X, the cumulative regret generated by (47) will satisfy

Reg c T (P 0 ) ≤ η -1 √ T log K + K k=1 log m k .
Proof: Recall that any P ∈ X may be decomposed as

P = diag(p 1 Q 1 , . . . , p K Q K ) with p = (p 1 , . . . , p K ) ∈ X 0 and Q = diag(Q 1 , . . . , Q K ) ∈ X + ≡ k D k .
Then, using the normalized power allocation vector q = p/P ∈ ∆ for convenience, let

H(q, Q) = h(q) + h + (Q) = K k=1 q k log q k + tr(Q k log Q k ) and consider the associated Legendre-Fenchel problem: maximize y|q + tr[YQ] -H(q, Q), subject to q ∈ ∆, Q ∈ k D k . (48)
Clearly, (48) may be decomposed as a sum of ( 31) and ( 42), so each component of the solution of (48) is given by Lemmas 1 and 2 respectively; likewise, the convex conjugate of H will be H * (y, Y) = h * (y) + h * + (Y), with h * and h * + defined as before. Our claim is then obtained by following the same steps as in the proofs of Propositions 4 and 6.

E. The Descent to Discrete Time

In this appendix, we to derive the no-regret properties of the discrete-time policies (XL-PA), (XL-COV) and of the AXL algorithm (Propositions 1, 3 and Theorem 1 respectively) by means of a comparison technique introduced by Sorin [START_REF] Sorin | Exponential weight algorithm in continuous time[END_REF] and developed further by J. Kwon and one of the authors [START_REF] Kwon | A continuous-time approach to online optimization[END_REF]. Specifically, we have:

Lemma 3.
Let C be a compact convex set in R N , let v(t) be a sequence of payoff vectors in R N with v(t) ≤ V in the uniform norm of R N (t = 1, 2 . . . ), and consider the sequence of play

x(t + 1) = Q ηt -1/2 t s=1 v(s) where Q : R N → C is C-Lipschitz with respect to the L 1 norm on C. Moreover, letting v c (t) = v( t ) be a piecewise constant interpolation of v(t) for t ∈ [1, +∞), consider the continuous-time process x c (t) = Q γ(t) t 0 v c (s) ds with γ(t) = min{ηt -1/2 ,
η}, and assume that it guarantees the regret bound:

T 0 v c (t)|x 0 -x c (t) dt ≤ R(T ) √ T for all x 0 ∈ X + . (49)
Then, for all x 0 ∈ A, the discrete-time sequence x(t) guarantees

T t=1 v(t)|x 0 -x(t) ≤ √ T R(T ) + 4CV 2 η . (50)
Proof: By assumption, if we set y(t) = t 0 v c (s) ds, we have x c (t) = Q(γ(t)y(t)) = x(t + 1) whenever t is a positive integer. Hence, for every integer T ≥ 1, we have

) | ≤ v c (t) ∞ • x c (t) -x c ( t ) 1 ≤ V x c (t) -x c ( t ) 1 ≤
V Q(γ(t)y(t)) -Q(γ( t )y( t )) 1 ≤ CV γ(t)y(t) -γ( t )y( t ) ∞ . The last term may then be rewritten as:

γ(t)y(t) -γ( t )y( t ) ∞ =
Recalling that γ(t) = min{η, ηt -1/2 }, this last integral is equal to ηt if t ∈ [0, 1] and 3η t 1/2t 1/2 otherwise. Thus, combining the above inequalities, we obtain: With this comparison at hand, the analysis of the previous sections yields:

Proof of Proposition 1: Note first that v k = ∂Φ ∂q k = P tr M k Q k , so the payoff vectors v of ( 16) are bounded in the uniform norm of R K by PM -cf. [START_REF] Nie | Adaptive channel allocation spectrum etiquette for cognitive radio networks[END_REF]. Given that the Lipschitz constant of the exponential mapping G(y) of ( 1) is C = 1 [START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF], the proposition follows by combining the continuous-time bound of Proposition 4 with Lemma 3.

Proof of Proposition 2: Note first that the modified Gibbs map of (38) simply represents the power allocation policy of (XL-PA ): indeed, by the KKT conditions for the maximization problem defining G 0 , we will have:

p k P k -p k = e λ-y k =⇒ p k = P k e y k e λ + e y k , (55)
so, given that the power vector p satisfies the total power constraint (7a), the Lagrange multiplier λ must satisfy the condition P = k p k = k P k (1 + e λ-y k ) -1 . Comparing this last equation with [START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF], we conclude that p k will be given by the power update step of (XL-PA ) with y replaced by γy, so our claim follows by combining Proposition 5 with Lemma 3. where the inequality follows from the concavity of Φ. Since P(t) is generated by the sequence of matrix payoffs M(t), the first term of this expression is simply the regret generated by P(t) against M(t), so we have As for the second term, it is easy to see that the process V(t) = tr Ξ(t) where D = max{ P 0 -P 1 : P 0 , P ∈ X} denotes the L 1 -diameter of X.

Proof of

The bound ( 26) is thus obtained by taking the expectation of Reg T (P 0 ) and using the zero-mean property of V.

Similarly, the fact that P(t) generates no regret almost surely (and not only in expectation) follows by noting that T -1 T t=1 V(t) → 0 as a consequence of the strong law of large numbers for martingale differences [START_REF] Hall | Martingale Limit Theory and Its Application, ser. Probability and Mathematical Statistics[END_REF]Theorem 2.18]. Finally, for the large deviations bounds ( 27), (56) yields:

P 1 T Reg T (P 0 ) ≥ R √ T + z ≤ P T t=1 |V(t)| ≥ T z . (58)
However, with Ξ ≤ Σ, Azuma's inequality [START_REF] Azuma | Weighted sums of certain dependent random variables[END_REF] yields P T t=1 V(t) ≥ T z ≤ exp -

T 2 z 2 2 T t=1 ess sup |V(t)| 2 ≤ exp -T z 2
2Σ 2 D 2 , and our claim follows.

  ); to test different fading conditions, we simulated average user velocities of v = 5 m/s and v = 15 m/s (Figs. 2(a) and 2(b) respectively).

Fig. 1 .

 1 Fig. 1. The long-term regret induced by augmented exponential learning and a random sampling transmit policy (Figs 1(a) and 1(b) respectively)for different users (see text for details). In tune with Theorem 1, AXL quickly falls below the no-regret threshold whereas the randomized policy (29) leads to positive regret for several users (in both figures the dashed "worst-case regret" curve represents the regret guarantee[START_REF] Mertikopoulos | Matrix exponential learning: Distributed optimization in MIMO systems[END_REF] of the AXL algorithm).

Fig. 2 .

 2 Fig.2. Data rates achieved by AXL in a changing environment with different fading velocities: the dynamic transmit policy induced by the AXL algorithm allows users to track their maximum achievable transmission rate remarkably well even under rapidly changing channel conditions.

  time with measurement errors (b) Learning with an average relative error level of 50%.

Fig. 3 .

 3 Fig. 3. Convergence and robustness of AXL with imperfect CSI in a MIMO MAC system with 10 PUs and 25 SUs: in contrast to water-filling methods, AXL attains the channel's sum capacity in the presence of very high measurement errors.

T

  0 v c (t)|x c (t) dt -T t=1 v(t)|x(t) = T 0 v c (t)|x c (t) dt -T 0 v( t )|x( t ) dt = T 0 v c (t)|x c (t)x c ( t )dt where we used the fact that x c ( t ) = x( t ) in the second step. On the other hand, Hölder's inequality gives | v c (t)|x c (t)x c ( t

  s)sγ(s)) ds.

T 0 v

 0 c (t)|x c (t)x c ( t ) dt ≤ CV 2 the definition of v c (t), we finally obtain T t=1 v(t)|x 0x(t) = T 0 v c (t)|x 0x c (t) dt + T 0 v c (t)|x c (t)x c ( t ) dt ≤ R(T )

Proposition 3 :

 3 The matrix payoffsV k = ∂Φ ∂Q * k = p k M k satify V k ≤ PM by[START_REF] Nie | Adaptive channel allocation spectrum etiquette for cognitive radio networks[END_REF]. Moreover, the von Neumann entropy h + is 1-strongly convex with respect to the L 1 norm, so the matrix exponential mappingY → Q Y = exp(Y) tr exp(Y) is 1-Lipschitz -see e.g. [23]. Our claim then follows by combining the continuous-time bound of Proposition 6 with Lemma 3. Proof of Theorem 1: As in the proofs of Propositions 1 and 3, the map (y, Y) → (q, Q) ∈ ∆ × k D k of (47) is 1-Lipschitz and the payoffs (v, V k ) are bounded by PM in the uniform norm of R K × k C m k ×m k . The theorem then follows by combining the continuous-time bound of Proposition 7 with Lemma 3.F. Learning with Imperfect CSIProof of Theorem 2: Let P(t) = diag (P 1 (t), . . . , P k (t)) ∈ X be the sequence of transmit profiles generated by the AXL algorithm with noisy observations M = M + Ξ. Then, for every P 0 ∈ X, we have:Reg T (P 0 ) ≤ T t=1tr ∇Φ(P(t)) • P 0 -P(t) = T t=1 tr M(t) • P 0 -P(t) -T t=1 tr Ξ(t) • P 0 -P(t) , (56)

  t) • P 0 -P(t) ≤ R √ T(57)by Theorem 1 (or, more accurately, by combining (36) and (46) with Lemma 3).

  Ξ(t)|F t-1 • P(t) -P 0 = 0. Moreover, with Ξ ≤ Σ, we will also have|V(t)| ≤ Ξ(t) • P 0 -P(t) 1 ≤ Σ • D,

• P(t) -P 0 is a martingale difference: indeed, since P(t) is fully determined by M(1), . . . , M(t -1), we get

E[V(t)|F t-1 ] = E tr Ξ(t) • P(t) -P 0 |F t-1 = tr E

See also[START_REF] Mertikopoulos | Adaptive spectrum management in MIMO-OFDM cognitive radio: An exponential learning approach[END_REF] for a closed-form expression of (XL-PA ) based on a modified version of the replicator equation of evolutionary game theory.

We did not optimize the choice of η because we wanted to focus on the case where the network's SUs have minimal information.

If the user's velocity becomes exceedingly high, the quality of this tracking may deteriorate as a result of the channel's extreme variability; even in this case however, AXL is guaranteed to perform at least as well as the best fixed transmit profile in hindsight.

The reason for using this ratio was to eliminate scaling artifacts arising e.g. from the sum rate taking values in a narrow band close to its maximum value.

This research was supported in part by the European Commission in the framework of the FP7 Network of Excellence in Wireless COMmunications NEWCOM# (contract no. 318306), by the French National Research Agency projects NETLEARN (ANR-13-INFR-004) and GAGA (ANR-13-JS01-0004-01), and by ENSEA, Cergy-Pontoise, France. Part of this work was presented at the 7th International Conference on Performance Evaluation and Tools (ValueTools 2013), Turin, Italy, Dec. 2013. . Mertikopoulos is with the French National Center for Scientific Research (CNRS)

Appendix Technical Proofs

Our proof approach relies on a technique introduced by Sorin [START_REF] Sorin | Exponential weight algorithm in continuous time[END_REF] and recently extended by J. Kwon and one of the authors to more general online mirror descent methods [START_REF] Kwon | A continuous-time approach to online optimization[END_REF]. First, we will establish the no-regret property of augmented exponential learning in continuous time; subsequently, we derive the corresponding discrete-time result by estimating the difference between the continuous-and discrete-time processes.

C. Online Signal Covariance Optimization

For the MIMO component (OCOV) of (ORM) we will consider the continuous-time scheme:

where, as before, γ = min{η, ηt -1/2 }. Then, with the user's regret defined as in [START_REF] Cantrell | Modern mathematical methods for physicists and engineers[END_REF], we get: Proposition 6. The cumulative regret generated by the continuous-time learning scheme (41

To prove Proposition 6, we first show that the matrix exponential of ( 21) solves the semidefinite problem:

where Y is a Hermitian matrix and h Accordingly, the convex conjugate h * + of h + is:

Proof: To begin with, let A(Y, Q) = tr YQ]h + (Q) denote the objective of the problem [START_REF] Azuma | Weighted sums of certain dependent random variables[END_REF], and let Z = {A ∈ C m×m : A † = A, tr(A) = 0} be the space of tangent directions to D. Then, if {q j , u j } m j=1 is an eigen-decomposition of Q + tZ for Q ∈ D • and Z ∈ Z, we will have A(Y, Q + tZ) = tr[YQ] + tr[YZ] tj q j log q j . Hence, the

qk log q k where we have used the fact that j q j = 0 (recall that j q j = tr(Q + tZ) = 1 for all t such that Q + tZ ∈ D • ). However, differentiating the defining relation (Q + tZ)u j = q j u j with respect to t gives Zu j + (Q + tZ) u j = q j u j + q j u j , so, after multiplying from the left by u † j , we get q j = u † j Zu j + u † j (Q + tZ) u jq j u † j u j = u † j Zu j . Summing over j gives j q j log q j = j u † j Zu j log q j = tr[Z log Q]; then, by substituting in the previous expression for

By standard convex-analytic arguments, it follows that [START_REF] Azuma | Weighted sums of certain dependent random variables[END_REF] Armed with this characterization, we now get: