Skip to content
กลับไปยังผลการค้นหา

Q-Learning

ผู้เสนอ
Christopher Watkins & Peter Dayan
ปี
1992
ประเภท
Model-free reinforcement-learning control algorithm
กลุ่มวิธี
Reinforcement learning

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

Q-learning ซึ่งนำเสนอโดย Christopher Watkins และ Peter Dayan ในปี 1992 เป็นอัลกอริทึมการเรียนรู้แบบเสริมกำลัง (reinforcement-learning) ที่ไม่ต้องใช้แบบจำลอง (model-free) ซึ่งเรียนรู้คุณค่าของการกระทำแต่ละอย่างในแต่ละสถานะ — ฟังก์ชัน Q — จากประสบการณ์โดยตรง โดยไม่ต้องอาศัยแบบจำลองของสภาพแวดล้อม เป็นแบบนอกนโยบาย (off-policy): เรียนรู้ค่าการกระทำที่เหมาะสมที่สุดในขณะที่ดำเนินตามนโยบายพฤติกรรมการสำรวจ และภายใต้เงื่อนไขมาตรฐาน สามารถพิสูจน์ได้ว่าลู่เข้าสู่นโยบายที่เหมาะสมที่สุด

แนวคิดเบื้องหลังวิธีการ

เอเจนต์ที่เรียนรู้จากการลองผิดลองถูกจำเป็นต้องทราบว่า ในแต่ละสถานการณ์ การกระทำที่เป็นไปได้แต่ละอย่างนั้นดีเพียงใดในระยะยาว Q-learning รักษาค่าเหล่านี้ไว้: ตาราง (หรือฟังก์ชัน) ของค่า Q ซึ่งประมาณค่าผลตอบแทนในอนาคตทั้งหมดของการกระทำการหนึ่งในสถานะหนึ่งและการปฏิบัติตนอย่างเหมาะสมที่สุดหลังจากนั้น ทุกครั้งที่เอเจนต์กระทำการ สังเกตผลตอบแทน และเข้าสู่สถานะใหม่ มันจะปรับค่า Q ให้เข้าใกล้สิ่งที่เพิ่งประสบมา บวกกับสิ่งที่ดีที่สุดที่เชื่อว่าสามารถทำได้ต่อไป สิ่งสำคัญคือ มันอัปเดตไปสู่การกระทำที่ดีที่สุดครั้งต่อไป โดยไม่คำนึงถึงสิ่งที่ได้ทำไปจริง ๆ — ดังนั้นจึงสามารถสำรวจได้อย่างอิสระในขณะที่ยังคงเรียนรู้นโยบายที่เหมาะสมที่สุด

ประวัติศาสตร์

Christopher Watkins ได้นำเสนอ Q-learning ในวิทยานิพนธ์ของเขาในปี 1989 และ Watkins กับ Dayan (1992) ได้ให้การพิสูจน์การลู่เข้า ซึ่งทำให้เป็นรากฐานสำคัญของการเรียนรู้แบบเสริมกำลัง วิธีนี้เป็นการขยายการเรียนรู้แบบความแตกต่างของเวลา (temporal-difference learning) ไปสู่การควบคุม และเป็นพื้นฐานของความสำเร็จในภายหลัง — โดยเฉพาะอย่างยิ่ง Deep Q-Networks (Mnih et al., 2015) ซึ่งรวม Q-learning กับโครงข่ายประสาทเทียมเชิงลึกเพื่อเล่นเกม Atari จากภาพพิกเซล วิธีนี้ได้รับการกล่าวถึงอย่างเป็นระบบในตำราของ Sutton และ Barto และยังคงเป็นจุดเริ่มต้นมาตรฐานสำหรับการเรียนรู้แบบเสริมกำลังที่อิงตามค่า (value-based RL)

ควรใช้เมื่อใด

ใช้ Q-learning สำหรับปัญหาการตัดสินใจตามลำดับที่กำหนดในรูปแบบของกระบวนการตัดสินใจมาร์คอฟ (Markov decision process) ที่คุณสามารถสุ่มตัวอย่างการเปลี่ยนผ่านและผลตอบแทนได้ แต่ไม่มีแบบจำลอง (หรือแบบจำลองที่ไม่น่าเชื่อถือ) ของพลวัต — การควบคุม เกม การกำหนดเส้นทาง การจัดตารางเวลา และระบบปรับตัว Q-learning แบบตาราง (Tabular Q-learning) เหมาะสำหรับปริภูมิสถานะ-การกระทำขนาดเล็กและไม่ต่อเนื่อง และลู่เข้าสู่ค่าที่เหมาะสมที่สุดหากมีการสำรวจเพียงพอและขนาดขั้นตอนลดลง สำหรับปริภูมิขนาดใหญ่หรือต่อเนื่อง ตารางจะถูกแทนที่ด้วยตัวประมาณค่าฟังก์ชัน (เช่น Deep Q-Networks) วิธีนี้สมมติคุณสมบัติมาร์คอฟและสภาพแวดล้อมที่คงที่ อาจไม่มีประสิทธิภาพในการใช้ตัวอย่าง (sample-inefficient) และตัวดำเนินการ max ก่อให้เกิดความเอนเอียงเชิงมองโลกในแง่ดี (การประมาณค่าสูงเกินไป) ซึ่งได้รับการแก้ไขโดยรูปแบบต่างๆ เช่น Double Q-learning เมื่อต้องการนโยบายแบบสุ่มหรือแบบต่อเนื่อง วิธีการไล่ระดับนโยบาย (policy-gradient methods) จะเป็นทางเลือก

