# การสุ่มแบบทอมป์สัน
การสุ่มแบบทอมป์สัน ซึ่งตั้งชื่อตาม วิลเลียม อาร์. ทอมป์สัน เป็นวิธีการแบบ heuristic สำหรับการเลือกการกระทำที่แก้ปัญหาความสมดุลระหว่าง การสำรวจและการแสวงหาผลประโยชน์ (exploration-exploitation dilemma) ในปัญหา multi-armed bandit โดยวิธีนี้จะเลือกการกระทำที่เพิ่มรางวัลคาดหวังสูงสุดตามความเชื่อที่ถูกสุ่มขึ้นมา

 คำอธิบาย 

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

องค์ประกอบของการสุ่มแบบทอมป์สัน ได้แก่:

1. ฟังก์ชันความน่าจะเป็น ;

2. ชุดของพารามิเตอร์  ที่กำหนดการกระจายตัวของ ;

3. การกระจายตัวก่อนหน้า (prior distribution)  สำหรับพารามิเตอร์เหล่านี้;

4. ชุดข้อมูลการสังเกตในอดีต ;

5. การกระจายตัวหลัง (posterior distribution)  โดยที่  คือฟังก์ชันความน่าจะเป็น

การสุ่มแบบทอมป์สันประกอบด้วยการเลือกการกระทำ  ตามความน่าจะเป็นที่การกระทำนั้นจะเพิ่มรางวัลคาดหวังสูงสุด โดยเลือกการกระทำ  ด้วยความน่าจะเป็น

โดยที่  คือ ฟังก์ชันบ่งชี้ (indicator function)

ในทางปฏิบัติ กฎนี้ถูกใช้งานโดยวิธีการสุ่ม (sampling) ในแต่ละรอบ จะมีการสุ่มค่าพารามิเตอร์  จากการกระจายตัวหลัง  และเลือกการกระทำ  ที่เพิ่มรางวัลคาดหวังสูงสุด  ซึ่งหมายความว่า ผู้เล่นจะสุ่มความเชื่อของตนในแต่ละรอบตามการกระจายตัวหลัง จากนั้นจึงกระทำตามที่เหมาะสมที่สุดกับความเชื่อนั้น

ในแอปพลิเคชันที่ใช้งานจริง การคำนวณและการสุ่มจากการกระจายตัวหลังอาจใช้ทรัพยากรสูง ดังนั้น การสุ่มแบบทอมป์สันมักใช้งานร่วมกับเทคนิคการสุ่มแบบประมาณค่า (approximate sampling techniques) 

 ประวัติ 

การสุ่มแบบทอมป์สันถูกอธิบายครั้งแรกโดย Thompson ในปี 1933 และถูกค้นพบอีกหลายครั้งอย่างอิสระในบริบทของปัญหาหลายแขนโจร (multi-armed bandit problems) โดยมีการพิสูจน์การลู่เข้าครั้งแรกสำหรับกรณีปัญหา bandit ในปี 1997 และการประยุกต์ใช้ครั้งแรกกับ กระบวนการตัดสินใจของมาร์คอฟ (Markov decision process) ในปี 2000

แนวทางที่เกี่ยวข้อง (ดู Bayesian control rule) ได้รับการเผยแพร่ในปี 2010 ในปีเดียวกัน ยังมีการแสดงให้เห็นว่าการสุ่มแบบทอมป์สันสามารถ แก้ไขตนเองในทันที (instantaneously self-correcting) ผลการลู่เข้าที่ไม่จำกัดสำหรับปัญหา contextual bandits ถูกตีพิมพ์ในปี 2011

การสุ่มแบบทอมป์สันถูกนำไปใช้ในปัญหาการเรียนรู้ออนไลน์ต่าง ๆ อย่างแพร่หลาย รวมถึงการทดสอบ A/B ในการออกแบบเว็บไซต์และการโฆษณาออนไลน์ และการเร่งกระบวนการเรียนรู้ในกระบวนการตัดสินใจแบบกระจายศูนย์ นอกจากนี้ ยังมีการเสนออัลกอริทึม Double Thompson Sampling (D-TS) สำหรับ dueling bandit ซึ่งเป็นตัวแปรของปัญหา MAB แบบดั้งเดิม ที่ให้ข้อเสนอแนะในรูปของการเปรียบเทียบเป็นคู่ (pairwise comparison)

 ความสัมพันธ์กับวิธีการอื่น ๆ 

การจับคู่ความน่าจะเป็น

