Randomized Linear Programming Solves the Markov Decision Problem in Nearly Linear (Sometimes Sublinear) Time (Q5119845): Difference between revisions

Latest revision as of 09:54, 23 July 2024

scientific article; zbMATH DE number 7242693

Language	Label	Description	Also known as
English	Randomized Linear Programming Solves the Markov Decision Problem in Nearly Linear (Sometimes Sublinear) Time	scientific article; zbMATH DE number 7242693

Statements

instance of

scholarly article

0 references

title

Randomized Linear Programming Solves the Markov Decision Problem in Nearly Linear (Sometimes Sublinear) Time (English)

0 references

author

Mengdi Wang

0 references

published in

Mathematics of Operations Research

0 references

publication date

1 September 2020

0 references

full work available at URL

https://arxiv.org/abs/1704.01869

0 references

zbMATH Keywords

Markov decision process

0 references

randomized algorithm

0 references

linear programming

0 references

duality

0 references

primal-dual method

0 references

runtime complexity

0 references

stochastic approximation

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model

0 references

Q3241581

0 references

Q4368722

0 references

Q3189557

0 references

Efficient Sampling Methods for Discrete Distributions

0 references

Sublinear optimization for machine learning

0 references

The Linear Programming Approach to Approximate Dynamic Programming

0 references

Q3270185

0 references

The value iteration algorithm is not strongly polynomial for discounted dynamic programming

0 references

Solving variational inequalities with Stochastic Mirror-Prox algorithm

0 references

Exponentiated gradient versus gradient descent for linear predictors

0 references

Q4421713

0 references

Robust Stochastic Approximation Approach to Stochastic Programming

0 references

Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes

0 references

Solving H-horizon, stationary Markov decision problems in time proportional to log (H)

0 references

An Efficient Method for Weighted Sampling without Replacement

0 references

A New Complexity Result on Solving the Markov Decision Problem

0 references

The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate

0 references

Identifiers

zbMATH Open document ID

1455.90148

0 references

DOI

10.1287/moor.2019.1000

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5119845

@@ Property / cites work @@
+Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model
+Normal rank
@@ Property / cites work @@
+Q3241581
@@ Property / cites work: Q3241581 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4368722
@@ Property / cites work: Q4368722 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3189557
@@ Property / cites work: Q3189557 / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient Sampling Methods for Discrete Distributions
+Normal rank
@@ Property / cites work @@
+Sublinear optimization for machine learning
@@ Property / cites work: Sublinear optimization for machine learning / rank @@
+Normal rank
@@ Property / cites work @@
+The Linear Programming Approach to Approximate Dynamic Programming
+Normal rank
@@ Property / cites work @@
+Q3270185
@@ Property / cites work: Q3270185 / rank @@
+Normal rank
@@ Property / cites work @@
+The value iteration algorithm is not strongly polynomial for discounted dynamic programming
+Normal rank
@@ Property / cites work @@
+Solving variational inequalities with Stochastic Mirror-Prox algorithm
+Normal rank
@@ Property / cites work @@
+Exponentiated gradient versus gradient descent for linear predictors
+Normal rank
@@ Property / cites work @@
+Q4421713
@@ Property / cites work: Q4421713 / rank @@
+Normal rank
@@ Property / cites work @@
+Robust Stochastic Approximation Approach to Stochastic Programming
+Normal rank
@@ Property / cites work @@
+Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes
+Normal rank
@@ Property / cites work @@
+Solving H-horizon, stationary Markov decision problems in time proportional to log (H)
+Normal rank
@@ Property / cites work @@
+An Efficient Method for Weighted Sampling without Replacement
+Normal rank
@@ Property / cites work @@
+A New Complexity Result on Solving the Markov Decision Problem
+Normal rank
@@ Property / cites work @@
+The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate
+Normal rank