Sequential Learning and Decision-Making in Wireless Resource Management (eBook)

Rong Zheng, Cunqing Hua (Autoren)

eBook Download: PDF

2017
118 Seiten
Springer International Publishing (Verlag)
978-3-319-50502-2 (ISBN)

Infos

This book lays out the theoretical foundation of the so-called multi-armed bandit (MAB) problems and puts it in the context of resource management in wireless networks. Part I of the book presents the formulations, algorithms and performance of three forms of MAB problems, namely, stochastic, Markov and adversarial. Covering all three forms of MAB problems makes this book unique in the field. Part II of the book provides detailed discussions of representative applications of the sequential learning framework in cognitive radio networks, wireless LANs and wireless mesh networks. 

Both individuals in industry and those in the wireless research community will benefit from this comprehensive and timely treatment of these topics. Advanced-level students studying communications engineering and networks will also find the content valuable and accessible.

Inhalt

Preface 6
Acknowledgements 8
Contents 9
Acronyms 12
Part I Theory 13
1 Introduction 14
1.1 The Gambler's Dilemma 14
1.2 A Taxonomy of Multi-armed Bandit Problems 15
1.3 Organization 17
References 17
2 Stochastic Multi-armed Bandit 19
2.1 Problem Formulation 19
2.2 Theoretical Lower Bound 21
2.3 Algorithms 22
2.3.1 Upper Confidence Bound (UCB) Strategies 23
2.3.2 ?-Greedy Policy 27
2.3.3 Thompson Sampling Policy 28
2.4 Variants of Stochastic Multi-armed Bandit 29
2.4.1 Multiplay MAB 29
2.4.2 MAB with Switching Costs 30
2.4.3 Pure Exploration MAB 31
2.5 Summary 34
References 34
3 Markov Multi-armed Bandit 36
3.1 Problem Formulation 36
3.1.1 Markov MAB and Markov Decision Process 37
3.1.2 Optimal Policies for Restless Markov MABs with Complete Information 38
3.2 Algorithms 39
3.2.1 Rested Markov MAB 40
3.2.2 Restless Markov MAB 41
3.3 Summary 48
References 48
4 Adversarial Multi-armed Bandit 49
4.1 Problem Formulation 49
4.2 Algorithms 53
4.2.1 Weighted Average Prediction Algorithm 53
4.2.2 Following-the-Perturbed-Leader (FPL) Algorithm 56
4.2.3 Implicitly Normalized Forecaster (INF) Algorithm 59
4.2.4 Internal-Regret Minimizing Algorithm 60
4.3 Game Theoretical Results for Multiplayer Adversarial Multi-armed Bandit 62
4.4 Summary 65
References 65
Part II Applications 66
5 Spectrum Sensing and Access in Cognitive Radio Networks 67
5.1 Introduction 67
5.2 Problem Formulation 69
5.2.1 Single SU with IID Rewards 69
5.2.2 Single SU with Markov Reward Processes 70
5.2.3 Multiple SUs 70
5.3 Solution Approaches 71
5.3.1 Cooperative Spectrum Access 71
5.3.2 Distributed Learning and Allocation 73
5.4 Summary 74
References 74
6 Sniffer-Channel Assignment in Multichannel Wireless Networks 76
6.1 Introduction 76
6.2 Problem Formulation 78
6.2.1 Optimal Channel Assignment in the Nominal Form 79
6.2.2 Linear Bandit for Optimal Channel Assignment with Uncertainty 80
6.2.3 Extensions 82
6.3 Solution Approaches 84
6.3.1 Spanners 84
6.3.2 An Upper Confidence Bound (UCB)-Based Policy 84
6.3.3 An ?-Greedy Algorithm with Spanner 85
6.3.4 An Upper Confidence Bound (UCB)-Based Policy for Switching Cost Consideration 86
6.3.5 Approximate Learning Algorithms 87
6.4 Numerical Results 91
6.5 Summary 93
References 94
7 Online Routing in Multi-hop Wireless Networks 96
7.1 Introduction 96
7.2 System Model and Problem Statement 98
7.2.1 Network Model 98
7.2.2 Online Routing Problem 99
7.3 Algorithm 100
7.4 Numerical Results 101
7.5 Summary 103
References 106
8 Channel Selection and User Association in WiFi Networks 107
8.1 Introduction 107
8.2 System Models and Problem Statement 109
8.2.1 Network Model 109
8.2.2 Airtime Cost 110
8.2.3 Channel Selection and User Association (CSUA) Problem 110
8.3 Adversarial MAB Framework for CSUA Problem and Algorithms 111
8.3.1 Adversarial MAB Formulation 111
8.3.2 Algorithm 113
8.4 Performance Evaluation 115
8.4.1 Simulation Setup 115
8.4.2 Simulation Results 115
8.5 Summary 118
References 119
Index 120

Produkt-Details

• Erscheint lt. Verlag: 5.1.2017
• Reihe/Serie: Wireless Networks
• Reihe/Serie: Wireless Networks
• Zusatzinfo: XIII, 118 p. 22 illus.
• Verlagsort: Cham
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Netzwerke
• Schlagworte: Bandits • Cognitive Radio Networks • Exploration and exploitation • Incomplete Information • Multi-armed bandit • Sequential Learning • Wireless data services • Wireless LANs • wireless mesh networks • wireless networks • Wireless resource management
• ISBN-10: 3-319-50502-5 / 3319505025
• ISBN-13: 978-3-319-50502-2 / 9783319505022