[Reinforcement Learning 101] ตะลุยคาสิโนด้วย RL: Muti-Armed Bandit (1)- Epsilon Greedy

วันนี้เรามาพูดถึงโมเดลเบื้องต้นของ Reinforcement Learning กันบ้างครับ โดยเราจะเริ่มตั้งแต่แบบเบื้องต้นกันครับ

เครื่อง Slot Machine

จุดประสงค์ของการไป Casino

สมมุติว่าเราไป Casino​ เป้าหมายของเราคืออะไร ก็คงไม่หาเงินจากการเล่นพันให้มากที่สุด แล้วเราเดินไปเล่นเครื่องเล่น Slot Machine ที่ในห้องนั้นมีอยู่ 3 เครื่อง โอกาสชนะ(win rate)ในแต่ละเครื่องไม่เท่ากัน​แต่เราน่ะไม่รู้หรอกว่าเครื่องไหนมี win rate เท่าไหร่บ้าง

สมมุติอีกว่าเครื่อง Slot Machine ของ Casino นี้เมื่อเราเข้าไปเล่นแต่ละครั้ง ถ้าชนะเราจะได้เงิน 1 เหรียญ ถ้าแพ้ก็จะได้ 0 เหรียญ  แต่ละเครื่องมี win rate ไม่เท่ากันดังนี้

• ​เครื่องที่ 1 มี win rate 10% ต่อการเล่นแต่ละครั้ง
• เครื่องที่ 2 มี win rate 20% ต่อการเล่นแต่ละครั้ง
• เครื่องที่ 3 มี win rate 50% ต่อการเล่นแต่ละครั้ง

​แต่ข้อมูลพวกนี้เราไม่มีทางรู้ได้เลยว่าจริงๆแล้วแต่ละเครื่องมี win rateเท่าไหร่ เพราะตอนเราเดินเข้าไปเล่นเราก็รู้แค่ว่า การเล่นรอบนั้นผลคือได้หรือไม่ได้เท่านั้นเอง สรุปว่า เราสามารถได้ข้อมูลมาจากการทดลองเท่านั้น และวิธีการแก้ปัญหานี้มีอะไรบ้างล่ะ

วิธีหนึงที่เราจะรู้ว่าเครื่องไหนมี win rate มากกว่ากัน ก็คือเล่นมันซะเครื่องละหลายๆรอบใช่ไหมครับ ตัวอย่างเช่น

• ​ถ้าเราเล่นเครื่อง A ที่มี win rate 10% ซัก 10,000 รอบ จำนวนครั้งที่เราขะชนะก็น่าจะ ไม่ห่างจาก 1,000 + – ไม่มากนัก
• ขณะเดียวกัน ถ้าเราไปเล่นเครื่อง C ที่มี win rate 50% 10,000 รอบเท่ากันการชนะของเราก็น่าจะประมาณ 5,000 + – ไม่มากนักเช่นกัน

วิธีการนี้มันก็ได้ผลนั่นแหละครับ แต่มันจะนำมาซึ่งปัญหา​ที่มีชื่อว่า “Explore/Exploit Dilemma​”

Explore/Exploit Dilemma​

Explore/Exploit Dilemma​ นั้นเป็นปัญหาใหญ่ปัญหาหนึงของ Reinforcement Learning คือ Trade-off ระหว่างเล่น Slot Machine เครื่องที่เราคิดว่าให้กำไรมากสุดเดี๋ยวนี้! และการรอให้สามารถยืนยันได้ก่อนว่า Slot Machine เครื่องนั้นๆนั้นให้กำไรกับเรามากที่สุดจริงจึงค่อยเข้าไปเล่น Slot Machine เครื่องนั้น

ตาม Law of Large Number ยิ่งเรา Sample ตัวอย่างมามากแค่ไหน เราก็ยิ่งประเมินค่าเฉลี่ยได้แม่นยำ ขณะเดียวกัน ถ้าเรา Sample ข้อมูลน้อย มันก็มีโอกาสที่จะได้ข้อสรุปผิดๆกับเราได้ตัวอย่างเช่น

• เครื่อง C win rate 50% แต่เราเล่นมัน(Sample) แค่ 5 ครั้ง มันก็มีความเป็นไปได้ที่เราจะได้ผลลัพธ์แบบ ชนะ 1/5 หรือ win-rate ที่ 20%
• เครื่อง B win rate 30% ก็อาจจะได้ผลเป็น ชนะ 3/5 หรือ win-rate 60%
• เครื่อง A win rate 10% ก็อาจจะได้ผลเป็น 4/5 หรือ win-rate 80% ซึ่งต่างกับความจริงมาก

