A Survey on Applications of Model-Free Strategy Learning in Cognitive Wireless Networks
---
paper_title: Cognitive radio: brain-empowered wireless communications

paper_content:

Cognitive radio is viewed as a novel approach for improving the utilization of a precious natural resource: the radio electromagnetic spectrum. The cognitive radio, built on a software-defined radio, is defined as an intelligent wireless communication system that is aware of its environment and uses the methodology of understanding-by-building to learn from the environment and adapt to statistical variations in the input stimuli, with two primary objectives in mind: /spl middot/ highly reliable communication whenever and wherever needed; /spl middot/ efficient utilization of the radio spectrum. Following the discussion of interference temperature as a new metric for the quantification and management of interference, the paper addresses three fundamental cognitive tasks. 1) Radio-scene analysis. 2) Channel-state estimation and predictive modeling. 3) Transmit-power control and dynamic spectrum management. This work also discusses the emergent behavior of cognitive radio.
---
paper_title: A Context Driven Architecture for Cognitive Radio Nodes

paper_content:

A cognitive radio (CR), in its generic form, needs to be highly flexible and adaptive while desirably hiding its complexities from users and system programmers. For the autonomic management the CR needs to be aware of the `self' and the `world' around it. Embedded intelligence with cognitive and collaborative adaptations require innovative techniques for managing the functionality of the device. Complexity of the cognitive processes involved demand for formal methods for run time evaluations and verification. In this paper we propose a generic architecture for a cognitive node with a context driven approach which incorporates some formalisms including context spaces, ontology, process algebra to represent and manipulate various cognitive processes managing the cognitive node functionality.
---
paper_title: Advances in cognitive radio networks: A survey

paper_content:

With the rapid deployment of new wireless devices and applications, the last decade has witnessed a growing demand for wireless radio spectrum. However, the fixed spectrum assignment policy becomes a bottleneck for more efficient spectrum utilization, under which a great portion of the licensed spectrum is severely under-utilized. The inefficient usage of the limited spectrum resources urges the spectrum regulatory bodies to review their policy and start to seek for innovative communication technology that can exploit the wireless spectrum in a more intelligent and flexible way. The concept of cognitive radio is proposed to address the issue of spectrum efficiency and has been receiving an increasing attention in recent years, since it equips wireless users the capability to optimally adapt their operating parameters according to the interactions with the surrounding radio environment. There have been many significant developments in the past few years on cognitive radios. This paper surveys recent advances in research related to cognitive radios. The fundamentals of cognitive radio technology, architecture of a cognitive radio network and its applications are first introduced. The existing works in spectrum sensing are reviewed, and important issues in dynamic spectrum allocation and sharing are investigated in detail.
---
paper_title: Reinforcement Learning: A Survey

paper_content:

This paper surveys the field of reinforcement learning from a computer-science perspective. It is written to be accessible to researchers familiar with machine learning. Both the historical basis of the field and a broad selection of current work are summarized. Reinforcement learning is the problem faced by an agent that learns behavior through trial-and-error interactions with a dynamic environment. The work described here has a resemblance to work in psychology, but differs considerably in the details and in the use of the word ``reinforcement.'' The paper discusses central issues of reinforcement learning, including trading off exploration and exploitation, establishing the foundations of the field via Markov decision theory, learning from delayed reinforcement, constructing empirical models to accelerate learning, making use of generalization and hierarchy, and coping with hidden state. It concludes with a survey of some implemented systems and an assessment of the practical utility of current methods for reinforcement learning.
---
paper_title: NeXt generation/dynamic spectrum access/cognitive Radio Wireless Networks: A Survey

paper_content:

Today's wireless networks are characterized by a fixed spectrum assignment policy. However, a large portion of the assigned spectrum is used sporadically and geographical variations in the utilization of assigned spectrum ranges from 15% to 85% with a high variance in time. The limited available spectrum and the inefficiency in the spectrum usage necessitate a new communication paradigm to exploit the existing wireless spectrum opportunistically. This new networking paradigm is referred to as NeXt Generation (xG) Networks as well as Dynamic Spectrum Access (DSA) and cognitive radio networks. The term xG networks is used throughout the paper. The novel functionalities and current research challenges of the xG networks are explained in detail. More specifically, a brief overview of the cognitive radio technology is provided and the xG network architecture is introduced. Moreover, the xG network functions such as spectrum management, spectrum mobility and spectrum sharing are explained in detail. The influence of these functions on the performance of the upper layer protocols such as routing and transport are investigated and open research issues in these areas are also outlined. Finally, the cross-layer design challenges in xG networks are discussed.
---
paper_title: A Survey on Context-Aware Mobile and Wireless Networking: On Networking and Computing Environments' Integration

paper_content:

During the last years, a continuous convergence and fusion of computing and networking systems is stressed in the ICT research community. Context awareness appears to be a major research "glue-point" of such kind of heterogeneous environments' integration. In this survey paper, we aim to assemble all the "puzzle-pieces" of the emerging research area of Context Aware Mobile and Wireless Networking (CAMoWiN) in order to provide the reader a holistic representation of the work having been done in the past emphasizing in recent research efforts. A precise definition of abstract Context Aware (CA) functionalities together with a clear classification of related state-of-the-art proposals are provided in the form of a proposed taxonomy scheme per CA functionality. Each taxonomy scheme can also serve as a sufficiently general framework permitting the easy classification of novel CAMoWiN solutions emerging in the near future. Therefore, our study not only defines all the possible components of a CAMoWiN architecture and clearly points out the similarities and differences of all research efforts in the field but also evaluates future research trends and paves the way for the researchers to work beyond the concepts investigated in this work. Finally, apart from identifying the open challenges, which arise when applying traditional concepts of pervasive computing to mobile and wireless networks, we further map them to the Mobile Cloud Computing paradigm, whose concepts appear to be very promising regarding next generation networking and computing environments' integration.
---
paper_title: Cognitive Dynamic Systems: Perception-action Cycle, Radar and Radio

paper_content:

The principles of cognition are becoming increasingly important in the areas of signal processing, communications and control. In this groundbreaking book, Simon Haykin, a pioneer in the field and an award-winning researcher, educator and author, sets out the fundamental ideas of cognitive dynamic systems. Weaving together the various branches of study involved, he demonstrates the power of cognitive information processing and highlights a range of future research directions. The book begins with a discussion of core topics such as cognition and sensing, dealing, in particular, with the perception-action cycle. Bayesian filtering, machine learning and dynamic programming are then addressed. Building on these foundations, there is detailed coverage of two important practical applications, cognitive radar and cognitive radio. Blending theory and practice, this insightful book is aimed at all graduate students and researchers looking for a thorough grounding in this fascinating field.
---
paper_title: Learning control of finite Markov chains with unknown transition probabilities

paper_content:

For a Markovian decision problem in which the transition probabilities are unknown, two learning algorithms are devised from the viewpoint of asymptotic optimality. Each time the algorithms select decisions to be used on the basis of not only the estimates of the unknown probabilities but also uncertainty of them. It is shown that the algorithms are asymptotically optimal in the sense that the probability of selecting an optimal policy converges to unity.
---
paper_title: Review: Reinforcement learning for context awareness and intelligence in wireless networks: Review, new features and open issues

paper_content:

In wireless networks, context awareness and intelligence are capabilities that enable each host to observe, learn, and respond to its complex and dynamic operating environment in an efficient manner. These capabilities contrast with traditional approaches where each host adheres to a predefined set of rules, and responds accordingly. In recent years, context awareness and intelligence have gained tremendous popularity due to the substantial network-wide performance enhancement they have to offer. In this article, we advocate the use of reinforcement learning (RL) to achieve context awareness and intelligence. The RL approach has been applied in a variety of schemes such as routing, resource management and dynamic channel selection in wireless networks. Examples of wireless networks are mobile ad hoc networks, wireless sensor networks, cellular networks and cognitive radio networks. This article presents an overview of classical RL and three extensions, including events, rules and agent interaction and coordination, to wireless networks. We discuss how several wireless network schemes have been approached using RL to provide network performance enhancement, and also open issues associated with this approach. Throughout the paper, discussions are presented in a tutorial manner, and are related to existing work in order to establish a foundation for further research in this field, specifically, for the improvement of the RL approach in the context of wireless networking, for the improvement of the RL approach through the use of the extensions in existing schemes, as well as for the design and implementation of RL in new schemes.
---
paper_title: Cognitive radio: brain-empowered wireless communications

paper_content:

Cognitive radio is viewed as a novel approach for improving the utilization of a precious natural resource: the radio electromagnetic spectrum. The cognitive radio, built on a software-defined radio, is defined as an intelligent wireless communication system that is aware of its environment and uses the methodology of understanding-by-building to learn from the environment and adapt to statistical variations in the input stimuli, with two primary objectives in mind: /spl middot/ highly reliable communication whenever and wherever needed; /spl middot/ efficient utilization of the radio spectrum. Following the discussion of interference temperature as a new metric for the quantification and management of interference, the paper addresses three fundamental cognitive tasks. 1) Radio-scene analysis. 2) Channel-state estimation and predictive modeling. 3) Transmit-power control and dynamic spectrum management. This work also discusses the emergent behavior of cognitive radio.
---
paper_title: Q-learning

paper_content:

\cal Q-learning (Watkins, 1989) is a simple way for agents to learn how to act optimally in controlled Markovian domains. It amounts to an incremental method for dynamic programming which imposes limited computational demands. It works by successively improving its evaluations of the quality of particular actions at particular states. ::: ::: This paper presents and proves in detail a convergence theorem for \cal Q-learning based on that outlined in Watkins (1989). We show that \cal Q-learning converges to the optimum action-values with probability 1 so long as all actions are repeatedly sampled in all states and the action-values are represented discretely. We also sketch extensions to the cases of non-discounted, but absorbing, Markov environments, and where many \cal Q values can be changed each iteration, rather than just one.
---
paper_title: Advances in cognitive radio networks: A survey

paper_content:

With the rapid deployment of new wireless devices and applications, the last decade has witnessed a growing demand for wireless radio spectrum. However, the fixed spectrum assignment policy becomes a bottleneck for more efficient spectrum utilization, under which a great portion of the licensed spectrum is severely under-utilized. The inefficient usage of the limited spectrum resources urges the spectrum regulatory bodies to review their policy and start to seek for innovative communication technology that can exploit the wireless spectrum in a more intelligent and flexible way. The concept of cognitive radio is proposed to address the issue of spectrum efficiency and has been receiving an increasing attention in recent years, since it equips wireless users the capability to optimally adapt their operating parameters according to the interactions with the surrounding radio environment. There have been many significant developments in the past few years on cognitive radios. This paper surveys recent advances in research related to cognitive radios. The fundamentals of cognitive radio technology, architecture of a cognitive radio network and its applications are first introduced. The existing works in spectrum sensing are reviewed, and important issues in dynamic spectrum allocation and sharing are investigated in detail.
---
paper_title: A reinforcement learning approach to automatic generation control

paper_content:

This paper formulates the automatic generation control (AGC) problem as a stochastic multistage decision problem. A strategy for solving this new AGC problem formulation is presented by using a reinforcement learning (RL) approach This method of obtaining an AGC controller does not depend on any knowledge of the system model and more importantly it admits considerable flexibility in defining the control objective. Two specific RL based AGC algorithms are presented. The first algorithm uses the traditional control objective of limiting area control error (ACE) excursions, where as, in the second algorithm, the controller can restore the load-generation balance by only monitoring deviation in tie line flows and system frequency and it does not need to know or estimate the composite ACE signal as is done by all current approaches. The effectiveness and versatility of the approaches has been demonstrated using a two area AGC model. (C) 2002 Elsevier Science B.V. All rights reserved.
---
paper_title: Markov Processes For Stochastic Modeling

paper_content:

Markov processes are used to model systems with limited memory. They are used in many areas including communications systems, transportation networks, image segmentation and analysis, biological systems and DNA sequence analysis, random atomic motion and diffusion in physics, social mobility, population studies, epidemiology, animal and insect migration, queuing systems, resource management, dams, financial engineering, actuarial science, and decision systems. This book, which is written for upper level undergraduate and graduate students, and researchers, presents a unified presentation of Markov processes.In addition to traditional topics such as Markovian queuing system, the book discusses such topics as continuous-time random walk, correlated random walk, Brownian motion, diffusion processes, hidden Markov models, Markov random fields, Markov point processes and Markov chain Monte Carlo. Continuous-time random walk is currently used in econophysics to model the financial market, which has traditionally been modeled as a Brownian motion.Correlated random walk is popularly used in ecological studies to model animal and insect movement. Hidden Markov models are used in speech analysis and DNA sequence analysis while Markov random fields and Markov point processes are used in image analysis. Thus, the book is designed to have a very broad appeal. It provides the practical, current applications of Markov processes, and covers HMM, Point processes, and Monte Carlo. It includes enough theory to help students gain thorough understanding of the subject. Principles can be immediately applied in many specific research projects, saving researchers time. The end of chapter exercises provide reinforcement, practice and increased understanding to the student.
---
paper_title: A Survey of Actor-Critic Reinforcement Learning: Standard and Natural Policy Gradients

paper_content:

Policy-gradient-based actor-critic algorithms are amongst the most popular algorithms in the reinforcement learning framework. Their advantage of being able to search for optimal policies using low-variance gradient estimates has made them useful in several real-life applications, such as robotics, power control, and finance. Although general surveys on reinforcement learning techniques already exist, no survey is specifically dedicated to actor-critic algorithms in particular. This paper, therefore, describes the state of the art of actor-critic algorithms, with a focus on methods that can work in an online setting and use function approximation in order to deal with continuous state and action spaces. After starting with a discussion on the concepts of reinforcement learning and the origins of actor-critic algorithms, this paper describes the workings of the natural gradient, which has made its way into many actor-critic algorithms over the past few years. A review of several standard and natural actor-critic algorithms is given, and the paper concludes with an overview of application areas and a discussion on open issues.
---
paper_title: Average reward reinforcement learning: Foundations, algorithms, and empirical results

paper_content:

This paper presents a detailed study of average reward reinforcement learning, an undiscounted optimality framework that is more appropriate for cyclical tasks than the much better studied discounted framework. A wide spectrum of average reward algorithms are described, ranging from synchronous dynamic programming methods to several (provably convergent) asynchronous algorithms from optimal control and learning automata. A general sensitive discount optimality metric calledn-discount-optimality is introduced, and used to compare the various algorithms. The overview identifies a key similarity across several asynchronous algorithms that is crucial to their convergence, namely independent estimation of the average reward and the relative values. The overview also uncovers a surprising limitation shared by the different algorithms while several algorithms can provably generategain-optimal policies that maximize average reward, none of them can reliably filter these to producebias-optimal (orT-optimal) policies that also maximize the finite reward to absorbing goal states. This paper also presents a detailed empirical study of R-learning, an average reward reinforcement learning method, using two empirical testbeds: a stochastic grid world domain and a simulated robot environment. A detailed sensitivity analysis of R-learning is carried out to test its dependence on learning rates and exploration levels. The results suggest that R-learning is quite sensitive to exploration strategies and can fall into sub-optimal limit cycles. The performance of R-learning is also compared with that of Q-learning, the best studied discounted RL method. Here, the results suggest that R-learning can be fine-tuned to give better performance than Q-learning in both domains.
---
paper_title: Reinforcement Learning: A Survey

paper_content:

This paper surveys the field of reinforcement learning from a computer-science perspective. It is written to be accessible to researchers familiar with machine learning. Both the historical basis of the field and a broad selection of current work are summarized. Reinforcement learning is the problem faced by an agent that learns behavior through trial-and-error interactions with a dynamic environment. The work described here has a resemblance to work in psychology, but differs considerably in the details and in the use of the word ``reinforcement.'' The paper discusses central issues of reinforcement learning, including trading off exploration and exploitation, establishing the foundations of the field via Markov decision theory, learning from delayed reinforcement, constructing empirical models to accelerate learning, making use of generalization and hierarchy, and coping with hidden state. It concludes with a survey of some implemented systems and an assessment of the practical utility of current methods for reinforcement learning.
---
paper_title: Ensemble Algorithms in Reinforcement Learning

paper_content:

This paper describes several ensemble methods that combine multiple different reinforcement learning (RL) algorithms in a single agent. The aim is to enhance learning speed and final performance by combining the chosen actions or action probabilities of different RL algorithms. We designed and implemented four different ensemble methods combining the following five different RL algorithms: Q-learning, Sarsa, actor-critic (AC), QV-learning, and AC learning automaton. The intuitively designed ensemble methods, namely, majority voting (MV), rank voting, Boltzmann multiplication (BM), and Boltzmann addition, combine the policies derived from the value functions of the different RL algorithms, in contrast to previous work where ensemble methods have been used in RL for representing and learning a single value function. We show experiments on five maze problems of varying complexity; the first problem is simple, but the other four maze tasks are of a dynamic or partially observable nature. The results indicate that the BM and MV ensembles significantly outperform the single RL algorithms.
---
paper_title: A Survey on Machine-Learning Techniques in Cognitive Radios

paper_content:

In this survey paper, we characterize the learning problem in cognitive radios (CRs) and state the importance of artificial intelligence in achieving real cognitive communications systems. We review various learning problems that have been studied in the context of CRs classifying them under two main categories: Decision-making and feature classification. Decision-making is responsible for determining policies and decision rules for CRs while feature classification permits identifying and classifying different observation models. The learning algorithms encountered are categorized as either supervised or unsupervised algorithms. We describe in detail several challenging learning issues that arise in cognitive radio networks (CRNs), in particular in non-Markovian environments and decentralized networks, and present possible solution methods to address them. We discuss similarities and differences among the presented algorithms and identify the conditions under which each of the techniques may be applied.
---
paper_title: Decentralized learning in finite Markov chains

paper_content:

The principal contribution of this paper is a new result on the decentralized control of finite Markov chains with unknown transition probabilities and rewards. One decentralized decision maker is associated with each state in which two or more actions (decisions) are available. Each decision maker uses a simple learning scheme, requiring minimal information, to update its action choice. It is shown that, if updating is done in sufficiently small steps, the group will converge to the policy that maximizes the long-term expected reward per step. The analysis is based on learning in sequential stochastic games and on certain properties, derived in this paper, of ergodic Markov chains.
---
paper_title: Cognitive Dynamic Systems: Perception-action Cycle, Radar and Radio

paper_content:

The principles of cognition are becoming increasingly important in the areas of signal processing, communications and control. In this groundbreaking book, Simon Haykin, a pioneer in the field and an award-winning researcher, educator and author, sets out the fundamental ideas of cognitive dynamic systems. Weaving together the various branches of study involved, he demonstrates the power of cognitive information processing and highlights a range of future research directions. The book begins with a discussion of core topics such as cognition and sensing, dealing, in particular, with the perception-action cycle. Bayesian filtering, machine learning and dynamic programming are then addressed. Building on these foundations, there is detailed coverage of two important practical applications, cognitive radar and cognitive radio. Blending theory and practice, this insightful book is aimed at all graduate students and researchers looking for a thorough grounding in this fascinating field.
---
paper_title: Individual learning of coordination knowledge

paper_content:

Abstract. Social agents, both human and computational, inhabiting a world containing multiple active agents, need to coordinate their activities. This is because agents share resources, and without proper coordination or ‘rules of the road’, everybody will be interfering with the plans of others. As such, we need coordination schemes that allow agents to effectively achieve local goals without adversely affecting the problem-solving capabilities of other agents. Researchers in the field of Distributed Artificial Intelligence (DAI) have developed a variety of coordination schemes under different assumptions about agent capabilities and relationships. Whereas some of these researchers have been motivated by human cognitive biases, others have approached it as an engineering problem of designing the most effective coordination architecture or protocol. We evaluate individual and concurrent learning by multiple, autonomous agents as a means for acquiring coordination knowledge. We show that a uniform reinforc...
---
paper_title: Accelerating Reinforcement Learning through Implicit Imitation

paper_content:

Imitation can be viewed as a means of enhancing learning in multiagent environments. It augments an agent's ability to learn useful behaviors by making intelligent use of the knowledge implicit in behaviors demonstrated by cooperative teachers or other more experienced agents. We propose and study a formal model of implicit imitation that can accelerate reinforcement learning dramatically in certain cases. Roughly, by observing a mentor, a reinforcement-learning agent can extract information about its own capabilities in, and the relative value of, unvisited parts of the state space. We study two specific instantiations of this model, one in which the learning agent and the mentor have identical abilities, and one designed to deal with agents and mentors with difierent action sets. We illustrate the benefits of implicit imitation by integrating it with prioritized sweeping, and demonstrating improved performance and convergence through observation of single and multiple mentors. Though we make some stringent assumptions regarding observability and possible interactions, we briefly comment on extensions of the model that relax these restricitions.
---
paper_title: Advances in cognitive radio networks: A survey

paper_content:

With the rapid deployment of new wireless devices and applications, the last decade has witnessed a growing demand for wireless radio spectrum. However, the fixed spectrum assignment policy becomes a bottleneck for more efficient spectrum utilization, under which a great portion of the licensed spectrum is severely under-utilized. The inefficient usage of the limited spectrum resources urges the spectrum regulatory bodies to review their policy and start to seek for innovative communication technology that can exploit the wireless spectrum in a more intelligent and flexible way. The concept of cognitive radio is proposed to address the issue of spectrum efficiency and has been receiving an increasing attention in recent years, since it equips wireless users the capability to optimally adapt their operating parameters according to the interactions with the surrounding radio environment. There have been many significant developments in the past few years on cognitive radios. This paper surveys recent advances in research related to cognitive radios. The fundamentals of cognitive radio technology, architecture of a cognitive radio network and its applications are first introduced. The existing works in spectrum sensing are reviewed, and important issues in dynamic spectrum allocation and sharing are investigated in detail.
---
paper_title: Cooperative Multi-Agent Learning: The State of the Art

paper_content:

Cooperative multi-agent systems (MAS) are ones in which several agents attempt, through their interaction, to jointly solve tasks or to maximize utility. Due to the interactions among the agents, multi-agent problem complexity can rise rapidly with the number of agents or their behavioral sophistication. The challenge this presents to the task of programming solutions to MAS problems has spawned increasing interest in machine learning techniques to automate the search and optimization process. We provide a broad survey of the cooperative multi-agent learning literature. Previous surveys of this area have largely focused on issues common to specific subareas (for example, reinforcement learning, RL or robotics). In this survey we attempt to draw from multi-agent learning work in a spectrum of areas, including RL, evolutionary computation, game theory, complex systems, agent modeling, and robotics. We find that this broad view leads to a division of the work into two categories, each with its own special issues: applying a single learner to discover joint solutions to multi-agent problems (team learning), or using multiple simultaneous learners, often one per agent (concurrent learning). Additionally, we discuss direct and indirect communication in connection with learning, plus open issues in task decomposition, scalability, and adaptive dynamics. We conclude with a presentation of multi-agent learning problem domains, and a list of multi-agent learning resources.
---
paper_title: Reinforcement Learning: An Introduction

paper_content:

Reinforcement learning, one of the most active research areas in artificial intelligence, is a computational approach to learning whereby an agent tries to maximize the total amount of reward it receives when interacting with a complex, uncertain environment. In Reinforcement Learning, Richard Sutton and Andrew Barto provide a clear and simple account of the key ideas and algorithms of reinforcement learning. Their discussion ranges from the history of the field's intellectual foundations to the most recent developments and applications. The only necessary mathematical background is familiarity with elementary concepts of probability. The book is divided into three parts. Part I defines the reinforcement learning problem in terms of Markov decision processes. Part II provides basic solution methods: dynamic programming, Monte Carlo methods, and temporal-difference learning. Part III presents a unified view of the solution methods and incorporates artificial neural networks, eligibility traces, and planning; the two final chapters present case studies and consider the future of reinforcement learning.
---
paper_title: Multi Agent Reinforcement Learning Independent vs Cooperative Agents

paper_content:

Intelligent human agents exist in a cooperative social environment that facilitates learning. They learn not only by trial-and-error, but also through cooperation by sharing instantaneous information, episodic experience, and learned knowledge. The key investigations of this paper are, “Given the same number of reinforcement learning agents, will cooperative agents outperform independent agents who do not communicate during learning?” and “What is the price for such cooperation?” Using independent agents as a benchmark, cooperative agents are studied in following ways: (1) sharing sensation, (2) sharing episodes, and (3) sharing learned policies. This paper shows that (a) additional sensation from another agent is beneficial if it can be used efficiently, (b) sharing learned policies or episodes among agents speeds up learning at the cost of communication, and (c) for joint tasks, agents engaging in partnership can significantly outperform independent agents although they may learn slowly in the beginning. These tradeoff's are not just limited to multi-agent reinforcement learning.
---
paper_title: The Dynamics of Reinforcement Learning in Cooperative Multiagent Systems

paper_content:

Reinforcement learning can provide a robust and natural means for agents to learn how to coordinate their action choices in multi agent systems. We examine some of the factors that can influence the dynamics of the learning process in such a setting. We first distinguish reinforcement learners that are unaware of (or ignore) the presence of other agents from those that explicitly attempt to learn the value of joint actions and the strategies of their counterparts. We study (a simple form of) Q-leaming in cooperative multi agent systems under these two perspectives, focusing on the influence of that game structure and exploration strategies on convergence to (optimal and suboptimal) Nash equilibria. We then propose alternative optimistic exploration strategies that increase the likelihood of convergence to an optimal equilibrium.
---
paper_title: Best-Response Multiagent Learning in Non-Stationary Environments

paper_content:

This paper investigates a relatively new direction in Multiagent Reinforcement Learning. Most multiagent learning techniques focus on Nash equilibria as elements of both the learning algorithm and its evaluation criteria. In contrast, we propose a multiagent learning algorithm that is optimal in the sense of finding a best-response policy, rather than in reaching an equilibrium. We present the first learning algorithm that is provably optimal against restricted classes of non-stationary opponents. The algorithm infers an accurate model of the opponentýs non-stationary strategy, and simultaneously creates a best-response policy against that strategy. Our learning algorithm works within the very general framework of n-player, general-sum stochastic games, and learns both the game structure and its associated optimal policy.
---
paper_title: Cooperative Control and Potential Games

paper_content:

We present a view of cooperative control using the language of learning in games. We review the game-theoretic concepts of potential and weakly acyclic games, and demonstrate how several cooperative control problems, such as consensus and dynamic sensor coverage, can be formulated in these settings. Motivated by this connection, we build upon game-theoretic concepts to better accommodate a broader class of cooperative control problems. In particular, we extend existing learning algorithms to accommodate restricted action sets caused by the limitations of agent capabilities and group based decision making. Furthermore, we also introduce a new class of games called sometimes weakly acyclic games for time-varying objective functions and action sets, and provide distributed algorithms for convergence to an equilibrium.
---
paper_title: Game Theory in Wireless and Communication Networks

