I detta dokument introducerar vi idén om en begränsad parameter Markov beslutsprocess (BMDP) som en generalisering av den välkända exakta MDP. En begränsad parameter MDP är en uppsättning exakta MDP som anges genom att ge övre och nedre gränser för övergångs sannolikheter och belöningar (alla MDP i uppsättningen delar samma tillstånd och åtgärd utrymme). BMDP utgör ett effektivt lösbart specialfall för den redan kända klassen av MDP med otydliga parametrar. Bounded-parameter MDP kan användas för att representera variation eller osäkerhet om parametrarna för sekventiella beslutsproblem i fall där det inte finns några tidigare sannolikheter för parametervärdena. Bounded-parameter MDP kan också användas i aggregeringssystem för att representera variationen i övergångssannolikheterna för olika basstater aggregerade i samma aggregerade tillstånd. Vi introducerar intervallvärdefunktioner som en naturlig förlängning av traditionella värdefunktioner. En funktion för intervallvärde tilldelar varje tillstånd ett slutet reellt intervall, vilket representerar påståendet att detta tillstånds värde ligger inom detta intervall. En intervallvärdefunktion kan användas för att begränsa resultatet av en policy över den uppsättning exakta MDP som är förknippad med en given begränsad parameter MDP. Vi beskriver en iterativ dynamisk programmeringsalgoritm kallad intervallpolicyutvärdering som beräknar en intervallvärdefunktion för en given BMDP och specificerad policy. Interval policyutvärdering på en policy beräknar den mest restriktiva intervallvärdefunktion som är sund, dvs. som begränsar värdefunktionen för varje exakt MDP i den uppsättning som definieras av den begränsade parametern MDP. Vi definierar optimistiska och pessimistiska kriterier för optimalitet och tillhandahåller en variant av värde iteration [1] som vi kallar intervallvärde iteration som beräknar policyer för en BMDP som är optimal med avseende på dessa kriterier. Vi visar att varje algoritm vi presenterar konvergerar till de önskade värdena i ett polynom antal iterationer givet en fast rabattfaktor.
Bounded-parametern Markov Decision Process (BMDP) REF ) är ett specialfall av en MDP-IP, där sannolikheterna och belöningarna specificeras med konstanta intervall.
Bounded-Parameter Markov Decision Processes
{'venue': 'Artificial Intelligence', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}