ด้วยการ Sample ข้อมูลที่น้อยขนาดนี้อาจจะทำให้เราคิดว่า เครื่อง A ให้กำไรเรามากที่สุดแล้วเราจึงลงเงินทั้งหมดไปกับการเล่นเครื่อง A เพราะคิดว่าจะทำกำไรได้เป็นกอบเป็นกำที่ win rate 80% แต่ผลสุดท้ายแล้วเครื่อง A มันมี win rate น้อยมากเราก็ขาดทุนไปโดยปริยาย การเอากำไรโดยการเล่นเครื่องที่เราคิดว่าที่ดีสุดนี่แหละครับคือการรีบ Exploit หรือ Exploitation มากเกินไป

การที่เราคิดว่าการประเมินตอนนี้แค่ 5 ครั้งของเราไม่ถูกต้อง เราต้องประเมินโดยการเล่นเพิ่ม เช่นไปเล่นอีกเครื่องละ 100,000 ครั้ง จนได้การประเมินที่เราพอใจอันนี้แหละครับที่เรียกว่า Explore หรือ Exploration

แล้วมันเป็น Dilemma ยังไง?

ถ้าเจ้าปลาหมึกกดเครื่องเดียวที่คิดว่าให้เงินมากสุดก็จะเป็น Pure exploitation ถ้าเจ้าปลาหมึกทดลองโดยกดหลายๆอันก็จะเป็น Pure exploration CR.:http://www.primarydigit.com/blog/multi-arm-bandits-explorationexploitation-trade-off

ในชีวิตจริงเงินทุนเราคงมีจำกัดใช่ไหมครับ ยิ่งเราไปเก็บ Sample โดยการไปเล่นหลายๆเครื่องหลายๆครั้ง เราก็จะเสียโอกาสในการทำเงินครับ และที่ร้ายแรงกว่าก็อาจจะเสียทุนไปจนหมดก็ได้ ลองติ๊ต่างว่า มีเครื่อง Slot Machine ซัก 20 เครื่องสิครับ แล้วเราต้องไปเล่นเครื่องล่ะ 10,000 – 100,000 รอบ เราคงหมดตัวแน่ๆ

ฉะนั้นยิ่งเรา Exploit มากเราก็ยิ่งจะเสียโอกาสในการตามหาค่าที่แท้จริงของ Slot Machine ยิ่ง Explore มากก็จะเสียโอกาสที่จะทำเงินจาก Slot Machine ที่ทำเงินได้ดีอยู่แล้ว เพราะฉะนั้นสิ่งที่ต้องทำคืออย่า หยุด Explore เร็วเกินไปและอย่ารีบ Exploit เกินไป

Sample Mean

ก่อนอื่นเราจะประเมิน win-rate ได้เราต้องคำนวณ Mean ใช่ไหมครับ งั้นเรามาดูวิธีการคำนวณ Mean กันแบบมีประสิทธิภาพกันครับ โดยปรกติ Mean เราจะคำนวณแบบนี้

สมการคำนวณ Mean

จะเห็นว่าจากสมการนี้ เราต้อง Sumation ข้อมูลทั้งหมดจากนั้นจึงมาคูณด้วย 1/N ทุกครั้งซึ่งมันก็คงไม่เป็นไรหรอกตอนเราทำงานปรกติ แต่เมื่อเราทำงานในปัญหานี้ คือเรารับข้อมูลมาจากการเล่นแต่ละครั้ง ถ้าเราเล่น 10 ครั้งแรก เราก็ต้องคำนวณ mean ของแต่ละเครื่องทีหนึง พอไปครั้งที่ 11 เราก็ต้องมาคำนวณอีก และ 12, 13, 14… N ไปเรื่อยๆจนกว่าจะจบการทำงาน ซึ่งมันคงเป็นอะไรที่ไม่ฉลาดนักเพราะเรามี information ทั้งหมดอยู่แล้วที่เราไม่มีก็แค่ตาล่าสุดที่เพิ่งเล่นไปนั่นเอง เช่นถ้าเราอยู่ที่ตาที่ 1,000 เราย่อมมี mean ของ slot machine ในแต่ละเครื่องอยู่หมดแล้ว แต่ที่ไม่มีคือ 1 ตาของ Slot Machine เครื่องใดเครื่องหนึงใน 3 เครื่องที่เราเล่นเท่านั้นเอง เราไม่มีความจำเป็นใดๆที่ต้องมาคำนวณใหม่ทั้งหมด ฉะนั้นเราจึงควรใช้วิธีการคำนวณ Mean แบบ Sample Mean

สมการคำนวฯ Mean แบบ Sample Mean

จะเห็นว่าถ้าเราคำนวณแบบนี้ เราไม่ต้องคำนวณข้อมูลที่มีอยู่ก่อนแล้วใหม่เลย ถ้าพูดอย่างง่ายๆก็คือ เราใช้ (1-1/N)*Old Mean + 1/N *New Value เท่านั้นเอง จะเห็นว่าในแต่ระรอบเราจะคำนวณ coefficient * ข้อมูล Mean เก่า + coefficient * ข้อมูลใหม่ เท่านั้น คราวนี้เราจะไม่เสียทรัพยากรในการ Computation ไปเปล่าๆแล้ว

