Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Randomized Linear Programming Solves the Discounted Markov Decision
  Problem In Nearly-Linear (Sometimes Sublinear) Running Time   We propose a novel randomized linear programming algorithm for approximating
the optimal policy of the discounted Markov decision problem. By leveraging the
value-policy duality and binary-tree data structures, the algorithm adaptively
samples state-action-state transitions and makes exponentiated primal-dual
updates. We show that it finds an $\epsilon$-optimal policy using nearly-linear
run time in the worst case. When the Markov decision process is ergodic and
specified in some special data formats, the algorithm finds an
$\epsilon$-optimal policy using run time linear in the total number of
state-action pairs, which is sublinear in the input size. These results provide
a new venue and complexity benchmarks for solving stochastic dynamic programs.

26
The categories of this paper are: bayes-an
6
The categories of this paper are: astro-ph
12
The categories of this paper are: nucl-th
22
The categories of this paper are: chao-dyn
21
The categories of this paper are: adap-org
32
The categories of this paper are: atom-ph
11
The categories of this paper are: hep-lat
0
The categories of this paper are: hep-ph
31
The categories of this paper are: ao-sci
33
The categories of this paper are: plasm-ph
35
The categories of this paper are: mtrl-th
15
The categories of this paper are: nucl-ex
13
The categories of this paper are: quant-ph
18
The categories of this paper are: econ
9
The categories of this paper are: nlin
30
The categories of this paper are: q-alg