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

จากบทความที่แล้ว เราได้พาไปดูการกำหนดปัญหา การไปเล่น Slot machine ที่คาสิโนของเราและได้หาวิธีการประเมินโอกาสชนะของเครื่อง Slot machine ด้วยวิธีการ Epsilon greedy มาแล้วและได้เปรียบเทียบผลลัพธ์ดู นับว่าทำงานได้ดีประมาณหนึง เอาเข้าจริงๆวิธีการนั้นก็ไม่ได้เป็นอะไรมากไปกว่าการคำนวณ mean ของแต่ละเครื่องผ่านการเล่น Slot machine แต่ละรอบๆเสริมด้วยวิธีการสุ่มเล่นเครื่อง Slot machine บ้างเป็นครั้งคราวเท่านั้นเอง

วันนี้เราจะมาดูสมการคณิตศาสตร์ที่ซับซ้อนขึ้นมาอีกนิดหนึง(นิดเดียว) UCB1 ตัวนี้ก็ใช้ในการประเมิน mean ตัวหนึงทำหน้าที่เหมือน Epsilon greedy แต่วิธีการทำนั้นต่างกัน

Image result for casino slot machines
กลับมาที่ Casino กันอีกครั้งหนึง

เนื่องจากเราจะแก้ปัญหาเดิม ก่อนอื่นผมขอนำ โอกาสในการชนะของ Slot machine มาแปะกันอีกครั้งนะครับ

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

UCB1

  • การ Sample ข้อมูลน้อยๆ เช่น 10 หรือ 20 ครั้ง แล้วประเมิณ Mean ย่อมมีความแม่นยำน้อยกว่าการประเมินจากการ Sample ข้อมูลเยอะๆ เช่น 1000 หรือ 2000 ครั้ง
  • ดังนั้นจึงมีการคิดค้นการใช้ Epsilon หรือโอกาสในการไปเล่น Slot Machine แบบสุ่มให้ลดลงตามจำนวนครั้งที่เราเคยเล่นมา เช่น ถ้าเราเล่นไป แค่ 10 ครั้งเราอาจจะต้องสุ่มมากหน่อยหนึง แต่ถ้าเราเล่นไปแล้ว 10,000 ครั้งเราก็พอจะรู้ได้แล้วว่าเครื่องไหนใน Slot machine ทั้ง 3 เครื่องนั้นน่าจะให้ผลลัพธ์ไปในทิศทางไหน ความจำเป็นในการสุ่มมากๆมันก็ไม่มีแล้ว เราจึงสุ่มให้น้อยลง
  • มันก็มีอีกหลายวิธี วิธีหนึง Epsilon Decay คือการเขียนสมการให้ค่า Epsilon มันเล็กลงไปตามจำนวนครั้งทีสุ่ม(เช่น Exponential Decay) ซึ่งเราสามารถกำหนดเองว่าให้จำนวนการสุ่ม Epsilon มันลดลงเร็วแค่ไหน แต่ขอไม่ยกมาพูดในที่นี้แล้วกันครับ
  • อีกวิธีก็คือการใช้ UCB1 คือการสร้าง confidence bound ตามจำนวนครั้งที่สุ่มนั่นแหละครับ

UCB1 ก็จะเปลี่ยนจากการสุ่มแบบ Epsilon เปอร์เซ็น เป็นการสร้างขอบเขตแห่งความมั่นใจ(confidence bound)ถ้าสุ่มมากความมั่นใจก็มาก ขอบเขตการสุ่มก็จะเล็ก เช่น

ถ้าเราเล่นไป 20 ครั้ง และจากข้อมูลที่เราเก็บมาได้ เครื่องที่ 1 ได้ win rate 60%, เครื่องที่ 2 ได้ 10%, เครื่องที่ 3 10% ตามลำดับมันคงไม่ฉลาดนักถ้าเราจะ Exploit หรือเล่นแต่เครื่องที่ 1 ไปตลอดเพื่อให้เราทำเงินได้มากที่สุดเพราะเราเพิ่งเล่นไปแค่เครื่องละไม่กี่ครั้งเท่านั้นเอง การประเมินของเราอาจจะผิดพลาดได้อันนี้เราเคยแก้ไปแล้วด้วย Epsilon greedy ข้อเสียคือเรายังต้องเสียเวลาสุ่มไปตลอด(ถ้าไม่ใช้ Epsilon Decay แต่ Epsilon Decay ก็ยังต้องมากำหนดความเร็วในการลดค่า Epsilon อยู่ดี)ถ้าเล่นไปมากๆแล้วเราก็ไม่จำเป็นต้องสุ่มแล้วเราก็ไม่ควรสุ่ม หรือแม้กระทั้ง ต่อให้เราสุ่มไปจำนวนมากครังหน่อย แต่ยังมีเครื่องบางเครื่อง สมมุติเครื่องที่ 3 แทบไม่ได้รับการเล่นเลย UCB1 ก็จะสามารถให้ confidence bound มันน้อยได้ โดยมีสมการดังนี้

สมการ UCB1
  • X่ucbj คือ การประเมิน Slot machine ตัวที่ j
  • Xbar คือ mean
  • N คือ จำนวนการเล่น Slot machine ทั้งหมด
  • Nj คือ จำนวนการเล่น Slot machine เครื่องที่ j

