In the paper "Concentration inequalities for Markov chains by Marton couplings and spectral methods", https://projecteuclid.org/euclid.ejp/1465067185, D. Paulin defines the pseudo-spectral gap for any finite Markov chain as follows. Let $P$ be an ergodic finite Markov chain represented by a row-stochastic matrix, and let $P^*$ denote its time reversal: $$ P^*(x,y) = \frac{ P(y,x) \pi(y)}{\pi(x)},$$ where $\pi$ is the (unique) stationary distribution of $P$. Then the pseudo-spectral gap of $P$ is defined as $$ \tilde\gamma(P):= \max_{k\ge1} \gamma( (P^*)^kP^k) / k $$ where $\gamma(\cdot)$ denotes the ordinary spectral gap of the reversible Markov chain supplied in the argument.

Now it is straightforward to efficiently compute lower bounds on $\tilde\gamma(P)$, and for many purposes this suffices. Suppose, however, one actually wanted to compute this quantity to some fixed precision. How would one effectively do that?

EDIT

My answer below shows that for any range $k\in[1,K]$, one gets both upper and lower bounds on $\tilde\gamma(P)$. However, the original question remains: If one wants to compute this quantity to within (say, additive) error $\epsilon$, how large must $K$ be behave as a function of $\epsilon$?