Reinforcement Learning ตัดสินใจเลือกทางที่ดีที่สุดอย่างไร Explore vs Exploit

Reinforcement Learning (RL) เป็น Machine Learning ประเภทหนึ่งที่เหมาะกับปัญหาที่มีหลายทางเลือก ว่าการเลือกทางใดจะได้รับประโยชน์มากที่สุด เช่น ระบบการแนะนำสินค้า ระบบการแนะนำโปรโมชัน ว่าแนะนำอะไรจะทำยอดขายได้ดีกว่า หรือบอทที่มีชื่อเสียงอย่าง AlphaGo ที่เป็น AI หมากล้อม แนะนำว่าควรเดินหมากที่ตำแหน่งใด บทความนี้จะอธิบายวิธีการตัดสินใจของ Reinforcement Learning

https://www.nature.com/articles/s42005-021-00684-3

ประเภทของ Machine Learning

http://www.cognub.com/index.php/cognitive-platform/

องค์ประกอบของ Reinforcement Learning

1. Agent (ตัวแทน / บอท)
2. Environment (สภาพแวดล้อม)
3. State (s) (สถานะ) สถานะการณ์ของสภาพแวดล้อม ณ เวลาที่กำหนด
4. Action (a) (การกระทำ) ตัวเลือกที่บอทเลือกกระทำ
5. Reward (รางวัล) รางวัลที่เกิดขึ้นจากการกระทำ

https://www.researchgate.net/figure/Reinforcement-learning-schematic-Reinforcement-learning-RL-can-be-formulated-as-a_fig4_322424392

การทำงานของ Reinforcement Learning

• กำหนดนิยามของสภาพแวดล้อม
• กำหนดสถานะของสภาพแวดล้อมว่าประกอบด้วยอะไรบ้าง
• กำหนดตัวเลือกทั้งหมดที่บอทสามารถเลือกกระทำในสภาพแวดล้อมนั้น
• บอทจะตัดสินใจเลือกตัวเลือกและกระทำตามตัวเลือกนั้น
• สถานะของสภาพแวดล้อมจะเปลี่ยนไปหลังจากมีการกระทำเกิดขึ้น
• หลังการกระทำจะได้รับรางวัลจากการกระทำนั้น (บางครั้งอาจเป็นการลงโทษแทนรางวัล)

การทำงานของ Reinforcement Learning เปรียบได้กับการลองผิดลองถูกของเด็ก เริ่มต้นบอทจะไม่รู้ว่าควรเลือกการกระทำแบบใด แต่หลังจากได้ลองกระทำและเรียนรู้จากรางวัลที่ได้รับแล้ว บอทจะรู้ว่าควรเลือกการกระทำใดเพื่อให้ได้รับรางวัลมากที่สุด

แบนดิทหลายแขน (Multi-Armed Bandit)

ปัญหาของการมีหลายตัวเลือกให้ตัดสินใจ เรียกว่า ปัญหาแบนดิทหลายแขน (Multi-Armed Bandit) ซึ่งมีที่มาจากการเล่นตู้สล็อต คือกรณีที่มีตู้สล็อตหลายตู้ ควรเลือกเล่นตู้ใดจึงจะได้ผลรางวัลที่ดีที่สุด เมื่อประยุกต์ Reinforcement Learning กับ Multi-Armed Bandit จะแทนที่แต่ละแขนของแบนดิทด้วยแต่ละตัวเลือก

ตัวอย่างการทำงานของ Reinforcement Learning

• กำหนดสภาพแวดล้อมเป็นการแสดงโฆษณาให้ลูกค้าแต่ละคนทาง Social Media
• กำหนดสถานะประกอบด้วย 2 ค่า คือจำนวนครั้งที่แสดงโฆษณาและจำนวนครั้งที่โฆษณาถูกคลิก
• กำหนดตัวเลือก คือมีโฆษณา 4 แบบ
• บอทเลือกโฆษณาที่นำไปแสดงกับลูกค้า
• อัพเดทสถานะของโฆษณานั้น จำนวนครั้งที่แสดงโฆษณาเพิ่มขึ้นหนึ่งหน่วย และหากลูกค้ามีการคลิกให้จำนวนครั้งที่โฆษณาถูกคลิกเพิ่มขึ้นหนึ่งหน่วย
• ถ้าลูกค้ากดคลิกจะได้รับรางวัล 1 คะแนน
• อาจกำหนดเพิ่มเติม ว่าถ้าลูกค้าไม่คลิกจะโดนลงโทษ หรือได้รับรางวัล -1 คะแนน เพราะการแสดงแต่ละครั้งจะมีค่าใช้จ่ายในการยิงโฆษณา

