การสุ่มตัวอย่าง แบบThompson ^{[ 1 ] [ 2 ] [ 3 ]}ซึ่งตั้งชื่อตามWilliam R. Thompsonเป็นฮิวริสติกสำหรับการเลือกการกระทำที่แก้ไขปัญหาความขัดแย้งระหว่างการสำรวจและการใช้ประโยชน์ใน ปัญหา Multi-Armed Banditโดยประกอบด้วยการเลือกการกระทำที่เพิ่มผลตอบแทนที่คาดหวังสูงสุดโดยสัมพันธ์กับความเชื่อที่สุ่มเลือกมา

พิจารณาชุดบริบทชุดการกระทำและรางวัลในเกม เป้าหมายของผู้เล่นคือการกระทำภายใต้บริบทต่างๆ เพื่อเพิ่มรางวัลสะสมให้สูงสุด โดยเฉพาะอย่างยิ่ง ในแต่ละรอบ ผู้เล่นจะได้รับบริบททำการกระทำและได้รับรางวัลตามการกระจายที่ขึ้นอยู่กับบริบทและการกระทำที่ทำไป ${\displaystyle {\mathcal {X}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle \mathbb {R} }$${\displaystyle x\in {\mathcal {X}}}$${\displaystyle a\in {\mathcal {A}}}$${\displaystyle r\in \mathbb {R} }$

องค์ประกอบของการสุ่มตัวอย่างแบบ Thompson มีดังต่อไปนี้: ^{[ 3 ] : มาตรา 4}

1. ฟังก์ชันความน่าจะเป็น ;${\displaystyle P(r|\theta ,a,x)}$
2. ชุดพารามิเตอร์ของการกระจายของ;${\displaystyle \Theta }$${\displaystyle \theta }$${\displaystyle r}$
3. การแจกแจงความน่าจะเป็นล่วงหน้า สำหรับพารามิเตอร์เหล่านี้${\displaystyle P(\theta )}$
4. การสังเกตการณ์ในอดีตสามชุด;${\displaystyle {\mathcal {D}}=\{(x;a;r)\}}$
5. การแจกแจงความน่าจะเป็นภายหลัง โดยที่คือฟังก์ชันความน่าจะเป็น${\displaystyle P(\theta |{\mathcal {D}})\propto P({\mathcal {D}}|\theta )P(\theta )}$${\displaystyle P({\mathcal {D}}|\theta )}$

การสุ่มตัวอย่างของ Thompson ประกอบด้วยการเล่นตามความน่าจะเป็นที่ทำให้รางวัลที่คาดหวังสูงสุดโดยเลือกการกระทำด้วยความน่าจะเป็น^{[ 3 ] : อัลกอริทึม 4} ${\displaystyle a^{\ast }\in {\mathcal {A}}}$${\displaystyle a^{\ast }}$

${\displaystyle \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 ,}$

ฟังก์ชันตัวบ่งชี้ อยู่ที่ไหน${\displaystyle \mathbb {I} }$

ในทางปฏิบัติ กฎนี้จะถูกนำไปใช้โดยการสุ่มตัวอย่าง ในแต่ละรอบ พารามิเตอร์จะถูกสุ่มจากค่าหลัง[ ^{3 ] : 7} และ เลือกการกระทำ ที่ทำให้ค่าสูงสุด นั่นคือ รางวัลที่คาดหวัง ^โดยพิจารณาจากพารามิเตอร์ที่สุ่ม การกระทำ และบริบทปัจจุบัน ในเชิงแนวคิด หมายความว่าผู้เล่นจะสร้างความเชื่อของตนแบบสุ่มในแต่ละรอบตามการแจกแจงค่าหลัง จากนั้นจึงกระทำการอย่างเหมาะสมที่สุดตามความเชื่อเหล่านั้น ในการใช้งานจริงส่วนใหญ่ การรักษาและการสุ่มตัวอย่างจากการแจกแจงค่าหลังเหนือโมเดลนั้นต้องใช้การคำนวณมาก ดังนั้น การสุ่มตัวอย่างของ Thompson จึงมักใช้ร่วมกับเทคนิคการสุ่มตัวอย่างโดยประมาณ^{[ 3 ] : ส่วนที่ 5} ${\displaystyle \theta ^{\ast }}$${\displaystyle P(\theta |{\mathcal {D}})}$${\displaystyle a^{\ast }}$${\displaystyle \mathbb {E} [r|\theta ^{\ast },a^{\ast },x]}$

การสุ่มตัวอย่างของ Thompson ได้รับการอธิบายครั้งแรกโดย Thompson ในปี 1933 ^{[ 1 ]}ต่อมาได้มีการค้นพบใหม่หลายครั้งโดยอิสระในบริบทของปัญหา multi-armed bandit ^{[ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] การพิสูจน์การ}ลู่เข้าครั้งแรกสำหรับกรณี bandit ได้รับการแสดงให้เห็นในปี 1997 ^{[ 4 ]}การประยุกต์ใช้ครั้งแรกกับกระบวนการตัดสินใจของ Markovเกิดขึ้นในปี 2000 ^{[ 6 ]}แนวทางที่เกี่ยวข้อง (ดูกฎการควบคุมแบบ Bayesian ) ได้รับการตีพิมพ์ในปี 2010 ^{[ 5 ]}ในปี 2010 ยังแสดงให้เห็นอีกว่าการสุ่มตัวอย่างของ Thompson สามารถแก้ไขตัวเองได้ทันที^{[ 9 ]}ผลลัพธ์การบรรจบกันแบบอสิมโทติกสำหรับแบนดิตตามบริบทได้รับการตีพิมพ์ในปี 2011 ^{[ 7 ]}การสุ่มตัวอย่างแบบทอมป์สันถูกนำมาใช้กันอย่างแพร่หลายในปัญหาการเรียนรู้ออนไลน์หลายอย่าง รวมถึงการทดสอบ A/Bในการออกแบบเว็บไซต์และการโฆษณาออนไลน์^{[ 10 ]}และการเรียนรู้แบบเร่งในกระบวนการตัดสินใจแบบกระจายศูนย์^{[ 11 ]} อัลกอริทึม การสุ่มตัวอย่างแบบทอมป์สันคู่ (D-TS) ^{[ 12 ]}ได้รับการเสนอสำหรับแบนดิตแบบดวลซึ่งเป็นรูปแบบหนึ่งของ MAB แบบดั้งเดิม โดยที่ผลตอบรับมาในรูปแบบของการเปรียบเทียบแบบคู่

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

การขยายผลของการสุ่มตัวอย่างของ Thompson ไปสู่สภาพแวดล้อมแบบไดนามิกและโครงสร้างเชิงสาเหตุใดๆ ซึ่งรู้จักกันในชื่อกฎการควบคุมแบบเบย์เซียนได้รับการพิสูจน์แล้วว่าเป็นวิธีแก้ปัญหาที่ดีที่สุดสำหรับปัญหาการเข้ารหัสแบบปรับตัวด้วยการกระทำและการสังเกต^{[ 5 ]}ในการกำหนดสูตรนี้ ตัวแทนจะถูกมองว่าเป็นส่วนผสมของพฤติกรรมต่างๆ เมื่อตัวแทนมีปฏิสัมพันธ์กับสภาพแวดล้อม มันจะเรียนรู้คุณสมบัติเชิงสาเหตุและปรับใช้พฤติกรรมที่ลดเอนโทรปีสัมพัทธ์ให้น้อยที่สุดเมื่อเทียบกับพฤติกรรมที่มีการคาดการณ์พฤติกรรมของสภาพแวดล้อมได้ดีที่สุด หากพฤติกรรมเหล่านี้ได้รับการเลือกตามหลักการของอรรถประโยชน์ที่คาดหวังสูงสุด พฤติกรรมเชิงอะซิมโทติกของกฎการควบคุมแบบเบย์เซียนจะตรงกับพฤติกรรมเชิงอะซิมโทติกของตัวแทนที่มีเหตุผลอย่างสมบูรณ์แบบ

การตั้งค่าเป็นดังนี้ ให้เป็นการกระทำที่ตัวแทนดำเนินการจนถึงเวลาและให้เป็นการสังเกตที่ตัวแทนรวบรวมจนถึงเวลาจากนั้นตัวแทนจะดำเนินการด้วยความน่าจะเป็น: ^{[ 5 ]}${\displaystyle a_{1},a_{2},\ldots ,a_{T}}$${\displaystyle T}$${\displaystyle o_{1},o_{2},\ldots ,o_{T}}$${\displaystyle T}$${\displaystyle a_{T+1}}$

${\displaystyle P(a_{T+1}|{\hat {a}}_{1:T},o_{1:T}),}$

โดยที่สัญลักษณ์ "หมวก" บ่งบอกถึงข้อเท็จจริงที่ว่าเป็นการแทรกแซงเชิงสาเหตุ (ดูความเป็นเหตุเป็นผล ) และไม่ใช่การสังเกตธรรมดา หากตัวแทนมีความเชื่อเกี่ยวกับพฤติกรรมของตนเอง กฎการควบคุมแบบเบย์เซียนก็จะกลายเป็น ${\displaystyle {\hat {a}}_{t}}$${\displaystyle a_{t}}$${\displaystyle \theta \in \Theta }$

${\displaystyle 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 }$,

การแจกแจงความน่าจะเป็นภายหลังของพารามิเตอร์ที่กำหนดโดยการกระทำและการสังเกตนั้น อยู่ ที่ใด${\displaystyle P(\theta |{\hat {a}}_{1:T},o_{1:T})}$${\displaystyle \theta }$${\displaystyle a_{1:T}}$${\displaystyle o_{1:T}}$

ในทางปฏิบัติ การควบคุมแบบเบย์เซียนเทียบเท่ากับการสุ่มเลือกพารามิเตอร์จากความน่าจะเป็นภายหลัง ในแต่ละช่วงเวลา โดยที่ความน่าจะเป็นภายหลังนั้นคำนวณโดยใช้กฎของเบย์ส โดยพิจารณาเฉพาะความน่าจะเป็น (เชิงสาเหตุ) ของการสังเกตการณ์และละเลยความน่าจะเป็น (เชิงสาเหตุ) ของการกระทำจากนั้นจึงสุ่มเลือกการกระทำจาก ความน่าจะเป็น ของการกระทำ${\displaystyle \theta ^{\ast }}$${\displaystyle P(\theta |{\hat {a}}_{1:T},o_{1:T})}$${\displaystyle o_{1},o_{2},\ldots ,o_{T}}$${\displaystyle a_{1},a_{2},\ldots ,a_{T}}$${\displaystyle a_{T+1}^{\ast }}$${\displaystyle P(a_{T+1}|\theta ^{\ast },{\hat {a}}_{1:T},o_{1:T})}$

การสุ่มตัวอย่างของ Thompson และอัลกอริธึมขอบเขตความเชื่อมั่นบนมีคุณสมบัติพื้นฐานร่วมกันซึ่งเป็นพื้นฐานของการรับประกันทางทฤษฎีหลายประการ โดยคร่าวๆ แล้ว อัลกอริธึมทั้งสองจะจัดสรรความพยายามในการสำรวจให้กับการกระทำที่อาจเหมาะสมที่สุดและในแง่นี้ถือว่า "มองโลกในแง่ดี" การใช้ประโยชน์จากคุณสมบัตินี้ทำให้สามารถแปลขอบเขตความเสียใจที่กำหนดขึ้นสำหรับอัลกอริธึม UCB ไปเป็น ขอบเขต ความเสียใจแบบเบย์เซียนสำหรับการสุ่มตัวอย่างของ Thompson ^{[ 13 ]}หรือรวมการวิเคราะห์ความเสียใจเข้าด้วยกันในอัลกอริธึมทั้งสองนี้และปัญหาหลายประเภท^{[ 14 ]}