paper_content:

This unified treatment of game theory focuses on finding state-of-the-art solutions to issues surrounding the next generation of wireless and communication networks. Future networkswillrelyonautonomousanddistributedarchitecturestoimprovetheefficiency and flexibility of mobile applications, and game theory provides the ideal framework for designing efficient and robust distributed algorithms. This book enables readers to develop a solid understanding of game theory, its applications, and its use as an effective tool for addressing various problems in wireless communication and networking. The key results and tools of game theory are covered, as are various real-world technologies including 3G/4G networks, wireless LANs, sensor networks, cognitive networks, and Internet networks. The book also covers a wide range of techniques for modeling, designing, and analyzing communication networks using game theory, as well as state-of-the-art distributed design techniques. This is an ideal resource for communications engineers, researchers, and graduate and undergraduate students.
---
paper_title: A Context Driven Architecture for Cognitive Radio Nodes

paper_content:

A cognitive radio (CR), in its generic form, needs to be highly flexible and adaptive while desirably hiding its complexities from users and system programmers. For the autonomic management the CR needs to be aware of the `self' and the `world' around it. Embedded intelligence with cognitive and collaborative adaptations require innovative techniques for managing the functionality of the device. Complexity of the cognitive processes involved demand for formal methods for run time evaluations and verification. In this paper we propose a generic architecture for a cognitive node with a context driven approach which incorporates some formalisms including context spaces, ontology, process algebra to represent and manipulate various cognitive processes managing the cognitive node functionality.
---
paper_title: Conjectural Equilibrium in Multiagent Learning

paper_content:

Learning in a multiagent environment is complicated by the fact that as other agents learn, the environment effectively changes. Moreover, other agents' actions are often not directly observable, and the actions taken by the learning agent can strongly bias which range of behaviors are encountered. We define the concept of a conjectural equilibrium, where all agents' expectations are realized, and each agent responds optimally to its expectations. We present a generic multiagent exchange situation, in which competitive behavior constitutes a conjectural equilibrium. We then introduce an agent that executes a more sophisticated strategic learning strategy, building a model of the response of other agents. We find that the system reliably converges to a conjectural equilibrium, but that the final result achieved is highly sensitive to initial belief. In essence, the strategic learner's actions tend to fulfill its expectations. Depending on the starting point, the agent may be better or worse off than had it not attempted to learn a model of the other agents at all.
---
paper_title: A simple adaptive procedure leading to correlated equilibrium

paper_content:

We propose a new and simple adaptive procedure for playing a game: "regret-matching." In this procedure, players depart from their current play with probabilities that are proportional to measures of regret for not having used other strategies in the past. It is shown that our adaptive procedure guarantees that, with probability one, the empirical distributions of play converge to the set of correlated equilibria of the game. To compute these regret measures, a player needs to know his payoff function and the history of play. We also offer a variation where every player knows only his own realized payoff history (but not his payoff function).
---
paper_title: Game Theory For Wireless Engineers

paper_content:

The application of mathematical analysis to wireless networks has met with limited success, due to the complexity of mobility and traffic models, coupled with the dynamic topology and the unpredictability of link quality that characterize such networks. The ability to model individual, independent decision makers whose actions potentially affect all other decision makers makes game theory particularly attractive to analyze the performance of ad hoc networks. Game theory is a field of applied mathematics that describes and analyzes interactive decision situations. It consists of a set of analytical tools that predict the outcome of complex interactions among rational entities, where rationality demands a strict adherence to a strategy based on perceived or measured results. In the early to mid-1990's, game theory was applied to networking problems including flow control, congestion control, routing and pricing of Internet services. More recently, there has been growing interest in adopting game-theoretic methods to model today's leading communications and networking issues, including power control and resource sharing in wireless and peer-to-peer networks. This work presents fundamental results in game theory and their application to wireless communications and networking. We discuss normal-form, repeated, and Markov games with examples selected from the literature. We also describe ways in which learning can be modeled in game theory, with direct applications to the emerging field of cognitive radio. Finally, we discuss challenges and limitations in the application of game theory to the analysis of wireless systems. We do not assume familiarity with game theory. We introduce major game theoretic models and discuss applications of game theory including medium access, routing, energy-efficient protocols, and others. We seek to provide the reader with a foundational understanding of the current research on game theory applied to wireless communications and networking.
---
paper_title: Nash Q-Learning for General-Sum Stochastic Games

paper_content:

We extend Q-learning to a noncooperative multiagent context, using the framework of general-sum stochastic games. A learning agent maintains Q-functions over joint actions, and performs updates based on assuming Nash equilibrium behavior over the current Q-values. This learning protocol provably converges given certain restrictions on the stage games (defined by Q-values) that arise during learning. Experiments with a pair of two-player grid games suggest that such restrictions on the game structure are not necessarily required. Stage games encountered during learning in both grid environments violate the conditions. However, learning consistently converges in the first grid game, which has a unique equilibrium Q-function, but sometimes fails to converge in the second, which has three different equilibrium Q-functions. In a comparison of offline learning performance in both games, we find agents are more likely to reach a joint optimal path with Nash Q-learning than with a single-agent Q-learning method. When at least one agent adopts Nash Q-learning, the performance of both agents is better than using single-agent Q-learning. We have also implemented an online version of Nash Q-learning that balances exploration with exploitation, yielding improved performance.
---
paper_title: Markov Games as a Framework for Multi-Agent Reinforcement Learning

paper_content:

In the Markov decision process (MDP) formalization of reinforcement learning, a single adaptive agent interacts with an environment defined by a probabilistic transition function. In this solipsis-tic view, secondary agents can only be part of the environment and are therefore fixed in their behavior. The framework of Markov games allows us to widen this view to include multiple adaptive agents with interacting or competing goals. This paper considers a step in this direction in which exactly two agents with diametrically opposed goals share an environment. It describes a Q-learning-like algorithm for finding optimal policies and demonstrates its application to a simple two-player game in which the optimal policy is probabilistic.
---
paper_title: On the Global Convergence of Stochastic Fictitious Play

paper_content:

We establish global convergence results for stochastic fictitious play for four classes of games: games with an interior ESS, zero sum games, potential games, and supermodular games. We do so by appealing to techniques from stochastic approximation theory, which relate the limit behavior of a stochastic process to the limit behavior of a differential equation defined by the expected motion of the process. The key result in our analysis of supermodular games is that the relevant differential equation defines a strongly monotone dynamical system. Our analyses of the other cases combine Lyapunov function arguments with a discrete choice theory result: that the choice probabilities generated by any additive random utility model can be derived from a deterministic model based on payoff perturbations that depend nonlinearly on the vector of choice probabilities.
---
paper_title: Distributed Strategic Learning for Wireless Engineers

paper_content:

Establishing the link between several theories, this book demonstrates what is needed to learn strategic interaction in wireless networks under uncertainty, randomness, and time delays. This robust game theory cookbook analyzes games where some parameters are uncertain and random. Starting with the fundamentals of strategic learning and game theory, the text then covers partially and fully distributed learning, combined learning for negotiation, bargaining solutions, Nash equilibria, Stackelberg solutions, correlated equilibria, conjectural variations, and satisfactory solutions. It concludes with practical algorithms and techniques to implement game theory in wireless networks.
---
paper_title: Equilibrium Points in Nonzero-Sum n-Person Submodular Games

paper_content:

A submodular game is a finite noncooperative game in which the set of feasible joint decisions is a sublattice and the cost function of each player has properties of submodularity and antitone differences. Examples of submodular games include 1) a game version of a system with complementary products; 2) an extension of the minimum cut problem to a situation where players choose from different sets of nodes and perceive different capacities, with special cases being a game with players choosing whether or not to participate in available economic activities and a game version of the selection problem; 3) the pricing problem of competitors producing substitute products; 4) a game version of the facility location problem; and 5) a game with players determining their optimal usage of available products. A fixed point approach establishes the existence of a pure equilibrium point for certain submodular games. Two algorithms which correspond to fictitious play in dynamic games generate sequences of feasible join...
---
paper_title: Decentralized Learning in Markov Games

paper_content:

Learning automata (LA) were recently shown to be valuable tools for designing multiagent reinforcement learning algorithms. One of the principal contributions of the LA theory is that a set of decentralized independent LA is able to control a finite Markov chain with unknown transition probabilities and rewards. In this paper, we propose to extend this algorithm to Markov games-a straightforward extension of single-agent Markov decision problems to distributed multiagent decision problems. We show that under the same ergodic assumptions of the original theorem, the extended algorithm will converge to a pure equilibrium point between agent policies.
---
paper_title: Game Theory and Learning for Wireless Networks: Fundamentals and Applications

paper_content:

* The first tutorial-style book that gives all the relevant theory at the right level of rigor, for the wireless communications engineer. * Bridges the gap between theory and practice by giving examples and case studies showing how game theory can solve real-word problems. * Contains algorithms and techniques to implement game theory in wireless terminals. Written by leading experts in the field, Game Theory and Learning for Wireless Networks Covers how theory can be used to solve prevalent problems in wireless networks such as power control, resource allocation or medium access control. With the emphasis now on promoting 'green' solutions in the wireless field where power consumption is minimized, there is an added focus on developing network solutions that maximizes the use of the spectrum available. With the growth of distributed wireless networks such as Wi-Fi and the Internet; the push to develop ad hoc and cognitive networks has led to a considerable interest in applying game theory to wireless communication systems. Game Theory and Learning for Wireless Networks is the first comprehensive resource of its kind, and is ideal for wireless communications R&D engineers and graduate students. Samson Lasaulce is a senior CNRS researcher at the Laboratory of Signals and Systems (LSS) at Suplec, Gif-sur-Yvette, France. He is also a part-time professor in the Department of Physics at cole Polytechnique, Palaiseau, France. Hamidou Tembine is a professor in the Department of Telecommunications at Suplec, Gif-sur-Yvette, France. Merouane Debbah is a professor at Suplec, Gif-sur-Yvette, France. He is the holder of the Alcatel-Lucent chair in flexible radio since 2007. The first tutorial style book that gives all the relevant theory, at the right level of rigour, for the wireless communications engineer Bridges the gap between theory and practice by giving examples and case studies showing how game theory can solve real world resource allocation problems Contains algorithms and techniques to implement game theory in wireless terminals
---
paper_title: A Survey on Context-Aware Mobile and Wireless Networking: On Networking and Computing Environments' Integration

paper_content:

During the last years, a continuous convergence and fusion of computing and networking systems is stressed in the ICT research community. Context awareness appears to be a major research "glue-point" of such kind of heterogeneous environments' integration. In this survey paper, we aim to assemble all the "puzzle-pieces" of the emerging research area of Context Aware Mobile and Wireless Networking (CAMoWiN) in order to provide the reader a holistic representation of the work having been done in the past emphasizing in recent research efforts. A precise definition of abstract Context Aware (CA) functionalities together with a clear classification of related state-of-the-art proposals are provided in the form of a proposed taxonomy scheme per CA functionality. Each taxonomy scheme can also serve as a sufficiently general framework permitting the easy classification of novel CAMoWiN solutions emerging in the near future. Therefore, our study not only defines all the possible components of a CAMoWiN architecture and clearly points out the similarities and differences of all research efforts in the field but also evaluates future research trends and paves the way for the researchers to work beyond the concepts investigated in this work. Finally, apart from identifying the open challenges, which arise when applying traditional concepts of pervasive computing to mobile and wireless networks, we further map them to the Mobile Cloud Computing paradigm, whose concepts appear to be very promising regarding next generation networking and computing environments' integration.
---
paper_title: Dynamic fictitious play, dynamic gradient play, and distributed convergence to Nash equilibria

paper_content:

We consider a continuous-time form of repeated matrix games in which player strategies evolve in reaction to opponent actions. Players observe each other's actions, but do not have access to other player utilities. Strategy evolution may be of the best response sort, as in fictitious play, or a gradient update. Such mechanisms are known to not necessarily converge. We introduce a form of "dynamic" fictitious and gradient play strategy update mechanisms. These mechanisms use derivative action in processing opponent actions and, in some cases, can lead to behavior converging to Nash equilibria in previously nonconvergent situations. We analyze convergence in the case of exact and approximate derivative measurements of the dynamic update mechanisms. In the ideal case of exact derivative measurements, we show that convergence to Nash equilibrium can always be achieved. In the case of approximate derivative measurements, we derive a characterization of local convergence that shows how the dynamic update mechanisms can converge if the traditional static counterparts do not. We primarily discuss two player games, but also outline extensions to multiplayer games. We illustrate these methods with convergent simulations of the well known Shapley and Jordan counterexamples.
---
paper_title: Learning through reinforcement for N-person repeated constrained games

paper_content:

The design and analysis of an adaptive strategy for N-person averaged constrained stochastic repeated game are addressed. Each player is modeled by a stochastic variable-structure learning automaton. Some constraints are imposed on some functions of the probabilities governing the selection of the player's actions. After each stage, the payoff to each player as well as the constraints are random variables. No information concerning the parameters of the game is a priori available. The "diagonal concavity" conditions are assumed to be fulfilled to guarantee the existence and uniqueness of the Nash equilibrium. The suggested adaptive strategy which uses only the current realizations (outcomes and constraints) of the game is based on the Bush-Mosteller reinforcement scheme in connection with a normalization procedure. The Lagrange multipliers approach with a regularization is used. The asymptotic properties of this algorithm are analyzed. Simulation results illustrate the feasibility and the performance of this adaptive strategy.
---
paper_title: Adapting behaviors through a learning process

paper_content:

This paper concerns the concepts of conjectures and reactions of agents in a dynamic context, a framework where agents form conjectures on how the other agents (would) react to their actions and update this belief according to observations. They decide based on this conjecture without knowing profit functions of other agents. Agents somehow “learn” about the behavior (including the conjectures) of the other agents. We show that some type of “consistency” of these conjectures spontaneously appears. We discuss the Pareto-optimality and the local stability of the strategies obtained in the long run and analyze the example of Cournot’s oligopoly.
---
paper_title: Decentralized learning in finite Markov chains

paper_content:

The principal contribution of this paper is a new result on the decentralized control of finite Markov chains with unknown transition probabilities and rewards. One decentralized decision maker is associated with each state in which two or more actions (decisions) are available. Each decision maker uses a simple learning scheme, requiring minimal information, to update its action choice. It is shown that, if updating is done in sufficiently small steps, the group will converge to the policy that maximizes the long-term expected reward per step. The analysis is based on learning in sequential stochastic games and on certain properties, derived in this paper, of ergodic Markov chains.
---
paper_title: Convergent Multiple-Timescales Reinforcement Learning Algorithms In Normal Form Games

paper_content:

We consider reinforcement learning algorithms in normal form games. Using two-timescales stochastic approximation, we introduce a model-free algorithm which is asymptotically equivalent to the smooth fictitious play algorithm, in that both result in asymptotic pseudotrajectories to the flow defined by the smooth best response dynamics. Both of these algorithms are shown to converge almost surely to Nash distribution in two-player zero-sum games and N -player partnership games. However, there are simple games for which these, and most other adaptive processes, fail to converge--in particular, we consider the N -player matching pennies game and Shapley's variant of the rock--scissors--paper game. By extending stochastic approximation results to multiple timescales we can allow each player to learn at a different rate. We show that this extension will converge for two-player zero-sum games and two-player partnership games, as well as for the two special cases we consider.
---
paper_title: Cognitive Dynamic Systems: Perception-action Cycle, Radar and Radio

paper_content:

The principles of cognition are becoming increasingly important in the areas of signal processing, communications and control. In this groundbreaking book, Simon Haykin, a pioneer in the field and an award-winning researcher, educator and author, sets out the fundamental ideas of cognitive dynamic systems. Weaving together the various branches of study involved, he demonstrates the power of cognitive information processing and highlights a range of future research directions. The book begins with a discussion of core topics such as cognition and sensing, dealing, in particular, with the perception-action cycle. Bayesian filtering, machine learning and dynamic programming are then addressed. Building on these foundations, there is detailed coverage of two important practical applications, cognitive radar and cognitive radio. Blending theory and practice, this insightful book is aimed at all graduate students and researchers looking for a thorough grounding in this fascinating field.
---
paper_title: Correlated Q-Learning

paper_content:

This paper introduces Correlated-Q (CE-Q) learning, a multiagent Q-learning algorithm based on the correlated equilibrium (CE) solution concept. CE-Q generalizes both Nash-Q and Friend-and-Foe-Q: in general-sum games, the set of correlated equilibria contains the set of Nash equilibria; in constant-sum games, the set of correlated equilibria contains the set of minimax equilibria. This paper describes experiments with four variants of CE-Q, demonstrating empirical convergence to equilibrium policies on a testbed of general-sum Markov games.
---
paper_title: On-Line Learning and Optimization for Wireless Video Transmission

paper_content:

In this paper, we address the problem of how to optimize the cross-layer transmission policy for delay-sensitive video streaming over slow-varying flat-fading wireless channels on-line, at transmission time, when the environment dynamics are unknown. We first formulate the cross-layer optimization using a systematic layered Markov decision process (MDP) framework, which complies with the layered architecture of the OSI stack. Subsequently, considering the unknown dynamics of the video sources and underlying wireless channels, we propose a layered real-time dynamic programming (LRTDP) algorithm, which requires no a priori knowledge about the source and network dynamics. LRTDP allows each layer to learn the dynamics on-the-fly, and adjusts its policy autonomously, based on their experienced dynamics as well as limited message exchanges with other layers. Unlike existing cross-layer methods, LRTDP optimizes the cross-layer policy in a layered and on-line fashion, exhibits a low computational complexity, requires limited message exchanges among layers, and is capable to adapt on-the-fly to the experienced environment dynamics. Finally, we prove that LRTDP converges to the optimal cross-layer policy asymptotically. Our numerical experiments show that LRTDP provides comparable performance to the idealized optimal cross-layer solutions based on complete knowledge.
---
paper_title: Learning to Compete for Resources in Wireless Stochastic Games

paper_content:

In this paper, we model the various users in a wireless network (e.g., cognitive radio network) as a collection of selfish autonomous agents that strategically interact to acquire dynamically available spectrum opportunities. Our main focus is on developing solutions for wireless users to successfully compete with each other for the limited and time-varying spectrum opportunities, given experienced dynamics in the wireless network. To analyze the interactions among users given the environment disturbance, we propose a stochastic game framework for modeling how the competition among users for spectrum opportunities evolves over time. At each stage of the stochastic game, a central spectrum moderator (CSM) auctions the available resources, and the users strategically bid for the required resources. The joint bid actions affect the resource allocation and, hence, the rewards and future strategies of all users. Based on the observed resource allocations and corresponding rewards, we propose a best-response learning algorithm that can be deployed by wireless users to improve their bidding policy at each stage. The simulation results show that by deploying the proposed best-response learning algorithm, the wireless users can significantly improve their own bidding strategies and, hence, their performance in terms of both the application quality and the incurred cost for the used resources.
---
paper_title: Distributed reduced-state SARSA algorithm for dynamic channel allocation in cellular networks featuring traffic mobility

paper_content:

This paper presents a distributed reinforcement learning solution to the problem of dynamic channel allocation for cellular telecommunication networks in the presence of mobile call handoffs. The performance of various dynamic channel allocation schemes are compared via extensive computer simulations, and it is shown that a reduced-state SARSA reinforcement learning algorithm can achieve superior new call and handoff blocking probabilities. A new distributed reduced state SARSA algorithm is also developed which uses only local environment information readily available to the learning agent. By way of computer simulations, the distributed SARSA algorithm is shown to be capable of producing call blocking probabilities that are comparable to those obtained by the centralised learning agent.
---
paper_title: Packet Routing in Dynamically Changing Networks: A Reinforcement Learning Approach

paper_content:

This paper describes the Q-routing algorithm for packet routing, in which a reinforcement learning module is embedded into each node of a switching network. Only local communication is used by each node to keep accurate statistics on which routing decisions lead to minimal delivery times. In simple experiments involving a 36-node, irregularly connected network, Q-routing proves superior to a nonadaptive algorithm based on precomputed shortest paths and is able to route efficiently even when critical aspects of the simulation, such as the network load, are allowed to vary dynamically. The paper concludes with a discussion of the tradeoff between discovering shortcuts and maintaining stable policies.
---
paper_title: Dynamic channel allocation for mobile cellular traffic using reduced-state reinforcement learning

paper_content:

This paper presents a reduced-state reinforcement learning solution to the dynamic channel allocation problem in cellular telecommunication networks featuring mobile traffic and call handoffs. We examine the performance of table-based function representation used in conjunction with the on-policy reinforcement learning algorithm SARSA and show that the policy obtained using a reduced-state table-based technique provides an online dynamic channel allocation solution with superior performance in terms of new call and handoff blocking probability as well as significantly reduced memory requirements. The superior performance of the proposed state-reduced technique is illustrated in simulation examples.
---
paper_title: Online Reinforcement Learning for Dynamic Multimedia Systems

paper_content:

In our previous work, we proposed a systematic cross-layer framework for dynamic multimedia systems, which allows each layer to make autonomous and foresighted decisions that maximize the system's long-term performance, while meeting the application's real-time delay constraints. The proposed solution solved the cross-layer optimization offline, under the assumption that the multimedia system's probabilistic dynamics were known a priori, by modeling the system as a layered Markov decision process. In practice, however, these dynamics are unknown a priori and, therefore, must be learned online. In this paper, we address this problem by allowing the multimedia system layers to learn, through repeated interactions with each other, to autonomously optimize the system's long-term performance at run-time. The two key challenges in this layered learning setting are: (i) each layer's learning performance is directly impacted by not only its own dynamics, but also by the learning processes of the other layers with which it interacts; and (ii) selecting a learning model that appropriately balances time-complexity (i.e., learning speed) with the multimedia system's limited memory and the multimedia application's real-time delay constraints. We propose two reinforcement learning algorithms for optimizing the system under different design constraints: the first algorithm solves the cross-layer optimization in a centralized manner and the second solves it in a decentralized manner. We analyze both algorithms in terms of their required computation, memory, and interlayer communication overheads. After noting that the proposed reinforcement learning algorithms learn too slowly, we introduce a complementary accelerated learning algorithm that exploits partial knowledge about the system's dynamics in order to dramatically improve the system's performance. In our experiments, we demonstrate that decentralized learning can perform equally as well as centralized learning, while enabling the layers to act autonomously. Additionally, we show that existing application-independent reinforcement learning algorithms, and existing myopic learning algorithms deployed in multimedia systems, perform significantly worse than our proposed application-aware and foresighted learning methods.
---
paper_title: A dynamic channel assignment policy through Q-learning

paper_content:

One of the fundamental issues in the operation of a mobile communication system is the assignment of channels to cells and to calls. This paper presents a novel approach to solving the dynamic channel assignment (DCA) problem by using a form of real-time reinforcement learning known as Q-learning in conjunction with neural network representation. Instead of relying on a known teacher the system is designed to learn an optimal channel assignment policy by directly interacting with the mobile communication environment. The performance of the Q-learning based DCA was examined by extensive simulation studies on a 49-cell mobile communication system under various conditions. Comparative studies with the fixed channel assignment (FCA) scheme and one of the best dynamic channel assignment strategies, MAXAVAIL, have revealed that the proposed approach is able to perform better than the FCA in various situations and capable of achieving a performance similar to that achieved by the MAXAVAIL, but with a significantly reduced computational complexity.
---
paper_title: Cross-Layer Rate and Power Adaptation Strategies for IR-HARQ Systems over Fading Channels with Memory: A SMDP-Based Approach

paper_content:

Incremental-redundancy hybrid automatic repeat- request (IR-HARQ) schemes are proposed in several wireless standards for increased throughput-efficiency and greater reliability. We investigate transmit power and modulation order adaptation strategies for the IR-HARQ schemes over correlated Rayleigh fading channels using semi-Markov decision process-based model. In order to jointly analyze physical layer and link layer, transmitter model incorporates a finite-size buffer that receives randomly varying traffic from a higher layer application. It is assumed that channel variations can be modeled with a first-order Markov chain. We show that the optimal transmission power and rate adaptation laws under buffering delay and packet overflow constraints can be obtained using the framework of semi-Markov decision process. We discuss three different adaptation models for the IR-HARQ schemes and compare their performances with the non-adaptive scheme. It is shown that unique optimal policy exists for each case and it can be computed using linear programming approach. This optimal policy is then applied for realistic channel fading and incoming traffic samples to evaluate its performance for both hard-decision and soft-decision decoding. Simulation results in general point out that substantial power savings can be achieved using adaptation and also if the transmission-delay requirements are relaxed.
---
paper_title: Towards a Unified Theory of State Abstraction for MDPs

paper_content:

State abstraction (or state aggregation) has been extensively studied in the fields of artificial intelligence and operations research. Instead of working in the ground state space, the decision maker usually finds solutions in the abstract state space much faster by treating groups of states as a unit by ignoring irrelevant state information. A number of abstractions have been proposed and studied in the reinforcement-learning and planning literatures, and positive and negative results are known. We provide a unified treatment of state abstraction for Markov decision processes. We study five particular abstraction schemes, some of which have been proposed in the past in different forms, and analyze their usability for planning and learning.
---
paper_title: Unified framework for optimal video streaming

paper_content:

We study the problem of how to stream layered video (live and stored) over a lossy packet network in order to optimize the video quality that is rendered at the receiver. We present a unified framework that combines scheduling, FEC error protection, and decoder error concealment. In the context of the unified framework, we study both the case of a channel with perfect state information and the case of a channel with imperfect state information (delayed or lost feedback). We adapt the theory of infinite-horizon, average-reward Markov decision processes (MDPs) with average-cost constraints to the problem. Based on simulations with MPEG-4 FGS video, we show that (1) optimizing together scheduling, FEC error correction and error concealment improves performance significantly and (2) policies with static error protection give near-optimal performance. We also find that degradations in quality for a channel with imperfect state information are small; thus our MDP approach is suitable for networks with long end-to-end delays
---
paper_title: Markov Processes For Stochastic Modeling

paper_content:

Markov processes are used to model systems with limited memory. They are used in many areas including communications systems, transportation networks, image segmentation and analysis, biological systems and DNA sequence analysis, random atomic motion and diffusion in physics, social mobility, population studies, epidemiology, animal and insect migration, queuing systems, resource management, dams, financial engineering, actuarial science, and decision systems. This book, which is written for upper level undergraduate and graduate students, and researchers, presents a unified presentation of Markov processes.In addition to traditional topics such as Markovian queuing system, the book discusses such topics as continuous-time random walk, correlated random walk, Brownian motion, diffusion processes, hidden Markov models, Markov random fields, Markov point processes and Markov chain Monte Carlo. Continuous-time random walk is currently used in econophysics to model the financial market, which has traditionally been modeled as a Brownian motion.Correlated random walk is popularly used in ecological studies to model animal and insect movement. Hidden Markov models are used in speech analysis and DNA sequence analysis while Markov random fields and Markov point processes are used in image analysis. Thus, the book is designed to have a very broad appeal. It provides the practical, current applications of Markov processes, and covers HMM, Point processes, and Monte Carlo. It includes enough theory to help students gain thorough understanding of the subject. Principles can be immediately applied in many specific research projects, saving researchers time. The end of chapter exercises provide reinforcement, practice and increased understanding to the student.
---
paper_title: A Q-Learning-Based Dynamic Channel Assignment Technique for Mobile Communication Systems

paper_content:

This paper deals with the problem of channel assignment in mobile communication systems. In particular, we propose an alternative approach to solving the dynamic channel assignment (DCA) problem through a form of real-time reinforcement learning known as Q learning. Instead of relying on a known teacher, the system is designed to learn an optimal assignment policy by directly interacting with the mobile communication environment. The performance of the Q-learning-based DCA was examined by extensive simulation studies on a 49-cell mobile communication system under various conditions including homogeneous and inhomogeneous traffic distributions, time-varying traffic patterns, and channel failures. Comparative studies with the fixed channel assignment (FCA) scheme and one of the best dynamic channel assignment strategies (MAXAVAIL) have revealed that the proposed approach is able to perform better than the FCA in various situations and is capable of achieving a similar performance to that achieved by MAXAVAIL, but with a significantly reduced computational complexity.
---
paper_title: Spectrum Access Games and Strategic Learning in Cognitive Radio Networks for Delay-Critical Applications

paper_content:

With the current proliferation of high bandwidth and delay-sensitive multimedia applications and services, each wireless user will try to maximize its utility by acquiring as much spectrum resources as possible unless a preemptive mechanism exists in the network. Thus, emerging solutions for dynamic spectrum access in cognitive radio networks will need to adopt market-based approaches in order to effectively regulate the available resources. In this paper, we show how various centralized and decentralized spectrum access markets can be designed based on a stochastic game framework, where wireless users (also referred to as secondary users) can compete over time for the dynamically available transmission opportunities (spectrum Bholes(). When operating in such spectrum access Bmarkets,( wireless users become selfish, autonomous agents that strategically interact in order to acquire the necessary spectrum opportunities. We also show how wireless users can successfully compete with each other for the limited and time-varying spectrum opportunities, given the experienced dynamics in the wireless network, by optimiz- ing both their external actions (e.g., the resource bids, power and channel used for transmission, etc.) and their internal actions (e.g., the modulation schemes, etc.). To determine their optimal actions in an informationally decentralized setting, users will need to learn and model directly or indirectly the other users' responses to their external actions. We studied the outcome of various dynamic interactions among self-interested wireless users possessing different knowledge and determine that the proposed framework can lead to multiuser communi- cation systems that achieve new measures of efficiency, rationality and fairness. Lastly, our illustrative results show that the presented game-theoretic solution for wireless resource management enables users deploying enhanced (Bsmarter() learning and communication algorithms and being able to make efficient use of the spectrum resources can derive higher utilities. This presents the designers of wireless devices and systems with important incentives to endow their next- generation products and services with enhanced capabilities to gather information, learn, and strategically compete for resources in the emerging spectrum resource markets made possible by the cognitive radio network technologies.
---
paper_title: Q-learning-based multirate transmission control scheme for RRM in multimedia WCDMA systems

paper_content:

In this paper, a Q-learning-based multirate transmission control (Q-MRTC) scheme for radio resource management in multimedia wide-band code-division multiple access (WCDMA) communication systems is proposed. The multirate transmission control problem is modeled as a Markov decision process where the transmission cost is defined in terms of the quality-of-service (QoS) parameters for enhancing spectrum utilization subject to QoS constraint. We adopt a real-time reinforcement learning algorithm, called Q-learning, to accurately estimate the transmission cost for the MRTC. In the meantime, we successfully employ the feature extraction method and radial basis function network (RBFN) for the Q-function that maps the original state space into a feature vector that represents the resultant interference profile. The state space and memory-storage requirement are then reduced and the convergence property of the Q-learning algorithm is improved. Simulation results show that the Q-MRTC for a multimedia WCDMA system can achieve higher system throughput by an amount of 80% and better users' satisfaction than the interference-based MRTC scheme, while the QoS requirements are guaranteed. Also, compared to the table-lookup method, the storage requirement is reduced by 41%.
---
paper_title: Efficient QoS Provisioning for Adaptive Multimedia in Mobile Communication Networks by Reinforcement Learning *

paper_content:

The scarcity and large fluctuations of link bandwidth in wireless networks have motivated the development of adaptive multimedia services in mobile communication networks, where it is possible to increase or decrease the bandwidth of individual ongoing flows. This paper studies the issues of quality of service (QoS) provisioning in such systems. In particular, call admission control and bandwidth adaptation are formulated as a constrained Markov decision problem. The rapid growth in the number of states and the difficulty in estimating state transition probabilities in practical systems make it very difficult to employ classical methods to find the optimal policy. We present a novel approach that uses a form of discounted reward reinforcement learning known as Q-learning to solve QoS provisioning for wireless adaptive multimedia. Q-learning does not require the explicit state transition model to solve the Markov decision problem; therefore more general and realistic assumptions can be applied to the underlying system model for this approach than in previous schemes. Moreover, the proposed scheme can efficiently handle the large state space and action set of the wireless adaptive multimedia QoS provisioning problem. Handoff dropping probability and average allocated bandwidth are considered as QoS constraints in our model and can be guaranteed simultaneously. Simulation results demonstrate the effectiveness of the proposed scheme in adaptive multimedia mobile communication networks.
---
paper_title: Opportunistic Spectrum Access via Periodic Channel Sensing

paper_content:

The problem of opportunistic access of parallel channels occupied by primary users is considered. Under a continuous-time Markov chain modeling of the channel occupancy by the primary users, a slotted transmission protocol for secondary users using a periodic sensing strategy with optimal dynamic access is proposed. To maximize channel utilization while limiting interference to primary users, a framework of constrained Markov decision processes is presented, and the optimal access policy is derived via a linear program. Simulations are used for performance evaluation. It is demonstrated that periodic sensing yields negligible loss of throughput when the constraint on interference is tight.
---
paper_title: Constrained Markov Decision Processes

paper_content:

INTRODUCTION Examples of Constrained Dynamic Control Problems On Solution Approaches for CMDPs with Expected Costs Other Types of CMDPs Cost Criteria and Assumptions The Convex Analytical Approach and Occupation Measures Linear Programming and Lagrangian Approach for CMDPs About the Methodology The Structure of the Book PART ONE: FINITE MDPS MARKOV DECISION PROCESSES The Model Cost Criteria and the Constrained Problem Some Notation The Dominance of Markov Policies THE DISCOUNTED COST Occupation Measure and the Primal LP Dynamic Programming and Dual LP: the Unconstrained Case Constrained Control: Lagrangian Approach The Dual LP Number of Randomizations THE EXPECTED AVERAGE COST Occupation Measure and the Primal LP Equivalent Linear Program The Dual Program Number of Randomizations FLOW AND SERVICE CONTROL IN A SINGLE-SERVER QUEUE The Model The Lagrangian The Original Constrained Problem Structure of Randomization and Implementation Issues On Coordination Between Controllers Open Questions PART TWO: INFINITE MDPS MDPS WITH INFINITE STATE AND ACTION SPACES The Model Cost Criteria Mixed Policies, and Topologic Structures The Dominance of Markov Policies Aggregation of States Extra Randomization in the Policies Equivalent Quasi-Markov Model and Quasi-Markov Policies THE TOTAL COST: CLASSIFICATION OF MDPS Transient and Absorbing MDPs MDPs With Uniform Lyapunov Functions Equivalence of MDP With Unbounded and bounded costs Properties of MDPs With Uniform Lyapunov Functions Properties for Fixed Initial Distribution Examples of Uniform Lyapunov Functions Contracting MDPs THE TOTAL COST: OCCUPATION MEASURES AND THE PRIMAL LP Occupation Measure Continuity of Occupation Measures More Properties of MDPs Characterization of Achievable Sets of Occupation Measure Relation Between Cost and Occupation Measure Dominating Classes of Policies Equivalent Linear Program The Dual Program THE TOTAL COST: DYNAMIC AND LINEAR PROGRAMMING Non-Constrained Control: Dynamic and Linear Programming Superharmonic Functions and Linear Programming Set of Achievable Costs Constrained Control: Lagrangian Approach The Dual LP State Truncation A Second LP Approach for Optimal Mixed Policies More on Unbound Costs THE DISCOUNTED COST The Equivalent Total Cost Model Occupation Measure and LP Non-negative Immediate Cost Weak Contracting Assumptions and Lyapunov Functions Example: Flow and Service Control THE EXPECTED AVERAGE COST Occupation Measures Completeness Properties of Stationary Policies Relation Between Cost and Occupation Measure Dominating Classes of Policies Equivalent Linear Program The Dual Program The Contracting Framework Other Conditions for the Uniform Integrability The Case of Uniform Lyapunov Conditions EXPECTED AVERAGE COST: DYNAMIC PROGRAMMING AND LP The Non-Constrained Case: Optimality Inequality Non-Constrained Control: Cost Bounded Below Dynamic Programming and Uniform Lyapunov Function Super-Harmonic Functions and Linear Programming Set of Achievable Costs Constrained Control: Lagrangian Approach The Dual LP A Second LP Approach for Optimal Mixed Policies PART THREE: ASYMPTOTIC METHODS AND APPROXIMATIONS SENSITIVITY ANALYSIS Introduction Approximation of the Values Approximation and Robustness of the Policies CONVERGENCE OF DISCOUNTED CONSTRAINED MDPS Convergence in the Discount Factor Convergence to the Expected Average Cost The Case of Uniform Lyapunov Function CONVERGENCE AS THE HORIZON TENDS TO INFINITY The Discounted Cost The Expected Average Cost: Stationary Policies The Expected Average Cost: General Policies STATE TRUNCATION AND APPROXIMATION The Approximating sets of States Scheme I: the Total Cost Scheme II: the Total Cost Scheme III: the Total Cost The Expected Average Cost Infinite MDPs: on the Number of Randomizations APPENDIX: CONVERGENCE OF PROBABILITY MEASURES REFERENCES LIST OF SYMBOLS AND NOTATION INDEX
---
paper_title: A New QoS Provisioning Method for Adaptive Multimedia in Wireless Networks

paper_content:

Future wireless networks are designed to support adaptive multimedia by controlling individual ongoing flows to increase or decrease their bandwidths in response to changes in traffic load. There is growing interest in quality-of-service (QoS) provisioning under this adaptive multimedia framework, in which a bandwidth adaptation algorithm needs to be used in conjunction with the call admission control algorithm. This paper presents a novel method for QoS provisioning via average reward reinforcement learning in conjunction with stochastic approximation, which can maximize the network revenue subject to several predetermined QoS constraints. Unlike other model-based algorithms (e.g., linear programming), our scheme does not require explicit state transition probabilities, and therefore, the assumptions behind the underlying system model are more realistic than those in previous schemes. In addition, when we consider the status of neighboring cells, the proposed scheme can dynamically adapt to changes in traffic condition. Moreover, the algorithm can control the bandwidth adaptation frequency effectively by accounting for the cost of bandwidth switching in the model. The effectiveness of the proposed approach is demonstrated using simulation results in adaptive multimedia wireless networks.
---
paper_title: Learning Interference Strategies in Cognitive ARQ Networks

paper_content:

Cognitive radios, which enable the coexistence on the same bandwidth of licensed primary and unlicensed secondary users, have the potential for dramatically increasing the efficiency of wireless networks. In this paper, we propose an on line learning algorithm to optimize the transmission strategy of secondary users in interference mitigation scenarios, where the secondary users are allowed to superimpose their transmission onto those of the primary users. Due to practical imitations, the secondary users have access to only a fraction of the current state of the primary users'' network. Therefore, the strategy of the secondary users is defined on a reduced state space. Numerical results show that the proposed practical learning algorithm operates close to the performance of the system under full knowledge.
---
paper_title: Reinforcement Learning in POMDP ’ s via Direct Gradient Ascent

paper_content:

This paper discusses theoretical and experimental aspects of gradient-based approaches to the direct optimization of policy performance in controlled POMDPs. We introduce GPOMDP, a REINFORCE-like algorithm for estimating an approximation to the gradient of the average reward as a function of the parameters of a stochastic policy. The algorithm’s chief advantages are that it requires only a single sample path of the underlying Markov chain, it uses only one free parameter 2 [0; 1), which has a natural interpretation in terms of bias-variance trade-off, and it requires no knowledge of the underlying state. We prove convergence of GPOMDP and show how the gradient estimates produced by GPOMDP can be used in a conjugate-gradient procedure to find local optima of the average reward.
---
paper_title: Actor-Critic--Type Learning Algorithms for Markov Decision Processes

paper_content:

Algorithms for learning the optimal policy of a Markov decision process (MDP) based on simulated transitions are formulated and analyzed. These are variants of the well-known "actor-critic" (or "adaptive critic") algorithm in the artificial intelligence literature. Distributed asynchronous implementations are considered. The analysis involves two time scale stochastic approximations.
---
paper_title: A Learning Framework for Cognitive Interference Networks with Partial and Noisy Observations

paper_content:

An algorithm for the optimization of secondary user's transmission strategies in cognitive networks with imperfect network state observations is proposed. The secondary user minimizes the time average of a cost function while generating a bounded performance loss to the primary users' network. The state of the primary users' network, defined as a collection of variables describing features of the network (e.g., buffer state, ARQ state) evolves over time according to a homogeneous Markov process. The statistics of the Markov process is dependent on the strategy of the secondary user and, thus, the instantaneous idleness/transmission action of the secondary user has a long-term impact on the temporal evolution of the network. The Markov process generates a sequence of states in the state space of the network that projects onto a sequence of observations in the observation space, that is, the collection of all the observations of the secondary user. Based on the sequence of observations, the proposed algorithm iteratively optimizes the strategy of the secondary users with no a priori knowledge of the statistics of the Markov process and of the state-observation probability map.
---
paper_title: A reinforcement learning approach to call admission and call dropping control in links with variable capacity

paper_content:

This paper defines a reinforcement learning (RL) approach to call control algorithms in links with variable capacity supporting multiple classes of service. The novelties of the document are the following: i) the problem is modeled as a constrained Markov decision process (MDP); ii) the constrained MDP is solved via a RL algorithm by using the Lagrangian approach and state aggregation. The proposed approach is capable of controlling classlevel quality of service in terms of both blocking and dropping probabilities. Numerical simulations show the effectiveness of the approach.
---
paper_title: A reinforcement learning optimization framework for cognitive interference networks

paper_content:

A Reinforcement Learning (RL) algorithm for the optimization of secondary user's transmission strategies in cognitive networks is presented. The secondary user minimizes a cost function while generating a bounded performance loss to the primary users' network. The state of the primary users' network, defined as a collection of variables describing features of the network (e.g., buffer state, ARQ state) evolves over time according to a homogeneous Markov process. The statistics of the Markov process is dependent on the strategy of the secondary user and, thus, the instantaneous idleness/transmission action of the secondary user has a long-term impact on the temporal evolution of the network. The proposed RL algorithm finds the optimal randomized past-independent policy from a sample-path of state-cost observations without any a priori knowledge of the statistics of the Markov process. The performance and structure of the policy resulting from the proposed RL algorithm is compared to those of the policy identified by the algorithm in [1].
---
paper_title: A survey on 3GPP heterogeneous networks

paper_content:

As the spectral efficiency of a point-to-point link in cellular networks approaches its theoretical limits, with the forecasted explosion of data traffic, there is a need for an increase in the node density to further improve network capacity. However, in already dense deployments in today's networks, cell splitting gains can be severely limited by high inter-cell interference. Moreover, high capital expenditure cost associated with high power macro nodes further limits viability of such an approach. This article discusses the need for an alternative strategy, where low power nodes are overlaid within a macro network, creating what is referred to as a heterogeneous network. We survey current state of the art in heterogeneous deployments and focus on 3GPP LTE air interface to describe future trends. A high-level overview of the 3GPP LTE air interface, network nodes, and spectrum allocation options is provided, along with the enabling mechanisms for heterogeneous deployments. Interference management techniques that are critical for LTE heterogeneous deployments are discussed in greater detail. Cell range expansion, enabled through cell biasing and adaptive resource partitioning, is seen as an effective method to balance the load among the nodes in the network and improve overall trunking efficiency. An interference cancellation receiver plays a crucial role in ensuring acquisition of weak cells and reliability of control and data reception in the presence of legacy signals.
---
paper_title: ${Q}$-Learning Algorithms for Constrained Markov Decision Processes With Randomized Monotone Policies: Application to MIMO Transmission Control

paper_content:

This paper presents novel Q-learning based stochastic control algorithms for rate and power control in V-BLAST transmission systems. The algorithms exploit the supermodularity and monotonic structure results derived in the companion paper. Rate and power control problem is posed as a stochastic optimization problem with the goal of minimizing the average transmission power under the constraint on the average delay that can be interpreted as the quality of service requirement of a given application. Standard Q-learning algorithm is modified to handle the constraints so that it can adaptively learn structured optimal policy for unknown channel/traffic statistics. We discuss the convergence of the proposed algorithms and explore their properties in simulations. To address the issue of unknown transmission costs in an unknown time-varying environment, we propose the variant of Q-learning algorithm in which power costs are estimated in online fashion, and we show that this algorithm converges to the optimal solution as long as the power cost estimates are asymptotically unbiased
---
paper_title: A constrained MDP-based vertical handoff decision algorithm for 4G heterogeneous wireless networks

paper_content:

The 4th generation wireless communication systems aim to provide users with the convenience of seamless roaming among heterogeneous wireless access networks. To achieve this goal, the support of vertical handoff is important in mobility management. This paper focuses on the vertical handoff decision algorithm, which determines the criteria under which vertical handoff should be performed. The problem is formulated as a constrained Markov decision process. The objective is to maximize the expected total reward of a connection subject to the expected total access cost constraint. In our model, a benefit function is used to assess the quality of the connection, and a penalty function is used to model the signaling incurred and call dropping. The user's velocity and location information are also considered when making handoff decisions. The policy iteration and Q-learning algorithms are employed to determine the optimal policy. Structural results on the optimal vertical handoff policy are derived by using the concept of supermodularity. We show that the optimal policy is a threshold policy in bandwidth, delay, and velocity. Numerical results show that our proposed vertical handoff decision algorithm outperforms other decision schemes in a wide range of conditions such as variations on connection duration, user's velocity, user's budget, traffic type, signaling cost, and monetary access cost.
---
paper_title: Efficient QoS Provisioning for Adaptive Multimedia in Mobile Communication Networks by Reinforcement Learning *

paper_content:

The scarcity and large fluctuations of link bandwidth in wireless networks have motivated the development of adaptive multimedia services in mobile communication networks, where it is possible to increase or decrease the bandwidth of individual ongoing flows. This paper studies the issues of quality of service (QoS) provisioning in such systems. In particular, call admission control and bandwidth adaptation are formulated as a constrained Markov decision problem. The rapid growth in the number of states and the difficulty in estimating state transition probabilities in practical systems make it very difficult to employ classical methods to find the optimal policy. We present a novel approach that uses a form of discounted reward reinforcement learning known as Q-learning to solve QoS provisioning for wireless adaptive multimedia. Q-learning does not require the explicit state transition model to solve the Markov decision problem; therefore more general and realistic assumptions can be applied to the underlying system model for this approach than in previous schemes. Moreover, the proposed scheme can efficiently handle the large state space and action set of the wireless adaptive multimedia QoS provisioning problem. Handoff dropping probability and average allocated bandwidth are considered as QoS constraints in our model and can be guaranteed simultaneously. Simulation results demonstrate the effectiveness of the proposed scheme in adaptive multimedia mobile communication networks.
---
paper_title: Decentralized cognitive MAC for opportunistic spectrum access in ad hoc networks: A POMDP framework

paper_content:

We propose decentralized cognitive MAC protocols that allow secondary users to independently search for spectrum opportunities without a central coordinator or a dedicated communication channel. Recognizing hardware and energy constraints, we assume that a secondary user may not be able to perform full-spectrum sensing or may not be willing to monitor the spectrum when it has no data to transmit. We develop an analytical framework for opportunistic spectrum access based on the theory of partially observable Markov decision process (POMDP). This decision-theoretic approach integrates the design of spectrum access protocols at the MAC layer with spectrum sensing at the physical layer and traffic statistics determined by the application layer of the primary network. It also allows easy incorporation of spectrum sensing error and constraint on the probability of colliding with the primary users. Under this POMDP framework, we propose cognitive MAC protocols that optimize the performance of secondary users while limiting the interference perceived by primary users. A suboptimal strategy with reduced complexity yet comparable performance is developed. Without additional control message exchange between the secondary transmitter and receiver, the proposed decentralized protocols ensure synchronous hopping in the spectrum between the transmitter and the receiver in the presence of collisions and spectrum sensing errors
---
paper_title: QoS Routing in MANETS with Imprecise Information Using Actor-Critic Reinforcement Learning

paper_content:

This paper proposes a path discovery scheme which supports delay-constrained least cost routing in MANETs. The aim of the scheme is to maximise the probability of success in finding feasible paths while maintaining communication overhead under control in presence of information uncertainty. The problem is viewed as a partially observable Markov decision process (POMDP) and is solved using an actor-critic reinforcement learning (RL) method. The scheme relies on approximate belief states of the environment which captures the network state uncertainty. Numerical results carried out under various scenarios of state uncertainty and stringent QoS requirements show that the proposed RL framework can lead to more efficient control of search messages, i.e., a reduction of up to 63% of average number of search messages with marginal reduction of up to 3 % in success ratio in comparison with a flooding scheme.
---
paper_title: A New QoS Provisioning Method for Adaptive Multimedia in Wireless Networks

paper_content:

Future wireless networks are designed to support adaptive multimedia by controlling individual ongoing flows to increase or decrease their bandwidths in response to changes in traffic load. There is growing interest in quality-of-service (QoS) provisioning under this adaptive multimedia framework, in which a bandwidth adaptation algorithm needs to be used in conjunction with the call admission control algorithm. This paper presents a novel method for QoS provisioning via average reward reinforcement learning in conjunction with stochastic approximation, which can maximize the network revenue subject to several predetermined QoS constraints. Unlike other model-based algorithms (e.g., linear programming), our scheme does not require explicit state transition probabilities, and therefore, the assumptions behind the underlying system model are more realistic than those in previous schemes. In addition, when we consider the status of neighboring cells, the proposed scheme can dynamically adapt to changes in traffic condition. Moreover, the algorithm can control the bandwidth adaptation frequency effectively by accounting for the cost of bandwidth switching in the model. The effectiveness of the proposed approach is demonstrated using simulation results in adaptive multimedia wireless networks.
---
paper_title: Multiagent Q-learning for aloha-like spectrum access in cognitive radio systems

paper_content:

An Aloha-like spectrum access scheme without negotiation is considered for multiuser and multichannel cognitive radio systems. To avoid collisions incurred by the lack of coordination, each secondary user learns how to select channels according to its experience. Multiagent reinforcement leaning (MARL) is applied for the secondary users to learn good strategies of channel selection. Specifically, the framework of Q-learning is extended from single user case to multiagent case by considering other secondary users as a part of the environment. The dynamics of the Q-learning are illustrated using a Metrick-Polak plot, which shows the traces of Q-values in the two-user case. For both complete and partial observation cases, rigorous proofs of the convergence of multiagent Q-learning without communications, under certain conditions, are provided using the Robins-Monro algorithm and contraction mapping, respectively. The learning performance (speed and gain in utility) is evaluated by numerical simulations.
---
paper_title: Learning Interference Strategies in Cognitive ARQ Networks

paper_content:

Cognitive radios, which enable the coexistence on the same bandwidth of licensed primary and unlicensed secondary users, have the potential for dramatically increasing the efficiency of wireless networks. In this paper, we propose an on line learning algorithm to optimize the transmission strategy of secondary users in interference mitigation scenarios, where the secondary users are allowed to superimpose their transmission onto those of the primary users. Due to practical imitations, the secondary users have access to only a fraction of the current state of the primary users'' network. Therefore, the strategy of the secondary users is defined on a reduced state space. Numerical results show that the proposed practical learning algorithm operates close to the performance of the system under full knowledge.
---
paper_title: Game Theory in Wireless and Communication Networks

paper_content:

This unified treatment of game theory focuses on finding state-of-the-art solutions to issues surrounding the next generation of wireless and communication networks. Future networkswillrelyonautonomousanddistributedarchitecturestoimprovetheefficiency and flexibility of mobile applications, and game theory provides the ideal framework for designing efficient and robust distributed algorithms. This book enables readers to develop a solid understanding of game theory, its applications, and its use as an effective tool for addressing various problems in wireless communication and networking. The key results and tools of game theory are covered, as are various real-world technologies including 3G/4G networks, wireless LANs, sensor networks, cognitive networks, and Internet networks. The book also covers a wide range of techniques for modeling, designing, and analyzing communication networks using game theory, as well as state-of-the-art distributed design techniques. This is an ideal resource for communications engineers, researchers, and graduate and undergraduate students.
---
paper_title: A Stochastic Approximation Method

paper_content:

Let M(x) denote the expected value at level x of the response to a certain experiment. M(x) is assumed to be a monotone function of x but is unknown to the experimenter, and it is desired to find the solution x = θ of the equation M(x) = α, where a is a given constant. We give a method for making successive experiments at levels x1, x2, ··· in such a way that xn will tend to θ in probability.
---
paper_title: Distributed reduced-state SARSA algorithm for dynamic channel allocation in cellular networks featuring traffic mobility

paper_content:

This paper presents a distributed reinforcement learning solution to the problem of dynamic channel allocation for cellular telecommunication networks in the presence of mobile call handoffs. The performance of various dynamic channel allocation schemes are compared via extensive computer simulations, and it is shown that a reduced-state SARSA reinforcement learning algorithm can achieve superior new call and handoff blocking probabilities. A new distributed reduced state SARSA algorithm is also developed which uses only local environment information readily available to the learning agent. By way of computer simulations, the distributed SARSA algorithm is shown to be capable of producing call blocking probabilities that are comparable to those obtained by the centralised learning agent.
---
paper_title: Dynamic channel allocation for mobile cellular traffic using reduced-state reinforcement learning