โอเคครับ กลับมาที่ปัญหาหลักของเรากันครับ คือ Explore/Exploit Dilemma เรามี Algorithm ง่ายๆมาแก้ปัญหานี้ครับชื่อว่า

โค้ด Multi-Armed Bandit

บรรทัดที่ 12-13 เป็นส่วนของการ random จาก m หรือ mean ที่แท้จริงจาก slot machine แต่ละเครื่อง

บรรทัดที่ 15-17 เป็นการทำส่วนของ Sample Mean ที่พูดถึงด้านบนครับ

Epsilon-Greedy Algorithm

Epsilon-Greedy คือ วิธีการแก้ปัญหาหนึงของ Explore/Exploit Dilemma​ วิธีการก็คือเราจะ มีตัวแปรตัวหนึงชื่อ Epsilon ขึ้นมาเป็น Probability ที่เราจะทำการ Exploration โดยทั่วไปก็จะกำหนดไว้ที่ประมาณ 5 – 10% แต่เท่าไหร่จึงจะเหมาะสมเราก็ต้องลองทดลองกันเอาเองโดยมี Algorithm ดังนี้

Epsilon Greddy Algorithm

ข้อดีของ Algorithm ก็คือมันเข้าใจ และทำงานได้ดีทีเดียว ข้อเสีย ก็คือสมมุติว่าเราใช้ Epsilon 10% จากนั้นเล่นไปจนเจอแล้วว่าตัวไหนที่มี win rate มากที่สุด เราก็ยังต้องเสีย 10% ของการเล่นทั้งหมดมาสุ่มเล่น Slot Machine เครื่องอื่นอยู่ดี ซึ่งตรงนี้สามารถแก้ได้โดยใช้ Confident Interval มาหาความมั่นใจแล้วจากนั้นเราสามารถเซต Epsilon ให้เป็น 0 ได้ แต่บทความหน้าผมจะนำวิธีที่ดีกว่านั้นมาบอกกล่าวกันครับ

ข้อดีของ Algorithm ก็คือมันเข้าใจ และทำงานได้ดีทีเดียว ข้อเสีย ก็คือสมมุติว่าเราใช้ Epsilon 10% จากนั้นเล่นไปจนเจอแล้วว่าตัวไหนที่มี win rate มากที่สุด เราก็ยังต้องเสีย 10% ของการเล่นทั้งหมดมาสุ่มเล่น Slot Machine เครื่องอื่นอยู่ดี ซึ่งตรงนี้สามารถแก้ได้โดยใช้ Confident Interval มาหาความมั่นใจแล้วจากนั้นเราสามารถเซต Epsilon ให้เป็น 0 ได้ แต่บทความหน้าผมจะนำวิธีที่ดีกว่านั้นมาบอกกล่าวกันครับ

โค้ดในส่วนของการ Run และการใช้ Epsilon Greedy

บรรทัดที่ 24- 31 เป็นส่วนของ Algorithm Epsilon Greedy ครับ โดยถ้าเลขที่เรา Random มาจาก np.random.random() จะให้ค่าระหว่าง 0-1 จากนั้นเราจะเก็บค่าไว้ใน p จากนั้นนำไปเปรียบเทียบกับค่า epsilon ที่เรากำหนด ถ้าน้อยกว่า เราก็ทำการเลือกเครื่อง Slot Machine แบบสุ่มครับ นอกเหนือจากนั้นให้เราเลือกตัวที่ได้ Mean มากสุด ณ ขณะนั้นไปครับ

เปรียบเทียบค่า Epsilon

ผมจะทำการทดลอง เปรียบเทียบค่า Epsilon และ กฎ Law of Large Number กันดีกว่าครับ โดยผมจะทดลองค่า Epsilon ตั้งแต่ 0.3 (30% Explore), 0.1 (10% Explore), 0.05 (5% Explore), 0.01 (1% Explore) จากนั้นผมจะรันเพื่อทดสอบผลของมันต่อ Law of Large Number กันครับ ซึ่งจะมีตั้งแต่การเล่น Slot Machine ด้วย Algorithm นี้ 50 และ 100,000 รอบ ตามลำดับครับ

เริ่มจากการเล่นแค่ 50 รอบดูก่อน

เล่น 50 รอบพล๊อตแบบ Log Scale