การจับคู่ความน่าจะเป็น (Probability matching) เป็นกลยุทธ์การตัดสินใจที่การทำนายการเป็นสมาชิกของคลาสสอดคล้องกับอัตราส่วนของคลาสในข้อมูลฝึกอบรม ตัวอย่างเช่น หากในชุดข้อมูลฝึกอบรมมีตัวอย่างที่เป็นบวก 60% และตัวอย่างที่เป็นลบ 40% ผู้สังเกตการณ์ที่ใช้กลยุทธ์การจับคู่ความน่าจะเป็นจะทำนายคลาส "บวก" สำหรับตัวอย่างที่ไม่ระบุ 60% และคลาส "ลบ" สำหรับ 40% ของตัวอย่าง

กฎการควบคุมแบบเบย์ (Bayesian control rule)

การขยายการสุ่มแบบทอมป์สันให้ครอบคลุมสภาพแวดล้อมแบบไดนามิกและโครงสร้างเชิงสาเหตุ เรียกว่า กฎการควบคุมแบบเบย์ (Bayesian control rule) ซึ่งถูกแสดงให้เห็นว่าเป็นคำตอบที่เหมาะสมที่สุดสำหรับปัญหาการเข้ารหัสแบบปรับตัวที่มีการกระทำและการสังเกต ในการกำหนดนี้ เอเจนต์ถูกมองว่าเป็นการผสมผสานระหว่างพฤติกรรมต่าง ๆ เมื่อเอเจนต์มีปฏิสัมพันธ์กับสภาพแวดล้อม มันจะเรียนรู้คุณสมบัติเชิงสาเหตุและเลือกใช้พฤติกรรมที่ลดค่าความเอนโทรปีสัมพัทธ์ (relative entropy) ไปยังพฤติกรรมที่คาดการณ์พฤติกรรมของสภาพแวดล้อมได้ดีที่สุด หากพฤติกรรมเหล่านี้ถูกเลือกตามหลักการของอรรถประโยชน์ที่คาดหวังสูงสุด พฤติกรรมของกฎการควบคุมแบบเบย์ในระยะยาวจะสอดคล้องกับพฤติกรรมของเอเจนต์ที่มีเหตุผลสมบูรณ์

การตั้งค่ามีดังนี้ ให้  เป็นการกระทำของเอเจนต์จนถึงเวลา  และ  เป็นการสังเกตที่เอเจนต์ได้รับจนถึงเวลา  จากนั้นเอเจนต์จะออกการกระทำ  ด้วยความน่าจะเป็น:

โดยที่สัญลักษณ์ "hat"  หมายถึงว่า  เป็นการแทรกแซงเชิงสาเหตุ (ดู Causality) ไม่ใช่การสังเกตธรรมดา หากเอเจนต์มีความเชื่อ  เกี่ยวกับพฤติกรรมของมัน กฎการควบคุมแบบเบย์จะกลายเป็น
,
โดยที่  เป็นการแจกแจงหลังการสังเกตพารามิเตอร์  ที่พิจารณาจากการกระทำ  และการสังเกต 

ในทางปฏิบัติ กฎการควบคุมแบบเบย์คือการสุ่มพารามิเตอร์  จากการแจกแจงหลัง  ในแต่ละช่วงเวลา โดยการแจกแจงหลังคำนวณโดยใช้กฎของเบย์โดยพิจารณาเฉพาะความน่าจะเป็นเชิงสาเหตุของการสังเกต  และละเลยความน่าจะเป็นเชิงสาเหตุของการกระทำ  จากนั้นสุ่มการกระทำ  จากการแจกแจงการกระทำ 

อัลกอริทึม UCB (Upper-Confidence-Bound)

การสุ่มแบบทอมป์สันและอัลกอริทึม UCB มีคุณสมบัติพื้นฐานร่วมกันที่สนับสนุนความน่าเชื่อถือทางทฤษฎีของทั้งสองวิธี กล่าวคือ ทั้งสองวิธีจัดสรรความพยายามในการสำรวจไปยังการกระทำที่อาจเป็นการกระทำที่เหมาะสมที่สุด และในแง่นี้ถือว่า "มองโลกในแง่ดี" การใช้คุณสมบัตินี้ ทำให้สามารถแปลงขอบเขตความเสียใจ (regret bounds) ที่กำหนดไว้สำหรับอัลกอริทึม UCB ไปเป็นขอบเขตความเสียใจแบบเบย์เซียน (Bayesian regret bounds) สำหรับการสุ่มแบบทอมป์สันได้ หรือรวมการวิเคราะห์ความเสียใจสำหรับทั้งสองวิธีนี้และหลายคลาสของปัญหาได้
 อ้างอิง