จากตัวอย่างนี้ สามารถเพิ่มประสิทธิภาพโดยการกำหนดสถานะให้ละเอียดมากขึ้น เช่น ข้อมูลการแสดงโฆษณา ข้อมูลของลูกค้า สถานะที่กำหนดใหม่จะประกอบด้วย 1. คือจำนวนครั้งที่แสดงโฆษณา 2. จำนวนครั้งที่โฆษณาถูกคลิก 3. จังหวัดที่แสดงโฆษณา 4. เวลาที่แสดงโฆษณา 5. Social Media Platform 6. อายุของลูกค้า 7. เพศของลูกค้า จะสังเกตได้ว่า ถ้าสถานะมีปัจจัยที่ 3, 4, 5, 6, 7 เพิ่มขึ้นมา จะช่วยให้ตัดสินใจได้ดีขึ้น ว่า จังหวัดใด เวลาใด ช่องทางใด ลูกค้าอายุและเพศแบบใด ควรแสดงโฆษณาแบบใดจึงได้ผลรางวัลที่มากที่สุด

การกำหนดองค์ประกอบของสถานะ เป็นหนึ่งในงานที่ยากของ Reinforcement Learning ว่าต้องกำหนดสถานะด้วยปัจจัยใดบ้าง จึงจะทำให้การตัดสินใจมีประสิทธิภาพ

การตัดสินใจของ Reinforcement Learning Agent

จากตัวอย่างการแนะนำโฆษณา เมื่อเวลาผ่านไปบอทจะรู้ว่าสถานะการแบบใดควรแสดงโฆษณาแบบใด แต่เมื่อเวลาผ่านไปอีกจะไม่สามารถการันตีได้ว่าการเลือกโฆษณานั้นยังคงให้ผลรางวัลที่ดีกว่าแบบอื่น บอทจึงต้องตัดสินใจระหว่างการเลือกโฆษณาแบบเดิมที่ให้ผลรางวัลดี หรือจะลองเลือกโฆษณาแบบอื่นที่อาจได้ผลรางวัลดีกว่าในเวลานั้น

การตัดสินใจระหว่างสองทางเลือกนี้ คือการเลือกระหว่างการเอาประโยชน์จากตัวเลือกเดิม (Exploit) และการสำรวจตัวเลือกใหม่ (Explore) ซึ่งการตัดสินใจระหว่างสองทางนี้จะกำหนดเป็นนโยบาย (Policy) สำหรับให้บอทใช้ว่าควรเลือกทางใด

Reinforcement Learning แบ่งตามการเรียนรู้เป็น 3 ประเภท

1. การเรียนรู้จากข้อมูลใหม่เพิ่มเรื่อย ๆ (Online Learning)
2. การเรียนรู้จากข้อมูลที่เตรียมไว้ และไม่เรียนรู้ข้อมูลใหม่เพิ่ม (Offline Learning)
3. การเรียนรู้จากข้อมูลที่เตรียมไว้ และเรียนรู้ข้อมูลใหม่เพิ่มเรื่อย ๆ (Hybrid Learning)

นโยบายการตัดสินใจ (Decision Policy)

พื้นฐานการคำนวณของ Machine Learning ทุกตัวจะมาจากสถิติศาสตร์ บทความนี้จะยกตัวอย่าง นโยบายการตัดสินใจของ Reinforcement Learning 2 แบบ ซึ่งสามารถประยุกต์ใช้ได้กับ Online Learning, Offline Learning และ Hybrid Learning