paper_content:

This paper presents a reduced-state reinforcement learning solution to the dynamic channel allocation problem in cellular telecommunication networks featuring mobile traffic and call handoffs. We examine the performance of table-based function representation used in conjunction with the on-policy reinforcement learning algorithm SARSA and show that the policy obtained using a reduced-state table-based technique provides an online dynamic channel allocation solution with superior performance in terms of new call and handoff blocking probability as well as significantly reduced memory requirements. The superior performance of the proposed state-reduced technique is illustrated in simulation examples.
---
paper_title: A Learning Framework for Cognitive Interference Networks with Partial and Noisy Observations

paper_content:

An algorithm for the optimization of secondary user's transmission strategies in cognitive networks with imperfect network state observations is proposed. The secondary user minimizes the time average of a cost function while generating a bounded performance loss to the primary users' network. The state of the primary users' network, defined as a collection of variables describing features of the network (e.g., buffer state, ARQ state) evolves over time according to a homogeneous Markov process. The statistics of the Markov process is dependent on the strategy of the secondary user and, thus, the instantaneous idleness/transmission action of the secondary user has a long-term impact on the temporal evolution of the network. The Markov process generates a sequence of states in the state space of the network that projects onto a sequence of observations in the observation space, that is, the collection of all the observations of the secondary user. Based on the sequence of observations, the proposed algorithm iteratively optimizes the strategy of the secondary users with no a priori knowledge of the statistics of the Markov process and of the state-observation probability map.
---
paper_title: A reinforcement learning optimization framework for cognitive interference networks

paper_content:

A Reinforcement Learning (RL) algorithm for the optimization of secondary user's transmission strategies in cognitive networks is presented. The secondary user minimizes a cost function while generating a bounded performance loss to the primary users' network. The state of the primary users' network, defined as a collection of variables describing features of the network (e.g., buffer state, ARQ state) evolves over time according to a homogeneous Markov process. The statistics of the Markov process is dependent on the strategy of the secondary user and, thus, the instantaneous idleness/transmission action of the secondary user has a long-term impact on the temporal evolution of the network. The proposed RL algorithm finds the optimal randomized past-independent policy from a sample-path of state-cost observations without any a priori knowledge of the statistics of the Markov process. The performance and structure of the policy resulting from the proposed RL algorithm is compared to those of the policy identified by the algorithm in [1].
---
paper_title: Cooperative Multi-Agent Learning: The State of the Art

paper_content:

Cooperative multi-agent systems (MAS) are ones in which several agents attempt, through their interaction, to jointly solve tasks or to maximize utility. Due to the interactions among the agents, multi-agent problem complexity can rise rapidly with the number of agents or their behavioral sophistication. The challenge this presents to the task of programming solutions to MAS problems has spawned increasing interest in machine learning techniques to automate the search and optimization process. We provide a broad survey of the cooperative multi-agent learning literature. Previous surveys of this area have largely focused on issues common to specific subareas (for example, reinforcement learning, RL or robotics). In this survey we attempt to draw from multi-agent learning work in a spectrum of areas, including RL, evolutionary computation, game theory, complex systems, agent modeling, and robotics. We find that this broad view leads to a division of the work into two categories, each with its own special issues: applying a single learner to discover joint solutions to multi-agent problems (team learning), or using multiple simultaneous learners, often one per agent (concurrent learning). Additionally, we discuss direct and indirect communication in connection with learning, plus open issues in task decomposition, scalability, and adaptive dynamics. We conclude with a presentation of multi-agent learning problem domains, and a list of multi-agent learning resources.
---
paper_title: A dynamic channel assignment policy through Q-learning

paper_content:

One of the fundamental issues in the operation of a mobile communication system is the assignment of channels to cells and to calls. This paper presents a novel approach to solving the dynamic channel assignment (DCA) problem by using a form of real-time reinforcement learning known as Q-learning in conjunction with neural network representation. Instead of relying on a known teacher the system is designed to learn an optimal channel assignment policy by directly interacting with the mobile communication environment. The performance of the Q-learning based DCA was examined by extensive simulation studies on a 49-cell mobile communication system under various conditions. Comparative studies with the fixed channel assignment (FCA) scheme and one of the best dynamic channel assignment strategies, MAXAVAIL, have revealed that the proposed approach is able to perform better than the FCA in various situations and capable of achieving a performance similar to that achieved by the MAXAVAIL, but with a significantly reduced computational complexity.
---
paper_title: A reinforcement learning approach to automatic generation control

paper_content:

This paper formulates the automatic generation control (AGC) problem as a stochastic multistage decision problem. A strategy for solving this new AGC problem formulation is presented by using a reinforcement learning (RL) approach This method of obtaining an AGC controller does not depend on any knowledge of the system model and more importantly it admits considerable flexibility in defining the control objective. Two specific RL based AGC algorithms are presented. The first algorithm uses the traditional control objective of limiting area control error (ACE) excursions, where as, in the second algorithm, the controller can restore the load-generation balance by only monitoring deviation in tie line flows and system frequency and it does not need to know or estimate the composite ACE signal as is done by all current approaches. The effectiveness and versatility of the approaches has been demonstrated using a two area AGC model. (C) 2002 Elsevier Science B.V. All rights reserved.
---
paper_title: Self-Organization in Small Cell Networks: A Reinforcement Learning Approach

paper_content:

In this paper, a decentralized and self-organizing mechanism for small cell networks (such as micro-, femto- and picocells) is proposed. In particular, an application to the case in which small cell networks aim to mitigate the interference caused to the macrocell network, while maximizing their own spectral efficiencies, is presented. The proposed mechanism is based on new notions of reinforcement learning (RL) through which small cells jointly estimate their time-average performance and optimize their probability distributions with which they judiciously choose their transmit configurations. Here, a minimum signal to interference plus noise ratio (SINR) is guaranteed at the macrocell user equipment (UE), while the small cells maximize their individual performances. The proposed RL procedure is fully distributed as every small cell base station requires only an observation of its instantaneous performance which can be obtained from its UE. Furthermore, it is shown that the proposed mechanism always converges to an epsilon Nash equilibrium when all small cells share the same interest. In addition, this mechanism is shown to possess better convergence properties and incur less overhead than existing techniques such as best response dynamics, fictitious play or classical RL. Finally, numerical results are given to validate the theoretical findings, highlighting the inherent tradeoffs facing small cells, namely exploration/exploitation, myopic/foresighted behavior and complete/incomplete information.
---
paper_title: Distributed Q-Learning for Aggregated Interference Control in Cognitive Radio Networks

paper_content:

This paper deals with the problem of aggregated interference generated by multiple cognitive radios (CRs) at the receivers of primary (licensed) users. In particular, we consider a secondary CR system based on the IEEE 802.22 standard for wireless regional area networks (WRANs), and we model it as a multiagent system where the multiple agents are the different secondary base stations in charge of controlling the secondary cells. We propose a form of real-time multiagent reinforcement learning, which is known as decentralized Q-learning, to manage the aggregated interference generated by multiple WRAN systems. We consider both situations of complete and partial information about the environment. By directly interacting with the surrounding environment in a distributed fashion, the multiagent system is able to learn, in the first case, an efficient policy to solve the problem and, in the second case, a reasonably good suboptimal policy. Computational and memory requirement considerations are also presented, discussing two different options for uploading and processing the learning information. Simulation results, which are presented for both the upstream and downstream cases, reveal that the proposed approach is able to fulfill the primary-user interference constraints, without introducing signaling overhead in the system.
---
paper_title: Distributed Q-learning based dynamic spectrum management in cognitive cellular systems: Choosing the right learning rate

paper_content:

This paper presents the concept of the Win-or-Learn-Fast (WoLF) variable learning rate for distributed Q-learning based dynamic spectrum management algorithms. It demonstrates the importance of choosing the learning rate correctly by simulating a large scale stadium temporary event network. The results show that using the WoLF variable learning rate provides a significant improvement in quality of service, in terms of the probabilities of file blocking and interruption, over typical values of fixed learning rates. The results have also demonstrated that it is possible to provide a better and more robust quality of service using distributed Q-learning with a WoLF variable learning rate, than a spectrum sensing based opportunistic spectrum access scheme, but with no spectrum sensing involved.
---
paper_title: Dynamic Inter-Cell Interference Coordination in HetNets: A reinforcement learning approach

paper_content:

In this paper, we investigate enhanced Inter-Cell Interference Coordination (e-ICIC) techniques for Heterogeneous Networks (HetNets), consisting of a mix of macro and picocells. We model this strategic coexistence as a multi-agent system in which decentralized interference management and cell association strategies inspired from Reinforcement Learning (RL) are devised. Specifically, we focus on time and frequency domain ICIC techniques in which picocells optimally learn their cell range bias and downlink transmit power allocation. In turn, the macrocell optimizes its transmission by serving its own users while adhering to the picocell interference constraint. To substantiate our theoretical findings, system level simulations are carried out in which our proposed solution is compared with a number of existing ICIC approaches, such as resource partitioning, fixed cell range expansion (CRE) and fixed Almost Blank Subframe (ABS). Interestingly, our proposed solution is shown to yield substantial gains of up to 125% compared to static ICIC approaches.
---
paper_title: Cooperation and Learning in Multiuser Opportunistic Spectrum Access

paper_content:

We consider how two secondary users should interact to maximize their total throughput in a two- channel sensing-based opportunistic spectrum access network where spectrum opportunities are time varying and spatially inhomogeneous. By modeling the occupancy of the primary users as discrete-time Markov chains, we obtain the optimal dynamic coordination policy using a partially observable Markov decision process (POMDP) solver. We also develop several tractable approaches - a cooperative multiuser approach based on explicit communication between the secondary users, a learning-based approach involving use of collision feedback information, and a single-user approach based on uncooperative independent decisions. As a baseline we consider the static partitioning policy where both users are allocated a single channel of their own. Simulations comparing the performance of these strategies yield several interesting findings: that significant improvements over static partitioning are possible with the optimal scheme; that the cooperative multiuser approach shows near-optimal performance in all cases; that there are scenarios when learning through collision feedback can be beneficial; and that the single-user approach generally shows poor performance.
---
paper_title: Experience cooperative sharing in cross-layer cognitive radio for real-time multimedia communication

paper_content:

The central problem in cognitive radio (CR) is how to adapt, given a wireless environment, so as to operate while meeting the constraints of a primary incumbent in a spectrum band. Adaptation for transmission of real-time multimedia lends itself to a cross-layer approach. This paper discusses a cross-layer CR scheme for real-time multimedia transmission that jointly adapt transmit bit rate and source-channel coding when sharing the spectrum with a primary network through DS-CDMA. While a cross-layer approach results in a notable reduction in distortion and congestion rate, it increases the complexity of the algorithm. This issue is addressed by introducing a novel cross-layer cooperative scheme that without performance loss reduces by as much as thirty times the number of iterations needed to achieve convergence by the cognitive algorithm. This scheme extends to a cross-layer setting, the docitive paradigm, by having secondary nodes share with a newcomer node their learned awareness of the environment and the associated results for actions.
---
paper_title: Distributed Q-Learning for Interference Control in OFDMA-Based Femtocell Networks

paper_content:

This paper proposes a self-organized power allocation technique to solve the interference problem caused by a femtocell network operating in the same channel as an orthogonal frequency division multiple access cellular network. We model the femto network as a multi-agent system where the different femto base stations are the agents in charge of managing the radio resources to be allocated to their femtousers. We propose a form of real-time multi-agent reinforcement learning, known as decentralized Q-learning, to manage the interference generated to macro-users. By directly interacting with the surrounding environment in a distributed fashion, the multi-agent system is able to learn an optimal policy to solve the interference problem. Simulation results show that the introduction of the femto network increases the system capacity without decreasing the capacity of the macro network.
---
paper_title: Applying multi-agent Q-learning scheme in cognitive wireless mesh networks for green communications

paper_content:

Cognitive wireless mesh networks have great potential to green communication. One of the critical challenges for realizing such networks is how to adaptively match transmit powers and allocate frequency resources among secondary users of the licensed frequency bands whilst maintaining the quality-of-service (QoS) requirement of the primary users, even in mutually entangled interferences environment. In this paper, we discuss the power assignment matching problem in cognitive wireless mesh networks formed by a number of clusters with the consideration of the Signal-to-Interference-plus-Noise Ratio (SINR) requirement of each secondary user (SU), the mean-squared error (MSE) constraint by the primary users, and the energy efficiency. Due to the secondary users' selfish and spontaneous features, the problem is modeled as a stochastic non-cooperative game. We extend the conventional single-agent Q-learning to a non-cooperative multi-agent learning context, using the framework of stochastic non-cooperative games. Within the multi-agent Q-learning processes, a learning SU maintains Q-functions over joint actions set, and performs updating based on the conjecture about the other SUs' behaviors over the current Q-values. Numerical experiments on a hybrid CogMesh consisting two SUs and one specific PU suggest validity and efficiency of the proposed algorithm.
---
paper_title: A Survey of Actor-Critic Reinforcement Learning: Standard and Natural Policy Gradients

paper_content:

Policy-gradient-based actor-critic algorithms are amongst the most popular algorithms in the reinforcement learning framework. Their advantage of being able to search for optimal policies using low-variance gradient estimates has made them useful in several real-life applications, such as robotics, power control, and finance. Although general surveys on reinforcement learning techniques already exist, no survey is specifically dedicated to actor-critic algorithms in particular. This paper, therefore, describes the state of the art of actor-critic algorithms, with a focus on methods that can work in an online setting and use function approximation in order to deal with continuous state and action spaces. After starting with a discussion on the concepts of reinforcement learning and the origins of actor-critic algorithms, this paper describes the workings of the natural gradient, which has made its way into many actor-critic algorithms over the past few years. A review of several standard and natural actor-critic algorithms is given, and the paper concludes with an overview of application areas and a discussion on open issues.
---
paper_title: A Q-Learning-Based Dynamic Channel Assignment Technique for Mobile Communication Systems

paper_content:

This paper deals with the problem of channel assignment in mobile communication systems. In particular, we propose an alternative approach to solving the dynamic channel assignment (DCA) problem through a form of real-time reinforcement learning known as Q learning. Instead of relying on a known teacher, the system is designed to learn an optimal assignment policy by directly interacting with the mobile communication environment. The performance of the Q-learning-based DCA was examined by extensive simulation studies on a 49-cell mobile communication system under various conditions including homogeneous and inhomogeneous traffic distributions, time-varying traffic patterns, and channel failures. Comparative studies with the fixed channel assignment (FCA) scheme and one of the best dynamic channel assignment strategies (MAXAVAIL) have revealed that the proposed approach is able to perform better than the FCA in various situations and is capable of achieving a similar performance to that achieved by MAXAVAIL, but with a significantly reduced computational complexity.
---
paper_title: Distributed Reinforcement Learning Frameworks for Cooperative Retransmission in Wireless Networks

paper_content:

We address the problem of cooperative retransmission in the media access control (MAC) layer of a distributed wireless network with spatial reuse, where there can be multiple concurrent transmissions from the source and relay nodes. We propose a novel Markov decision process (MDP) framework for adjusting the transmission powers and transmission probabilities in the source and relay nodes to achieve the highest network throughput per unit of consumed energy. We also propose distributed methods that avoid solving a centralized MDP model with a large number of states by employing model-free reinforcement learning (RL) algorithms. We show the convergence to a local solution and compute a lower bound for the performance of the proposed RL algorithms. We further empirically confirm that the proposed learning schemes are robust to collisions and are scalable with regard to the network size and can provide significant cooperative diversity while enjoying low complexity and fast convergence.
---
paper_title: Multi Agent Reinforcement Learning Independent vs Cooperative Agents

paper_content:

Intelligent human agents exist in a cooperative social environment that facilitates learning. They learn not only by trial-and-error, but also through cooperation by sharing instantaneous information, episodic experience, and learned knowledge. The key investigations of this paper are, “Given the same number of reinforcement learning agents, will cooperative agents outperform independent agents who do not communicate during learning?” and “What is the price for such cooperation?” Using independent agents as a benchmark, cooperative agents are studied in following ways: (1) sharing sensation, (2) sharing episodes, and (3) sharing learned policies. This paper shows that (a) additional sensation from another agent is beneficial if it can be used efficiently, (b) sharing learned policies or episodes among agents speeds up learning at the cost of communication, and (c) for joint tasks, agents engaging in partnership can significantly outperform independent agents although they may learn slowly in the beginning. These tradeoff's are not just limited to multi-agent reinforcement learning.
---
paper_title: A Q-learning based approach to interference avoidance in self-organized femtocell networks

paper_content:

The femtocell concept is an emerging technology for deploying the next generation of the wireless networks, aiming at indoor coverage enhancement, increasing capacity, and offloading the overlay macrocell traffic. Nevertheless, the detrimental factor in such networks is co-channel interference between macrocells and femtocells, as well as among neighboring femtocells. This in turn can dramatically decrease the overall capacity of the network. In addition, due to their non-coordinated nature, femtocells need to self-organize in a distributed manner not to cause interference on the macrocell, while at the same time managing interference among neighboring femtocells. This paper proposes and analyzes a Reinforcement-Learning (RL) framework where a macrocell network is underlaid with femtocells sharing the same spectrum. A distributed Q-learning algorithm is proposed in which each Femto Base Station/Access Point (FBS/FAP) gradually learns (by interacting with its local environment) through trials and errors, and adapt the channel selection strategy until reaching convergence. The proposed Q-learning algorithm is cast into high level and low level subproblems, in which the former finds in a decentralized way the channel allocation through Q-learning, while the latter computes the optimal power allocation. Investigations show that through learning, femtocells are not only able to self-organize with only local information, but also mitigate their interference towards the macrocell network.
---
paper_title: Sensing time and power allocation for cognitive radios using distributed Q-learning

paper_content:

In cognitive radios systems, the sparse assigned frequency bands are opened to secondary users, provided that the aggregated interferences induced by the secondary transmitters on the primary receivers are negligible. Cognitive radios are established in two steps: the radios firstly sense the available frequency bands and secondly communicate using these bands. In this article, we propose two decentralized resource allocation Q-learning algorithms: the first one is used to share the sensing time among the cognitive radios in a way that maximize the throughputs of the radios. The second one is used to allocate the cognitive radio powers in a way that maximizes the signal on interference-plus-noise ratio (SINR) at the secondary receivers while meeting the primary protection constraint. Numerical results show the convergence of the proposed algorithms and allow the discussion of the exploration strategy, the choice of the cost function and the frequency of execution of each algorithm.
---
paper_title: A learning approach for prioritized handoff channel allocation in mobile multimedia networks

paper_content:

An efficient channel allocation policy that prioritizes handoffs is an indispensable ingredient in future cellular networks in order to support multimedia traffic while ensuring quality of service requirements (QoS). In this paper we study the application of a reinforcement-learning algorithm to develop an alternative channel allocation scheme in mobile cellular networks that supports multiple heterogeneous traffic classes. The proposed scheme prioritizes handoff call requests over new calls and provides differentiated services for different traffic classes with diverse characteristics and quality of service requirements. Furthermore, it is asymptotically optimal, computationally inexpensive, model-free, and can adapt to changing traffic conditions. Simulations are provided to compare the effectiveness of the proposed algorithm with other known resource-sharing policies such as complete sharing and reservation policies
---
paper_title: Efficient Objective Functions for Coordinated Learning in Large-Scale Distributed OSA Systems

paper_content:

In this paper, we derive and evaluate private objective functions for large-scale, distributed opportunistic spectrum access (OSA) systems. By means of any learning algorithms, these derived objective functions enable OSA users to assess, locate, and exploit unused spectrum opportunities effectively by maximizing the users' average received rewards. We consider the elastic traffic model, suitable for elastic applications such as file transfer and web browsing, and in which an SU's received reward increases proportionally to the amount of received service when the amount is higher than a certain threshold. But when this amount is below the threshold, the reward decreases exponentially with the amount of received service. In this model, SUs are assumed to be treated fairly in that the SUs using the same band will roughly receive an equal share of the total amount of service offered by the band. We show that the proposed objective functions are: near-optimal, as they achieve high performances in terms of average received rewards; highly scalable, as they perform well for small- as well as large-scale systems; highly learnable, as they reach up near-optimal values very quickly; and distributive, as they require information sharing only among OSA users belonging to the same band.
---
paper_title: Power allocation with stackelberg game in femtocell networks: a self-learning approach

paper_content:

This paper investigates the energy-efficient power allocation for a two-tier, underlaid femtocell network. The behaviors of the Macrocell Base Station (MBS) and the Femtocell Users (FUs) are modeled hierarchically as a Stackelberg game. The MBS guarantees its own QoS requirement by charging the FUs individually according to the cross-tier interference, and the FUs responds by controlling the local transmit power non-cooperatively. Due to the limit of information exchange in intra- and inter-tiers, a self-learning based strategy-updating mechanism is proposed for each user to learn the equilibrium strategies. In the same Stackelberg-game framework, two different scenarios based on the continuous and discrete power profiles for the FUs are studied, respectively. The self-learning schemes in the two scenarios are designed based on the local best response. By studying the properties of the proposed game in the two situations, the convergence property of the learning schemes is provided. The simulation results are provided to support the theoretical finding in different situations of the proposed game, and the efficiency of the learning schemes is validated.
---
paper_title: Detection of Spectral Resources in Cognitive Radios Using Reinforcement Learning

paper_content:

Available spectrum for wireless communications is a limited resource which gains importance with the increasing demand for mobile communication services with high data rates. Measurements show that assigned frequency bands (FBs) are not used efficiently. One approach for increasing the efficiency in spectrum use is the concept of overlay systems, which can be seen as an enabling technology for cognitive radio and dynamic spectrum access by providing frequency agility. In this paper, we propose an approach for the detection of spectral resources based on reinforcement learning, allowing the cognitive radio to select the FBs with the most available resources.
---
paper_title: Achieving Coverage through Distributed Reinforcement Learning in Wireless Sensor Networks

paper_content:

With the extensive implementations of wireless sensor networks in many areas, it is imperative to have better management of the coverage and energy consumption of such networks. These networks consist of large number of sensor nodes and therefore a multi-agent system approach needs to be taken in order for a more accurate model. Three coordination algorithms are being put to the test in this paper: (i) fully distributed Q-learning which we refer to as independent learner (IL), (ii) distributed value function (DVF) and (iii) an algorithm we developed which is a variation of the IL, coordinated algorithm (COORD). The results show that the IL and DVF algorithm performed for higher sensor node densities but at low sensor node densities, the three algorithms have similar performance.
---
paper_title: Decentralized learning in finite Markov chains

paper_content:

The principal contribution of this paper is a new result on the decentralized control of finite Markov chains with unknown transition probabilities and rewards. One decentralized decision maker is associated with each state in which two or more actions (decisions) are available. Each decision maker uses a simple learning scheme, requiring minimal information, to update its action choice. It is shown that, if updating is done in sufficiently small steps, the group will converge to the policy that maximizes the long-term expected reward per step. The analysis is based on learning in sequential stochastic games and on certain properties, derived in this paper, of ergodic Markov chains.
---
paper_title: Spectrum Management of Cognitive Radio Using Multi-agent Reinforcement Learning

paper_content:

Wireless cognitive radio (CR) is a newly emerging paradigm that attempts to opportunistically transmit in licensed frequencies, without affecting the pre-assigned users of these bands. To enable this functionality, such a radio must predict its operational parameters, such as transmit power and spectrum. These tasks, collectively called spectrum management, is difficult to achieve in a dynamic distributed environment, in which CR users may only take local decisions, and react to the environmental changes. In this paper, we introduce a multi-agent reinforcement learning approach based spectrum management. Our approach uses value functions to evaluate the desirability of choosing different transmission parameters, and enables efficient assignment of spectrums and transmit powers by maximizing long-term reward. We then investigate various real-world scenarios, and compare the communication performance using different sets of learning parameters. We also apply Kanerva-based function approximation to improve our approach's ability to handle large cognitive radio networks and evaluate its effect on communication performance. We conclude that our reinforcement learning based spectrum management can significantly reduce the interference to the licensed users, while maintaining a high probability of successful transmissions in a cognitive radio ad hoc network.
---
paper_title: Experience-weighted Attraction Learning in Normal Form Games

paper_content:

In ‘experience-weighted attraction’ (EWA) learning, strategies have attractions that reflect initial predispositions, are updated based on payoff experience, and determine choice probabilities according to some rule (e.g., logit). A key feature is a parameter δ that weights the strength of hypothetical reinforcement of strategies that were not chosen according to the payoff they would have yielded, relative to reinforcement of chosen strategies according to received payoffs. The other key features are two discount rates, φ and ρ, which separately discount previous attractions, and an experience weight. EWA includes reinforcement learning and weighted fictitious play (belief learning) as special cases, and hybridizes their key elements. When δ= 0 and ρ= 0, cumulative choice reinforcement results. When δ= 1 and ρ=φ, levels of reinforcement of strategies are exactly the same as expected payoffs given weighted fictitious play beliefs. Using three sets of experimental data, parameter estimates of the model were calibrated on part of the data and used to predict a holdout sample. Estimates of δ are generally around .50, φ around .8 − 1, and ρ varies from 0 to φ. Reinforcement and belief-learning special cases are generally rejected in favor of EWA, though belief models do better in some constant-sum games. EWA is able to combine the best features of previous approaches, allowing attractions to begin and grow flexibly as choice reinforcement does, but reinforcing unchosen strategies substantially as belief-based models implicitly do.
---
paper_title: Cognition and Docition in OFDMA-Based Femtocell Networks

paper_content:

We address the coexistence problem between macrocell and femtocell systems by controlling the aggregated interference generated by multiple femtocell base stations at the macrocell receivers in a distributed fashion. We propose a solution based on intelligent and self-organized femtocells implementing a realtime multi-agent reinforcement learning technique, known as decentralized Q- learning. We compare this cognitive approach to a non-cognitive algorithm and to the well known iterative water- filling, showing the general superiority of our scheme in terms of (non-jeopardized) macrocell capacity. Furthermore, in distributed settings of such femtocell networks, the learning may be complex and slow due to mutually impacting decision making processes, which results in a non-stationary environment. We propose a timely solution -referred to as docition- to improve the learning process based on the concept of teaching and expert knowledge sharing in wireless environments. We demonstrate that such an approach improves the femtocells' learning ability and accuracy. We evaluate the docitive paradigm in the context of a 3GPP compliant OFDMA (Orthogonal Frequency Division Multiple Access) femtocell network modeled as a multi-agent system. We propose different docitive algorithms and we show their superiority to the well known paradigm of independent learning in terms of speed of convergence and precision.
---
paper_title: Use of learning, game theory and optimization as biomimetic approaches for Self-Organization in macro-femtocell coexistence

