การสุ่มแบบทอมป์สัน

การสุ่มแบบทอมป์สัน ซึ่งตั้งชื่อตาม วิลเลียม อาร์. ทอมป์สัน เป็นวิธีการแบบ heuristic สำหรับการเลือกการกระทำที่แก้ปัญหาความสมดุลระหว่าง การสำรวจและการแสวงหาผลประโยชน์ (exploration-exploitation dilemma) ในปัญหา multi-armed bandit โดยวิธีนี้จะเลือกการกระทำที่เพิ่มรางวัลคาดหวังสูงสุดตามความเชื่อที่ถูกสุ่มขึ้นมา
คำอธิบาย.
พิจารณาชุดของบริบท <math>\mathcal{X}</math> ชุดของการกระทำ <math>\mathcal{A}</math> และรางวัลใน <math>\mathbb{R}</math> เป้าหมายของผู้เล่นคือการเลือกการกระทำในบริบทต่าง ๆ เพื่อเพิ่มรางวัลสะสมให้ได้มากที่สุด โดยในแต่ละรอบ ผู้เล่นจะได้รับบริบท <math>x \in \mathcal{X}</math> เลือกการกระทำ <math>a \in \mathcal{A}</math> และได้รับรางวัล <math>r \in \mathbb{R}</math> ซึ่งมีการกระจายตัวที่ขึ้นอยู่กับบริบทและการกระทำที่เลือก
องค์ประกอบของการสุ่มแบบทอมป์สัน ได้แก่:
1. ฟังก์ชันความน่าจะเป็น <math>P(r|\theta,a,x)</math>;
2. ชุดของพารามิเตอร์ <math>\Theta</math> ที่กำหนดการกระจายตัวของ <math>r</math>;
3. การกระจายตัวก่อนหน้า (prior distribution) <math>P(\theta)</math> สำหรับพารามิเตอร์เหล่านี้;
4. ชุดข้อมูลการสังเกตในอดีต <math>\mathcal{D} = {(x; a; r)}</math>;
5. การกระจายตัวหลัง (posterior distribution) <math>P(\theta|\mathcal{D}) \propto P(\mathcal{D}|\theta)P(\theta)</math> โดยที่ <math>P(\mathcal{D}|\theta)</math> คือฟังก์ชันความน่าจะเป็น
การสุ่มแบบทอมป์สันประกอบด้วยการเลือกการกระทำ <math>a^\ast \in \mathcal{A}</math> ตามความน่าจะเป็นที่การกระทำนั้นจะเพิ่มรางวัลคาดหวังสูงสุด โดยเลือกการกระทำ <math>a^\ast</math> ด้วยความน่าจะเป็น
<math>\int \mathbb{I} \left[ \mathbb{E}(r|a^\ast,x,\theta) = \max_{a'} \mathbb{E}(r|a',x,\theta) \right] P(\theta|\mathcal{D}) d\theta,</math>
โดยที่ <math>\mathbb{I}</math> คือ ฟังก์ชันบ่งชี้ (indicator function)
ในทางปฏิบัติ กฎนี้ถูกใช้งานโดยวิธีการสุ่ม (sampling) ในแต่ละรอบ จะมีการสุ่มค่าพารามิเตอร์ <math>\theta^\ast</math> จากการกระจายตัวหลัง <math>P(\theta|\mathcal{D})</math> และเลือกการกระทำ <math>a^\ast</math> ที่เพิ่มรางวัลคาดหวังสูงสุด <math>\mathbb{E}[r|\theta^\ast,a^\ast,x]</math> ซึ่งหมายความว่า ผู้เล่นจะสุ่มความเชื่อของตนในแต่ละรอบตามการกระจายตัวหลัง จากนั้นจึงกระทำตามที่เหมาะสมที่สุดกับความเชื่อนั้น
ในแอปพลิเคชันที่ใช้งานจริง การคำนวณและการสุ่มจากการกระจายตัวหลังอาจใช้ทรัพยากรสูง ดังนั้น การสุ่มแบบทอมป์สันมักใช้งานร่วมกับเทคนิคการสุ่มแบบประมาณค่า (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) ไปยังพฤติกรรมที่คาดการณ์พฤติกรรมของสภาพแวดล้อมได้ดีที่สุด หากพฤติกรรมเหล่านี้ถูกเลือกตามหลักการของอรรถประโยชน์ที่คาดหวังสูงสุด พฤติกรรมของกฎการควบคุมแบบเบย์ในระยะยาวจะสอดคล้องกับพฤติกรรมของเอเจนต์ที่มีเหตุผลสมบูรณ์
การตั้งค่ามีดังนี้ ให้ <math>a_1, a_2, \ldots, a_T</math> เป็นการกระทำของเอเจนต์จนถึงเวลา <math>T</math> และ <math>o_1, o_2, \ldots, o_T</math> เป็นการสังเกตที่เอเจนต์ได้รับจนถึงเวลา <math>T</math> จากนั้นเอเจนต์จะออกการกระทำ <math>a_{T+1}</math> ด้วยความน่าจะเป็น:
<math>P(a_{T+1}|\hat{a}{1:T}, o{1:T}),</math>
โดยที่สัญลักษณ์ "hat" <math>\hat{a}t</math> หมายถึงว่า <math>a_t</math> เป็นการแทรกแซงเชิงสาเหตุ (ดู Causality) ไม่ใช่การสังเกตธรรมดา หากเอเจนต์มีความเชื่อ <math>\theta \in \Theta</math> เกี่ยวกับพฤติกรรมของมัน กฎการควบคุมแบบเบย์จะกลายเป็น
<math>P(a{T+1}|\hat{a}{1:T}, o{1:T}) = \int_{\Theta} P(a_{T+1}|\theta, \hat{a}{1:T}, o{1:T}) P(\theta|\hat{a}{1:T}, o{1:T}) , d\theta</math>,
โดยที่ <math>P(\theta|\hat{a}{1:T}, o{1:T})</math> เป็นการแจกแจงหลังการสังเกตพารามิเตอร์ <math>\theta</math> ที่พิจารณาจากการกระทำ <math>a_{1:T}</math> และการสังเกต <math>o_{1:T}</math>
ในทางปฏิบัติ กฎการควบคุมแบบเบย์คือการสุ่มพารามิเตอร์ <math>\theta^\ast</math> จากการแจกแจงหลัง <math>P(\theta|\hat{a}{1:T}, o{1:T})</math> ในแต่ละช่วงเวลา โดยการแจกแจงหลังคำนวณโดยใช้กฎของเบย์โดยพิจารณาเฉพาะความน่าจะเป็นเชิงสาเหตุของการสังเกต <math>o_1, o_2, \ldots, o_T</math> และละเลยความน่าจะเป็นเชิงสาเหตุของการกระทำ <math>a_1, a_2, \ldots, a_T</math> จากนั้นสุ่มการกระทำ <math>a^\ast_{T+1}</math> จากการแจกแจงการกระทำ <math>P(a_{T+1}|\theta^\ast,\hat{a}{1:T},o{1:T})</math>
อัลกอริทึม UCB (Upper-Confidence-Bound).
การสุ่มแบบทอมป์สันและอัลกอริทึม UCB มีคุณสมบัติพื้นฐานร่วมกันที่สนับสนุนความน่าเชื่อถือทางทฤษฎีของทั้งสองวิธี กล่าวคือ ทั้งสองวิธีจัดสรรความพยายามในการสำรวจไปยังการกระทำที่อาจเป็นการกระทำที่เหมาะสมที่สุด และในแง่นี้ถือว่า "มองโลกในแง่ดี" การใช้คุณสมบัตินี้ ทำให้สามารถแปลงขอบเขตความเสียใจ (regret bounds) ที่กำหนดไว้สำหรับอัลกอริทึม UCB ไปเป็นขอบเขตความเสียใจแบบเบย์เซียน (Bayesian regret bounds) สำหรับการสุ่มแบบทอมป์สันได้ หรือรวมการวิเคราะห์ความเสียใจสำหรับทั้งสองวิธีนี้และหลายคลาสของปัญหาได้