ข้อจำกัดและข้อควรพิจารณา

  • รูปแบบตารางไม่สามารถปรับขนาดให้เข้ากับปริภูมิสถานะ/การกระทำขนาดใหญ่หรือต่อเนื่องได้
  • ไม่มีประสิทธิภาพในการใช้ตัวอย่าง (Sample-inefficient); อาจต้องใช้อีพิโซดจำนวนมากจึงจะลู่เข้า
  • ความเอนเอียงจากการประมาณค่าสูงเกินไป (overestimation bias) จากตัวดำเนินการ max; ลดทอนได้ด้วย Double Q-learning
  • สมมติว่าเป็นกระบวนการตัดสินใจมาร์คอฟ (Markov decision process) ที่คงที่; มีปัญหาภายใต้การสังเกตการณ์บางส่วนหรือการเปลี่ยนแปลง

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • ไม่ต้องใช้แบบจำลอง (Model-free): ไม่ต้องการแบบจำลองการเปลี่ยนผ่าน/ผลตอบแทน ต้องการเพียงประสบการณ์ที่สุ่มตัวอย่างได้
  • นอกนโยบาย (Off-policy): เรียนรู้นโยบายที่เหมาะสมที่สุดในขณะที่สำรวจด้วยนโยบายอื่น
  • สามารถพิสูจน์ได้ว่าลู่เข้าสู่ค่าการกระทำที่เหมาะสมที่สุดภายใต้เงื่อนไขมาตรฐาน
  • เรียบง่าย เป็นพื้นฐาน และเป็นรากฐานของ Deep Q-Networks และส่วนขยายอื่นๆ อีกมากมาย

การประยุกต์ใช้

  • การเล่นเกมและงานควบคุมจำลอง
  • การนำทางหุ่นยนต์และการควบคุมแบบปรับได้
  • การกำหนดเส้นทางแบบไดนามิก การจัดตารางเวลา และการจัดสรรทรัพยากร
  • นโยบายการแนะนำและการโต้ตอบแบบปรับได้
  • วิธีการอิงตามค่าที่เป็นพื้นฐานก่อน Deep Q-Networks

วิธีการทำงาน

วิธีการทำงาน

1

Q(s, a) ประมาณค่าผลรวมส่วนลดที่คาดหวังของผลตอบแทนในอนาคตจากการกระทำ a ในสถานะ s และจากนั้นจึงปฏิบัติตนอย่างเหมาะสมที่สุด ตัวคูณส่วนลด γ ให้ความสำคัญกับผลตอบแทนที่ใกล้กว่ามากกว่าผลตอบแทนที่อยู่ไกลออกไป การเรียนรู้ Q สำหรับคู่สถานะ-การกระทำทั้งหมดเทียบเท่ากับการแก้ปัญหาการควบคุม

สูตร
Q(s,a) \approx \mathbb{E}\!\left[\textstyle\sum_{k\ge0}\gamma^{k} r_{t+k+1}\mid s_t=s,a_t=a\right]
2

