บทนำสู่โจรหลายแขน

ลิขสิทธิ์ 2021 The TF-Agents Authors.

บทนำ

Multi-Armed Bandit (MAB) เป็นเฟรมเวิร์กการเรียนรู้ของเครื่องที่ตัวแทนต้องเลือกการกระทำ (อาวุธ) เพื่อเพิ่มรางวัลสะสมในระยะยาว ในแต่ละรอบ เจ้าหน้าที่จะได้รับข้อมูลบางอย่างเกี่ยวกับสถานะปัจจุบัน (บริบท) จากนั้นจึงเลือกการดำเนินการตามข้อมูลนี้และประสบการณ์ที่รวบรวมในรอบก่อนหน้า ในตอนท้ายของแต่ละรอบ ตัวแทนจะได้รับรางวัลที่เกี่ยวข้องกับการกระทำที่เลือก

บางทีอาจจะเป็นตัวอย่างที่บริสุทธิ์เป็นปัญหาที่ยืมชื่อ MAB: คิดว่าเรากำลังเผชิญกับ k เครื่องสล็อต (หนึ่งติดอาวุธโจร) และเราต้องคิดออกที่หนึ่งที่มีการจ่ายเงินที่ดีที่สุดในขณะที่ไม่สูญเสียเงินมากเกินไป

การลองใช้เครื่องแต่ละเครื่องแล้วเลือกเครื่องที่จ่ายมากที่สุดไม่ใช่กลยุทธ์ที่ดี: ตัวแทนอาจตกอยู่ในการเลือกเครื่องที่มีผลลัพท์ที่ดีในตอนเริ่มต้น แต่โดยทั่วไปแล้วถือว่าด้อยประสิทธิภาพ ตัวแทนควรกลับมาเลือกเครื่องจักรที่ดูไม่ดีซ้ำแล้วซ้ำเล่า เพื่อรวบรวมข้อมูลเพิ่มเติมเกี่ยวกับเครื่องจักรเหล่านั้น นี่คือความท้าทายหลักใน Multi-Armed Bandits: เจ้าหน้าที่ต้องหาส่วนผสมที่เหมาะสมระหว่างการใช้ประโยชน์จากความรู้เดิมและการสำรวจเพื่อหลีกเลี่ยงการมองข้ามการกระทำที่เหมาะสมที่สุด

กรณีที่ใช้งานได้จริงมากขึ้นของ MAB เกี่ยวข้องกับข้อมูลข้างเคียงทุกครั้งที่ผู้เรียนทำการตัดสินใจ เราเรียกข้อมูลด้านนี้ว่า "บริบท" หรือ "การสังเกต"

โจรหลายอาวุธและการเรียนรู้การเสริมกำลัง

ทำไมถึงมี MAB Suite ในห้องสมุด TF-Agents? ความสัมพันธ์ระหว่าง RL และ MAB คืออะไร? Multi-Armed Bandits ถือได้ว่าเป็นกรณีพิเศษของ Reinforcement Learning ที่จะพูด แนะนำ RL :

ในแต่ละขั้นตอนเวลาที่ตัวแทนจะใช้เวลาดำเนินการในสภาพแวดล้อมที่อยู่บนพื้นฐานของนโยบาย \(\pi(a_t|s_t)\)ที่ \(s_t\) เป็นข้อสังเกตในปัจจุบันจากสภาพแวดล้อมและได้รับรางวัล \(r_{t+1}\) และสังเกตต่อไป \(s_{t+1}\) จากสภาพแวดล้อม . เป้าหมายคือการปรับปรุงนโยบายเพื่อให้ได้ผลตอบแทนสูงสุด (ผลตอบแทน) สูงสุด

ในกรณี RL ทั่วไปสังเกตต่อไป \(s_{t+1}\) ขึ้นอยู่กับสถานะก่อนหน้า \(s_t\) และการกระทำ \(a_t\) ถ่ายโดยนโยบาย ส่วนสุดท้ายนี้คือสิ่งที่แยก MAB ออกจาก RL: ใน MAB สถานะถัดไป ซึ่งเป็นการสังเกต ไม่ได้ขึ้นอยู่กับการดำเนินการที่เลือกโดยตัวแทน

ความคล้ายคลึงกันนี้ทำให้เราสามารถนำแนวคิดทั้งหมดที่มีอยู่ใน TF-Agents กลับมาใช้ใหม่ได้

• สภาพแวดล้อมที่เอาท์พุทสังเกตและตอบสนองต่อการกระทำที่มีผลตอบแทน
• นโยบายการดำเนินการเอาท์พุทจากการสังเกตและ
• ตัวแทนซ้ำ ๆ การปรับปรุงนโยบายขึ้นอยู่กับ tuples สังเกตการกระทำรางวัลก่อนหน้านี้

สิ่งแวดล้อมเห็ด

เพื่อเป็นตัวอย่าง เราใช้ตัวอย่างของเล่นที่เรียกว่า "สภาพแวดล้อมของเห็ด" ชุดข้อมูลเห็ด ( Schlimmer 1981 ) ประกอบด้วยตัวอย่างการติดป้ายชื่อของเห็ดที่กินได้และเป็นพิษ ลักษณะเด่น ได้แก่ รูปร่าง สี ขนาดส่วนต่างๆ ของเห็ด กลิ่น และอื่นๆ อีกมากมาย