1. นโยบายจากสถิติแบบความถี่ (Frequentist Statistics) จะใช้นโยบายการตัดสินใจจากการคำนวนด้วยความถี่ของสิ่งที่เกิดขึ้น เช่น นโยบายจากอัลกอริทึมความเชื่อมั่นขอบเขตบน (Upper Confidence Bound)
2. นโยบายจากสถิติความน่าจะเป็นแบบเบย์ (Bayesian Statistics) จะใช้นโยบายการตัดสินใจโดยกำหนดการแจกแจงไว้ก่อน (Prior Distribution) ก่อนที่จะรู้ค่าการแจกแจงจริงในภายหลัง (Posterior Distribution) เช่น นโยบายจากอัลกอริทึมการสุ่มตัวอย่างแบบทอมสัน (Thompson Sampling)

อัลกอริทึมความเชื่อมั่นขอบเขตบน (Upper Confidence Bound Algorithm: UCB)

1. จากสมการ พจน์ซ้ายคือคุณค่าของตัวเลือก (Action-Values) เมื่อเลือกตัวเลือก a ณ เวลา t เช่น กำหนดให้ Action-Values คือค่าเฉลี่ย (mean) — พจน์ซ้ายเปรียบเสมือนการ Exploit เพราะเป็นค่าจากรางวัลที่รู้แล้ว
2. จากสมการ พจน์ขวาคือขอบเขตบน (Upper Bound) ของตัวเลือก โดย Y คือค่าถ่วงน้ำหนักของขอบเขตบน เช่น กำหนดให้เป็น 1 และ n_a คือจำนวนครั้งที่ตัวเลือก a เคยถูกเลือก ณ เวลา t — พจน์ขวาเปรียบเสมือนการ Explore เพราะเป็นค่าถ่วงน้ำหนักสำหรับการสำรวจตัวเลือกใหม่ (เมื่อตัวเลือก a ถูกเลือกบ่อยขึ้น ค่าของพจน์นี้จะน้อยลง แต่เมื่อเวลาผ่านไปตัวเลือกที่ไม่ค่อยถูกเลือกจะมีค่าของพจน์นี้มากขึ้น ทำให้ตัวเลือกที่ไม่ค่อยถูกเลือกมีโอกาสในการถูกเลือกเพิ่มขึ้น)
3. คำนวณค่าความเชื่อมั่นขอบเขตบนตามสมการให้กับทุกตัวเลือก
4. เลือกกระทำตามตัวเลือกที่ผลคำนวณมีค่ามากที่สุด

1:  # Upper Confidence Bound by ArtSyntax #

2:  state = {dict of state parameters}
3:  action_list = [list of actions]
4:  action_mean_reward_list = np.zeros(len(action_list))
5:  selected_action_count_list = np.zeros(len(action_list))
6:  round = 1
7:  while(not is_end):
8:    action_upper_bound_list = np.sqrt(
        np.log(round) / selected_action_count_list)
9:    selected_action_index = np.argmax(
        action_mean_reward_list + action_upper_bound_list)
10:   selected_action = action_list[selected_action_index]
11:   next_state, reward = make_action(state, selected_action)
12:   action_mean_reward_list[selected_action_index] = update_mean(
        action_mean_reward_list[selected_action_index], 
        reward)
13:   selected_action_count_list[selected_action_index] += 1
14:   round += 1
15:   state = next_state

