Eine Theorie der Lernbarkeit für Offline-Entscheidungsfindung

Wir untersuchen das Problem der Offline-Entscheidungsfindung, das sich darauf konzentriert, Entscheidungen aus Datensätzen zu lernen, die nur teilweise mit dem Lernziel korreliert sind. Während frühere Forschungen spezifische Probleme der Offline-Entscheidungsfindung wie Offline-Verstärkungslernen (RL) und Off-Policy-Bewertung (OPE) umfassend untersucht haben, fehlt ein einheitliches Framework und eine Theorie. Um diese Lücke zu schließen, führen wir ein einheitliches Framework namens Entscheidungsfindung mit Offline-Feedback (DMOF) ein, das eine breite Palette von Offline-Entscheidungsfindungsproblemen abdeckt, einschließlich Offline-RL, OPE und offline teilweise beobachtbare Markov-Entscheidungsprozesse (POMDPs). Für das DMOF-Framework führen wir ein Maß für die Schwierigkeit ein, das als Offline-Schätzkoeffizient (OEC) bezeichnet wird und die Lernbarkeit von Offline-Entscheidungsfindungsproblemen misst, was sich auch in den abgeleiteten Minimax-Untergrenzen widerspiegelt. Darüber hinaus führen wir einen Algorithmus namens Empirische Entscheidung mit Divergenz (EDD) ein, für den wir sowohl eine instanzabhängige obere Grenze als auch eine Minimax-obere Grenze festlegen. Die Minimax-obere Grenze entspricht nahezu der unteren Grenze, die durch den OEC bestimmt wird. Schließlich zeigen wir, dass EDD eine schnelle Konvergenzrate erreicht (d.h. eine Rate, die sich als 1/N skaliert, wobei N die Stichprobengröße ist) für spezifische Einstellungen wie das überwachte Lernen und Markov-sequenzielle Probleme (z.B. MDPs) mit teilweiser Abdeckung.