จากการทดลอง การเล่นแบบสั้นๆแค่ 50 รอบ จะเห็นว่า Epsilon 0.3 หรือ เราจะทำการ Explore 30% ของทั้งหมด จะทำผลงานได้ดีที่สุดเพราะ ในการที่เราเล่นจำนวนไม่มากรอบนัก ถ้าค่า Epsilon น้อยมากๆอย่าง 0.5 (5%) และ 0.01(1%) นั้นอาจจะไม่ได้เกิดการ Explore ในรอบนั้นๆเลย ดั่งเช่น เส้นสีฟ้าที่ Epsilon 0.01 อาจจะไม่ได้ทำการ Explore gเลยแม้ซักครั้ง มันจึงทำผลงานให้เราได้แย่ที่สุด(เว้นแต่รอบแรกๆมันจะ”ฟลุ๊ก”จะเล่นเครื่องที่ให้โอกาสชนะสูงบ่อยๆครับ ) ขณะที่ Epsilon 0.3 และ 0.1 นั้นจะมีการ Explore ที่พอสมควรจึงสามารถทำผลงานได้ดีตามลำดับครับ

แล้วเราสามารถสรุปว่า Epsilon เยอะดีกว่าได้หรือไม่ คำตอบคือ ยังสรุปไม่ได้ครับ เราต้องลองกับข้อมูลที่มากกว่านี้ก่อนโดยเราจะเล่นจำนวนรอบเยอะขึ้นครับ

ลองเล่น 100,000 รอบ

เล่น 100,000 รอบพล๊อตแบบ Log Scale

จะเห็นว่าต่างกับผลของ 50 มาก เพราะว่าเมื่อเราเล่น 100,000 รอบ กฎของ Law of Large Number ก็เข้ามามีผลกระทบ จะเห็นว่าในช่วงแรกๆ Epsilon 0.3 ทำผลงานนำอย่างรวดเร็ว จากนั้นตามด้วย 0.1 0.05 และ 0.01 ตามลำดับ ที่เป็นแบบนี้ก็เพราะ พวก epsilon น้อยๆจะมีโอกาสสุ่มไปเจอเครื่อง Slot Machine ดีๆน้อยกว่า แต่เมื่อเวลาผ่านไป ก็จะค่อยๆเรียนรู้ที่จะลงเงินในเครื่องที่ดีขึ้นตามลำดับ และเล่นเครื่องที่แย่น้อยลง ดังเห็นว่า 0.1 จะสามาแซง 0.3 ได้จากนั้นก็ 0.05 แต่ในระยะยาว 0.01 ก็จะทำให้ผลงานดีที่สุด นี่คือ Trade-off ที่เห็นได้ชัดของ Explore/Exploit Delima เราต้องเลือกระหว่างเอาเงินตอนนี้เลย กับเอาเงินทีหลังแต่ได้มากกว่า ถ้าเรามีเวลาไม่จำกัดเราคงเลือกแบบหลัง แต่ถ้าจำกัดเราก็ต้องหาจุดสมดุลเอาเอง

ปัญหาอีกอย่างเมื่อเราเจอ Slot Machine ที่ทำเงินได้มากสุดแล้ว เรายังต้องเสียเวลา Epsilon ไปสุ่มเล่นอีกทั้งๆที่ไม่จำเป็น เป็นผลให้ในช่วงท้ายผู้ที่มี Epsilon น้อยสุดจึงทำผลงานได้ดีสุดนั่นเอง

เล่น 100,000 รอบพล๊อตแบบ Linear Scale จะเห็นว่า 0.01 ชนะได้ในระยะยาว

โค้ดในส่วนของการรันเพื่อเปรียบเทียบ Epsilon

นี่คือวิธีที่ Naive ที่สุดแล้วครับ ในบทความต่อๆไป ผมจะพาพวกไปดูโมเดลที่น่าสนใจขึ้นเรื่อยๆนะครับ เช่น UCB1, Thompson Sampling etc. ก่อนที่เราจะไปต่อกันเรื่อง Markov Decision Process ซึ่งถือเป็นหัวใจหลักของ Reinforcement learning กันครับ

แล้วมันเกี่ยวกับการลงทุนไหม

ถ้าเป็น Epsilon Greddy, UCB1, Thompson Sampling อาจจะไม่เกี่ยวโดยตรงมากนักแต่ก็มีดังเช่น

งานวิจัยที่ใช้การจัด Portfolio ด้วย Algorithm Reinforcement Learning หลายๆแบบ
cr. Risk-Aware Multi-Armed Bandit Problem with Application to Portfolio Selection

รูปด้านบนเป็นเทคนิคการเลือกหุ้นเข้ามาใน Portfolio เทียบกันหลายๆ Algorithm และต่อไปมันเป็นพื้นฐานไปยัง Reinforcement Learning ที่จะกลายเป็นดาวในวงการไม่ช้านี้ครับ Deep Q Learning, Recurrent Reinforcement Learning ก็มีการนำมาใช้ในการทำ Quantitative Trading อยู่ครับ