paper_content:

In this paper, we present the use of several Biomimetic approaches for Self Organization (SO) in heterogeneous scenarios where macrocell and femtocell networks coexist. Mainly these approaches are categorized in indirect biomimetics and direct biomimetics. Under indirect biomimetics we discuss 1) emerging paradigms in learning theory and 2) game theory for their potential to enable SO solutions in heterogeneous networks. By means of numerical results we demonstrate the pros and cons of these indirect biomimetic approaches for designing SO in macro-femto coexistence scenarios. Furthermore, we demonstrate the use of direct biomimetic approaches for designing SO by exploiting one to one mapping between a natural SO system and our system model for heterogeneous networks based on Outdoor Fixed Relays (OFR). Numerical results show that the proposed analytical solution can enhance wireless backhaul capacity of the OFR based femtocells by adapting the macro base station (BS) antenna tilts in a distributed and self organizing manner.
---
paper_title: Accelerated learning in machine learning-based resource allocation methods for Heterogenous Networks

paper_content:

Heterogeneous Networks, such as those with Femtocells and Macrocell Basestations, face the task of resource allocation to ensure all users, both primary (mobile user) and secondary (femtocell user), receive assurances of quality of service. One method of performing this allocation, Q-learning, involves the use of a reward function (defining objectives) and a Q-table (storing policy information). This Q-table can be shared between users to speed up convergence on a policy ensuring a desired quality of service. In this paper, a reward function and state structure are presented and compared to another Q-learning reward function. The designed RF is shown to increase the sum femtocell user capacity in most scenarios while maintaining the desired quality of service for the mobile user. The sharing of Q-tables formed using th e designed reward function and state structure with nodes entering the network is shown to significantly speed up convergence in most scenarios when compared to convergence without sharing Q-tables.
---
paper_title: Average reward reinforcement learning: Foundations, algorithms, and empirical results

paper_content:

This paper presents a detailed study of average reward reinforcement learning, an undiscounted optimality framework that is more appropriate for cyclical tasks than the much better studied discounted framework. A wide spectrum of average reward algorithms are described, ranging from synchronous dynamic programming methods to several (provably convergent) asynchronous algorithms from optimal control and learning automata. A general sensitive discount optimality metric calledn-discount-optimality is introduced, and used to compare the various algorithms. The overview identifies a key similarity across several asynchronous algorithms that is crucial to their convergence, namely independent estimation of the average reward and the relative values. The overview also uncovers a surprising limitation shared by the different algorithms while several algorithms can provably generategain-optimal policies that maximize average reward, none of them can reliably filter these to producebias-optimal (orT-optimal) policies that also maximize the finite reward to absorbing goal states. This paper also presents a detailed empirical study of R-learning, an average reward reinforcement learning method, using two empirical testbeds: a stochastic grid world domain and a simulated robot environment. A detailed sensitivity analysis of R-learning is carried out to test its dependence on learning rates and exploration levels. The results suggest that R-learning is quite sensitive to exploration strategies and can fall into sub-optimal limit cycles. The performance of R-learning is also compared with that of Q-learning, the best studied discounted RL method. Here, the results suggest that R-learning can be fine-tuned to give better performance than Q-learning in both domains.
---
paper_title: Reinforcement Learning: A Survey

paper_content:

This paper surveys the field of reinforcement learning from a computer-science perspective. It is written to be accessible to researchers familiar with machine learning. Both the historical basis of the field and a broad selection of current work are summarized. Reinforcement learning is the problem faced by an agent that learns behavior through trial-and-error interactions with a dynamic environment. The work described here has a resemblance to work in psychology, but differs considerably in the details and in the use of the word ``reinforcement.'' The paper discusses central issues of reinforcement learning, including trading off exploration and exploitation, establishing the foundations of the field via Markov decision theory, learning from delayed reinforcement, constructing empirical models to accelerate learning, making use of generalization and hierarchy, and coping with hidden state. It concludes with a survey of some implemented systems and an assessment of the practical utility of current methods for reinforcement learning.
---
paper_title: Learning from experts in cognitive radio networks: The docitive paradigm

paper_content:

In this paper we introduce the novel paradigm of docition for cognitive radio (CR) networks. We consider that the CRs are intelligent radios implementing a learning process through which they interact with the surrounding environment to make self-adaptive decisions. However, in distributed settings the learning may be complex and slow, due to interactive decision making processes, which results in a non-stationary environment. The docitive paradigm proposes a timely solution based on knowledge sharing, which allows CRs to develop new capacities for selecting actions. We demonstrate that this improves the CRs' learning ability and accuracy, and gives them strategies for action selection in unvisited states. We evaluate the docitive paradigm in the context of a secondary system modeled as a multi-agent system, where the agents are IEEE 802.22 CR base stations, implementing a real-time multi-agent reinforcement learning technique known as decentralized Q-learning. Our goal is to solve the aggregated interference problem generated by multiple CR systems at the receivers of a primary system. We propose three different docitive algorithms and we show their superiority to the well know paradigm of independent learning in terms of speed of convergence and precision.
---
paper_title: Transfer Learning for Reinforcement Learning Domains: A Survey

paper_content:

The reinforcement learning paradigm is a popular way to address problems that have only limited environmental feedback, rather than correctly labeled examples, as is common in other machine learning contexts. While significant progress has been made to improve learning in a single task, the idea of transfer learning has only recently been applied to reinforcement learning tasks. The core idea of transfer is that experience gained in learning to perform one task can help improve learning performance in a related, but different, task. In this article we present a framework that classifies transfer learning methods in terms of their capabilities and goals, and then use it to survey the existing literature, as well as to suggest future directions for transfer learning work.
---
paper_title: Game Theory in Wireless and Communication Networks

paper_content:

This unified treatment of game theory focuses on finding state-of-the-art solutions to issues surrounding the next generation of wireless and communication networks. Future networkswillrelyonautonomousanddistributedarchitecturestoimprovetheefficiency and flexibility of mobile applications, and game theory provides the ideal framework for designing efficient and robust distributed algorithms. This book enables readers to develop a solid understanding of game theory, its applications, and its use as an effective tool for addressing various problems in wireless communication and networking. The key results and tools of game theory are covered, as are various real-world technologies including 3G/4G networks, wireless LANs, sensor networks, cognitive networks, and Internet networks. The book also covers a wide range of techniques for modeling, designing, and analyzing communication networks using game theory, as well as state-of-the-art distributed design techniques. This is an ideal resource for communications engineers, researchers, and graduate and undergraduate students.
---
paper_title: Average reward reinforcement learning: Foundations, algorithms, and empirical results

paper_content:

This paper presents a detailed study of average reward reinforcement learning, an undiscounted optimality framework that is more appropriate for cyclical tasks than the much better studied discounted framework. A wide spectrum of average reward algorithms are described, ranging from synchronous dynamic programming methods to several (provably convergent) asynchronous algorithms from optimal control and learning automata. A general sensitive discount optimality metric calledn-discount-optimality is introduced, and used to compare the various algorithms. The overview identifies a key similarity across several asynchronous algorithms that is crucial to their convergence, namely independent estimation of the average reward and the relative values. The overview also uncovers a surprising limitation shared by the different algorithms while several algorithms can provably generategain-optimal policies that maximize average reward, none of them can reliably filter these to producebias-optimal (orT-optimal) policies that also maximize the finite reward to absorbing goal states. This paper also presents a detailed empirical study of R-learning, an average reward reinforcement learning method, using two empirical testbeds: a stochastic grid world domain and a simulated robot environment. A detailed sensitivity analysis of R-learning is carried out to test its dependence on learning rates and exploration levels. The results suggest that R-learning is quite sensitive to exploration strategies and can fall into sub-optimal limit cycles. The performance of R-learning is also compared with that of Q-learning, the best studied discounted RL method. Here, the results suggest that R-learning can be fine-tuned to give better performance than Q-learning in both domains.
---
paper_title: Efficient power control via pricing in wireless data networks

paper_content:

A major challenge in the operation of wireless communications systems is the efficient use of radio resources. One important component of radio resource management is power control, which has been studied extensively in the context of voice communications. With the increasing demand for wireless data services, it is necessary to establish power control algorithms for information sources other than voice. We present a power control solution for wireless data in the analytical setting of a game theoretic framework. In this context, the quality of service (QoS) a wireless terminal receives is referred to as the utility and distributed power control is a noncooperative power control game where users maximize their utility. The outcome of the game results in a Nash (1951) equilibrium that is inefficient. We introduce pricing of transmit powers in order to obtain Pareto improvement of the noncooperative power control game, i.e., to obtain improvements in user utilities relative to the case with no pricing. Specifically, we consider a pricing function that is a linear function of the transmit power. The simplicity of the pricing function allows a distributed implementation where the price can be broadcast by the base station to all the terminals. We see that pricing is especially helpful in a heavily loaded system.
---
paper_title: Reinforcement Learning: A Survey

paper_content:

This paper surveys the field of reinforcement learning from a computer-science perspective. It is written to be accessible to researchers familiar with machine learning. Both the historical basis of the field and a broad selection of current work are summarized. Reinforcement learning is the problem faced by an agent that learns behavior through trial-and-error interactions with a dynamic environment. The work described here has a resemblance to work in psychology, but differs considerably in the details and in the use of the word ``reinforcement.'' The paper discusses central issues of reinforcement learning, including trading off exploration and exploitation, establishing the foundations of the field via Markov decision theory, learning from delayed reinforcement, constructing empirical models to accelerate learning, making use of generalization and hierarchy, and coping with hidden state. It concludes with a survey of some implemented systems and an assessment of the practical utility of current methods for reinforcement learning.
---
paper_title: Eavesdropping and jamming in next-generation wireless networks: A game-theoretic approach

paper_content:

The efficient design of next-generation wireless systems faces multifaceted problems involving a variety of node types such as wireless users, relay stations, base stations, eavesdroppers, and jammers. In this paper, the complex decision making processes between a network of wireless users that perform uplink transmission via relay stations and an active malicious node, that is able to act as an eavesdropper and as a jammer, is studied. A noncooperative game in which the users and the malicious node are the players is formulated. On the one hand, the users seek to choose the relay station that maximizes their utilities which reflect their mutual interference as well as the security of the chosen path. On the other hand, the objective of the malicious node is to choose whether to eavesdrop, jam, or use a combination of both strategies, in a way to reduce the total network capacity. To solve the game, a fictitious play-based algorithm is proposed using which the users and the malicious node reach a mixed-strategy Nash equilibrium. Simulation results show that the proposed approach improves the average expected utility per user up to 49.4% relative to a nearest neighbor algorithm. The results also show how the malicious node can strategically decide on whether to jam or eavesdrop depending on its capabilities and objectives.
---
paper_title: Individual learning of coordination knowledge

paper_content:

Abstract. Social agents, both human and computational, inhabiting a world containing multiple active agents, need to coordinate their activities. This is because agents share resources, and without proper coordination or ‘rules of the road’, everybody will be interfering with the plans of others. As such, we need coordination schemes that allow agents to effectively achieve local goals without adversely affecting the problem-solving capabilities of other agents. Researchers in the field of Distributed Artificial Intelligence (DAI) have developed a variety of coordination schemes under different assumptions about agent capabilities and relationships. Whereas some of these researchers have been motivated by human cognitive biases, others have approached it as an engineering problem of designing the most effective coordination architecture or protocol. We evaluate individual and concurrent learning by multiple, autonomous agents as a means for acquiring coordination knowledge. We show that a uniform reinforc...
---
paper_title: Game Theory in Wireless and Communication Networks

paper_content:

This unified treatment of game theory focuses on finding state-of-the-art solutions to issues surrounding the next generation of wireless and communication networks. Future networkswillrelyonautonomousanddistributedarchitecturestoimprovetheefficiency and flexibility of mobile applications, and game theory provides the ideal framework for designing efficient and robust distributed algorithms. This book enables readers to develop a solid understanding of game theory, its applications, and its use as an effective tool for addressing various problems in wireless communication and networking. The key results and tools of game theory are covered, as are various real-world technologies including 3G/4G networks, wireless LANs, sensor networks, cognitive networks, and Internet networks. The book also covers a wide range of techniques for modeling, designing, and analyzing communication networks using game theory, as well as state-of-the-art distributed design techniques. This is an ideal resource for communications engineers, researchers, and graduate and undergraduate students.
---
paper_title: Equilibrium Efficiency Improvement in MIMO Interference Systems: A Decentralized Stream Control Approach

paper_content:

We consider a multi-link MIMO interference system in which each link wishes to maximize its own mutual information by choosing its own signal vector, which leads to a multi-player game. We show the existence of a Nash equilibrium and obtain sufficient conditions for the uniqueness of equilibrium. We consider two decentralized link adjustment algorithms called best-response process (a.k.a. iterative water-filling) and gradient-play (an autonomous and non-cooperative version of the well-known gradient ascent algorithm). Under our uniqueness conditions, we establish the convergence of these algorithms to the unique equilibrium provided that the links use some inertia. To improve the efficiency of an equilibrium with respect to the total mutual information by imposing limits on the number of independent data streams, we present a stream control approach using linear transformation of the link covariance matrices. We then show how to decentralize our stream control approach by allowing the links to negotiate the limits on the number of independent data streams that they are willing to impose upon themselves. To achieve this, we introduce a variation of a learning algorithm called "adaptive play" that has desirable convergence properties in potential games with reduced computation.
---
paper_title: Distributed convergence to Nash equilibria with local utility measurements

paper_content:

We consider multiplayer repeated matrix games in which several players seek to increase their individual rewards by updating their strategies based on limited information. One body of work assumes that players can measure the actions of other players, but do not have access to the utility functions of other players. In this case, well known strategy update mechanisms such as fictitious play (FP) and gradient play (GP) provide convergence to Nash equilibria in certain special classes of games. Recent work by the authors introduced "dynamic" versions of FP and GP, where players use derivative action to process and respond to the information available to them. These mechanisms, called derivative action FP and derivative Action GP, lead to behavior converging to Nash equilibria in a significantly larger set of games than standard FP and GP provide. In this paper, we consider the case where players do not have access to opposing actions. As before, players do not have access to opposing player utility functions. Furthermore, a player's access to its own utility function is restricted to the measured utility at each round of the repeated game - structural parameters of its own utility remain unknown. Our main result is to show that derivative action FP and GP can be adapted to the utility measurement case to yield the same dynamics (in continuous-time and up to a coordinate transformation) as though players could measure other player actions. The transformation holds for both two-player games as well as in multiplayer games with a specific utility structure. The implication is that many of the stability and convergence properties obtained under derivative action FP and GP can be extended to the utility measurement case.
---
paper_title: Stochastic Learning Solution for Distributed Discrete Power Control Game in Wireless Data Networks

paper_content:

Distributed power control is an important issue in wireless networks. Recently, noncooperative game theory has been applied to investigate interesting solutions to this problem. The majority of these studies assumes that the transmitter power level can take values in a continuous domain. However, recent trends such as the GSM standard and Qualcomm's proposal to the IS-95 standard use a finite number of discretized power levels. This motivates the need to investigate solutions for distributed discrete power control which is the primary objective of this paper. We first note that, by simply discretizing, the previously proposed continuous power adaptation techniques will not suffice. This is because a simple discretization does not guarantee convergence and uniqueness. We propose two probabilistic power adaptation algorithms and analyze their theoretical properties along with the numerical behavior. The distributed discrete power control problem is formulated as an N-person, nonzero sum game. In this game, each user evaluates a power strategy by computing a utility value. This evaluation is performed using a stochastic iterative procedures. We approximate the discrete power control iterations by an equivalent ordinary differential equation to prove that the proposed stochastic learning power control algorithm converges to a stable Nash equilibrium. Conditions when more than one stable Nash equilibrium or even only mixed equilibrium may exist are also studied. Experimental results are presented for several cases and compared with the continuous power level adaptation solutions.
---
paper_title: Precoding Strategy Selection for Cognitive MIMO Multiple Access Channels Using Learning Automata

paper_content:

In this paper, we study the quantized precoding strategy selection for multiple-input multiple-output (MIMO) multiple access channels (MAC) in cognitive radio (CR) networks through a game-theoretic perspective. Since the secondary users in such system are difficult to be coordinated by a centralized authority, they are noncooperative and attempt to maximize their own payoffs selfishly in a distributed method. We propose a noncooperative precoding strategy selection game and find that it is a potential game which possesses at least one pure strategy Nash equilibrium. A decentralized learning algorithm with a small amount of feedback is proposed to obtain Nash equilibrium. We prove that the proposed algorithm can converge to a pure strategy Nash equilibrium. Simulation results are provided to verify our analysis.
---
paper_title: Self-Organization in Small Cell Networks: A Reinforcement Learning Approach

paper_content:

In this paper, a decentralized and self-organizing mechanism for small cell networks (such as micro-, femto- and picocells) is proposed. In particular, an application to the case in which small cell networks aim to mitigate the interference caused to the macrocell network, while maximizing their own spectral efficiencies, is presented. The proposed mechanism is based on new notions of reinforcement learning (RL) through which small cells jointly estimate their time-average performance and optimize their probability distributions with which they judiciously choose their transmit configurations. Here, a minimum signal to interference plus noise ratio (SINR) is guaranteed at the macrocell user equipment (UE), while the small cells maximize their individual performances. The proposed RL procedure is fully distributed as every small cell base station requires only an observation of its instantaneous performance which can be obtained from its UE. Furthermore, it is shown that the proposed mechanism always converges to an epsilon Nash equilibrium when all small cells share the same interest. In addition, this mechanism is shown to possess better convergence properties and incur less overhead than existing techniques such as best response dynamics, fictitious play or classical RL. Finally, numerical results are given to validate the theoretical findings, highlighting the inherent tradeoffs facing small cells, namely exploration/exploitation, myopic/foresighted behavior and complete/incomplete information.
---
paper_title: A Game-Theoretic Framework for Medium Access Control

paper_content:

In this paper, we generalize the random access game model, and show that it provides a general game- theoretic framework for designing contention based medium access control. We extend the random access game model to the network with multiple contention measure signals, study the design of random access games, and analyze different distributed algorithms achieving their equilibria. As examples, a series of utility functions is proposed for games achieving the maximum throughput in a network of homogeneous nodes. In a network with n traffic classes, an N-signal game model is proposed which achieves the maximum throughput under the fairness constraint among different traffic classes. In addition, the convergence of different dynamic algorithms such as best response, gradient play and Jacobi play under propagation delay and estimation error is established. Simulation results show that game model based protocols can achieve superior performance over the standard IEEE 802.11 DCF, and comparable performance as existing protocols with the best performance in literature.
---
paper_title: Markov Games as a Framework for Multi-Agent Reinforcement Learning

paper_content:

In the Markov decision process (MDP) formalization of reinforcement learning, a single adaptive agent interacts with an environment defined by a probabilistic transition function. In this solipsis-tic view, secondary agents can only be part of the environment and are therefore fixed in their behavior. The framework of Markov games allows us to widen this view to include multiple adaptive agents with interacting or competing goals. This paper considers a step in this direction in which exactly two agents with diametrically opposed goals share an environment. It describes a Q-learning-like algorithm for finding optimal policies and demonstrates its application to a simple two-player game in which the optimal policy is probabilistic.
---
paper_title: On the Global Convergence of Stochastic Fictitious Play

paper_content:

We establish global convergence results for stochastic fictitious play for four classes of games: games with an interior ESS, zero sum games, potential games, and supermodular games. We do so by appealing to techniques from stochastic approximation theory, which relate the limit behavior of a stochastic process to the limit behavior of a differential equation defined by the expected motion of the process. The key result in our analysis of supermodular games is that the relevant differential equation defines a strongly monotone dynamical system. Our analyses of the other cases combine Lyapunov function arguments with a discrete choice theory result: that the choice probabilities generated by any additive random utility model can be derived from a deterministic model based on payoff perturbations that depend nonlinearly on the vector of choice probabilities.
---
paper_title: A hybrid systems model for power control in multicell wireless data networks

paper_content:

We present a power control scheme based on noncooperative game theory, using a fairly broad class of convex cost functions. The multicell CDMA wireless data network is modeled as a switched hybrid system where handoffs of mobiles between different cells correspond to discrete switching events between different subsystems. Under a set of sufficient conditions, we prove the existence of a unique Nash equilibrium for each subsystem, and prove global exponential stability of an update algorithm. We also establish the global convergence of the dynamics of the multicell power control game to a convex superset of Nash equilibria for any switching (handoff) scheme satisfying a mild condition on average dwell-time. Robustness of these results to feedback delays as well as to quantization is investigated. In addition, we consider a quantization scheme to reduce the communication overhead between mobiles and the base stations. Finally, we illustrate the proposed power control scheme through simulations.
---
paper_title: Stochastic Traffic Engineering in Multihop Cognitive Wireless Mesh Networks

paper_content:

In this work, the stochastic traffic engineering problem in multihop cognitive wireless mesh networks is addressed. The challenges induced by the random behaviors of the primary users are investigated in a stochastic network utility maximization framework. For the convex stochastic traffic engineering problem, we propose a fully distributed algorithmic solution which provably converges to the global optimum with probability one. We next extend our framework to the cognitive wireless mesh networks with nonconvex utility functions, where a decentralized algorithmic solution, based on learning automata techniques, is proposed. We show that the decentralized solution converges to the global optimum solution asymptotically.
---
paper_title: NeXt generation/dynamic spectrum access/cognitive Radio Wireless Networks: A Survey

paper_content:

Today's wireless networks are characterized by a fixed spectrum assignment policy. However, a large portion of the assigned spectrum is used sporadically and geographical variations in the utilization of assigned spectrum ranges from 15% to 85% with a high variance in time. The limited available spectrum and the inefficiency in the spectrum usage necessitate a new communication paradigm to exploit the existing wireless spectrum opportunistically. This new networking paradigm is referred to as NeXt Generation (xG) Networks as well as Dynamic Spectrum Access (DSA) and cognitive radio networks. The term xG networks is used throughout the paper. The novel functionalities and current research challenges of the xG networks are explained in detail. More specifically, a brief overview of the cognitive radio technology is provided and the xG network architecture is introduced. Moreover, the xG network functions such as spectrum management, spectrum mobility and spectrum sharing are explained in detail. The influence of these functions on the performance of the upper layer protocols such as routing and transport are investigated and open research issues in these areas are also outlined. Finally, the cross-layer design challenges in xG networks are discussed.
---
paper_title: Power allocation with stackelberg game in femtocell networks: a self-learning approach

paper_content:

This paper investigates the energy-efficient power allocation for a two-tier, underlaid femtocell network. The behaviors of the Macrocell Base Station (MBS) and the Femtocell Users (FUs) are modeled hierarchically as a Stackelberg game. The MBS guarantees its own QoS requirement by charging the FUs individually according to the cross-tier interference, and the FUs responds by controlling the local transmit power non-cooperatively. Due to the limit of information exchange in intra- and inter-tiers, a self-learning based strategy-updating mechanism is proposed for each user to learn the equilibrium strategies. In the same Stackelberg-game framework, two different scenarios based on the continuous and discrete power profiles for the FUs are studied, respectively. The self-learning schemes in the two scenarios are designed based on the local best response. By studying the properties of the proposed game in the two situations, the convergence property of the learning schemes is provided. The simulation results are provided to support the theoretical finding in different situations of the proposed game, and the efficiency of the learning schemes is validated.
---
paper_title: Decentralized Learning of Nash Equilibria in Multi-Person Stochastic Games With Incomplete Information

paper_content:

A multi-person discrete game where the payoff after each play is stochastic is considered. The distribution of the random payoff is unknown to the players and further none of the players know the strategies or the actual moves of other players. A learning algorithm for the game based on a decentralized team of learning automata is presented. It is proved that all stable stationary points of the algorithm are Nash equilibria for the game. Two special cases of the game are also discussed, namely, game with common payoff and the relaxation labelling problem. The former has applications such as pattern recognition and the latter is a problem widely studied in computer vision. For the two special cases it is shown that the algorithm always converges to a desirable solution. >
---
paper_title: Non-cooperative power control for wireless ad hoc networks with repeated games

paper_content:

One of the distinctive features in a wireless ad hoc network is lack of any central controller or single point of authority, in which each node/link then makes its own decisions independently. Therefore, fully cooperative behaviors, such as cooperation for increasing system capacity, mitigating interference for each other, or honestly revealing private information, might not be directly applied. It has been shown that power control is an efficient approach to achieve quality of service (QoS) requirement in ad hoc networks. However, the existing work has largely relied on cooperation among different nodes/links or a pricing mechanism that often needs a third-party involvement. In this paper, we aim to design a non-cooperative power control algorithm without pricing mechanism for ad hoc networks. We view the interaction among the users' decision for power level as a repeated game. With the theory of stochastic fictitious play (SFP), we propose a reinforcement learning algorithm to schedule each user's power level. There are three distinctive features in our proposed scheme. First, the user's decision at each stage is self-incentive with myopic best response correspondence. Second, the dynamics arising from our proposed algorithm eventually converges to pure Nash equilibrium (NE). Third, our scheme does not need any information exchange or to observe the opponents' private information. Therefore, this proposed algorithm can safely run in a fully selfish environment without any additional pricing and secure mechanism. Simulation study demonstrates the effectiveness of our proposed scheme.
---
paper_title: Dynamic fictitious play, dynamic gradient play, and distributed convergence to Nash equilibria

paper_content:

We consider a continuous-time form of repeated matrix games in which player strategies evolve in reaction to opponent actions. Players observe each other's actions, but do not have access to other player utilities. Strategy evolution may be of the best response sort, as in fictitious play, or a gradient update. Such mechanisms are known to not necessarily converge. We introduce a form of "dynamic" fictitious and gradient play strategy update mechanisms. These mechanisms use derivative action in processing opponent actions and, in some cases, can lead to behavior converging to Nash equilibria in previously nonconvergent situations. We analyze convergence in the case of exact and approximate derivative measurements of the dynamic update mechanisms. In the ideal case of exact derivative measurements, we show that convergence to Nash equilibrium can always be achieved. In the case of approximate derivative measurements, we derive a characterization of local convergence that shows how the dynamic update mechanisms can converge if the traditional static counterparts do not. We primarily discuss two player games, but also outline extensions to multiplayer games. We illustrate these methods with convergent simulations of the well known Shapley and Jordan counterexamples.
---
paper_title: Near-Optimal Power Control in Wireless Networks: A Potential Game Approach

