Efficient Exploration for Sequential Decision Making with Non-linear Function Approximation = 비선형 함수 근사를 활용한 순차적 의사결정에서의 효율적인 탐색 방법에 관한 연구

국문 초록 (Abstract)

순차적 의사결정 문제에서 학습자(또는 에이전트)는 환경과 직접 상호작용하며 과제를 학습하는 데 필요한 데이터를 획득한다. 다른 머신러닝 패러다임과의 가장 큰 차이점은 학습자가 환경으로부터의 피드백을 활용하여 학습에 적합한 데이터를 직접 수집해야 한다는 점이다. 이러한 순차적 의사결정 문제를 위한 알고리즘을 설계할 때 다음 세 가지 주요 도전 과제가 존재한다: (i) 탐색-활용 균형(Exploration-Exploitation Trade-off): 더 나은 데이터를 획득하기 위해 학습자는 현재의 지식을 활용하여 최적의 결정을 내리는 것과 새로운 정보를 탐색하여 학습을 촉진하는 것 사이에서 균형을 유지해야 한다. (ii) 일반화(Generalization): 현실 세계의 의사결정 문제에서는 선택해야 할 옵션의 집합이 방대하며, 학습 과정에서 동일한 데이터를 반복적으로 마주칠 가능성이 낮다. 따라서 알고리즘은 이전에 본 적 없는 데이터에 대해서도 성능을 보장할 수 있어야 한다. (iii) 지연된 피드백(Delayed Feedback): 바둑과 같은 보드게임 환경에서는 학습자의 초기 행동에 대한 피드백이 게임이 끝난 후에야 주어지는 경우가 있다. 이러한 도전 과제를 해결하는 것뿐만 아니라, 현실 세계의 의사결정 문제를 위한 알고리즘은 성능 보장을 제공해야 한다. 이는 게임과 같은 시뮬레이션 환경과 비교했을 때, 현실 세계에서의 의사결정이 훨씬 더 중요한 영향을 미치기 때문이다. 본 논문에서는 두 가지 주요 순차적 의사결정 문제에 대해 성능 보장을 갖춘 알고리즘을 설계하는 데 초점을 맞춘다.

조합적 컨텍츄얼 밴딧 문제(Contextual Combinatorial Bandits, 2장): 학습 환경에서 제공되는 피드백에 대한 모델링 가정에 의존하지 않는 조합적 컨텍츄얼 밴딧 알고리즘을 논의한다. 심층 신경망의 강력한 표현력을 활용하여 제안된 알고리즘은 뛰어난 일반화 성능을 보이며, UCB 및 톰슨 샘플링을 활용한 효율적인 탐색을 통해 리그렛(regret) 유계에 대한 성능을 보장을 달성한다.

비선형 함수 근사 기반 강화학습(Reinforcement Learning with Non-linear Function Approximation, 3장 \& 4장): 비선형 함수 근사를 기반으로 한 강화학습 알고리즘을 소개한다. 먼저, 기존의 선형 함수 근사 기반 강화학습 알고리즘의 한계를 분석하고, 이를 극복하기 위한 새로운 비선형 강화학습 프레임워크를 제안한다. UCB 및 무작위 탐색 전략을 활용함으로써 제안된 알고리즘이 계산 및 통계적으로 효율적임을 보인다.

다국어 초록 (Multilingual Abstract)

In sequential decision-making problems, a learner (or agent) acquires the data required to learn a task by directly interacting with the environment. A key distinction from other machine learning paradigms is that the learner must actively collect data conducive to learning by leveraging feedback from the environment. Designing algorithms for such sequential decision-making problems involves three major challenges: (i) Exploration-Exploitation Trade-off: To acquire better data, the learner must balance exploiting the current knowledge to make the best decision and exploring new information to facilitate learning. (ii) Generalization: In real-world decision-making problems, the set of options to choose from is often vast. Moreover, it is unlikely to encounter the same data twice during the learning process. Thus, algorithms must ensure performance guarantees even on unseen data. (iii) Delayed Feedback: In some environments, such as board games like Go, feedback on the learner's initial actions is only available after the game ends. In addition to addressing these challenges, algorithms for real-world decision-making problems must come with performance guarantees. This is because the impact of decision-making in real-world settings is far more significant than in simulated environments like games. In this thesis, we focus on designing sequential decision-making algorithms with performance guarantees for two primary classes of sequential decision-making problems:

Contextual Combinatorial Bandits (Chapter 2): We discuss contextual combinatorial bandit algorithms that do not rely on modeling assumptions about the feedback received from the interactive environment. Leveraging the powerful representational capacity of deep neural networks, the proposed algorithms excel in generalization. Furthermore, by utilizing UCB and Thompson sampling for efficient exploration, the algorithms achieve rigorous performance guarantees.

Reinforcement Learning with Non-linear Function Approximation (Chapters 3 \& 4): We introduce reinforcement learning algorithms based on non-linear function approximation. We first outline the limitations of existing RL algorithms that rely on linear function approximation and propose a novel non-linear RL framework to overcome these challenges. By employing UCB and randomized exploration strategies, we demonstrate the proposed algorithms are computationally tractable and statistically efficient.

목차 (Table of Contents)