หลังจากการเปลี่ยนผ่านแต่ละครั้ง (สถานะ s, การกระทำ a, ผลตอบแทน r, สถานะถัดไป s') Q-learning จะอัปเดต Q(s, a) ด้วยขั้นตอน α ไปสู่เป้าหมายความแตกต่างของเวลา (temporal-difference target) r + γ·max ของ Q(s', a') โดยพิจารณาการกระทำถัดไป 'max' คือสิ่งที่ทำให้เป็นแบบนอกนโยบาย (off-policy) และชี้การเรียนรู้ไปยังค่าที่เหมาะสมที่สุด โดยไม่ขึ้นกับการกระทำที่ทำไปจริง ๆ ในครั้งต่อไป

สูตร
Q(s,a) \leftarrow Q(s,a) + \alpha\big[r + \gamma \max_{a'} Q(s',a') - Q(s,a)\big]
3

เพื่อรวบรวมประสบการณ์ เอเจนต์จะกระทำการตามนโยบายการสำรวจ (exploration policy) ซึ่งโดยทั่วไปคือ ε-greedy: โดยปกติจะเลือกการกระทำที่ดีที่สุดในปัจจุบัน แต่ด้วยความน่าจะเป็น ε จะเลือกการกระทำแบบสุ่ม การสำรวจช่วยให้แน่ใจว่าคู่สถานะ-การกระทำทั้งหมดจะถูกลอง ซึ่งการรับประกันการลู่เข้าต้องการ; โดยทั่วไป ε จะลดลงเมื่อเวลาผ่านไป

สูตร
a = \begin{cases}\arg\max_a Q(s,a) & \text{prob } 1-\epsilon\\ \text{random} & \text{prob } \epsilon\end{cases}
4

เมื่อ Q ลู่เข้าสู่ค่าการกระทำที่เหมาะสมที่สุด Q* นโยบายที่เหมาะสมที่สุดก็คือการเลือกการกระทำที่มีค่า Q สูงสุดในแต่ละสถานะ ในทางปฏิบัติ นโยบายแบบละโมบ (greedy policy) ที่สัมพันธ์กับ Q ปัจจุบันจะถูกดึงออกมาในตอนท้าย (หรือใช้เมื่อนำไปใช้งาน)

สูตร
\pi^*(s) = \arg\max_a Q^*(s,a)

ข้อผิดพลาดที่พบบ่อย

  • การสำรวจไม่เพียงพอ (ε น้อยเกินไป/ลดลงเร็วเกินไป) ทำให้ไม่สามารถเรียนรู้นโยบายที่เหมาะสมที่สุดได้
  • ตารางการเรียนรู้ที่ไม่เหมาะสม ทำให้เกิดการลู่ออกหรือการเรียนรู้ที่ช้ามาก
  • การใช้ Q-learning แบบตารางกับปริภูมิขนาดใหญ่แทนตัวประมาณค่าฟังก์ชัน
  • การละเลยความเอนเอียงจากการประมาณค่าสูงเกินไปในปัญหาแบบสุ่ม ซึ่ง Double Q-learning สามารถช่วยได้

คำถามที่พบบ่อย

คำว่า 'นอกนโยบาย' (off-policy) ใน Q-learning หมายถึงอะไร?

หมายความว่า Q-learning เรียนรู้คุณค่าของนโยบายที่เหมาะสมที่สุดในขณะที่เอเจนต์ปฏิบัติตามนโยบายพฤติกรรมการสำรวจ (exploratory) ที่แตกต่างกัน เป้าหมายการอัปเดตคือ r + γ·max Q(s', a') — การกระทำที่ดีที่สุดครั้งต่อไป — ไม่ใช่การกระทำที่ทำไปจริง ๆ ดังนั้น การสำรวจจึงไม่ทำให้ค่าที่เหมาะสมที่สุดที่เรียนรู้เกิดความเอนเอียง

Q-learning เกี่ยวข้องกับ Deep Q-Networks (DQN) อย่างไร?

DQN แทนที่ตาราง Q ด้วยโครงข่ายประสาทเทียมเชิงลึกที่ประมาณค่า Q(s, a) ทำให้ Q-learning สามารถทำงานในปริภูมิสถานะขนาดใหญ่หรือต่อเนื่อง (เช่น ภาพพิกเซล) ได้ DQN เพิ่มเทคนิคการทำให้เสถียร — การเล่นซ้ำประสบการณ์ (experience replay) และโครงข่ายเป้าหมาย (target network) — แต่กฎการเรียนรู้หลักคือการอัปเดตความแตกต่างของเวลาของ Q-learning

เหตุใด Q-learning จึงประมาณค่าสูงเกินไป?

ตัวดำเนินการ max ในการอัปเดตมีแนวโน้มที่จะเลือกค่าประมาณที่มองโลกในแง่ดีเกินไป ทำให้ค่า Q เอนเอียงไปทางสูง โดยเฉพาะอย่างยิ่งกับผลตอบแทนที่มีสัญญาณรบกวน Double Q-learning ช่วยลดปัญหานี้โดยการแยกการเลือกการกระทำออกจากการประเมินค่าโดยใช้ตัวประมาณค่าสองตัว ซึ่งให้ผลลัพธ์ที่เอนเอียงน้อยลงและมักจะได้นโยบายที่ดีกว่า

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Watkins, C. J. C. H., & Dayan, P. (1992). Q-learning. Machine Learning, 8(3–4), 279–292.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press.

    ISBN: 978-0-262-03924-6
    คัดลอกแล้ว