שיטות פתרון אדפטיביות לתהליכי מרקוב עם קירוב פונקציונלי

תקציר מקורי באנגליתarXiv:2505.12037v2 Announce Type: replace Abstract: Learning the optimal policy for Markov decision process problems (MDPs) from samples is a fundamental problem in online and data-driven decision-making. Function approximations are usually deployed to handle large or infinite state-action space. In our work, we consider the MDP problems with function approximation and we develop a new algorithm to solve it efficiently. Our algorithm is based on a linear programming (LP) reformulation and repeatedly resolves the identified reduced linear system as new transition samples arrive. After the optimal basis is identified, we show that, after $N$ resolving rounds, the expected averaged iterate achieves an instance-dependent $\widetilde O(C_{\mathrm{inst}}/N)$ objective shortfall and signed constr