ชุดข้อมูลเห็ด เหมือนกับชุดข้อมูลการเรียนรู้ภายใต้การดูแลทั้งหมด สามารถเปลี่ยนเป็นปัญหา MAB ตามบริบทได้ เราใช้วิธีการที่ใช้โดย Riquelme, et al (2018) ในแปลงนี้ตัวแทนได้รับคุณสมบัติของเห็ดตัดสินใจว่าจะกินหรือไม่ การกินเห็ดที่กินได้จะทำให้ได้รางวัล +5 ในขณะที่การกินเห็ดพิษจะให้ +5 หรือ -35 อย่างใดอย่างหนึ่งด้วยความน่าจะเป็นเท่ากัน การไม่กินเห็ดทำให้ได้รางวัลเป็น 0 โดยไม่ขึ้นกับชนิดของเห็ด ตารางต่อไปนี้สรุปการมอบหมายรางวัล:

           | edible | poisonous
-----------|--------|----------
eating it  |     +5 | -35 / +5
leaving it |      0 |        0

ตัวแทน LinUCB

การแสดงได้ดีในสภาพแวดล้อมแบบโจรกรรมตามบริบทจำเป็นต้องมีการประมาณที่ดีเกี่ยวกับฟังก์ชันการให้รางวัลของแต่ละการกระทำ เมื่อพิจารณาจากการสังเกต ความเป็นไปได้อย่างหนึ่งคือการประมาณการฟังก์ชันการให้รางวัลด้วยฟังก์ชันเชิงเส้น นั่นคือสำหรับการดำเนินการทุก \(i\)เรากำลังพยายามที่จะหาพารามิเตอร์ \(\theta_i\in\mathbb R^d\) ที่ประมาณการไว้

\(r_{t, i} \sim \langle v_t, \theta_i\rangle\)

ใกล้เคียงกับความเป็นจริงมากที่สุด นี่ \(v_t\in\mathbb R^d\) เป็นบริบทที่ได้รับในเวลาขั้นตอน \(t\)แล้วถ้าตัวแทนมีความมั่นใจมากในการประมาณการของมันก็สามารถเลือก \(\arg\max_{1, ..., K}\langle v_t, \theta_k\rangle\) ที่จะได้รับผลตอบแทนที่คาดว่าจะสูงที่สุด

ตามที่อธิบายไว้ข้างต้น การเลือกแขนที่มีรางวัลโดยประมาณที่ดีที่สุดไม่ได้นำไปสู่กลยุทธ์ที่ดี มีหลายวิธีในการผสมการใช้ประโยชน์และการสำรวจในตัวแทนประมาณการเชิงเส้นและหนึ่งที่มีชื่อเสียงมากที่สุดคือความเชื่อมั่นเชิงเส้น Upper Bound (LinUCB) อัลกอริทึม (ดูเช่น Li et al. 2010 ) LinUCB มีหน่วยการสร้างหลักสองส่วน (โดยละเว้นรายละเอียดบางส่วน):

1. มันจะเก็บค่าประมาณสำหรับพารามิเตอร์ของแขนทุกแบบลิเนียร์สแควน้อย: \(\hat\theta_i\sim X^+_i r_i\)ที่ \(X_i\) และ \(r_i\) เป็นบริบทที่ซ้อนกันและผลตอบแทนของรอบที่แขน \(i\) ได้รับการคัดเลือกและ \(()^+\) เป็นสิ่งที่ตรงกันข้ามหลอก .
2. มันจะเก็บ ellipsoids ความเชื่อมั่นที่กำหนดโดยผกผันแปรปรวน \(X_i^\top X_i\) สำหรับการประมาณการดังกล่าวข้างต้น

แนวคิดหลักของ LinUCB คือ "การมองในแง่ดีเมื่อเผชิญกับความไม่แน่นอน" ตัวแทนรวมการสำรวจผ่านการเพิ่มการประมาณการด้วยจำนวนที่สอดคล้องกับความแปรปรวนของการประมาณการเหล่านั้น ที่เป็นที่ ellipsoids ความมั่นใจที่เข้ามาในภาพ: ทุกแขนประมาณการในแง่ดีเป็น \(\hat r_i = \max_{\theta\in E_i}\langle v_t, \theta\rangle\)ที่ \(E_i\) เป็นทรงรีรอบ \(\hat\theta_i\)เลือกตัวแทนที่ดีที่สุดมองแขน \(\arg\max_i\hat r_i\)

แน่นอน คำอธิบายข้างต้นเป็นเพียงบทสรุปที่เข้าใจง่ายแต่เพียงผิวเผินของสิ่งที่ LinUCB ทำ การดำเนินการสามารถพบได้ใน codebase ของเรา ที่นี่

อะไรต่อไป?

หากคุณต้องการที่จะมีรายละเอียดเพิ่มเติมเกี่ยวกับการกวดวิชาห้องสมุดโจรของเราจะดูที่เรา สอนสำหรับโจร หาก แต่คุณต้องการที่จะเริ่มต้นการสำรวจห้องสมุดของเราทันทีที่คุณสามารถค้นหาได้ ที่นี่ หากคุณมีมากขึ้นความกระตือรือร้นที่จะเริ่มต้นการฝึกอบรมดูที่บางส่วนของตัวอย่างแบบ end-to-end ของเรา ที่นี่ รวมทั้งสภาพแวดล้อมดังกล่าวข้างต้นเห็ดอธิบายด้วย LinUCB ที่นี่