กราฟ Confident Interval ของ Action-Values ของตัวเลือก A, B, C, D (https://www.geeksforgeeks.org/upper-confidence-bound-algorithm-in-reinforcement-learning/)

• จากรูปด้านบน Q(A) มีความเชื่อมั่นขอบเขตบนมากที่สุด บอทจะเลือกกระทำตัวเลือก A
• สังเกตได้ว่าค่าความเชื่อมั่นของแต่ละตัวเลือกแตกต่างกัน ตัวเลือกที่ถูกเลือกบ่อยค่าความเชื่อมั่นจะแคบ ส่วนตัวเลือกที่ไม่ค่อยถูกเลือกค่าความเชื่อมั่นจะกว้าง
• เมื่อเวลาผ่านไปหลาย ๆ รอบ และแต่ละตัวเลือกถูกเลือกมากขึ้น ค่าความเชื่อมั่นของแต่ละตัวเลือกจะลู่เข้าใกล้เคียงค่าจริงของตัวเลือกนั้นมากขึ้นเรื่อย ๆ

อัลกอริทึมการสุ่มตัวอย่างแบบทอมสัน (Thompson Sampling Algorithm: TS)

1. กำหนด Prior Distribution ให้กับทุกตัวเลือก เช่น กำหนดเป็น Beta Distribution
2. สุ่มค่าให้กับแต่ละตัวเลือกจาก Prior Distribution ของตัวเลือกนั้น
3. เลือกกระทำตามตัวเลือกที่ค่าสุ่มมีค่ามากที่สุด

1:  # Thompson Sampling by ArtSyntax #

2:  state = {dict of state parameters}
3:  action_list = [list of actions]
4:  action_win_count_list = np.zeros(len(action_list))
5:  action_not_win_count_list = np.zeros(len(action_list))
6:  while(not is_end):
7:    action_prob_list = np.random.beta(
        action_win_count_list + 1, 
        action_not_win_count_list + 1)
8:    selected_action_index = np.argmax(action_prob_list)
9:    selected_action = action_list[selected_action_index]
10:   next_state, reward = make_action(state, selected_action)
11:   if reward > 0: 
12:     action_win_count_list[selected_action_index] += 1
13:   else: 
14:     action_not_win_count_list[selected_action_index] += 1
15:   state = next_state

ตัวอย่าง Beta Distribution

• จากรูปด้านบน ตัวเลือก X มีค่า action_win=2, action_not_win=2 ถ้ามีการเลือกกระทำตัวเลือก X และได้รับรางวัล ค่า action_win + 1
• ในรอบถัดไป จะสุ่มค่าของตัวเลือก X จาก beta(3, 2) สังเกตได้จากกราฟว่าการสุ่มในรอบนี้มีโอกาสได้ค่าที่มากขึ้น หากรอบนี้กระทำตัวเลือก X และได้รับรางวัลอีก ค่า action_win + 1
• ในรอบถัดไป จะสุ่มค่าของตัวเลือก X จาก beta(4, 2) สังเกตได้จากกราฟว่าการสุ่มในรอบนี้มีโอกาสได้ค่าสุ่มที่มากขึ้นไปอีก ดังนั้นตัวเลือกที่กระทำแล้วได้รับรางวัลบ่อย ๆ จะมีโอกาสที่สุ่มแล้วได้ค่ามากขึ้นเรื่อย ๆ ทำให้มีโอกาสที่บอทจะเลือกตัวเลือกนั้นมากกว่าตัวเลือกอื่น แต่หากรอบนี้กระทำตัวเลือก X และไม่ได้รับรางวัล ค่า action_not_win + 1
• ในรอบถัดไป จะสุ่มค่าของตัวเลือก X จาก beta(4, 3) สังเกตได้จากกราฟว่าการสุ่มในรอบนี้มีโอกาสได้ค่าสุ่มที่น้อยลงจากรอบที่แล้ว เพราะตัวเลือกนี้ในรอบที่แล้วไม่ชนะ เมื่อค่าสุ่มของตัวเลือกนี้น้อยลง ก็มีโอกาสที่ค่าสุ่มของตัวเลือกอื่นจะมากกว่าค่าสุ่มของตัวเลือกนี้ บอทก็อาจเปลี่ยนไปเลือกกระทำตัวเลือกอื่น
• เมื่อเวลาผ่านไปหลาย ๆ รอบ การแจกแจงของแต่ละตัวเลือกจะลู่เข้าใกล้เคียงการแจกแจงจริงของตัวเลือกนั้นมากขึ้นเรื่อย ๆ

ข้อสังเกต

สัดส่วนระหว่าง Exploit:Explore ของ Thompson Sampling จะสูงกว่าของ Upper Confidence Bound

• การเลือกตัวเลือกของ Thompson Sampling มาจากการสุ่มค่า ตัวเลือกที่มีสัดส่วนการชนะมากกว่าตัวเลือกอื่น จะมีโอกาสที่ค่าสุ่มสูงกว่าตัวเลือกอื่น ทำให้เกิดการเลือกตัวเลือกนั้นซ้ำ ๆ และพลาดโอกาสในการสำรวจตัวเลือกอื่นที่รางวัล ณ ตอนนั้นอาจสูงกว่าได้ ต้องรอให้ตัวเลือกนั้นไม่ชนะบ่อยขึ้น ค่าสุ่มของตัวเลือกนั้นจึงมีโอกาสน้่อยลง และค่าสุ่มของตัวเลือกอื่นชนะ
• การเลือกตัวเลือกของ Upper Confidence Bound จะมีการถ่วงน้ำหนักการสำรวจ ตัวเลือกที่ไม่ค่อยถูกเลือก จะมีค่าถ่วงน้ำหนักการสำรวจเพิ่มขึ้นเรื่อย ๆ ทำให้มีโอกาสในการเปลี่ยนไปลองตัวเลือกอื่น มากกว่า Thompson Sampling
• สำหรับสภาพแวดล้อมที่ผลรางวัลของแต่ละตัวเลือกแน่นอนการใช้ Thompson Sampling จะดีกว่า เพราะจะเน้นเลือกตัวเลือกที่ให้รางวัลมาก โดยไม่ต้องเสียเวลาไปสำรวจตัวเลือกอื่นที่ให้รางวัลน้อยกว่า
• สำหรับสภาพแวดล้อมที่ผลรางวัลของแต่ละตัวเลือกมีการเปลี่ยนแปลง คือแต่ละตัวเลือกสลับกันให้ผลตอบแทนที่ดีกว่าในแต่ละช่วงเวลา การใช้ Upper Confidence Bound จะดีกว่า เพราะจะมีการสำรวจตัวเลือกอื่นที่ไม่ค่อยถูกเลือกเป็นระยะ ทำให้รู้ว่าตัวเลือกใดให้ผลตอบแทนที่ดีกว่าอยู่เรื่อย ๆ และสลับไปเลือกตัวเลือกนั้นให้บ่อยขึ้นได้อย่างรวดเร็ว

กระบวนการตัดสินใจแบบมาร์คอฟ Markov Decision Process (MDP)

สำหรับตัวอย่างการแสดงโฆษณาข้างต้นของบทความเป็นเพียงปัญหา Multi-Armed Bandit เพราะเป็นแค่การตัดสินใจว่าจะเลือกตัวเลือกใด

ปัญหาการแสดงโฆษณานี้สามารถพัฒนาต่อด้วยหลักการของ Markov Decision Process เช่น การแสดงโฆษณาแบบต่อเนื่องหลายครั้งกับลูกค้าคนเดิม การแสดงโฆษณาเพื่อให้ข้อมูลสินค้า 2 ครั้ง และต่อด้วยการแสดงโฆษณาโปรโมชัน 1 ครั้ง อาจทำให้ผู้ใช้คลิกมากกว่าการแสดงโฆษณาโปรโมชันอย่างเดียว 3 ครั้ง

สำหรับเนื้อหาการประยุกต์ Reinforcement learning กับ Markov Decision Process จะอธิบายในบทความต่อไป

Reinforcement Learning กับการใช้ชีวิต

เราสามารถประยุกต์ใช้หลักการในการตัดสินใจเลือกระหว่าง Exploit และ Explore กับชีวิตของเราได้ คือการต่อยอดสิ่งในที่เรามีหรือการเรียนรู้สิ่งใหม่ เรียนรู้จากผลของการตัดสินใจ เรียนรู้จากการกระทำที่เราเลือก เพื่อให้ชีวิตเราได้รับผลรางวัลที่มากขึ้น การเลือกทางเดิมอย่างเดียวอาจทำให้เราพลาดทางเลือกใหม่ที่ให้คุณค่ากับเรามากกว่า

https://nesslabs.com/exploration-exploitation-ambidextrous-mindset-success-trap

อ่านเพิ่มเติมเกี่ยวกับ Big Data และ Data Scientist

Big Data คืออะไร Data Science คืออะไร มีข้อมูลอยู่จะเริ่มอย่างไร ในทีมต้องมีใคร

Data Scientist คืออะไร และสกิลของ Data Scientist

อ้างอิง

Reinforcement Learning: An Introduction

A Review of B. F. Skinner's 'Reinforcement Theory of Motivation'

An Empirical Evaluation of Thompson Sampling

Finite-time Analysis of the Multiarmed Bandit Problem - Machine Learning

Using confidence bounds for exploitation-exploration trade-offs | The Journal of Machine Learning…

How to Do Thompson Sampling Using Python -- Visual Studio Magazine

Reinforcement Learning : The Concept Behind UCB Explained With Code

Not All Who Wander Are Lost