In timed, zero-sum games, the goal

In timed, zero-sum games, the goal is to maximize the probability
of winning, which is not necessarily the same as maximizing
our expected reward. We consider cumulative intermediate
reward to be the difference between our score and
our opponent’s score; the “true” reward of a win, loss, or
tie is determined at the end of a game by applying a threshold
function to the cumulative intermediate reward. We introduce
thresholded-rewards problems to capture this dependency
of the final reward outcome on the cumulative intermediate
reward. Thresholded-rewards problems reflect different
real-world stochastic planning domains, especially zero-sum
games, in which time and score need to be considered. We
investigate the application of thresholded rewards to finitehorizon
Markov Decision Processes (MDPs). In general, the
optimal policy for a thresholded-rewards MDP will be nonstationary,
depending on the number of time steps remaining
and the cumulative intermediate reward. We introduce
an efficient value iteration algorithm that solves thresholdedrewards
MDPs exactly, but with running time quadratic on
the number of states in the MDP and the length of the time
horizon. We investigate a number of heuristic-based techniques
that efficiently find approximate solutions for MDPs
with large state spaces or long time horizons.

ผลลัพธ์ (ไทย) 1:

ในเวลาที่กำหนด ศูนย์รวมเกมส์ เป้าหมายคือการ ขยายความเป็นไปได้ชนะ ซึ่งไม่จำเป็นต้องเหมือนกับการเพิ่มของเราผลตอบแทนที่คาดไว้ เราพิจารณาระดับปานกลางสะสมรางวัลมีความแตกต่างระหว่างคะแนนของเรา และคะแนนของฝ่ายตรงข้ามของเรา รางวัล "ความจริง" ของการชนะ ขาดทุน หรือเสมอเป็นไปตามที่สุดของเกมใช้เป็นขีดจำกัดฟังก์ชันการสะสมรางวัลกลาง เราแนะนำปัญหา thresholded ของรางวัลในการจับภาพนี้อ้างอิงผลรางวัลสุดท้ายในระดับปานกลางสะสมรางวัล ปัญหา Thresholded รางวัลที่สะท้อนให้เห็นถึงแตกต่างกันโดเมนวางแผนแบบเฟ้นสุ่มจริง โดยเฉพาะอย่างยิ่งศูนย์รวมเกม ซึ่งเวลาและคะแนนต้องได้รับการพิจารณา เราตรวจสอบโปรแกรมประยุกต์ของรางวัล thresholded finitehorizonกระบวนการตัดสินใจ Markov (MDPs) ทั่วไป การนโยบายที่เหมาะสมที่สุดสำหรับ MDP thresholded รางวัลจะเป็น nonstationaryขึ้นอยู่กับจำนวนขั้นตอนเวลาที่เหลือและรางวัลกลางสะสม เราแนะนำมีค่าประสิทธิภาพเกิดซ้ำอัลกอริทึมที่แก้ thresholdedrewardsMDPs แน่นอน แต่ มีการเรียกใช้เวลากำลังสองในหมายเลขของอเมริกา MDP และระยะเวลาขอบฟ้า เราตรวจสอบจำนวนเทคนิค heuristic ตามที่มีประสิทธิภาพค้นหาโซลูชั่นโดยประมาณ MDPsมีช่องว่างรัฐขนาดใหญ่หรือยาวเวลาฮอลิซันส์

ผลลัพธ์ (ไทย) 2:

หมดเวลาในเกมศูนย์รวมเป้าหมายคือเพื่อเพิ่มความน่าจะเป็นในการชนะที่ไม่จำเป็นต้องเหมือนกับการเพิ่มผลตอบแทนที่คาดหวังของเรา เราพิจารณากลางสะสมรางวัลจะเป็นความแตกต่างระหว่างคะแนนของเราและคะแนนของฝ่ายตรงข้ามของเรา; "true" รางวัลชนะสูญเสียหรือผูกจะถูกกำหนดในตอนท้ายของเกมโดยใช้เกณฑ์การทำงานเพื่อผลตอบแทนสะสมกลาง เราแนะนำปัญหาผลตอบแทน-thresholded ในการจับภาพการพึ่งพานี้ของผลรางวัลรอบสุดท้ายเมื่อกลางสะสมรางวัล Thresholded-ผลตอบแทนที่สะท้อนให้เห็นถึงปัญหาที่แตกต่างกันในโลกความจริงโดเมนวางแผนสุ่มโดยเฉพาะอย่างยิ่งศูนย์รวมเกมซึ่งในเวลาและคะแนนจะต้องพิจารณา เราตรวจสอบแอพลิเคชันของรางวัล thresholded เพื่อ finitehorizon กระบวนการตัดสินใจมาร์คอฟ (MDPs) โดยทั่วไปนโยบายที่ดีที่สุดสำหรับผลตอบแทน-thresholded MDP จะไม่คงที่, ขึ้นอยู่กับจำนวนของขั้นตอนเวลาที่เหลืออยู่และรางวัลสะสมกลาง เราแนะนำขั้นตอนวิธีการทำซ้ำค่าที่มีประสิทธิภาพที่จะช่วยแก้ thresholdedrewards MDPs ว่า แต่กับการทำงานเวลากำลังสองในจำนวนของรัฐในMDP และความยาวของเวลาที่ขอบฟ้า เราจะตรวจสอบจำนวนของเทคนิคการแก้ปัญหาตามที่มีประสิทธิภาพหาทางแก้ไขปัญหาโดยประมาณสำหรับ MDPs ที่มีช่องว่างขนาดใหญ่ของรัฐหรือขอบฟ้าเวลานาน

ผลลัพธ์ (ไทย) 3:

ในจังหวะที่ ซีโร่ซัมเกม เป้าหมายคือเพื่อเพิ่มความน่าจะเป็น
ชนะ ซึ่งไม่เหมือนกับการเพิ่ม
ของเราคาดหวังรางวัล เราพิจารณาสะสมกลาง
รางวัลเป็นความแตกต่างระหว่างคะแนน และคะแนนของฝ่ายตรงข้าม
; " เป็นจริง " รางวัลชนะ แพ้ หรือเสมอ
ถูกกำหนดในตอนท้ายของเกม โดยใช้เกณฑ์
ฟังก์ชันที่จะให้รางวัลกลางสะสม เราแนะนำ
thresholded รางวัลปัญหาเพื่อจับภาพนี้พึ่งพา
ผลรางวัลสุดท้ายรางวัลกลาง
สะสม thresholded รางวัลปัญหาแสดงให้เห็นถึงความแตกต่าง
-
โดยเฉพาะผลรวมสุ่มวางแผนโดเมน , ศูนย์เกมและคะแนนในเวลาที่ต้องได้รับการพิจารณา เรา
ศึกษาการประยุกต์ใช้ thresholded รางวัลการตัดสินใจ finitehorizon
กระบวนการมาร์คอฟ ( mdps ) โดยทั่วไป นโยบายที่เหมาะสมสำหรับรางวัล
thresholded MDP จะติจิ
, ขึ้นอยู่กับจำนวนของขั้นตอนเวลาคงเหลือ
และรางวัลกลางสะสม เราแนะนำที่มีประสิทธิภาพการสร้างค่า

mdps แก้ thresholdedrewards ทุกประการแต่เวลาวิ่งกำลังสองบน
หมายเลขของรัฐใน MDP และความยาวของเวลา
ขอบฟ้า เราตรวจสอบหมายเลขของฮิวริสติกที่ใช้เทคนิค
ที่มีประสิทธิภาพหาโซลูชั่นสำหรับประมาณ mdps
กับรัฐหรือขอบเขตขนาดใหญ่เป็นเวลานาน