• Abstract i
• Contents v
• List of Tables vi
• List of Figures vii
• Acknowledgement viii
• Chapter 1 Introduction 1
• 1.1 Problems 2
• 1.1.1 Contextual Combinatorial Bandits 2
• 1.1.2 Reinforcement Learning with Function Approximation 3
• 1.2 Summary of Contributions 3
• Chapter 2 Contextual Combinatorial Bandits with Deep Neural Networks 6
• 2.1 Introduction 6
• 2.2 Problem setting 8
• 2.2.1 Contextual Combinatorial Bandit 8
• 2.3 Combinatorial Neural UCB (CN-UCB) 10
• 2.3.1 CN-UCB Algorithm 10
• 2.3.2 Regret of CN-UCB 11
• 2.3.3 Proof Sketch of Theorem 1 12
• 2.4 Combinatorial Neural TS (CN-TS) 14
• 2.4.1 Challenges in Worst-Case Regret Analysis for Combinatorial Actions 14
• 2.4.2 CN-TS Algorithm 15
• 2.4.3 Regret of CN-TS 16
• 2.4.4 Proof Sketch of Theorem 2 17
• 2.5 Numerical Experiments 18
• 2.6 Concluding Remarks 20
• Chapter 3 Optimism-based Exploration for Multinomial Logistic Markov Decision Processes 21
• 3.1 Introduction 21
• 3.1.1 RelatedWork 24
• 3.2 Preliminaries 25
• 3.2.1 Notations 25
• 3.2.2 ProblemFormulation 25
• 3.2.3 Linear Transition Model vs. Multinomial Logistic Transition Model 27
• 3.3 Algorithm and Main Results 28
• 3.3.1 UCRL-MNLAlgorithm 28
• 3.3.2 Regret Bound for UCRL-MNL Algorithm 30
• 3.3.3 Proof Sketch and Key Lemmas 31
• 3.4 Numerical Experiments 32
• 3.5 Concluding Remarks 34
• Chapter 4 Randomized Exploration for Multinomial Logistic Markov Decision Processes 35
• 4.1 Introduction 35
• 4.1.1 Related Work 37
• 4.2 ProblemSetting 39
• 4.2.1 Multinomial Logistic Markov Decision Processes (MNL-MDPs) 40
• 4.2.2 Assumptions 41
• 4.3 Randomized Algorithm for MNL-MDPs having constant-time computationalcost 41
• 4.3.1 Algorithm:RRL-MNL 41
• 4.3.2 Regret bound of RRL-MNL 44
• 4.4 Statistically Improved Algorithm for MNL-MDPs 45
• 4.4.1 Algorithms:ORRL-MNL 46
• 4.4.2 Regret Bound of ORRL-MNL 48
• 4.5 Numerical Experiments 49
• 4.6 ConcludingRemarks 50
• Conclusion and Future Directions 51
• Bibliography 52
• Appendix A: Contextual Combinatorial Bandits with Deep Neural Networks 64
• A.1 Regret Bound for CN-UCB 64
• A.1.1 Proof of Lemma 1 64
• A.1.2 Proof of Corollary 1 67
• A.1.3 Proof of Lemma2 67
• A.1.4 Proof of Theorem 1 70
• A.2 Regret Bound for CN-TS 73
• A.2.1 Proof of Lemma 3 73
• A.2.2 Proof of Theorem 2 74
• A.3 Auxiliary Lemmas 80
• A.4 Extensions from Neural Bandits for Single Action 81
• A.5 Extension of Regret Analysis to α-approximation Oracle 83
• A.6 When Time Horizon T Is Unknown 84
• A.6.1 Algorithms 84
• A.6.2 Regret Analysis 85
• A.7 Specific Examples of Combinaotrial Feedback Models 86
• A.7.1 Semi-bandit Model 86
• A.7.2 Document-based Model 87
• A.7.3 Position-based Model 87
• A.7.4 Cascade Model 88
• A.8 Additional Related Work 89
• A.9 Additional Experiments 90
• Appendix B: Optimism-based Exploration for Multinomial Logistic Markov Decision Processes 92
• B.1 Further Discussion on the Limitations of the Linear Transition Model 92
• B.1.1 Proof of Proposition 1 92
• B.1.2 Proof of Proposition 2 94
• B.2 Proof of Theorem 3 94
• B.2.1 Proof of Lemma 4 94
• B.2.2 Proof of Lemma 5 99
• B.2.3 Proof of Lemma 6 100
• B.2.4 Proof of Theorem 3 101
• B.3 Supporting Lemmas Used in Appendix B.2 102
• B.4 Auxiliary Lemmas 106
• B.5 Experiment Details106
• Appendix C: Randomized Exploration for Multinomial Logistic Markov Decision Processes 108
• C.1 Additional Notations & Definitions 108
• C.2 Detailed Regret Analysis for RRL-MNL (Theorem 4) 115
• C.2.1 Concentration of Estimated Transition Core θkh 115
• C.2.2 Bound on Prediction Error 127
• C.2.3 Good Events with High Probability 128
• C.2.4 Stochastic Optimism 129
• C.2.5 Bound on Estimation Part 133
• C.2.6 Bound on Pessimism Part 135
• C.2.7 Regret Bound of RRL-MNL 140
• C.3 Detailed Regret Analysis for ORRL-MNL (Theorem 5) 140
• C.3.1 Concentration of Estimated Transition Core θk 140
• C.3.2 Bound on Prediction Error 151
• C.3.3 Good Events with High Probability 158
• C.3.4 Stochastic Optimism 158
• C.3.5 Bound on Estimation Part 161
• C.3.6 Bound on Pessimism Part 172
• C.3.7 Regret Bound of ORRL-MNL 173
• C.4 Optimistic Exploration Extension 173
• C.4.1 Optimism 176
• C.5 Experiment Details 177
• C.6 AuxiliaryLemmas 178
• 초록 180