จากสมการนี้จะเป็นการบอกเราว่า ถ้าเราเล่นเครื่องใดเครื่องหนึงมากหรือน้อยไปยังไง เราก็ควรจะเซต confidence bound ให้เหมาะกับจำนวนการเล่นเครื่องนั้นๆ เช้น ถ้า N ใหญ่คือเราทำการเล่นไปหลายครั้งแล้ว แต่ Nj ถูกเล่นไปไม่กี่ครั้ง Ratio มันก็จะใหญ่ ซึ่งก็หมายความว่าเราไม่มั่นใจว่าเครื่องที่ j มันให้ผลลัพธ์เท่านี้จริงๆรึเปล่า(เพราะเล่นไปน้อย) ขณะเดียวกันยิ่ง Nj มากขึ้น Ratio ตรงส่วนนั้นก็จะหดลงๆ

โค้ดในส่วนของ UCB1 ที่เพิ่มเข้ามา

โค้ดตามสมการด้านบนแบบตรงไปตรงมา

ที่น่าสนใจอีกจุดคือ ส่วนบนที่ N นั้นมี ln มาวางหน้าเป็น ln(N) หมายความอัตราการโตของ N มันจะโตช้ากว่า Nj ที่ไม่มี ln มาวางหน้า หมายความว่ายิ่งเราเล่น Slot machine มากขึ้นๆ confidence bound ก็จะเล็กจนสุดท้ายเราก็จะไม่ต้องเสียเวลาสุ่มเหมือน Epsilon greedy อีกต่อไป เพราะเราสามารถเลือกอันที่ทำผลงานดีที่สุดได้เลย

ตัวอย่างความสัมพันธ์ระหว่าง log และ linear number
อัตราการลดลงของ boundary assume ว่าเล่นแต่ละเครื่องเท่ากัน

สัดส่วนการลดลงของ Confidence bound เมื่อทำการเล่นไป 10,000 รอบ จะเห็นว่ามันมีการลดลงเรื่อยๆ ยิ่งเล่นมากยิ่งมีความมั่นใจในการประเมิณ mean ของ Slot machine แต่ล่ะเครื่องมากขึ้น Confidence bound ก็ลดลงๆ

ในส่วนของการ run ผลการทดลองเราต้องเปลี่ยนนิดหน่อย เพราะเราไม่ต้องใช้ Epsilon greedy แล้วดังนั้น if else เราไม่ต้องใช้อีกต่อไป และใช้ฟังก์ชั่น UCB1 ที่เขียนไว้มาช่วยประเมิณ mean แทน

โค้ดในส่วนของ run algorithm ucb1

ก่อนอื่นเอาผลงานของ Epsilon greedy ที่ epsilon = 0.3, 0.1, 0.05 ตามลำดับ มาลงอีกครั้งเพื่อเปรียบเทียบกับ UCB1

รูปเปรียบเทียบ UCB1 และ Epsilon 0.3, 0.1, 0.05 ตามลำดับ พล๊อตแบบ Log Scale

จะเห็นว่า UCB1 ตอนแรกๆจะมีความมั่นใจต่ำทำใจค่าที่ + เพิ่มมาจะสูง ทำให้ Algorithm เราพยายามเปลี่ยนเครื่องเล่นไปเรื่อยๆ เมื่อเวลาผ่านไป ความมั่นใจในการประเมินเครื่องเล่นแต่ละเครื่องสูงแล้ว ค่าที่ + เพิ่มมาก็น้อยลง ทำให้ UCB1 ตอนหลัง UCB1 จะไม่เสียเวลาไปเปลี่ยนเครื่องเล่นแบบสุ่มอีกต่อไป ทำให้สามารถทำเงินได้มากสุดจากเครื่อง Slot machine ที่ให้โอกาสชนะมากที่สุดได้เลย ต่างกับ Epsilon จะเห็นว่า 0.3 ไม่ว่าเวลาจะผ่านไปแค้ไหน เค้าก็จะยังใช้เวลา 30% 10% และ 5% ในการสุ่มไปเล่นเครื่องอื่นโดยที่ไม่จำเป็นอีกเลย ลองดูแบบ Linear Scale กันบ้างครับ

รูปเปรียบเทียบ UCB1 และ Epsilon 0.3, 0.1, 0.05 ตามลำดับ พล๊อตแบบ Linear Scale

ภาพในระยะยาวยิ่งชัดขึ้นเมื่อเราดูแบบ Linear scale จะเห็นว่า UCB1 เป็นการแก้ปัญหาในระยะยาวที่เหมาะสมกว่า Epsilon greedy

ยังจำได้ไหม Finance

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

งานวิจัยที่ผมยกมาปิดท้ายบทความครั้งก่อน ตอนนี้เราก็รู้จักอีก Algorithm ในเปเปอร์นั้นเพิ่มมาอีกตัวแล้วนะครับ UCB1 ผลงานใช้ได้เลยทีเดียว ตอนนี้เรารู้จัก ไป 2 ใน 5 แบบในกราฟแล้ว จริงๆก็น่าจะ 3 ใน 5 มากกว่าเพราะ Equally Weighted Portfolio ก็คือการถือหุ้นในพอร์ตปริมาณเท่ากันหมดแค่นั้นเอง ต่อไปในอนาคตผมจะทยอยๆเขียนมาลงให้นะครับ

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s