paper_content:

We study power control in a multi-cell CDMA wireless system whereby self-interested users share a common spectrum and interfere with each other. Our objective is to design a power control scheme that achieves a (near) optimal power allocation with respect to any predetermined network objective (such as the maximization of sum-rate, or some fairness criterion). To obtain this, we introduce the potential-game approach that relies on approximating the underlying noncooperative game with a "close" potential game, for which prices that induce an optimal power allocation can be derived. We use the proximity of the original game with the approximate game to establish through Lyapunov-based analysis that natural user-update schemes (applied to the original game) converge within a neighborhood of the desired operating point, thereby inducing near-optimal performance in a dynamical sense. Additionally, we demonstrate through simulations that the actual performance can in practice be very close to optimal, even when the approximation is inaccurate. As a concrete example, we focus on the sum-rate objective, and evaluate our approach both theoretically and empirically.
---
paper_title: Distributed Resource Management in Multihop Cognitive Radio Networks for Delay-Sensitive Transmission

paper_content:

In this paper, we investigate the problem of multiuser resource management in multihop cognitive radio networks for delay-sensitive applications. Since tolerable delay does not allow propagating global information back and forth throughout the multihop network to a centralized decision maker, the source nodes and relays need to adapt their actions (transmission frequency channel and route selections) in a distributed manner, based on local network information. We propose a distributed resource-management algorithm that allows network nodes to exchange information and that explicitly considers the delays and cost of exchanging the network information over multihop cognitive radio networks. In this paper, the term ldquocognitiverdquo refers to both the capability of the network nodes to achieve large spectral efficiencies by dynamically exploiting available frequency channels and their ability to learn the ldquoenvironmentrdquo (the actions of interfering nodes) based on the designed information exchange. Note that the node competition is due to the mutual interference of neighboring nodes using the same frequency channel. Based on this, we adopt a multiagent-learning approach, i.e., adaptive fictitious play, which uses the available interference information. We also discuss the tradeoff between the cost of the required information exchange and the learning efficiency. The results show that our distributed resource-management approach improves the peak signal-to-noise ratio (PSNR) of multiple video streams by more than 3 dB, as opposed to the state-of-the-art dynamic frequency channel/route selection approaches without learning capability, when the network resources are limited.
---
paper_title: Relay Selection and Discrete Power Control for Cognitive Relay Networks via Potential Game

paper_content:

In this paper, we study the joint relay selection and discrete power control problem for cognitive relay networks via a game-theoretic approach subject to the interference power con- straint at the primary receivers and the total available power con- straint for the secondary relays. The problem is formulated as a noncooperative game where the achievable rate of the cognitive relay network is used to design a common utility. This game is shown to be a potential game which possesses at least one pure strategy Nash equilibrium (NE) and an optimal strategy profile that maximizes the rate of cognitive relay network constitutes a pure strategy NE of our proposed game.We provethat undersome mild conditions, our proposed game can guarantee the feasibility of a pure strategy NE without advance knowledge of infeasible strategyprofiles. Moreover, wefind that the price of anarchy (PoA) of our proposed game is equal to 1 under some conditions. In order to achieve the pure strategy NE, we design a centralized iterative algorithm and a decentralized stochastic learning algorithm based on learning automata. The convergence and the complexity of our designed algorithms are discussed. It is shown that our designed algorithms can achieve optimal or near-optimal rate performance with low complexity.
---
paper_title: The Dynamics of Reinforcement Learning in Cooperative Multiagent Systems

paper_content:

Reinforcement learning can provide a robust and natural means for agents to learn how to coordinate their action choices in multi agent systems. We examine some of the factors that can influence the dynamics of the learning process in such a setting. We first distinguish reinforcement learners that are unaware of (or ignore) the presence of other agents from those that explicitly attempt to learn the value of joint actions and the strategies of their counterparts. We study (a simple form of) Q-leaming in cooperative multi agent systems under these two perspectives, focusing on the influence of that game structure and exploration strategies on convergence to (optimal and suboptimal) Nash equilibria. We then propose alternative optimistic exploration strategies that increase the likelihood of convergence to an optimal equilibrium.
---
paper_title: Learning control of finite Markov chains with unknown transition probabilities

paper_content:

For a Markovian decision problem in which the transition probabilities are unknown, two learning algorithms are devised from the viewpoint of asymptotic optimality. Each time the algorithms select decisions to be used on the basis of not only the estimates of the unknown probabilities but also uncertainty of them. It is shown that the algorithms are asymptotically optimal in the sense that the probability of selecting an optimal policy converges to unity.
---
paper_title: Hierarchical Network Formation Games in the Uplink of Multi-Hop Wireless Networks

paper_content:

In this paper, we propose a game theoretic approach to tackle the problem of the distributed formation of the hierarchical network architecture that connects the nodes in the uplink of a wireless multi-hop network. Unlike existing literature which focused on the performance assessment of hierarchical multi-hop networks given an existing topology, this paper investigates the problem of the formation of this topology among a number of nodes that seek to send data in the uplink to a central base station through multi-hop. We model the problem as a hierarchical network formation game and we divide the network into different hierarchy levels, whereby the nodes belonging to the same level engage in a non-cooperative Nash game for selecting their next hop. As a solution to the game, we propose a novel equilibrium concept, the hierarchical Nash equilibrium, for a sequence of multi-stage Nash games, which can be found by backward induction analytically. For finding this equilibrium, we propose a distributed myopic dynamics algorithm, based on fictitious play, in which each node computes the mixed strategies that maximize its utility which represents the probability of successful transmission over the multi-hop communication path in the presence of interference. Simulation results show that the proposed algorithm presents significant gains in terms of average achieved expected utility per user up to 125.6% relative to a nearest neighbor algorithm.
---
paper_title: Opportunistic Spectrum Access in Unknown Dynamic Environment: A Game-Theoretic Stochastic Learning Solution

paper_content:

We investigate the problem of distributed channel selection using a game-theoretic stochastic learning solution in an opportunistic spectrum access (OSA) system where the channel availability statistics and the number of the secondary users are apriori unknown. We formulate the channel selection problem as a game which is proved to be an exact potential game. However, due to the lack of information about other users and the restriction that the spectrum is time-varying with unknown availability statistics, the task of achieving Nash equilibrium (NE) points of the game is challenging. Firstly, we propose a genie-aided algorithm to achieve the NE points under the assumption of perfect environment knowledge. Based on this, we investigate the achievable performance of the game in terms of system throughput and fairness. Then, we propose a stochastic learning automata (SLA) based channel selection algorithm, with which the secondary users learn from their individual action-reward history and adjust their behaviors towards a NE point. The proposed learning algorithm neither requires information exchange, nor needs prior information about the channel availability statistics and the number of secondary users. Simulation results show that the SLA based learning algorithm achieves high system throughput with good fairness.
---
paper_title: Stochastic Game-Theoretic Spectrum Access in Distributed and Dynamic Environment

paper_content:

In this paper, we investigate the problem of channel selection for interference mitigation in opportunistic spectrum access networks using a stochastic game-theoretic approach. The studied network is distributed and dynamic , where each user only has its individual information, and no information exchange is available among users. Moreover, each user is considered to be dynamically active due to its specific data service requirement. Specifically, a user randomly becomes active and then competes for the wireless channel to transmit for a random duration. To capture such dynamic interactions among users, a dynamic interference graph is defined, and based on this, the interference mitigation problem is formulated as a graphical stochastic game. It is proved to be an exact potential game, in which the existence of the Nash equilibrium (NE) is guaranteed. Then, the performance bounds of the NE are theoretically analyzed. Furthermore, we design a fully distributed and online algorithm based on stochastic learning for the interference-mitigation channel selection, which is proved to converge to the NE of the formulated game. Finally, we conduct simulations to validate the effectiveness of the proposed algorithm for interference mitigation and throughput improvement in the distributed and dynamic environment.
---
paper_title: Correlated Q-Learning

paper_content:

This paper introduces Correlated-Q (CE-Q) learning, a multiagent Q-learning algorithm based on the correlated equilibrium (CE) solution concept. CE-Q generalizes both Nash-Q and Friend-and-Foe-Q: in general-sum games, the set of correlated equilibria contains the set of Nash equilibria; in constant-sum games, the set of correlated equilibria contains the set of minimax equilibria. This paper describes experiments with four variants of CE-Q, demonstrating empirical convergence to equilibrium policies on a testbed of general-sum Markov games.
---
paper_title: Learning Automata And Stochastic Optimization

paper_content:

Stochastic optimization.- On learning automata.- Unconstrained optimization problems.- Constrained optimization problems.- Optimization of nonstationary functions.
---
paper_title: Reinforcement Learning for Repeated Power Control Game in Cognitive Radio Networks

paper_content:

Cognitive radio (CR) users are expected to be uncoordinated users that opportunistically seek the spectrum resource from primary users (PUs) in a competitive way. In most existing works, however, CR users are required to share the interference channel information and power strategies to conduct the game with pricing mechanisms that incur the frequent exchange of information. The requirement of significant communication overheads among CR users impedes fully distributed solutions for the deployment of CR networks, which is a challenging problem in the research communities. In this paper, a robust distributed power control algorithm is designed with low implementation complexity for CR networks through reinforcement learning, which does not require the interference channel and power strategy information among CR users (and from CR users to PUs). To the best of our knowledge, this research provides the solution for the first time for the incomplete-information power control game in CR networks. During the repeated game, CR users can control their power strategies by observing the interference from the feedback signals of PUs and transmission rates obtained in the previous step. This procedure allows achieving high spectrum efficiency while conforming to the interference constraint of PUs. This constrained repeated stochastic game with learning automaton is proved to be asymptotically equivalence to the traditional game with complete information. The properties of existence, diagonal concavity and uniqueness for the game are studied. A Bush-Mosteller reinforcement learning procedure is designed for the power control algorithm, and the properties of convergence and learning rate of the algorithm are analyzed. The performance of the learning-based power control algorithm is thoroughly investigated with simulation results, which demonstrates the effectiveness of the proposed algorithm in solving variety of practical CR network problems for real-world applications.
---
paper_title: Stochastic Traffic Engineering in Multihop Cognitive Wireless Mesh Networks

paper_content:

In this work, the stochastic traffic engineering problem in multihop cognitive wireless mesh networks is addressed. The challenges induced by the random behaviors of the primary users are investigated in a stochastic network utility maximization framework. For the convex stochastic traffic engineering problem, we propose a fully distributed algorithmic solution which provably converges to the global optimum with probability one. We next extend our framework to the cognitive wireless mesh networks with nonconvex utility functions, where a decentralized algorithmic solution, based on learning automata techniques, is proposed. We show that the decentralized solution converges to the global optimum solution asymptotically.
---
paper_title: Learning through reinforcement for N-person repeated constrained games

paper_content:

The design and analysis of an adaptive strategy for N-person averaged constrained stochastic repeated game are addressed. Each player is modeled by a stochastic variable-structure learning automaton. Some constraints are imposed on some functions of the probabilities governing the selection of the player's actions. After each stage, the payoff to each player as well as the constraints are random variables. No information concerning the parameters of the game is a priori available. The "diagonal concavity" conditions are assumed to be fulfilled to guarantee the existence and uniqueness of the Nash equilibrium. The suggested adaptive strategy which uses only the current realizations (outcomes and constraints) of the game is based on the Bush-Mosteller reinforcement scheme in connection with a normalization procedure. The Lagrange multipliers approach with a regularization is used. The asymptotic properties of this algorithm are analyzed. Simulation results illustrate the feasibility and the performance of this adaptive strategy.
---
paper_title: Convergent Multiple-Timescales Reinforcement Learning Algorithms In Normal Form Games

paper_content:

We consider reinforcement learning algorithms in normal form games. Using two-timescales stochastic approximation, we introduce a model-free algorithm which is asymptotically equivalent to the smooth fictitious play algorithm, in that both result in asymptotic pseudotrajectories to the flow defined by the smooth best response dynamics. Both of these algorithms are shown to converge almost surely to Nash distribution in two-player zero-sum games and N -player partnership games. However, there are simple games for which these, and most other adaptive processes, fail to converge--in particular, we consider the N -player matching pennies game and Shapley's variant of the rock--scissors--paper game. By extending stochastic approximation results to multiple timescales we can allow each player to learn at a different rate. We show that this extension will converge for two-player zero-sum games and two-player partnership games, as well as for the two special cases we consider.
---
paper_title: A simple adaptive procedure leading to correlated equilibrium

paper_content:

We propose a new and simple adaptive procedure for playing a game: "regret-matching." In this procedure, players depart from their current play with probabilities that are proportional to measures of regret for not having used other strategies in the past. It is shown that our adaptive procedure guarantees that, with probability one, the empirical distributions of play converge to the set of correlated equilibria of the game. To compute these regret measures, a player needs to know his payoff function and the history of play. We also offer a variation where every player knows only his own realized payoff history (but not his payoff function).
---
paper_title: Adaptive channel allocation spectrum etiquette for cognitive radio networks

paper_content:

In this work, we propose a game theoretic framework to analyze the behavior of cognitive radios for distributed adaptive channel allocation. We define two different objective functions for the spectrum sharing games, which capture the utility of selfish users and cooperative users, respectively. Based on the utility definition for cooperative users, we show that the channel allocation problem can be formulated as a potential game, and thus converges to a deterministic channel allocation Nash equilibrium point. Alternatively, a no-regret learning implementation is proposed for both scenarios and it is shown to have similar performance with the potential game when cooperation is enforced, but with a higher variability across users. The no-regret learning formulation is particularly useful to accommodate selfish users. Non-cooperative learning games have the advantage of a very low overhead for information exchange in the network. We show that cooperation based spectrum sharing etiquette improves the overall network performance at the expense of an increased overhead required for information exchange.
---
paper_title: Decentralized Learning in Markov Games

paper_content:

Learning automata (LA) were recently shown to be valuable tools for designing multiagent reinforcement learning algorithms. One of the principal contributions of the LA theory is that a set of decentralized independent LA is able to control a finite Markov chain with unknown transition probabilities and rewards. In this paper, we propose to extend this algorithm to Markov games-a straightforward extension of single-agent Markov decision problems to distributed multiagent decision problems. We show that under the same ergodic assumptions of the original theorem, the extended algorithm will converge to a pure equilibrium point between agent policies.
---
paper_title: Algorithmic game theory

paper_content:

A new era of theoretical computer science addresses fundamental problems about auctions, networks, and human behavior.
---
paper_title: A General Class of No-Regret Learning Algorithms and Game-Theoretic Equilibria

paper_content:

A general class of no-regret learning algorithms, called Φ-no-regret learning algorithms is defined, which spans the spectrum from no-internal-regret learning to no-external-regret learning, and beyond. Φ describes the set of strategies to which the play of a learning algorithm is compared: a learning algorithm satisfies Φ-no-regret iff no regret is experienced for playing as the algorithm prescribes, rather than playing according to any of the transformations of the algorithm’s play prescribed by elements of Φ. Analogously, a class of game-theoretic equilibria, called Φ-equilibria, is defined, and it is shown that the empirical distribution of play of Φ-no-regret algorithms converges to the set of Φ-equilibria. Perhaps surprisingly, the strongest form of no-regret algorithms in this class are no-internal-regret algorithms. Thus, the tightest game-theoretic solution concept to which Φ-no-regret algorithms (provably) converge is correlated equilibrium. In particular, Nash equilibrium is not a necessary outcome of learning via any Φ-no-regret learning algorithms.
---
paper_title: No-Regret Learning in Collaborative Spectrum Sensing with Malicious Nodes

paper_content:

In cognitive radio network, spectrum sensing is a key component to detect spectrum holes (i.e., channels not used by any primary users). Collaborative spectrum sensing among the cognitive radio nodes is expected to improve fidelity of primary user detection. However, malicious nodes can significantly impair the collaborative spectrum sensing by sending the wrong reports to the fusion center. To overcome this problem, in this paper we propose non- regret learning algorithms to study the non-constructive secondary users caused either by evil-intention or altruistical incapability. Both perfect observation and partial monitoring are investigated, and two algorithms are proposed respectively. Some convergence properties are also shown. Moreover, we also analyze the case in which the nature is assumed to be a player. Illustration example and simulation results demonstrate the proposed schemes can automatically pick the malicious nodes in a distributed way.
---
paper_title: An Auction Framework for Spectrum Allocation with Interference Constraint in Cognitive Radio Networks

paper_content:

Extensive research in recent years has shown the benefits of \textit{cognitive radio} technologies to improve the flexibility and efficiency of spectrum utilization. This new communication paradigm, however, requires a well-designed spectrum allocation mechanism. In this paper, we propose an auction framework for cognitive radio networks to allow unlicensed secondary users (SUs) to share the available spectrum of licensed primary users (PUs) fairly and efficiently, subject to the interference temperature constraint at each PU. To study the competition among SUs, we formulate a non-cooperative multiple-PU multiple-SU auction game and study the structure of the resulting equilibrium by solving a non-continuous two-dimensional optimization problem. A distributed algorithm is developed in which each SU updates its strategy based on local information to converge to the equilibrium. We then extend the proposed auction framework to the more challenging scenario with free spectrum bands. We develop an algorithm based on the no-regret learning to reach a correlated equilibrium of the auction game. The proposed algorithm, which can be implemented distributedly based on local observation, is especially suited in decentralized adaptive learning environments as cognitive radio networks. Finally, through numerical experiments, we demonstrate the effectiveness of the proposed auction framework in achieving high efficiency and fairness in spectrum allocation.
---
paper_title: Distributed reduced-state SARSA algorithm for dynamic channel allocation in cellular networks featuring traffic mobility

paper_content:

This paper presents a distributed reinforcement learning solution to the problem of dynamic channel allocation for cellular telecommunication networks in the presence of mobile call handoffs. The performance of various dynamic channel allocation schemes are compared via extensive computer simulations, and it is shown that a reduced-state SARSA reinforcement learning algorithm can achieve superior new call and handoff blocking probabilities. A new distributed reduced state SARSA algorithm is also developed which uses only local environment information readily available to the learning agent. By way of computer simulations, the distributed SARSA algorithm is shown to be capable of producing call blocking probabilities that are comparable to those obtained by the centralised learning agent.
---
paper_title: Distributive Opportunistic Spectrum Access for Cognitive Radio using Correlated Equilibrium and No-Regret Learning

paper_content:

Cognitive radio has been proposed as a novel approach for improving the utilization of the precious limited radio resources by dynamically accessing the spectrum. One of the major design challenges is to coordinate and cooperate in accessing the spectrum opportunistically among multiple distributive users with only local information. In this paper, we propose a game theoretical approach with a new solution concept, the correlated equilibrium, which is better compared to the non-cooperative Nash equilibrium in terms of spectrum utilization efficiency and fairness among the distributive users. To achieve this correlated equilibrium, we construct an adaptive algorithm based on no-regret learning that guarantees convergence. From the simulation results, the optimal correlated equilibria achieve better fairness and 5% ~15% performance gain, compared to the Nash equilibria.
---
paper_title: Distributed Channel Selection for Interference Mitigation in Dynamic Environment: A Game-Theoretic Stochastic Learning Solution

paper_content:

In this paper, we investigate the problem of distributed chan- nel selection for interference mitigation in a canonical communication network. The channel is assumed time-varying, and the active user set is considered dynamically variable due to the specific service requirement. This problem is formulated as an exact potential game, and the optimality property of the solution to this problem is first analyzed. Then, we design a low-complexity fully distributed no-regret learning algorithm for chan- nel adaptation in a dynamic environment, where each active player can independently and automatically update its action with no information exchange. The proposed algorithm is proven to converge to a set of correlated equilibria with a probability of 1. Finally, we conduct simula- tions to demonstrate that the proposed algorithm achieves near-optimal performance for interference mitigation in dynamic environments. Index Terms—Distributed channel allocation, dynamic environment, interference mitigation, no-regret learning, potential game.
---
paper_title: Distributed Spectrum Sensing in Cognitive Radio Networks with Fairness Consideration: Efficiency of Correlated Equilibrium

paper_content:

Cooperative spectrum sensing improves the reliability of detection. However, if the secondary users are selfish, they may not collaborate for sensing. In order to address this problem, Medium Access Control (MAC) protocols can be designed to enforce cooperation among secondary users for spectrum sensing. In this paper, we investigate this problem using game theoretical framework. We introduce the concept of correlated equilibrium for the cooperative spectrum sensing game among non-cooperative secondary users and formulate the optimization problem for the case where secondary users have heterogeneous traffic dynamics. We show that the correlated equilibrium improves the system utility, as compared to the mixed strategy Nash equilibrium. While maximizing system payoff is important, fairness is also equally important in systems with dissimilar users. In order to address fairness issue, we propose a new fair social welfare correlated equilibrium, which maximizes the system utility and ensures that the less well-off users do not starve. We employ a no-regret learning algorithm for distributed implementation of the correlated equilibrium. Finally, we propose a neighbourhood based learning algorithm and show that it achieves better performance than the no-regret algorithm.
---
paper_title: Subcarrier allocation based on correlated equilibrium in multi-cell OFDMA systems

paper_content:

In uplink orthogonal frequency division multiple access (OFDMA) systems, efficient resource allocation can greatly improve system performance. In this article, taking throughput, inter-cell interference and complexity into account, we present a game-theoretical approach to perform distributed subcarrier allocation for multi-cell OFDMA systems with limited base station (BS) coordination. Firstly, we construct a multi-cell resource allocation game. Creatively, the subcarrier is viewed as a game player to choose the most satisfying user and the BS acts as a referee or a coordinator. Then, we introduce the correlated equilibrium which helps the non-cooperative players coordinate their strategies, hence, achieves better performance compared to Nash equilibrium. Particularly, we point out the condition under which the correlated equilibrium is Pareto efficient. Moreover, we propose a novel subcarrier allocation algorithm based on the no-regret procedure that guarantees convergence to correlated equilibrium, in which the BS coordinates the players’ strategies and provides only partial information exchange. Extensive simulation results are provided to demonstrate the effectiveness of the proposed algorithm.
---
paper_title: Decentralized dynamic spectrum access for cognitive radios: cooperative design of a non-cooperative game

paper_content:

We consider dynamic spectrum access among cognitive radios from an adaptive, game theoretic learning perspective. Spectrum-agile cognitive radios compete for channels temporarily vacated by licensed primary users in order to satisfy their own demands while minimizing interference. For both slowly varying primary user activity and slowly varying statistics of "fast" primary user activity, we apply an adaptive regret based learning procedure which tracks the set of correlated equilibria of the game, treated as a distributed stochastic approximation. This procedure is shown to perform very well compared with other similar adaptive algorithms. We also estimate channel contention for a simple CSMA channel sharing scheme.
---
paper_title: Constrained Stochastic Games in Wireless Networks

paper_content:

We consider the situation where N nodes share a common access point. With each node i there is an associated buffer and channel state that change in time. Node i dynamically chooses both the power and the admission control to be adopted so as to maximize the expected capacity, which depends on the actions and states of all the players, given its power and delay constraints. The information structure that we consider is such that each player knows the state of its own buffer and channel and its own actions. It does not know the states of, and the actions taken by other players. Using Markov Decision Processes we analyze the single player optimal policies under different model parameters. In the context of stochastic games we study the equilibria of the N player scenario.
---
paper_title: Distributed cross-layer resource allocation using Correlated Equilibrium based stochastic learning

paper_content:

In recent years, cross-layer Resource Management (RM) has been widely considered as an efficient approach for improving the network performance. However, due to the factors such as limited knowledge about the wireless environment and spontaneous characteristics of device behaviors, designing an efficient distributed RM scheme using the cross-layer paradigm becomes extremely difficult. In this paper, a distributed, cross-layer RM scheme for multi-users transmitting scalable video in an ad-hoc CDMA network is presented. For the cross-layer RM design, an end-to-end performance criterion at the APP layer is applied and the resource allocations in the PHY, LINK and APP layers are unified into a single decision process. Due to the dynamic property of the wireless channels and the uncoordinated user interactions, the distributed RM decision is modeled in the framework of stochastic game. In the game, each device gradually learns its policy using a distributed, Correlated Equilibrium (CE) based Q-Learning algorithm. In order to calculate the CE in a distributed way, the local devices apply the regret-matching based mechanism for policy and state-action value updating. Simulation experiments show that with the proposed resource management scheme, the system performance can be improved by about 15% compared to the layered RM scheme and 10% compared to the RM scheme purely based on the local-level learning.
---
paper_title: Multiagent Q-learning for aloha-like spectrum access in cognitive radio systems

paper_content:

An Aloha-like spectrum access scheme without negotiation is considered for multiuser and multichannel cognitive radio systems. To avoid collisions incurred by the lack of coordination, each secondary user learns how to select channels according to its experience. Multiagent reinforcement leaning (MARL) is applied for the secondary users to learn good strategies of channel selection. Specifically, the framework of Q-learning is extended from single user case to multiagent case by considering other secondary users as a part of the environment. The dynamics of the Q-learning are illustrated using a Metrick-Polak plot, which shows the traces of Q-values in the two-user case. For both complete and partial observation cases, rigorous proofs of the convergence of multiagent Q-learning without communications, under certain conditions, are provided using the Robins-Monro algorithm and contraction mapping, respectively. The learning performance (speed and gain in utility) is evaluated by numerical simulations.
---
paper_title: Learning to Compete for Resources in Wireless Stochastic Games

paper_content:

In this paper, we model the various users in a wireless network (e.g., cognitive radio network) as a collection of selfish autonomous agents that strategically interact to acquire dynamically available spectrum opportunities. Our main focus is on developing solutions for wireless users to successfully compete with each other for the limited and time-varying spectrum opportunities, given experienced dynamics in the wireless network. To analyze the interactions among users given the environment disturbance, we propose a stochastic game framework for modeling how the competition among users for spectrum opportunities evolves over time. At each stage of the stochastic game, a central spectrum moderator (CSM) auctions the available resources, and the users strategically bid for the required resources. The joint bid actions affect the resource allocation and, hence, the rewards and future strategies of all users. Based on the observed resource allocations and corresponding rewards, we propose a best-response learning algorithm that can be deployed by wireless users to improve their bidding policy at each stage. The simulation results show that by deploying the proposed best-response learning algorithm, the wireless users can significantly improve their own bidding strategies and, hence, their performance in terms of both the application quality and the incurred cost for the used resources.
---
paper_title: A stochastic game framework for joint frequency and power allocation in dynamic decentralized cognitive radio networks

paper_content:

Abstract Cognitive radio networks (CRNs) have been recognized as a promising solution to improve the radio spectrum utilization. This article investigates a novel issue of joint frequency and power allocation in decentralized CRNs with dynamic or time-varying spectrum resources. We firstly model the interactions between decentralized cognitive radio links as a stochastic game and then proposed a strategy learning algorithm which effectively integrates multi-agent frequency strategy learning and power pricing. The convergence of the proposed algorithm to Nash equilibrium is proofed theoretically. Simulation results demonstrate that the throughput performance of the proposed algorithm is very close to that of the centralized optimal learning algorithm, while the proposed algorithm could be implemented distributively and reduce information exchanges significantly.
---
paper_title: Game Theory in Wireless and Communication Networks

paper_content:

This unified treatment of game theory focuses on finding state-of-the-art solutions to issues surrounding the next generation of wireless and communication networks. Future networkswillrelyonautonomousanddistributedarchitecturestoimprovetheefficiency and flexibility of mobile applications, and game theory provides the ideal framework for designing efficient and robust distributed algorithms. This book enables readers to develop a solid understanding of game theory, its applications, and its use as an effective tool for addressing various problems in wireless communication and networking. The key results and tools of game theory are covered, as are various real-world technologies including 3G/4G networks, wireless LANs, sensor networks, cognitive networks, and Internet networks. The book also covers a wide range of techniques for modeling, designing, and analyzing communication networks using game theory, as well as state-of-the-art distributed design techniques. This is an ideal resource for communications engineers, researchers, and graduate and undergraduate students.
---
paper_title: Energy-Efficiency Oriented Traffic Offloading in Wireless Networks: A Brief Survey and a Learning Approach for Heterogeneous Cellular Networks

paper_content:

This paper first provides a brief survey on existing traffic offloading techniques in wireless networks. Particularly as a case study, we put forward an online reinforcement learning framework for the problem of traffic offloading in a stochastic heterogeneous cellular network (HCN), where the time-varying traffic in the network can be offloaded to nearby small cells. Our aim is to minimize the total discounted energy consumption of the HCN while maintaining the quality-of-service (QoS) experienced by mobile users. For each cell (i.e., a macro cell or a small cell), the energy consumption is determined by its system load, which is coupled with system loads in other cells due to the sharing over a common frequency band. We model the energy-aware traffic offloading problem in such HCNs as a discrete-time Markov decision process (DTMDP). Based on the traffic observations and the traffic offloading operations, the network controller gradually optimizes the traffic offloading strategy with no prior knowledge of the DTMDP statistics. Such a model-free learning framework is important, particularly when the state space is huge. In order to solve the curse of dimensionality, we design a centralized $Q$ -learning with compact state representation algorithm, which is named $QC$ -learning. Moreover, a decentralized version of the $QC$ -learning is developed based on the fact the macro base stations (BSs) can independently manage the operations of local small-cell BSs through making use of the global network state information obtained from the network controller. Simulations are conducted to show the effectiveness of the derived centralized and decentralized $QC$ -learning algorithms in balancing the tradeoff between energy saving and QoS satisfaction.
---
paper_title: Distributed reduced-state SARSA algorithm for dynamic channel allocation in cellular networks featuring traffic mobility

paper_content:

This paper presents a distributed reinforcement learning solution to the problem of dynamic channel allocation for cellular telecommunication networks in the presence of mobile call handoffs. The performance of various dynamic channel allocation schemes are compared via extensive computer simulations, and it is shown that a reduced-state SARSA reinforcement learning algorithm can achieve superior new call and handoff blocking probabilities. A new distributed reduced state SARSA algorithm is also developed which uses only local environment information readily available to the learning agent. By way of computer simulations, the distributed SARSA algorithm is shown to be capable of producing call blocking probabilities that are comparable to those obtained by the centralised learning agent.
---
paper_title: Competing Mobile Network Game: Embracing antijamming and jamming strategies with reinforcement learning

paper_content:

We introduce Competing Mobile Network Game (CMNG), a stochastic game played by cognitive radio networks that compete for dominating an open spectrum access. Differentiated from existing approaches, we incorporate both communicator and jamming nodes to form a network for friendly coalition, integrate antijamming and jamming subgames into a stochastic framework, and apply Q-learning techniques to solve for an optimal channel access strategy. We empirically evaluate our Q-learning based strategies and find that Minimax-Q learning is more suitable for an aggressive environment than Nash-Q while Friend-or-foe Q-learning can provide the best solution under distributed mobile ad hoc networking scenarios in which the centralized control can hardly be available.
---
paper_title: Nash Q-Learning for General-Sum Stochastic Games

paper_content:

We extend Q-learning to a noncooperative multiagent context, using the framework of general-sum stochastic games. A learning agent maintains Q-functions over joint actions, and performs updates based on assuming Nash equilibrium behavior over the current Q-values. This learning protocol provably converges given certain restrictions on the stage games (defined by Q-values) that arise during learning. Experiments with a pair of two-player grid games suggest that such restrictions on the game structure are not necessarily required. Stage games encountered during learning in both grid environments violate the conditions. However, learning consistently converges in the first grid game, which has a unique equilibrium Q-function, but sometimes fails to converge in the second, which has three different equilibrium Q-functions. In a comparison of offline learning performance in both games, we find agents are more likely to reach a joint optimal path with Nash Q-learning than with a single-agent Q-learning method. When at least one agent adopts Nash Q-learning, the performance of both agents is better than using single-agent Q-learning. We have also implemented an online version of Nash Q-learning that balances exploration with exploitation, yielding improved performance.
---
paper_title: Markov Games as a Framework for Multi-Agent Reinforcement Learning

paper_content:

In the Markov decision process (MDP) formalization of reinforcement learning, a single adaptive agent interacts with an environment defined by a probabilistic transition function. In this solipsis-tic view, secondary agents can only be part of the environment and are therefore fixed in their behavior. The framework of Markov games allows us to widen this view to include multiple adaptive agents with interacting or competing goals. This paper considers a step in this direction in which exactly two agents with diametrically opposed goals share an environment. It describes a Q-learning-like algorithm for finding optimal policies and demonstrates its application to a simple two-player game in which the optimal policy is probabilistic.
---
paper_title: Unified framework for optimal video streaming

paper_content:

We study the problem of how to stream layered video (live and stored) over a lossy packet network in order to optimize the video quality that is rendered at the receiver. We present a unified framework that combines scheduling, FEC error protection, and decoder error concealment. In the context of the unified framework, we study both the case of a channel with perfect state information and the case of a channel with imperfect state information (delayed or lost feedback). We adapt the theory of infinite-horizon, average-reward Markov decision processes (MDPs) with average-cost constraints to the problem. Based on simulations with MPEG-4 FGS video, we show that (1) optimizing together scheduling, FEC error correction and error concealment improves performance significantly and (2) policies with static error protection give near-optimal performance. We also find that degradations in quality for a channel with imperfect state information are small; thus our MDP approach is suitable for networks with long end-to-end delays
---
paper_title: Stochastic Game for Wireless Network Virtualization

paper_content:

We propose a new framework for wireless network virtualization. In this framework, service providers (SPs) and the network operator (NO) are decoupled from each other: The NO is solely responsible for spectrum management, and SPs are responsible for quality-of-service (QoS) management for their own users. SPs compete for the shared wireless resources to satisfy their distinct service objectives and constraints. We model the dynamic interactions among SPs and the NO as a stochastic game. SPs bid for the resources via dynamically announcing their value functions. The game is regulated by the NO through: 1) sum-utility optimization under rate region constraints; 2) enforcement of Vickrey-Clarke-Groves (VCG) mechanism for pricing the instantaneous rate consumption; and 3) declaration of conjectured prices for future resource consumption. We prove that there exists one Nash equilibrium in the conjectural prices that is efficient, i.e., the sum-utility is maximized. Thus, the NO has the incentive to compute the equilibrium point and feedback to SPs. Given the conjectural prices and the VCG mechanism, we also show that SPs must reveal their truthful value functions at each step to maximize their long-term utilities. As another major contribution, we develop an online learning algorithm that allows the SPs to update the value functions and the NO to update the conjectural prices iteratively. Thus, the proposed framework can deal with unknown dynamics in traffic characteristics and channel conditions. We present simulation results to show the convergence to the Nash equilibrium prices under various dynamic traffic and channel conditions.
---
paper_title: Spectrum Access Games and Strategic Learning in Cognitive Radio Networks for Delay-Critical Applications

paper_content:

With the current proliferation of high bandwidth and delay-sensitive multimedia applications and services, each wireless user will try to maximize its utility by acquiring as much spectrum resources as possible unless a preemptive mechanism exists in the network. Thus, emerging solutions for dynamic spectrum access in cognitive radio networks will need to adopt market-based approaches in order to effectively regulate the available resources. In this paper, we show how various centralized and decentralized spectrum access markets can be designed based on a stochastic game framework, where wireless users (also referred to as secondary users) can compete over time for the dynamically available transmission opportunities (spectrum Bholes(). When operating in such spectrum access Bmarkets,( wireless users become selfish, autonomous agents that strategically interact in order to acquire the necessary spectrum opportunities. We also show how wireless users can successfully compete with each other for the limited and time-varying spectrum opportunities, given the experienced dynamics in the wireless network, by optimiz- ing both their external actions (e.g., the resource bids, power and channel used for transmission, etc.) and their internal actions (e.g., the modulation schemes, etc.). To determine their optimal actions in an informationally decentralized setting, users will need to learn and model directly or indirectly the other users' responses to their external actions. We studied the outcome of various dynamic interactions among self-interested wireless users possessing different knowledge and determine that the proposed framework can lead to multiuser communi- cation systems that achieve new measures of efficiency, rationality and fairness. Lastly, our illustrative results show that the presented game-theoretic solution for wireless resource management enables users deploying enhanced (Bsmarter() learning and communication algorithms and being able to make efficient use of the spectrum resources can derive higher utilities. This presents the designers of wireless devices and systems with important incentives to endow their next- generation products and services with enhanced capabilities to gather information, learn, and strategically compete for resources in the emerging spectrum resource markets made possible by the cognitive radio network technologies.
---
paper_title: Multi Agent Reinforcement Learning Independent vs Cooperative Agents

paper_content:

Intelligent human agents exist in a cooperative social environment that facilitates learning. They learn not only by trial-and-error, but also through cooperation by sharing instantaneous information, episodic experience, and learned knowledge. The key investigations of this paper are, “Given the same number of reinforcement learning agents, will cooperative agents outperform independent agents who do not communicate during learning?” and “What is the price for such cooperation?” Using independent agents as a benchmark, cooperative agents are studied in following ways: (1) sharing sensation, (2) sharing episodes, and (3) sharing learned policies. This paper shows that (a) additional sensation from another agent is beneficial if it can be used efficiently, (b) sharing learned policies or episodes among agents speeds up learning at the cost of communication, and (c) for joint tasks, agents engaging in partnership can significantly outperform independent agents although they may learn slowly in the beginning. These tradeoff's are not just limited to multi-agent reinforcement learning.
---
paper_title: Distributed Strategic Learning for Wireless Engineers

paper_content:

Establishing the link between several theories, this book demonstrates what is needed to learn strategic interaction in wireless networks under uncertainty, randomness, and time delays. This robust game theory cookbook analyzes games where some parameters are uncertain and random. Starting with the fundamentals of strategic learning and game theory, the text then covers partially and fully distributed learning, combined learning for negotiation, bargaining solutions, Nash equilibria, Stackelberg solutions, correlated equilibria, conjectural variations, and satisfactory solutions. It concludes with practical algorithms and techniques to implement game theory in wireless networks.
---
paper_title: Interference Aware Routing Game for Cognitive Radio Multi-Hop Networks

paper_content:

In this paper, we introduce a distributed dynamic routing algorithm in multi-hop cognitive radio (CR) networks, in which secondary users (SUs) want to minimize their interference to the primary users (PUs) while keeping the delay along the route low. We employ a cognitive pilot channel (CPC) for SUs to be able to access the information about PUs, including PUs' locations and channel conditions. Medial axis with a relaxation factor is used as a reference path for the routing, along which we develop a hierarchical structure for multiple sources to reach their destinations. We introduce a temporal and spatial dynamic non-cooperative game to model the interactions among the SUs as well as their influences on the PUs, and obtain by backward induction a set of mixed (behavioral) Nash equilibrium strategies. We also employ a multi-stage fictitious play learning algorithm for distributed routing, which minimizes the overall interference from the SUs to the PUs, as well as the average packet delay along the route from the SU nodes to their destinations. Simulation results show that our proposed algorithm can avoid congestion in the CR network and minimize delay while keeping the interference level low.
---
paper_title: Dynamic conjectures in random access networks using bio-inspired learning

paper_content:

Inspired by the biological entities' ability to achieve reciprocity in the course of evolution, this paper considers a conjecture-based distributed learning approach that enables autonomous nodes to independently optimize their transmission probabilities in random access networks. We model the interaction among multiple self-interested nodes as a game. It is well-known that the Nash equilibria in this game result in zero throughput for all the nodes if they take myopic best-response, thereby leading to a network collapse. This paper enables nodes to behave as intelligent entities which can proactively gather information, form internal conjectures on how their competitors would react to their actions, and update their beliefs according to their local observations. In this way, nodes are capable to autonomously "learn" the behavior of their competitors, optimize their own actions, and eventually cultivate reciprocity in the random access network. To characterize the steady-state outcome of this "evolution", the conjectural equilibrium is introduced. Inspired by the biological phenomena of "derivative action" and "gradient dynamics", two distributed conjecture-based action update mechanisms are proposed to stabilize the random access network. The sufficient conditions that guarantee the proposed conjecture-based learning algorithms to converge are derived. Moreover, it is analytically shown that all the achievable operating points in the throughput region are stable conjectural equilibria corresponding to different conjectures. We also investigate how the conjectural equilibrium can be selected in heterogeneous networks and how the proposed methods can be extended to ad-hoc networks. Numerical simulations verify that the system performance significantly outperforms existing protocols, such as IEEE 802.11 Distributed Coordination Function (DCF) protocol and priority-based fair medium access control (P-MAC) protocol, in terms of throughput, fairness, convergence, and stability.
---
paper_title: An anti-jamming stochastic game for cognitive radio networks

paper_content:

Various spectrum management schemes have been proposed in recent years to improve the spectrum utilization in cognitive radio networks. However, few of them have considered the existence of cognitive attackers who can adapt their attacking strategy to the time-varying spectrum environment and the secondary users' strategy. In this paper, we investigate the security mechanism when secondary users are facing the jamming attack, and propose a stochastic game framework for anti-jamming defense. At each stage of the game, secondary users observe the spectrum availability, the channel quality, and the attackers' strategy from the status of jammed channels. According to this observation, they will decide how many channels they should reserve for transmitting control and data messages and how to switch between the different channels. Using the minimax-Q learning, secondary users can gradually learn the optimal policy, which maximizes the expected sum of discounted payoffs defined as the spectrum-efficient throughput. The proposed stationary policy in the anti-jamming game is shown to achieve much better performance than the policy obtained from myopic learning, which only maximizes each stage's payoff, and a random defense strategy, since it successfully accommodates the environment dynamics and the strategic behavior of the cognitive attackers.
---
paper_title: A game-theoretical anti-jamming scheme for cognitive radio networks

paper_content:

Cognitive radio networks are a promising solution to the spectrum scarcity issue. However, cognitive radio networks are vulnerable to various kinds of security attacks, among which the jamming attack has attracted great attention as it can significantly degrade spectrum utilization. In this article we model the jamming and anti-jamming process as a Markov decision process. With this approach, secondary users are able to avoid the jamming attack launched by external attackers and therefore maximize the payoff function. We first use a policy iteration method to solve the problem. However, this approach is computationally intensive. To decrease the computation complexity, Q-function is used as an alternate method. Furthermore, we propose an algorithm to solve the Q-function. The simulation results indicate that our approach can achieve better performance than existing approaches to defend against the jamming attack.
---
paper_title: Transmission control in cognitive radio as a Markovian dynamic game: Structural result on randomized threshold policies

paper_content:

This paper considers an uplink time division multiple access (TDMA) cognitive radio network where multiple cognitive radios (secondary users) attempt to access a spectrum hole. We assume that each secondary user can access the channel according to a decentralized predefined access rule based on the channel quality and the transmission delay of each secondary user. By modeling secondary user block fading channel qualities as a finite state Markov chain, we formulate the transmission rate adaptation problem of each secondary user as a general-sum Markovian dynamic game with a delay constraint. Conditions are given so that the Nash equilibrium transmission policy of each secondary user is a randomized mixture of pure threshold policies. Such threshold policies can be easily implemented. We then present a stochastic approximation algorithm that can adaptively estimate the Nash equilibrium policies and track such policies for non-stationary problems where the statistics of the channel and user parameters evolve with time.
---
paper_title: Efficient QoS Provisioning for Adaptive Multimedia in Mobile Communication Networks by Reinforcement Learning *

paper_content:

The scarcity and large fluctuations of link bandwidth in wireless networks have motivated the development of adaptive multimedia services in mobile communication networks, where it is possible to increase or decrease the bandwidth of individual ongoing flows. This paper studies the issues of quality of service (QoS) provisioning in such systems. In particular, call admission control and bandwidth adaptation are formulated as a constrained Markov decision problem. The rapid growth in the number of states and the difficulty in estimating state transition probabilities in practical systems make it very difficult to employ classical methods to find the optimal policy. We present a novel approach that uses a form of discounted reward reinforcement learning known as Q-learning to solve QoS provisioning for wireless adaptive multimedia. Q-learning does not require the explicit state transition model to solve the Markov decision problem; therefore more general and realistic assumptions can be applied to the underlying system model for this approach than in previous schemes. Moreover, the proposed scheme can efficiently handle the large state space and action set of the wireless adaptive multimedia QoS provisioning problem. Handoff dropping probability and average allocated bandwidth are considered as QoS constraints in our model and can be guaranteed simultaneously. Simulation results demonstrate the effectiveness of the proposed scheme in adaptive multimedia mobile communication networks.
---
paper_title: Computing Equilibria in Multiplayer Stochastic Games of Imperfect Information

paper_content:

Computing a Nash equilibrium in multiplayer stochastic games is a notoriously difficult problem. Prior algorithms have been proven to converge in extremely limited settings and have only been tested on small problems. In contrast, we recently presented an algorithm for computing approximate jam/fold equilibrium strategies in a three-player nolimit Texas hold'em tournament--a very large real-world stochastic game of imperfect information [5]. In this paper we show that it is possible for that algorithm to converge to a non-equilibrium strategy profile. However, we develop an ex post procedure that determines exactly how much each player can gain by deviating from his strategy and confirm that the strategies computed in that paper actually do constitute an e-equilibrium for a very small e (0.5% of the tournament entry fee). Next, we develop several new algorithms for computing a Nash equilibrium in multiplayer stochastic games (with perfect or imperfect information) which can provably never converge to a non-equilibrium. Experiments show that one of these algorithms outperforms the original algorithm on the same poker tournament. In short, we present the first algorithms for provably computing an e-equilibrium of a large stochastic game for small e. Finally, we present an efficient algorithm that minimizes external regret in both the perfect and imperfect information cases.
---
paper_title: A Dynamical Games Approach to Transmission-Rate Adaptation in Multimedia WLAN

paper_content:

This paper considers the scheduling, rate adaptation, and buffer management in a multiuser wireless local-area network (WLAN) where each user transmits scalable video payload. Based on opportunistic scheduling, users access the available medium (channel) in a decentralized manner. The rate adaptation problem of the WLAN multimedia networks is then formulated as a general-sum switching control dynamic Markovian game by modelling the video states and block fading channel qualities of each user as a finite states Markovian chain. A value iteration algorithm is proposed to compute the Nash equilibrium policy of such a game and the convergence of the algorithm is also proved. We also give assumptions on the system so that the Nash equilibrium transmission policy of each user is a randomization of two pure policies with each policy nondecreasing on the buffer state occupancy. Based on this structural result, we use the policy gradient algorithm to compute the Nash equilibrium policy.
---
paper_title: Dynamic fictitious play, dynamic gradient play, and distributed convergence to Nash equilibria

paper_content:

We consider a continuous-time form of repeated matrix games in which player strategies evolve in reaction to opponent actions. Players observe each other's actions, but do not have access to other player utilities. Strategy evolution may be of the best response sort, as in fictitious play, or a gradient update. Such mechanisms are known to not necessarily converge. We introduce a form of "dynamic" fictitious and gradient play strategy update mechanisms. These mechanisms use derivative action in processing opponent actions and, in some cases, can lead to behavior converging to Nash equilibria in previously nonconvergent situations. We analyze convergence in the case of exact and approximate derivative measurements of the dynamic update mechanisms. In the ideal case of exact derivative measurements, we show that convergence to Nash equilibrium can always be achieved. In the case of approximate derivative measurements, we derive a characterization of local convergence that shows how the dynamic update mechanisms can converge if the traditional static counterparts do not. We primarily discuss two player games, but also outline extensions to multiplayer games. We illustrate these methods with convergent simulations of the well known Shapley and Jordan counterexamples.
---
paper_title: A New QoS Provisioning Method for Adaptive Multimedia in Wireless Networks

paper_content:

Future wireless networks are designed to support adaptive multimedia by controlling individual ongoing flows to increase or decrease their bandwidths in response to changes in traffic load. There is growing interest in quality-of-service (QoS) provisioning under this adaptive multimedia framework, in which a bandwidth adaptation algorithm needs to be used in conjunction with the call admission control algorithm. This paper presents a novel method for QoS provisioning via average reward reinforcement learning in conjunction with stochastic approximation, which can maximize the network revenue subject to several predetermined QoS constraints. Unlike other model-based algorithms (e.g., linear programming), our scheme does not require explicit state transition probabilities, and therefore, the assumptions behind the underlying system model are more realistic than those in previous schemes. In addition, when we consider the status of neighboring cells, the proposed scheme can dynamically adapt to changes in traffic condition. Moreover, the algorithm can control the bandwidth adaptation frequency effectively by accounting for the cost of bandwidth switching in the model. The effectiveness of the proposed approach is demonstrated using simulation results in adaptive multimedia wireless networks.
---
paper_title: Stochastic Power Adaptation with Multiagent Reinforcement Learning for Cognitive Wireless Mesh Networks

paper_content:

As the scarce spectrum resource is becoming overcrowded, cognitive radio indicates great flexibility to improve the spectrum efficiency by opportunistically accessing the authorized frequency bands. One of the critical challenges for operating such radios in a network is how to efficiently allocate transmission powers and frequency resource among the secondary users (SUs) while satisfying the quality-of-service constraints of the primary users. In this paper, we focus on the noncooperative power allocation problem in cognitive wireless mesh networks formed by a number of clusters with the consideration of energy efficiency. Due to the SUs' dynamic and spontaneous properties, the problem is modeled as a stochastic learning process. We first extend the single-agent Q-learning to a multiuser context, and then propose a conjecture-based multiagent Q-learning algorithm to achieve the optimal transmission strategies with only private and incomplete information. An intelligent SU performs Q-function updates based on the conjecture over the other SUs' stochastic behaviors. This learning algorithm provably converges given certain restrictions that arise during the learning procedure. Simulation experiments are used to verify the performance of our algorithm and demonstrate its effectiveness of improving the energy efficiency.
---
paper_title: A game theoretic model for stochastic routing in self-organized MANETs

paper_content:

In this paper, we propose a game theoretic model for zero-sum stochastic routing game in presence of the intelligent attackers in mobile ad hoc networks (MANETs). In each and every stage of the game, the source node observes the available multiple paths, the residual bandwidth of the paths, quality of the paths, and the strategy of the attackers from the previous stage of the game. Based on this observation, the source node selects an optimal routing strategy by using minimax-Q learning for secure multihop data flow from source to destination through a attack free path among the multiple paths. The selected optimal routing strategy of multihop data flow maximizes the expected payoff defined as the bandwidth utilization. The proposed technique achieves significant performance gains in terms of bandwidth utilization in MANETs. It also provides a randomized security of multihop data flow by accommodating the stochastic multihop data flow, the system dynamics, and the strategic behaviors of the attackers.
---
paper_title: Correlated Q-Learning

paper_content:

This paper introduces Correlated-Q (CE-Q) learning, a multiagent Q-learning algorithm based on the correlated equilibrium (CE) solution concept. CE-Q generalizes both Nash-Q and Friend-and-Foe-Q: in general-sum games, the set of correlated equilibria contains the set of Nash equilibria; in constant-sum games, the set of correlated equilibria contains the set of minimax equilibria. This paper describes experiments with four variants of CE-Q, demonstrating empirical convergence to equilibrium policies on a testbed of general-sum Markov games.
---
paper_title: Opportunistic Spectrum Access in Cognitive Radio Networks: Global Optimization Using Local Interaction Games

paper_content:

We investigate the problem of achieving global optimization for distributed channel selections in cognitive radio networks (CRNs), using game theoretic solutions. To cope with the lack of centralized control and local influences, we propose two special cases of local interaction game to study this problem. The first is local altruistic game, in which each user considers the payoffs of itself as well as its neighbors rather than considering itself only. The second is local congestion game, in which each user minimizes the number of competing neighbors. It is shown that with the proposed games, global optimization is achieved with local information. Specifically, the local altruistic game maximizes the network throughput and the local congestion game minimizes the network collision level. Also, the concurrent spatial adaptive play (C-SAP), which is an extension of the existing spatial adaptive play (SAP), is proposed to achieve the global optimum both autonomously as well as rapidly.
---
paper_title: Multiagent Q-learning for aloha-like spectrum access in cognitive radio systems

paper_content:

An Aloha-like spectrum access scheme without negotiation is considered for multiuser and multichannel cognitive radio systems. To avoid collisions incurred by the lack of coordination, each secondary user learns how to select channels according to its experience. Multiagent reinforcement leaning (MARL) is applied for the secondary users to learn good strategies of channel selection. Specifically, the framework of Q-learning is extended from single user case to multiagent case by considering other secondary users as a part of the environment. The dynamics of the Q-learning are illustrated using a Metrick-Polak plot, which shows the traces of Q-values in the two-user case. For both complete and partial observation cases, rigorous proofs of the convergence of multiagent Q-learning without communications, under certain conditions, are provided using the Robins-Monro algorithm and contraction mapping, respectively. The learning performance (speed and gain in utility) is evaluated by numerical simulations.
---
paper_title: Cooperative Control and Potential Games

paper_content:

We present a view of cooperative control using the language of learning in games. We review the game-theoretic concepts of potential and weakly acyclic games, and demonstrate how several cooperative control problems, such as consensus and dynamic sensor coverage, can be formulated in these settings. Motivated by this connection, we build upon game-theoretic concepts to better accommodate a broader class of cooperative control problems. In particular, we extend existing learning algorithms to accommodate restricted action sets caused by the limitations of agent capabilities and group based decision making. Furthermore, we also introduce a new class of games called sometimes weakly acyclic games for time-varying objective functions and action sets, and provide distributed algorithms for convergence to an equilibrium.
---
paper_title: Learning to Compete for Resources in Wireless Stochastic Games

paper_content:

In this paper, we model the various users in a wireless network (e.g., cognitive radio network) as a collection of selfish autonomous agents that strategically interact to acquire dynamically available spectrum opportunities. Our main focus is on developing solutions for wireless users to successfully compete with each other for the limited and time-varying spectrum opportunities, given experienced dynamics in the wireless network. To analyze the interactions among users given the environment disturbance, we propose a stochastic game framework for modeling how the competition among users for spectrum opportunities evolves over time. At each stage of the stochastic game, a central spectrum moderator (CSM) auctions the available resources, and the users strategically bid for the required resources. The joint bid actions affect the resource allocation and, hence, the rewards and future strategies of all users. Based on the observed resource allocations and corresponding rewards, we propose a best-response learning algorithm that can be deployed by wireless users to improve their bidding policy at each stage. The simulation results show that by deploying the proposed best-response learning algorithm, the wireless users can significantly improve their own bidding strategies and, hence, their performance in terms of both the application quality and the incurred cost for the used resources.
---
paper_title: Game Theory in Wireless and Communication Networks

paper_content:

This unified treatment of game theory focuses on finding state-of-the-art solutions to issues surrounding the next generation of wireless and communication networks. Future networkswillrelyonautonomousanddistributedarchitecturestoimprovetheefficiency and flexibility of mobile applications, and game theory provides the ideal framework for designing efficient and robust distributed algorithms. This book enables readers to develop a solid understanding of game theory, its applications, and its use as an effective tool for addressing various problems in wireless communication and networking. The key results and tools of game theory are covered, as are various real-world technologies including 3G/4G networks, wireless LANs, sensor networks, cognitive networks, and Internet networks. The book also covers a wide range of techniques for modeling, designing, and analyzing communication networks using game theory, as well as state-of-the-art distributed design techniques. This is an ideal resource for communications engineers, researchers, and graduate and undergraduate students.
---
paper_title: Reinforcement Learning for Repeated Power Control Game in Cognitive Radio Networks

paper_content:

Cognitive radio (CR) users are expected to be uncoordinated users that opportunistically seek the spectrum resource from primary users (PUs) in a competitive way. In most existing works, however, CR users are required to share the interference channel information and power strategies to conduct the game with pricing mechanisms that incur the frequent exchange of information. The requirement of significant communication overheads among CR users impedes fully distributed solutions for the deployment of CR networks, which is a challenging problem in the research communities. In this paper, a robust distributed power control algorithm is designed with low implementation complexity for CR networks through reinforcement learning, which does not require the interference channel and power strategy information among CR users (and from CR users to PUs). To the best of our knowledge, this research provides the solution for the first time for the incomplete-information power control game in CR networks. During the repeated game, CR users can control their power strategies by observing the interference from the feedback signals of PUs and transmission rates obtained in the previous step. This procedure allows achieving high spectrum efficiency while conforming to the interference constraint of PUs. This constrained repeated stochastic game with learning automaton is proved to be asymptotically equivalence to the traditional game with complete information. The properties of existence, diagonal concavity and uniqueness for the game are studied. A Bush-Mosteller reinforcement learning procedure is designed for the power control algorithm, and the properties of convergence and learning rate of the algorithm are analyzed. The performance of the learning-based power control algorithm is thoroughly investigated with simulation results, which demonstrates the effectiveness of the proposed algorithm in solving variety of practical CR network problems for real-world applications.
---
paper_title: Nash Q-Learning for General-Sum Stochastic Games

paper_content:

We extend Q-learning to a noncooperative multiagent context, using the framework of general-sum stochastic games. A learning agent maintains Q-functions over joint actions, and performs updates based on assuming Nash equilibrium behavior over the current Q-values. This learning protocol provably converges given certain restrictions on the stage games (defined by Q-values) that arise during learning. Experiments with a pair of two-player grid games suggest that such restrictions on the game structure are not necessarily required. Stage games encountered during learning in both grid environments violate the conditions. However, learning consistently converges in the first grid game, which has a unique equilibrium Q-function, but sometimes fails to converge in the second, which has three different equilibrium Q-functions. In a comparison of offline learning performance in both games, we find agents are more likely to reach a joint optimal path with Nash Q-learning than with a single-agent Q-learning method. When at least one agent adopts Nash Q-learning, the performance of both agents is better than using single-agent Q-learning. We have also implemented an online version of Nash Q-learning that balances exploration with exploitation, yielding improved performance.
---
paper_title: How to Select Optimal Gateway in Multi-Domain Wireless Networks: Alternative Solutions without Learning

paper_content:

Gateways are a crucial part of wireless networks. In multi-domain wireless networks, the existing solution to the problem of optimal gateway selection is based on distributed learning. While such a solution is interesting and useful, it has a fundamental limitation: the learning algorithm may stay for long time in a Nash Equilibrium that does not correspond to the optimal gateway selection. This stay can be so long that people can hardly wait for the convergence of the learning algorithm to the optimal gateway selection. In this paper, we present a systematic study of the gateway selection problem. We distinguish three cases and present an alternative solution to the problem in each of these cases: for public link costs, an algorithm to compute the optimal gateway selection directly; for two domains with private link costs, a cryptographic protocol; for three or more domains with private link costs, a perturbation-based protocol. In all the three cases, our solutions accurately compute the optimal gateway selection within reasonable amounts of time, although we emphasize that our solutions are NOT improvements to the gateway selection solutions based on distributed learning (mainly because our solutions are centralized instead of distributed).
---
paper_title: An Interference-Minimization Potential Game for OFDMA-Based Distributed Spectrum Sharing Systems

paper_content:

Wireless orthogonal frequency-division multiple-access (OFDMA) networks, where distributed users can access the spectrum dynamically, offer great flexibility and the potential for the efficient utilization of scarce spectrum resources. Despite that, managing such large-scale networks while maintaining fair and efficient spectrum usage poses a great challenge, mainly due to cochannel interference from the spatially reusable subcarrier. This paper considers the problem of interference minimization in such a scenario from a game-theoretical viewpoint. A general framework that defines the distributed OFDMA-based spectrum access problem is presented. Next, our game-theoretical analysis shows that the proposed interference-minimizing utility function exhibits the properties of a potential game. Given a deterministic number of subcarriers by each player, there exists a pure-strategy Nash equilibrium solution, and therefore, convergence can be guaranteed via sequential best-response dynamics. Our simulation results verify the analysis, and at the same time, the fairness and optimality of the solutions obtained through the proposed game are examined.
---
paper_title: Game Theory and Learning for Wireless Networks: Fundamentals and Applications

paper_content:

* The first tutorial-style book that gives all the relevant theory at the right level of rigor, for the wireless communications engineer. * Bridges the gap between theory and practice by giving examples and case studies showing how game theory can solve real-word problems. * Contains algorithms and techniques to implement game theory in wireless terminals. Written by leading experts in the field, Game Theory and Learning for Wireless Networks Covers how theory can be used to solve prevalent problems in wireless networks such as power control, resource allocation or medium access control. With the emphasis now on promoting 'green' solutions in the wireless field where power consumption is minimized, there is an added focus on developing network solutions that maximizes the use of the spectrum available. With the growth of distributed wireless networks such as Wi-Fi and the Internet; the push to develop ad hoc and cognitive networks has led to a considerable interest in applying game theory to wireless communication systems. Game Theory and Learning for Wireless Networks is the first comprehensive resource of its kind, and is ideal for wireless communications R&D engineers and graduate students. Samson Lasaulce is a senior CNRS researcher at the Laboratory of Signals and Systems (LSS) at Suplec, Gif-sur-Yvette, France. He is also a part-time professor in the Department of Physics at cole Polytechnique, Palaiseau, France. Hamidou Tembine is a professor in the Department of Telecommunications at Suplec, Gif-sur-Yvette, France. Merouane Debbah is a professor at Suplec, Gif-sur-Yvette, France. He is the holder of the Alcatel-Lucent chair in flexible radio since 2007. The first tutorial style book that gives all the relevant theory, at the right level of rigour, for the wireless communications engineer Bridges the gap between theory and practice by giving examples and case studies showing how game theory can solve real world resource allocation problems Contains algorithms and techniques to implement game theory in wireless terminals
---
paper_title: Self-Organization in Decentralized Networks: A Trial and Error Learning Approach

paper_content:

In this paper, the problem of channel selection and power control is jointly analyzed in the context of multiple-channel clustered ad-hoc networks, i.e., decentralized networks in which radio devices are arranged into groups (clusters) and each cluster is managed by a central controller (CC). This problem is modeled by game in normal form in which the corresponding utility functions are designed for making some of the Nash equilibria (NE) to coincide with the solutions to a global network optimization problem. In order to ensure that the network operates in the equilibria that are globally optimal, a learning algorithm based on the paradigm of trial and error learning is proposed. These results are presented in the most general form and therefore, they can also be seen as a framework for designing both games and learning algorithms with which decentralized networks can operate at global optimal points using only their available local knowledge. The pertinence of the game design and the learning algorithm are highlighted using specific scenarios in decentralized clustered ad hoc networks. Numerical results confirm the relevance of using appropriate utility functions and trial and error learning for enhancing the performance of decentralized networks.
---
paper_title: Decentralized Learning of Nash Equilibria in Multi-Person Stochastic Games With Incomplete Information

paper_content:

A multi-person discrete game where the payoff after each play is stochastic is considered. The distribution of the random payoff is unknown to the players and further none of the players know the strategies or the actual moves of other players. A learning algorithm for the game based on a decentralized team of learning automata is presented. It is proved that all stable stationary points of the algorithm are Nash equilibria for the game. Two special cases of the game are also discussed, namely, game with common payoff and the relaxation labelling problem. The former has applications such as pattern recognition and the latter is a problem widely studied in computer vision. For the two special cases it is shown that the algorithm always converges to a desirable solution. >
---
paper_title: Non-cooperative power control for wireless ad hoc networks with repeated games

paper_content:

One of the distinctive features in a wireless ad hoc network is lack of any central controller or single point of authority, in which each node/link then makes its own decisions independently. Therefore, fully cooperative behaviors, such as cooperation for increasing system capacity, mitigating interference for each other, or honestly revealing private information, might not be directly applied. It has been shown that power control is an efficient approach to achieve quality of service (QoS) requirement in ad hoc networks. However, the existing work has largely relied on cooperation among different nodes/links or a pricing mechanism that often needs a third-party involvement. In this paper, we aim to design a non-cooperative power control algorithm without pricing mechanism for ad hoc networks. We view the interaction among the users' decision for power level as a repeated game. With the theory of stochastic fictitious play (SFP), we propose a reinforcement learning algorithm to schedule each user's power level. There are three distinctive features in our proposed scheme. First, the user's decision at each stage is self-incentive with myopic best response correspondence. Second, the dynamics arising from our proposed algorithm eventually converges to pure Nash equilibrium (NE). Third, our scheme does not need any information exchange or to observe the opponents' private information. Therefore, this proposed algorithm can safely run in a fully selfish environment without any additional pricing and secure mechanism. Simulation study demonstrates the effectiveness of our proposed scheme.
---
paper_title: If multi-agent learning is the answer, what is the question?

paper_content:

The area of learning in multi-agent systems is today one of the most fertile grounds for interaction between game theory and artificial intelligence. We focus on the foundational questions in this interdisciplinary area, and identify several distinct agendas that ought to, we argue, be separated. The goal of this article is to start a discussion in the research community that will result in firmer foundations for the area.
---
paper_title: Near-Optimal Power Control in Wireless Networks: A Potential Game Approach

paper_content:

We study power control in a multi-cell CDMA wireless system whereby self-interested users share a common spectrum and interfere with each other. Our objective is to design a power control scheme that achieves a (near) optimal power allocation with respect to any predetermined network objective (such as the maximization of sum-rate, or some fairness criterion). To obtain this, we introduce the potential-game approach that relies on approximating the underlying noncooperative game with a "close" potential game, for which prices that induce an optimal power allocation can be derived. We use the proximity of the original game with the approximate game to establish through Lyapunov-based analysis that natural user-update schemes (applied to the original game) converge within a neighborhood of the desired operating point, thereby inducing near-optimal performance in a dynamical sense. Additionally, we demonstrate through simulations that the actual performance can in practice be very close to optimal, even when the approximation is inaccurate. As a concrete example, we focus on the sum-rate objective, and evaluate our approach both theoretically and empirically.
---
paper_title: Convergent Multiple-Timescales Reinforcement Learning Algorithms In Normal Form Games

paper_content:

We consider reinforcement learning algorithms in normal form games. Using two-timescales stochastic approximation, we introduce a model-free algorithm which is asymptotically equivalent to the smooth fictitious play algorithm, in that both result in asymptotic pseudotrajectories to the flow defined by the smooth best response dynamics. Both of these algorithms are shown to converge almost surely to Nash distribution in two-player zero-sum games and N -player partnership games. However, there are simple games for which these, and most other adaptive processes, fail to converge--in particular, we consider the N -player matching pennies game and Shapley's variant of the rock--scissors--paper game. By extending stochastic approximation results to multiple timescales we can allow each player to learn at a different rate. We show that this extension will converge for two-player zero-sum games and two-player partnership games, as well as for the two special cases we consider.
---
paper_title: Stochastic Power Adaptation with Multiagent Reinforcement Learning for Cognitive Wireless Mesh Networks

paper_content:

As the scarce spectrum resource is becoming overcrowded, cognitive radio indicates great flexibility to improve the spectrum efficiency by opportunistically accessing the authorized frequency bands. One of the critical challenges for operating such radios in a network is how to efficiently allocate transmission powers and frequency resource among the secondary users (SUs) while satisfying the quality-of-service constraints of the primary users. In this paper, we focus on the noncooperative power allocation problem in cognitive wireless mesh networks formed by a number of clusters with the consideration of energy efficiency. Due to the SUs' dynamic and spontaneous properties, the problem is modeled as a stochastic learning process. We first extend the single-agent Q-learning to a multiuser context, and then propose a conjecture-based multiagent Q-learning algorithm to achieve the optimal transmission strategies with only private and incomplete information. An intelligent SU performs Q-function updates based on the conjecture over the other SUs' stochastic behaviors. This learning algorithm provably converges given certain restrictions that arise during the learning procedure. Simulation experiments are used to verify the performance of our algorithm and demonstrate its effectiveness of improving the energy efficiency.
---
paper_title: Improving energy efficiency in Green femtocell networks: A hierarchical reinforcement learning framework

paper_content:

This paper investigates energy efficiency for the two-tier femtocell networks through combining game theory and stochastic learning. With the Stackelberg game formulation, a hierarchical reinforcement learning framework is developed to study the joint expected utility maximization of macrocells and femtocells. The macrocells behave as the leaders and the femtocells are followers during the learning procedure. At each time step, the leaders commit to dynamic strategies based on the best responses of the followers, while the followers compete against each other with no further information but the leaders' strategy information. In this paper, two learning algorithms are proposed to schedule each cell's transmission power. Numerical results are presented to validate the proposed studies and show that the two learning algorithms substantially improve the energy efficiency of the femtocell networks.
---
paper_title: Review: Reinforcement learning for context awareness and intelligence in wireless networks: Review, new features and open issues

paper_content:

In wireless networks, context awareness and intelligence are capabilities that enable each host to observe, learn, and respond to its complex and dynamic operating environment in an efficient manner. These capabilities contrast with traditional approaches where each host adheres to a predefined set of rules, and responds accordingly. In recent years, context awareness and intelligence have gained tremendous popularity due to the substantial network-wide performance enhancement they have to offer. In this article, we advocate the use of reinforcement learning (RL) to achieve context awareness and intelligence. The RL approach has been applied in a variety of schemes such as routing, resource management and dynamic channel selection in wireless networks. Examples of wireless networks are mobile ad hoc networks, wireless sensor networks, cellular networks and cognitive radio networks. This article presents an overview of classical RL and three extensions, including events, rules and agent interaction and coordination, to wireless networks. We discuss how several wireless network schemes have been approached using RL to provide network performance enhancement, and also open issues associated with this approach. Throughout the paper, discussions are presented in a tutorial manner, and are related to existing work in order to establish a foundation for further research in this field, specifically, for the improvement of the RL approach in the context of wireless networking, for the improvement of the RL approach through the use of the extensions in existing schemes, as well as for the design and implementation of RL in new schemes.
---
paper_title: Experience-weighted Attraction Learning in Normal Form Games

paper_content:

In ‘experience-weighted attraction’ (EWA) learning, strategies have attractions that reflect initial predispositions, are updated based on payoff experience, and determine choice probabilities according to some rule (e.g., logit). A key feature is a parameter δ that weights the strength of hypothetical reinforcement of strategies that were not chosen according to the payoff they would have yielded, relative to reinforcement of chosen strategies according to received payoffs. The other key features are two discount rates, φ and ρ, which separately discount previous attractions, and an experience weight. EWA includes reinforcement learning and weighted fictitious play (belief learning) as special cases, and hybridizes their key elements. When δ= 0 and ρ= 0, cumulative choice reinforcement results. When δ= 1 and ρ=φ, levels of reinforcement of strategies are exactly the same as expected payoffs given weighted fictitious play beliefs. Using three sets of experimental data, parameter estimates of the model were calibrated on part of the data and used to predict a holdout sample. Estimates of δ are generally around .50, φ around .8 − 1, and ρ varies from 0 to φ. Reinforcement and belief-learning special cases are generally rejected in favor of EWA, though belief models do better in some constant-sum games. EWA is able to combine the best features of previous approaches, allowing attractions to begin and grow flexibly as choice reinforcement does, but reinforcing unchosen strategies substantially as belief-based models implicitly do.
---
paper_title: Game Theory in Wireless and Communication Networks

paper_content:

This unified treatment of game theory focuses on finding state-of-the-art solutions to issues surrounding the next generation of wireless and communication networks. Future networkswillrelyonautonomousanddistributedarchitecturestoimprovetheefficiency and flexibility of mobile applications, and game theory provides the ideal framework for designing efficient and robust distributed algorithms. This book enables readers to develop a solid understanding of game theory, its applications, and its use as an effective tool for addressing various problems in wireless communication and networking. The key results and tools of game theory are covered, as are various real-world technologies including 3G/4G networks, wireless LANs, sensor networks, cognitive networks, and Internet networks. The book also covers a wide range of techniques for modeling, designing, and analyzing communication networks using game theory, as well as state-of-the-art distributed design techniques. This is an ideal resource for communications engineers, researchers, and graduate and undergraduate students.
---
paper_title: Sophisticated Experience-Weighted Attraction learning and strategic teaching in repeated games

paper_content:

Most learning models assume players are adaptive (i.e., they respond only to their own previous experience and ignore others' payoff information) and behavior is not sensitive to the way in which players are matched. Empirical evidence suggests otherwise. In this paper, we extend our adaptive experience-weighted attraction (EWA) learning model to capture sophisticated learning and strategic teaching in repeated games. The generalized model assumes there is a mixture of adaptive learners and sophisticated players. An adaptive learner adjusts his behavior the EWA way. A sophisticated player rationally best-responds to her forecasts of all other behaviors. A sophisticated player can be either myopic or farsighted. A farsighted player develops multiple-period rather than single-period forecasts of others' behaviors and chooses to “teach” the other players by choosing a strategy scenario that gives her the highest discounted net present value. We estimate the model using data from p-beauty contests and repeated trust games with incomplete information. The generalized model is better than the adaptive EWA model in describing and predicting behavior. Including teaching also allows an empirical learning-based approach to reputation formation which predicts better than a quantal-response extension of the standard type-based approach.
---
paper_title: Dynamic fictitious play, dynamic gradient play, and distributed convergence to Nash equilibria

paper_content:

We consider a continuous-time form of repeated matrix games in which player strategies evolve in reaction to opponent actions. Players observe each other's actions, but do not have access to other player utilities. Strategy evolution may be of the best response sort, as in fictitious play, or a gradient update. Such mechanisms are known to not necessarily converge. We introduce a form of "dynamic" fictitious and gradient play strategy update mechanisms. These mechanisms use derivative action in processing opponent actions and, in some cases, can lead to behavior converging to Nash equilibria in previously nonconvergent situations. We analyze convergence in the case of exact and approximate derivative measurements of the dynamic update mechanisms. In the ideal case of exact derivative measurements, we show that convergence to Nash equilibrium can always be achieved. In the case of approximate derivative measurements, we derive a characterization of local convergence that shows how the dynamic update mechanisms can converge if the traditional static counterparts do not. We primarily discuss two player games, but also outline extensions to multiplayer games. We illustrate these methods with convergent simulations of the well known Shapley and Jordan counterexamples.
---
paper_title: Learning and transfer in signaling games

paper_content:

We explore how learning to play strategically in one signaling game promotes strategic play in a related signaling game. Following convergence to a pooling equilibrium, payoffs are changed to only support separating equilibria. More strategic play is observed following the change in payoffs than for inexperienced subjects in control sessions, contrary to the prediction of a fictitious play learning model. Introducing a growing proportion of sophisticated learners, subjects who anticipate responders’ behavior following the change in payoffs, enables the model to capture the positive cross-game learning observed in the data.
---
paper_title: Transfer Learning: A Paradigm for Dynamic Spectrum and Topology Management in Flexible Architectures

paper_content:

In this paper, we introduce a novel paradigm of transfer learning for spectrum and topology management in a rapidly deployable opportunistic network for the post disaster and temporary event scenarios. The network architecture is designed to be rapidly changing between different disaster phases, and highly flexible during the temporary event period. Transfer learning is developed to learn the dynamic radio environment from network topologies. This also allows previously learnt information in earlier phases of a deployment to be efficiently used to influence the learning process in later phases of a deployment. A Transfer Learning strategy is designed to change the knowledge base from the most recent phase via multi-agent coordination. We evaluate transfer learning paradigm in a small cell Terrestrial eNB architecture, integrated with Q-Learning and Linear Reinforcement Learning. It is demonstrated that transfer learning significantly improves the initial performance, the convergence speed and the steady state QoS, by exchanging topology information for resource prioritization.
---
paper_title: TACT: A Transfer Actor-Critic Learning Framework for Energy Saving in Cellular Radio Access Networks

paper_content:

Recent works have validated the possibility of improving energy efficiency in radio access networks (RANs), achieved by dynamically turning on/off some base stations (BSs). In this paper, we extend the research over BS switching operations, which should match up with traffic load variations. Instead of depending on the dynamic traffic loads which are still quite challenging to precisely forecast, we firstly formulate the traffic variations as a Markov decision process. Afterwards, in order to foresightedly minimize the energy consumption of RANs, we design a reinforcement learning framework based BS switching operation scheme. Furthermore, to avoid the underlying curse of dimensionality in reinforcement learning, a transfer actor-critic algorithm (TACT), which utilizes the transferred learning expertise in historical periods or neighboring regions, is proposed and provably converges. In the end, we evaluate our proposed scheme by extensive simulations under various practical configurations and show that the proposed TACT algorithm contributes to a performance jumpstart and demonstrates the feasibility of significant energy efficiency improvement at the expense of tolerable delay performance.
---
paper_title: Transfer in Reinforcement Learning Domains

paper_content:

In reinforcement learning (RL) problems, learning agents sequentially execute actions with the goal of maximizing a reward signal. The RL framework has gained popularity with the development of algorithms capable of mastering increasingly complex problems, but learning difficult tasks is often slow or infeasible when RL agents begin with no prior knowledge. The key insight behind "transfer learning" is that generalization may occur not only within tasks, but also across tasks. While transfer has been studied in the psychological literature for many years, the RL community has only recently begun to investigate the benefits of transferring knowledge. This book provides an introduction to the RL transfer problem and discusses methods which demonstrate the promise of this exciting area of research. The key contributions of this book are: Definition of the transfer problem in RL domains Background on RL, sufficient to allow a wide audience to understand discussed transfer concepts Taxonomy for transfer methods in RL Survey of existing approaches In-depth presentation of selected transfer methods Discussion of key open questions By way of the research presented in this book, the author has established himself as the pre-eminent worldwide expert on transfer learning in sequential decision making tasks. A particular strength of the research is its very thorough and methodical empirical evaluation, which Matthew presents, motivates, and analyzes clearly in prose throughout the book. Whether this is your initial introduction to the concept of transfer learning, or whether you are a practitioner in the field looking for nuanced details, I trust that you will find this book to be an enjoyable and enlightening read. Peter Stone, Associate Professor of Computer Science
---
paper_title: Transfer Learning for Reinforcement Learning Domains: A Survey

paper_content:

The reinforcement learning paradigm is a popular way to address problems that have only limited environmental feedback, rather than correctly labeled examples, as is common in other machine learning contexts. While significant progress has been made to improve learning in a single task, the idea of transfer learning has only recently been applied to reinforcement learning tasks. The core idea of transfer is that experience gained in learning to perform one task can help improve learning performance in a related, but different, task. In this article we present a framework that classifies transfer learning methods in terms of their capabilities and goals, and then use it to survey the existing literature, as well as to suggest future directions for transfer learning work.
---

Title: A Survey on Applications of Model-Free Strategy Learning in Cognitive Wireless Networks

Section 1: INTRODUCTION
Description 1: Introduce the concept of Cognitive Radio Networks (CRNs), their features, and the significance of model-free strategy learning in these networks.

Section 2: BACKGROUND: MODEL-FREE LEARNING IN THE DOMAINS OF DISTRIBUTED CONTROL AND GAME THEORY
Description 2: Provide an overview of general-purpose learning methods developed in distributed control and game theory, and categorize them by the coupling among decision-making agents.

Section 3: APPLICATIONS OF MODEL-FREE STRATEGY LEARNING IN COGNITIVE WIRELESS NETWORKS
Description 3: Survey the applications of model-free learning in cognitive wireless networks across different layers of the network protocol stacks, categorized by single-agent systems, loosely coupled multi-agent systems, and game-based multi-agent systems.

Section 4: CHALLENGES AND OPEN ISSUES IN MODEL-FREE LEARNING FOR COGNITIVE RADIO NETWORKS
Description 4: Discuss the challenges and open issues yet to be addressed in the area of learning for distributed control and/or wireless networking, including the goals of learning, coping with outlier agents, and transferring experiences between heterogeneous learners.

Section 5: CONCLUSION
Description 5: Summarize the significance of model-free learning for distributed wireless networks and outline the contributions of this survey, while encouraging further exploration in future research.