Do there exist functions $g(\epsilon)$ and $h(\epsilon)$ defined for $\epsilon>0$ such that $g(\epsilon)\to 0$ and $h(\epsilon)\to 0$ as $\epsilon\to 0^+$ with the following property:


If $X$ and $Y$ are random variables with joint pmf $p(X,Y)$ satisfying
$$\mathbb{I}(X;Y)=\mathbb{E}\_{X,Y}\left(\log\frac{p(X,Y)}{p(X)\cdot p(Y)}\right)\leq\epsilon,$$
then $\mathbb P(\Lambda\_\epsilon)<h(\epsilon)$, where
$$\Lambda\_\epsilon:=\left\{(x,y):\frac{p(y)}{p(y|x)}\leq1-g(\epsilon)\right\}$$


First, I do a wrong analysis with $g(\epsilon)=1-e^{-\sqrt{\epsilon}}$ as follows:
\begin{align}
\mathbb{P}(\Lambda)&=\mathbb{P}\left(\frac{p(Y)}{p(Y|X)}\leq 1-g(\epsilon)\right)\nonumber\\
&=\mathbb{P}\left(\log\frac{p(Y)}{p(Y|X)}\leq \log (1-g(\epsilon))\right)\nonumber\\
&=\mathbb{P}\left(\log\frac{p(Y|X)}{p(Y)}\geq \log\frac{1}{1-g(\epsilon)}\right)\nonumber\\
&\overset{(a)}{\leq}\frac{\epsilon}{\log\frac{1}{1-g(\epsilon)}}=\sqrt{\epsilon}.
\end{align}
where $(a)$ comes from Markov inequality. This analysis is wrong because Markov inequality is correct only for non-negative random variables and $\log\frac{p(Y|X)}{p(Y)}$ is not necessarily non-negative. In addition, maybe Pinsker inequality could help you:
$$\frac{1}{2}\lVert p(x,y)-p(x)p(y)\rVert\_1^2\leq I(X;Y)\leq\epsilon$$
where $\lVert.\rVert\_1$ denotes total variation distance.



Does small expected value of a random variable show the small probability for its tail?
So you can recover what you want directly from the Pinsker inequality. 


Set $g(\epsilon)=\sqrt[4]\epsilon$. Let $p\_{ij}=\mathbb P(X=i,Y=j)$, $p\_i=\mathbb P(X=i)$ and $q\_j=\mathbb P(Y=j)$. 


Then 
$$
\mathbb P(\Lambda\_\epsilon)=\sum\_{(i,j)\in\Lambda\_\epsilon}p\_{i,j}.
$$
If $(i,j)\in\Lambda\_\epsilon$, then $p\_iq\_j/p\_{ij}<1-\sqrt[4]\epsilon$. That is $p\_iq\_j<p\_{ij}-\sqrt[4]\epsilon p\_{ij}$, which implies $|p\_iq\_j-p\_{ij}|>\sqrt[4]\epsilon p\_{ij}$. 
Hence if $(i,j)\in \Lambda\_\epsilon$, then $p\_{ij}<1/\sqrt[4]\epsilon |p\_iq\_j-p\_{ij}|$. 


Now 
\begin{align\*}
\mathbb P(\Lambda\_\epsilon)&=\sum\_{(i,j)\in\Lambda\_\epsilon}p\_{ij}\\
&<\frac 1{\sqrt[4]\epsilon}\sum\_{(i,j)\in\Lambda\_\epsilon}|p\_iq\_j-p\_{ij}|\\
&<\frac 1{\sqrt[4]\epsilon}\sum\_{i,j}|p\_iq\_j-p\_{ij}|\\
&=\epsilon^{-1/4}\|p\_iq\_j-p\_{ij}\|\_1<\epsilon^{-1/4}\sqrt{2\epsilon}=\sqrt 2\epsilon^{1/4}.
\end{align\*}


