Given the costs and a feasible solution for a minimum cost flow problem on a countably infinite network, inverse optimization involves finding new costs that are close to the original ones and that make the given solution optimal. We study this problem using the weighted absolute sum metric to quantify closeness of cost vectors. We provide sufficient conditions under which known results from inverse optimization in minimum cost flow problems on finite networks extend to the countably infinite case. These conditions ensure that recent duality results on countably infinite linear programs can be applied to our setting. Specifically, they enable us to prove that the inverse optimization problem can be reformulated as a capacitated, minimum cost circulation problem on a countably infinite network. Finite‐dimensional truncations of this problem can be solved in polynomial time when the weights equal one, which yields an efficient solution method. The circulation problem can also be solved via the shadow simplex method, where each finite‐dimensional truncation is tackled using the usual network Simplex algorithm that is empirically known to be computationally efficient. We illustrate these results on an infinite horizon shortest path problem.
We study optimal transport for stationary stochastic processes taking values in finite spaces. In order to reflect the stationarity of the underlying processes, we restrict attention to stationary couplings, also known as joinings. The resulting optimal joining problem captures differences in the long-run average behavior of the processes of interest. We introduce estimators of both optimal joinings and the optimal joining cost, and establish consistency of the estimators under mild conditions. Furthermore, under stronger mixing assumptions we establish finite-sample error rates for the estimated optimal joining cost that extend the best known results in the iid case. We also extend the consistency and rate analysis to an entropy-penalized version of the optimal joining problem. Finally, we validate our convergence results empirically as well as demonstrate the computational advantage of the entropic problem in a simulation experiment.
more » « less- PAR ID:
- 10502448
- Publisher / Repository:
- Oxford University Press
- Date Published:
- Journal Name:
- Information and Inference: A Journal of the IMA
- Volume:
- 13
- Issue:
- 2
- ISSN:
- 2049-8772
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
Abstract -
more » « less
Summary The paper is concerned with inference for linear models with fixed regressors and weakly dependent stationary time series errors. Theoretically, we obtain asymptotic normality for the M-estimator of the regression parameter under mild conditions and establish a uniform Bahadur representation for recursive M-estimators. Methodologically, we extend the recently proposed self-normalized approach of Shao from stationary time series to the regression set-up, where the sequence of response variables is typically non-stationary in mean. Since the limiting distribution of the self-normalized statistic depends on the design matrix and its corresponding critical values are case dependent, we develop a simulation-based approach to approximate the critical values consistently. Through a simulation study, we demonstrate favourable finite sample performance of our method in comparison with a block-bootstrap-based approach. Empirical illustrations using two real data sets are also provided.
-
We consider the problem of offline reinforcement learning (RL) -- a well-motivated setting of RL that aims at policy optimization using only historical data. Despite its wide applicability, theoretical understandings of offline RL, such as its optimal sample complexity, remain largely open even in basic settings such as \emph{tabular} Markov Decision Processes (MDPs). In this paper, we propose Off-Policy Double Variance Reduction (OPDVR), a new variance reduction based algorithm for offline RL. Our main result shows that OPDVR provably identifies an ϵ-optimal policy with O˜(H2/dmϵ2) episodes of offline data in the finite-horizon stationary transition setting, where H is the horizon length and dm is the minimal marginal state-action distribution induced by the behavior policy. This improves over the best known upper bound by a factor of H. Moreover, we establish an information-theoretic lower bound of Ω(H2/dmϵ2) which certifies that OPDVR is optimal up to logarithmic factors. Lastly, we show that OPDVR also achieves rate-optimal sample complexity under alternative settings such as the finite-horizon MDPs with non-stationary transitions and the infinite horizon MDPs with discounted rewards.more » « less
-
more » « less
We consider the problem of using an autoregressive (AR) approximation to estimate the spectral density function and the
n ×n autocovariance matrix based on stationary dataX 1, … ,X n . The consistency of the autoregressive spectral density estimator has been proven since the 1970s under a linearity assumption. We extend these ideas to the nonlinear setting, and give an application to estimating then ×n autocovariance matrix. Under mild assumptions on the underlying dependence structure and the orderp of the fittedAR (p ) model, we are able to show that the autoregressive spectral estimate and the associated AR‐based autocovariance matrix estimator are consistent. We are also able to establish an explicit bound on the rate of convergence of the proposed estimators. -
more » « less
Abstract Optimizing the allocation of units into treatment groups can help researchers improve the precision of causal estimators and decrease costs when running factorial experiments. However, existing optimal allocation results typically assume a super-population model and that the outcome data come from a known family of distributions. Instead, we focus on randomization-based causal inference for the finite-population setting, which does not require model specifications for the data or sampling assumptions. We propose exact theoretical solutions for optimal allocation in
{2}^{K}
